device for OCR'ing documents
[swftools.git] / lib / art / art_svp_vpath_stroke.c
1 /* Libart_LGPL - library of basic graphic primitives
2  * Copyright (C) 1998-2000 Raph Levien
3  *
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.
8  *
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.
13  *
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.
18  */
19
20
21 #include "config.h"
22 #include "art_svp_vpath_stroke.h"
23
24 #include <stdlib.h>
25 #include <math.h>
26
27 #include "art_misc.h"
28
29 #include "art_vpath.h"
30 #include "art_svp.h"
31 #ifdef ART_USE_NEW_INTERSECTOR
32 #include "art_svp_intersect.h"
33 #else
34 #include "art_svp_wind.h"
35 #endif
36 #include "art_svp_vpath.h"
37
38 #define EPSILON 1e-6
39 #define EPSILON_2 1e-12
40
41 #define yes_OPTIMIZE_INNER
42
43 /* Render an arc segment starting at (xc + x0, yc + y0) to (xc + x1,
44    yc + y1), centered at (xc, yc), and with given radius. Both x0^2 +
45    y0^2 and x1^2 + y1^2 should be equal to radius^2.
46
47    A positive value of radius means curve to the left, negative means
48    curve to the right.
49 */
50 static void
51 art_svp_vpath_stroke_arc (ArtVpath **p_vpath, int *pn, int *pn_max,
52                           double xc, double yc,
53                           double x0, double y0,
54                           double x1, double y1,
55                           double radius,
56                           double flatness)
57 {
58   double theta;
59   double th_0, th_1;
60   int n_pts;
61   int i;
62   double aradius;
63
64   aradius = fabs (radius);
65   theta = 2 * M_SQRT2 * sqrt (flatness / aradius);
66   th_0 = atan2 (y0, x0);
67   th_1 = atan2 (y1, x1);
68   if (radius > 0)
69     {
70       /* curve to the left */
71       if (th_0 < th_1) th_0 += M_PI * 2;
72       n_pts = ceil ((th_0 - th_1) / theta);
73     }
74   else
75     {
76       /* curve to the right */
77       if (th_1 < th_0) th_1 += M_PI * 2;
78       n_pts = ceil ((th_1 - th_0) / theta);
79     }
80 #ifdef VERBOSE
81   printf ("start %f %f; th_0 = %f, th_1 = %f, r = %f, theta = %f\n", x0, y0, th_0, th_1, radius, theta);
82 #endif
83   art_vpath_add_point (p_vpath, pn, pn_max,
84                        ART_LINETO, xc + x0, yc + y0);
85   for (i = 1; i < n_pts; i++)
86     {
87       theta = th_0 + (th_1 - th_0) * i / n_pts;
88       art_vpath_add_point (p_vpath, pn, pn_max,
89                            ART_LINETO, xc + cos (theta) * aradius,
90                            yc + sin (theta) * aradius);
91 #ifdef VERBOSE
92       printf ("mid %f %f\n", cos (theta) * radius, sin (theta) * radius);
93 #endif
94     }
95   art_vpath_add_point (p_vpath, pn, pn_max,
96                        ART_LINETO, xc + x1, yc + y1);
97 #ifdef VERBOSE
98   printf ("end %f %f\n", x1, y1);
99 #endif
100 }
101
102 /* Assume that forw and rev are at point i0. Bring them to i1,
103    joining with the vector i1 - i2.
104
105    This used to be true, but isn't now that the stroke_raw code is
106    filtering out (near)zero length vectors: {It so happens that all
107    invocations of this function maintain the precondition i1 = i0 + 1,
108    so we could decrease the number of arguments by one. We haven't
109    done that here, though.}
110
111    forw is to the line's right and rev is to its left.
112
113    Precondition: no zero-length vectors, otherwise a divide by
114    zero will happen.  */
115 static void
116 render_seg (ArtVpath **p_forw, int *pn_forw, int *pn_forw_max,
117             ArtVpath **p_rev, int *pn_rev, int *pn_rev_max,
118             ArtVpath *vpath, int i0, int i1, int i2,
119             ArtPathStrokeJoinType join,
120             double line_width, double miter_limit, double flatness)
121 {
122   double dx0, dy0;
123   double dx1, dy1;
124   double dlx0, dly0;
125   double dlx1, dly1;
126   double dmx, dmy;
127   double dmr2;
128   double scale;
129   double cross;
130
131 #ifdef VERBOSE
132   printf ("join style = %d\n", join);
133 #endif
134
135   /* The vectors of the lines from i0 to i1 and i1 to i2. */
136   dx0 = vpath[i1].x - vpath[i0].x;
137   dy0 = vpath[i1].y - vpath[i0].y;
138
139   dx1 = vpath[i2].x - vpath[i1].x;
140   dy1 = vpath[i2].y - vpath[i1].y;
141
142   /* Set dl[xy]0 to the vector from i0 to i1, rotated counterclockwise
143      90 degrees, and scaled to the length of line_width. */
144   scale = line_width / sqrt (dx0 * dx0 + dy0 * dy0);
145   dlx0 = dy0 * scale;
146   dly0 = -dx0 * scale;
147
148   /* Set dl[xy]1 to the vector from i1 to i2, rotated counterclockwise
149      90 degrees, and scaled to the length of line_width. */
150   scale = line_width / sqrt (dx1 * dx1 + dy1 * dy1);
151   dlx1 = dy1 * scale;
152   dly1 = -dx1 * scale;
153
154 #ifdef VERBOSE
155   printf ("%% render_seg: (%g, %g) - (%g, %g) - (%g, %g)\n",
156           vpath[i0].x, vpath[i0].y,
157           vpath[i1].x, vpath[i1].y,
158           vpath[i2].x, vpath[i2].y);
159
160   printf ("%% render_seg: d[xy]0 = (%g, %g), dl[xy]0 = (%g, %g)\n",
161           dx0, dy0, dlx0, dly0);
162
163   printf ("%% render_seg: d[xy]1 = (%g, %g), dl[xy]1 = (%g, %g)\n",
164           dx1, dy1, dlx1, dly1);
165 #endif
166
167   /* now, forw's last point is expected to be colinear along d[xy]0
168      to point i0 - dl[xy]0, and rev with i0 + dl[xy]0. */
169
170   /* positive for positive area (i.e. left turn) */
171   cross = dx1 * dy0 - dx0 * dy1;
172
173   dmx = (dlx0 + dlx1) * 0.5;
174   dmy = (dly0 + dly1) * 0.5;
175   dmr2 = dmx * dmx + dmy * dmy;
176
177   if (join == ART_PATH_STROKE_JOIN_MITER &&
178       dmr2 * miter_limit * miter_limit < line_width * line_width)
179     join = ART_PATH_STROKE_JOIN_BEVEL;
180
181   /* the case when dmr2 is zero or very small bothers me
182      (i.e. near a 180 degree angle)
183      ALEX: So, we avoid the optimization when dmr2 is very small. This should
184      be safe since dmx/y is only used in optimization and in MITER case, and MITER
185      should be converted to BEVEL when dmr2 is very small. */
186   if (dmr2 > EPSILON_2)
187     {
188       scale = line_width * line_width / dmr2;
189       dmx *= scale;
190       dmy *= scale;
191     }
192
193   if (cross * cross < EPSILON_2 && dx0 * dx1 + dy0 * dy1 >= 0)
194     {
195       /* going straight */
196 #ifdef VERBOSE
197       printf ("%% render_seg: straight\n");
198 #endif
199       art_vpath_add_point (p_forw, pn_forw, pn_forw_max,
200                        ART_LINETO, vpath[i1].x - dlx0, vpath[i1].y - dly0);
201       art_vpath_add_point (p_rev, pn_rev, pn_rev_max,
202                        ART_LINETO, vpath[i1].x + dlx0, vpath[i1].y + dly0);
203     }
204   else if (cross > 0)
205     {
206       /* left turn, forw is outside and rev is inside */
207
208 #ifdef VERBOSE
209       printf ("%% render_seg: left\n");
210 #endif
211       if (
212 #ifdef NO_OPTIMIZE_INNER
213           0 &&
214 #endif
215           (dmr2 > EPSILON_2) &&
216           /* check that i1 + dm[xy] is inside i0-i1 rectangle */
217           (dx0 + dmx) * dx0 + (dy0 + dmy) * dy0 > 0 &&
218           /* and that i1 + dm[xy] is inside i1-i2 rectangle */
219           ((dx1 - dmx) * dx1 + (dy1 - dmy) * dy1 > 0)
220 #ifdef PEDANTIC_INNER
221           &&
222           /* check that i1 + dl[xy]1 is inside i0-i1 rectangle */
223           (dx0 + dlx1) * dx0 + (dy0 + dly1) * dy0 > 0 &&
224           /* and that i1 + dl[xy]0 is inside i1-i2 rectangle */
225           ((dx1 - dlx0) * dx1 + (dy1 - dly0) * dy1 > 0)
226 #endif
227           )
228         {
229           /* can safely add single intersection point */
230           art_vpath_add_point (p_rev, pn_rev, pn_rev_max,
231                            ART_LINETO, vpath[i1].x + dmx, vpath[i1].y + dmy);
232         }
233       else
234         {
235           /* need to loop-de-loop the inside */
236           art_vpath_add_point (p_rev, pn_rev, pn_rev_max,
237                            ART_LINETO, vpath[i1].x + dlx0, vpath[i1].y + dly0);
238           art_vpath_add_point (p_rev, pn_rev, pn_rev_max,
239                            ART_LINETO, vpath[i1].x, vpath[i1].y);
240           art_vpath_add_point (p_rev, pn_rev, pn_rev_max,
241                            ART_LINETO, vpath[i1].x + dlx1, vpath[i1].y + dly1);
242         }
243
244       if (join == ART_PATH_STROKE_JOIN_BEVEL)
245         {
246           /* bevel */
247           art_vpath_add_point (p_forw, pn_forw, pn_forw_max,
248                            ART_LINETO, vpath[i1].x - dlx0, vpath[i1].y - dly0);
249           art_vpath_add_point (p_forw, pn_forw, pn_forw_max,
250                            ART_LINETO, vpath[i1].x - dlx1, vpath[i1].y - dly1);
251         }
252       else if (join == ART_PATH_STROKE_JOIN_MITER)
253         {
254           art_vpath_add_point (p_forw, pn_forw, pn_forw_max,
255                            ART_LINETO, vpath[i1].x - dmx, vpath[i1].y - dmy);
256         }
257       else if (join == ART_PATH_STROKE_JOIN_ROUND) {
258         art_svp_vpath_stroke_arc (p_forw, pn_forw, pn_forw_max,
259                                   vpath[i1].x, vpath[i1].y,
260                                   -dlx0, -dly0,
261                                   -dlx1, -dly1,
262                                   line_width,
263                                   flatness);
264       }
265     }
266   else
267     {
268       /* right turn, rev is outside and forw is inside */
269 #ifdef VERBOSE
270       printf ("%% render_seg: right\n");
271 #endif
272
273       if (
274 #ifdef NO_OPTIMIZE_INNER
275           0 &&
276 #endif
277           (dmr2 > EPSILON_2) &&
278           /* check that i1 - dm[xy] is inside i0-i1 rectangle */
279           (dx0 - dmx) * dx0 + (dy0 - dmy) * dy0 > 0 &&
280           /* and that i1 - dm[xy] is inside i1-i2 rectangle */
281           ((dx1 + dmx) * dx1 + (dy1 + dmy) * dy1 > 0)
282 #ifdef PEDANTIC_INNER
283           &&
284           /* check that i1 - dl[xy]1 is inside i0-i1 rectangle */
285           (dx0 - dlx1) * dx0 + (dy0 - dly1) * dy0 > 0 &&
286           /* and that i1 - dl[xy]0 is inside i1-i2 rectangle */
287           ((dx1 + dlx0) * dx1 + (dy1 + dly0) * dy1 > 0)
288 #endif
289           )
290         {
291           /* can safely add single intersection point */
292           art_vpath_add_point (p_forw, pn_forw, pn_forw_max,
293                            ART_LINETO, vpath[i1].x - dmx, vpath[i1].y - dmy);
294         }
295       else
296         {
297           /* need to loop-de-loop the inside */
298           art_vpath_add_point (p_forw, pn_forw, pn_forw_max,
299                            ART_LINETO, vpath[i1].x - dlx0, vpath[i1].y - dly0);
300           art_vpath_add_point (p_forw, pn_forw, pn_forw_max,
301                            ART_LINETO, vpath[i1].x, vpath[i1].y);
302           art_vpath_add_point (p_forw, pn_forw, pn_forw_max,
303                            ART_LINETO, vpath[i1].x - dlx1, vpath[i1].y - dly1);
304         }
305
306       if (join == ART_PATH_STROKE_JOIN_BEVEL)
307         {
308           /* bevel */
309           art_vpath_add_point (p_rev, pn_rev, pn_rev_max,
310                            ART_LINETO, vpath[i1].x + dlx0, vpath[i1].y + dly0);
311           art_vpath_add_point (p_rev, pn_rev, pn_rev_max,
312                            ART_LINETO, vpath[i1].x + dlx1, vpath[i1].y + dly1);
313         }
314       else if (join == ART_PATH_STROKE_JOIN_MITER)
315         {
316           art_vpath_add_point (p_rev, pn_rev, pn_rev_max,
317                            ART_LINETO, vpath[i1].x + dmx, vpath[i1].y + dmy);
318         }
319       else if (join == ART_PATH_STROKE_JOIN_ROUND) {
320         art_svp_vpath_stroke_arc (p_rev, pn_rev, pn_rev_max,
321                                   vpath[i1].x, vpath[i1].y,
322                                   dlx0, dly0,
323                                   dlx1, dly1,
324                                   -line_width,
325                                   flatness);
326       }
327
328     }
329 }
330
331 /* caps i1, under the assumption of a vector from i0 */
332 static void
333 render_cap (ArtVpath **p_result, int *pn_result, int *pn_result_max,
334             ArtVpath *vpath, int i0, int i1,
335             ArtPathStrokeCapType cap, double line_width, double flatness)
336 {
337   double dx0, dy0;
338   double dlx0, dly0;
339   double scale;
340   int n_pts;
341   int i;
342
343   dx0 = vpath[i1].x - vpath[i0].x;
344   dy0 = vpath[i1].y - vpath[i0].y;
345
346   /* Set dl[xy]0 to the vector from i0 to i1, rotated counterclockwise
347      90 degrees, and scaled to the length of line_width. */
348   scale = line_width / sqrt (dx0 * dx0 + dy0 * dy0);
349   dlx0 = dy0 * scale;
350   dly0 = -dx0 * scale;
351
352 #ifdef VERBOSE
353   printf ("cap style = %d\n", cap);
354 #endif
355
356   switch (cap)
357     {
358     case ART_PATH_STROKE_CAP_BUTT:
359       art_vpath_add_point (p_result, pn_result, pn_result_max,
360                            ART_LINETO, vpath[i1].x - dlx0, vpath[i1].y - dly0);
361       art_vpath_add_point (p_result, pn_result, pn_result_max,
362                            ART_LINETO, vpath[i1].x + dlx0, vpath[i1].y + dly0);
363       break;
364     case ART_PATH_STROKE_CAP_ROUND:
365       n_pts = ceil (M_PI / (2.0 * M_SQRT2 * sqrt (flatness / line_width)));
366       art_vpath_add_point (p_result, pn_result, pn_result_max,
367                            ART_LINETO, vpath[i1].x - dlx0, vpath[i1].y - dly0);
368       for (i = 1; i < n_pts; i++)
369         {
370           double theta, c_th, s_th;
371
372           theta = M_PI * i / n_pts;
373           c_th = cos (theta);
374           s_th = sin (theta);
375           art_vpath_add_point (p_result, pn_result, pn_result_max,
376                                ART_LINETO,
377                                vpath[i1].x - dlx0 * c_th - dly0 * s_th,
378                                vpath[i1].y - dly0 * c_th + dlx0 * s_th);
379         }
380       art_vpath_add_point (p_result, pn_result, pn_result_max,
381                            ART_LINETO, vpath[i1].x + dlx0, vpath[i1].y + dly0);
382       break;
383     case ART_PATH_STROKE_CAP_SQUARE:
384       art_vpath_add_point (p_result, pn_result, pn_result_max,
385                            ART_LINETO,
386                            vpath[i1].x - dlx0 - dly0,
387                            vpath[i1].y - dly0 + dlx0);
388       art_vpath_add_point (p_result, pn_result, pn_result_max,
389                            ART_LINETO,
390                            vpath[i1].x + dlx0 - dly0,
391                            vpath[i1].y + dly0 + dlx0);
392       break;
393     }
394 }
395
396 /**
397  * art_svp_from_vpath_raw: Stroke a vector path, raw version
398  * @vpath: #ArtVPath to stroke.
399  * @join: Join style.
400  * @cap: Cap style.
401  * @line_width: Width of stroke.
402  * @miter_limit: Miter limit.
403  * @flatness: Flatness.
404  *
405  * Exactly the same as art_svp_vpath_stroke(), except that the resulting
406  * stroke outline may self-intersect and have regions of winding number
407  * greater than 1.
408  *
409  * Return value: Resulting raw stroked outline in svp format.
410  **/
411 ArtVpath *
412 art_svp_vpath_stroke_raw (ArtVpath *vpath,
413                           ArtPathStrokeJoinType join,
414                           ArtPathStrokeCapType cap,
415                           double line_width,
416                           double miter_limit,
417                           double flatness)
418 {
419   int begin_idx, end_idx;
420   int i;
421   ArtVpath *forw, *rev;
422   int n_forw, n_rev;
423   int n_forw_max, n_rev_max;
424   ArtVpath *result;
425   int n_result, n_result_max;
426   double half_lw = 0.5 * line_width;
427   int closed;
428   int last, xthis, next, second;
429   double dx, dy;
430
431   n_forw_max = 16;
432   forw = art_new (ArtVpath, n_forw_max);
433
434   n_rev_max = 16;
435   rev = art_new (ArtVpath, n_rev_max);
436
437   n_result = 0;
438   n_result_max = 16;
439   result = art_new (ArtVpath, n_result_max);
440
441   for (begin_idx = 0; vpath[begin_idx].code != ART_END; begin_idx = end_idx)
442     {
443       n_forw = 0;
444       n_rev = 0;
445
446       closed = (vpath[begin_idx].code == ART_MOVETO);
447
448       /* we don't know what the first point joins with until we get to the
449          last point and see if it's closed. So we start with the second
450          line in the path.
451
452          Note: this is not strictly true (we now know it's closed from
453          the opening pathcode), but why fix code that isn't broken?
454       */
455
456       xthis = begin_idx;
457       /* skip over identical points at the beginning of the subpath */
458       for (i = xthis + 1; vpath[i].code == ART_LINETO; i++)
459         {
460           dx = vpath[i].x - vpath[xthis].x;
461           dy = vpath[i].y - vpath[xthis].y;
462           if (dx * dx + dy * dy > EPSILON_2)
463             break;
464         }
465       next = i;
466       second = next;
467
468       /* invariant: this doesn't coincide with next */
469       while (vpath[next].code == ART_LINETO)
470         {
471           last = xthis;
472           xthis = next;
473           /* skip over identical points after the beginning of the subpath */
474           for (i = xthis + 1; vpath[i].code == ART_LINETO; i++)
475             {
476               dx = vpath[i].x - vpath[xthis].x;
477               dy = vpath[i].y - vpath[xthis].y;
478               if (dx * dx + dy * dy > EPSILON_2)
479                 break;
480             }
481           next = i;
482           if (vpath[next].code != ART_LINETO)
483             {
484               /* reached end of path */
485               /* make "closed" detection conform to PostScript
486                  semantics (i.e. explicit closepath code rather than
487                  just the fact that end of the path is the beginning) */
488               if (closed &&
489                   vpath[xthis].x == vpath[begin_idx].x &&
490                   vpath[xthis].y == vpath[begin_idx].y)
491                 {
492                   int j;
493
494                   /* path is closed, render join to beginning */
495                   render_seg (&forw, &n_forw, &n_forw_max,
496                               &rev, &n_rev, &n_rev_max,
497                               vpath, last, xthis, second,
498                               join, half_lw, miter_limit, flatness);
499
500 #ifdef VERBOSE
501                   printf ("%% forw %d, rev %d\n", n_forw, n_rev);
502 #endif
503                   /* do forward path */
504                   art_vpath_add_point (&result, &n_result, &n_result_max,
505                                    ART_MOVETO, forw[n_forw - 1].x,
506                                    forw[n_forw - 1].y);
507                   for (j = 0; j < n_forw; j++)
508                     art_vpath_add_point (&result, &n_result, &n_result_max,
509                                      ART_LINETO, forw[j].x,
510                                      forw[j].y);
511
512                   /* do reverse path, reversed */
513                   art_vpath_add_point (&result, &n_result, &n_result_max,
514                                    ART_MOVETO, rev[0].x,
515                                    rev[0].y);
516                   for (j = n_rev - 1; j >= 0; j--)
517                     art_vpath_add_point (&result, &n_result, &n_result_max,
518                                      ART_LINETO, rev[j].x,
519                                      rev[j].y);
520                 }
521               else
522                 {
523                   /* path is open */
524                   int j;
525
526                   /* add to forw rather than result to ensure that
527                      forw has at least one point. */
528                   render_cap (&forw, &n_forw, &n_forw_max,
529                               vpath, last, xthis,
530                               cap, half_lw, flatness);
531                   art_vpath_add_point (&result, &n_result, &n_result_max,
532                                    ART_MOVETO, forw[0].x,
533                                    forw[0].y);
534                   for (j = 1; j < n_forw; j++)
535                     art_vpath_add_point (&result, &n_result, &n_result_max,
536                                      ART_LINETO, forw[j].x,
537                                      forw[j].y);
538                   for (j = n_rev - 1; j >= 0; j--)
539                     art_vpath_add_point (&result, &n_result, &n_result_max,
540                                      ART_LINETO, rev[j].x,
541                                      rev[j].y);
542                   render_cap (&result, &n_result, &n_result_max,
543                               vpath, second, begin_idx,
544                               cap, half_lw, flatness);
545                   art_vpath_add_point (&result, &n_result, &n_result_max,
546                                    ART_LINETO, forw[0].x,
547                                    forw[0].y);
548                 }
549             }
550           else
551             render_seg (&forw, &n_forw, &n_forw_max,
552                         &rev, &n_rev, &n_rev_max,
553                         vpath, last, xthis, next,
554                         join, half_lw, miter_limit, flatness);
555         }
556       end_idx = next;
557     }
558
559   art_free (forw);
560   art_free (rev);
561 #ifdef VERBOSE
562   printf ("%% n_result = %d\n", n_result);
563 #endif
564   art_vpath_add_point (&result, &n_result, &n_result_max, ART_END, 0, 0);
565   return result;
566 }
567
568 #define noVERBOSE
569
570 #ifdef VERBOSE
571
572 #define XOFF 50
573 #define YOFF 700
574
575 static void
576 print_ps_vpath (ArtVpath *vpath)
577 {
578   int i;
579
580   for (i = 0; vpath[i].code != ART_END; i++)
581     {
582       switch (vpath[i].code)
583         {
584         case ART_MOVETO:
585           printf ("%g %g moveto\n", XOFF + vpath[i].x, YOFF - vpath[i].y);
586           break;
587         case ART_LINETO:
588           printf ("%g %g lineto\n", XOFF + vpath[i].x, YOFF - vpath[i].y);
589           break;
590         default:
591           break;
592         }
593     }
594   printf ("stroke showpage\n");
595 }
596
597 static void
598 print_ps_svp (ArtSVP *vpath)
599 {
600   int i, j;
601
602   printf ("%% begin\n");
603   for (i = 0; i < vpath->n_segs; i++)
604     {
605       printf ("%g setgray\n", vpath->segs[i].dir ? 0.7 : 0);
606       for (j = 0; j < vpath->segs[i].n_points; j++)
607         {
608           printf ("%g %g %s\n",
609                   XOFF + vpath->segs[i].points[j].x,
610                   YOFF - vpath->segs[i].points[j].y,
611                   j ? "lineto" : "moveto");
612         }
613       printf ("stroke\n");
614     }
615
616   printf ("showpage\n");
617 }
618 #endif
619
620 /* Render a vector path into a stroked outline.
621
622    Status of this routine:
623
624    Basic correctness: Only miter and bevel line joins are implemented,
625    and only butt line caps. Otherwise, seems to be fine.
626
627    Numerical stability: We cheat (adding random perturbation). Thus,
628    it seems very likely that no numerical stability problems will be
629    seen in practice.
630
631    Speed: Should be pretty good.
632
633    Precision: The perturbation fuzzes the coordinates slightly,
634    but not enough to be visible.  */
635 /**
636  * art_svp_vpath_stroke: Stroke a vector path.
637  * @vpath: #ArtVPath to stroke.
638  * @join: Join style.
639  * @cap: Cap style.
640  * @line_width: Width of stroke.
641  * @miter_limit: Miter limit.
642  * @flatness: Flatness.
643  *
644  * Computes an svp representing the stroked outline of @vpath. The
645  * width of the stroked line is @line_width.
646  *
647  * Lines are joined according to the @join rule. Possible values are
648  * ART_PATH_STROKE_JOIN_MITER (for mitered joins),
649  * ART_PATH_STROKE_JOIN_ROUND (for round joins), and
650  * ART_PATH_STROKE_JOIN_BEVEL (for bevelled joins). The mitered join
651  * is converted to a bevelled join if the miter would extend to a
652  * distance of more than @miter_limit * @line_width from the actual
653  * join point.
654  *
655  * If there are open subpaths, the ends of these subpaths are capped
656  * according to the @cap rule. Possible values are
657  * ART_PATH_STROKE_CAP_BUTT (squared cap, extends exactly to end
658  * point), ART_PATH_STROKE_CAP_ROUND (rounded half-circle centered at
659  * the end point), and ART_PATH_STROKE_CAP_SQUARE (squared cap,
660  * extending half @line_width past the end point).
661  *
662  * The @flatness parameter controls the accuracy of the rendering. It
663  * is most important for determining the number of points to use to
664  * approximate circular arcs for round lines and joins. In general, the
665  * resulting vector path will be within @flatness pixels of the "ideal"
666  * path containing actual circular arcs. I reserve the right to use
667  * the @flatness parameter to convert bevelled joins to miters for very
668  * small turn angles, as this would reduce the number of points in the
669  * resulting outline path.
670  *
671  * The resulting path is "clean" with respect to self-intersections, i.e.
672  * the winding number is 0 or 1 at each point.
673  *
674  * Return value: Resulting stroked outline in svp format.
675  **/
676 ArtSVP *
677 art_svp_vpath_stroke (ArtVpath *vpath,
678                       ArtPathStrokeJoinType join,
679                       ArtPathStrokeCapType cap,
680                       double line_width,
681                       double miter_limit,
682                       double flatness)
683 {
684 #ifdef ART_USE_NEW_INTERSECTOR
685   ArtVpath *vpath_stroke;
686   ArtSVP *svp, *svp2;
687   ArtSvpWriter *swr;
688
689   vpath_stroke = art_svp_vpath_stroke_raw (vpath, join, cap,
690                                            line_width, miter_limit, flatness);
691 #ifdef VERBOSE
692   //print_ps_vpath (vpath_stroke);
693 #endif
694   svp = art_svp_from_vpath (vpath_stroke);
695 #ifdef VERBOSE
696   //print_ps_svp (svp);
697 #endif
698   art_free (vpath_stroke);
699
700   swr = art_svp_writer_rewind_new (ART_WIND_RULE_NONZERO);
701   art_svp_intersector (svp, swr);
702
703   svp2 = art_svp_writer_rewind_reap (swr);
704 #ifdef VERBOSE
705   //print_ps_svp (svp2);
706 #endif
707   art_svp_free (svp);
708   return svp2;
709 #else
710   ArtVpath *vpath_stroke, *vpath2;
711   ArtSVP *svp, *svp2, *svp3;
712
713   vpath_stroke = art_svp_vpath_stroke_raw (vpath, join, cap,
714                                            line_width, miter_limit, flatness);
715 #ifdef VERBOSE
716   //print_ps_vpath (vpath_stroke);
717 #endif
718   vpath2 = art_vpath_perturb (vpath_stroke);
719 #ifdef VERBOSE
720   //print_ps_vpath (vpath2);
721 #endif
722   art_free (vpath_stroke);
723   svp = art_svp_from_vpath (vpath2);
724 #ifdef VERBOSE
725   //print_ps_svp (svp);
726 #endif
727   art_free (vpath2);
728   svp2 = art_svp_uncross (svp);
729 #ifdef VERBOSE
730   //print_ps_svp (svp2);
731 #endif
732   art_svp_free (svp);
733   svp3 = art_svp_rewind_uncrossed (svp2, ART_WIND_RULE_NONZERO);
734 #ifdef VERBOSE
735   //print_ps_svp (svp3);
736 #endif
737   art_svp_free (svp2);
738
739   return svp3;
740 #endif
741 }