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
4 * Copyright © 2002 University of Southern California
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.
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
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/
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.
29 * The Original Code is the cairo graphics library.
31 * The Initial Developer of the Original Code is University of Southern
35 * Carl D. Worth <cworth@cworth.org>
36 * Chris Wilson <chris@chris-wilson.co.uk>
39 #define _BSD_SOURCE /* for hypot() */
42 #include "cairo-box-inline.h"
43 #include "cairo-boxes-private.h"
44 #include "cairo-error-private.h"
45 #include "cairo-path-fixed-private.h"
46 #include "cairo-slope-private.h"
47 #include "cairo-stroke-dash-private.h"
48 #include "cairo-traps-private.h"
50 typedef struct cairo_stroker {
51 cairo_stroke_style_t style;
53 const cairo_matrix_t *ctm;
54 const cairo_matrix_t *ctm_inverse;
55 double half_line_width;
57 double spline_cusp_tolerance;
58 double ctm_determinant;
59 cairo_bool_t ctm_det_positive;
62 cairo_status_t (*add_external_edge) (void *closure,
63 const cairo_point_t *p1,
64 const cairo_point_t *p2);
65 cairo_status_t (*add_triangle) (void *closure,
66 const cairo_point_t triangle[3]);
67 cairo_status_t (*add_triangle_fan) (void *closure,
68 const cairo_point_t *midpt,
69 const cairo_point_t *points,
71 cairo_status_t (*add_convex_quad) (void *closure,
72 const cairo_point_t quad[4]);
76 cairo_point_t current_point;
77 cairo_point_t first_point;
79 cairo_bool_t has_initial_sub_path;
81 cairo_bool_t has_current_face;
82 cairo_stroke_face_t current_face;
84 cairo_bool_t has_first_face;
85 cairo_stroke_face_t first_face;
87 cairo_stroker_dash_t dash;
89 cairo_bool_t has_bounds;
94 # to avoid warning : defined but not used [-Wunused-function]
96 _cairo_stroke_segment_intersect (cairo_point_t *p1, cairo_point_t *p2,
97 cairo_point_t *p3, cairo_point_t *p4,
100 double x1, y1, x2, y2, x3, y3, x4, y4;
104 x1 = _cairo_fixed_to_double (p1->x);
105 y1 = _cairo_fixed_to_double (p1->y);
106 x2 = _cairo_fixed_to_double (p2->x);
107 y2 = _cairo_fixed_to_double (p2->y);
108 x3 = _cairo_fixed_to_double (p3->x);
109 y3 = _cairo_fixed_to_double (p3->y);
110 x4 = _cairo_fixed_to_double (p4->x);
111 y4 = _cairo_fixed_to_double (p4->y);
113 d = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);
117 pre = x1 * y2 - y1 * x2;
118 post = x3 * y4 - y3 * x4;
119 x = (pre * (x3 - x4) - (x1 - x2) * post) / d;
120 y = (pre * (y3 - y4) - (y1 - y2) * post) / d;
122 // check if x, y are within both segments
123 if (x < MIN (x1, x2) || x > MAX (x1, x2) ||
124 x < MIN (x3, x4) || x > MAX (x3, x4))
126 if (y < MIN (y1, y2) || y > MAX (y1, y2) ||
127 y < MIN (y1, y2) || y > MAX (y3, y4))
130 p->x = _cairo_fixed_from_double (x);
131 p->y = _cairo_fixed_from_double (y);
137 _cairo_stroker_limit (cairo_stroker_t *stroker,
138 const cairo_path_fixed_t *path,
139 const cairo_box_t *boxes,
143 cairo_fixed_t fdx, fdy;
145 stroker->has_bounds = TRUE;
146 _cairo_boxes_get_extents (boxes, num_boxes, &stroker->bounds);
148 /* Extend the bounds in each direction to account for the maximum area
149 * we might generate trapezoids, to capture line segments that are outside
150 * of the bounds but which might generate rendering that's within bounds.
153 _cairo_stroke_style_max_distance_from_path (&stroker->style, path,
154 stroker->ctm, &dx, &dy);
156 fdx = _cairo_fixed_from_double (dx);
157 fdy = _cairo_fixed_from_double (dy);
159 stroker->bounds.p1.x -= fdx;
160 stroker->bounds.p2.x += fdx;
162 stroker->bounds.p1.y -= fdy;
163 stroker->bounds.p2.y += fdy;
166 static cairo_status_t
167 _cairo_stroker_init (cairo_stroker_t *stroker,
168 const cairo_path_fixed_t *path,
169 const cairo_stroke_style_t *stroke_style,
170 const cairo_matrix_t *ctm,
171 const cairo_matrix_t *ctm_inverse,
173 const cairo_box_t *limits,
176 cairo_status_t status;
178 stroker->style = *stroke_style;
180 stroker->ctm_inverse = ctm_inverse;
181 stroker->tolerance = tolerance;
182 stroker->half_line_width = stroke_style->line_width / 2.0;
184 /* To test whether we need to join two segments of a spline using
185 * a round-join or a bevel-join, we can inspect the angle between the
186 * two segments. If the difference between the chord distance
187 * (half-line-width times the cosine of the bisection angle) and the
188 * half-line-width itself is greater than tolerance then we need to
191 stroker->spline_cusp_tolerance = 1 - tolerance / stroker->half_line_width;
192 stroker->spline_cusp_tolerance *= stroker->spline_cusp_tolerance;
193 stroker->spline_cusp_tolerance *= 2;
194 stroker->spline_cusp_tolerance -= 1;
196 stroker->ctm_determinant = _cairo_matrix_compute_determinant (stroker->ctm);
197 stroker->ctm_det_positive = stroker->ctm_determinant >= 0.0;
199 status = _cairo_pen_init (&stroker->pen,
200 stroker->half_line_width, tolerance, ctm);
201 if (unlikely (status))
204 stroker->has_current_face = FALSE;
205 stroker->has_first_face = FALSE;
206 stroker->has_initial_sub_path = FALSE;
208 _cairo_stroker_dash_init (&stroker->dash, stroke_style);
210 stroker->add_external_edge = NULL;
212 stroker->has_bounds = FALSE;
214 _cairo_stroker_limit (stroker, path, limits, num_limits);
216 return CAIRO_STATUS_SUCCESS;
220 _cairo_stroker_fini (cairo_stroker_t *stroker)
222 _cairo_pen_fini (&stroker->pen);
226 _translate_point (cairo_point_t *point, const cairo_point_t *offset)
228 point->x += offset->x;
229 point->y += offset->y;
233 _cairo_stroker_join_is_clockwise (const cairo_stroke_face_t *in,
234 const cairo_stroke_face_t *out)
236 cairo_slope_t in_slope, out_slope;
238 _cairo_slope_init (&in_slope, &in->point, &in->cw);
239 _cairo_slope_init (&out_slope, &out->point, &out->cw);
241 return _cairo_slope_compare (&in_slope, &out_slope) < 0;
245 * _cairo_slope_compare_sgn:
247 * Return -1, 0 or 1 depending on the relative slopes of
251 _cairo_slope_compare_sgn (double dx1, double dy1, double dx2, double dy2)
253 double c = (dx1 * dy2 - dx2 * dy1);
256 if (c < 0) return -1;
261 _range_step (int i, int step, int max)
272 * Construct a fan around the midpoint using the vertices from pen between
275 static cairo_status_t
276 _tessellate_fan (cairo_stroker_t *stroker,
277 const cairo_slope_t *in_vector,
278 const cairo_slope_t *out_vector,
279 const cairo_point_t *midpt,
280 const cairo_point_t *inpt,
281 const cairo_point_t *outpt,
282 cairo_bool_t clockwise)
284 cairo_point_t stack_points[64], *points = stack_points;
285 cairo_pen_t *pen = &stroker->pen;
286 int start, stop, num_points = 0;
287 cairo_status_t status = CAIRO_STATUS_SUCCESS;
289 if (stroker->has_bounds &&
290 ! _cairo_box_contains_point (&stroker->bounds, midpt))
293 assert (stroker->pen.num_vertices);
296 _cairo_pen_find_active_ccw_vertices (pen,
297 in_vector, out_vector,
299 if (stroker->add_external_edge) {
302 while (start != stop) {
303 cairo_point_t p = *midpt;
304 _translate_point (&p, &pen->vertices[start].point);
306 status = stroker->add_external_edge (stroker->closure,
308 if (unlikely (status))
313 start += pen->num_vertices;
315 status = stroker->add_external_edge (stroker->closure,
321 num_points = stop - start;
323 num_points += pen->num_vertices;
325 num_points = pen->num_vertices - stop + start;
327 if (num_points > ARRAY_LENGTH(stack_points)) {
328 points = _cairo_malloc_ab (num_points, sizeof (cairo_point_t));
329 if (unlikely (points == NULL))
330 return _cairo_error (CAIRO_STATUS_NO_MEMORY);
335 while (start != stop) {
336 points[num_points] = *midpt;
337 _translate_point (&points[num_points], &pen->vertices[start].point);
341 start += pen->num_vertices;
343 points[num_points++] = *outpt;
346 _cairo_pen_find_active_cw_vertices (pen,
347 in_vector, out_vector,
349 if (stroker->add_external_edge) {
352 while (start != stop) {
353 cairo_point_t p = *midpt;
354 _translate_point (&p, &pen->vertices[start].point);
356 status = stroker->add_external_edge (stroker->closure,
358 if (unlikely (status))
362 if (++start == pen->num_vertices)
365 status = stroker->add_external_edge (stroker->closure,
371 num_points = stop - start;
373 num_points += pen->num_vertices;
375 num_points = pen->num_vertices - stop + start;
377 if (num_points > ARRAY_LENGTH(stack_points)) {
378 points = _cairo_malloc_ab (num_points, sizeof (cairo_point_t));
379 if (unlikely (points == NULL))
380 return _cairo_error (CAIRO_STATUS_NO_MEMORY);
385 while (start != stop) {
386 points[num_points] = *midpt;
387 _translate_point (&points[num_points], &pen->vertices[start].point);
390 if (++start == pen->num_vertices)
393 points[num_points++] = *outpt;
398 status = stroker->add_triangle_fan (stroker->closure,
399 midpt, points, num_points);
402 if (points != stack_points)
408 /* Ensure a leak free connection... */
409 if (stroker->add_external_edge != NULL) {
411 return stroker->add_external_edge (stroker->closure, inpt, outpt);
413 return stroker->add_external_edge (stroker->closure, outpt, inpt);
415 stack_points[0] = *midpt;
416 stack_points[1] = *inpt;
417 stack_points[2] = *outpt;
418 return stroker->add_triangle (stroker->closure, stack_points);
422 static cairo_status_t
423 _cairo_stroker_join (cairo_stroker_t *stroker,
424 const cairo_stroke_face_t *in,
425 const cairo_stroke_face_t *out)
427 int clockwise = _cairo_stroker_join_is_clockwise (out, in);
428 const cairo_point_t *inpt, *outpt;
429 cairo_point_t points[4];
430 cairo_status_t status;
432 if (in->cw.x == out->cw.x && in->cw.y == out->cw.y &&
433 in->ccw.x == out->ccw.x && in->ccw.y == out->ccw.y)
435 return CAIRO_STATUS_SUCCESS;
439 if (stroker->add_external_edge != NULL) {
440 status = stroker->add_external_edge (stroker->closure,
441 &out->cw, &in->point);
442 if (unlikely (status))
445 status = stroker->add_external_edge (stroker->closure,
446 &in->point, &in->cw);
447 if (unlikely (status))
454 if (stroker->add_external_edge != NULL) {
455 status = stroker->add_external_edge (stroker->closure,
456 &in->ccw, &in->point);
457 if (unlikely (status))
460 status = stroker->add_external_edge (stroker->closure,
461 &in->point, &out->ccw);
462 if (unlikely (status))
470 switch (stroker->style.line_join) {
471 case CAIRO_LINE_JOIN_ROUND:
472 /* construct a fan around the common midpoint */
473 return _tessellate_fan (stroker,
476 &in->point, inpt, outpt,
479 case CAIRO_LINE_JOIN_MITER:
481 /* dot product of incoming slope vector with outgoing slope vector */
482 double in_dot_out = -in->usr_vector.x * out->usr_vector.x +
483 -in->usr_vector.y * out->usr_vector.y;
484 double ml = stroker->style.miter_limit;
486 /* Check the miter limit -- lines meeting at an acute angle
487 * can generate long miters, the limit converts them to bevel
489 * Consider the miter join formed when two line segments
490 * meet at an angle psi:
497 * We can zoom in on the right half of that to see:
515 * The right triangle in that figure, (the line-width side is
516 * shown faintly with three '.' characters), gives us the
517 * following expression relating miter length, angle and line
520 * 1 /sin (psi/2) = miter_length / line_width
522 * The right-hand side of this relationship is the same ratio
523 * in which the miter limit (ml) is expressed. We want to know
524 * when the miter length is within the miter limit. That is
525 * when the following condition holds:
529 * 1 <= ml² sin²(psi/2)
530 * 2 <= ml² 2 sin²(psi/2)
531 * 2·sin²(psi/2) = 1-cos(psi)
532 * 2 <= ml² (1-cos(psi))
534 * in · out = |in| |out| cos (psi)
536 * in and out are both unit vectors, so:
538 * in · out = cos (psi)
540 * 2 <= ml² (1 - in · out)
543 if (2 <= ml * ml * (1 - in_dot_out)) {
544 double x1, y1, x2, y2;
546 double dx1, dx2, dy1, dy2;
548 double fdx1, fdy1, fdx2, fdy2;
552 * we've got the points already transformed to device
553 * space, but need to do some computation with them and
554 * also need to transform the slope from user space to
557 /* outer point of incoming line face */
558 x1 = _cairo_fixed_to_double (inpt->x);
559 y1 = _cairo_fixed_to_double (inpt->y);
560 dx1 = in->usr_vector.x;
561 dy1 = in->usr_vector.y;
562 cairo_matrix_transform_distance (stroker->ctm, &dx1, &dy1);
564 /* outer point of outgoing line face */
565 x2 = _cairo_fixed_to_double (outpt->x);
566 y2 = _cairo_fixed_to_double (outpt->y);
567 dx2 = out->usr_vector.x;
568 dy2 = out->usr_vector.y;
569 cairo_matrix_transform_distance (stroker->ctm, &dx2, &dy2);
572 * Compute the location of the outer corner of the miter.
573 * That's pretty easy -- just the intersection of the two
574 * outer edges. We've got slopes and points on each
575 * of those edges. Compute my directly, then compute
576 * mx by using the edge with the larger dy; that avoids
577 * dividing by values close to zero.
579 my = (((x2 - x1) * dy1 * dy2 - y2 * dx2 * dy1 + y1 * dx1 * dy2) /
580 (dx1 * dy2 - dx2 * dy1));
581 if (fabs (dy1) >= fabs (dy2))
582 mx = (my - y1) * dx1 / dy1 + x1;
584 mx = (my - y2) * dx2 / dy2 + x2;
587 * When the two outer edges are nearly parallel, slight
588 * perturbations in the position of the outer points of the lines
589 * caused by representing them in fixed point form can cause the
590 * intersection point of the miter to move a large amount. If
591 * that moves the miter intersection from between the two faces,
592 * then draw a bevel instead.
595 ix = _cairo_fixed_to_double (in->point.x);
596 iy = _cairo_fixed_to_double (in->point.y);
598 /* slope of one face */
599 fdx1 = x1 - ix; fdy1 = y1 - iy;
601 /* slope of the other face */
602 fdx2 = x2 - ix; fdy2 = y2 - iy;
604 /* slope from the intersection to the miter point */
605 mdx = mx - ix; mdy = my - iy;
608 * Make sure the miter point line lies between the two
609 * faces by comparing the slopes
611 if (_cairo_slope_compare_sgn (fdx1, fdy1, mdx, mdy) !=
612 _cairo_slope_compare_sgn (fdx2, fdy2, mdx, mdy))
614 if (stroker->add_external_edge != NULL) {
615 points[0].x = _cairo_fixed_from_double (mx);
616 points[0].y = _cairo_fixed_from_double (my);
619 status = stroker->add_external_edge (stroker->closure,
621 if (unlikely (status))
624 status = stroker->add_external_edge (stroker->closure,
626 if (unlikely (status))
629 status = stroker->add_external_edge (stroker->closure,
631 if (unlikely (status))
634 status = stroker->add_external_edge (stroker->closure,
636 if (unlikely (status))
640 return CAIRO_STATUS_SUCCESS;
642 points[0] = in->point;
644 points[2].x = _cairo_fixed_from_double (mx);
645 points[2].y = _cairo_fixed_from_double (my);
648 return stroker->add_convex_quad (stroker->closure, points);
654 /* fall through ... */
656 case CAIRO_LINE_JOIN_BEVEL:
657 if (stroker->add_external_edge != NULL) {
659 return stroker->add_external_edge (stroker->closure,
662 return stroker->add_external_edge (stroker->closure,
666 points[0] = in->point;
670 return stroker->add_triangle (stroker->closure, points);
675 static cairo_status_t
676 _cairo_stroker_add_cap (cairo_stroker_t *stroker,
677 const cairo_stroke_face_t *f)
679 switch (stroker->style.line_cap) {
680 case CAIRO_LINE_CAP_ROUND: {
683 slope.dx = -f->dev_vector.dx;
684 slope.dy = -f->dev_vector.dy;
686 return _tessellate_fan (stroker,
689 &f->point, &f->cw, &f->ccw,
694 case CAIRO_LINE_CAP_SQUARE: {
696 cairo_slope_t fvector;
697 cairo_point_t quad[4];
699 dx = f->usr_vector.x;
700 dy = f->usr_vector.y;
701 dx *= stroker->half_line_width;
702 dy *= stroker->half_line_width;
703 cairo_matrix_transform_distance (stroker->ctm, &dx, &dy);
704 fvector.dx = _cairo_fixed_from_double (dx);
705 fvector.dy = _cairo_fixed_from_double (dy);
708 quad[1].x = f->ccw.x + fvector.dx;
709 quad[1].y = f->ccw.y + fvector.dy;
710 quad[2].x = f->cw.x + fvector.dx;
711 quad[2].y = f->cw.y + fvector.dy;
714 if (stroker->add_external_edge != NULL) {
715 cairo_status_t status;
717 status = stroker->add_external_edge (stroker->closure,
719 if (unlikely (status))
722 status = stroker->add_external_edge (stroker->closure,
724 if (unlikely (status))
727 status = stroker->add_external_edge (stroker->closure,
729 if (unlikely (status))
732 return CAIRO_STATUS_SUCCESS;
734 return stroker->add_convex_quad (stroker->closure, quad);
738 case CAIRO_LINE_CAP_BUTT:
740 if (stroker->add_external_edge != NULL) {
741 return stroker->add_external_edge (stroker->closure,
744 return CAIRO_STATUS_SUCCESS;
749 static cairo_status_t
750 _cairo_stroker_add_leading_cap (cairo_stroker_t *stroker,
751 const cairo_stroke_face_t *face)
753 cairo_stroke_face_t reversed;
758 /* The initial cap needs an outward facing vector. Reverse everything */
759 reversed.usr_vector.x = -reversed.usr_vector.x;
760 reversed.usr_vector.y = -reversed.usr_vector.y;
761 reversed.dev_vector.dx = -reversed.dev_vector.dx;
762 reversed.dev_vector.dy = -reversed.dev_vector.dy;
764 reversed.cw = reversed.ccw;
767 return _cairo_stroker_add_cap (stroker, &reversed);
770 static cairo_status_t
771 _cairo_stroker_add_trailing_cap (cairo_stroker_t *stroker,
772 const cairo_stroke_face_t *face)
774 return _cairo_stroker_add_cap (stroker, face);
777 static inline cairo_bool_t
778 _compute_normalized_device_slope (double *dx, double *dy,
779 const cairo_matrix_t *ctm_inverse,
782 double dx0 = *dx, dy0 = *dy;
785 cairo_matrix_transform_distance (ctm_inverse, &dx0, &dy0);
787 if (dx0 == 0.0 && dy0 == 0.0) {
802 } else if (dy0 == 0.0) {
812 mag = hypot (dx0, dy0);
824 _compute_face (const cairo_point_t *point,
825 const cairo_slope_t *dev_slope,
828 cairo_stroker_t *stroker,
829 cairo_stroke_face_t *face)
831 double face_dx, face_dy;
832 cairo_point_t offset_ccw, offset_cw;
835 * rotate to get a line_width/2 vector along the face, note that
836 * the vector must be rotated the right direction in device space,
837 * but by 90° in user space. So, the rotation depends on
838 * whether the ctm reflects or not, and that can be determined
839 * by looking at the determinant of the matrix.
841 if (stroker->ctm_det_positive)
843 face_dx = - slope_dy * stroker->half_line_width;
844 face_dy = slope_dx * stroker->half_line_width;
848 face_dx = slope_dy * stroker->half_line_width;
849 face_dy = - slope_dx * stroker->half_line_width;
852 /* back to device space */
853 cairo_matrix_transform_distance (stroker->ctm, &face_dx, &face_dy);
855 offset_ccw.x = _cairo_fixed_from_double (face_dx);
856 offset_ccw.y = _cairo_fixed_from_double (face_dy);
857 offset_cw.x = -offset_ccw.x;
858 offset_cw.y = -offset_ccw.y;
861 _translate_point (&face->ccw, &offset_ccw);
863 face->point = *point;
866 _translate_point (&face->cw, &offset_cw);
868 face->usr_vector.x = slope_dx;
869 face->usr_vector.y = slope_dy;
871 face->dev_vector = *dev_slope;
874 static cairo_status_t
875 _cairo_stroker_add_caps (cairo_stroker_t *stroker)
877 cairo_status_t status;
879 /* check for a degenerative sub_path */
880 if (stroker->has_initial_sub_path
881 && ! stroker->has_first_face
882 && ! stroker->has_current_face
883 && stroker->style.line_cap == CAIRO_LINE_CAP_ROUND)
885 /* pick an arbitrary slope to use */
886 double dx = 1.0, dy = 0.0;
887 cairo_slope_t slope = { CAIRO_FIXED_ONE, 0 };
888 cairo_stroke_face_t face;
891 _compute_normalized_device_slope (&dx, &dy,
892 stroker->ctm_inverse, NULL);
894 /* arbitrarily choose first_point
895 * first_point and current_point should be the same */
896 _compute_face (&stroker->first_point, &slope, dx, dy, stroker, &face);
898 status = _cairo_stroker_add_leading_cap (stroker, &face);
899 if (unlikely (status))
902 status = _cairo_stroker_add_trailing_cap (stroker, &face);
903 if (unlikely (status))
907 if (stroker->has_first_face) {
908 status = _cairo_stroker_add_leading_cap (stroker,
909 &stroker->first_face);
910 if (unlikely (status))
914 if (stroker->has_current_face) {
915 status = _cairo_stroker_add_trailing_cap (stroker,
916 &stroker->current_face);
917 if (unlikely (status))
921 return CAIRO_STATUS_SUCCESS;
924 static cairo_status_t
925 _cairo_stroker_add_sub_edge (cairo_stroker_t *stroker,
926 const cairo_point_t *p1,
927 const cairo_point_t *p2,
928 cairo_slope_t *dev_slope,
929 double slope_dx, double slope_dy,
930 cairo_stroke_face_t *start,
931 cairo_stroke_face_t *end)
933 _compute_face (p1, dev_slope, slope_dx, slope_dy, stroker, start);
936 if (p1->x == p2->x && p1->y == p2->y)
937 return CAIRO_STATUS_SUCCESS;
940 end->ccw.x += p2->x - p1->x;
941 end->ccw.y += p2->y - p1->y;
942 end->cw.x += p2->x - p1->x;
943 end->cw.y += p2->y - p1->y;
945 if (stroker->add_external_edge != NULL) {
946 cairo_status_t status;
948 status = stroker->add_external_edge (stroker->closure,
949 &end->cw, &start->cw);
950 if (unlikely (status))
953 status = stroker->add_external_edge (stroker->closure,
954 &start->ccw, &end->ccw);
955 if (unlikely (status))
958 return CAIRO_STATUS_SUCCESS;
960 cairo_point_t quad[4];
965 quad[3] = start->ccw;
967 return stroker->add_convex_quad (stroker->closure, quad);
971 static cairo_status_t
972 _cairo_stroker_move_to (void *closure,
973 const cairo_point_t *point)
975 cairo_stroker_t *stroker = closure;
976 cairo_status_t status;
978 /* reset the dash pattern for new sub paths */
979 _cairo_stroker_dash_start (&stroker->dash);
981 /* Cap the start and end of the previous sub path as needed */
982 status = _cairo_stroker_add_caps (stroker);
983 if (unlikely (status))
986 stroker->first_point = *point;
987 stroker->current_point = *point;
989 stroker->has_first_face = FALSE;
990 stroker->has_current_face = FALSE;
991 stroker->has_initial_sub_path = FALSE;
993 return CAIRO_STATUS_SUCCESS;
996 static cairo_status_t
997 _cairo_stroker_line_to (void *closure,
998 const cairo_point_t *point)
1000 cairo_stroker_t *stroker = closure;
1001 cairo_stroke_face_t start, end;
1002 cairo_point_t *p1 = &stroker->current_point;
1003 cairo_slope_t dev_slope;
1004 double slope_dx, slope_dy;
1005 cairo_status_t status;
1008 stroker->has_initial_sub_path = TRUE;
1010 if (p1->x == point->x && p1->y == point->y)
1011 return CAIRO_STATUS_SUCCESS;
1013 _cairo_slope_init (&dev_slope, p1, point);
1014 slope_dx = _cairo_fixed_to_double (point->x - p1->x);
1015 slope_dy = _cairo_fixed_to_double (point->y - p1->y);
1016 _compute_normalized_device_slope (&slope_dx, &slope_dy,
1017 stroker->ctm_inverse, NULL);
1019 status = _cairo_stroker_add_sub_edge (stroker,
1024 if (unlikely (status))
1027 if (stroker->has_current_face) {
1028 /* Join with final face from previous segment */
1029 status = _cairo_stroker_join (stroker,
1030 &stroker->current_face,
1032 if (unlikely (status))
1034 } else if (! stroker->has_first_face) {
1035 /* Save sub path's first face in case needed for closing join */
1036 stroker->first_face = start;
1037 stroker->has_first_face = TRUE;
1039 stroker->current_face = end;
1040 stroker->has_current_face = TRUE;
1042 stroker->current_point = *point;
1044 return CAIRO_STATUS_SUCCESS;
1047 static cairo_status_t
1048 _cairo_stroker_spline_to (void *closure,
1049 const cairo_point_t *point,
1050 const cairo_slope_t *tangent)
1052 cairo_stroker_t *stroker = closure;
1053 cairo_stroke_face_t new_face;
1054 double slope_dx, slope_dy;
1055 cairo_point_t points[3];
1056 cairo_point_t intersect_point;
1057 cairo_line_join_t line_join_save;
1058 cairo_status_t status;
1060 stroker->has_initial_sub_path = TRUE;
1061 new_face.length = 0.0;
1063 if (stroker->current_point.x == point->x &&
1064 stroker->current_point.y == point->y)
1065 return CAIRO_STATUS_SUCCESS;
1067 slope_dx = _cairo_fixed_to_double (tangent->dx);
1068 slope_dy = _cairo_fixed_to_double (tangent->dy);
1070 if (! _compute_normalized_device_slope (&slope_dx, &slope_dy,
1071 stroker->ctm_inverse, NULL))
1072 return CAIRO_STATUS_SUCCESS;
1074 _compute_face (point, tangent,
1076 stroker, &new_face);
1078 assert (stroker->has_current_face);
1080 if ((new_face.dev_slope.x * stroker->current_face.dev_slope.x +
1081 new_face.dev_slope.y * stroker->current_face.dev_slope.y) < stroker->spline_cusp_tolerance) {
1083 const cairo_point_t *inpt, *outpt;
1084 int clockwise = _cairo_stroker_join_is_clockwise (&new_face,
1085 &stroker->current_face);
1088 inpt = &stroker->current_face.cw;
1089 outpt = &new_face.cw;
1091 inpt = &stroker->current_face.ccw;
1092 outpt = &new_face.ccw;
1095 _tessellate_fan (stroker,
1096 &stroker->current_face.dev_vector,
1097 &new_face.dev_vector,
1098 &stroker->current_face.point,
1103 if (_slow_segment_intersection (&stroker->current_face.cw,
1104 &stroker->current_face.ccw,
1107 &intersect_point)) {
1108 points[0] = stroker->current_face.ccw;
1109 points[1] = new_face.ccw;
1110 points[2] = intersect_point;
1111 stroker->add_triangle (stroker->closure, points);
1113 points[0] = stroker->current_face.cw;
1114 points[1] = new_face.cw;
1115 stroker->add_triangle (stroker->closure, points);
1117 points[0] = stroker->current_face.ccw;
1118 points[1] = stroker->current_face.cw;
1119 points[2] = new_face.cw;
1120 stroker->add_triangle (stroker->closure, points);
1122 points[0] = stroker->current_face.ccw;
1123 points[1] = new_face.cw;
1124 points[2] = new_face.ccw;
1125 stroker->add_triangle (stroker->closure, points);
1129 /* Temporarily modify the stroker to use round joins to guarantee
1130 * smooth stroked curves. */
1131 line_join_save = stroker->style.line_join;
1132 stroker->style.line_join = CAIRO_LINE_JOIN_ROUND;
1134 if (! stroker->dash.dashed || stroker->dash.dash_on) {
1135 if (stroker->has_current_face) {
1136 status = _cairo_stroker_join (stroker,
1137 &stroker->current_face, &new_face);
1138 if (unlikely (status))
1143 stroker->style.line_join = line_join_save;
1145 stroker->current_face = new_face;
1146 stroker->has_current_face = TRUE;
1147 stroker->current_point = *point;
1149 return CAIRO_STATUS_SUCCESS;
1153 * Dashed lines. Cap each dash end, join around turns when on
1155 static cairo_status_t
1156 _cairo_stroker_line_to_dashed (void *closure,
1157 const cairo_point_t *p2)
1159 cairo_stroker_t *stroker = closure;
1160 double mag, remain, step_length = 0;
1161 double slope_dx, slope_dy;
1163 cairo_stroke_face_t sub_start, sub_end;
1164 cairo_point_t *p1 = &stroker->current_point;
1165 cairo_slope_t dev_slope;
1166 cairo_line_t segment;
1167 cairo_bool_t fully_in_bounds;
1168 cairo_status_t status;
1169 sub_start.length = 0.0;
1171 stroker->has_initial_sub_path = stroker->dash.dash_starts_on;
1173 if (p1->x == p2->x && p1->y == p2->y)
1174 return CAIRO_STATUS_SUCCESS;
1176 fully_in_bounds = TRUE;
1177 if (stroker->has_bounds &&
1178 (! _cairo_box_contains_point (&stroker->bounds, p1) ||
1179 ! _cairo_box_contains_point (&stroker->bounds, p2)))
1181 fully_in_bounds = FALSE;
1184 _cairo_slope_init (&dev_slope, p1, p2);
1186 slope_dx = _cairo_fixed_to_double (p2->x - p1->x);
1187 slope_dy = _cairo_fixed_to_double (p2->y - p1->y);
1189 if (! _compute_normalized_device_slope (&slope_dx, &slope_dy,
1190 stroker->ctm_inverse, &mag))
1192 return CAIRO_STATUS_SUCCESS;
1198 step_length = MIN (stroker->dash.dash_remain, remain);
1199 remain -= step_length;
1200 dx2 = slope_dx * (mag - remain);
1201 dy2 = slope_dy * (mag - remain);
1202 cairo_matrix_transform_distance (stroker->ctm, &dx2, &dy2);
1203 segment.p2.x = _cairo_fixed_from_double (dx2) + p1->x;
1204 segment.p2.y = _cairo_fixed_from_double (dy2) + p1->y;
1206 if (stroker->dash.dash_on &&
1208 (! stroker->has_first_face && stroker->dash.dash_starts_on) ||
1209 _cairo_box_intersects_line_segment (&stroker->bounds, &segment)))
1211 status = _cairo_stroker_add_sub_edge (stroker,
1212 &segment.p1, &segment.p2,
1215 &sub_start, &sub_end);
1216 if (unlikely (status))
1219 if (stroker->has_current_face)
1221 /* Join with final face from previous segment */
1222 status = _cairo_stroker_join (stroker,
1223 &stroker->current_face,
1225 if (unlikely (status))
1228 stroker->has_current_face = FALSE;
1230 else if (! stroker->has_first_face &&
1231 stroker->dash.dash_starts_on)
1233 /* Save sub path's first face in case needed for closing join */
1234 stroker->first_face = sub_start;
1235 stroker->has_first_face = TRUE;
1239 /* Cap dash start if not connecting to a previous segment */
1240 status = _cairo_stroker_add_leading_cap (stroker, &sub_start);
1241 if (unlikely (status))
1246 /* Cap dash end if not at end of segment */
1247 status = _cairo_stroker_add_trailing_cap (stroker, &sub_end);
1248 if (unlikely (status))
1251 stroker->current_face = sub_end;
1252 stroker->has_current_face = TRUE;
1255 if (stroker->has_current_face) {
1256 /* Cap final face from previous segment */
1257 status = _cairo_stroker_add_trailing_cap (stroker,
1258 &stroker->current_face);
1259 if (unlikely (status))
1262 stroker->has_current_face = FALSE;
1266 _cairo_stroker_dash_step (&stroker->dash, step_length);
1267 segment.p1 = segment.p2;
1270 if (stroker->dash.dash_on && ! stroker->has_current_face) {
1271 /* This segment ends on a transition to dash_on, compute a new face
1272 * and add cap for the beginning of the next dash_on step.
1274 * Note: this will create a degenerate cap if this is not the last line
1275 * in the path. Whether this behaviour is desirable or not is debatable.
1276 * On one side these degenerate caps can not be reproduced with regular
1278 * On the other hand, Acroread 7 also produces the degenerate caps.
1280 _compute_face (p2, &dev_slope,
1283 &stroker->current_face);
1285 status = _cairo_stroker_add_leading_cap (stroker,
1286 &stroker->current_face);
1287 if (unlikely (status))
1290 stroker->has_current_face = TRUE;
1293 stroker->current_point = *p2;
1295 return CAIRO_STATUS_SUCCESS;
1297 static cairo_status_t
1298 _cairo_stroker_curve_to (void *closure,
1299 const cairo_point_t *b,
1300 const cairo_point_t *c,
1301 const cairo_point_t *d)
1303 cairo_stroker_t *stroker = closure;
1304 cairo_spline_t spline;
1305 cairo_line_join_t line_join_save;
1306 cairo_stroke_face_t face;
1307 double slope_dx, slope_dy;
1308 cairo_spline_add_point_func_t line_to;
1309 cairo_spline_add_point_func_t spline_to;
1310 cairo_status_t status = CAIRO_STATUS_SUCCESS;
1313 line_to = stroker->dash.dashed ?
1314 (cairo_spline_add_point_func_t) _cairo_stroker_line_to_dashed :
1315 (cairo_spline_add_point_func_t) _cairo_stroker_line_to;
1317 /* spline_to is only capable of rendering non-degenerate splines. */
1318 spline_to = stroker->dash.dashed ?
1319 (cairo_spline_add_point_func_t) _cairo_stroker_line_to_dashed :
1320 (cairo_spline_add_point_func_t) _cairo_stroker_spline_to;
1322 if (! _cairo_spline_init (&spline,
1325 &stroker->current_point, b, c, d))
1327 cairo_slope_t fallback_slope;
1328 _cairo_slope_init (&fallback_slope, &stroker->current_point, d);
1329 return line_to (closure, d, &fallback_slope);
1332 /* If the line width is so small that the pen is reduced to a
1333 single point, then we have nothing to do. */
1334 if (stroker->pen.num_vertices <= 1)
1335 return CAIRO_STATUS_SUCCESS;
1337 /* Compute the initial face */
1338 if (! stroker->dash.dashed || stroker->dash.dash_on) {
1339 slope_dx = _cairo_fixed_to_double (spline.initial_slope.dx);
1340 slope_dy = _cairo_fixed_to_double (spline.initial_slope.dy);
1341 if (_compute_normalized_device_slope (&slope_dx, &slope_dy,
1342 stroker->ctm_inverse, NULL))
1344 _compute_face (&stroker->current_point,
1345 &spline.initial_slope,
1349 if (stroker->has_current_face) {
1350 status = _cairo_stroker_join (stroker,
1351 &stroker->current_face, &face);
1352 if (unlikely (status))
1354 } else if (! stroker->has_first_face) {
1355 stroker->first_face = face;
1356 stroker->has_first_face = TRUE;
1359 stroker->current_face = face;
1360 stroker->has_current_face = TRUE;
1363 /* Temporarily modify the stroker to use round joins to guarantee
1364 * smooth stroked curves. */
1365 line_join_save = stroker->style.line_join;
1366 stroker->style.line_join = CAIRO_LINE_JOIN_ROUND;
1368 status = _cairo_spline_decompose (&spline, stroker->tolerance);
1369 if (unlikely (status))
1372 /* And join the final face */
1373 if (! stroker->dash.dashed || stroker->dash.dash_on) {
1374 slope_dx = _cairo_fixed_to_double (spline.final_slope.dx);
1375 slope_dy = _cairo_fixed_to_double (spline.final_slope.dy);
1376 if (_compute_normalized_device_slope (&slope_dx, &slope_dy,
1377 stroker->ctm_inverse, NULL))
1379 _compute_face (&stroker->current_point,
1380 &spline.final_slope,
1385 status = _cairo_stroker_join (stroker, &stroker->current_face, &face);
1386 if (unlikely (status))
1389 stroker->current_face = face;
1392 stroker->style.line_join = line_join_save;
1394 return CAIRO_STATUS_SUCCESS;
1397 static cairo_status_t
1398 _cairo_stroker_close_path (void *closure)
1400 cairo_stroker_t *stroker = closure;
1401 cairo_status_t status;
1403 if (stroker->dash.dashed)
1404 status = _cairo_stroker_line_to_dashed (stroker, &stroker->first_point);
1406 status = _cairo_stroker_line_to (stroker, &stroker->first_point);
1407 if (unlikely (status))
1410 if (stroker->has_first_face && stroker->has_current_face) {
1411 /* Join first and final faces of sub path */
1412 status = _cairo_stroker_join (stroker,
1413 &stroker->current_face,
1414 &stroker->first_face);
1415 if (unlikely (status))
1418 /* Cap the start and end of the sub path as needed */
1419 status = _cairo_stroker_add_caps (stroker);
1420 if (unlikely (status))
1424 stroker->has_initial_sub_path = FALSE;
1425 stroker->has_first_face = FALSE;
1426 stroker->has_current_face = FALSE;
1428 return CAIRO_STATUS_SUCCESS;
1432 _cairo_path_fixed_stroke_to_shaper (cairo_path_fixed_t *path,
1433 const cairo_stroke_style_t *stroke_style,
1434 const cairo_matrix_t *ctm,
1435 const cairo_matrix_t *ctm_inverse,
1437 cairo_status_t (*add_triangle) (void *closure,
1438 const cairo_point_t triangle[3]),
1439 cairo_status_t (*add_triangle_fan) (void *closure,
1440 const cairo_point_t *midpt,
1441 const cairo_point_t *points,
1443 cairo_status_t (*add_convex_quad) (void *closure,
1444 const cairo_point_t quad[4]),
1447 cairo_stroker_t stroker;
1448 cairo_status_t status;
1450 status = _cairo_stroker_init (&stroker, path, stroke_style,
1451 ctm, ctm_inverse, tolerance,
1453 if (unlikely (status))
1456 stroker.add_triangle = add_triangle;
1457 stroker.add_triangle_fan = add_triangle_fan;
1458 stroker.add_convex_quad = add_convex_quad;
1459 stroker.closure = closure;
1461 status = _cairo_path_fixed_interpret (path,
1462 _cairo_stroker_move_to,
1463 stroker.dash.dashed ?
1464 _cairo_stroker_line_to_dashed :
1465 _cairo_stroker_line_to,
1466 _cairo_stroker_curve_to,
1467 _cairo_stroker_close_path,
1470 if (unlikely (status))
1473 /* Cap the start and end of the final sub path as needed */
1474 status = _cairo_stroker_add_caps (&stroker);
1477 _cairo_stroker_fini (&stroker);
1483 _cairo_path_fixed_stroke_dashed_to_polygon (const cairo_path_fixed_t *path,
1484 const cairo_stroke_style_t *stroke_style,
1485 const cairo_matrix_t *ctm,
1486 const cairo_matrix_t *ctm_inverse,
1488 cairo_polygon_t *polygon)
1490 cairo_stroker_t stroker;
1491 cairo_status_t status;
1493 status = _cairo_stroker_init (&stroker, path, stroke_style,
1494 ctm, ctm_inverse, tolerance,
1495 polygon->limits, polygon->num_limits);
1496 if (unlikely (status))
1499 stroker.add_external_edge = _cairo_polygon_add_external_edge,
1500 stroker.closure = polygon;
1502 status = _cairo_path_fixed_interpret (path,
1503 _cairo_stroker_move_to,
1504 stroker.dash.dashed ?
1505 _cairo_stroker_line_to_dashed :
1506 _cairo_stroker_line_to,
1507 _cairo_stroker_curve_to,
1508 _cairo_stroker_close_path,
1511 if (unlikely (status))
1514 /* Cap the start and end of the final sub path as needed */
1515 status = _cairo_stroker_add_caps (&stroker);
1518 _cairo_stroker_fini (&stroker);
1524 _cairo_path_fixed_stroke_polygon_to_traps (const cairo_path_fixed_t *path,
1525 const cairo_stroke_style_t *stroke_style,
1526 const cairo_matrix_t *ctm,
1527 const cairo_matrix_t *ctm_inverse,
1529 cairo_traps_t *traps)
1531 cairo_int_status_t status;
1532 cairo_polygon_t polygon;
1534 _cairo_polygon_init (&polygon, traps->limits, traps->num_limits);
1535 status = _cairo_path_fixed_stroke_to_polygon (path,
1541 if (unlikely (status))
1544 status = _cairo_polygon_status (&polygon);
1545 if (unlikely (status))
1548 status = _cairo_bentley_ottmann_tessellate_polygon (traps, &polygon,
1549 CAIRO_FILL_RULE_WINDING);
1552 _cairo_polygon_fini (&polygon);