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