Graphviz  2.41.20170921.2350
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 #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 
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 
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)
83 }
84 #endif
85 
86 /*
87  * handle zeros
88  */
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  */
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 {
127  int cnt;
128  int sz;
129 } vararr_t;
130 
131 
132 static vararr_t*
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
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
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
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
180 freeArr (vararr_t* arr)
181 {
182  free (arr->pts);
183  free (arr);
184 }
185 
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  */
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 
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:121
#define N_NEW(n, t)
Definition: memory.h:36
int size
Definition: types.h:110
#define D2R(d)
Definition: taper.c:39
double(* radfunc_t)(double, double, double)
Definition: emit.c:2241
char type
Definition: taper.c:118
pathpoint * pts
Definition: taper.c:126
Definition: geom.h:28
double dir
Definition: taper.c:119
#define INITSZ
Definition: taper.c:33
pointf * vertices
Definition: types.h:161
int sz
Definition: taper.c:128
double lout
Definition: taper.c:120
double y
Definition: geom.h:28
int cnt
Definition: taper.c:127
stroke_t * taper(bezier *, double(*radfunc_t)(double, double, double), double initwid, int linejoin, int linecap)
Definition: taper.c:271
pointf * list
Definition: types.h:109
#define moveto(p, x, y)
Definition: taper.c:44
int flags
Definition: types.h:160
int nvertices
Definition: types.h:159
double y
Definition: taper.c:116
pointf Bezier(pointf *V, int degree, double t, pointf *Left, pointf *Right)
Definition: utils.c:221
#define NULL
Definition: logic.h:39
double x
Definition: geom.h:28
Definition: types.h:108
#define lineto(p, x, y)
Definition: taper.c:45
double lengthsofar
Definition: taper.c:117
#define M_PI
Definition: arith.h:77
#define BEZIERSUBDIVISION
Definition: taper.c:30
double dist(Site *s, Site *t)
Definition: site.c:41
double dir2
Definition: taper.c:122
#define FALSE
Definition: cgraph.h:35
int main(int argc, char **argv)
Definition: dot.c:95
stroke_t * taper0(bezier *bez, double initwid)
Definition: taper.c:423
#define NEW(t)
Definition: memory.h:35
#define TRUE
Definition: cgraph.h:38
double x
Definition: taper.c:115