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
42static 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
47static 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
60static 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
76static 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 */
89static 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 */
104static 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
114typedef 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
125typedef struct {
126 pathpoint* pts;
127 int cnt;
128 int sz;
129} vararr_t;
130
131
132static vararr_t*
133newArr (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
144static void
145insertArr (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
158static void
159printArr (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
172static void
173fixArr (vararr_t* arr)
174{
175 if (arr->sz > arr->cnt)
176 arr->pts = RALLOC(arr->cnt,arr->pts,pathpoint);
177}
178
179static void
180freeArr (vararr_t* arr)
181{
182 free (arr->pts);
183 free (arr);
184}
185
186static 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 */
196static 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
233static 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
258typedef 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 */
271stroke_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
418static double halffunc (double curlen, double totallen, double initwid)
419{
420 return ((1 - (curlen/totallen))*initwid/2.0);
421}
422
423stroke_t* taper0 (bezier* bez, double initwid)
424{
425 return taper(bez, halffunc, initwid, 0, 0);
426}
427
428#ifdef TEST
429static pointf pts[] = {
430 {100,100},
431 {150,150},
432 {200,100},
433 {250,200},
434};
435
436main ()
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