libraries/libart_lgpl-2.3.7/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 <stdlib.h>
  22 #include <math.h>
  23
  24 #include "art_misc.h"
  25
  26 #include "art_vpath.h"
  27 #include "art_svp.h"
  28 #ifdef ART_USE_NEW_INTERSECTOR
  29 #include "art_svp_intersect.h"
  30 #else
  31 #include "art_svp_wind.h"
  32 #endif
  33 #include "art_svp_vpath.h"
  34 #include "art_svp_vpath_stroke.h"
  35
  36 #define EPSILON 1e-6
  37 #define EPSILON_2 1e-12
  38
  39 #define yes_OPTIMIZE_INNER
  40
  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.
  44
  45    A positive value of radius means curve to the left, negative means
  46    curve to the right.
  47 */
  48 static void
  49 art_svp_vpath_stroke_arc (ArtVpath **p_vpath, int *pn, int *pn_max,
  50                           double xc, double yc,
  51                           double x0, double y0,
  52                           double x1, double y1,
  53                           double radius,
  54                           double flatness)
  55 {
  56   double theta;
  57   double th_0, th_1;
  58   int n_pts;
  59   int i;
  60   double aradius;
  61
  62   aradius = fabs (radius);
  63   theta = 2 * M_SQRT2 * sqrt (flatness / aradius);
  64   th_0 = atan2 (y0, x0);
  65   th_1 = atan2 (y1, x1);
  66   if (radius > 0)
  67     {
  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);
  71     }
  72   else
  73     {
  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);
  77     }
  78 #ifdef VERBOSE
  79   printf ("start %f %f; th_0 = %f, th_1 = %f, r = %f, theta = %f\n", x0, y0, th_0, th_1, radius, theta);
  80 #endif
  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++)
  84     {
  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);
  89 #ifdef VERBOSE
  90       printf ("mid %f %f\n", cos (theta) * radius, sin (theta) * radius);
  91 #endif
  92     }
  93   art_vpath_add_point (p_vpath, pn, pn_max,
  94                        ART_LINETO, xc + x1, yc + y1);
  95 #ifdef VERBOSE
  96   printf ("end %f %f\n", x1, y1);
  97 #endif
  98 }
  99
 100 /* Assume that forw and rev are at point i0. Bring them to i1,
 101    joining with the vector i1 - i2.
 102
 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.}
 108
 109    forw is to the line's right and rev is to its left.
 110
 111    Precondition: no zero-length vectors, otherwise a divide by
 112    zero will happen.  */
 113 static void
 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)
 119 {
 120   double dx0, dy0;
 121   double dx1, dy1;
 122   double dlx0, dly0;
 123   double dlx1, dly1;
 124   double dmx, dmy;
 125   double dmr2;
 126   double scale;
 127   double cross;
 128
 129 #ifdef VERBOSE
 130   printf ("join style = %d\n", join);
 131 #endif
 132
 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;
 136
 137   dx1 = vpath[i2].x - vpath[i1].x;
 138   dy1 = vpath[i2].y - vpath[i1].y;
 139
 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);
 143   dlx0 = dy0 * scale;
 144   dly0 = -dx0 * scale;
 145
 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);
 149   dlx1 = dy1 * scale;
 150   dly1 = -dx1 * scale;
 151
 152 #ifdef VERBOSE
 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);
 157
 158   printf ("%% render_seg: d[xy]0 = (%g, %g), dl[xy]0 = (%g, %g)\n",
 159           dx0, dy0, dlx0, dly0);
 160
 161   printf ("%% render_seg: d[xy]1 = (%g, %g), dl[xy]1 = (%g, %g)\n",
 162           dx1, dy1, dlx1, dly1);
 163 #endif
 164
 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. */
 167
 168   /* positive for positive area (i.e. left turn) */
 169   cross = dx1 * dy0 - dx0 * dy1;
 170
 171   dmx = (dlx0 + dlx1) * 0.5;
 172   dmy = (dly0 + dly1) * 0.5;
 173   dmr2 = dmx * dmx + dmy * dmy;
 174
 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;
 178
 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;
 182   dmx *= scale;
 183   dmy *= scale;
 184
 185   if (cross * cross < EPSILON_2 && dx0 * dx1 + dy0 * dy1 >= 0)
 186     {
 187       /* going straight */
 188 #ifdef VERBOSE
 189       printf ("%% render_seg: straight\n");
 190 #endif
 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);
 195     }
 196   else if (cross > 0)
 197     {
 198       /* left turn, forw is outside and rev is inside */
 199
 200 #ifdef VERBOSE
 201       printf ("%% render_seg: left\n");
 202 #endif
 203       if (
 204 #ifdef NO_OPTIMIZE_INNER
 205           0 &&
 206 #endif
 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
 212           &&
 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)
 217 #endif
 218           )
 219         {
 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);
 223         }
 224       else
 225         {
 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);
 233         }
 234
 235       if (join == ART_PATH_STROKE_JOIN_BEVEL)
 236         {
 237           /* 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);
 242         }
 243       else if (join == ART_PATH_STROKE_JOIN_MITER)
 244         {
 245           art_vpath_add_point (p_forw, pn_forw, pn_forw_max,
 246                            ART_LINETO, vpath[i1].x - dmx, vpath[i1].y - dmy);
 247         }
 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,
 251                                   -dlx0, -dly0,
 252                                   -dlx1, -dly1,
 253                                   line_width,
 254                                   flatness);
 255     }
 256   else
 257     {
 258       /* right turn, rev is outside and forw is inside */
 259 #ifdef VERBOSE
 260       printf ("%% render_seg: right\n");
 261 #endif
 262
 263       if (
 264 #ifdef NO_OPTIMIZE_INNER
 265           0 &&
 266 #endif
 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
 272           &&
 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)
 277 #endif
 278           )
 279         {
 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);
 283         }
 284       else
 285         {
 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);
 293         }
 294
 295       if (join == ART_PATH_STROKE_JOIN_BEVEL)
 296         {
 297           /* 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);
 302         }
 303       else if (join == ART_PATH_STROKE_JOIN_MITER)
 304         {
 305           art_vpath_add_point (p_rev, pn_rev, pn_rev_max,
 306                            ART_LINETO, vpath[i1].x + dmx, vpath[i1].y + dmy);
 307         }
 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,
 311                                   dlx0, dly0,
 312                                   dlx1, dly1,
 313                                   -line_width,
 314                                   flatness);
 315
 316     }
 317 }
 318
 319 /* caps i1, under the assumption of a vector from i0 */
 320 static void
 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)
 324 {
 325   double dx0, dy0;
 326   double dlx0, dly0;
 327   double scale;
 328   int n_pts;
 329   int i;
 330
 331   dx0 = vpath[i1].x - vpath[i0].x;
 332   dy0 = vpath[i1].y - vpath[i0].y;
 333
 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);
 337   dlx0 = dy0 * scale;
 338   dly0 = -dx0 * scale;
 339
 340 #ifdef VERBOSE
 341   printf ("cap style = %d\n", cap);
 342 #endif
 343
 344   switch (cap)
 345     {
 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);
 351       break;
 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++)
 357         {
 358           double theta, c_th, s_th;
 359
 360           theta = M_PI * i / n_pts;
 361           c_th = cos (theta);
 362           s_th = sin (theta);
 363           art_vpath_add_point (p_result, pn_result, pn_result_max,
 364                                ART_LINETO,
 365                                vpath[i1].x - dlx0 * c_th - dly0 * s_th,
 366                                vpath[i1].y - dly0 * c_th + dlx0 * s_th);
 367         }
 368       art_vpath_add_point (p_result, pn_result, pn_result_max,
 369                            ART_LINETO, vpath[i1].x + dlx0, vpath[i1].y + dly0);
 370       break;
 371     case ART_PATH_STROKE_CAP_SQUARE:
 372       art_vpath_add_point (p_result, pn_result, pn_result_max,
 373                            ART_LINETO,
 374                            vpath[i1].x - dlx0 - dly0,
 375                            vpath[i1].y - dly0 + dlx0);
 376       art_vpath_add_point (p_result, pn_result, pn_result_max,
 377                            ART_LINETO,
 378                            vpath[i1].x + dlx0 - dly0,
 379                            vpath[i1].y + dly0 + dlx0);
 380       break;
 381     }
 382 }
 383
 384 /**
 385  * art_svp_from_vpath_raw: Stroke a vector path, raw version
 386  * @vpath: #ArtVPath to stroke.
 387  * @join: Join style.
 388  * @cap: Cap style.
 389  * @line_width: Width of stroke.
 390  * @miter_limit: Miter limit.
 391  * @flatness: Flatness.
 392  *
 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
 395  * greater than 1.
 396  *
 397  * Return value: Resulting raw stroked outline in svp format.
 398  **/
 399 ArtVpath *
 400 art_svp_vpath_stroke_raw (ArtVpath *vpath,
 401                           ArtPathStrokeJoinType join,
 402                           ArtPathStrokeCapType cap,
 403                           double line_width,
 404                           double miter_limit,
 405                           double flatness)
 406 {
 407   int begin_idx, end_idx;
 408   int i;
 409   ArtVpath *forw, *rev;
 410   int n_forw, n_rev;
 411   int n_forw_max, n_rev_max;
 412   ArtVpath *result;
 413   int n_result, n_result_max;
 414   double half_lw = 0.5 * line_width;
 415   int closed;
 416   int last, this, next, second;
 417   double dx, dy;
 418
 419   n_forw_max = 16;
 420   forw = art_new (ArtVpath, n_forw_max);
 421
 422   n_rev_max = 16;
 423   rev = art_new (ArtVpath, n_rev_max);
 424
 425   n_result = 0;
 426   n_result_max = 16;
 427   result = art_new (ArtVpath, n_result_max);
 428
 429   for (begin_idx = 0; vpath[begin_idx].code != ART_END; begin_idx = end_idx)
 430     {
 431       n_forw = 0;
 432       n_rev = 0;
 433
 434       closed = (vpath[begin_idx].code == ART_MOVETO);
 435
 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
 438          line in the path.
 439
 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?
 442       */
 443
 444       this = begin_idx;
 445       /* skip over identical points at the beginning of the subpath */
 446       for (i = this + 1; vpath[i].code == ART_LINETO; i++)
 447         {
 448           dx = vpath[i].x - vpath[this].x;
 449           dy = vpath[i].y - vpath[this].y;
 450           if (dx * dx + dy * dy > EPSILON_2)
 451             break;
 452         }
 453       next = i;
 454       second = next;
 455
 456       /* invariant: this doesn't coincide with next */
 457       while (vpath[next].code == ART_LINETO)
 458         {
 459           last = this;
 460           this = next;
 461           /* skip over identical points after the beginning of the subpath */
 462           for (i = this + 1; vpath[i].code == ART_LINETO; i++)
 463             {
 464               dx = vpath[i].x - vpath[this].x;
 465               dy = vpath[i].y - vpath[this].y;
 466               if (dx * dx + dy * dy > EPSILON_2)
 467                 break;
 468             }
 469           next = i;
 470           if (vpath[next].code != ART_LINETO)
 471             {
 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) */
 476               if (closed &&
 477                   vpath[this].x == vpath[begin_idx].x &&
 478                   vpath[this].y == vpath[begin_idx].y)
 479                 {
 480                   int j;
 481
 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);
 487
 488 #ifdef VERBOSE
 489                   printf ("%% forw %d, rev %d\n", n_forw, n_rev);
 490 #endif
 491                   /* do forward path */
 492                   art_vpath_add_point (&result, &n_result, &n_result_max,
 493                                    ART_MOVETO, forw[n_forw - 1].x,
 494                                    forw[n_forw - 1].y);
 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,
 498                                      forw[j].y);
 499
 500                   /* do reverse path, reversed */
 501                   art_vpath_add_point (&result, &n_result, &n_result_max,
 502                                    ART_MOVETO, rev[0].x,
 503                                    rev[0].y);
 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,
 507                                      rev[j].y);
 508                 }
 509               else
 510                 {
 511                   /* path is open */
 512                   int j;
 513
 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,
 517                               vpath, last, this,
 518                               cap, half_lw, flatness);
 519                   art_vpath_add_point (&result, &n_result, &n_result_max,
 520                                    ART_MOVETO, forw[0].x,
 521                                    forw[0].y);
 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,
 525                                      forw[j].y);
 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,
 529                                      rev[j].y);
 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,
 535                                    forw[0].y);
 536                 }
 537             }
 538           else
 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);
 543         }
 544       end_idx = next;
 545     }
 546
 547   art_free (forw);
 548   art_free (rev);
 549 #ifdef VERBOSE
 550   printf ("%% n_result = %d\n", n_result);
 551 #endif
 552   art_vpath_add_point (&result, &n_result, &n_result_max, ART_END, 0, 0);
 553   return result;
 554 }
 555
 556 #define noVERBOSE
 557
 558 #ifdef VERBOSE
 559
 560 #define XOFF 50
 561 #define YOFF 700
 562
 563 static void
 564 print_ps_vpath (ArtVpath *vpath)
 565 {
 566   int i;
 567
 568   for (i = 0; vpath[i].code != ART_END; i++)
 569     {
 570       switch (vpath[i].code)
 571         {
 572         case ART_MOVETO:
 573           printf ("%g %g moveto\n", XOFF + vpath[i].x, YOFF - vpath[i].y);
 574           break;
 575         case ART_LINETO:
 576           printf ("%g %g lineto\n", XOFF + vpath[i].x, YOFF - vpath[i].y);
 577           break;
 578         default:
 579           break;
 580         }
 581     }
 582   printf ("stroke showpage\n");
 583 }
 584
 585 static void
 586 print_ps_svp (ArtSVP *vpath)
 587 {
 588   int i, j;
 589
 590   printf ("%% begin\n");
 591   for (i = 0; i < vpath->n_segs; i++)
 592     {
 593       printf ("%g setgray\n", vpath->segs[i].dir ? 0.7 : 0);
 594       for (j = 0; j < vpath->segs[i].n_points; j++)
 595         {
 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");
 600         }
 601       printf ("stroke\n");
 602     }
 603
 604   printf ("showpage\n");
 605 }
 606 #endif
 607
 608 /* Render a vector path into a stroked outline.
 609
 610    Status of this routine:
 611
 612    Basic correctness: Only miter and bevel line joins are implemented,
 613    and only butt line caps. Otherwise, seems to be fine.
 614
 615    Numerical stability: We cheat (adding random perturbation). Thus,
 616    it seems very likely that no numerical stability problems will be
 617    seen in practice.
 618
 619    Speed: Should be pretty good.
 620
 621    Precision: The perturbation fuzzes the coordinates slightly,
 622    but not enough to be visible.  */
 623 /**
 624  * art_svp_vpath_stroke: Stroke a vector path.
 625  * @vpath: #ArtVPath to stroke.
 626  * @join: Join style.
 627  * @cap: Cap style.
 628  * @line_width: Width of stroke.
 629  * @miter_limit: Miter limit.
 630  * @flatness: Flatness.
 631  *
 632  * Computes an svp representing the stroked outline of @vpath. The
 633  * width of the stroked line is @line_width.
 634  *
 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
 641  * join point.
 642  *
 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).
 649  *
 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.
 658  *
 659  * The resulting path is "clean" with respect to self-intersections, i.e.
 660  * the winding number is 0 or 1 at each point.
 661  *
 662  * Return value: Resulting stroked outline in svp format.
 663  **/
 664 ArtSVP *
 665 art_svp_vpath_stroke (ArtVpath *vpath,
 666                       ArtPathStrokeJoinType join,
 667                       ArtPathStrokeCapType cap,
 668                       double line_width,
 669                       double miter_limit,
 670                       double flatness)
 671 {
 672 #ifdef ART_USE_NEW_INTERSECTOR
 673   ArtVpath *vpath_stroke;
 674   ArtSVP *svp, *svp2;
 675   ArtSvpWriter *swr;
 676
 677   vpath_stroke = art_svp_vpath_stroke_raw (vpath, join, cap,
 678                                            line_width, miter_limit, flatness);
 679 #ifdef VERBOSE
 680   print_ps_vpath (vpath_stroke);
 681 #endif
 682   svp = art_svp_from_vpath (vpath_stroke);
 683 #ifdef VERBOSE
 684   print_ps_svp (svp);
 685 #endif
 686   art_free (vpath_stroke);
 687
 688   swr = art_svp_writer_rewind_new (ART_WIND_RULE_NONZERO);
 689   art_svp_intersector (svp, swr);
 690
 691   svp2 = art_svp_writer_rewind_reap (swr);
 692 #ifdef VERBOSE
 693   print_ps_svp (svp2);
 694 #endif
 695   art_svp_free (svp);
 696   return svp2;
 697 #else
 698   ArtVpath *vpath_stroke, *vpath2;
 699   ArtSVP *svp, *svp2, *svp3;
 700
 701   vpath_stroke = art_svp_vpath_stroke_raw (vpath, join, cap,
 702                                            line_width, miter_limit, flatness);
 703 #ifdef VERBOSE
 704   print_ps_vpath (vpath_stroke);
 705 #endif
 706   vpath2 = art_vpath_perturb (vpath_stroke);
 707 #ifdef VERBOSE
 708   print_ps_vpath (vpath2);
 709 #endif
 710   art_free (vpath_stroke);
 711   svp = art_svp_from_vpath (vpath2);
 712 #ifdef VERBOSE
 713   print_ps_svp (svp);
 714 #endif
 715   art_free (vpath2);
 716   svp2 = art_svp_uncross (svp);
 717 #ifdef VERBOSE
 718   print_ps_svp (svp2);
 719 #endif
 720   art_svp_free (svp);
 721   svp3 = art_svp_rewind_uncrossed (svp2, ART_WIND_RULE_NONZERO);
 722 #ifdef VERBOSE
 723   print_ps_svp (svp3);
 724 #endif
 725   art_svp_free (svp2);
 726
 727   return svp3;
 728 #endif
 729 }