src/cairo-path-stroke-traps.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 © 2013 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 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 #include "cairoint.h"
  41
  42 #include "cairo-box-inline.h"
  43 #include "cairo-path-fixed-private.h"
  44 #include "cairo-slope-private.h"
  45 #include "cairo-stroke-dash-private.h"
  46 #include "cairo-traps-private.h"
  47
  48 #include <float.h>
  49
  50 struct stroker {
  51     const cairo_stroke_style_t  *style;
  52
  53     const cairo_matrix_t *ctm;
  54     const cairo_matrix_t *ctm_inverse;
  55     double spline_cusp_tolerance;
  56     double half_line_width;
  57     double tolerance;
  58     double ctm_determinant;
  59     cairo_bool_t ctm_det_positive;
  60     cairo_line_join_t line_join;
  61
  62     cairo_traps_t *traps;
  63
  64     cairo_pen_t pen;
  65
  66     cairo_point_t first_point;
  67
  68     cairo_bool_t has_initial_sub_path;
  69
  70     cairo_bool_t has_current_face;
  71     cairo_stroke_face_t current_face;
  72
  73     cairo_bool_t has_first_face;
  74     cairo_stroke_face_t first_face;
  75
  76     cairo_stroker_dash_t dash;
  77
  78     cairo_bool_t has_bounds;
  79     cairo_box_t tight_bounds;
  80     cairo_box_t line_bounds;
  81     cairo_box_t join_bounds;
  82 };
  83
  84 static cairo_status_t
  85 stroker_init (struct stroker            *stroker,
  86               const cairo_path_fixed_t  *path,
  87               const cairo_stroke_style_t        *style,
  88               const cairo_matrix_t      *ctm,
  89               const cairo_matrix_t      *ctm_inverse,
  90               double                     tolerance,
  91               cairo_traps_t             *traps)
  92 {
  93     cairo_status_t status;
  94
  95     stroker->style = style;
  96     stroker->ctm = ctm;
  97     stroker->ctm_inverse = NULL;
  98     if (! _cairo_matrix_is_identity (ctm_inverse))
  99         stroker->ctm_inverse = ctm_inverse;
 100     stroker->line_join = style->line_join;
 101     stroker->half_line_width = style->line_width / 2.0;
 102     stroker->tolerance = tolerance;
 103     stroker->traps = traps;
 104
 105     /* To test whether we need to join two segments of a spline using
 106      * a round-join or a bevel-join, we can inspect the angle between the
 107      * two segments. If the difference between the chord distance
 108      * (half-line-width times the cosine of the bisection angle) and the
 109      * half-line-width itself is greater than tolerance then we need to
 110      * inject a point.
 111      */
 112     stroker->spline_cusp_tolerance = 1 - tolerance / stroker->half_line_width;
 113     stroker->spline_cusp_tolerance *= stroker->spline_cusp_tolerance;
 114     stroker->spline_cusp_tolerance *= 2;
 115     stroker->spline_cusp_tolerance -= 1;
 116
 117     stroker->ctm_determinant = _cairo_matrix_compute_determinant (stroker->ctm);
 118     stroker->ctm_det_positive = stroker->ctm_determinant >= 0.0;
 119
 120     status = _cairo_pen_init (&stroker->pen,
 121                               stroker->half_line_width,
 122                               tolerance, ctm);
 123     if (unlikely (status))
 124         return status;
 125
 126     stroker->has_current_face = FALSE;
 127     stroker->has_first_face = FALSE;
 128     stroker->has_initial_sub_path = FALSE;
 129
 130     _cairo_stroker_dash_init (&stroker->dash, style);
 131
 132     stroker->has_bounds = traps->num_limits;
 133     if (stroker->has_bounds) {
 134         /* Extend the bounds in each direction to account for the maximum area
 135          * we might generate trapezoids, to capture line segments that are outside
 136          * of the bounds but which might generate rendering that's within bounds.
 137          */
 138         double dx, dy;
 139         cairo_fixed_t fdx, fdy;
 140
 141         stroker->tight_bounds = traps->bounds;
 142
 143         _cairo_stroke_style_max_distance_from_path (stroker->style, path,
 144                                                     stroker->ctm, &dx, &dy);
 145
 146         _cairo_stroke_style_max_line_distance_from_path (stroker->style, path,
 147                                                          stroker->ctm, &dx, &dy);
 148
 149         fdx = _cairo_fixed_from_double (dx);
 150         fdy = _cairo_fixed_from_double (dy);
 151
 152         stroker->line_bounds = stroker->tight_bounds;
 153         stroker->line_bounds.p1.x -= fdx;
 154         stroker->line_bounds.p2.x += fdx;
 155         stroker->line_bounds.p1.y -= fdy;
 156         stroker->line_bounds.p2.y += fdy;
 157
 158         _cairo_stroke_style_max_join_distance_from_path (stroker->style, path,
 159                                                          stroker->ctm, &dx, &dy);
 160
 161         fdx = _cairo_fixed_from_double (dx);
 162         fdy = _cairo_fixed_from_double (dy);
 163
 164         stroker->join_bounds = stroker->tight_bounds;
 165         stroker->join_bounds.p1.x -= fdx;
 166         stroker->join_bounds.p2.x += fdx;
 167         stroker->join_bounds.p1.y -= fdy;
 168         stroker->join_bounds.p2.y += fdy;
 169     }
 170
 171     return CAIRO_STATUS_SUCCESS;
 172 }
 173
 174 static void
 175 stroker_fini (struct stroker *stroker)
 176 {
 177     _cairo_pen_fini (&stroker->pen);
 178 }
 179
 180 static void
 181 translate_point (cairo_point_t *point, cairo_point_t *offset)
 182 {
 183     point->x += offset->x;
 184     point->y += offset->y;
 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 int
 195 slope_compare_sgn (double dx1, double dy1, double dx2, double dy2)
 196 {
 197     double c = dx1 * dy2 - dx2 * dy1;
 198     if (c > 0) return 1;
 199     if (c < 0) return -1;
 200     return 0;
 201 }
 202
 203 static cairo_bool_t
 204 stroker_intersects_join (const struct stroker *stroker,
 205                          const cairo_point_t *in,
 206                          const cairo_point_t *out)
 207 {
 208     cairo_line_t segment;
 209
 210     if (! stroker->has_bounds)
 211         return TRUE;
 212
 213     segment.p1 = *in;
 214     segment.p2 = *out;
 215     return _cairo_box_intersects_line_segment (&stroker->join_bounds, &segment);
 216 }
 217
 218 static void
 219 join (struct stroker *stroker,
 220       cairo_stroke_face_t *in,
 221       cairo_stroke_face_t *out)
 222 {
 223     int clockwise = join_is_clockwise (out, in);
 224     cairo_point_t *inpt, *outpt;
 225
 226     if (in->cw.x == out->cw.x &&
 227         in->cw.y == out->cw.y &&
 228         in->ccw.x == out->ccw.x &&
 229         in->ccw.y == out->ccw.y)
 230     {
 231         return;
 232     }
 233
 234     if (clockwise) {
 235         inpt = &in->ccw;
 236         outpt = &out->ccw;
 237     } else {
 238         inpt = &in->cw;
 239         outpt = &out->cw;
 240     }
 241
 242     if (! stroker_intersects_join (stroker, inpt, outpt))
 243             return;
 244
 245     switch (stroker->line_join) {
 246     case CAIRO_LINE_JOIN_ROUND:
 247         /* construct a fan around the common midpoint */
 248         if ((in->dev_slope.x * out->dev_slope.x +
 249              in->dev_slope.y * out->dev_slope.y) < stroker->spline_cusp_tolerance)
 250         {
 251             int start, stop;
 252             cairo_point_t tri[3], edges[4];
 253             cairo_pen_t *pen = &stroker->pen;
 254
 255             edges[0] = in->cw;
 256             edges[1] = in->ccw;
 257             tri[0] = in->point;
 258             tri[1] = *inpt;
 259             if (clockwise) {
 260                 _cairo_pen_find_active_ccw_vertices (pen,
 261                                                      &in->dev_vector, &out->dev_vector,
 262                                                      &start, &stop);
 263                 while (start != stop) {
 264                     tri[2] = in->point;
 265                     translate_point (&tri[2], &pen->vertices[start].point);
 266                     edges[2] = in->point;
 267                     edges[3] = tri[2];
 268                     _cairo_traps_tessellate_triangle_with_edges (stroker->traps,
 269                                                                  tri, edges);
 270                     tri[1] = tri[2];
 271                     edges[0] = edges[2];
 272                     edges[1] = edges[3];
 273
 274                     if (start-- == 0)
 275                         start += pen->num_vertices;
 276                 }
 277             } else {
 278                 _cairo_pen_find_active_cw_vertices (pen,
 279                                                     &in->dev_vector, &out->dev_vector,
 280                                                     &start, &stop);
 281                 while (start != stop) {
 282                     tri[2] = in->point;
 283                     translate_point (&tri[2], &pen->vertices[start].point);
 284                     edges[2] = in->point;
 285                     edges[3] = tri[2];
 286                     _cairo_traps_tessellate_triangle_with_edges (stroker->traps,
 287                                                                  tri, edges);
 288                     tri[1] = tri[2];
 289                     edges[0] = edges[2];
 290                     edges[1] = edges[3];
 291
 292                     if (++start == pen->num_vertices)
 293                         start = 0;
 294                 }
 295             }
 296             tri[2] = *outpt;
 297             edges[2] = out->cw;
 298             edges[3] = out->ccw;
 299             _cairo_traps_tessellate_triangle_with_edges (stroker->traps,
 300                                                          tri, edges);
 301         } else {
 302             cairo_point_t t[] = { { in->point.x, in->point.y}, { inpt->x, inpt->y }, { outpt->x, outpt->y } };
 303             cairo_point_t e[] = { { in->cw.x, in->cw.y}, { in->ccw.x, in->ccw.y },
 304                                   { out->cw.x, out->cw.y}, { out->ccw.x, out->ccw.y } };
 305             _cairo_traps_tessellate_triangle_with_edges (stroker->traps, t, e);
 306         }
 307         break;
 308
 309     case CAIRO_LINE_JOIN_MITER:
 310     default: {
 311         /* dot product of incoming slope vector with outgoing slope vector */
 312         double in_dot_out = (-in->usr_vector.x * out->usr_vector.x +
 313                              -in->usr_vector.y * out->usr_vector.y);
 314         double ml = stroker->style->miter_limit;
 315
 316         /* Check the miter limit -- lines meeting at an acute angle
 317          * can generate long miters, the limit converts them to bevel
 318          *
 319          * Consider the miter join formed when two line segments
 320          * meet at an angle psi:
 321          *
 322          *         /.\
 323          *        /. .\
 324          *       /./ \.\
 325          *      /./psi\.\
 326          *
 327          * We can zoom in on the right half of that to see:
 328          *
 329          *          |\
 330          *          | \ psi/2
 331          *          |  \
 332          *          |   \
 333          *          |    \
 334          *          |     \
 335          *        miter    \
 336          *       length     \
 337          *          |        \
 338          *          |        .\
 339          *          |    .     \
 340          *          |.   line   \
 341          *           \    width  \
 342          *            \           \
 343          *
 344          *
 345          * The right triangle in that figure, (the line-width side is
 346          * shown faintly with three '.' characters), gives us the
 347          * following expression relating miter length, angle and line
 348          * width:
 349          *
 350          *      1 /sin (psi/2) = miter_length / line_width
 351          *
 352          * The right-hand side of this relationship is the same ratio
 353          * in which the miter limit (ml) is expressed. We want to know
 354          * when the miter length is within the miter limit. That is
 355          * when the following condition holds:
 356          *
 357          *      1/sin(psi/2) <= ml
 358          *      1 <= ml sin(psi/2)
 359          *      1 <= ml² sin²(psi/2)
 360          *      2 <= ml² 2 sin²(psi/2)
 361          *                              2·sin²(psi/2) = 1-cos(psi)
 362          *      2 <= ml² (1-cos(psi))
 363          *
 364          *                              in · out = |in| |out| cos (psi)
 365          *
 366          * in and out are both unit vectors, so:
 367          *
 368          *                              in · out = cos (psi)
 369          *
 370          *      2 <= ml² (1 - in · out)
 371          *
 372          */
 373         if (2 <= ml * ml * (1 - in_dot_out)) {
 374             double              x1, y1, x2, y2;
 375             double              mx, my;
 376             double              dx1, dx2, dy1, dy2;
 377             cairo_point_t       outer;
 378             cairo_point_t       quad[4];
 379             double              ix, iy;
 380             double              fdx1, fdy1, fdx2, fdy2;
 381             double              mdx, mdy;
 382
 383             /*
 384              * we've got the points already transformed to device
 385              * space, but need to do some computation with them and
 386              * also need to transform the slope from user space to
 387              * device space
 388              */
 389             /* outer point of incoming line face */
 390             x1 = _cairo_fixed_to_double (inpt->x);
 391             y1 = _cairo_fixed_to_double (inpt->y);
 392             dx1 = in->usr_vector.x;
 393             dy1 = in->usr_vector.y;
 394             cairo_matrix_transform_distance (stroker->ctm, &dx1, &dy1);
 395
 396             /* outer point of outgoing line face */
 397             x2 = _cairo_fixed_to_double (outpt->x);
 398             y2 = _cairo_fixed_to_double (outpt->y);
 399             dx2 = out->usr_vector.x;
 400             dy2 = out->usr_vector.y;
 401             cairo_matrix_transform_distance (stroker->ctm, &dx2, &dy2);
 402
 403             /*
 404              * Compute the location of the outer corner of the miter.
 405              * That's pretty easy -- just the intersection of the two
 406              * outer edges.  We've got slopes and points on each
 407              * of those edges.  Compute my directly, then compute
 408              * mx by using the edge with the larger dy; that avoids
 409              * dividing by values close to zero.
 410              */
 411             my = (((x2 - x1) * dy1 * dy2 - y2 * dx2 * dy1 + y1 * dx1 * dy2) /
 412                   (dx1 * dy2 - dx2 * dy1));
 413             if (fabs (dy1) >= fabs (dy2))
 414                 mx = (my - y1) * dx1 / dy1 + x1;
 415             else
 416                 mx = (my - y2) * dx2 / dy2 + x2;
 417
 418             /*
 419              * When the two outer edges are nearly parallel, slight
 420              * perturbations in the position of the outer points of the lines
 421              * caused by representing them in fixed point form can cause the
 422              * intersection point of the miter to move a large amount. If
 423              * that moves the miter intersection from between the two faces,
 424              * then draw a bevel instead.
 425              */
 426
 427             ix = _cairo_fixed_to_double (in->point.x);
 428             iy = _cairo_fixed_to_double (in->point.y);
 429
 430             /* slope of one face */
 431             fdx1 = x1 - ix; fdy1 = y1 - iy;
 432
 433             /* slope of the other face */
 434             fdx2 = x2 - ix; fdy2 = y2 - iy;
 435
 436             /* slope from the intersection to the miter point */
 437             mdx = mx - ix; mdy = my - iy;
 438
 439             /*
 440              * Make sure the miter point line lies between the two
 441              * faces by comparing the slopes
 442              */
 443             if (slope_compare_sgn (fdx1, fdy1, mdx, mdy) !=
 444                 slope_compare_sgn (fdx2, fdy2, mdx, mdy))
 445             {
 446                 /*
 447                  * Draw the quadrilateral
 448                  */
 449                 outer.x = _cairo_fixed_from_double (mx);
 450                 outer.y = _cairo_fixed_from_double (my);
 451
 452                 quad[0] = in->point;
 453                 quad[1] = *inpt;
 454                 quad[2] = outer;
 455                 quad[3] = *outpt;
 456
 457                 _cairo_traps_tessellate_convex_quad (stroker->traps, quad);
 458                 break;
 459             }
 460         }
 461         /* fall through ... */
 462     }
 463
 464     case CAIRO_LINE_JOIN_BEVEL: {
 465         cairo_point_t t[] = { { in->point.x, in->point.y }, { inpt->x, inpt->y }, { outpt->x, outpt->y } };
 466         cairo_point_t e[] = { { in->cw.x, in->cw.y }, { in->ccw.x, in->ccw.y },
 467                               { out->cw.x, out->cw.y }, { out->ccw.x, out->ccw.y } };
 468         _cairo_traps_tessellate_triangle_with_edges (stroker->traps, t, e);
 469         break;
 470     }
 471     }
 472 }
 473
 474 static void
 475 add_cap (struct stroker *stroker, cairo_stroke_face_t *f)
 476 {
 477     switch (stroker->style->line_cap) {
 478     case CAIRO_LINE_CAP_ROUND: {
 479         int start, stop;
 480         cairo_slope_t in_slope, out_slope;
 481         cairo_point_t tri[3], edges[4];
 482         cairo_pen_t *pen = &stroker->pen;
 483
 484         in_slope = f->dev_vector;
 485         out_slope.dx = -in_slope.dx;
 486         out_slope.dy = -in_slope.dy;
 487         _cairo_pen_find_active_cw_vertices (pen, &in_slope, &out_slope,
 488                                             &start, &stop);
 489         edges[0] = f->cw;
 490         edges[1] = f->ccw;
 491         tri[0] = f->point;
 492         tri[1] = f->cw;
 493         while (start != stop) {
 494             tri[2] = f->point;
 495             translate_point (&tri[2], &pen->vertices[start].point);
 496             edges[2] = f->point;
 497             edges[3] = tri[2];
 498             _cairo_traps_tessellate_triangle_with_edges (stroker->traps,
 499                                                          tri, edges);
 500
 501             tri[1] = tri[2];
 502             edges[0] = edges[2];
 503             edges[1] = edges[3];
 504             if (++start == pen->num_vertices)
 505                 start = 0;
 506         }
 507         tri[2] = f->ccw;
 508         edges[2] = f->cw;
 509         edges[3] = f->ccw;
 510         _cairo_traps_tessellate_triangle_with_edges (stroker->traps,
 511                                                      tri, edges);
 512         break;
 513     }
 514
 515     case CAIRO_LINE_CAP_SQUARE: {
 516         double dx, dy;
 517         cairo_slope_t fvector;
 518         cairo_point_t quad[4];
 519
 520         dx = f->usr_vector.x;
 521         dy = f->usr_vector.y;
 522         dx *= stroker->half_line_width;
 523         dy *= stroker->half_line_width;
 524         cairo_matrix_transform_distance (stroker->ctm, &dx, &dy);
 525         fvector.dx = _cairo_fixed_from_double (dx);
 526         fvector.dy = _cairo_fixed_from_double (dy);
 527
 528         quad[0] = f->cw;
 529         quad[1].x = f->cw.x + fvector.dx;
 530         quad[1].y = f->cw.y + fvector.dy;
 531         quad[2].x = f->ccw.x + fvector.dx;
 532         quad[2].y = f->ccw.y + fvector.dy;
 533         quad[3] = f->ccw;
 534
 535         _cairo_traps_tessellate_convex_quad (stroker->traps, quad);
 536         break;
 537     }
 538
 539     case CAIRO_LINE_CAP_BUTT:
 540     default:
 541         break;
 542     }
 543 }
 544
 545 static void
 546 add_leading_cap (struct stroker     *stroker,
 547                  cairo_stroke_face_t *face)
 548 {
 549     cairo_stroke_face_t reversed;
 550     cairo_point_t t;
 551
 552     reversed = *face;
 553
 554     /* The initial cap needs an outward facing vector. Reverse everything */
 555     reversed.usr_vector.x = -reversed.usr_vector.x;
 556     reversed.usr_vector.y = -reversed.usr_vector.y;
 557     reversed.dev_vector.dx = -reversed.dev_vector.dx;
 558     reversed.dev_vector.dy = -reversed.dev_vector.dy;
 559     t = reversed.cw;
 560     reversed.cw = reversed.ccw;
 561     reversed.ccw = t;
 562
 563     add_cap (stroker, &reversed);
 564 }
 565
 566 static void
 567 add_trailing_cap (struct stroker *stroker, cairo_stroke_face_t *face)
 568 {
 569     add_cap (stroker, face);
 570 }
 571
 572 static inline double
 573 normalize_slope (double *dx, double *dy)
 574 {
 575     double dx0 = *dx, dy0 = *dy;
 576
 577     if (dx0 == 0.0 && dy0 == 0.0)
 578         return 0;
 579
 580     if (dx0 == 0.0) {
 581         *dx = 0.0;
 582         if (dy0 > 0.0) {
 583             *dy = 1.0;
 584             return dy0;
 585         } else {
 586             *dy = -1.0;
 587             return -dy0;
 588         }
 589     } else if (dy0 == 0.0) {
 590         *dy = 0.0;
 591         if (dx0 > 0.0) {
 592             *dx = 1.0;
 593             return dx0;
 594         } else {
 595             *dx = -1.0;
 596             return -dx0;
 597         }
 598     } else {
 599         double mag = hypot (dx0, dy0);
 600         *dx = dx0 / mag;
 601         *dy = dy0 / mag;
 602         return mag;
 603     }
 604 }
 605
 606 static void
 607 compute_face (const cairo_point_t *point,
 608               const cairo_slope_t *dev_slope,
 609               struct stroker *stroker,
 610               cairo_stroke_face_t *face)
 611 {
 612     double face_dx, face_dy;
 613     cairo_point_t offset_ccw, offset_cw;
 614     double slope_dx, slope_dy;
 615
 616     slope_dx = _cairo_fixed_to_double (dev_slope->dx);
 617     slope_dy = _cairo_fixed_to_double (dev_slope->dy);
 618     face->length = normalize_slope (&slope_dx, &slope_dy);
 619     face->dev_slope.x = slope_dx;
 620     face->dev_slope.y = slope_dy;
 621
 622     /*
 623      * rotate to get a line_width/2 vector along the face, note that
 624      * the vector must be rotated the right direction in device space,
 625      * but by 90° in user space. So, the rotation depends on
 626      * whether the ctm reflects or not, and that can be determined
 627      * by looking at the determinant of the matrix.
 628      */
 629     if (stroker->ctm_inverse) {
 630         cairo_matrix_transform_distance (stroker->ctm_inverse, &slope_dx, &slope_dy);
 631         normalize_slope (&slope_dx, &slope_dy);
 632
 633         if (stroker->ctm_det_positive) {
 634             face_dx = - slope_dy * stroker->half_line_width;
 635             face_dy = slope_dx * stroker->half_line_width;
 636         } else {
 637             face_dx = slope_dy * stroker->half_line_width;
 638             face_dy = - slope_dx * stroker->half_line_width;
 639         }
 640
 641         /* back to device space */
 642         cairo_matrix_transform_distance (stroker->ctm, &face_dx, &face_dy);
 643     } else {
 644         face_dx = - slope_dy * stroker->half_line_width;
 645         face_dy = slope_dx * stroker->half_line_width;
 646     }
 647
 648     offset_ccw.x = _cairo_fixed_from_double (face_dx);
 649     offset_ccw.y = _cairo_fixed_from_double (face_dy);
 650     offset_cw.x = -offset_ccw.x;
 651     offset_cw.y = -offset_ccw.y;
 652
 653     face->ccw = *point;
 654     translate_point (&face->ccw, &offset_ccw);
 655
 656     face->point = *point;
 657
 658     face->cw = *point;
 659     translate_point (&face->cw, &offset_cw);
 660
 661     face->usr_vector.x = slope_dx;
 662     face->usr_vector.y = slope_dy;
 663
 664     face->dev_vector = *dev_slope;
 665 }
 666
 667 static void
 668 add_caps (struct stroker *stroker)
 669 {
 670     /* check for a degenerative sub_path */
 671     if (stroker->has_initial_sub_path &&
 672         !stroker->has_first_face &&
 673         !stroker->has_current_face &&
 674         stroker->style->line_cap == CAIRO_LINE_CAP_ROUND)
 675     {
 676         /* pick an arbitrary slope to use */
 677         cairo_slope_t slope = { CAIRO_FIXED_ONE, 0 };
 678         cairo_stroke_face_t face;
 679
 680         /* arbitrarily choose first_point
 681          * first_point and current_point should be the same */
 682         compute_face (&stroker->first_point, &slope, stroker, &face);
 683
 684         add_leading_cap (stroker, &face);
 685         add_trailing_cap (stroker, &face);
 686     }
 687
 688     if (stroker->has_first_face)
 689         add_leading_cap (stroker, &stroker->first_face);
 690
 691     if (stroker->has_current_face)
 692         add_trailing_cap (stroker, &stroker->current_face);
 693 }
 694
 695 static cairo_bool_t
 696 stroker_intersects_edge (const struct stroker *stroker,
 697                          const cairo_stroke_face_t *start,
 698                          const cairo_stroke_face_t *end)
 699 {
 700     cairo_box_t box;
 701
 702     if (! stroker->has_bounds)
 703         return TRUE;
 704
 705     if (_cairo_box_contains_point (&stroker->tight_bounds, &start->cw))
 706         return TRUE;
 707     box.p2 = box.p1 = start->cw;
 708
 709     if (_cairo_box_contains_point (&stroker->tight_bounds, &start->ccw))
 710         return TRUE;
 711     _cairo_box_add_point (&box, &start->ccw);
 712
 713     if (_cairo_box_contains_point (&stroker->tight_bounds, &end->cw))
 714         return TRUE;
 715     _cairo_box_add_point (&box, &end->cw);
 716
 717     if (_cairo_box_contains_point (&stroker->tight_bounds, &end->ccw))
 718         return TRUE;
 719     _cairo_box_add_point (&box, &end->ccw);
 720
 721     return (box.p2.x > stroker->tight_bounds.p1.x &&
 722             box.p1.x < stroker->tight_bounds.p2.x &&
 723             box.p2.y > stroker->tight_bounds.p1.y &&
 724             box.p1.y < stroker->tight_bounds.p2.y);
 725 }
 726
 727 static void
 728 add_sub_edge (struct stroker *stroker,
 729               const cairo_point_t *p1, const cairo_point_t *p2,
 730               const cairo_slope_t *dev_slope,
 731               cairo_stroke_face_t *start, cairo_stroke_face_t *end)
 732 {
 733     cairo_point_t rectangle[4];
 734
 735     compute_face (p1, dev_slope, stroker, start);
 736
 737     *end = *start;
 738     end->point = *p2;
 739     rectangle[0].x = p2->x - p1->x;
 740     rectangle[0].y = p2->y - p1->y;
 741     translate_point (&end->ccw, &rectangle[0]);
 742     translate_point (&end->cw, &rectangle[0]);
 743
 744     if (p1->x == p2->x && p1->y == p2->y)
 745         return;
 746
 747     if (! stroker_intersects_edge (stroker, start, end))
 748         return;
 749
 750     rectangle[0] = start->cw;
 751     rectangle[1] = start->ccw;
 752     rectangle[2] = end->ccw;
 753     rectangle[3] = end->cw;
 754
 755     _cairo_traps_tessellate_convex_quad (stroker->traps, rectangle);
 756 }
 757
 758 static cairo_status_t
 759 move_to (void *closure, const cairo_point_t *point)
 760 {
 761     struct stroker *stroker = closure;
 762
 763     /* Cap the start and end of the previous sub path as needed */
 764     add_caps (stroker);
 765
 766     stroker->first_point = *point;
 767     stroker->current_face.point = *point;
 768
 769     stroker->has_first_face = FALSE;
 770     stroker->has_current_face = FALSE;
 771     stroker->has_initial_sub_path = FALSE;
 772
 773     return CAIRO_STATUS_SUCCESS;
 774 }
 775
 776 static cairo_status_t
 777 move_to_dashed (void *closure, const cairo_point_t *point)
 778 {
 779     /* reset the dash pattern for new sub paths */
 780     struct stroker *stroker = closure;
 781
 782     _cairo_stroker_dash_start (&stroker->dash);
 783     return move_to (closure, point);
 784 }
 785
 786 static cairo_status_t
 787 line_to (void *closure, const cairo_point_t *point)
 788 {
 789     struct stroker *stroker = closure;
 790     cairo_stroke_face_t start, end;
 791     const cairo_point_t *p1 = &stroker->current_face.point;
 792     const cairo_point_t *p2 = point;
 793     cairo_slope_t dev_slope;
 794
 795     stroker->has_initial_sub_path = TRUE;
 796     memset (&start, 0, sizeof (cairo_stroke_face_t));
 797     memset (&end, 0, sizeof (cairo_stroke_face_t));
 798
 799     if (p1->x == p2->x && p1->y == p2->y)
 800         return CAIRO_STATUS_SUCCESS;
 801
 802     _cairo_slope_init (&dev_slope, p1, p2);
 803     add_sub_edge (stroker, p1, p2, &dev_slope, &start, &end);
 804
 805     if (stroker->has_current_face) {
 806         /* Join with final face from previous segment */
 807         join (stroker, &stroker->current_face, &start);
 808     } else if (!stroker->has_first_face) {
 809         /* Save sub path's first face in case needed for closing join */
 810         stroker->first_face = start;
 811         stroker->has_first_face = TRUE;
 812     }
 813     stroker->current_face = end;
 814     stroker->has_current_face = TRUE;
 815
 816     return CAIRO_STATUS_SUCCESS;
 817 }
 818
 819 /*
 820  * Dashed lines.  Cap each dash end, join around turns when on
 821  */
 822 static cairo_status_t
 823 line_to_dashed (void *closure, const cairo_point_t *point)
 824 {
 825     struct stroker *stroker = closure;
 826     double mag, remain, step_length = 0;
 827     double slope_dx, slope_dy;
 828     double dx2, dy2;
 829     cairo_stroke_face_t sub_start, sub_end;
 830     const cairo_point_t *p1 = &stroker->current_face.point;
 831     const cairo_point_t *p2 = point;
 832     cairo_slope_t dev_slope;
 833     cairo_line_t segment;
 834     cairo_bool_t fully_in_bounds;
 835
 836     memset (&sub_start, 0, sizeof (cairo_stroke_face_t));
 837     memset (&sub_end, 0, sizeof (cairo_stroke_face_t));
 838
 839     stroker->has_initial_sub_path = stroker->dash.dash_starts_on;
 840
 841     if (p1->x == p2->x && p1->y == p2->y)
 842         return CAIRO_STATUS_SUCCESS;
 843
 844     fully_in_bounds = TRUE;
 845     if (stroker->has_bounds &&
 846         (! _cairo_box_contains_point (&stroker->join_bounds, p1) ||
 847          ! _cairo_box_contains_point (&stroker->join_bounds, p2)))
 848     {
 849         fully_in_bounds = FALSE;
 850     }
 851
 852     _cairo_slope_init (&dev_slope, p1, p2);
 853
 854     slope_dx = _cairo_fixed_to_double (p2->x - p1->x);
 855     slope_dy = _cairo_fixed_to_double (p2->y - p1->y);
 856
 857     if (stroker->ctm_inverse)
 858         cairo_matrix_transform_distance (stroker->ctm_inverse, &slope_dx, &slope_dy);
 859     mag = normalize_slope (&slope_dx, &slope_dy);
 860     if (mag <= DBL_EPSILON)
 861         return CAIRO_STATUS_SUCCESS;
 862
 863     remain = mag;
 864     segment.p1 = *p1;
 865     while (remain) {
 866         step_length = MIN (stroker->dash.dash_remain, remain);
 867         remain -= step_length;
 868         dx2 = slope_dx * (mag - remain);
 869         dy2 = slope_dy * (mag - remain);
 870         cairo_matrix_transform_distance (stroker->ctm, &dx2, &dy2);
 871         segment.p2.x = _cairo_fixed_from_double (dx2) + p1->x;
 872         segment.p2.y = _cairo_fixed_from_double (dy2) + p1->y;
 873
 874         if (stroker->dash.dash_on &&
 875             (fully_in_bounds ||
 876              (! stroker->has_first_face && stroker->dash.dash_starts_on) ||
 877              _cairo_box_intersects_line_segment (&stroker->join_bounds, &segment)))
 878         {
 879             add_sub_edge (stroker,
 880                           &segment.p1, &segment.p2,
 881                           &dev_slope,
 882                           &sub_start, &sub_end);
 883
 884             if (stroker->has_current_face) {
 885                 /* Join with final face from previous segment */
 886                 join (stroker, &stroker->current_face, &sub_start);
 887
 888                 stroker->has_current_face = FALSE;
 889             } else if (! stroker->has_first_face && stroker->dash.dash_starts_on) {
 890                 /* Save sub path's first face in case needed for closing join */
 891                 stroker->first_face = sub_start;
 892                 stroker->has_first_face = TRUE;
 893             } else {
 894                 /* Cap dash start if not connecting to a previous segment */
 895                 add_leading_cap (stroker, &sub_start);
 896             }
 897
 898             if (remain) {
 899                 /* Cap dash end if not at end of segment */
 900                 add_trailing_cap (stroker, &sub_end);
 901             } else {
 902                 stroker->current_face = sub_end;
 903                 stroker->has_current_face = TRUE;
 904             }
 905         } else {
 906             if (stroker->has_current_face) {
 907                 /* Cap final face from previous segment */
 908                 add_trailing_cap (stroker, &stroker->current_face);
 909
 910                 stroker->has_current_face = FALSE;
 911             }
 912         }
 913
 914         _cairo_stroker_dash_step (&stroker->dash, step_length);
 915         segment.p1 = segment.p2;
 916     }
 917
 918     if (stroker->dash.dash_on && ! stroker->has_current_face) {
 919         /* This segment ends on a transition to dash_on, compute a new face
 920          * and add cap for the beginning of the next dash_on step.
 921          *
 922          * Note: this will create a degenerate cap if this is not the last line
 923          * in the path. Whether this behaviour is desirable or not is debatable.
 924          * On one side these degenerate caps can not be reproduced with regular
 925          * path stroking.
 926          * On the other hand, Acroread 7 also produces the degenerate caps.
 927          */
 928         compute_face (point, &dev_slope, stroker, &stroker->current_face);
 929
 930         add_leading_cap (stroker, &stroker->current_face);
 931
 932         stroker->has_current_face = TRUE;
 933     } else
 934         stroker->current_face.point = *point;
 935
 936     return CAIRO_STATUS_SUCCESS;
 937 }
 938
 939 static cairo_status_t
 940 spline_to (void *closure,
 941            const cairo_point_t *point,
 942            const cairo_slope_t *tangent)
 943 {
 944     struct stroker *stroker = closure;
 945     cairo_stroke_face_t face;
 946
 947     if ((tangent->dx | tangent->dy) == 0) {
 948         cairo_point_t t;
 949
 950         face = stroker->current_face;
 951
 952         face.usr_vector.x = -face.usr_vector.x;
 953         face.usr_vector.y = -face.usr_vector.y;
 954         face.dev_slope.x = -face.dev_slope.x;
 955         face.dev_slope.y = -face.dev_slope.y;
 956         face.dev_vector.dx = -face.dev_vector.dx;
 957         face.dev_vector.dy = -face.dev_vector.dy;
 958
 959         t = face.cw;
 960         face.cw = face.ccw;
 961         face.ccw = t;
 962
 963         join (stroker, &stroker->current_face, &face);
 964     } else {
 965         cairo_point_t rectangle[4];
 966
 967         compute_face (&stroker->current_face.point, tangent, stroker, &face);
 968         join (stroker, &stroker->current_face, &face);
 969
 970         rectangle[0] = face.cw;
 971         rectangle[1] = face.ccw;
 972
 973         rectangle[2].x = point->x - face.point.x;
 974         rectangle[2].y = point->y - face.point.y;
 975         face.point = *point;
 976         translate_point (&face.ccw, &rectangle[2]);
 977         translate_point (&face.cw, &rectangle[2]);
 978
 979         rectangle[2] = face.ccw;
 980         rectangle[3] = face.cw;
 981
 982         _cairo_traps_tessellate_convex_quad (stroker->traps, rectangle);
 983     }
 984
 985     stroker->current_face = face;
 986
 987     return CAIRO_STATUS_SUCCESS;
 988 }
 989
 990 static cairo_status_t
 991 curve_to (void *closure,
 992           const cairo_point_t *b,
 993           const cairo_point_t *c,
 994           const cairo_point_t *d)
 995 {
 996     struct stroker *stroker = closure;
 997     cairo_line_join_t line_join_save;
 998     cairo_spline_t spline;
 999     cairo_stroke_face_t face;
1000     cairo_status_t status;
1001
1002     if (stroker->has_bounds &&
1003         ! _cairo_spline_intersects (&stroker->current_face.point, b, c, d,
1004                                     &stroker->line_bounds))
1005         return line_to (closure, d);
1006
1007     if (! _cairo_spline_init (&spline, spline_to, stroker,
1008                               &stroker->current_face.point, b, c, d))
1009         return line_to (closure, d);
1010
1011     compute_face (&stroker->current_face.point, &spline.initial_slope,
1012                   stroker, &face);
1013
1014     if (stroker->has_current_face) {
1015         /* Join with final face from previous segment */
1016         join (stroker, &stroker->current_face, &face);
1017     } else {
1018         if (! stroker->has_first_face) {
1019             /* Save sub path's first face in case needed for closing join */
1020             stroker->first_face = face;
1021             stroker->has_first_face = TRUE;
1022         }
1023         stroker->has_current_face = TRUE;
1024     }
1025     stroker->current_face = face;
1026
1027     /* Temporarily modify the stroker to use round joins to guarantee
1028      * smooth stroked curves. */
1029     line_join_save = stroker->line_join;
1030     stroker->line_join = CAIRO_LINE_JOIN_ROUND;
1031
1032     status = _cairo_spline_decompose (&spline, stroker->tolerance);
1033
1034     stroker->line_join = line_join_save;
1035
1036     return status;
1037 }
1038
1039 static cairo_status_t
1040 curve_to_dashed (void *closure,
1041                  const cairo_point_t *b,
1042                  const cairo_point_t *c,
1043                  const cairo_point_t *d)
1044 {
1045     struct stroker *stroker = closure;
1046     cairo_spline_t spline;
1047     cairo_line_join_t line_join_save;
1048     cairo_spline_add_point_func_t func;
1049     cairo_status_t status;
1050
1051     func = (cairo_spline_add_point_func_t)line_to_dashed;
1052
1053     if (stroker->has_bounds &&
1054         ! _cairo_spline_intersects (&stroker->current_face.point, b, c, d,
1055                                     &stroker->line_bounds))
1056         return func (closure, d, NULL);
1057
1058     if (! _cairo_spline_init (&spline, func, stroker,
1059                               &stroker->current_face.point, b, c, d))
1060         return func (closure, d, NULL);
1061
1062     /* Temporarily modify the stroker to use round joins to guarantee
1063      * smooth stroked curves. */
1064     line_join_save = stroker->line_join;
1065     stroker->line_join = CAIRO_LINE_JOIN_ROUND;
1066
1067     status = _cairo_spline_decompose (&spline, stroker->tolerance);
1068
1069     stroker->line_join = line_join_save;
1070
1071     return status;
1072 }
1073
1074 static cairo_status_t
1075 _close_path (struct stroker *stroker)
1076 {
1077     if (stroker->has_first_face && stroker->has_current_face) {
1078         /* Join first and final faces of sub path */
1079         join (stroker, &stroker->current_face, &stroker->first_face);
1080     } else {
1081         /* Cap the start and end of the sub path as needed */
1082         add_caps (stroker);
1083     }
1084
1085     stroker->has_initial_sub_path = FALSE;
1086     stroker->has_first_face = FALSE;
1087     stroker->has_current_face = FALSE;
1088     return CAIRO_STATUS_SUCCESS;
1089 }
1090
1091 static cairo_status_t
1092 close_path (void *closure)
1093 {
1094     struct stroker *stroker = closure;
1095     cairo_status_t status;
1096
1097     status = line_to (stroker, &stroker->first_point);
1098     if (unlikely (status))
1099         return status;
1100
1101     return _close_path (stroker);
1102 }
1103
1104 static cairo_status_t
1105 close_path_dashed (void *closure)
1106 {
1107     struct stroker *stroker = closure;
1108     cairo_status_t status;
1109
1110     status = line_to_dashed (stroker, &stroker->first_point);
1111     if (unlikely (status))
1112         return status;
1113
1114     return _close_path (stroker);
1115 }
1116
1117 cairo_int_status_t
1118 _cairo_path_fixed_stroke_to_traps (const cairo_path_fixed_t     *path,
1119                                    const cairo_stroke_style_t   *style,
1120                                    const cairo_matrix_t         *ctm,
1121                                    const cairo_matrix_t         *ctm_inverse,
1122                                    double                        tolerance,
1123                                    cairo_traps_t                *traps)
1124 {
1125     struct stroker stroker;
1126     cairo_status_t status;
1127
1128     status = stroker_init (&stroker, path, style,
1129                            ctm, ctm_inverse, tolerance,
1130                            traps);
1131     if (unlikely (status))
1132         return status;
1133
1134     if (stroker.dash.dashed)
1135         status = _cairo_path_fixed_interpret (path,
1136                                               move_to_dashed,
1137                                               line_to_dashed,
1138                                               curve_to_dashed,
1139                                               close_path_dashed,
1140                                               &stroker);
1141     else
1142         status = _cairo_path_fixed_interpret (path,
1143                                               move_to,
1144                                               line_to,
1145                                               curve_to,
1146                                               close_path,
1147                                               &stroker);
1148     assert(status == CAIRO_STATUS_SUCCESS);
1149     add_caps (&stroker);
1150
1151     stroker_fini (&stroker);
1152
1153     return traps->status;
1154 }