Graphviz 13.1.2~dev.20250723.1036
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
101DEFINE_LIST(vararr, pathpoint)
102
103static void
104insertArr (vararr_t* arr, pointf p, double l)
105{
106 pathpoint pt = {.x = p.x, .y = p.y, .lengthsofar = l};
107 vararr_append(arr, pt);
108}
109
110static void
111printArr (vararr_t* arr, FILE* fp)
112{
113 fprintf(fp, "size %" PRISIZE_T "\n", vararr_size(arr));
114 for (size_t i = 0; i < vararr_size(arr); i++) {
115 pathpoint pt = vararr_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 = vararr_size(&arr);
197 pathpoint *pathpoints = vararr_detach(&arr);
198 linelen = pathpoints[pathcount-1].lengthsofar;
199
200 /* determine miter and bevel points and directions */
201 for (size_t i = 0; i < pathcount; i++) {
202 const size_t l = i == 0 ? pathcount - 1 : i - 1;
203 const size_t n = (i + 1) % pathcount;
204
205 cur_point = pathpoints[i];
206 x = cur_point.x;
207 y = cur_point.y;
208 dist = cur_point.lengthsofar;
209
210 next_point = pathpoints[n];
211 nx = next_point.x;
212 ny = next_point.y;
213 ndir = myatan (ny-y, nx-x);
214
215 last_point = pathpoints[l];
216 lx = last_point.x;
217 ly = last_point.y;
218 ldir = myatan (ly-y, lx-x);
219
220 bool bevel = false;
221 direction_2 = 0;
222
223 /* effective line radius at this point */
224 linerad = radfunc(dist, linelen, initwid);
225
226 if (i == 0 || i == pathcount-1) {
227 lineout = linerad;
228 if (i == 0) {
229 direction = ndir + D2R(90);
230 } else {
231 direction = ldir - D2R(90);
232 }
233 direction_2 = direction;
234 } else {
235 theta = ndir-ldir;
236 if (theta < 0) {
237 theta += D2R(360);
238 }
239 phi = D2R(90) - theta / 2;
240 /* actual distance to junction point */
241 if (cos(phi) == 0) {
242 lineout = 0;
243 } else {
244 lineout = linerad / cos(phi);
245 }
246 /* direction to junction point */
247 direction = ndir+D2R(90)+phi;
248 if (lineout > currentmiterlimit * linerad) {
249 bevel = true;
250 lineout = linerad;
251 direction = mymod(ldir-D2R(90),D2R(360));
252 direction_2 = mymod(ndir+D2R(90),D2R(360));
253 if (i == pathcount-1) {
254 bevel = false;
255 }
256 } else {
257 direction_2 = direction;
258 }
259 }
260 pathpoints[i].x = x;
261 pathpoints[i].y = y;
262 pathpoints[i].lengthsofar = dist;
263 pathpoints[i].type = 'l';
264 pathpoints[i].dir = direction;
265 pathpoints[i].lout = lineout;
266 pathpoints[i].bevel = bevel;
267 pathpoints[i].dir2 = direction_2;
268 }
269
270 /* draw line */
271 stroke_t p = {0};
272 /* side 1 */
273 for (size_t i = 0; i < pathcount; i++) {
274 cur_point = pathpoints[i];
275 x = cur_point.x;
276 y = cur_point.y;
277 direction = cur_point.dir;
278 lineout = cur_point.lout;
279 bool bevel = cur_point.bevel;
280 direction_2 = cur_point.dir2;
281 if (i == 0) {
282 moveto(&p, x+cos(direction)*lineout, y+sin(direction)*lineout);
283 } else {
284 lineto(&p, x+cos(direction)*lineout, y+sin(direction)*lineout);
285 }
286 if (bevel) {
287 drawbevel(x, lineout, true, direction, direction_2, &p);
288 }
289 }
290 /* end circle as needed */
291 direction += D2R(180);
292 lineto(&p, x+cos(direction)*lineout, y+sin(direction)*lineout);
293 /* side 2 */
294 assert(pathcount > 0);
295 for (size_t i = pathcount - 2; i != SIZE_MAX; i--) {
296 cur_point = pathpoints[i];
297 x = cur_point.x;
298 y = cur_point.y;
299 direction = cur_point.dir + D2R(180);
300 lineout = cur_point.lout;
301 bool bevel = cur_point.bevel;
302 direction_2 = cur_point.dir2 + D2R(180);
303 lineto(&p, x+cos(direction_2)*lineout, y+sin(direction_2)*lineout);
304 if (bevel) {
305 drawbevel(x, lineout, false, direction, direction_2, &p);
306 }
307 }
308 free(pathpoints);
309 return p;
310}
311
312#ifdef TEST
313static double halffunc (double curlen, double totallen, double initwid)
314{
315 return (1 - curlen / totallen) * initwid / 2.0;
316}
317
318static pointf pts[] = {
319 {100,100},
320 {150,150},
321 {200,100},
322 {250,200},
323};
324
325main ()
326{
327 stroke_t* sp;
328 bezier bez;
329
330 bez.size = sizeof(pts)/sizeof(pointf);
331 bez.list = pts;
332 sp = taper(&bez, halffunc, 20.0);
333 printf ("newpath\n");
334 printf ("%.02f %.02f moveto\n", sp->vertices[0].x, sp->vertices[0].y);
335 for (size_t i = 1; i < sp->nvertices; i++)
336 printf ("%.02f %.02f lineto\n", sp->vertices[i].x, sp->vertices[i].y);
337 printf ("fill showpage\n");
338}
339#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:180
#define DEFINE_LIST(name, type)
Definition list.h:22
#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
static void insertArr(vararr_t *arr, pointf p, double l)
Definition taper.c:104
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