Graphviz 13.1.3~dev.20250831.0023
Loading...
Searching...
No Matches
taper.c
Go to the documentation of this file.
1
3/*************************************************************************
4 * Copyright (c) 2011 AT&T Intellectual Property
5 * All rights reserved. This program and the accompanying materials
6 * are made available under the terms of the Eclipse Public License v1.0
7 * which accompanies this distribution, and is available at
8 * https://www.eclipse.org/legal/epl-v10.html
9 *
10 * Contributors: Details at https://graphviz.org
11 *************************************************************************/
12
13/*
14 * Tapered edges, based on lines.ps written by Denis Moskowitz.
15 */
16
17#include "config.h"
18#include <assert.h>
19#include <math.h>
20#include <stdbool.h>
21#include <stdint.h>
22#include <stdio.h>
23#include <stdlib.h>
24#include <types.h>
25#include <common/render.h>
26#include <common/utils.h>
27#include <util/agxbuf.h>
28#include <util/alloc.h>
29#include <util/list.h>
30#include <util/prisize_t.h>
31
32#ifdef DEBUG
33enum { debug = 1 };
34#else
35enum { debug = 0 };
36#endif
37
38 /* sample point size; should be dynamic based on dpi or under user control */
39#define BEZIERSUBDIVISION 20
40
41 /* convert degrees to radians and vice versa */
42#ifndef M_PI
43#define M_PI 3.14159265358979323846
44#endif
45#define D2R(d) (M_PI*(d)/180.0)
46#define R2D(r) (180.0*(r)/M_PI)
47
48static double currentmiterlimit = 10.0;
49
50#define moveto(p,x,y) addto(p,x,y)
51#define lineto(p,x,y) addto(p,x,y)
52
53static void addto (stroke_t* p, double x, double y)
54{
55 pointf pt;
56
58 sizeof(pointf));
59 pt.x = x;
60 pt.y = y;
61 p->vertices[p->nvertices++] = pt;
62}
63
64/*
65 * handle zeros
66 */
67static double myatan (double y, double x)
68{
69 double v;
70 if (x == 0 && y == 0)
71 return 0;
72 v = atan2 (y, x);
73 if (v >= 0) return v;
74 return v + 2 * M_PI;
75}
76
77/*
78 * mod that accepts floats and makes negatives positive
79 */
80static double mymod (double original, double modulus)
81{
82 double v;
83 if (original < 0 || original >= modulus) {
84 v = -floor(original/modulus);
85 return v * modulus + original;
86 }
87 return original;
88}
89
90typedef struct {
91 double x;
92 double y;
94 char type;
95 double dir;
96 double lout;
97 bool bevel;
98 double dir2;
99} pathpoint;
100
101typedef LIST(pathpoint) vararr_t;
102
103static void
104insertArr (vararr_t* arr, pointf p, double l)
105{
106 pathpoint pt = {.x = p.x, .y = p.y, .lengthsofar = l};
107 LIST_APPEND(arr, pt);
108}
109
110static void
111printArr (vararr_t* arr, FILE* fp)
112{
113 fprintf(fp, "size %" PRISIZE_T "\n", LIST_SIZE(arr));
114 for (size_t i = 0; i < LIST_SIZE(arr); i++) {
115 pathpoint pt = LIST_GET(arr, i);
116 fprintf(fp, " [%" PRISIZE_T "] x %.02f y %.02f d %.02f\n", i, pt.x, pt.y,
117 pt.lengthsofar);
118 }
119}
120
121static double l2dist (pointf p0, pointf p1)
122{
123 double delx = p0.x - p1.x;
124 double dely = p0.y - p1.y;
125 return hypot(delx, dely);
126}
127
128/* analyze current path, creating pathpoints array
129 * turn all curves into lines
130 */
131static vararr_t pathtolines(bezier *bez) {
132 int step;
133 double seglen, linelen = 0;
134 vararr_t arr = {0};
135 pointf p0, p1, V[4];
136 const size_t n = bez->size;
137 pointf* A = bez->list;
138
139 insertArr(&arr, A[0], 0);
140 V[3] = A[0];
141 for (size_t i = 0; i + 3 < n; i += 3) {
142 V[0] = V[3];
143 for (size_t j = 1; j <= 3; j++)
144 V[j] = A[i + j];
145 p0 = V[0];
146 for (step = 1; step <= BEZIERSUBDIVISION; step++) {
147 p1 = Bezier(V, (double) step / BEZIERSUBDIVISION, NULL, NULL);
148 seglen = l2dist(p0, p1);
149 /* If initwid is large, this may never happen, so turn off. I assume this is to prevent
150 * too man points or too small a movement. Perhaps a better test can be made, but for now
151 * we turn it off.
152 */
153 /* if (seglen > initwid/10) { */
154 linelen += seglen;
155 insertArr(&arr, p1, linelen);
156 /* } */
157 p0 = p1;
158 }
159 }
160 if (debug) {
161 printArr(&arr, stderr);
162 }
163 return arr;
164}
165
166static void drawbevel(double x, double lineout, bool forward, double dir,
167 double dir2, stroke_t *p) {
168 double a2;
169
170 if (forward) {
171 a2 = dir2;
172 } else {
173 a2 = dir;
174 }
175 lineto (p, x + lineout*cos(a2), x + lineout*sin(a2));
176}
177
178typedef double (*radfunc_t) (double curlen, double totallen, double initwid);
179
180/* taper:
181 * Given a B-spline bez, returns a polygon that represents spline as a tapered
182 * edge, starting with width initwid.
183 * The radfunc determines the half-width along the curve. Typically, this will
184 * decrease from initwid to 0 as the curlen goes from 0 to totallen.
185 */
186stroke_t taper(bezier *bez, radfunc_t radfunc, double initwid) {
187 double direction=0, direction_2=0;
188 vararr_t arr = pathtolines(bez);
189 pathpoint cur_point, last_point, next_point;
190 double x=0, y=0, dist;
191 double nx, ny, ndir;
192 double lx, ly, ldir;
193 double lineout=0, linerad=0, linelen=0;
194 double theta, phi;
195
196 size_t pathcount;
197 pathpoint *pathpoints;
198 LIST_DETACH(&arr, &pathpoints, &pathcount);
199 linelen = pathpoints[pathcount-1].lengthsofar;
200
201 /* determine miter and bevel points and directions */
202 for (size_t i = 0; i < pathcount; i++) {
203 const size_t l = i == 0 ? pathcount - 1 : i - 1;
204 const size_t n = (i + 1) % pathcount;
205
206 cur_point = pathpoints[i];
207 x = cur_point.x;
208 y = cur_point.y;
209 dist = cur_point.lengthsofar;
210
211 next_point = pathpoints[n];
212 nx = next_point.x;
213 ny = next_point.y;
214 ndir = myatan (ny-y, nx-x);
215
216 last_point = pathpoints[l];
217 lx = last_point.x;
218 ly = last_point.y;
219 ldir = myatan (ly-y, lx-x);
220
221 bool bevel = false;
222 direction_2 = 0;
223
224 /* effective line radius at this point */
225 linerad = radfunc(dist, linelen, initwid);
226
227 if (i == 0 || i == pathcount-1) {
228 lineout = linerad;
229 if (i == 0) {
230 direction = ndir + D2R(90);
231 } else {
232 direction = ldir - D2R(90);
233 }
234 direction_2 = direction;
235 } else {
236 theta = ndir-ldir;
237 if (theta < 0) {
238 theta += D2R(360);
239 }
240 phi = D2R(90) - theta / 2;
241 /* actual distance to junction point */
242 if (cos(phi) == 0) {
243 lineout = 0;
244 } else {
245 lineout = linerad / cos(phi);
246 }
247 /* direction to junction point */
248 direction = ndir+D2R(90)+phi;
249 if (lineout > currentmiterlimit * linerad) {
250 bevel = true;
251 lineout = linerad;
252 direction = mymod(ldir-D2R(90),D2R(360));
253 direction_2 = mymod(ndir+D2R(90),D2R(360));
254 if (i == pathcount-1) {
255 bevel = false;
256 }
257 } else {
258 direction_2 = direction;
259 }
260 }
261 pathpoints[i].x = x;
262 pathpoints[i].y = y;
263 pathpoints[i].lengthsofar = dist;
264 pathpoints[i].type = 'l';
265 pathpoints[i].dir = direction;
266 pathpoints[i].lout = lineout;
267 pathpoints[i].bevel = bevel;
268 pathpoints[i].dir2 = direction_2;
269 }
270
271 /* draw line */
272 stroke_t p = {0};
273 /* side 1 */
274 for (size_t i = 0; i < pathcount; i++) {
275 cur_point = pathpoints[i];
276 x = cur_point.x;
277 y = cur_point.y;
278 direction = cur_point.dir;
279 lineout = cur_point.lout;
280 bool bevel = cur_point.bevel;
281 direction_2 = cur_point.dir2;
282 if (i == 0) {
283 moveto(&p, x+cos(direction)*lineout, y+sin(direction)*lineout);
284 } else {
285 lineto(&p, x+cos(direction)*lineout, y+sin(direction)*lineout);
286 }
287 if (bevel) {
288 drawbevel(x, lineout, true, direction, direction_2, &p);
289 }
290 }
291 /* end circle as needed */
292 direction += D2R(180);
293 lineto(&p, x+cos(direction)*lineout, y+sin(direction)*lineout);
294 /* side 2 */
295 assert(pathcount > 0);
296 for (size_t i = pathcount - 2; i != SIZE_MAX; i--) {
297 cur_point = pathpoints[i];
298 x = cur_point.x;
299 y = cur_point.y;
300 direction = cur_point.dir + D2R(180);
301 lineout = cur_point.lout;
302 bool bevel = cur_point.bevel;
303 direction_2 = cur_point.dir2 + D2R(180);
304 lineto(&p, x+cos(direction_2)*lineout, y+sin(direction_2)*lineout);
305 if (bevel) {
306 drawbevel(x, lineout, false, direction, direction_2, &p);
307 }
308 }
309 free(pathpoints);
310 return p;
311}
312
313#ifdef TEST
314static double halffunc (double curlen, double totallen, double initwid)
315{
316 return (1 - curlen / totallen) * initwid / 2.0;
317}
318
319static pointf pts[] = {
320 {100,100},
321 {150,150},
322 {200,100},
323 {250,200},
324};
325
326main ()
327{
328 stroke_t* sp;
329 bezier bez;
330
331 bez.size = sizeof(pts)/sizeof(pointf);
332 bez.list = pts;
333 sp = taper(&bez, halffunc, 20.0);
334 printf ("newpath\n");
335 printf ("%.02f %.02f moveto\n", sp->vertices[0].x, sp->vertices[0].y);
336 for (size_t i = 1; i < sp->nvertices; i++)
337 printf ("%.02f %.02f lineto\n", sp->vertices[i].x, sp->vertices[i].y);
338 printf ("fill showpage\n");
339}
340#endif
Memory allocation wrappers that exit on failure.
static void * gv_recalloc(void *ptr, size_t old_nmemb, size_t new_nmemb, size_t size)
Definition alloc.h:73
pointf Bezier(pointf *V, double t, pointf *Left, pointf *Right)
Definition utils.c:171
#define A(n, t)
Definition expr.h:76
static double dist(int dim, double *x, double *y)
#define V
Definition gdefs.h:5
void free(void *)
#define SIZE_MAX
Definition gmlscan.c:347
node NULL
Definition grammar.y:181
type-generic dynamically expanding list
#define LIST_DETACH(list, datap, sizep)
Definition list.h:434
#define LIST(type)
Definition list.h:55
#define LIST_SIZE(list)
Definition list.h:80
#define LIST_APPEND(list, item)
Definition list.h:132
#define LIST_GET(list, index)
Definition list.h:165
#define PRISIZE_T
Definition prisize_t.h:25
Definition types.h:89
size_t size
Definition types.h:91
pointf * list
Definition types.h:90
double dir2
Definition taper.c:98
char type
Definition taper.c:94
double y
Definition taper.c:92
bool bevel
Definition taper.c:97
double dir
Definition taper.c:95
double lout
Definition taper.c:96
double x
Definition taper.c:91
double lengthsofar
Definition taper.c:93
double x
Definition geom.h:29
double y
Definition geom.h:29
pointf * vertices
Definition types.h:175
size_t nvertices
number of points in the stroke
Definition types.h:174
static void drawbevel(double x, double lineout, bool forward, double dir, double dir2, stroke_t *p)
Definition taper.c:166
static void addto(stroke_t *p, double x, double y)
Definition taper.c:53
#define moveto(p, x, y)
Definition taper.c:50
#define D2R(d)
Definition taper.c:45
static double l2dist(pointf p0, pointf p1)
Definition taper.c:121
static double myatan(double y, double x)
Definition taper.c:67
@ debug
Definition taper.c:35
static vararr_t pathtolines(bezier *bez)
Definition taper.c:131
static double mymod(double original, double modulus)
Definition taper.c:80
double(* radfunc_t)(double curlen, double totallen, double initwid)
Definition taper.c:178
#define lineto(p, x, y)
Definition taper.c:51
static double currentmiterlimit
Definition taper.c:48
stroke_t taper(bezier *bez, radfunc_t radfunc, double initwid)
Definition taper.c:186
static void printArr(vararr_t *arr, FILE *fp)
Definition taper.c:111
#define M_PI
Definition taper.c:43
#define BEZIERSUBDIVISION
Definition taper.c:39
int main()
graphs, nodes and edges info: Agraphinfo_t, Agnodeinfo_t and Agedgeinfo_t