1 #include <stdlib.h>
2 #include <stdio.h>
3 #include <math.h>
4 #include "../gfxdevice.h"
5 #include "../gfxtools.h"
6 #include "poly.h"
7 #include "wind.h"
8 #include "convert.h"
9 
10 /* notice: left/right for a coordinate system where y goes up, not down */
11 typedef enum {LEFT=0, RIGHT=1} leftright_t;
12 
13 /* factor that determines into how many line fragments a spline is converted */
14 #define SUBFRACTION (2.4)
15 
16 // spline equation:
17 // s(t) = t*t*x2 + 2*t*(1-t)*cx + (1-t)*(1-t)*x1
18 //
19 // s(0.5) = 0.25*x2 + 0.5*cx + 0.25*x1
20 // ds(t)/dt = 2*t*x2 + (2-2t)*cx + (2t-2)*x1
21 // ds(0) = 2*(cx-x1)
22 
draw_arc(gfxdrawer_t * draw,double x,double y,double a1,double a2,double r)23 static void draw_arc(gfxdrawer_t*draw, double x, double y, double a1, double a2, double r)
24 {
25     if(a2<a1) a2+=M_PI*2;
26 
27     double d = (a2-a1);
28     int steps = ceil(8*d/(M_PI*2)); // we use 8 splines for a full circle
29     if(!steps) return;
30 
31     int t;
32     double step = (a2-a1)/steps;
33     double lastx = x+cos(a1)*r;
34     double lasty = y+sin(a1)*r;
35 
36     /* we could probably build a table for this- there are only 8
37        possible values for step */
38     double r2 = r*(2-sqrt(0.5+0.5*cos(step)));
39 
40     draw->lineTo(draw, x+cos(a1)*r,y+sin(a1)*r);
41     for(t=1;t<=steps;t++) {
42 	double a = a1 + t*step;
43 	double c = cos(a)*r;
44 	double s = sin(a)*r;
45 	double xx = c + x;
46 	double yy = s + y;
47 	double dx = x + cos(a-step/2)*r2;
48 	double dy = y + sin(a-step/2)*r2;
49 	draw->splineTo(draw, dx, dy, xx, yy);
50 	lastx = xx;
51 	lasty = yy;
52     }
53 }
54 
draw_single_stroke(gfxpoint_t * p,int num,gfxdrawer_t * draw,double width,gfx_capType cap,gfx_joinType join,double limit)55 static void draw_single_stroke(gfxpoint_t*p, int num, gfxdrawer_t*draw, double width, gfx_capType cap, gfx_joinType join, double limit)
56 {
57     width/=2;
58     if(width<=0)
59 	width = 0.05;
60 
61     /* remove duplicate points */
62     int s=1,t;
63     gfxpoint_t last = p[0];
64     for(t=1;t<num;t++) {
65 	if(p[t].x != last.x || p[t].y != last.y) {
66 	    p[s++] = last = p[t];
67 	}
68     }
69     num = s;
70 
71     char closed = (num>2 && p[0].x == p[num-1].x && p[0].y == p[num-1].y);
72 
73     int start = 0;
74     int end = num-1;
75     int incr = 1;
76     int pos = 0;
77 
78     double lastw=0;
79     /* iterate through the points two times: first forward, then backward,
80        adding a stroke outline to the right side and line caps after each
81        pass */
82     int pass;
83     for(pass=0;pass<2;pass++) {
84 	if(closed) {
85 	    double dx = p[end].x - p[end-incr].x;
86 	    double dy = p[end].y - p[end-incr].y;
87 	    lastw = atan2(dy,dx);
88 	    if(lastw<0) lastw+=M_PI*2;
89 	}
90 
91 	int pos;
92 	for(pos=start;pos!=end;pos+=incr) {
93 	    //printf("%d) %.2f %.2f\n", pos, p[pos].x, p[pos].y);
94 	    double dx = p[pos+incr].x - p[pos].x;
95 	    double dy = p[pos+incr].y - p[pos].y;
96 	    double w = atan2(dy,dx);
97 	    if(w<0) w+=M_PI*2;
98 
99 	    if(closed || pos!=start) {
100 		double d = w-lastw;
101 		leftright_t turn;
102 		if(d>=0 && d<M_PI) turn=LEFT;
103 		else if(d<0 && d>-M_PI) turn=RIGHT;
104 		else if(d>=M_PI) {turn=RIGHT;}
105 		else if(d<=-M_PI) {turn=LEFT;d+=M_PI*2;}
106 		else {assert(0);}
107 		if(turn!=LEFT || join==gfx_joinBevel) {
108 		    // nothing to do. bevel joins are easy
109 		} else if(join==gfx_joinRound) {
110 		    draw_arc(draw, p[pos].x, p[pos].y, lastw-M_PI/2, w-M_PI/2, width);
111 		} else if(join==gfx_joinMiter) {
112 		    double xw = M_PI/2 - d/2;
113 		    if(xw>0) {
114 			double r2 = 1.0 / sin(M_PI/2-d/2);
115 			if(r2 < limit) {
116 			    r2 *= width;
117 			    double addx = cos(lastw-M_PI/2+d/2)*r2;
118 			    double addy = sin(lastw-M_PI/2+d/2)*r2;
119 			    draw->lineTo(draw, p[pos].x+addx, p[pos].y+addy);
120 			}
121 		    }
122 		}
123 	    }
124 
125 	    double addx = cos(w-M_PI/2)*width;
126 	    double addy = sin(w-M_PI/2)*width;
127 	    draw->lineTo(draw, p[pos].x+addx, p[pos].y+addy);
128 	    double px2 = p[pos+incr].x + addx;
129 	    double py2 = p[pos+incr].y + addy;
130 	    draw->lineTo(draw, p[pos+incr].x+addx, p[pos+incr].y+addy);
131 	    lastw = w;
132 	}
133 
134 	if(closed) {
135 	    draw->close(draw);
136 	} else {
137 	    /* draw stroke ends. We draw duplicates of some points here. The drawer
138 	       implementation should be smart enough to remove them. */
139 	    double c = cos(lastw-M_PI/2)*width;
140 	    double s = sin(lastw-M_PI/2)*width;
141 	    if(cap == gfx_capButt) {
142 		draw->lineTo(draw, p[pos].x+c, p[pos].y+s);
143 		draw->lineTo(draw, p[pos].x-c, p[pos].y-s);
144 	    } else if(cap == gfx_capRound) {
145 		draw_arc(draw, p[pos].x, p[pos].y, lastw-M_PI/2, lastw+M_PI/2, width);
146 	    } else if(cap == gfx_capSquare) {
147 		double c = cos(lastw-M_PI/2)*width;
148 		double s = sin(lastw-M_PI/2)*width;
149 		draw->lineTo(draw, p[pos].x+c, p[pos].y+s);
150 		draw->lineTo(draw, p[pos].x+c-s, p[pos].y+s+c);
151 		draw->lineTo(draw, p[pos].x-c-s, p[pos].y-s+c);
152 		draw->lineTo(draw, p[pos].x-c, p[pos].y-s);
153 	    }
154 	    lastw += M_PI; // for dots
155 	}
156 	start=num-1;
157 	end=0;
158 	incr=-1;
159     }
160     if(!closed)
161 	draw->close(draw);
162 }
163 
draw_stroke(gfxline_t * start,gfxdrawer_t * draw,double width,gfx_capType cap,gfx_joinType join,double miterLimit)164 void draw_stroke(gfxline_t*start, gfxdrawer_t*draw, double width, gfx_capType cap, gfx_joinType join, double miterLimit)
165 {
166     if(!start)
167 	return;
168     assert(start->type == gfx_moveTo);
169     gfxline_t*line = start;
170     // measure array size
171     int size = 0;
172     int pos = 0;
173     double lastx,lasty;
174     while(line) {
175 	if(line->type == gfx_moveTo) {
176 	    if(pos>size) size = pos;
177 	    pos++;
178 	} else if(line->type == gfx_lineTo) {
179 	    pos++;
180 	} else if(line->type == gfx_splineTo) {
181             int parts = (int)(sqrt(fabs(line->x-2*line->sx+lastx) + fabs(line->y-2*line->sy+lasty))*SUBFRACTION);
182             if(!parts) parts = 1;
183 	    pos+=parts+1;
184 	}
185 	lastx = line->x;
186 	lasty = line->y;
187 	line = line->next;
188     }
189     if(pos>size) size = pos;
190     if(!size) return;
191 
192     gfxpoint_t* points = malloc(sizeof(gfxpoint_t)*size);
193     line = start;
194     pos = 0;
195     while(line) {
196 	if(line->type == gfx_moveTo) {
197 	    if(pos)
198 		draw_single_stroke(points, pos, draw, width, cap, join, miterLimit);
199 	    pos = 0;
200 	} else if(line->type == gfx_splineTo) {
201             int parts = (int)(sqrt(fabs(line->x-2*line->sx+lastx) + fabs(line->y-2*line->sy+lasty))*SUBFRACTION);
202             if(!parts) parts = 1;
203 	    double stepsize = 1.0/parts;
204             int i;
205 	    for(i=0;i<parts;i++) {
206 		double t = (double)i*stepsize;
207 		points[pos].x = (line->x*t*t + 2*line->sx*t*(1-t) + lastx*(1-t)*(1-t));
208 		points[pos].y = (line->y*t*t + 2*line->sy*t*(1-t) + lasty*(1-t)*(1-t));
209 		pos++;
210 	    }
211 	}
212 	lastx = points[pos].x = line->x;
213 	lasty = points[pos].y = line->y;
214 	pos++;
215 	line = line->next;
216     }
217     if(pos) draw_single_stroke(points, pos, draw, width, cap, join, miterLimit);
218     free(points);
219 }
220 
221 static windcontext_t onepolygon = {1};
gfxpoly_from_stroke(gfxline_t * line,gfxcoord_t width,gfx_capType cap_style,gfx_joinType joint_style,gfxcoord_t miterLimit,double gridsize)222 gfxpoly_t* gfxpoly_from_stroke(gfxline_t*line, gfxcoord_t width, gfx_capType cap_style, gfx_joinType joint_style, gfxcoord_t miterLimit, double gridsize)
223 {
224     gfxdrawer_t d;
225     gfxdrawer_target_poly(&d, gridsize);
226     draw_stroke(line, &d, width, cap_style, joint_style, miterLimit);
227     gfxpoly_t*poly = (gfxpoly_t*)d.result(&d);
228     assert(gfxpoly_check(poly, 1));
229     gfxpoly_t*poly2 = gfxpoly_process(poly, 0, &windrule_circular, &onepolygon, 0);
230     gfxpoly_destroy(poly);
231     return poly2;
232 }
233 
234