Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | Download | RSS feed

  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.  *
  6.  * This library is free software; you can redistribute it and/or
  7.  * modify it either under the terms of the GNU Lesser General Public
  8.  * License version 2.1 as published by the Free Software Foundation
  9.  * (the "LGPL") or, at your option, under the terms of the Mozilla
  10.  * Public License Version 1.1 (the "MPL"). If you do not alter this
  11.  * notice, a recipient may use your version of this file under either
  12.  * the MPL or the LGPL.
  13.  *
  14.  * You should have received a copy of the LGPL along with this library
  15.  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
  16.  * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
  17.  * You should have received a copy of the MPL along with this library
  18.  * in the file COPYING-MPL-1.1
  19.  *
  20.  * The contents of this file are subject to the Mozilla Public License
  21.  * Version 1.1 (the "License"); you may not use this file except in
  22.  * compliance with the License. You may obtain a copy of the License at
  23.  * http://www.mozilla.org/MPL/
  24.  *
  25.  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
  26.  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
  27.  * the specific language governing rights and limitations.
  28.  *
  29.  * The Original Code is the cairo graphics library.
  30.  *
  31.  * The Initial Developer of the Original Code is University of Southern
  32.  * California.
  33.  *
  34.  * Contributor(s):
  35.  *      Carl D. Worth <cworth@cworth.org>
  36.  *      Chris Wilson <chris@chris-wilson.co.uk>
  37.  */
  38.  
  39. #define _BSD_SOURCE /* for hypot() */
  40. #include "cairoint.h"
  41.  
  42. #include "cairo-boxes-private.h"
  43. #include "cairo-error-private.h"
  44. #include "cairo-path-fixed-private.h"
  45. #include "cairo-slope-private.h"
  46.  
  47. typedef struct _cairo_stroker_dash {
  48.     cairo_bool_t dashed;
  49.     unsigned int dash_index;
  50.     cairo_bool_t dash_on;
  51.     cairo_bool_t dash_starts_on;
  52.     double dash_remain;
  53.  
  54.     double dash_offset;
  55.     const double *dashes;
  56.     unsigned int num_dashes;
  57. } cairo_stroker_dash_t;
  58.  
  59. typedef struct cairo_stroker {
  60.     cairo_stroke_style_t style;
  61.  
  62.     const cairo_matrix_t *ctm;
  63.     const cairo_matrix_t *ctm_inverse;
  64.     double tolerance;
  65.     double ctm_determinant;
  66.     cairo_bool_t ctm_det_positive;
  67.  
  68.     void *closure;
  69.     cairo_status_t (*add_external_edge) (void *closure,
  70.                                          const cairo_point_t *p1,
  71.                                          const cairo_point_t *p2);
  72.     cairo_status_t (*add_triangle) (void *closure,
  73.                                     const cairo_point_t triangle[3]);
  74.     cairo_status_t (*add_triangle_fan) (void *closure,
  75.                                         const cairo_point_t *midpt,
  76.                                         const cairo_point_t *points,
  77.                                         int npoints);
  78.     cairo_status_t (*add_convex_quad) (void *closure,
  79.                                        const cairo_point_t quad[4]);
  80.  
  81.     cairo_pen_t   pen;
  82.  
  83.     cairo_point_t current_point;
  84.     cairo_point_t first_point;
  85.  
  86.     cairo_bool_t has_initial_sub_path;
  87.  
  88.     cairo_bool_t has_current_face;
  89.     cairo_stroke_face_t current_face;
  90.  
  91.     cairo_bool_t has_first_face;
  92.     cairo_stroke_face_t first_face;
  93.  
  94.     cairo_stroker_dash_t dash;
  95.  
  96.     cairo_bool_t has_bounds;
  97.     cairo_box_t bounds;
  98. } cairo_stroker_t;
  99.  
  100. static void
  101. _cairo_stroker_dash_start (cairo_stroker_dash_t *dash)
  102. {
  103.     double offset;
  104.     cairo_bool_t on = TRUE;
  105.     unsigned int i = 0;
  106.  
  107.     if (! dash->dashed)
  108.         return;
  109.  
  110.     offset = dash->dash_offset;
  111.  
  112.     /* We stop searching for a starting point as soon as the
  113.        offset reaches zero.  Otherwise when an initial dash
  114.        segment shrinks to zero it will be skipped over. */
  115.     while (offset > 0.0 && offset >= dash->dashes[i]) {
  116.         offset -= dash->dashes[i];
  117.         on = !on;
  118.         if (++i == dash->num_dashes)
  119.             i = 0;
  120.     }
  121.  
  122.     dash->dash_index = i;
  123.     dash->dash_on = dash->dash_starts_on = on;
  124.     dash->dash_remain = dash->dashes[i] - offset;
  125. }
  126.  
  127. static void
  128. _cairo_stroker_dash_step (cairo_stroker_dash_t *dash, double step)
  129. {
  130.     dash->dash_remain -= step;
  131.     if (dash->dash_remain <= 0.) {
  132.         if (++dash->dash_index == dash->num_dashes)
  133.             dash->dash_index = 0;
  134.  
  135.         dash->dash_on = ! dash->dash_on;
  136.         dash->dash_remain = dash->dashes[dash->dash_index];
  137.     }
  138. }
  139.  
  140. static void
  141. _cairo_stroker_dash_init (cairo_stroker_dash_t *dash,
  142.                           const cairo_stroke_style_t *style)
  143. {
  144.     dash->dashed = style->dash != NULL;
  145.     if (! dash->dashed)
  146.         return;
  147.  
  148.     dash->dashes = style->dash;
  149.     dash->num_dashes = style->num_dashes;
  150.     dash->dash_offset = style->dash_offset;
  151.  
  152.     _cairo_stroker_dash_start (dash);
  153. }
  154.  
  155. static cairo_status_t
  156. _cairo_stroker_init (cairo_stroker_t            *stroker,
  157.                      const cairo_stroke_style_t *stroke_style,
  158.                      const cairo_matrix_t       *ctm,
  159.                      const cairo_matrix_t       *ctm_inverse,
  160.                      double                      tolerance)
  161. {
  162.     cairo_status_t status;
  163.  
  164.     stroker->style = *stroke_style;
  165.     stroker->ctm = ctm;
  166.     stroker->ctm_inverse = ctm_inverse;
  167.     stroker->tolerance = tolerance;
  168.  
  169.     stroker->ctm_determinant = _cairo_matrix_compute_determinant (stroker->ctm);
  170.     stroker->ctm_det_positive = stroker->ctm_determinant >= 0.0;
  171.  
  172.     status = _cairo_pen_init (&stroker->pen,
  173.                               stroke_style->line_width / 2.0,
  174.                               tolerance, ctm);
  175.     if (unlikely (status))
  176.         return status;
  177.  
  178.     stroker->has_bounds = FALSE;
  179.  
  180.     stroker->has_current_face = FALSE;
  181.     stroker->has_first_face = FALSE;
  182.     stroker->has_initial_sub_path = FALSE;
  183.  
  184.     _cairo_stroker_dash_init (&stroker->dash, stroke_style);
  185.  
  186.     stroker->add_external_edge = NULL;
  187.  
  188.     return CAIRO_STATUS_SUCCESS;
  189. }
  190.  
  191. static void
  192. _cairo_stroker_limit (cairo_stroker_t *stroker,
  193.                       const cairo_box_t *boxes,
  194.                       int num_boxes)
  195. {
  196.     double dx, dy;
  197.     cairo_fixed_t fdx, fdy;
  198.  
  199.     stroker->has_bounds = TRUE;
  200.     _cairo_boxes_get_extents (boxes, num_boxes, &stroker->bounds);
  201.  
  202.     /* Extend the bounds in each direction to account for the maximum area
  203.      * we might generate trapezoids, to capture line segments that are outside
  204.      * of the bounds but which might generate rendering that's within bounds.
  205.      */
  206.  
  207.     _cairo_stroke_style_max_distance_from_path (&stroker->style, stroker->ctm,
  208.                                                 &dx, &dy);
  209.  
  210.     fdx = _cairo_fixed_from_double (dx);
  211.     fdy = _cairo_fixed_from_double (dy);
  212.  
  213.     stroker->bounds.p1.x -= fdx;
  214.     stroker->bounds.p2.x += fdx;
  215.  
  216.     stroker->bounds.p1.y -= fdy;
  217.     stroker->bounds.p2.y += fdy;
  218. }
  219.  
  220. static void
  221. _cairo_stroker_fini (cairo_stroker_t *stroker)
  222. {
  223.     _cairo_pen_fini (&stroker->pen);
  224. }
  225.  
  226. static void
  227. _translate_point (cairo_point_t *point, const cairo_point_t *offset)
  228. {
  229.     point->x += offset->x;
  230.     point->y += offset->y;
  231. }
  232.  
  233. static int
  234. _cairo_stroker_join_is_clockwise (const cairo_stroke_face_t *in,
  235.                                   const cairo_stroke_face_t *out)
  236. {
  237.     cairo_slope_t in_slope, out_slope;
  238.  
  239.     _cairo_slope_init (&in_slope, &in->point, &in->cw);
  240.     _cairo_slope_init (&out_slope, &out->point, &out->cw);
  241.  
  242.     return _cairo_slope_compare (&in_slope, &out_slope) < 0;
  243. }
  244.  
  245. /**
  246.  * _cairo_slope_compare_sgn
  247.  *
  248.  * Return -1, 0 or 1 depending on the relative slopes of
  249.  * two lines.
  250.  */
  251. static int
  252. _cairo_slope_compare_sgn (double dx1, double dy1, double dx2, double dy2)
  253. {
  254.     double  c = (dx1 * dy2 - dx2 * dy1);
  255.  
  256.     if (c > 0) return 1;
  257.     if (c < 0) return -1;
  258.     return 0;
  259. }
  260.  
  261. static inline int
  262. _range_step (int i, int step, int max)
  263. {
  264.     i += step;
  265.     if (i < 0)
  266.         i = max - 1;
  267.     if (i >= max)
  268.         i = 0;
  269.     return i;
  270. }
  271.  
  272. /*
  273.  * Construct a fan around the midpoint using the vertices from pen between
  274.  * inpt and outpt.
  275.  */
  276. static cairo_status_t
  277. _tessellate_fan (cairo_stroker_t *stroker,
  278.                  const cairo_slope_t *in_vector,
  279.                  const cairo_slope_t *out_vector,
  280.                  const cairo_point_t *midpt,
  281.                  const cairo_point_t *inpt,
  282.                  const cairo_point_t *outpt,
  283.                  cairo_bool_t clockwise)
  284. {
  285.     cairo_point_t stack_points[64], *points = stack_points;
  286.     int start, stop, step, i, npoints;
  287.     cairo_status_t status;
  288.  
  289.     if (clockwise) {
  290.         step  = -1;
  291.  
  292.         start = _cairo_pen_find_active_ccw_vertex_index (&stroker->pen,
  293.                                                          in_vector);
  294.         if (_cairo_slope_compare (&stroker->pen.vertices[start].slope_ccw,
  295.                                   in_vector) < 0)
  296.             start = _range_step (start, -1, stroker->pen.num_vertices);
  297.  
  298.         stop  = _cairo_pen_find_active_ccw_vertex_index (&stroker->pen,
  299.                                                          out_vector);
  300.         if (_cairo_slope_compare (&stroker->pen.vertices[stop].slope_cw,
  301.                                   out_vector) > 0)
  302.         {
  303.             stop = _range_step (stop, 1, stroker->pen.num_vertices);
  304.             if (_cairo_slope_compare (&stroker->pen.vertices[stop].slope_ccw,
  305.                                       in_vector) < 0)
  306.             {
  307.                 goto BEVEL;
  308.             }
  309.         }
  310.  
  311.         npoints = start - stop;
  312.     } else {
  313.         step  = 1;
  314.  
  315.         start = _cairo_pen_find_active_cw_vertex_index (&stroker->pen,
  316.                                                         in_vector);
  317.         if (_cairo_slope_compare (&stroker->pen.vertices[start].slope_cw,
  318.                                   in_vector) < 0)
  319.             start = _range_step (start, 1, stroker->pen.num_vertices);
  320.  
  321.         stop  = _cairo_pen_find_active_cw_vertex_index (&stroker->pen,
  322.                                                         out_vector);
  323.         if (_cairo_slope_compare (&stroker->pen.vertices[stop].slope_ccw,
  324.                                   out_vector) > 0)
  325.         {
  326.             stop = _range_step (stop, -1, stroker->pen.num_vertices);
  327.             if (_cairo_slope_compare (&stroker->pen.vertices[stop].slope_cw,
  328.                                       in_vector) < 0)
  329.             {
  330.                 goto BEVEL;
  331.             }
  332.         }
  333.  
  334.         npoints = stop - start;
  335.     }
  336.     stop = _range_step (stop, step, stroker->pen.num_vertices);
  337.  
  338.     if (npoints < 0)
  339.         npoints += stroker->pen.num_vertices;
  340.     npoints += 3;
  341.  
  342.     if (npoints <= 1)
  343.         goto BEVEL;
  344.  
  345.     if (npoints > ARRAY_LENGTH (stack_points)) {
  346.         points = _cairo_malloc_ab (npoints, sizeof (cairo_point_t));
  347.         if (unlikely (points == NULL))
  348.             return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  349.     }
  350.  
  351.  
  352.     /* Construct the fan. */
  353.     npoints = 0;
  354.     points[npoints++] = *inpt;
  355.     for (i = start;
  356.          i != stop;
  357.         i = _range_step (i, step, stroker->pen.num_vertices))
  358.     {
  359.         points[npoints] = *midpt;
  360.         _translate_point (&points[npoints], &stroker->pen.vertices[i].point);
  361.         npoints++;
  362.     }
  363.     points[npoints++] = *outpt;
  364.  
  365.     if (stroker->add_external_edge != NULL) {
  366.         for (i = 0; i < npoints - 1; i++) {
  367.             if (clockwise) {
  368.                 status = stroker->add_external_edge (stroker->closure,
  369.                                                      &points[i], &points[i+1]);
  370.             } else {
  371.                 status = stroker->add_external_edge (stroker->closure,
  372.                                                      &points[i+1], &points[i]);
  373.             }
  374.             if (unlikely (status))
  375.                 break;
  376.         }
  377.     } else {
  378.         status = stroker->add_triangle_fan (stroker->closure,
  379.                                             midpt, points, npoints);
  380.     }
  381.  
  382.     if (points != stack_points)
  383.         free (points);
  384.  
  385.     return status;
  386.  
  387. BEVEL:
  388.     /* Ensure a leak free connection... */
  389.     if (stroker->add_external_edge != NULL) {
  390.         if (clockwise)
  391.             return stroker->add_external_edge (stroker->closure, inpt, outpt);
  392.         else
  393.             return stroker->add_external_edge (stroker->closure, outpt, inpt);
  394.     } else {
  395.         stack_points[0] = *midpt;
  396.         stack_points[1] = *inpt;
  397.         stack_points[2] = *outpt;
  398.         return stroker->add_triangle (stroker->closure, stack_points);
  399.     }
  400. }
  401.  
  402. static cairo_status_t
  403. _cairo_stroker_join (cairo_stroker_t *stroker,
  404.                      const cairo_stroke_face_t *in,
  405.                      const cairo_stroke_face_t *out)
  406. {
  407.     int  clockwise = _cairo_stroker_join_is_clockwise (out, in);
  408.     const cairo_point_t *inpt, *outpt;
  409.     cairo_point_t points[4];
  410.     cairo_status_t status;
  411.  
  412.     if (in->cw.x  == out->cw.x  && in->cw.y  == out->cw.y &&
  413.         in->ccw.x == out->ccw.x && in->ccw.y == out->ccw.y)
  414.     {
  415.         return CAIRO_STATUS_SUCCESS;
  416.     }
  417.  
  418.     if (clockwise) {
  419.         if (stroker->add_external_edge != NULL) {
  420.             status = stroker->add_external_edge (stroker->closure,
  421.                                                  &out->cw, &in->point);
  422.             if (unlikely (status))
  423.                 return status;
  424.  
  425.             status = stroker->add_external_edge (stroker->closure,
  426.                                                  &in->point, &in->cw);
  427.             if (unlikely (status))
  428.                 return status;
  429.         }
  430.  
  431.         inpt = &in->ccw;
  432.         outpt = &out->ccw;
  433.     } else {
  434.         if (stroker->add_external_edge != NULL) {
  435.             status = stroker->add_external_edge (stroker->closure,
  436.                                                  &in->ccw, &in->point);
  437.             if (unlikely (status))
  438.                 return status;
  439.  
  440.             status = stroker->add_external_edge (stroker->closure,
  441.                                                  &in->point, &out->ccw);
  442.             if (unlikely (status))
  443.                 return status;
  444.         }
  445.  
  446.         inpt = &in->cw;
  447.         outpt = &out->cw;
  448.     }
  449.  
  450.     switch (stroker->style.line_join) {
  451.     case CAIRO_LINE_JOIN_ROUND:
  452.         /* construct a fan around the common midpoint */
  453.         return _tessellate_fan (stroker,
  454.                                 &in->dev_vector,
  455.                                 &out->dev_vector,
  456.                                 &in->point, inpt, outpt,
  457.                                 clockwise);
  458.  
  459.     case CAIRO_LINE_JOIN_MITER:
  460.     default: {
  461.         /* dot product of incoming slope vector with outgoing slope vector */
  462.         double  in_dot_out = -in->usr_vector.x * out->usr_vector.x +
  463.                              -in->usr_vector.y * out->usr_vector.y;
  464.         double  ml = stroker->style.miter_limit;
  465.  
  466.         /* Check the miter limit -- lines meeting at an acute angle
  467.          * can generate long miters, the limit converts them to bevel
  468.          *
  469.          * Consider the miter join formed when two line segments
  470.          * meet at an angle psi:
  471.          *
  472.          *         /.\
  473.          *        /. .\
  474.          *       /./ \.\
  475.          *      /./psi\.\
  476.          *
  477.          * We can zoom in on the right half of that to see:
  478.          *
  479.          *          |\
  480.          *          | \ psi/2
  481.          *          |  \
  482.          *          |   \
  483.          *          |    \
  484.          *          |     \
  485.          *        miter    \
  486.          *       length     \
  487.          *          |        \
  488.          *          |        .\
  489.          *          |    .     \
  490.          *          |.   line   \
  491.          *           \    width  \
  492.          *            \           \
  493.          *
  494.          *
  495.          * The right triangle in that figure, (the line-width side is
  496.          * shown faintly with three '.' characters), gives us the
  497.          * following expression relating miter length, angle and line
  498.          * width:
  499.          *
  500.          *      1 /sin (psi/2) = miter_length / line_width
  501.          *
  502.          * The right-hand side of this relationship is the same ratio
  503.          * in which the miter limit (ml) is expressed. We want to know
  504.          * when the miter length is within the miter limit. That is
  505.          * when the following condition holds:
  506.          *
  507.          *      1/sin(psi/2) <= ml
  508.          *      1 <= ml sin(psi/2)
  509.          *      1 <= ml² sin²(psi/2)
  510.          *      2 <= ml² 2 sin²(psi/2)
  511.          *                              2·sin²(psi/2) = 1-cos(psi)
  512.          *      2 <= ml² (1-cos(psi))
  513.          *
  514.          *                              in · out = |in| |out| cos (psi)
  515.          *
  516.          * in and out are both unit vectors, so:
  517.          *
  518.          *                              in · out = cos (psi)
  519.          *
  520.          *      2 <= ml² (1 - in · out)
  521.          *
  522.          */
  523.         if (2 <= ml * ml * (1 - in_dot_out)) {
  524.             double              x1, y1, x2, y2;
  525.             double              mx, my;
  526.             double              dx1, dx2, dy1, dy2;
  527.             double              ix, iy;
  528.             double              fdx1, fdy1, fdx2, fdy2;
  529.             double              mdx, mdy;
  530.  
  531.             /*
  532.              * we've got the points already transformed to device
  533.              * space, but need to do some computation with them and
  534.              * also need to transform the slope from user space to
  535.              * device space
  536.              */
  537.             /* outer point of incoming line face */
  538.             x1 = _cairo_fixed_to_double (inpt->x);
  539.             y1 = _cairo_fixed_to_double (inpt->y);
  540.             dx1 = in->usr_vector.x;
  541.             dy1 = in->usr_vector.y;
  542.             cairo_matrix_transform_distance (stroker->ctm, &dx1, &dy1);
  543.  
  544.             /* outer point of outgoing line face */
  545.             x2 = _cairo_fixed_to_double (outpt->x);
  546.             y2 = _cairo_fixed_to_double (outpt->y);
  547.             dx2 = out->usr_vector.x;
  548.             dy2 = out->usr_vector.y;
  549.             cairo_matrix_transform_distance (stroker->ctm, &dx2, &dy2);
  550.  
  551.             /*
  552.              * Compute the location of the outer corner of the miter.
  553.              * That's pretty easy -- just the intersection of the two
  554.              * outer edges.  We've got slopes and points on each
  555.              * of those edges.  Compute my directly, then compute
  556.              * mx by using the edge with the larger dy; that avoids
  557.              * dividing by values close to zero.
  558.              */
  559.             my = (((x2 - x1) * dy1 * dy2 - y2 * dx2 * dy1 + y1 * dx1 * dy2) /
  560.                   (dx1 * dy2 - dx2 * dy1));
  561.             if (fabs (dy1) >= fabs (dy2))
  562.                 mx = (my - y1) * dx1 / dy1 + x1;
  563.             else
  564.                 mx = (my - y2) * dx2 / dy2 + x2;
  565.  
  566.             /*
  567.              * When the two outer edges are nearly parallel, slight
  568.              * perturbations in the position of the outer points of the lines
  569.              * caused by representing them in fixed point form can cause the
  570.              * intersection point of the miter to move a large amount. If
  571.              * that moves the miter intersection from between the two faces,
  572.              * then draw a bevel instead.
  573.              */
  574.  
  575.             ix = _cairo_fixed_to_double (in->point.x);
  576.             iy = _cairo_fixed_to_double (in->point.y);
  577.  
  578.             /* slope of one face */
  579.             fdx1 = x1 - ix; fdy1 = y1 - iy;
  580.  
  581.             /* slope of the other face */
  582.             fdx2 = x2 - ix; fdy2 = y2 - iy;
  583.  
  584.             /* slope from the intersection to the miter point */
  585.             mdx = mx - ix; mdy = my - iy;
  586.  
  587.             /*
  588.              * Make sure the miter point line lies between the two
  589.              * faces by comparing the slopes
  590.              */
  591.             if (_cairo_slope_compare_sgn (fdx1, fdy1, mdx, mdy) !=
  592.                 _cairo_slope_compare_sgn (fdx2, fdy2, mdx, mdy))
  593.             {
  594.                 if (stroker->add_external_edge != NULL) {
  595.                     points[0].x = _cairo_fixed_from_double (mx);
  596.                     points[0].y = _cairo_fixed_from_double (my);
  597.  
  598.                     if (clockwise) {
  599.                         status = stroker->add_external_edge (stroker->closure,
  600.                                                              inpt, &points[0]);
  601.                         if (unlikely (status))
  602.                             return status;
  603.  
  604.                         status = stroker->add_external_edge (stroker->closure,
  605.                                                              &points[0], outpt);
  606.                         if (unlikely (status))
  607.                             return status;
  608.                     } else {
  609.                         status = stroker->add_external_edge (stroker->closure,
  610.                                                              outpt, &points[0]);
  611.                         if (unlikely (status))
  612.                             return status;
  613.  
  614.                         status = stroker->add_external_edge (stroker->closure,
  615.                                                              &points[0], inpt);
  616.                         if (unlikely (status))
  617.                             return status;
  618.                     }
  619.  
  620.                     return CAIRO_STATUS_SUCCESS;
  621.                 } else {
  622.                     points[0] = in->point;
  623.                     points[1] = *inpt;
  624.                     points[2].x = _cairo_fixed_from_double (mx);
  625.                     points[2].y = _cairo_fixed_from_double (my);
  626.                     points[3] = *outpt;
  627.  
  628.                     return stroker->add_convex_quad (stroker->closure, points);
  629.                 }
  630.             }
  631.         }
  632.     }
  633.  
  634.     /* fall through ... */
  635.  
  636.     case CAIRO_LINE_JOIN_BEVEL:
  637.         if (stroker->add_external_edge != NULL) {
  638.             if (clockwise) {
  639.                 return stroker->add_external_edge (stroker->closure,
  640.                                                    inpt, outpt);
  641.             } else {
  642.                 return stroker->add_external_edge (stroker->closure,
  643.                                                    outpt, inpt);
  644.             }
  645.         } else {
  646.             points[0] = in->point;
  647.             points[1] = *inpt;
  648.             points[2] = *outpt;
  649.  
  650.             return stroker->add_triangle (stroker->closure, points);
  651.         }
  652.     }
  653. }
  654.  
  655. static cairo_status_t
  656. _cairo_stroker_add_cap (cairo_stroker_t *stroker,
  657.                         const cairo_stroke_face_t *f)
  658. {
  659.     switch (stroker->style.line_cap) {
  660.     case CAIRO_LINE_CAP_ROUND: {
  661.         cairo_slope_t slope;
  662.  
  663.         slope.dx = -f->dev_vector.dx;
  664.         slope.dy = -f->dev_vector.dy;
  665.  
  666.         return _tessellate_fan (stroker,
  667.                                 &f->dev_vector,
  668.                                 &slope,
  669.                                 &f->point, &f->cw, &f->ccw,
  670.                                 FALSE);
  671.  
  672.     }
  673.  
  674.     case CAIRO_LINE_CAP_SQUARE: {
  675.         double dx, dy;
  676.         cairo_slope_t   fvector;
  677.         cairo_point_t   quad[4];
  678.  
  679.         dx = f->usr_vector.x;
  680.         dy = f->usr_vector.y;
  681.         dx *= stroker->style.line_width / 2.0;
  682.         dy *= stroker->style.line_width / 2.0;
  683.         cairo_matrix_transform_distance (stroker->ctm, &dx, &dy);
  684.         fvector.dx = _cairo_fixed_from_double (dx);
  685.         fvector.dy = _cairo_fixed_from_double (dy);
  686.  
  687.         quad[0] = f->ccw;
  688.         quad[1].x = f->ccw.x + fvector.dx;
  689.         quad[1].y = f->ccw.y + fvector.dy;
  690.         quad[2].x = f->cw.x + fvector.dx;
  691.         quad[2].y = f->cw.y + fvector.dy;
  692.         quad[3] = f->cw;
  693.  
  694.         if (stroker->add_external_edge != NULL) {
  695.             cairo_status_t status;
  696.  
  697.             status = stroker->add_external_edge (stroker->closure,
  698.                                                  &quad[0], &quad[1]);
  699.             if (unlikely (status))
  700.                 return status;
  701.  
  702.             status = stroker->add_external_edge (stroker->closure,
  703.                                                  &quad[1], &quad[2]);
  704.             if (unlikely (status))
  705.                 return status;
  706.  
  707.             status = stroker->add_external_edge (stroker->closure,
  708.                                                  &quad[2], &quad[3]);
  709.             if (unlikely (status))
  710.                 return status;
  711.  
  712.             return CAIRO_STATUS_SUCCESS;
  713.         } else {
  714.             return stroker->add_convex_quad (stroker->closure, quad);
  715.         }
  716.     }
  717.  
  718.     case CAIRO_LINE_CAP_BUTT:
  719.     default:
  720.         if (stroker->add_external_edge != NULL) {
  721.             return stroker->add_external_edge (stroker->closure,
  722.                                                &f->ccw, &f->cw);
  723.         } else {
  724.             return CAIRO_STATUS_SUCCESS;
  725.         }
  726.     }
  727. }
  728.  
  729. static cairo_status_t
  730. _cairo_stroker_add_leading_cap (cairo_stroker_t     *stroker,
  731.                                 const cairo_stroke_face_t *face)
  732. {
  733.     cairo_stroke_face_t reversed;
  734.     cairo_point_t t;
  735.  
  736.     reversed = *face;
  737.  
  738.     /* The initial cap needs an outward facing vector. Reverse everything */
  739.     reversed.usr_vector.x = -reversed.usr_vector.x;
  740.     reversed.usr_vector.y = -reversed.usr_vector.y;
  741.     reversed.dev_vector.dx = -reversed.dev_vector.dx;
  742.     reversed.dev_vector.dy = -reversed.dev_vector.dy;
  743.     t = reversed.cw;
  744.     reversed.cw = reversed.ccw;
  745.     reversed.ccw = t;
  746.  
  747.     return _cairo_stroker_add_cap (stroker, &reversed);
  748. }
  749.  
  750. static cairo_status_t
  751. _cairo_stroker_add_trailing_cap (cairo_stroker_t     *stroker,
  752.                                  const cairo_stroke_face_t *face)
  753. {
  754.     return _cairo_stroker_add_cap (stroker, face);
  755. }
  756.  
  757. static inline cairo_bool_t
  758. _compute_normalized_device_slope (double *dx, double *dy,
  759.                                   const cairo_matrix_t *ctm_inverse,
  760.                                   double *mag_out)
  761. {
  762.     double dx0 = *dx, dy0 = *dy;
  763.     double mag;
  764.  
  765.     cairo_matrix_transform_distance (ctm_inverse, &dx0, &dy0);
  766.  
  767.     if (dx0 == 0.0 && dy0 == 0.0) {
  768.         if (mag_out)
  769.             *mag_out = 0.0;
  770.         return FALSE;
  771.     }
  772.  
  773.     if (dx0 == 0.0) {
  774.         *dx = 0.0;
  775.         if (dy0 > 0.0) {
  776.             mag = dy0;
  777.             *dy = 1.0;
  778.         } else {
  779.             mag = -dy0;
  780.             *dy = -1.0;
  781.         }
  782.     } else if (dy0 == 0.0) {
  783.         *dy = 0.0;
  784.         if (dx0 > 0.0) {
  785.             mag = dx0;
  786.             *dx = 1.0;
  787.         } else {
  788.             mag = -dx0;
  789.             *dx = -1.0;
  790.         }
  791.     } else {
  792.         mag = hypot (dx0, dy0);
  793.         *dx = dx0 / mag;
  794.         *dy = dy0 / mag;
  795.     }
  796.  
  797.     if (mag_out)
  798.         *mag_out = mag;
  799.  
  800.     return TRUE;
  801. }
  802.  
  803. static void
  804. _compute_face (const cairo_point_t *point, cairo_slope_t *dev_slope,
  805.                double slope_dx, double slope_dy,
  806.                cairo_stroker_t *stroker, cairo_stroke_face_t *face)
  807. {
  808.     double face_dx, face_dy;
  809.     cairo_point_t offset_ccw, offset_cw;
  810.  
  811.     /*
  812.      * rotate to get a line_width/2 vector along the face, note that
  813.      * the vector must be rotated the right direction in device space,
  814.      * but by 90° in user space. So, the rotation depends on
  815.      * whether the ctm reflects or not, and that can be determined
  816.      * by looking at the determinant of the matrix.
  817.      */
  818.     if (stroker->ctm_det_positive)
  819.     {
  820.         face_dx = - slope_dy * (stroker->style.line_width / 2.0);
  821.         face_dy = slope_dx * (stroker->style.line_width / 2.0);
  822.     }
  823.     else
  824.     {
  825.         face_dx = slope_dy * (stroker->style.line_width / 2.0);
  826.         face_dy = - slope_dx * (stroker->style.line_width / 2.0);
  827.     }
  828.  
  829.     /* back to device space */
  830.     cairo_matrix_transform_distance (stroker->ctm, &face_dx, &face_dy);
  831.  
  832.     offset_ccw.x = _cairo_fixed_from_double (face_dx);
  833.     offset_ccw.y = _cairo_fixed_from_double (face_dy);
  834.     offset_cw.x = -offset_ccw.x;
  835.     offset_cw.y = -offset_ccw.y;
  836.  
  837.     face->ccw = *point;
  838.     _translate_point (&face->ccw, &offset_ccw);
  839.  
  840.     face->point = *point;
  841.  
  842.     face->cw = *point;
  843.     _translate_point (&face->cw, &offset_cw);
  844.  
  845.     face->usr_vector.x = slope_dx;
  846.     face->usr_vector.y = slope_dy;
  847.  
  848.     face->dev_vector = *dev_slope;
  849. }
  850.  
  851. static cairo_status_t
  852. _cairo_stroker_add_caps (cairo_stroker_t *stroker)
  853. {
  854.     cairo_status_t status;
  855.  
  856.     /* check for a degenerative sub_path */
  857.     if (stroker->has_initial_sub_path
  858.         && ! stroker->has_first_face
  859.         && ! stroker->has_current_face
  860.         && stroker->style.line_cap == CAIRO_LINE_JOIN_ROUND)
  861.     {
  862.         /* pick an arbitrary slope to use */
  863.         double dx = 1.0, dy = 0.0;
  864.         cairo_slope_t slope = { CAIRO_FIXED_ONE, 0 };
  865.         cairo_stroke_face_t face;
  866.  
  867.         _compute_normalized_device_slope (&dx, &dy,
  868.                                           stroker->ctm_inverse, NULL);
  869.  
  870.         /* arbitrarily choose first_point
  871.          * first_point and current_point should be the same */
  872.         _compute_face (&stroker->first_point, &slope, dx, dy, stroker, &face);
  873.  
  874.         status = _cairo_stroker_add_leading_cap (stroker, &face);
  875.         if (unlikely (status))
  876.             return status;
  877.  
  878.         status = _cairo_stroker_add_trailing_cap (stroker, &face);
  879.         if (unlikely (status))
  880.             return status;
  881.     }
  882.  
  883.     if (stroker->has_first_face) {
  884.         status = _cairo_stroker_add_leading_cap (stroker,
  885.                                                  &stroker->first_face);
  886.         if (unlikely (status))
  887.             return status;
  888.     }
  889.  
  890.     if (stroker->has_current_face) {
  891.         status = _cairo_stroker_add_trailing_cap (stroker,
  892.                                                   &stroker->current_face);
  893.         if (unlikely (status))
  894.             return status;
  895.     }
  896.  
  897.     return CAIRO_STATUS_SUCCESS;
  898. }
  899.  
  900. static cairo_status_t
  901. _cairo_stroker_add_sub_edge (cairo_stroker_t *stroker,
  902.                              const cairo_point_t *p1,
  903.                              const cairo_point_t *p2,
  904.                              cairo_slope_t *dev_slope,
  905.                              double slope_dx, double slope_dy,
  906.                              cairo_stroke_face_t *start,
  907.                              cairo_stroke_face_t *end)
  908. {
  909.     _compute_face (p1, dev_slope, slope_dx, slope_dy, stroker, start);
  910.     *end = *start;
  911.  
  912.     if (p1->x == p2->x && p1->y == p2->y)
  913.         return CAIRO_STATUS_SUCCESS;
  914.  
  915.     end->point = *p2;
  916.     end->ccw.x += p2->x - p1->x;
  917.     end->ccw.y += p2->y - p1->y;
  918.     end->cw.x += p2->x - p1->x;
  919.     end->cw.y += p2->y - p1->y;
  920.  
  921.     if (stroker->add_external_edge != NULL) {
  922.         cairo_status_t status;
  923.  
  924.         status = stroker->add_external_edge (stroker->closure,
  925.                                              &end->cw, &start->cw);
  926.         if (unlikely (status))
  927.             return status;
  928.  
  929.         status = stroker->add_external_edge (stroker->closure,
  930.                                              &start->ccw, &end->ccw);
  931.         if (unlikely (status))
  932.             return status;
  933.  
  934.         return CAIRO_STATUS_SUCCESS;
  935.     } else {
  936.         cairo_point_t quad[4];
  937.  
  938.         quad[0] = start->cw;
  939.         quad[1] = end->cw;
  940.         quad[2] = end->ccw;
  941.         quad[3] = start->ccw;
  942.  
  943.         return stroker->add_convex_quad (stroker->closure, quad);
  944.     }
  945. }
  946.  
  947. static cairo_status_t
  948. _cairo_stroker_move_to (void *closure,
  949.                         const cairo_point_t *point)
  950. {
  951.     cairo_stroker_t *stroker = closure;
  952.     cairo_status_t status;
  953.  
  954.     /* reset the dash pattern for new sub paths */
  955.     _cairo_stroker_dash_start (&stroker->dash);
  956.  
  957.     /* Cap the start and end of the previous sub path as needed */
  958.     status = _cairo_stroker_add_caps (stroker);
  959.     if (unlikely (status))
  960.         return status;
  961.  
  962.     stroker->first_point = *point;
  963.     stroker->current_point = *point;
  964.  
  965.     stroker->has_first_face = FALSE;
  966.     stroker->has_current_face = FALSE;
  967.     stroker->has_initial_sub_path = FALSE;
  968.  
  969.     return CAIRO_STATUS_SUCCESS;
  970. }
  971.  
  972. static cairo_status_t
  973. _cairo_stroker_line_to (void *closure,
  974.                         const cairo_point_t *point)
  975. {
  976.     cairo_stroker_t *stroker = closure;
  977.     cairo_stroke_face_t start, end;
  978.     cairo_point_t *p1 = &stroker->current_point;
  979.     cairo_slope_t dev_slope;
  980.     double slope_dx, slope_dy;
  981.     cairo_status_t status;
  982.  
  983.     stroker->has_initial_sub_path = TRUE;
  984.  
  985.     if (p1->x == point->x && p1->y == point->y)
  986.         return CAIRO_STATUS_SUCCESS;
  987.  
  988.     _cairo_slope_init (&dev_slope, p1, point);
  989.     slope_dx = _cairo_fixed_to_double (point->x - p1->x);
  990.     slope_dy = _cairo_fixed_to_double (point->y - p1->y);
  991.     _compute_normalized_device_slope (&slope_dx, &slope_dy,
  992.                                       stroker->ctm_inverse, NULL);
  993.  
  994.     status = _cairo_stroker_add_sub_edge (stroker,
  995.                                           p1, point,
  996.                                           &dev_slope,
  997.                                           slope_dx, slope_dy,
  998.                                           &start, &end);
  999.     if (unlikely (status))
  1000.         return status;
  1001.  
  1002.     if (stroker->has_current_face) {
  1003.         /* Join with final face from previous segment */
  1004.         status = _cairo_stroker_join (stroker,
  1005.                                       &stroker->current_face,
  1006.                                       &start);
  1007.         if (unlikely (status))
  1008.             return status;
  1009.     } else if (! stroker->has_first_face) {
  1010.         /* Save sub path's first face in case needed for closing join */
  1011.         stroker->first_face = start;
  1012.         stroker->has_first_face = TRUE;
  1013.     }
  1014.     stroker->current_face = end;
  1015.     stroker->has_current_face = TRUE;
  1016.  
  1017.     stroker->current_point = *point;
  1018.  
  1019.     return CAIRO_STATUS_SUCCESS;
  1020. }
  1021.  
  1022. /*
  1023.  * Dashed lines.  Cap each dash end, join around turns when on
  1024.  */
  1025. static cairo_status_t
  1026. _cairo_stroker_line_to_dashed (void *closure,
  1027.                                const cairo_point_t *p2)
  1028. {
  1029.     cairo_stroker_t *stroker = closure;
  1030.     double mag, remain, step_length = 0;
  1031.     double slope_dx, slope_dy;
  1032.     double dx2, dy2;
  1033.     cairo_stroke_face_t sub_start, sub_end;
  1034.     cairo_point_t *p1 = &stroker->current_point;
  1035.     cairo_slope_t dev_slope;
  1036.     cairo_line_t segment;
  1037.     cairo_bool_t fully_in_bounds;
  1038.     cairo_status_t status;
  1039.  
  1040.     stroker->has_initial_sub_path = stroker->dash.dash_starts_on;
  1041.  
  1042.     if (p1->x == p2->x && p1->y == p2->y)
  1043.         return CAIRO_STATUS_SUCCESS;
  1044.  
  1045.     fully_in_bounds = TRUE;
  1046.     if (stroker->has_bounds &&
  1047.         (! _cairo_box_contains_point (&stroker->bounds, p1) ||
  1048.          ! _cairo_box_contains_point (&stroker->bounds, p2)))
  1049.     {
  1050.         fully_in_bounds = FALSE;
  1051.     }
  1052.  
  1053.     _cairo_slope_init (&dev_slope, p1, p2);
  1054.  
  1055.     slope_dx = _cairo_fixed_to_double (p2->x - p1->x);
  1056.     slope_dy = _cairo_fixed_to_double (p2->y - p1->y);
  1057.  
  1058.     if (! _compute_normalized_device_slope (&slope_dx, &slope_dy,
  1059.                                             stroker->ctm_inverse, &mag))
  1060.     {
  1061.         return CAIRO_STATUS_SUCCESS;
  1062.     }
  1063.  
  1064.     remain = mag;
  1065.     segment.p1 = *p1;
  1066.     while (remain) {
  1067.         step_length = MIN (stroker->dash.dash_remain, remain);
  1068.         remain -= step_length;
  1069.         dx2 = slope_dx * (mag - remain);
  1070.         dy2 = slope_dy * (mag - remain);
  1071.         cairo_matrix_transform_distance (stroker->ctm, &dx2, &dy2);
  1072.         segment.p2.x = _cairo_fixed_from_double (dx2) + p1->x;
  1073.         segment.p2.y = _cairo_fixed_from_double (dy2) + p1->y;
  1074.  
  1075.         if (stroker->dash.dash_on &&
  1076.             (fully_in_bounds ||
  1077.              (! stroker->has_first_face && stroker->dash.dash_starts_on) ||
  1078.              _cairo_box_intersects_line_segment (&stroker->bounds, &segment)))
  1079.         {
  1080.             status = _cairo_stroker_add_sub_edge (stroker,
  1081.                                                   &segment.p1, &segment.p2,
  1082.                                                   &dev_slope,
  1083.                                                   slope_dx, slope_dy,
  1084.                                                   &sub_start, &sub_end);
  1085.             if (unlikely (status))
  1086.                 return status;
  1087.  
  1088.             if (stroker->has_current_face)
  1089.             {
  1090.                 /* Join with final face from previous segment */
  1091.                 status = _cairo_stroker_join (stroker,
  1092.                                               &stroker->current_face,
  1093.                                               &sub_start);
  1094.                 if (unlikely (status))
  1095.                     return status;
  1096.  
  1097.                 stroker->has_current_face = FALSE;
  1098.             }
  1099.             else if (! stroker->has_first_face &&
  1100.                        stroker->dash.dash_starts_on)
  1101.             {
  1102.                 /* Save sub path's first face in case needed for closing join */
  1103.                 stroker->first_face = sub_start;
  1104.                 stroker->has_first_face = TRUE;
  1105.             }
  1106.             else
  1107.             {
  1108.                 /* Cap dash start if not connecting to a previous segment */
  1109.                 status = _cairo_stroker_add_leading_cap (stroker, &sub_start);
  1110.                 if (unlikely (status))
  1111.                     return status;
  1112.             }
  1113.  
  1114.             if (remain) {
  1115.                 /* Cap dash end if not at end of segment */
  1116.                 status = _cairo_stroker_add_trailing_cap (stroker, &sub_end);
  1117.                 if (unlikely (status))
  1118.                     return status;
  1119.             } else {
  1120.                 stroker->current_face = sub_end;
  1121.                 stroker->has_current_face = TRUE;
  1122.             }
  1123.         } else {
  1124.             if (stroker->has_current_face) {
  1125.                 /* Cap final face from previous segment */
  1126.                 status = _cairo_stroker_add_trailing_cap (stroker,
  1127.                                                           &stroker->current_face);
  1128.                 if (unlikely (status))
  1129.                     return status;
  1130.  
  1131.                 stroker->has_current_face = FALSE;
  1132.             }
  1133.         }
  1134.  
  1135.         _cairo_stroker_dash_step (&stroker->dash, step_length);
  1136.         segment.p1 = segment.p2;
  1137.     }
  1138.  
  1139.     if (stroker->dash.dash_on && ! stroker->has_current_face) {
  1140.         /* This segment ends on a transition to dash_on, compute a new face
  1141.          * and add cap for the beginning of the next dash_on step.
  1142.          *
  1143.          * Note: this will create a degenerate cap if this is not the last line
  1144.          * in the path. Whether this behaviour is desirable or not is debatable.
  1145.          * On one side these degenerate caps can not be reproduced with regular
  1146.          * path stroking.
  1147.          * On the other hand, Acroread 7 also produces the degenerate caps.
  1148.          */
  1149.         _compute_face (p2, &dev_slope,
  1150.                        slope_dx, slope_dy,
  1151.                        stroker,
  1152.                        &stroker->current_face);
  1153.  
  1154.         status = _cairo_stroker_add_leading_cap (stroker,
  1155.                                                  &stroker->current_face);
  1156.         if (unlikely (status))
  1157.             return status;
  1158.  
  1159.         stroker->has_current_face = TRUE;
  1160.     }
  1161.  
  1162.     stroker->current_point = *p2;
  1163.  
  1164.     return CAIRO_STATUS_SUCCESS;
  1165. }
  1166.  
  1167. static cairo_status_t
  1168. _cairo_stroker_curve_to (void *closure,
  1169.                          const cairo_point_t *b,
  1170.                          const cairo_point_t *c,
  1171.                          const cairo_point_t *d)
  1172. {
  1173.     cairo_stroker_t *stroker = closure;
  1174.     cairo_spline_t spline;
  1175.     cairo_line_join_t line_join_save;
  1176.     cairo_stroke_face_t face;
  1177.     double slope_dx, slope_dy;
  1178.     cairo_path_fixed_line_to_func_t *line_to;
  1179.     cairo_status_t status = CAIRO_STATUS_SUCCESS;
  1180.  
  1181.     line_to = stroker->dash.dashed ?
  1182.         _cairo_stroker_line_to_dashed :
  1183.         _cairo_stroker_line_to;
  1184.  
  1185.     if (! _cairo_spline_init (&spline,
  1186.                               line_to, stroker,
  1187.                               &stroker->current_point, b, c, d))
  1188.     {
  1189.         return line_to (closure, d);
  1190.     }
  1191.  
  1192.     /* If the line width is so small that the pen is reduced to a
  1193.        single point, then we have nothing to do. */
  1194.     if (stroker->pen.num_vertices <= 1)
  1195.         return CAIRO_STATUS_SUCCESS;
  1196.  
  1197.     /* Compute the initial face */
  1198.     if (! stroker->dash.dashed || stroker->dash.dash_on) {
  1199.         slope_dx = _cairo_fixed_to_double (spline.initial_slope.dx);
  1200.         slope_dy = _cairo_fixed_to_double (spline.initial_slope.dy);
  1201.         if (_compute_normalized_device_slope (&slope_dx, &slope_dy,
  1202.                                               stroker->ctm_inverse, NULL))
  1203.         {
  1204.             _compute_face (&stroker->current_point,
  1205.                            &spline.initial_slope,
  1206.                            slope_dx, slope_dy,
  1207.                            stroker, &face);
  1208.         }
  1209.         if (stroker->has_current_face) {
  1210.             status = _cairo_stroker_join (stroker,
  1211.                                           &stroker->current_face, &face);
  1212.             if (unlikely (status))
  1213.                 return status;
  1214.         } else if (! stroker->has_first_face) {
  1215.             stroker->first_face = face;
  1216.             stroker->has_first_face = TRUE;
  1217.         }
  1218.  
  1219.         stroker->current_face = face;
  1220.         stroker->has_current_face = TRUE;
  1221.     }
  1222.  
  1223.     /* Temporarily modify the stroker to use round joins to guarantee
  1224.      * smooth stroked curves. */
  1225.     line_join_save = stroker->style.line_join;
  1226.     stroker->style.line_join = CAIRO_LINE_JOIN_ROUND;
  1227.  
  1228.     status = _cairo_spline_decompose (&spline, stroker->tolerance);
  1229.     if (unlikely (status))
  1230.         return status;
  1231.  
  1232.     /* And join the final face */
  1233.     if (! stroker->dash.dashed || stroker->dash.dash_on) {
  1234.         slope_dx = _cairo_fixed_to_double (spline.final_slope.dx);
  1235.         slope_dy = _cairo_fixed_to_double (spline.final_slope.dy);
  1236.         if (_compute_normalized_device_slope (&slope_dx, &slope_dy,
  1237.                                               stroker->ctm_inverse, NULL))
  1238.         {
  1239.             _compute_face (&stroker->current_point,
  1240.                            &spline.final_slope,
  1241.                            slope_dx, slope_dy,
  1242.                            stroker, &face);
  1243.         }
  1244.  
  1245.         status = _cairo_stroker_join (stroker, &stroker->current_face, &face);
  1246.         if (unlikely (status))
  1247.             return status;
  1248.  
  1249.         stroker->current_face = face;
  1250.     }
  1251.  
  1252.     stroker->style.line_join = line_join_save;
  1253.  
  1254.     return CAIRO_STATUS_SUCCESS;
  1255. }
  1256.  
  1257. static cairo_status_t
  1258. _cairo_stroker_close_path (void *closure)
  1259. {
  1260.     cairo_stroker_t *stroker = closure;
  1261.     cairo_status_t status;
  1262.  
  1263.     if (stroker->dash.dashed)
  1264.         status = _cairo_stroker_line_to_dashed (stroker, &stroker->first_point);
  1265.     else
  1266.         status = _cairo_stroker_line_to (stroker, &stroker->first_point);
  1267.     if (unlikely (status))
  1268.         return status;
  1269.  
  1270.     if (stroker->has_first_face && stroker->has_current_face) {
  1271.         /* Join first and final faces of sub path */
  1272.         status = _cairo_stroker_join (stroker,
  1273.                                       &stroker->current_face,
  1274.                                       &stroker->first_face);
  1275.         if (unlikely (status))
  1276.             return status;
  1277.     } else {
  1278.         /* Cap the start and end of the sub path as needed */
  1279.         status = _cairo_stroker_add_caps (stroker);
  1280.         if (unlikely (status))
  1281.             return status;
  1282.     }
  1283.  
  1284.     stroker->has_initial_sub_path = FALSE;
  1285.     stroker->has_first_face = FALSE;
  1286.     stroker->has_current_face = FALSE;
  1287.  
  1288.     return CAIRO_STATUS_SUCCESS;
  1289. }
  1290.  
  1291. cairo_status_t
  1292. _cairo_path_fixed_stroke_to_shaper (cairo_path_fixed_t  *path,
  1293.                                     const cairo_stroke_style_t  *stroke_style,
  1294.                                     const cairo_matrix_t        *ctm,
  1295.                                     const cairo_matrix_t        *ctm_inverse,
  1296.                                     double               tolerance,
  1297.                                     cairo_status_t (*add_triangle) (void *closure,
  1298.                                                                     const cairo_point_t triangle[3]),
  1299.                                     cairo_status_t (*add_triangle_fan) (void *closure,
  1300.                                                                         const cairo_point_t *midpt,
  1301.                                                                         const cairo_point_t *points,
  1302.                                                                         int npoints),
  1303.                                     cairo_status_t (*add_convex_quad) (void *closure,
  1304.                                                                        const cairo_point_t quad[4]),
  1305.                                     void *closure)
  1306. {
  1307.     cairo_stroker_t stroker;
  1308.     cairo_status_t status;
  1309.  
  1310.     status = _cairo_stroker_init (&stroker, stroke_style,
  1311.                                   ctm, ctm_inverse, tolerance);
  1312.     if (unlikely (status))
  1313.         return status;
  1314.  
  1315.     stroker.add_triangle = add_triangle;
  1316.     stroker.add_triangle_fan = add_triangle_fan;
  1317.     stroker.add_convex_quad = add_convex_quad;
  1318.     stroker.closure = closure;
  1319.  
  1320.     status = _cairo_path_fixed_interpret (path,
  1321.                                           CAIRO_DIRECTION_FORWARD,
  1322.                                           _cairo_stroker_move_to,
  1323.                                           stroker.dash.dashed ?
  1324.                                           _cairo_stroker_line_to_dashed :
  1325.                                           _cairo_stroker_line_to,
  1326.                                           _cairo_stroker_curve_to,
  1327.                                           _cairo_stroker_close_path,
  1328.                                           &stroker);
  1329.  
  1330.     if (unlikely (status))
  1331.         goto BAIL;
  1332.  
  1333.     /* Cap the start and end of the final sub path as needed */
  1334.     status = _cairo_stroker_add_caps (&stroker);
  1335.  
  1336. BAIL:
  1337.     _cairo_stroker_fini (&stroker);
  1338.  
  1339.     return status;
  1340. }
  1341.  
  1342. cairo_status_t
  1343. _cairo_path_fixed_stroke_to_polygon (const cairo_path_fixed_t   *path,
  1344.                                      const cairo_stroke_style_t *stroke_style,
  1345.                                      const cairo_matrix_t       *ctm,
  1346.                                      const cairo_matrix_t       *ctm_inverse,
  1347.                                      double              tolerance,
  1348.                                      cairo_polygon_t *polygon)
  1349. {
  1350.     cairo_stroker_t stroker;
  1351.     cairo_status_t status;
  1352.  
  1353.     status = _cairo_stroker_init (&stroker, stroke_style,
  1354.                                   ctm, ctm_inverse, tolerance);
  1355.     if (unlikely (status))
  1356.         return status;
  1357.  
  1358.     stroker.add_external_edge = _cairo_polygon_add_external_edge,
  1359.     stroker.closure = polygon;
  1360.  
  1361.     if (polygon->num_limits)
  1362.         _cairo_stroker_limit (&stroker, polygon->limits, polygon->num_limits);
  1363.  
  1364.     status = _cairo_path_fixed_interpret (path,
  1365.                                           CAIRO_DIRECTION_FORWARD,
  1366.                                           _cairo_stroker_move_to,
  1367.                                           stroker.dash.dashed ?
  1368.                                           _cairo_stroker_line_to_dashed :
  1369.                                           _cairo_stroker_line_to,
  1370.                                           _cairo_stroker_curve_to,
  1371.                                           _cairo_stroker_close_path,
  1372.                                           &stroker);
  1373.  
  1374.     if (unlikely (status))
  1375.         goto BAIL;
  1376.  
  1377.     /* Cap the start and end of the final sub path as needed */
  1378.     status = _cairo_stroker_add_caps (&stroker);
  1379.  
  1380. BAIL:
  1381.     _cairo_stroker_fini (&stroker);
  1382.  
  1383.     return status;
  1384. }
  1385.  
  1386. cairo_status_t
  1387. _cairo_path_fixed_stroke_to_traps (const cairo_path_fixed_t     *path,
  1388.                                    const cairo_stroke_style_t   *stroke_style,
  1389.                                    const cairo_matrix_t *ctm,
  1390.                                    const cairo_matrix_t *ctm_inverse,
  1391.                                    double                tolerance,
  1392.                                    cairo_traps_t        *traps)
  1393. {
  1394.     cairo_status_t status;
  1395.     cairo_polygon_t polygon;
  1396.  
  1397.     /* Before we do anything else, we attempt the rectilinear
  1398.      * stroker. It's careful to generate trapezoids that align to
  1399.      * device-pixel boundaries when possible. Many backends can render
  1400.      * those much faster than non-aligned trapezoids, (by using clip
  1401.      * regions, etc.) */
  1402.     if (path->is_rectilinear) {
  1403.         status = _cairo_path_fixed_stroke_rectilinear_to_traps (path,
  1404.                                                                 stroke_style,
  1405.                                                                 ctm,
  1406.                                                                 traps);
  1407.         if (status != CAIRO_INT_STATUS_UNSUPPORTED)
  1408.             return status;
  1409.     }
  1410.  
  1411.     _cairo_polygon_init (&polygon);
  1412.     if (traps->num_limits)
  1413.         _cairo_polygon_limit (&polygon, traps->limits, traps->num_limits);
  1414.  
  1415.     status = _cairo_path_fixed_stroke_to_polygon (path,
  1416.                                                   stroke_style,
  1417.                                                   ctm,
  1418.                                                   ctm_inverse,
  1419.                                                   tolerance,
  1420.                                                   &polygon);
  1421.     if (unlikely (status))
  1422.         goto BAIL;
  1423.  
  1424.     status = _cairo_polygon_status (&polygon);
  1425.     if (unlikely (status))
  1426.         goto BAIL;
  1427.  
  1428.     status = _cairo_bentley_ottmann_tessellate_polygon (traps, &polygon,
  1429.                                                         CAIRO_FILL_RULE_WINDING);
  1430.  
  1431. BAIL:
  1432.     _cairo_polygon_fini (&polygon);
  1433.  
  1434.     return status;
  1435. }
  1436.  
  1437. typedef struct _segment_t {
  1438.     cairo_point_t p1, p2;
  1439.     cairo_bool_t is_horizontal;
  1440.     cairo_bool_t has_join;
  1441. } segment_t;
  1442.  
  1443. typedef struct _cairo_rectilinear_stroker {
  1444.     const cairo_stroke_style_t *stroke_style;
  1445.     const cairo_matrix_t *ctm;
  1446.  
  1447.     cairo_fixed_t half_line_width;
  1448.     cairo_bool_t do_traps;
  1449.     void *container;
  1450.     cairo_point_t current_point;
  1451.     cairo_point_t first_point;
  1452.     cairo_bool_t open_sub_path;
  1453.  
  1454.     cairo_stroker_dash_t dash;
  1455.  
  1456.     cairo_bool_t has_bounds;
  1457.     cairo_box_t bounds;
  1458.  
  1459.     int num_segments;
  1460.     int segments_size;
  1461.     segment_t *segments;
  1462.     segment_t segments_embedded[8]; /* common case is a single rectangle */
  1463. } cairo_rectilinear_stroker_t;
  1464.  
  1465. static void
  1466. _cairo_rectilinear_stroker_limit (cairo_rectilinear_stroker_t *stroker,
  1467.                                   const cairo_box_t *boxes,
  1468.                                   int num_boxes)
  1469. {
  1470.     stroker->has_bounds = TRUE;
  1471.     _cairo_boxes_get_extents (boxes, num_boxes, &stroker->bounds);
  1472.  
  1473.     stroker->bounds.p1.x -= stroker->half_line_width;
  1474.     stroker->bounds.p2.x += stroker->half_line_width;
  1475.  
  1476.     stroker->bounds.p1.y -= stroker->half_line_width;
  1477.     stroker->bounds.p2.y += stroker->half_line_width;
  1478. }
  1479.  
  1480. static cairo_bool_t
  1481. _cairo_rectilinear_stroker_init (cairo_rectilinear_stroker_t    *stroker,
  1482.                                  const cairo_stroke_style_t     *stroke_style,
  1483.                                  const cairo_matrix_t           *ctm,
  1484.                                  cairo_bool_t                    do_traps,
  1485.                                  void                           *container)
  1486. {
  1487.     /* This special-case rectilinear stroker only supports
  1488.      * miter-joined lines (not curves) and a translation-only matrix
  1489.      * (though it could probably be extended to support a matrix with
  1490.      * uniform, integer scaling).
  1491.      *
  1492.      * It also only supports horizontal and vertical line_to
  1493.      * elements. But we don't catch that here, but instead return
  1494.      * UNSUPPORTED from _cairo_rectilinear_stroker_line_to if any
  1495.      * non-rectilinear line_to is encountered.
  1496.      */
  1497.     if (stroke_style->line_join != CAIRO_LINE_JOIN_MITER)
  1498.         return FALSE;
  1499.  
  1500.     /* If the miter limit turns right angles into bevels, then we
  1501.      * can't use this optimization. Remember, the ratio is
  1502.      * 1/sin(ɸ/2). So the cutoff is 1/sin(π/4.0) or ⎷2,
  1503.      * which we round for safety. */
  1504.     if (stroke_style->miter_limit < M_SQRT2)
  1505.         return FALSE;
  1506.  
  1507.     if (! (stroke_style->line_cap == CAIRO_LINE_CAP_BUTT ||
  1508.            stroke_style->line_cap == CAIRO_LINE_CAP_SQUARE))
  1509.     {
  1510.         return FALSE;
  1511.     }
  1512.  
  1513.     if (! _cairo_matrix_has_unity_scale (ctm))
  1514.         return FALSE;
  1515.  
  1516.     stroker->stroke_style = stroke_style;
  1517.     stroker->ctm = ctm;
  1518.  
  1519.     stroker->half_line_width =
  1520.         _cairo_fixed_from_double (stroke_style->line_width / 2.0);
  1521.     stroker->open_sub_path = FALSE;
  1522.     stroker->segments = stroker->segments_embedded;
  1523.     stroker->segments_size = ARRAY_LENGTH (stroker->segments_embedded);
  1524.     stroker->num_segments = 0;
  1525.  
  1526.     _cairo_stroker_dash_init (&stroker->dash, stroke_style);
  1527.  
  1528.     stroker->has_bounds = FALSE;
  1529.  
  1530.     stroker->do_traps = do_traps;
  1531.     stroker->container = container;
  1532.  
  1533.     return TRUE;
  1534. }
  1535.  
  1536. static void
  1537. _cairo_rectilinear_stroker_fini (cairo_rectilinear_stroker_t    *stroker)
  1538. {
  1539.     if (stroker->segments != stroker->segments_embedded)
  1540.         free (stroker->segments);
  1541. }
  1542.  
  1543. static cairo_status_t
  1544. _cairo_rectilinear_stroker_add_segment (cairo_rectilinear_stroker_t *stroker,
  1545.                                         const cairo_point_t     *p1,
  1546.                                         const cairo_point_t     *p2,
  1547.                                         cairo_bool_t             is_horizontal,
  1548.                                         cairo_bool_t             has_join)
  1549. {
  1550.     if (CAIRO_INJECT_FAULT ())
  1551.         return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  1552.  
  1553.     if (stroker->num_segments == stroker->segments_size) {
  1554.         int new_size = stroker->segments_size * 2;
  1555.         segment_t *new_segments;
  1556.  
  1557.         if (stroker->segments == stroker->segments_embedded) {
  1558.             new_segments = _cairo_malloc_ab (new_size, sizeof (segment_t));
  1559.             if (unlikely (new_segments == NULL))
  1560.                 return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  1561.  
  1562.             memcpy (new_segments, stroker->segments,
  1563.                     stroker->num_segments * sizeof (segment_t));
  1564.         } else {
  1565.             new_segments = _cairo_realloc_ab (stroker->segments,
  1566.                                               new_size, sizeof (segment_t));
  1567.             if (unlikely (new_segments == NULL))
  1568.                 return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  1569.         }
  1570.  
  1571.         stroker->segments_size = new_size;
  1572.         stroker->segments = new_segments;
  1573.     }
  1574.  
  1575.     stroker->segments[stroker->num_segments].p1 = *p1;
  1576.     stroker->segments[stroker->num_segments].p2 = *p2;
  1577.     stroker->segments[stroker->num_segments].has_join = has_join;
  1578.     stroker->segments[stroker->num_segments].is_horizontal = is_horizontal;
  1579.     stroker->num_segments++;
  1580.  
  1581.     return CAIRO_STATUS_SUCCESS;
  1582. }
  1583.  
  1584. static cairo_status_t
  1585. _cairo_rectilinear_stroker_emit_segments (cairo_rectilinear_stroker_t *stroker)
  1586. {
  1587.     cairo_status_t status;
  1588.     cairo_line_cap_t line_cap = stroker->stroke_style->line_cap;
  1589.     cairo_fixed_t half_line_width = stroker->half_line_width;
  1590.     int i;
  1591.  
  1592.     for (i = 0; i < stroker->num_segments; i++) {
  1593.         cairo_point_t *a, *b;
  1594.         cairo_bool_t lengthen_initial, shorten_final, lengthen_final;
  1595.  
  1596.         a = &stroker->segments[i].p1;
  1597.         b = &stroker->segments[i].p2;
  1598.  
  1599.         /* For each segment we generate a single rectangular
  1600.          * trapezoid. This rectangle is based on a perpendicular
  1601.          * extension (by half the line width) of the segment endpoints
  1602.          * after some adjustments of the endpoints to account for caps
  1603.          * and joins.
  1604.          */
  1605.  
  1606.         /* We adjust the initial point of the segment to extend the
  1607.          * rectangle to include the previous cap or join, (this
  1608.          * adjustment applies to all segments except for the first
  1609.          * segment of open, butt-capped paths).
  1610.          */
  1611.         lengthen_initial = TRUE;
  1612.         if (i == 0 && stroker->open_sub_path && line_cap == CAIRO_LINE_CAP_BUTT)
  1613.             lengthen_initial = FALSE;
  1614.  
  1615.         /* The adjustment of the final point is trickier. For all but
  1616.          * the last segment we shorten the segment at the final
  1617.          * endpoint to not overlap with the subsequent join. For the
  1618.          * last segment we do the same shortening if the path is
  1619.          * closed. If the path is open and butt-capped we do no
  1620.          * adjustment, while if it's open and square-capped we do a
  1621.          * lengthening adjustment instead to include the cap.
  1622.          */
  1623.         shorten_final = TRUE;
  1624.         lengthen_final = FALSE;
  1625.         if (i == stroker->num_segments - 1 && stroker->open_sub_path) {
  1626.             shorten_final = FALSE;
  1627.             if (line_cap == CAIRO_LINE_CAP_SQUARE)
  1628.                 lengthen_final = TRUE;
  1629.         }
  1630.  
  1631.         /* Perform the adjustments of the endpoints. */
  1632.         if (a->y == b->y) {
  1633.             if (a->x < b->x) {
  1634.                 if (lengthen_initial)
  1635.                     a->x -= half_line_width;
  1636.                 if (shorten_final)
  1637.                     b->x -= half_line_width;
  1638.                 else if (lengthen_final)
  1639.                     b->x += half_line_width;
  1640.             } else {
  1641.                 if (lengthen_initial)
  1642.                     a->x += half_line_width;
  1643.                 if (shorten_final)
  1644.                     b->x += half_line_width;
  1645.                 else if (lengthen_final)
  1646.                     b->x -= half_line_width;
  1647.             }
  1648.  
  1649.             if (a->x > b->x) {
  1650.                 cairo_point_t *t;
  1651.  
  1652.                 t = a;
  1653.                 a = b;
  1654.                 b = t;
  1655.             }
  1656.         } else {
  1657.             if (a->y < b->y) {
  1658.                 if (lengthen_initial)
  1659.                     a->y -= half_line_width;
  1660.                 if (shorten_final)
  1661.                     b->y -= half_line_width;
  1662.                 else if (lengthen_final)
  1663.                     b->y += half_line_width;
  1664.             } else {
  1665.                 if (lengthen_initial)
  1666.                     a->y += half_line_width;
  1667.                 if (shorten_final)
  1668.                     b->y += half_line_width;
  1669.                 else if (lengthen_final)
  1670.                     b->y -= half_line_width;
  1671.             }
  1672.  
  1673.             if (a->y > b->y) {
  1674.                 cairo_point_t *t;
  1675.  
  1676.                 t = a;
  1677.                 a = b;
  1678.                 b = t;
  1679.             }
  1680.         }
  1681.  
  1682.         /* Form the rectangle by expanding by half the line width in
  1683.          * either perpendicular direction. */
  1684.         if (a->y == b->y) {
  1685.             a->y -= half_line_width;
  1686.             b->y += half_line_width;
  1687.         } else {
  1688.             a->x -= half_line_width;
  1689.             b->x += half_line_width;
  1690.         }
  1691.  
  1692.         if (stroker->do_traps) {
  1693.             status = _cairo_traps_tessellate_rectangle (stroker->container, a, b);
  1694.         } else {
  1695.             cairo_box_t box;
  1696.  
  1697.             box.p1 = *a;
  1698.             box.p2 = *b;
  1699.  
  1700.             status = _cairo_boxes_add (stroker->container, &box);
  1701.         }
  1702.         if (unlikely (status))
  1703.             return status;
  1704.     }
  1705.  
  1706.     stroker->num_segments = 0;
  1707.  
  1708.     return CAIRO_STATUS_SUCCESS;
  1709. }
  1710.  
  1711. static cairo_status_t
  1712. _cairo_rectilinear_stroker_emit_segments_dashed (cairo_rectilinear_stroker_t *stroker)
  1713. {
  1714.     cairo_status_t status;
  1715.     cairo_line_cap_t line_cap = stroker->stroke_style->line_cap;
  1716.     cairo_fixed_t half_line_width = stroker->half_line_width;
  1717.     int i;
  1718.  
  1719.     for (i = 0; i < stroker->num_segments; i++) {
  1720.         cairo_point_t *a, *b;
  1721.         cairo_bool_t is_horizontal;
  1722.  
  1723.         a = &stroker->segments[i].p1;
  1724.         b = &stroker->segments[i].p2;
  1725.  
  1726.         is_horizontal = stroker->segments[i].is_horizontal;
  1727.  
  1728.         /* Handle the joins for a potentially degenerate segment. */
  1729.         if (line_cap == CAIRO_LINE_CAP_BUTT &&
  1730.             stroker->segments[i].has_join &&
  1731.             (i != stroker->num_segments - 1 ||
  1732.              (! stroker->open_sub_path && stroker->dash.dash_starts_on)))
  1733.         {
  1734.             cairo_point_t p1 = stroker->segments[i].p1;
  1735.             cairo_point_t p2 = stroker->segments[i].p2;
  1736.             cairo_slope_t out_slope;
  1737.             int j = (i + 1) % stroker->num_segments;
  1738.  
  1739.             _cairo_slope_init (&out_slope,
  1740.                                &stroker->segments[j].p1,
  1741.                                &stroker->segments[j].p2);
  1742.  
  1743.             if (is_horizontal) {
  1744.                 if (p1.x <= p2.x) {
  1745.                     p1.x = p2.x;
  1746.                     p2.x += half_line_width;
  1747.                 } else {
  1748.                     p1.x = p2.x - half_line_width;
  1749.                 }
  1750.                 if (out_slope.dy >= 0)
  1751.                     p1.y -= half_line_width;
  1752.                 if (out_slope.dy <= 0)
  1753.                     p2.y += half_line_width;
  1754.             } else {
  1755.                 if (p1.y <= p2.y) {
  1756.                     p1.y = p2.y;
  1757.                     p2.y += half_line_width;
  1758.                 } else {
  1759.                     p1.y = p2.y - half_line_width;
  1760.                 }
  1761.                 if (out_slope.dx >= 0)
  1762.                     p1.x -= half_line_width;
  1763.                 if (out_slope.dx <= 0)
  1764.                     p2.x += half_line_width;
  1765.             }
  1766.  
  1767.             if (stroker->do_traps) {
  1768.                 status = _cairo_traps_tessellate_rectangle (stroker->container, &p1, &p2);
  1769.             } else {
  1770.                 cairo_box_t box;
  1771.  
  1772.                 box.p1 = p1;
  1773.                 box.p2 = p2;
  1774.  
  1775.                 status = _cairo_boxes_add (stroker->container, &box);
  1776.             }
  1777.             if (unlikely (status))
  1778.                 return status;
  1779.         }
  1780.  
  1781.         /* Perform the adjustments of the endpoints. */
  1782.         if (is_horizontal) {
  1783.             if (line_cap == CAIRO_LINE_CAP_SQUARE) {
  1784.                 if (a->x <= b->x) {
  1785.                     a->x -= half_line_width;
  1786.                     b->x += half_line_width;
  1787.                 } else {
  1788.                     a->x += half_line_width;
  1789.                     b->x -= half_line_width;
  1790.                 }
  1791.             }
  1792.  
  1793.             if (a->x > b->x) {
  1794.                 cairo_point_t *t;
  1795.  
  1796.                 t = a;
  1797.                 a = b;
  1798.                 b = t;
  1799.             }
  1800.  
  1801.             a->y -= half_line_width;
  1802.             b->y += half_line_width;
  1803.         } else {
  1804.             if (line_cap == CAIRO_LINE_CAP_SQUARE) {
  1805.                 if (a->y <= b->y) {
  1806.                     a->y -= half_line_width;
  1807.                     b->y += half_line_width;
  1808.                 } else {
  1809.                     a->y += half_line_width;
  1810.                     b->y -= half_line_width;
  1811.                 }
  1812.             }
  1813.  
  1814.             if (a->y > b->y) {
  1815.                 cairo_point_t *t;
  1816.  
  1817.                 t = a;
  1818.                 a = b;
  1819.                 b = t;
  1820.             }
  1821.  
  1822.             a->x -= half_line_width;
  1823.             b->x += half_line_width;
  1824.         }
  1825.  
  1826.         if (a->x == b->x && a->y == b->y)
  1827.             continue;
  1828.  
  1829.         if (stroker->do_traps) {
  1830.             status = _cairo_traps_tessellate_rectangle (stroker->container, a, b);
  1831.         } else {
  1832.             cairo_box_t box;
  1833.  
  1834.             box.p1 = *a;
  1835.             box.p2 = *b;
  1836.  
  1837.             status = _cairo_boxes_add (stroker->container, &box);
  1838.         }
  1839.         if (unlikely (status))
  1840.             return status;
  1841.     }
  1842.  
  1843.     stroker->num_segments = 0;
  1844.  
  1845.     return CAIRO_STATUS_SUCCESS;
  1846. }
  1847.  
  1848. static cairo_status_t
  1849. _cairo_rectilinear_stroker_move_to (void                *closure,
  1850.                                     const cairo_point_t *point)
  1851. {
  1852.     cairo_rectilinear_stroker_t *stroker = closure;
  1853.     cairo_status_t status;
  1854.  
  1855.     if (stroker->dash.dashed)
  1856.         status = _cairo_rectilinear_stroker_emit_segments_dashed (stroker);
  1857.     else
  1858.         status = _cairo_rectilinear_stroker_emit_segments (stroker);
  1859.     if (unlikely (status))
  1860.         return status;
  1861.  
  1862.     /* reset the dash pattern for new sub paths */
  1863.     _cairo_stroker_dash_start (&stroker->dash);
  1864.  
  1865.     stroker->current_point = *point;
  1866.     stroker->first_point = *point;
  1867.  
  1868.     return CAIRO_STATUS_SUCCESS;
  1869. }
  1870.  
  1871. static cairo_status_t
  1872. _cairo_rectilinear_stroker_line_to (void                *closure,
  1873.                                     const cairo_point_t *b)
  1874. {
  1875.     cairo_rectilinear_stroker_t *stroker = closure;
  1876.     cairo_point_t *a = &stroker->current_point;
  1877.     cairo_status_t status;
  1878.  
  1879.     /* We only support horizontal or vertical elements. */
  1880.     assert (a->x == b->x || a->y == b->y);
  1881.  
  1882.     /* We don't draw anything for degenerate paths. */
  1883.     if (a->x == b->x && a->y == b->y)
  1884.         return CAIRO_STATUS_SUCCESS;
  1885.  
  1886.     status = _cairo_rectilinear_stroker_add_segment (stroker, a, b,
  1887.                                                      a->y == b->y,
  1888.                                                      TRUE);
  1889.  
  1890.     stroker->current_point = *b;
  1891.     stroker->open_sub_path = TRUE;
  1892.  
  1893.     return status;
  1894. }
  1895.  
  1896. static cairo_status_t
  1897. _cairo_rectilinear_stroker_line_to_dashed (void         *closure,
  1898.                                            const cairo_point_t  *point)
  1899. {
  1900.     cairo_rectilinear_stroker_t *stroker = closure;
  1901.     const cairo_point_t *a = &stroker->current_point;
  1902.     const cairo_point_t *b = point;
  1903.     cairo_bool_t fully_in_bounds;
  1904.     double sign, remain;
  1905.     cairo_fixed_t mag;
  1906.     cairo_status_t status;
  1907.     cairo_line_t segment;
  1908.     cairo_bool_t dash_on = FALSE;
  1909.     cairo_bool_t is_horizontal;
  1910.  
  1911.     /* We don't draw anything for degenerate paths. */
  1912.     if (a->x == b->x && a->y == b->y)
  1913.         return CAIRO_STATUS_SUCCESS;
  1914.  
  1915.     /* We only support horizontal or vertical elements. */
  1916.     assert (a->x == b->x || a->y == b->y);
  1917.  
  1918.     fully_in_bounds = TRUE;
  1919.     if (stroker->has_bounds &&
  1920.         (! _cairo_box_contains_point (&stroker->bounds, a) ||
  1921.          ! _cairo_box_contains_point (&stroker->bounds, b)))
  1922.     {
  1923.         fully_in_bounds = FALSE;
  1924.     }
  1925.  
  1926.     is_horizontal = a->y == b->y;
  1927.     if (is_horizontal)
  1928.         mag = b->x - a->x;
  1929.     else
  1930.         mag = b->y - a->y;
  1931.     if (mag < 0) {
  1932.         remain = _cairo_fixed_to_double (-mag);
  1933.         sign = 1.;
  1934.     } else {
  1935.         remain = _cairo_fixed_to_double (mag);
  1936.         sign = -1.;
  1937.     }
  1938.  
  1939.     segment.p2 = segment.p1 = *a;
  1940.     while (remain > 0.) {
  1941.         double step_length;
  1942.  
  1943.         step_length = MIN (stroker->dash.dash_remain, remain);
  1944.         remain -= step_length;
  1945.  
  1946.         mag = _cairo_fixed_from_double (sign*remain);
  1947.         if (is_horizontal)
  1948.             segment.p2.x = b->x + mag;
  1949.         else
  1950.             segment.p2.y = b->y + mag;
  1951.  
  1952.         if (stroker->dash.dash_on &&
  1953.             (fully_in_bounds ||
  1954.              _cairo_box_intersects_line_segment (&stroker->bounds, &segment)))
  1955.         {
  1956.             status = _cairo_rectilinear_stroker_add_segment (stroker,
  1957.                                                              &segment.p1,
  1958.                                                              &segment.p2,
  1959.                                                              is_horizontal,
  1960.                                                              remain <= 0.);
  1961.             if (unlikely (status))
  1962.                 return status;
  1963.  
  1964.             dash_on = TRUE;
  1965.         }
  1966.         else
  1967.         {
  1968.             dash_on = FALSE;
  1969.         }
  1970.  
  1971.         _cairo_stroker_dash_step (&stroker->dash, step_length);
  1972.         segment.p1 = segment.p2;
  1973.     }
  1974.  
  1975.     if (stroker->dash.dash_on && ! dash_on &&
  1976.         (fully_in_bounds ||
  1977.          _cairo_box_intersects_line_segment (&stroker->bounds, &segment)))
  1978.     {
  1979.  
  1980.         /* This segment ends on a transition to dash_on, compute a new face
  1981.          * and add cap for the beginning of the next dash_on step.
  1982.          */
  1983.  
  1984.         status = _cairo_rectilinear_stroker_add_segment (stroker,
  1985.                                                          &segment.p1,
  1986.                                                          &segment.p1,
  1987.                                                          is_horizontal,
  1988.                                                          TRUE);
  1989.         if (unlikely (status))
  1990.             return status;
  1991.     }
  1992.  
  1993.     stroker->current_point = *point;
  1994.     stroker->open_sub_path = TRUE;
  1995.  
  1996.     return CAIRO_STATUS_SUCCESS;
  1997. }
  1998.  
  1999. static cairo_status_t
  2000. _cairo_rectilinear_stroker_close_path (void *closure)
  2001. {
  2002.     cairo_rectilinear_stroker_t *stroker = closure;
  2003.     cairo_status_t status;
  2004.  
  2005.     /* We don't draw anything for degenerate paths. */
  2006.     if (! stroker->open_sub_path)
  2007.         return CAIRO_STATUS_SUCCESS;
  2008.  
  2009.     if (stroker->dash.dashed) {
  2010.         status = _cairo_rectilinear_stroker_line_to_dashed (stroker,
  2011.                                                             &stroker->first_point);
  2012.     } else {
  2013.         status = _cairo_rectilinear_stroker_line_to (stroker,
  2014.                                                      &stroker->first_point);
  2015.     }
  2016.     if (unlikely (status))
  2017.         return status;
  2018.  
  2019.     stroker->open_sub_path = FALSE;
  2020.  
  2021.     if (stroker->dash.dashed)
  2022.         status = _cairo_rectilinear_stroker_emit_segments_dashed (stroker);
  2023.     else
  2024.         status = _cairo_rectilinear_stroker_emit_segments (stroker);
  2025.     if (unlikely (status))
  2026.         return status;
  2027.  
  2028.     return CAIRO_STATUS_SUCCESS;
  2029. }
  2030.  
  2031. cairo_int_status_t
  2032. _cairo_path_fixed_stroke_rectilinear_to_traps (const cairo_path_fixed_t *path,
  2033.                                                const cairo_stroke_style_t       *stroke_style,
  2034.                                                const cairo_matrix_t     *ctm,
  2035.                                                cairo_traps_t            *traps)
  2036. {
  2037.     cairo_rectilinear_stroker_t rectilinear_stroker;
  2038.     cairo_int_status_t status;
  2039.  
  2040.     assert (path->is_rectilinear);
  2041.  
  2042.     if (! _cairo_rectilinear_stroker_init (&rectilinear_stroker,
  2043.                                            stroke_style, ctm,
  2044.                                            TRUE, traps))
  2045.     {
  2046.         return CAIRO_INT_STATUS_UNSUPPORTED;
  2047.     }
  2048.  
  2049.     if (traps->num_limits) {
  2050.         _cairo_rectilinear_stroker_limit (&rectilinear_stroker,
  2051.                                           traps->limits,
  2052.                                           traps->num_limits);
  2053.     }
  2054.  
  2055.     status = _cairo_path_fixed_interpret (path,
  2056.                                           CAIRO_DIRECTION_FORWARD,
  2057.                                           _cairo_rectilinear_stroker_move_to,
  2058.                                           rectilinear_stroker.dash.dashed ?
  2059.                                           _cairo_rectilinear_stroker_line_to_dashed :
  2060.                                           _cairo_rectilinear_stroker_line_to,
  2061.                                           NULL,
  2062.                                           _cairo_rectilinear_stroker_close_path,
  2063.                                           &rectilinear_stroker);
  2064.     if (unlikely (status))
  2065.         goto BAIL;
  2066.  
  2067.     if (rectilinear_stroker.dash.dashed)
  2068.         status = _cairo_rectilinear_stroker_emit_segments_dashed (&rectilinear_stroker);
  2069.     else
  2070.         status = _cairo_rectilinear_stroker_emit_segments (&rectilinear_stroker);
  2071.  
  2072.     traps->is_rectilinear = 1;
  2073.     traps->is_rectangular = 1;
  2074.     /* As we incrementally tessellate, we do not eliminate self-intersections */
  2075.     traps->has_intersections = traps->num_traps > 1;
  2076. BAIL:
  2077.     _cairo_rectilinear_stroker_fini (&rectilinear_stroker);
  2078.  
  2079.     if (unlikely (status))
  2080.         _cairo_traps_clear (traps);
  2081.  
  2082.     return status;
  2083. }
  2084.  
  2085. cairo_int_status_t
  2086. _cairo_path_fixed_stroke_rectilinear_to_boxes (const cairo_path_fixed_t *path,
  2087.                                                const cairo_stroke_style_t       *stroke_style,
  2088.                                                const cairo_matrix_t     *ctm,
  2089.                                                cairo_boxes_t            *boxes)
  2090. {
  2091.     cairo_rectilinear_stroker_t rectilinear_stroker;
  2092.     cairo_int_status_t status;
  2093.  
  2094.     assert (path->is_rectilinear);
  2095.  
  2096.     if (! _cairo_rectilinear_stroker_init (&rectilinear_stroker,
  2097.                                            stroke_style, ctm,
  2098.                                            FALSE, boxes))
  2099.     {
  2100.         return CAIRO_INT_STATUS_UNSUPPORTED;
  2101.     }
  2102.  
  2103.     if (boxes->num_limits) {
  2104.         _cairo_rectilinear_stroker_limit (&rectilinear_stroker,
  2105.                                           boxes->limits,
  2106.                                           boxes->num_limits);
  2107.     }
  2108.  
  2109.     status = _cairo_path_fixed_interpret (path,
  2110.                                           CAIRO_DIRECTION_FORWARD,
  2111.                                           _cairo_rectilinear_stroker_move_to,
  2112.                                           rectilinear_stroker.dash.dashed ?
  2113.                                           _cairo_rectilinear_stroker_line_to_dashed :
  2114.                                           _cairo_rectilinear_stroker_line_to,
  2115.                                           NULL,
  2116.                                           _cairo_rectilinear_stroker_close_path,
  2117.                                           &rectilinear_stroker);
  2118.     if (unlikely (status))
  2119.         goto BAIL;
  2120.  
  2121.     if (rectilinear_stroker.dash.dashed)
  2122.         status = _cairo_rectilinear_stroker_emit_segments_dashed (&rectilinear_stroker);
  2123.     else
  2124.         status = _cairo_rectilinear_stroker_emit_segments (&rectilinear_stroker);
  2125.     if (unlikely (status))
  2126.         goto BAIL;
  2127.  
  2128.     /* As we incrementally tessellate, we do not eliminate self-intersections */
  2129.     status = _cairo_bentley_ottmann_tessellate_boxes (boxes,
  2130.                                                       CAIRO_FILL_RULE_WINDING,
  2131.                                                       boxes);
  2132.     if (unlikely (status))
  2133.         goto BAIL;
  2134.  
  2135.     _cairo_rectilinear_stroker_fini (&rectilinear_stroker);
  2136.  
  2137.     return CAIRO_STATUS_SUCCESS;
  2138.  
  2139. BAIL:
  2140.     _cairo_rectilinear_stroker_fini (&rectilinear_stroker);
  2141.     _cairo_boxes_clear (boxes);
  2142.     return status;
  2143. }
  2144.