1 /* vim:set shiftwidth=4 ts=8: */
2
3
4 /*************************************************************************
5 * Copyright (c) 2011 AT&T Intellectual Property
6 * All rights reserved. This program and the accompanying materials
7 * are made available under the terms of the Eclipse Public License v1.0
8 * which accompanies this distribution, and is available at
9 * http://www.eclipse.org/legal/epl-v10.html
10 *
11 * Contributors: See CVS logs. Details at http://www.graphviz.org/
12 *************************************************************************/
13
14 /*
15 * Tapered edges, based on lines.ps written by Denis Moskowitz.
16 */
17
18 #include "config.h"
19
20 #include <math.h>
21 #include <stdio.h>
22 #include <stdlib.h>
23 #include <types.h>
24 #include <memory.h>
25 #include <logic.h>
26 #include <agxbuf.h>
27 #include <utils.h>
28
29 /* sample point size; should be dynamic based on dpi or under user control */
30 #define BEZIERSUBDIVISION 20
31
32 /* initial guess of array size */
33 #define INITSZ 2000
34
35 /* convert degrees to radians and vice versa */
36 #ifndef M_PI
37 #define M_PI 3.14159265358979323846
38 #endif
39 #define D2R(d) (M_PI*(d)/180.0)
40 #define R2D(r) (180.0*(r)/M_PI)
41
42 static double currentmiterlimit = 10.0;
43
44 #define moveto(p,x,y) addto(p,x,y)
45 #define lineto(p,x,y) addto(p,x,y)
46
addto(stroke_t * p,double x,double y)47 static void addto (stroke_t* p, double x, double y)
48 {
49 pointf pt;
50
51 if (p->nvertices >= p->flags) {
52 p->flags =+ INITSZ;
53 p->vertices = RALLOC(p->flags,p->vertices,pointf);
54 }
55 pt.x = x;
56 pt.y = y;
57 p->vertices[p->nvertices++] = pt;
58 }
59
arcn(stroke_t * p,double x,double y,double r,double a1,double a2)60 static void arcn (stroke_t* p, double x, double y, double r, double a1, double a2)
61 {
62 double theta;
63 int i;
64
65 addto (p, x+r*cos(a1), y+r*sin(a1));
66 if (r == 0) return;
67 while (a2 > a1) a2 -= 2*M_PI;
68 theta = a1 - a2;
69 while (theta > 2*M_PI) theta -= 2*M_PI;
70 theta /= (BEZIERSUBDIVISION-1);
71 for (i = 1; i < BEZIERSUBDIVISION; i++)
72 addto (p, x+r*cos(a1-i*theta), y+r*sin(a1-i*theta));
73 }
74
75 #if 0
76 static void closepath (stroke_t* p)
77 {
78 pointf pt = p->vertices[0];
79
80 addto (p, pt.x, pt.y);
81 if (p->flags > p->nvertices)
82 p->vertices = RALLOC(p->nvertices,p->vertices,pointf);
83 }
84 #endif
85
86 /*
87 * handle zeros
88 */
myatan(double y,double x)89 static double myatan (double y, double x)
90 {
91 double v;
92 if ((x == 0) && (y == 0))
93 return 0;
94 else {
95 v = atan2 (y, x);
96 if (v >= 0) return v;
97 else return (v + 2*M_PI);
98 }
99 }
100
101 /*
102 * mod that accepts floats and makes negatives positive
103 */
mymod(double original,double modulus)104 static double mymod (double original, double modulus)
105 {
106 double v;
107 if ((original < 0) || (original >= modulus)) {
108 v = -floor(original/modulus);
109 return ((v*modulus) + original);
110 }
111 return original;
112 }
113
114 typedef struct {
115 double x;
116 double y;
117 double lengthsofar;
118 char type;
119 double dir;
120 double lout;
121 int bevel;
122 double dir2;
123 } pathpoint;
124
125 typedef struct {
126 pathpoint* pts;
127 int cnt;
128 int sz;
129 } vararr_t;
130
131
132 static vararr_t*
newArr(void)133 newArr (void)
134 {
135 vararr_t* arr = NEW(vararr_t);
136
137 arr->cnt = 0;
138 arr->sz = INITSZ;
139 arr->pts = N_NEW(INITSZ,pathpoint);
140
141 return arr;
142 }
143
144 static void
insertArr(vararr_t * arr,pointf p,double l)145 insertArr (vararr_t* arr, pointf p, double l)
146 {
147 if (arr->cnt >= arr->sz) {
148 arr->sz *= 2;
149 arr->pts = RALLOC(arr->sz,arr->pts,pathpoint);
150 }
151
152 arr->pts[arr->cnt].x = p.x;
153 arr->pts[arr->cnt].y = p.y;
154 arr->pts[arr->cnt++].lengthsofar = l;
155 }
156
157 #ifdef DEBUG
158 static void
printArr(vararr_t * arr,FILE * fp)159 printArr (vararr_t* arr, FILE* fp)
160 {
161 int i;
162 pathpoint pt;
163
164 fprintf (fp, "cnt %d sz %d\n", arr->cnt, arr->sz);
165 for (i = 0; i < arr->cnt; i++) {
166 pt = arr->pts[i];
167 fprintf (fp, " [%d] x %.02f y %.02f d %.02f\n", i, pt.x, pt.y, pt.lengthsofar);
168 }
169 }
170 #endif
171
172 static void
fixArr(vararr_t * arr)173 fixArr (vararr_t* arr)
174 {
175 if (arr->sz > arr->cnt)
176 arr->pts = RALLOC(arr->cnt,arr->pts,pathpoint);
177 }
178
179 static void
freeArr(vararr_t * arr)180 freeArr (vararr_t* arr)
181 {
182 free (arr->pts);
183 free (arr);
184 }
185
l2dist(pointf p0,pointf p1)186 static double l2dist (pointf p0, pointf p1)
187 {
188 double delx = p0.x - p1.x;
189 double dely = p0.y - p1.y;
190 return sqrt(delx*delx + dely*dely);
191 }
192
193 /* analyze current path, creating pathpoints array
194 * turn all curves into lines
195 */
pathtolines(bezier * bez,double initwid)196 static vararr_t* pathtolines (bezier* bez, double initwid)
197 {
198 int i, j, step;
199 double seglen, linelen = 0;
200 vararr_t* arr = newArr();
201 pointf p0, p1, V[4];
202 int n = bez->size;
203 pointf* A = bez->list;
204
205 insertArr (arr, A[0], 0);
206 V[3] = A[0];
207 for (i = 0; i + 3 < n; i += 3) {
208 V[0] = V[3];
209 for (j = 1; j <= 3; j++)
210 V[j] = A[i + j];
211 p0 = V[0];
212 for (step = 1; step <= BEZIERSUBDIVISION; step++) {
213 p1 = Bezier(V, 3, (double) step / BEZIERSUBDIVISION, NULL, NULL);
214 seglen = l2dist(p0, p1);
215 /* If initwid is large, this may never happen, so turn off. I assume this is to prevent
216 * too man points or too small a movement. Perhaps a better test can be made, but for now
217 * we turn it off.
218 */
219 /* if (seglen > initwid/10) { */
220 linelen += seglen;
221 insertArr (arr, p1, linelen);
222 /* } */
223 p0 = p1;
224 }
225 }
226 fixArr (arr);
227 #ifdef DEBUG
228 printArr (arr, stderr);
229 #endif
230 return arr;
231 }
232
drawbevel(double x,double y,double lineout,int forward,double dir,double dir2,int linejoin,stroke_t * p)233 static void drawbevel(double x, double y, double lineout, int forward, double dir, double dir2, int linejoin, stroke_t* p)
234 {
235 double a, a1, a2;
236
237 if (forward) {
238 a1 = dir;
239 a2 = dir2;
240 } else {
241 a1 = dir2;
242 a2 = dir;
243 }
244 if (linejoin == 1) {
245 a = a1 - a2;
246 if (a <= D2R(0.1)) a += D2R(360);
247 if (a < D2R(180)) {
248 a1 = a + a2;
249 arcn (p,x,y,lineout,a1,a2);
250 } else {
251 lineto (p, x + lineout*cos(a2), x + lineout*sin(a2));
252 }
253 } else {
254 lineto (p, x + lineout*cos(a2), x + lineout*sin(a2));
255 }
256 }
257
258 typedef double (*radfunc_t) (double curlen, double totallen, double initwid);
259
260 /* taper:
261 * Given a B-spline bez, returns a polygon that represents spline as a tapered
262 * edge, starting with width initwid.
263 * The radfunc determines the half-width along the curve. Typically, this will
264 * decrease from initwid to 0 as the curlen goes from 0 to totallen.
265 * The linejoin and linecap parameters have roughly the same meaning as in postscript.
266 * - linejoin = 0 or 1
267 * - linecap = 0 or 1 or 2
268 *
269 * Calling function needs to free the allocated stoke_t.
270 */
taper(bezier * bez,radfunc_t radfunc,double initwid,int linejoin,int linecap)271 stroke_t* taper (bezier* bez, radfunc_t radfunc, double initwid, int linejoin, int linecap)
272 {
273 int i, l, n;
274 int pathcount, bevel;
275 double direction=0, direction_2=0;
276 vararr_t* arr = pathtolines (bez, initwid);
277 pathpoint* pathpoints;
278 pathpoint cur_point, last_point, next_point;
279 double x=0, y=0, dist;
280 double nx, ny, ndir;
281 double lx, ly, ldir;
282 double lineout=0, linerad=0, linelen=0;
283 double theta, phi;
284 stroke_t* p;
285
286 pathcount = arr->cnt;
287 pathpoints = arr->pts;
288 linelen = pathpoints[pathcount-1].lengthsofar;
289
290 /* determine miter and bevel points and directions */
291 for (i = 0; i < pathcount; i++) {
292 l = mymod(i-1,pathcount);
293 n = mymod(i+1,pathcount);
294
295 cur_point = pathpoints[i];
296 x = cur_point.x;
297 y = cur_point.y;
298 dist = cur_point.lengthsofar;
299
300 next_point = pathpoints[n];
301 nx = next_point.x;
302 ny = next_point.y;
303 ndir = myatan (ny-y, nx-x);
304
305 last_point = pathpoints[l];
306 lx = last_point.x;
307 ly = last_point.y;
308 ldir = myatan (ly-y, lx-x);
309
310 bevel = FALSE;
311 direction_2 = 0;
312
313 /* effective line radius at this point */
314 linerad = radfunc(dist, linelen, initwid);
315
316 if ((i == 0) || (i == pathcount-1)) {
317 lineout = linerad;
318 if (i == 0) {
319 direction = ndir + D2R(90);
320 if (linecap == 2) {
321 x -= cos(ndir)*lineout;
322 y -= sin(ndir)*lineout;
323 }
324 } else {
325 direction = ldir - D2R(90);
326 if (linecap == 2) {
327 x -= cos(ldir)*lineout;
328 y -= sin(ldir)*lineout;
329 }
330 }
331 direction_2 = direction;
332 } else {
333 theta = ndir-ldir;
334 if (theta < 0) {
335 theta += D2R(360);
336 }
337 phi = D2R(90)-(theta/2);
338 /* actual distance to junction point */
339 if (cos(phi) == 0) {
340 lineout = 0;
341 } else {
342 lineout = linerad/(cos(phi));
343 }
344 /* direction to junction point */
345 direction = ndir+D2R(90)+phi;
346 if ((0 != linejoin) || (lineout > currentmiterlimit * linerad)) {
347 bevel = TRUE;
348 lineout = linerad;
349 direction = mymod(ldir-D2R(90),D2R(360));
350 direction_2 = mymod(ndir+D2R(90),D2R(360));
351 if (i == pathcount-1) {
352 bevel = FALSE;
353 }
354 } else {
355 direction_2 = direction;
356 }
357 }
358 pathpoints[i].x = x;
359 pathpoints[i].y = y;
360 pathpoints[i].lengthsofar = dist;
361 pathpoints[i].type = 'l';
362 pathpoints[i].dir = direction;
363 pathpoints[i].lout = lineout;
364 pathpoints[i].bevel = bevel;
365 pathpoints[i].dir2 = direction_2;
366 }
367
368 /* draw line */
369 p = NEW(stroke_t);
370 /* side 1 */
371 for (i = 0; i < pathcount; i++) {
372 cur_point = pathpoints[i];
373 x = cur_point.x;
374 y = cur_point.y;
375 direction = cur_point.dir;
376 lineout = cur_point.lout;
377 bevel = cur_point.bevel;
378 direction_2 = cur_point.dir2;
379 if (i == 0) {
380 moveto (p, x+cos(direction)*lineout, y+sin(direction)*lineout);
381 } else {
382 lineto (p, x+cos(direction)*lineout, y+sin(direction)*lineout);
383 }
384 if (bevel) {
385 drawbevel (x, y, lineout, TRUE, direction, direction_2, linejoin, p);
386 }
387 }
388 /* end circle as needed */
389 if (linecap == 1) {
390 arcn (p, x,y,lineout,direction,direction+D2R(180));
391 } else {
392 direction += D2R(180);
393 lineto (p, x+cos(direction)*lineout, y+sin(direction)*lineout);
394 }
395 /* side 2 */
396 for (i = pathcount-2; i >= 0; i--) {
397 cur_point = pathpoints[i];
398 x = cur_point.x;
399 y = cur_point.y;
400 direction = cur_point.dir + D2R(180);
401 lineout = cur_point.lout;
402 bevel = cur_point.bevel;
403 direction_2 = cur_point.dir2 + D2R(180);
404 lineto (p, x+cos(direction_2)*lineout, y+sin(direction_2)*lineout);
405 if (bevel) {
406 drawbevel (x, y, lineout, FALSE, direction, direction_2, linejoin, p);
407 }
408 }
409 /* start circle if needed */
410 if (linecap == 1) {
411 arcn (p, x,y,lineout,direction,direction+D2R(180));
412 }
413 /* closepath (p); */
414 freeArr (arr);
415 return p;
416 }
417
halffunc(double curlen,double totallen,double initwid)418 static double halffunc (double curlen, double totallen, double initwid)
419 {
420 return ((1 - (curlen/totallen))*initwid/2.0);
421 }
422
taper0(bezier * bez,double initwid)423 stroke_t* taper0 (bezier* bez, double initwid)
424 {
425 return taper(bez, halffunc, initwid, 0, 0);
426 }
427
428 #ifdef TEST
429 static pointf pts[] = {
430 {100,100},
431 {150,150},
432 {200,100},
433 {250,200},
434 };
435
main()436 main ()
437 {
438 stroke_t* sp;
439 bezier bez;
440 int i;
441
442 bez.size = sizeof(pts)/sizeof(pointf);
443 bez.list = pts;
444 sp = taper0 (&bez, 20);
445 printf ("newpath\n");
446 printf ("%.02f %.02f moveto\n", sp->vertices[0].x, sp->vertices[0].y);
447 for (i=1; i<sp->nvertices; i++)
448 printf ("%.02f %.02f lineto\n", sp->vertices[i].x, sp->vertices[i].y);
449 printf ("fill showpage\n");
450 }
451 #endif
452