Graphviz  2.39.20141217.0545
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 typedef struct {
117  double x;
118  double y;
119  double lengthsofar;
120  char type;
121  double dir;
122  double lout;
123  int bevel;
124  double dir2;
125 } pathpoint;
126 
127 typedef struct {
129  int cnt;
130  int sz;
131 } vararr_t;
132 
133 
134 static vararr_t*
135 newArr (void)
136 {
137  vararr_t* arr = NEW(vararr_t);
138 
139  arr->cnt = 0;
140  arr->sz = INITSZ;
141  arr->pts = N_NEW(INITSZ,pathpoint);
142 
143  return arr;
144 }
145 
146 static void
147 insertArr (vararr_t* arr, pointf p, double l)
148 {
149  if (arr->cnt >= arr->sz) {
150  arr->sz *= 2;
151  arr->pts = RALLOC(arr->sz,arr->pts,pathpoint);
152  }
153 
154  arr->pts[arr->cnt].x = p.x;
155  arr->pts[arr->cnt].y = p.y;
156  arr->pts[arr->cnt++].lengthsofar = l;
157 }
158 
159 #ifdef DEBUG
160 static void
161 printArr (vararr_t* arr, FILE* fp)
162 {
163  int i;
164  pathpoint pt;
165 
166  fprintf (fp, "cnt %d sz %d\n", arr->cnt, arr->sz);
167  for (i = 0; i < arr->cnt; i++) {
168  pt = arr->pts[i];
169  fprintf (fp, " [%d] x %.02f y %.02f d %.02f\n", i, pt.x, pt.y, pt.lengthsofar);
170  }
171 }
172 #endif
173 
174 static void
175 fixArr (vararr_t* arr)
176 {
177  if (arr->sz > arr->cnt)
178  arr->pts = RALLOC(arr->cnt,arr->pts,pathpoint);
179 }
180 
181 static void
182 freeArr (vararr_t* arr)
183 {
184  free (arr->pts);
185  free (arr);
186 }
187 
188 static double l2dist (pointf p0, pointf p1)
189 {
190  double delx = p0.x - p1.x;
191  double dely = p0.y - p1.y;
192  return sqrt(delx*delx + dely*dely);
193 }
194 
195 /* analyze current path, creating pathpoints array
196  * turn all curves into lines
197  */
198 static vararr_t* pathtolines (bezier* bez, double initwid)
199 {
200  int i, j, step;
201  double seglen, linelen = 0;
202  vararr_t* arr = newArr();
203  pointf p0, p1, V[4];
204  int n = bez->size;
205  pointf* A = bez->list;
206 
207  insertArr (arr, A[0], 0);
208  V[3] = A[0];
209  for (i = 0; i + 3 < n; i += 3) {
210  V[0] = V[3];
211  for (j = 1; j <= 3; j++)
212  V[j] = A[i + j];
213  p0 = V[0];
214  for (step = 1; step <= BEZIERSUBDIVISION; step++) {
215  p1 = Bezier(V, 3, (double) step / BEZIERSUBDIVISION, NULL, NULL);
216  seglen = l2dist(p0, p1);
217  /* If initwid is large, this may never happen, so turn off. I assume this is to prevent
218  * too man points or too small a movement. Perhaps a better test can be made, but for now
219  * we turn it off.
220  */
221  /* if (seglen > initwid/10) { */
222  linelen += seglen;
223  insertArr (arr, p1, linelen);
224  /* } */
225  p0 = p1;
226  }
227  }
228  fixArr (arr);
229  /* printArr (arr, stderr); */
230  return arr;
231 }
232 
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  */
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 
418 static double halffunc (double curlen, double totallen, double initwid)
419 {
420  return ((1 - (curlen/totallen))*initwid/2.0);
421 }
422 
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 
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
#define RALLOC(size, ptr, type)
Definition: memory.h:42
int bevel
Definition: taper.c:123
#define N_NEW(n, t)
Definition: memory.h:36
int size
Definition: types.h:110
#define D2R(d)
Definition: taper.c:41
char type
Definition: taper.c:120
pathpoint * pts
Definition: taper.c:128
Definition: geom.h:30
stroke_t * taper0(bezier *bez, double initwid)
Definition: taper.c:423
double dir
Definition: taper.c:121
double(* radfunc_t)(double curlen, double totallen, double initwid)
Definition: taper.c:258
#define INITSZ
Definition: taper.c:35
pointf * vertices
Definition: types.h:157
int sz
Definition: taper.c:130
void free()
double lout
Definition: taper.c:122
int i
Definition: gvdevice.c:448
double y
Definition: geom.h:30
int cnt
Definition: taper.c:129
pointf * list
Definition: types.h:109
#define moveto(p, x, y)
Definition: taper.c:46
int flags
Definition: types.h:156
int nvertices
Definition: types.h:155
double y
Definition: taper.c:118
#define M_PI
Definition: taper.c:39
pointf Bezier(pointf *V, int degree, double t, pointf *Left, pointf *Right)
Definition: utils.c:219
#define NULL
Definition: logic.h:50
stroke_t * taper(bezier *bez, radfunc_t radfunc, double initwid, int linejoin, int linecap)
Definition: taper.c:271
double x
Definition: geom.h:30
Definition: types.h:108
#define lineto(p, x, y)
Definition: taper.c:47
double lengthsofar
Definition: taper.c:119
#define BEZIERSUBDIVISION
Definition: taper.c:32
double dist(Site *s, Site *t)
Definition: site.c:41
double dir2
Definition: taper.c:124
#define FALSE
Definition: cgraph.h:24
int main(int argc, char **argv)
Definition: dot.c:153
#define NEW(t)
Definition: memory.h:35
#define TRUE
Definition: cgraph.h:27
double x
Definition: taper.c:117