1 /* Libart_LGPL - library of basic graphic primitives
2 * Copyright (C) 1998-2000 Raph Levien
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Library General Public
6 * License as published by the Free Software Foundation; either
7 * version 2 of the License, or (at your option) any later version.
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Library General Public License for more details.
14 * You should have received a copy of the GNU Library General Public
15 * License along with this library; if not, write to the
16 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17 * Boston, MA 02111-1307, USA.
26 #include "art_vpath.h"
28 #ifdef ART_USE_NEW_INTERSECTOR
29 #include "art_svp_intersect.h"
31 #include "art_svp_wind.h"
33 #include "art_svp_vpath.h"
34 #include "art_svp_vpath_stroke.h"
37 #define EPSILON_2 1e-12
39 #define yes_OPTIMIZE_INNER
41 /* Render an arc segment starting at (xc + x0, yc + y0) to (xc + x1,
42 yc + y1), centered at (xc, yc), and with given radius. Both x0^2 +
43 y0^2 and x1^2 + y1^2 should be equal to radius^2.
45 A positive value of radius means curve to the left, negative means
49 art_svp_vpath_stroke_arc (ArtVpath **p_vpath, int *pn, int *pn_max,
62 aradius = fabs (radius);
63 theta = 2 * M_SQRT2 * sqrt (flatness / aradius);
64 th_0 = atan2 (y0, x0);
65 th_1 = atan2 (y1, x1);
68 /* curve to the left */
69 if (th_0 < th_1) th_0 += M_PI * 2;
70 n_pts = ceil ((th_0 - th_1) / theta);
74 /* curve to the right */
75 if (th_1 < th_0) th_1 += M_PI * 2;
76 n_pts = ceil ((th_1 - th_0) / theta);
79 printf ("start %f %f; th_0 = %f, th_1 = %f, r = %f, theta = %f\n", x0, y0, th_0, th_1, radius, theta);
81 art_vpath_add_point (p_vpath, pn, pn_max,
82 ART_LINETO, xc + x0, yc + y0);
83 for (i = 1; i < n_pts; i++)
85 theta = th_0 + (th_1 - th_0) * i / n_pts;
86 art_vpath_add_point (p_vpath, pn, pn_max,
87 ART_LINETO, xc + cos (theta) * aradius,
88 yc + sin (theta) * aradius);
90 printf ("mid %f %f\n", cos (theta) * radius, sin (theta) * radius);
93 art_vpath_add_point (p_vpath, pn, pn_max,
94 ART_LINETO, xc + x1, yc + y1);
96 printf ("end %f %f\n", x1, y1);
100 /* Assume that forw and rev are at point i0. Bring them to i1,
101 joining with the vector i1 - i2.
103 This used to be true, but isn't now that the stroke_raw code is
104 filtering out (near)zero length vectors: {It so happens that all
105 invocations of this function maintain the precondition i1 = i0 + 1,
106 so we could decrease the number of arguments by one. We haven't
107 done that here, though.}
109 forw is to the line's right and rev is to its left.
111 Precondition: no zero-length vectors, otherwise a divide by
114 render_seg (ArtVpath **p_forw, int *pn_forw, int *pn_forw_max,
115 ArtVpath **p_rev, int *pn_rev, int *pn_rev_max,
116 ArtVpath *vpath, int i0, int i1, int i2,
117 ArtPathStrokeJoinType join,
118 double line_width, double miter_limit, double flatness)
130 printf ("join style = %d\n", join);
133 /* The vectors of the lines from i0 to i1 and i1 to i2. */
134 dx0 = vpath[i1].x - vpath[i0].x;
135 dy0 = vpath[i1].y - vpath[i0].y;
137 dx1 = vpath[i2].x - vpath[i1].x;
138 dy1 = vpath[i2].y - vpath[i1].y;
140 /* Set dl[xy]0 to the vector from i0 to i1, rotated counterclockwise
141 90 degrees, and scaled to the length of line_width. */
142 scale = line_width / sqrt (dx0 * dx0 + dy0 * dy0);
146 /* Set dl[xy]1 to the vector from i1 to i2, rotated counterclockwise
147 90 degrees, and scaled to the length of line_width. */
148 scale = line_width / sqrt (dx1 * dx1 + dy1 * dy1);
153 printf ("%% render_seg: (%g, %g) - (%g, %g) - (%g, %g)\n",
154 vpath[i0].x, vpath[i0].y,
155 vpath[i1].x, vpath[i1].y,
156 vpath[i2].x, vpath[i2].y);
158 printf ("%% render_seg: d[xy]0 = (%g, %g), dl[xy]0 = (%g, %g)\n",
159 dx0, dy0, dlx0, dly0);
161 printf ("%% render_seg: d[xy]1 = (%g, %g), dl[xy]1 = (%g, %g)\n",
162 dx1, dy1, dlx1, dly1);
165 /* now, forw's last point is expected to be colinear along d[xy]0
166 to point i0 - dl[xy]0, and rev with i0 + dl[xy]0. */
168 /* positive for positive area (i.e. left turn) */
169 cross = dx1 * dy0 - dx0 * dy1;
171 dmx = (dlx0 + dlx1) * 0.5;
172 dmy = (dly0 + dly1) * 0.5;
173 dmr2 = dmx * dmx + dmy * dmy;
175 if (join == ART_PATH_STROKE_JOIN_MITER &&
176 dmr2 * miter_limit * miter_limit < line_width * line_width)
177 join = ART_PATH_STROKE_JOIN_BEVEL;
179 /* the case when dmr2 is zero or very small bothers me
180 (i.e. near a 180 degree angle) */
181 scale = line_width * line_width / dmr2;
185 if (cross * cross < EPSILON_2 && dx0 * dx1 + dy0 * dy1 >= 0)
189 printf ("%% render_seg: straight\n");
191 art_vpath_add_point (p_forw, pn_forw, pn_forw_max,
192 ART_LINETO, vpath[i1].x - dlx0, vpath[i1].y - dly0);
193 art_vpath_add_point (p_rev, pn_rev, pn_rev_max,
194 ART_LINETO, vpath[i1].x + dlx0, vpath[i1].y + dly0);
198 /* left turn, forw is outside and rev is inside */
201 printf ("%% render_seg: left\n");
204 #ifdef NO_OPTIMIZE_INNER
207 /* check that i1 + dm[xy] is inside i0-i1 rectangle */
208 (dx0 + dmx) * dx0 + (dy0 + dmy) * dy0 > 0 &&
209 /* and that i1 + dm[xy] is inside i1-i2 rectangle */
210 ((dx1 - dmx) * dx1 + (dy1 - dmy) * dy1 > 0)
211 #ifdef PEDANTIC_INNER
213 /* check that i1 + dl[xy]1 is inside i0-i1 rectangle */
214 (dx0 + dlx1) * dx0 + (dy0 + dly1) * dy0 > 0 &&
215 /* and that i1 + dl[xy]0 is inside i1-i2 rectangle */
216 ((dx1 - dlx0) * dx1 + (dy1 - dly0) * dy1 > 0)
220 /* can safely add single intersection point */
221 art_vpath_add_point (p_rev, pn_rev, pn_rev_max,
222 ART_LINETO, vpath[i1].x + dmx, vpath[i1].y + dmy);
226 /* need to loop-de-loop the inside */
227 art_vpath_add_point (p_rev, pn_rev, pn_rev_max,
228 ART_LINETO, vpath[i1].x + dlx0, vpath[i1].y + dly0);
229 art_vpath_add_point (p_rev, pn_rev, pn_rev_max,
230 ART_LINETO, vpath[i1].x, vpath[i1].y);
231 art_vpath_add_point (p_rev, pn_rev, pn_rev_max,
232 ART_LINETO, vpath[i1].x + dlx1, vpath[i1].y + dly1);
235 if (join == ART_PATH_STROKE_JOIN_BEVEL)
238 art_vpath_add_point (p_forw, pn_forw, pn_forw_max,
239 ART_LINETO, vpath[i1].x - dlx0, vpath[i1].y - dly0);
240 art_vpath_add_point (p_forw, pn_forw, pn_forw_max,
241 ART_LINETO, vpath[i1].x - dlx1, vpath[i1].y - dly1);
243 else if (join == ART_PATH_STROKE_JOIN_MITER)
245 art_vpath_add_point (p_forw, pn_forw, pn_forw_max,
246 ART_LINETO, vpath[i1].x - dmx, vpath[i1].y - dmy);
248 else if (join == ART_PATH_STROKE_JOIN_ROUND)
249 art_svp_vpath_stroke_arc (p_forw, pn_forw, pn_forw_max,
250 vpath[i1].x, vpath[i1].y,
258 /* right turn, rev is outside and forw is inside */
260 printf ("%% render_seg: right\n");
264 #ifdef NO_OPTIMIZE_INNER
267 /* check that i1 - dm[xy] is inside i0-i1 rectangle */
268 (dx0 - dmx) * dx0 + (dy0 - dmy) * dy0 > 0 &&
269 /* and that i1 - dm[xy] is inside i1-i2 rectangle */
270 ((dx1 + dmx) * dx1 + (dy1 + dmy) * dy1 > 0)
271 #ifdef PEDANTIC_INNER
273 /* check that i1 - dl[xy]1 is inside i0-i1 rectangle */
274 (dx0 - dlx1) * dx0 + (dy0 - dly1) * dy0 > 0 &&
275 /* and that i1 - dl[xy]0 is inside i1-i2 rectangle */
276 ((dx1 + dlx0) * dx1 + (dy1 + dly0) * dy1 > 0)
280 /* can safely add single intersection point */
281 art_vpath_add_point (p_forw, pn_forw, pn_forw_max,
282 ART_LINETO, vpath[i1].x - dmx, vpath[i1].y - dmy);
286 /* need to loop-de-loop the inside */
287 art_vpath_add_point (p_forw, pn_forw, pn_forw_max,
288 ART_LINETO, vpath[i1].x - dlx0, vpath[i1].y - dly0);
289 art_vpath_add_point (p_forw, pn_forw, pn_forw_max,
290 ART_LINETO, vpath[i1].x, vpath[i1].y);
291 art_vpath_add_point (p_forw, pn_forw, pn_forw_max,
292 ART_LINETO, vpath[i1].x - dlx1, vpath[i1].y - dly1);
295 if (join == ART_PATH_STROKE_JOIN_BEVEL)
298 art_vpath_add_point (p_rev, pn_rev, pn_rev_max,
299 ART_LINETO, vpath[i1].x + dlx0, vpath[i1].y + dly0);
300 art_vpath_add_point (p_rev, pn_rev, pn_rev_max,
301 ART_LINETO, vpath[i1].x + dlx1, vpath[i1].y + dly1);
303 else if (join == ART_PATH_STROKE_JOIN_MITER)
305 art_vpath_add_point (p_rev, pn_rev, pn_rev_max,
306 ART_LINETO, vpath[i1].x + dmx, vpath[i1].y + dmy);
308 else if (join == ART_PATH_STROKE_JOIN_ROUND)
309 art_svp_vpath_stroke_arc (p_rev, pn_rev, pn_rev_max,
310 vpath[i1].x, vpath[i1].y,
319 /* caps i1, under the assumption of a vector from i0 */
321 render_cap (ArtVpath **p_result, int *pn_result, int *pn_result_max,
322 ArtVpath *vpath, int i0, int i1,
323 ArtPathStrokeCapType cap, double line_width, double flatness)
331 dx0 = vpath[i1].x - vpath[i0].x;
332 dy0 = vpath[i1].y - vpath[i0].y;
334 /* Set dl[xy]0 to the vector from i0 to i1, rotated counterclockwise
335 90 degrees, and scaled to the length of line_width. */
336 scale = line_width / sqrt (dx0 * dx0 + dy0 * dy0);
341 printf ("cap style = %d\n", cap);
346 case ART_PATH_STROKE_CAP_BUTT:
347 art_vpath_add_point (p_result, pn_result, pn_result_max,
348 ART_LINETO, vpath[i1].x - dlx0, vpath[i1].y - dly0);
349 art_vpath_add_point (p_result, pn_result, pn_result_max,
350 ART_LINETO, vpath[i1].x + dlx0, vpath[i1].y + dly0);
352 case ART_PATH_STROKE_CAP_ROUND:
353 n_pts = ceil (M_PI / (2.0 * M_SQRT2 * sqrt (flatness / line_width)));
354 art_vpath_add_point (p_result, pn_result, pn_result_max,
355 ART_LINETO, vpath[i1].x - dlx0, vpath[i1].y - dly0);
356 for (i = 1; i < n_pts; i++)
358 double theta, c_th, s_th;
360 theta = M_PI * i / n_pts;
363 art_vpath_add_point (p_result, pn_result, pn_result_max,
365 vpath[i1].x - dlx0 * c_th - dly0 * s_th,
366 vpath[i1].y - dly0 * c_th + dlx0 * s_th);
368 art_vpath_add_point (p_result, pn_result, pn_result_max,
369 ART_LINETO, vpath[i1].x + dlx0, vpath[i1].y + dly0);
371 case ART_PATH_STROKE_CAP_SQUARE:
372 art_vpath_add_point (p_result, pn_result, pn_result_max,
374 vpath[i1].x - dlx0 - dly0,
375 vpath[i1].y - dly0 + dlx0);
376 art_vpath_add_point (p_result, pn_result, pn_result_max,
378 vpath[i1].x + dlx0 - dly0,
379 vpath[i1].y + dly0 + dlx0);
385 * art_svp_from_vpath_raw: Stroke a vector path, raw version
386 * @vpath: #ArtVPath to stroke.
389 * @line_width: Width of stroke.
390 * @miter_limit: Miter limit.
391 * @flatness: Flatness.
393 * Exactly the same as art_svp_vpath_stroke(), except that the resulting
394 * stroke outline may self-intersect and have regions of winding number
397 * Return value: Resulting raw stroked outline in svp format.
400 art_svp_vpath_stroke_raw (ArtVpath *vpath,
401 ArtPathStrokeJoinType join,
402 ArtPathStrokeCapType cap,
407 int begin_idx, end_idx;
409 ArtVpath *forw, *rev;
411 int n_forw_max, n_rev_max;
413 int n_result, n_result_max;
414 double half_lw = 0.5 * line_width;
416 int last, this, next, second;
420 forw = art_new (ArtVpath, n_forw_max);
423 rev = art_new (ArtVpath, n_rev_max);
427 result = art_new (ArtVpath, n_result_max);
429 for (begin_idx = 0; vpath[begin_idx].code != ART_END; begin_idx = end_idx)
434 closed = (vpath[begin_idx].code == ART_MOVETO);
436 /* we don't know what the first point joins with until we get to the
437 last point and see if it's closed. So we start with the second
440 Note: this is not strictly true (we now know it's closed from
441 the opening pathcode), but why fix code that isn't broken?
445 /* skip over identical points at the beginning of the subpath */
446 for (i = this + 1; vpath[i].code == ART_LINETO; i++)
448 dx = vpath[i].x - vpath[this].x;
449 dy = vpath[i].y - vpath[this].y;
450 if (dx * dx + dy * dy > EPSILON_2)
456 /* invariant: this doesn't coincide with next */
457 while (vpath[next].code == ART_LINETO)
461 /* skip over identical points after the beginning of the subpath */
462 for (i = this + 1; vpath[i].code == ART_LINETO; i++)
464 dx = vpath[i].x - vpath[this].x;
465 dy = vpath[i].y - vpath[this].y;
466 if (dx * dx + dy * dy > EPSILON_2)
470 if (vpath[next].code != ART_LINETO)
472 /* reached end of path */
473 /* make "closed" detection conform to PostScript
474 semantics (i.e. explicit closepath code rather than
475 just the fact that end of the path is the beginning) */
477 vpath[this].x == vpath[begin_idx].x &&
478 vpath[this].y == vpath[begin_idx].y)
482 /* path is closed, render join to beginning */
483 render_seg (&forw, &n_forw, &n_forw_max,
484 &rev, &n_rev, &n_rev_max,
485 vpath, last, this, second,
486 join, half_lw, miter_limit, flatness);
489 printf ("%% forw %d, rev %d\n", n_forw, n_rev);
491 /* do forward path */
492 art_vpath_add_point (&result, &n_result, &n_result_max,
493 ART_MOVETO, forw[n_forw - 1].x,
495 for (j = 0; j < n_forw; j++)
496 art_vpath_add_point (&result, &n_result, &n_result_max,
497 ART_LINETO, forw[j].x,
500 /* do reverse path, reversed */
501 art_vpath_add_point (&result, &n_result, &n_result_max,
502 ART_MOVETO, rev[0].x,
504 for (j = n_rev - 1; j >= 0; j--)
505 art_vpath_add_point (&result, &n_result, &n_result_max,
506 ART_LINETO, rev[j].x,
514 /* add to forw rather than result to ensure that
515 forw has at least one point. */
516 render_cap (&forw, &n_forw, &n_forw_max,
518 cap, half_lw, flatness);
519 art_vpath_add_point (&result, &n_result, &n_result_max,
520 ART_MOVETO, forw[0].x,
522 for (j = 1; j < n_forw; j++)
523 art_vpath_add_point (&result, &n_result, &n_result_max,
524 ART_LINETO, forw[j].x,
526 for (j = n_rev - 1; j >= 0; j--)
527 art_vpath_add_point (&result, &n_result, &n_result_max,
528 ART_LINETO, rev[j].x,
530 render_cap (&result, &n_result, &n_result_max,
531 vpath, second, begin_idx,
532 cap, half_lw, flatness);
533 art_vpath_add_point (&result, &n_result, &n_result_max,
534 ART_LINETO, forw[0].x,
539 render_seg (&forw, &n_forw, &n_forw_max,
540 &rev, &n_rev, &n_rev_max,
541 vpath, last, this, next,
542 join, half_lw, miter_limit, flatness);
550 printf ("%% n_result = %d\n", n_result);
552 art_vpath_add_point (&result, &n_result, &n_result_max, ART_END, 0, 0);
564 print_ps_vpath (ArtVpath *vpath)
568 for (i = 0; vpath[i].code != ART_END; i++)
570 switch (vpath[i].code)
573 printf ("%g %g moveto\n", XOFF + vpath[i].x, YOFF - vpath[i].y);
576 printf ("%g %g lineto\n", XOFF + vpath[i].x, YOFF - vpath[i].y);
582 printf ("stroke showpage\n");
586 print_ps_svp (ArtSVP *vpath)
590 printf ("%% begin\n");
591 for (i = 0; i < vpath->n_segs; i++)
593 printf ("%g setgray\n", vpath->segs[i].dir ? 0.7 : 0);
594 for (j = 0; j < vpath->segs[i].n_points; j++)
596 printf ("%g %g %s\n",
597 XOFF + vpath->segs[i].points[j].x,
598 YOFF - vpath->segs[i].points[j].y,
599 j ? "lineto" : "moveto");
604 printf ("showpage\n");
608 /* Render a vector path into a stroked outline.
610 Status of this routine:
612 Basic correctness: Only miter and bevel line joins are implemented,
613 and only butt line caps. Otherwise, seems to be fine.
615 Numerical stability: We cheat (adding random perturbation). Thus,
616 it seems very likely that no numerical stability problems will be
619 Speed: Should be pretty good.
621 Precision: The perturbation fuzzes the coordinates slightly,
622 but not enough to be visible. */
624 * art_svp_vpath_stroke: Stroke a vector path.
625 * @vpath: #ArtVPath to stroke.
628 * @line_width: Width of stroke.
629 * @miter_limit: Miter limit.
630 * @flatness: Flatness.
632 * Computes an svp representing the stroked outline of @vpath. The
633 * width of the stroked line is @line_width.
635 * Lines are joined according to the @join rule. Possible values are
636 * ART_PATH_STROKE_JOIN_MITER (for mitered joins),
637 * ART_PATH_STROKE_JOIN_ROUND (for round joins), and
638 * ART_PATH_STROKE_JOIN_BEVEL (for bevelled joins). The mitered join
639 * is converted to a bevelled join if the miter would extend to a
640 * distance of more than @miter_limit * @line_width from the actual
643 * If there are open subpaths, the ends of these subpaths are capped
644 * according to the @cap rule. Possible values are
645 * ART_PATH_STROKE_CAP_BUTT (squared cap, extends exactly to end
646 * point), ART_PATH_STROKE_CAP_ROUND (rounded half-circle centered at
647 * the end point), and ART_PATH_STROKE_CAP_SQUARE (squared cap,
648 * extending half @line_width past the end point).
650 * The @flatness parameter controls the accuracy of the rendering. It
651 * is most important for determining the number of points to use to
652 * approximate circular arcs for round lines and joins. In general, the
653 * resulting vector path will be within @flatness pixels of the "ideal"
654 * path containing actual circular arcs. I reserve the right to use
655 * the @flatness parameter to convert bevelled joins to miters for very
656 * small turn angles, as this would reduce the number of points in the
657 * resulting outline path.
659 * The resulting path is "clean" with respect to self-intersections, i.e.
660 * the winding number is 0 or 1 at each point.
662 * Return value: Resulting stroked outline in svp format.
665 art_svp_vpath_stroke (ArtVpath *vpath,
666 ArtPathStrokeJoinType join,
667 ArtPathStrokeCapType cap,
672 #ifdef ART_USE_NEW_INTERSECTOR
673 ArtVpath *vpath_stroke;
677 vpath_stroke = art_svp_vpath_stroke_raw (vpath, join, cap,
678 line_width, miter_limit, flatness);
680 print_ps_vpath (vpath_stroke);
682 svp = art_svp_from_vpath (vpath_stroke);
686 art_free (vpath_stroke);
688 swr = art_svp_writer_rewind_new (ART_WIND_RULE_NONZERO);
689 art_svp_intersector (svp, swr);
691 svp2 = art_svp_writer_rewind_reap (swr);
698 ArtVpath *vpath_stroke, *vpath2;
699 ArtSVP *svp, *svp2, *svp3;
701 vpath_stroke = art_svp_vpath_stroke_raw (vpath, join, cap,
702 line_width, miter_limit, flatness);
704 print_ps_vpath (vpath_stroke);
706 vpath2 = art_vpath_perturb (vpath_stroke);
708 print_ps_vpath (vpath2);
710 art_free (vpath_stroke);
711 svp = art_svp_from_vpath (vpath2);
716 svp2 = art_svp_uncross (svp);
721 svp3 = art_svp_rewind_uncrossed (svp2, ART_WIND_RULE_NONZERO);