src/cairo-path-stroke-tristrip.c

   1 /* -*- Mode: c; tab-width: 8; c-basic-offset: 4; indent-tabs-mode: t; -*- */
   2 /* cairo - a vector graphics library with display and print output
   3  *
   4  * Copyright © 2002 University of Southern California
   5  * Copyright © 2011 Intel Corporation
   6  *
   7  * This library is free software; you can redistribute it and/or
   8  * modify it either under the terms of the GNU Lesser General Public
   9  * License version 2.1 as published by the Free Software Foundation
  10  * (the "LGPL") or, at your option, under the terms of the Mozilla
  11  * Public License Version 1.1 (the "MPL"). If you do not alter this
  12  * notice, a recipient may use your version of this file under either
  13  * the MPL or the LGPL.
  14  *
  15  * You should have received a copy of the LGPL along with this library
  16  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
  17  * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
  18  * You should have received a copy of the MPL along with this library
  19  * in the file COPYING-MPL-1.1
  20  *
  21  * The contents of this file are subject to the Mozilla Public License
  22  * Version 1.1 (the "License"); you may not use this file except in
  23  * compliance with the License. You may obtain a copy of the License at
  24  * http://www.mozilla.org/MPL/
  25  *
  26  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
  27  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
  28  * the specific language governing rights and limitations.
  29  *
  30  * The Original Code is the cairo graphics library.
  31  *
  32  * The Initial Developer of the Original Code is University of Southern
  33  * California.
  34  *
  35  * Contributor(s):
  36  *      Carl D. Worth <cworth@cworth.org>
  37  *      Chris Wilson <chris@chris-wilson.co.uk>
  38  */
  39
  40 #define _BSD_SOURCE /* for hypot() */
  41 #include "cairoint.h"
  42
  43 #include "cairo-box-private.h"
  44 #include "cairo-boxes-private.h"
  45 #include "cairo-error-private.h"
  46 #include "cairo-path-fixed-private.h"
  47 #include "cairo-slope-private.h"
  48 #include "cairo-tristrip-private.h"
  49
  50 struct stroker {
  51     cairo_stroke_style_t style;
  52
  53     cairo_tristrip_t *strip;
  54
  55     const cairo_matrix_t *ctm;
  56     const cairo_matrix_t *ctm_inverse;
  57     double tolerance;
  58     cairo_bool_t ctm_det_positive;
  59
  60     cairo_pen_t pen;
  61
  62     cairo_bool_t has_sub_path;
  63
  64     cairo_point_t first_point;
  65
  66     cairo_bool_t has_current_face;
  67     cairo_stroke_face_t current_face;
  68
  69     cairo_bool_t has_first_face;
  70     cairo_stroke_face_t first_face;
  71
  72     cairo_box_t limit;
  73     cairo_bool_t has_limits;
  74 };
  75
  76 static inline double
  77 normalize_slope (double *dx, double *dy);
  78
  79 static void
  80 compute_face (const cairo_point_t *point,
  81               const cairo_slope_t *dev_slope,
  82               struct stroker *stroker,
  83               cairo_stroke_face_t *face);
  84
  85 static void
  86 translate_point (cairo_point_t *point, const cairo_point_t *offset)
  87 {
  88     point->x += offset->x;
  89     point->y += offset->y;
  90 }
  91
  92 static int
  93 slope_compare_sgn (double dx1, double dy1, double dx2, double dy2)
  94 {
  95     double  c = (dx1 * dy2 - dx2 * dy1);
  96
  97     if (c > 0) return 1;
  98     if (c < 0) return -1;
  99     return 0;
 100 }
 101
 102 static inline int
 103 range_step (int i, int step, int max)
 104 {
 105     i += step;
 106     if (i < 0)
 107         i = max - 1;
 108     if (i >= max)
 109         i = 0;
 110     return i;
 111 }
 112
 113 /*
 114  * Construct a fan around the midpoint using the vertices from pen between
 115  * inpt and outpt.
 116  */
 117 static void
 118 add_fan (struct stroker *stroker,
 119          const cairo_slope_t *in_vector,
 120          const cairo_slope_t *out_vector,
 121          const cairo_point_t *midpt,
 122          const cairo_point_t *inpt,
 123          const cairo_point_t *outpt,
 124          cairo_bool_t clockwise)
 125 {
 126     int start, stop, step, i, npoints;
 127
 128     if (clockwise) {
 129         step  = 1;
 130
 131         start = _cairo_pen_find_active_cw_vertex_index (&stroker->pen,
 132                                                         in_vector);
 133         if (_cairo_slope_compare (&stroker->pen.vertices[start].slope_cw,
 134                                   in_vector) < 0)
 135             start = range_step (start, 1, stroker->pen.num_vertices);
 136
 137         stop  = _cairo_pen_find_active_cw_vertex_index (&stroker->pen,
 138                                                         out_vector);
 139         if (_cairo_slope_compare (&stroker->pen.vertices[stop].slope_ccw,
 140                                   out_vector) > 0)
 141         {
 142             stop = range_step (stop, -1, stroker->pen.num_vertices);
 143             if (_cairo_slope_compare (&stroker->pen.vertices[stop].slope_cw,
 144                                       in_vector) < 0)
 145                 return;
 146         }
 147
 148         npoints = stop - start;
 149     } else {
 150         step  = -1;
 151
 152         start = _cairo_pen_find_active_ccw_vertex_index (&stroker->pen,
 153                                                          in_vector);
 154         if (_cairo_slope_compare (&stroker->pen.vertices[start].slope_ccw,
 155                                   in_vector) < 0)
 156             start = range_step (start, -1, stroker->pen.num_vertices);
 157
 158         stop  = _cairo_pen_find_active_ccw_vertex_index (&stroker->pen,
 159                                                          out_vector);
 160         if (_cairo_slope_compare (&stroker->pen.vertices[stop].slope_cw,
 161                                   out_vector) > 0)
 162         {
 163             stop = range_step (stop, 1, stroker->pen.num_vertices);
 164             if (_cairo_slope_compare (&stroker->pen.vertices[stop].slope_ccw,
 165                                       in_vector) < 0)
 166                 return;
 167         }
 168
 169         npoints = start - stop;
 170     }
 171     stop = range_step (stop, step, stroker->pen.num_vertices);
 172     if (npoints < 0)
 173         npoints += stroker->pen.num_vertices;
 174     if (npoints <= 1)
 175         return;
 176
 177     for (i = start;
 178          i != stop;
 179         i = range_step (i, step, stroker->pen.num_vertices))
 180     {
 181         cairo_point_t p = *midpt;
 182         translate_point (&p, &stroker->pen.vertices[i].point);
 183         //contour_add_point (stroker, c, &p);
 184     }
 185 }
 186
 187 static int
 188 join_is_clockwise (const cairo_stroke_face_t *in,
 189                    const cairo_stroke_face_t *out)
 190 {
 191     return _cairo_slope_compare (&in->dev_vector, &out->dev_vector) < 0;
 192 }
 193
 194 static void
 195 inner_join (struct stroker *stroker,
 196             const cairo_stroke_face_t *in,
 197             const cairo_stroke_face_t *out,
 198             int clockwise)
 199 {
 200     const cairo_point_t *outpt;
 201
 202     if (clockwise) {
 203         outpt = &out->ccw;
 204     } else {
 205         outpt = &out->cw;
 206     }
 207     //contour_add_point (stroker, inner, &in->point);
 208     //contour_add_point (stroker, inner, outpt);
 209 }
 210
 211 static void
 212 inner_close (struct stroker *stroker,
 213              const cairo_stroke_face_t *in,
 214              cairo_stroke_face_t *out)
 215 {
 216     const cairo_point_t *inpt;
 217
 218     if (join_is_clockwise (in, out)) {
 219         inpt = &out->ccw;
 220     } else {
 221         inpt = &out->cw;
 222     }
 223
 224     //contour_add_point (stroker, inner, &in->point);
 225     //contour_add_point (stroker, inner, inpt);
 226     //*_cairo_contour_first_point (&inner->contour) =
 227         //*_cairo_contour_last_point (&inner->contour);
 228 }
 229
 230 static void
 231 outer_close (struct stroker *stroker,
 232              const cairo_stroke_face_t *in,
 233              const cairo_stroke_face_t *out)
 234 {
 235     const cairo_point_t *inpt, *outpt;
 236     int clockwise;
 237
 238     if (in->cw.x == out->cw.x && in->cw.y == out->cw.y &&
 239         in->ccw.x == out->ccw.x && out->ccw.y == out->ccw.y)
 240     {
 241         return;
 242     }
 243     clockwise = join_is_clockwise (in, out);
 244     if (clockwise) {
 245         inpt = &in->cw;
 246         outpt = &out->cw;
 247     } else {
 248         inpt = &in->ccw;
 249         outpt = &out->ccw;
 250     }
 251
 252     switch (stroker->style.line_join) {
 253     case CAIRO_LINE_JOIN_ROUND:
 254         /* construct a fan around the common midpoint */
 255         add_fan (stroker,
 256                  &in->dev_vector,
 257                  &out->dev_vector,
 258                  &in->point, inpt, outpt,
 259                  clockwise);
 260         break;
 261
 262     case CAIRO_LINE_JOIN_MITER:
 263     default: {
 264         /* dot product of incoming slope vector with outgoing slope vector */
 265         double  in_dot_out = -in->usr_vector.x * out->usr_vector.x +
 266                              -in->usr_vector.y * out->usr_vector.y;
 267         double  ml = stroker->style.miter_limit;
 268
 269         /* Check the miter limit -- lines meeting at an acute angle
 270          * can generate long miters, the limit converts them to bevel
 271          *
 272          * Consider the miter join formed when two line segments
 273          * meet at an angle psi:
 274          *
 275          *         /.\
 276          *        /. .\
 277          *       /./ \.\
 278          *      /./psi\.\
 279          *
 280          * We can zoom in on the right half of that to see:
 281          *
 282          *          |\
 283          *          | \ psi/2
 284          *          |  \
 285          *          |   \
 286          *          |    \
 287          *          |     \
 288          *        miter    \
 289          *       length     \
 290          *          |        \
 291          *          |        .\
 292          *          |    .     \
 293          *          |.   line   \
 294          *           \    width  \
 295          *            \           \
 296          *
 297          *
 298          * The right triangle in that figure, (the line-width side is
 299          * shown faintly with three '.' characters), gives us the
 300          * following expression relating miter length, angle and line
 301          * width:
 302          *
 303          *      1 /sin (psi/2) = miter_length / line_width
 304          *
 305          * The right-hand side of this relationship is the same ratio
 306          * in which the miter limit (ml) is expressed. We want to know
 307          * when the miter length is within the miter limit. That is
 308          * when the following condition holds:
 309          *
 310          *      1/sin(psi/2) <= ml
 311          *      1 <= ml sin(psi/2)
 312          *      1 <= ml² sin²(psi/2)
 313          *      2 <= ml² 2 sin²(psi/2)
 314          *                              2·sin²(psi/2) = 1-cos(psi)
 315          *      2 <= ml² (1-cos(psi))
 316          *
 317          *                              in · out = |in| |out| cos (psi)
 318          *
 319          * in and out are both unit vectors, so:
 320          *
 321          *                              in · out = cos (psi)
 322          *
 323          *      2 <= ml² (1 - in · out)
 324          *
 325          */
 326         if (2 <= ml * ml * (1 - in_dot_out)) {
 327             double              x1, y1, x2, y2;
 328             double              mx, my;
 329             double              dx1, dx2, dy1, dy2;
 330             double              ix, iy;
 331             double              fdx1, fdy1, fdx2, fdy2;
 332             double              mdx, mdy;
 333
 334             /*
 335              * we've got the points already transformed to device
 336              * space, but need to do some computation with them and
 337              * also need to transform the slope from user space to
 338              * device space
 339              */
 340             /* outer point of incoming line face */
 341             x1 = _cairo_fixed_to_double (inpt->x);
 342             y1 = _cairo_fixed_to_double (inpt->y);
 343             dx1 = in->usr_vector.x;
 344             dy1 = in->usr_vector.y;
 345             cairo_matrix_transform_distance (stroker->ctm, &dx1, &dy1);
 346
 347             /* outer point of outgoing line face */
 348             x2 = _cairo_fixed_to_double (outpt->x);
 349             y2 = _cairo_fixed_to_double (outpt->y);
 350             dx2 = out->usr_vector.x;
 351             dy2 = out->usr_vector.y;
 352             cairo_matrix_transform_distance (stroker->ctm, &dx2, &dy2);
 353
 354             /*
 355              * Compute the location of the outer corner of the miter.
 356              * That's pretty easy -- just the intersection of the two
 357              * outer edges.  We've got slopes and points on each
 358              * of those edges.  Compute my directly, then compute
 359              * mx by using the edge with the larger dy; that avoids
 360              * dividing by values close to zero.
 361              */
 362             my = (((x2 - x1) * dy1 * dy2 - y2 * dx2 * dy1 + y1 * dx1 * dy2) /
 363                   (dx1 * dy2 - dx2 * dy1));
 364             if (fabs (dy1) >= fabs (dy2))
 365                 mx = (my - y1) * dx1 / dy1 + x1;
 366             else
 367                 mx = (my - y2) * dx2 / dy2 + x2;
 368
 369             /*
 370              * When the two outer edges are nearly parallel, slight
 371              * perturbations in the position of the outer points of the lines
 372              * caused by representing them in fixed point form can cause the
 373              * intersection point of the miter to move a large amount. If
 374              * that moves the miter intersection from between the two faces,
 375              * then draw a bevel instead.
 376              */
 377
 378             ix = _cairo_fixed_to_double (in->point.x);
 379             iy = _cairo_fixed_to_double (in->point.y);
 380
 381             /* slope of one face */
 382             fdx1 = x1 - ix; fdy1 = y1 - iy;
 383
 384             /* slope of the other face */
 385             fdx2 = x2 - ix; fdy2 = y2 - iy;
 386
 387             /* slope from the intersection to the miter point */
 388             mdx = mx - ix; mdy = my - iy;
 389
 390             /*
 391              * Make sure the miter point line lies between the two
 392              * faces by comparing the slopes
 393              */
 394             if (slope_compare_sgn (fdx1, fdy1, mdx, mdy) !=
 395                 slope_compare_sgn (fdx2, fdy2, mdx, mdy))
 396             {
 397                 cairo_point_t p;
 398
 399                 p.x = _cairo_fixed_from_double (mx);
 400                 p.y = _cairo_fixed_from_double (my);
 401
 402                 //*_cairo_contour_last_point (&outer->contour) = p;
 403                 //*_cairo_contour_first_point (&outer->contour) = p;
 404                 return;
 405             }
 406         }
 407         break;
 408     }
 409
 410     case CAIRO_LINE_JOIN_BEVEL:
 411         break;
 412     }
 413     //contour_add_point (stroker, outer, outpt);
 414 }
 415
 416 static void
 417 outer_join (struct stroker *stroker,
 418             const cairo_stroke_face_t *in,
 419             const cairo_stroke_face_t *out,
 420             int clockwise)
 421 {
 422     const cairo_point_t *inpt, *outpt;
 423
 424     if (in->cw.x == out->cw.x && in->cw.y == out->cw.y &&
 425         in->ccw.x == out->ccw.x && out->ccw.y == out->ccw.y)
 426     {
 427         return;
 428     }
 429     if (clockwise) {
 430         inpt = &in->cw;
 431         outpt = &out->cw;
 432     } else {
 433         inpt = &in->ccw;
 434         outpt = &out->ccw;
 435     }
 436
 437     switch (stroker->style.line_join) {
 438     case CAIRO_LINE_JOIN_ROUND:
 439         /* construct a fan around the common midpoint */
 440         add_fan (stroker,
 441                  &in->dev_vector,
 442                  &out->dev_vector,
 443                  &in->point, inpt, outpt,
 444                  clockwise);
 445         break;
 446
 447     case CAIRO_LINE_JOIN_MITER:
 448     default: {
 449         /* dot product of incoming slope vector with outgoing slope vector */
 450         double  in_dot_out = -in->usr_vector.x * out->usr_vector.x +
 451                              -in->usr_vector.y * out->usr_vector.y;
 452         double  ml = stroker->style.miter_limit;
 453
 454         /* Check the miter limit -- lines meeting at an acute angle
 455          * can generate long miters, the limit converts them to bevel
 456          *
 457          * Consider the miter join formed when two line segments
 458          * meet at an angle psi:
 459          *
 460          *         /.\
 461          *        /. .\
 462          *       /./ \.\
 463          *      /./psi\.\
 464          *
 465          * We can zoom in on the right half of that to see:
 466          *
 467          *          |\
 468          *          | \ psi/2
 469          *          |  \
 470          *          |   \
 471          *          |    \
 472          *          |     \
 473          *        miter    \
 474          *       length     \
 475          *          |        \
 476          *          |        .\
 477          *          |    .     \
 478          *          |.   line   \
 479          *           \    width  \
 480          *            \           \
 481          *
 482          *
 483          * The right triangle in that figure, (the line-width side is
 484          * shown faintly with three '.' characters), gives us the
 485          * following expression relating miter length, angle and line
 486          * width:
 487          *
 488          *      1 /sin (psi/2) = miter_length / line_width
 489          *
 490          * The right-hand side of this relationship is the same ratio
 491          * in which the miter limit (ml) is expressed. We want to know
 492          * when the miter length is within the miter limit. That is
 493          * when the following condition holds:
 494          *
 495          *      1/sin(psi/2) <= ml
 496          *      1 <= ml sin(psi/2)
 497          *      1 <= ml² sin²(psi/2)
 498          *      2 <= ml² 2 sin²(psi/2)
 499          *                              2·sin²(psi/2) = 1-cos(psi)
 500          *      2 <= ml² (1-cos(psi))
 501          *
 502          *                              in · out = |in| |out| cos (psi)
 503          *
 504          * in and out are both unit vectors, so:
 505          *
 506          *                              in · out = cos (psi)
 507          *
 508          *      2 <= ml² (1 - in · out)
 509          *
 510          */
 511         if (2 <= ml * ml * (1 - in_dot_out)) {
 512             double              x1, y1, x2, y2;
 513             double              mx, my;
 514             double              dx1, dx2, dy1, dy2;
 515             double              ix, iy;
 516             double              fdx1, fdy1, fdx2, fdy2;
 517             double              mdx, mdy;
 518
 519             /*
 520              * we've got the points already transformed to device
 521              * space, but need to do some computation with them and
 522              * also need to transform the slope from user space to
 523              * device space
 524              */
 525             /* outer point of incoming line face */
 526             x1 = _cairo_fixed_to_double (inpt->x);
 527             y1 = _cairo_fixed_to_double (inpt->y);
 528             dx1 = in->usr_vector.x;
 529             dy1 = in->usr_vector.y;
 530             cairo_matrix_transform_distance (stroker->ctm, &dx1, &dy1);
 531
 532             /* outer point of outgoing line face */
 533             x2 = _cairo_fixed_to_double (outpt->x);
 534             y2 = _cairo_fixed_to_double (outpt->y);
 535             dx2 = out->usr_vector.x;
 536             dy2 = out->usr_vector.y;
 537             cairo_matrix_transform_distance (stroker->ctm, &dx2, &dy2);
 538
 539             /*
 540              * Compute the location of the outer corner of the miter.
 541              * That's pretty easy -- just the intersection of the two
 542              * outer edges.  We've got slopes and points on each
 543              * of those edges.  Compute my directly, then compute
 544              * mx by using the edge with the larger dy; that avoids
 545              * dividing by values close to zero.
 546              */
 547             my = (((x2 - x1) * dy1 * dy2 - y2 * dx2 * dy1 + y1 * dx1 * dy2) /
 548                   (dx1 * dy2 - dx2 * dy1));
 549             if (fabs (dy1) >= fabs (dy2))
 550                 mx = (my - y1) * dx1 / dy1 + x1;
 551             else
 552                 mx = (my - y2) * dx2 / dy2 + x2;
 553
 554             /*
 555              * When the two outer edges are nearly parallel, slight
 556              * perturbations in the position of the outer points of the lines
 557              * caused by representing them in fixed point form can cause the
 558              * intersection point of the miter to move a large amount. If
 559              * that moves the miter intersection from between the two faces,
 560              * then draw a bevel instead.
 561              */
 562
 563             ix = _cairo_fixed_to_double (in->point.x);
 564             iy = _cairo_fixed_to_double (in->point.y);
 565
 566             /* slope of one face */
 567             fdx1 = x1 - ix; fdy1 = y1 - iy;
 568
 569             /* slope of the other face */
 570             fdx2 = x2 - ix; fdy2 = y2 - iy;
 571
 572             /* slope from the intersection to the miter point */
 573             mdx = mx - ix; mdy = my - iy;
 574
 575             /*
 576              * Make sure the miter point line lies between the two
 577              * faces by comparing the slopes
 578              */
 579             if (slope_compare_sgn (fdx1, fdy1, mdx, mdy) !=
 580                 slope_compare_sgn (fdx2, fdy2, mdx, mdy))
 581             {
 582                 cairo_point_t p;
 583
 584                 p.x = _cairo_fixed_from_double (mx);
 585                 p.y = _cairo_fixed_from_double (my);
 586
 587                 //*_cairo_contour_last_point (&outer->contour) = p;
 588                 return;
 589             }
 590         }
 591         break;
 592     }
 593
 594     case CAIRO_LINE_JOIN_BEVEL:
 595         break;
 596     }
 597     //contour_add_point (stroker,outer, outpt);
 598 }
 599
 600 static void
 601 add_cap (struct stroker *stroker,
 602          const cairo_stroke_face_t *f)
 603 {
 604     switch (stroker->style.line_cap) {
 605     case CAIRO_LINE_CAP_ROUND: {
 606         cairo_slope_t slope;
 607
 608         slope.dx = -f->dev_vector.dx;
 609         slope.dy = -f->dev_vector.dy;
 610
 611         add_fan (stroker, &f->dev_vector, &slope,
 612                  &f->point, &f->ccw, &f->cw,
 613                  FALSE);
 614         break;
 615     }
 616
 617     case CAIRO_LINE_CAP_SQUARE: {
 618         double dx, dy;
 619         cairo_slope_t   fvector;
 620         cairo_point_t   quad[4];
 621
 622         dx = f->usr_vector.x;
 623         dy = f->usr_vector.y;
 624         dx *= stroker->style.line_width / 2.0;
 625         dy *= stroker->style.line_width / 2.0;
 626         cairo_matrix_transform_distance (stroker->ctm, &dx, &dy);
 627         fvector.dx = _cairo_fixed_from_double (dx);
 628         fvector.dy = _cairo_fixed_from_double (dy);
 629
 630         quad[0] = f->ccw;
 631         quad[1].x = f->ccw.x + fvector.dx;
 632         quad[1].y = f->ccw.y + fvector.dy;
 633         quad[2].x = f->cw.x + fvector.dx;
 634         quad[2].y = f->cw.y + fvector.dy;
 635         quad[3] = f->cw;
 636
 637         //contour_add_point (stroker, c, &quad[1]);
 638         //contour_add_point (stroker, c, &quad[2]);
 639     }
 640
 641     case CAIRO_LINE_CAP_BUTT:
 642     default:
 643         break;
 644     }
 645     //contour_add_point (stroker, c, &f->cw);
 646 }
 647
 648 static void
 649 add_leading_cap (struct stroker *stroker,
 650                  const cairo_stroke_face_t *face)
 651 {
 652     cairo_stroke_face_t reversed;
 653     cairo_point_t t;
 654
 655     reversed = *face;
 656
 657     /* The initial cap needs an outward facing vector. Reverse everything */
 658     reversed.usr_vector.x = -reversed.usr_vector.x;
 659     reversed.usr_vector.y = -reversed.usr_vector.y;
 660     reversed.dev_vector.dx = -reversed.dev_vector.dx;
 661     reversed.dev_vector.dy = -reversed.dev_vector.dy;
 662
 663     t = reversed.cw;
 664     reversed.cw = reversed.ccw;
 665     reversed.ccw = t;
 666
 667     add_cap (stroker, &reversed);
 668 }
 669
 670 static void
 671 add_trailing_cap (struct stroker *stroker,
 672                   const cairo_stroke_face_t *face)
 673 {
 674     add_cap (stroker, face);
 675 }
 676
 677 static inline double
 678 normalize_slope (double *dx, double *dy)
 679 {
 680     double dx0 = *dx, dy0 = *dy;
 681     double mag;
 682
 683     assert (dx0 != 0.0 || dy0 != 0.0);
 684
 685     if (dx0 == 0.0) {
 686         *dx = 0.0;
 687         if (dy0 > 0.0) {
 688             mag = dy0;
 689             *dy = 1.0;
 690         } else {
 691             mag = -dy0;
 692             *dy = -1.0;
 693         }
 694     } else if (dy0 == 0.0) {
 695         *dy = 0.0;
 696         if (dx0 > 0.0) {
 697             mag = dx0;
 698             *dx = 1.0;
 699         } else {
 700             mag = -dx0;
 701             *dx = -1.0;
 702         }
 703     } else {
 704         mag = hypot (dx0, dy0);
 705         *dx = dx0 / mag;
 706         *dy = dy0 / mag;
 707     }
 708
 709     return mag;
 710 }
 711
 712 static void
 713 compute_face (const cairo_point_t *point,
 714               const cairo_slope_t *dev_slope,
 715               struct stroker *stroker,
 716               cairo_stroke_face_t *face)
 717 {
 718     double face_dx, face_dy;
 719     cairo_point_t offset_ccw, offset_cw;
 720     double slope_dx, slope_dy;
 721
 722     slope_dx = _cairo_fixed_to_double (dev_slope->dx);
 723     slope_dy = _cairo_fixed_to_double (dev_slope->dy);
 724     face->length = normalize_slope (&slope_dx, &slope_dy);
 725     face->dev_slope.x = slope_dx;
 726     face->dev_slope.y = slope_dy;
 727
 728     /*
 729      * rotate to get a line_width/2 vector along the face, note that
 730      * the vector must be rotated the right direction in device space,
 731      * but by 90° in user space. So, the rotation depends on
 732      * whether the ctm reflects or not, and that can be determined
 733      * by looking at the determinant of the matrix.
 734      */
 735     if (! _cairo_matrix_is_identity (stroker->ctm_inverse)) {
 736         /* Normalize the matrix! */
 737         cairo_matrix_transform_distance (stroker->ctm_inverse,
 738                                          &slope_dx, &slope_dy);
 739         normalize_slope (&slope_dx, &slope_dy);
 740
 741         if (stroker->ctm_det_positive) {
 742             face_dx = - slope_dy * (stroker->style.line_width / 2.0);
 743             face_dy = slope_dx * (stroker->style.line_width / 2.0);
 744         } else {
 745             face_dx = slope_dy * (stroker->style.line_width / 2.0);
 746             face_dy = - slope_dx * (stroker->style.line_width / 2.0);
 747         }
 748
 749         /* back to device space */
 750         cairo_matrix_transform_distance (stroker->ctm, &face_dx, &face_dy);
 751     } else {
 752         face_dx = - slope_dy * (stroker->style.line_width / 2.0);
 753         face_dy = slope_dx * (stroker->style.line_width / 2.0);
 754     }
 755
 756     offset_ccw.x = _cairo_fixed_from_double (face_dx);
 757     offset_ccw.y = _cairo_fixed_from_double (face_dy);
 758     offset_cw.x = -offset_ccw.x;
 759     offset_cw.y = -offset_ccw.y;
 760
 761     face->ccw = *point;
 762     translate_point (&face->ccw, &offset_ccw);
 763
 764     face->point = *point;
 765
 766     face->cw = *point;
 767     translate_point (&face->cw, &offset_cw);
 768
 769     face->usr_vector.x = slope_dx;
 770     face->usr_vector.y = slope_dy;
 771
 772     face->dev_vector = *dev_slope;
 773 }
 774
 775 static void
 776 add_caps (struct stroker *stroker)
 777 {
 778     /* check for a degenerative sub_path */
 779     if (stroker->has_sub_path &&
 780         ! stroker->has_first_face &&
 781         ! stroker->has_current_face &&
 782         stroker->style.line_cap == CAIRO_LINE_CAP_ROUND)
 783     {
 784         /* pick an arbitrary slope to use */
 785         cairo_slope_t slope = { CAIRO_FIXED_ONE, 0 };
 786         cairo_stroke_face_t face;
 787
 788         /* arbitrarily choose first_point */
 789         compute_face (&stroker->first_point, &slope, stroker, &face);
 790
 791         add_leading_cap (stroker, &face);
 792         add_trailing_cap (stroker, &face);
 793
 794         /* ensure the circle is complete */
 795         //_cairo_contour_add_point (&stroker->ccw.contour,
 796                                   //_cairo_contour_first_point (&stroker->ccw.contour));
 797     } else {
 798         if (stroker->has_current_face)
 799             add_trailing_cap (stroker, &stroker->current_face);
 800
 801         //_cairo_polygon_add_contour (stroker->polygon, &stroker->ccw.contour);
 802         //_cairo_contour_reset (&stroker->ccw.contour);
 803
 804         if (stroker->has_first_face) {
 805             //_cairo_contour_add_point (&stroker->ccw.contour,
 806                                       //&stroker->first_face.cw);
 807             add_leading_cap (stroker, &stroker->first_face);
 808             //_cairo_polygon_add_contour (stroker->polygon,
 809                                         //&stroker->ccw.contour);
 810             //_cairo_contour_reset (&stroker->ccw.contour);
 811         }
 812     }
 813 }
 814
 815 static cairo_status_t
 816 move_to (void *closure,
 817          const cairo_point_t *point)
 818 {
 819     struct stroker *stroker = closure;
 820
 821     /* Cap the start and end of the previous sub path as needed */
 822     add_caps (stroker);
 823
 824     stroker->has_first_face = FALSE;
 825     stroker->has_current_face = FALSE;
 826     stroker->has_sub_path = FALSE;
 827
 828     stroker->first_point = *point;
 829
 830     stroker->current_face.point = *point;
 831
 832     return CAIRO_STATUS_SUCCESS;
 833 }
 834
 835 static cairo_status_t
 836 line_to (void *closure,
 837          const cairo_point_t *point)
 838 {
 839     struct stroker *stroker = closure;
 840     cairo_stroke_face_t start;
 841     cairo_point_t *p1 = &stroker->current_face.point;
 842     cairo_slope_t dev_slope;
 843
 844     stroker->has_sub_path = TRUE;
 845
 846     if (p1->x == point->x && p1->y == point->y)
 847         return CAIRO_STATUS_SUCCESS;
 848
 849     _cairo_slope_init (&dev_slope, p1, point);
 850     compute_face (p1, &dev_slope, stroker, &start);
 851
 852     if (stroker->has_current_face) {
 853         int clockwise = join_is_clockwise (&stroker->current_face, &start);
 854         /* Join with final face from previous segment */
 855         outer_join (stroker, &stroker->current_face, &start, clockwise);
 856         inner_join (stroker, &stroker->current_face, &start, clockwise);
 857     } else {
 858         if (! stroker->has_first_face) {
 859             /* Save sub path's first face in case needed for closing join */
 860             stroker->first_face = start;
 861             _cairo_tristrip_move_to (stroker->strip, &start.cw);
 862             stroker->has_first_face = TRUE;
 863         }
 864         stroker->has_current_face = TRUE;
 865
 866         _cairo_tristrip_add_point (stroker->strip, &start.cw);
 867         _cairo_tristrip_add_point (stroker->strip, &start.ccw);
 868     }
 869
 870     stroker->current_face = start;
 871     stroker->current_face.point = *point;
 872     stroker->current_face.ccw.x += dev_slope.dx;
 873     stroker->current_face.ccw.y += dev_slope.dy;
 874     stroker->current_face.cw.x += dev_slope.dx;
 875     stroker->current_face.cw.y += dev_slope.dy;
 876
 877     _cairo_tristrip_add_point (stroker->strip, &stroker->current_face.cw);
 878     _cairo_tristrip_add_point (stroker->strip, &stroker->current_face.ccw);
 879
 880     return CAIRO_STATUS_SUCCESS;
 881 }
 882
 883 static cairo_status_t
 884 spline_to (void *closure,
 885            const cairo_point_t *point,
 886            const cairo_slope_t *tangent)
 887 {
 888     struct stroker *stroker = closure;
 889     cairo_stroke_face_t face;
 890
 891     if (tangent->dx == 0 && tangent->dy == 0) {
 892         const cairo_point_t *inpt, *outpt;
 893         cairo_point_t t;
 894         int clockwise;
 895
 896         face = stroker->current_face;
 897
 898         face.usr_vector.x = -face.usr_vector.x;
 899         face.usr_vector.y = -face.usr_vector.y;
 900         face.dev_vector.dx = -face.dev_vector.dx;
 901         face.dev_vector.dy = -face.dev_vector.dy;
 902
 903         t = face.cw;
 904         face.cw = face.ccw;
 905         face.ccw = t;
 906
 907         clockwise = join_is_clockwise (&stroker->current_face, &face);
 908         if (clockwise) {
 909             inpt = &stroker->current_face.cw;
 910             outpt = &face.cw;
 911         } else {
 912             inpt = &stroker->current_face.ccw;
 913             outpt = &face.ccw;
 914         }
 915
 916         add_fan (stroker,
 917                  &stroker->current_face.dev_vector,
 918                  &face.dev_vector,
 919                  &stroker->current_face.point, inpt, outpt,
 920                  clockwise);
 921     } else {
 922         compute_face (point, tangent, stroker, &face);
 923
 924         if (face.dev_slope.x * stroker->current_face.dev_slope.x +
 925             face.dev_slope.y * stroker->current_face.dev_slope.y < 0)
 926         {
 927             const cairo_point_t *inpt, *outpt;
 928             int clockwise = join_is_clockwise (&stroker->current_face, &face);
 929
 930             stroker->current_face.cw.x += face.point.x - stroker->current_face.point.x;
 931             stroker->current_face.cw.y += face.point.y - stroker->current_face.point.y;
 932             //contour_add_point (stroker, &stroker->cw, &stroker->current_face.cw);
 933
 934             stroker->current_face.ccw.x += face.point.x - stroker->current_face.point.x;
 935             stroker->current_face.ccw.y += face.point.y - stroker->current_face.point.y;
 936             //contour_add_point (stroker, &stroker->ccw, &stroker->current_face.ccw);
 937
 938             if (clockwise) {
 939                 inpt = &stroker->current_face.cw;
 940                 outpt = &face.cw;
 941             } else {
 942                 inpt = &stroker->current_face.ccw;
 943                 outpt = &face.ccw;
 944             }
 945             add_fan (stroker,
 946                      &stroker->current_face.dev_vector,
 947                      &face.dev_vector,
 948                      &stroker->current_face.point, inpt, outpt,
 949                      clockwise);
 950         }
 951
 952         _cairo_tristrip_add_point (stroker->strip, &face.cw);
 953         _cairo_tristrip_add_point (stroker->strip, &face.ccw);
 954     }
 955
 956     stroker->current_face = face;
 957
 958     return CAIRO_STATUS_SUCCESS;
 959 }
 960
 961 static cairo_status_t
 962 curve_to (void *closure,
 963           const cairo_point_t *b,
 964           const cairo_point_t *c,
 965           const cairo_point_t *d)
 966 {
 967     struct stroker *stroker = closure;
 968     cairo_spline_t spline;
 969     cairo_stroke_face_t face;
 970
 971     if (stroker->has_limits) {
 972         if (! _cairo_spline_intersects (&stroker->current_face.point, b, c, d,
 973                                         &stroker->limit))
 974             return line_to (closure, d);
 975     }
 976
 977     if (! _cairo_spline_init (&spline, spline_to, stroker,
 978                               &stroker->current_face.point, b, c, d))
 979         return line_to (closure, d);
 980
 981     compute_face (&stroker->current_face.point, &spline.initial_slope,
 982                   stroker, &face);
 983
 984     if (stroker->has_current_face) {
 985         int clockwise = join_is_clockwise (&stroker->current_face, &face);
 986         /* Join with final face from previous segment */
 987         outer_join (stroker, &stroker->current_face, &face, clockwise);
 988         inner_join (stroker, &stroker->current_face, &face, clockwise);
 989     } else {
 990         if (! stroker->has_first_face) {
 991             /* Save sub path's first face in case needed for closing join */
 992             stroker->first_face = face;
 993             _cairo_tristrip_move_to (stroker->strip, &face.cw);
 994             stroker->has_first_face = TRUE;
 995         }
 996         stroker->has_current_face = TRUE;
 997
 998         _cairo_tristrip_add_point (stroker->strip, &face.cw);
 999         _cairo_tristrip_add_point (stroker->strip, &face.ccw);
1000     }
1001     stroker->current_face = face;
1002
1003     return _cairo_spline_decompose (&spline, stroker->tolerance);
1004 }
1005
1006 static cairo_status_t
1007 close_path (void *closure)
1008 {
1009     struct stroker *stroker = closure;
1010     cairo_status_t status;
1011
1012     status = line_to (stroker, &stroker->first_point);
1013     if (unlikely (status))
1014         return status;
1015
1016     if (stroker->has_first_face && stroker->has_current_face) {
1017         /* Join first and final faces of sub path */
1018         outer_close (stroker, &stroker->current_face, &stroker->first_face);
1019         inner_close (stroker, &stroker->current_face, &stroker->first_face);
1020     } else {
1021         /* Cap the start and end of the sub path as needed */
1022         add_caps (stroker);
1023     }
1024
1025     stroker->has_sub_path = FALSE;
1026     stroker->has_first_face = FALSE;
1027     stroker->has_current_face = FALSE;
1028
1029     return CAIRO_STATUS_SUCCESS;
1030 }
1031
1032 cairo_int_status_t
1033 _cairo_path_fixed_stroke_to_tristrip (const cairo_path_fixed_t  *path,
1034                                       const cairo_stroke_style_t*style,
1035                                       const cairo_matrix_t      *ctm,
1036                                       const cairo_matrix_t      *ctm_inverse,
1037                                       double                     tolerance,
1038                                       cairo_tristrip_t           *strip)
1039 {
1040     struct stroker stroker;
1041     cairo_int_status_t status;
1042     int i;
1043
1044     if (style->num_dashes)
1045         return CAIRO_INT_STATUS_UNSUPPORTED;
1046
1047     stroker.style = *style;
1048     stroker.ctm = ctm;
1049     stroker.ctm_inverse = ctm_inverse;
1050     stroker.tolerance = tolerance;
1051
1052     stroker.ctm_det_positive =
1053         _cairo_matrix_compute_determinant (ctm) >= 0.0;
1054
1055     status = _cairo_pen_init (&stroker.pen,
1056                               style->line_width / 2.0,
1057                               tolerance, ctm);
1058     if (unlikely (status))
1059         return status;
1060
1061     if (stroker.pen.num_vertices <= 1)
1062         return CAIRO_INT_STATUS_NOTHING_TO_DO;
1063
1064     stroker.has_current_face = FALSE;
1065     stroker.has_first_face = FALSE;
1066     stroker.has_sub_path = FALSE;
1067
1068     stroker.has_limits = strip->num_limits > 0;
1069     stroker.limit = strip->limits[0];
1070     for (i = 1; i < strip->num_limits; i++)
1071         _cairo_box_add_box (&stroker.limit, &strip->limits[i]);
1072
1073     stroker.strip = strip;
1074
1075     status = _cairo_path_fixed_interpret (path,
1076                                           move_to,
1077                                           line_to,
1078                                           curve_to,
1079                                           close_path,
1080                                           &stroker);
1081     /* Cap the start and end of the final sub path as needed */
1082     if (likely (status == CAIRO_INT_STATUS_SUCCESS))
1083         add_caps (&stroker);
1084
1085     _cairo_pen_fini (&stroker.pen);
1086
1087     return status;
1088 }