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 }