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 ctm_determinant;
58 cairo_bool_t ctm_det_positive;
61 cairo_status_t (*add_external_edge) (void *closure,
62 const cairo_point_t *p1,
63 const cairo_point_t *p2);
64 cairo_status_t (*add_triangle) (void *closure,
65 const cairo_point_t triangle[3]);
66 cairo_status_t (*add_triangle_fan) (void *closure,
67 const cairo_point_t *midpt,
68 const cairo_point_t *points,
70 cairo_status_t (*add_convex_quad) (void *closure,
71 const cairo_point_t quad[4]);
75 cairo_point_t current_point;
76 cairo_point_t first_point;
78 cairo_bool_t has_initial_sub_path;
80 cairo_bool_t has_current_face;
81 cairo_stroke_face_t current_face;
83 cairo_bool_t has_first_face;
84 cairo_stroke_face_t first_face;
86 cairo_stroker_dash_t dash;
88 cairo_bool_t has_bounds;
93 _cairo_stroke_segment_intersect (cairo_point_t *p1, cairo_point_t *p2,
94 cairo_point_t *p3, cairo_point_t *p4,
97 double x1, y1, x2, y2, x3, y3, x4, y4;
101 x1 = _cairo_fixed_to_double (p1->x);
102 y1 = _cairo_fixed_to_double (p1->y);
103 x2 = _cairo_fixed_to_double (p2->x);
104 y2 = _cairo_fixed_to_double (p2->y);
105 x3 = _cairo_fixed_to_double (p3->x);
106 y3 = _cairo_fixed_to_double (p3->y);
107 x4 = _cairo_fixed_to_double (p4->x);
108 y4 = _cairo_fixed_to_double (p4->y);
110 d = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4);
114 pre = x1 * y2 - y1 * x2;
115 post = x3 * y4 - y3 * x4;
116 x = (pre * (x3 - x4) - (x1 - x2) * post) / d;
117 y = (pre * (y3 - y4) - (y1 - y2) * post) / d;
119 /* check if x, y are within both segments */
120 if (x < MIN (x1, x2) || x > MAX (x1, x2) ||
121 x < MIN (x3, x4) || x > MAX (x3, x4))
123 if (y < MIN (y1, y2) || y > MAX (y1, y2) ||
124 y < MIN (y1, y2) || y > MAX (y3, y4))
127 p->x = _cairo_fixed_from_double (x);
128 p->y = _cairo_fixed_from_double (y);
133 _cairo_stroker_limit (cairo_stroker_t *stroker,
134 const cairo_path_fixed_t *path,
135 const cairo_box_t *boxes,
139 cairo_fixed_t fdx, fdy;
141 stroker->has_bounds = TRUE;
142 _cairo_boxes_get_extents (boxes, num_boxes, &stroker->bounds);
144 /* Extend the bounds in each direction to account for the maximum area
145 * we might generate trapezoids, to capture line segments that are outside
146 * of the bounds but which might generate rendering that's within bounds.
149 _cairo_stroke_style_max_distance_from_path (&stroker->style, path,
150 stroker->ctm, &dx, &dy);
152 fdx = _cairo_fixed_from_double (dx);
153 fdy = _cairo_fixed_from_double (dy);
155 stroker->bounds.p1.x -= fdx;
156 stroker->bounds.p2.x += fdx;
158 stroker->bounds.p1.y -= fdy;
159 stroker->bounds.p2.y += fdy;
162 static cairo_status_t
163 _cairo_stroker_init (cairo_stroker_t *stroker,
164 const cairo_path_fixed_t *path,
165 const cairo_stroke_style_t *stroke_style,
166 const cairo_matrix_t *ctm,
167 const cairo_matrix_t *ctm_inverse,
169 const cairo_box_t *limits,
172 cairo_status_t status;
174 stroker->style = *stroke_style;
176 stroker->ctm_inverse = ctm_inverse;
177 stroker->tolerance = tolerance;
178 stroker->half_line_width = stroke_style->line_width / 2.0;
180 stroker->ctm_determinant = _cairo_matrix_compute_determinant (stroker->ctm);
181 stroker->ctm_det_positive = stroker->ctm_determinant >= 0.0;
183 status = _cairo_pen_init (&stroker->pen,
184 stroker->half_line_width, tolerance, ctm);
185 if (unlikely (status))
188 stroker->has_current_face = FALSE;
189 stroker->has_first_face = FALSE;
190 stroker->has_initial_sub_path = FALSE;
192 _cairo_stroker_dash_init (&stroker->dash, stroke_style);
194 stroker->add_external_edge = NULL;
196 stroker->has_bounds = FALSE;
198 _cairo_stroker_limit (stroker, path, limits, num_limits);
200 return CAIRO_STATUS_SUCCESS;
204 _cairo_stroker_fini (cairo_stroker_t *stroker)
206 _cairo_pen_fini (&stroker->pen);
210 _translate_point (cairo_point_t *point, const cairo_point_t *offset)
212 point->x += offset->x;
213 point->y += offset->y;
217 _cairo_stroker_join_is_clockwise (const cairo_stroke_face_t *in,
218 const cairo_stroke_face_t *out)
220 cairo_slope_t in_slope, out_slope;
222 _cairo_slope_init (&in_slope, &in->point, &in->cw);
223 _cairo_slope_init (&out_slope, &out->point, &out->cw);
225 return _cairo_slope_compare (&in_slope, &out_slope) < 0;
229 * _cairo_slope_compare_sgn:
231 * Return -1, 0 or 1 depending on the relative slopes of
235 _cairo_slope_compare_sgn (double dx1, double dy1, double dx2, double dy2)
237 double c = (dx1 * dy2 - dx2 * dy1);
240 if (c < 0) return -1;
245 _range_step (int i, int step, int max)
256 * Construct a fan around the midpoint using the vertices from pen between
259 static cairo_status_t
260 _tessellate_fan (cairo_stroker_t *stroker,
261 const cairo_slope_t *in_vector,
262 const cairo_slope_t *out_vector,
263 const cairo_point_t *midpt,
264 const cairo_point_t *inpt,
265 const cairo_point_t *outpt,
266 cairo_bool_t clockwise)
268 cairo_point_t stack_points[64], *points = stack_points;
269 cairo_pen_t *pen = &stroker->pen;
270 int start, stop, num_points = 0;
271 cairo_status_t status;
273 if (stroker->has_bounds &&
274 ! _cairo_box_contains_point (&stroker->bounds, midpt))
277 assert (stroker->pen.num_vertices);
280 _cairo_pen_find_active_ccw_vertices (pen,
281 in_vector, out_vector,
283 if (stroker->add_external_edge) {
286 while (start != stop) {
287 cairo_point_t p = *midpt;
288 _translate_point (&p, &pen->vertices[start].point);
290 status = stroker->add_external_edge (stroker->closure,
292 if (unlikely (status))
297 start += pen->num_vertices;
299 status = stroker->add_external_edge (stroker->closure,
305 num_points = stop - start;
307 num_points += pen->num_vertices;
309 if (num_points > ARRAY_LENGTH(stack_points)) {
310 points = _cairo_malloc_ab (num_points, sizeof (cairo_point_t));
311 if (unlikely (points == NULL))
312 return _cairo_error (CAIRO_STATUS_NO_MEMORY);
317 while (start != stop) {
318 points[num_points] = *midpt;
319 _translate_point (&points[num_points], &pen->vertices[start].point);
323 start += pen->num_vertices;
325 points[num_points++] = *outpt;
328 _cairo_pen_find_active_cw_vertices (pen,
329 in_vector, out_vector,
331 if (stroker->add_external_edge) {
334 while (start != stop) {
335 cairo_point_t p = *midpt;
336 _translate_point (&p, &pen->vertices[start].point);
338 status = stroker->add_external_edge (stroker->closure,
340 if (unlikely (status))
344 if (++start == pen->num_vertices)
347 status = stroker->add_external_edge (stroker->closure,
353 num_points = stop - start;
355 num_points += pen->num_vertices;
357 if (num_points > ARRAY_LENGTH(stack_points)) {
358 points = _cairo_malloc_ab (num_points, sizeof (cairo_point_t));
359 if (unlikely (points == NULL))
360 return _cairo_error (CAIRO_STATUS_NO_MEMORY);
365 while (start != stop) {
366 points[num_points] = *midpt;
367 _translate_point (&points[num_points], &pen->vertices[start].point);
370 if (++start == pen->num_vertices)
373 points[num_points++] = *outpt;
378 status = stroker->add_triangle_fan (stroker->closure,
379 midpt, points, num_points);
382 if (points != stack_points)
388 /* Ensure a leak free connection... */
389 if (stroker->add_external_edge != NULL) {
391 return stroker->add_external_edge (stroker->closure, inpt, outpt);
393 return stroker->add_external_edge (stroker->closure, outpt, inpt);
395 stack_points[0] = *midpt;
396 stack_points[1] = *inpt;
397 stack_points[2] = *outpt;
398 return stroker->add_triangle (stroker->closure, stack_points);
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)
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;
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)
415 return CAIRO_STATUS_SUCCESS;
419 if (stroker->add_external_edge != NULL) {
420 status = stroker->add_external_edge (stroker->closure,
421 &out->cw, &in->point);
422 if (unlikely (status))
425 status = stroker->add_external_edge (stroker->closure,
426 &in->point, &in->cw);
427 if (unlikely (status))
434 if (stroker->add_external_edge != NULL) {
435 status = stroker->add_external_edge (stroker->closure,
436 &in->ccw, &in->point);
437 if (unlikely (status))
440 status = stroker->add_external_edge (stroker->closure,
441 &in->point, &out->ccw);
442 if (unlikely (status))
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,
456 &in->point, inpt, outpt,
459 case CAIRO_LINE_JOIN_MITER:
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;
466 /* Check the miter limit -- lines meeting at an acute angle
467 * can generate long miters, the limit converts them to bevel
469 * Consider the miter join formed when two line segments
470 * meet at an angle psi:
477 * We can zoom in on the right half of that to see:
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
500 * 1 /sin (psi/2) = miter_length / line_width
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:
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))
514 * in · out = |in| |out| cos (psi)
516 * in and out are both unit vectors, so:
518 * in · out = cos (psi)
520 * 2 <= ml² (1 - in · out)
523 if (2 <= ml * ml * (1 - in_dot_out)) {
524 double x1, y1, x2, y2;
526 double dx1, dx2, dy1, dy2;
528 double fdx1, fdy1, fdx2, fdy2;
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
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);
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);
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.
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;
564 mx = (my - y2) * dx2 / dy2 + x2;
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.
575 ix = _cairo_fixed_to_double (in->point.x);
576 iy = _cairo_fixed_to_double (in->point.y);
578 /* slope of one face */
579 fdx1 = x1 - ix; fdy1 = y1 - iy;
581 /* slope of the other face */
582 fdx2 = x2 - ix; fdy2 = y2 - iy;
584 /* slope from the intersection to the miter point */
585 mdx = mx - ix; mdy = my - iy;
588 * Make sure the miter point line lies between the two
589 * faces by comparing the slopes
591 if (_cairo_slope_compare_sgn (fdx1, fdy1, mdx, mdy) !=
592 _cairo_slope_compare_sgn (fdx2, fdy2, mdx, mdy))
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);
599 status = stroker->add_external_edge (stroker->closure,
601 if (unlikely (status))
604 status = stroker->add_external_edge (stroker->closure,
606 if (unlikely (status))
609 status = stroker->add_external_edge (stroker->closure,
611 if (unlikely (status))
614 status = stroker->add_external_edge (stroker->closure,
616 if (unlikely (status))
620 return CAIRO_STATUS_SUCCESS;
622 points[0] = in->point;
624 points[2].x = _cairo_fixed_from_double (mx);
625 points[2].y = _cairo_fixed_from_double (my);
628 return stroker->add_convex_quad (stroker->closure, points);
634 /* fall through ... */
636 case CAIRO_LINE_JOIN_BEVEL:
637 if (stroker->add_external_edge != NULL) {
639 return stroker->add_external_edge (stroker->closure,
642 return stroker->add_external_edge (stroker->closure,
646 points[0] = in->point;
650 return stroker->add_triangle (stroker->closure, points);
655 static cairo_status_t
656 _cairo_stroker_add_cap (cairo_stroker_t *stroker,
657 const cairo_stroke_face_t *f)
659 switch (stroker->style.line_cap) {
660 case CAIRO_LINE_CAP_ROUND: {
663 slope.dx = -f->dev_vector.dx;
664 slope.dy = -f->dev_vector.dy;
666 return _tessellate_fan (stroker,
669 &f->point, &f->cw, &f->ccw,
674 case CAIRO_LINE_CAP_SQUARE: {
676 cairo_slope_t fvector;
677 cairo_point_t quad[4];
679 dx = f->usr_vector.x;
680 dy = f->usr_vector.y;
681 dx *= stroker->half_line_width;
682 dy *= stroker->half_line_width;
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);
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;
694 if (stroker->add_external_edge != NULL) {
695 cairo_status_t status;
697 status = stroker->add_external_edge (stroker->closure,
699 if (unlikely (status))
702 status = stroker->add_external_edge (stroker->closure,
704 if (unlikely (status))
707 status = stroker->add_external_edge (stroker->closure,
709 if (unlikely (status))
712 return CAIRO_STATUS_SUCCESS;
714 return stroker->add_convex_quad (stroker->closure, quad);
718 case CAIRO_LINE_CAP_BUTT:
720 if (stroker->add_external_edge != NULL) {
721 return stroker->add_external_edge (stroker->closure,
724 return CAIRO_STATUS_SUCCESS;
729 static cairo_status_t
730 _cairo_stroker_add_leading_cap (cairo_stroker_t *stroker,
731 const cairo_stroke_face_t *face)
733 cairo_stroke_face_t reversed;
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;
744 reversed.cw = reversed.ccw;
747 return _cairo_stroker_add_cap (stroker, &reversed);
750 static cairo_status_t
751 _cairo_stroker_add_trailing_cap (cairo_stroker_t *stroker,
752 const cairo_stroke_face_t *face)
754 return _cairo_stroker_add_cap (stroker, face);
757 static inline cairo_bool_t
758 _compute_normalized_device_slope (double *dx, double *dy,
759 const cairo_matrix_t *ctm_inverse,
762 double dx0 = *dx, dy0 = *dy;
765 cairo_matrix_transform_distance (ctm_inverse, &dx0, &dy0);
767 if (dx0 == 0.0 && dy0 == 0.0) {
782 } else if (dy0 == 0.0) {
792 mag = hypot (dx0, dy0);
804 _compute_face (const cairo_point_t *point,
805 const cairo_slope_t *dev_slope,
808 cairo_stroker_t *stroker,
809 cairo_stroke_face_t *face)
811 double face_dx, face_dy;
812 cairo_point_t offset_ccw, offset_cw;
815 * rotate to get a line_width/2 vector along the face, note that
816 * the vector must be rotated the right direction in device space,
817 * but by 90° in user space. So, the rotation depends on
818 * whether the ctm reflects or not, and that can be determined
819 * by looking at the determinant of the matrix.
821 if (stroker->ctm_det_positive)
823 face_dx = - slope_dy * stroker->half_line_width;
824 face_dy = slope_dx * stroker->half_line_width;
828 face_dx = slope_dy * stroker->half_line_width;
829 face_dy = - slope_dx * stroker->half_line_width;
832 /* back to device space */
833 cairo_matrix_transform_distance (stroker->ctm, &face_dx, &face_dy);
835 offset_ccw.x = _cairo_fixed_from_double (face_dx);
836 offset_ccw.y = _cairo_fixed_from_double (face_dy);
837 offset_cw.x = -offset_ccw.x;
838 offset_cw.y = -offset_ccw.y;
841 _translate_point (&face->ccw, &offset_ccw);
843 face->point = *point;
846 _translate_point (&face->cw, &offset_cw);
848 face->usr_vector.x = slope_dx;
849 face->usr_vector.y = slope_dy;
851 face->dev_vector = *dev_slope;
854 static cairo_status_t
855 _cairo_stroker_add_caps (cairo_stroker_t *stroker)
857 cairo_status_t status;
859 /* check for a degenerative sub_path */
860 if (stroker->has_initial_sub_path
861 && ! stroker->has_first_face
862 && ! stroker->has_current_face
863 && stroker->style.line_cap == CAIRO_LINE_CAP_ROUND)
865 /* pick an arbitrary slope to use */
866 double dx = 1.0, dy = 0.0;
867 cairo_slope_t slope = { CAIRO_FIXED_ONE, 0 };
868 cairo_stroke_face_t face;
870 _compute_normalized_device_slope (&dx, &dy,
871 stroker->ctm_inverse, NULL);
873 /* arbitrarily choose first_point
874 * first_point and current_point should be the same */
875 _compute_face (&stroker->first_point, &slope, dx, dy, stroker, &face);
877 status = _cairo_stroker_add_leading_cap (stroker, &face);
878 if (unlikely (status))
881 status = _cairo_stroker_add_trailing_cap (stroker, &face);
882 if (unlikely (status))
886 if (stroker->has_first_face) {
887 status = _cairo_stroker_add_leading_cap (stroker,
888 &stroker->first_face);
889 if (unlikely (status))
893 if (stroker->has_current_face) {
894 status = _cairo_stroker_add_trailing_cap (stroker,
895 &stroker->current_face);
896 if (unlikely (status))
900 return CAIRO_STATUS_SUCCESS;
903 static cairo_status_t
904 _cairo_stroker_add_sub_edge (cairo_stroker_t *stroker,
905 const cairo_point_t *p1,
906 const cairo_point_t *p2,
907 cairo_slope_t *dev_slope,
908 double slope_dx, double slope_dy,
909 cairo_stroke_face_t *start,
910 cairo_stroke_face_t *end)
912 _compute_face (p1, dev_slope, slope_dx, slope_dy, stroker, start);
915 if (p1->x == p2->x && p1->y == p2->y)
916 return CAIRO_STATUS_SUCCESS;
919 end->ccw.x += p2->x - p1->x;
920 end->ccw.y += p2->y - p1->y;
921 end->cw.x += p2->x - p1->x;
922 end->cw.y += p2->y - p1->y;
924 if (stroker->add_external_edge != NULL) {
925 cairo_status_t status;
927 status = stroker->add_external_edge (stroker->closure,
928 &end->cw, &start->cw);
929 if (unlikely (status))
932 status = stroker->add_external_edge (stroker->closure,
933 &start->ccw, &end->ccw);
934 if (unlikely (status))
937 return CAIRO_STATUS_SUCCESS;
939 cairo_point_t quad[4];
944 quad[3] = start->ccw;
946 return stroker->add_convex_quad (stroker->closure, quad);
950 static cairo_status_t
951 _cairo_stroker_move_to (void *closure,
952 const cairo_point_t *point)
954 cairo_stroker_t *stroker = closure;
955 cairo_status_t status;
957 /* reset the dash pattern for new sub paths */
958 _cairo_stroker_dash_start (&stroker->dash);
960 /* Cap the start and end of the previous sub path as needed */
961 status = _cairo_stroker_add_caps (stroker);
962 if (unlikely (status))
965 stroker->first_point = *point;
966 stroker->current_point = *point;
968 stroker->has_first_face = FALSE;
969 stroker->has_current_face = FALSE;
970 stroker->has_initial_sub_path = FALSE;
972 return CAIRO_STATUS_SUCCESS;
975 static cairo_status_t
976 _cairo_stroker_line_to (void *closure,
977 const cairo_point_t *point)
979 cairo_stroker_t *stroker = closure;
980 cairo_stroke_face_t start, end;
981 cairo_point_t *p1 = &stroker->current_point;
982 cairo_slope_t dev_slope;
983 double slope_dx, slope_dy;
984 cairo_status_t status;
986 stroker->has_initial_sub_path = TRUE;
988 if (p1->x == point->x && p1->y == point->y)
989 return CAIRO_STATUS_SUCCESS;
991 _cairo_slope_init (&dev_slope, p1, point);
992 slope_dx = _cairo_fixed_to_double (point->x - p1->x);
993 slope_dy = _cairo_fixed_to_double (point->y - p1->y);
994 _compute_normalized_device_slope (&slope_dx, &slope_dy,
995 stroker->ctm_inverse, NULL);
997 status = _cairo_stroker_add_sub_edge (stroker,
1002 if (unlikely (status))
1005 if (stroker->has_current_face) {
1006 /* Join with final face from previous segment */
1007 status = _cairo_stroker_join (stroker,
1008 &stroker->current_face,
1010 if (unlikely (status))
1012 } else if (! stroker->has_first_face) {
1013 /* Save sub path's first face in case needed for closing join */
1014 stroker->first_face = start;
1015 stroker->has_first_face = TRUE;
1017 stroker->current_face = end;
1018 stroker->has_current_face = TRUE;
1020 stroker->current_point = *point;
1022 return CAIRO_STATUS_SUCCESS;
1025 static cairo_status_t
1026 _cairo_stroker_spline_to (void *closure,
1027 const cairo_point_t *point,
1028 const cairo_slope_t *tangent)
1030 cairo_stroker_t *stroker = closure;
1031 cairo_stroke_face_t new_face;
1032 double slope_dx, slope_dy;
1033 cairo_point_t points[3];
1034 cairo_point_t intersect_point;
1036 stroker->has_initial_sub_path = TRUE;
1038 if (stroker->current_point.x == point->x &&
1039 stroker->current_point.y == point->y)
1040 return CAIRO_STATUS_SUCCESS;
1042 slope_dx = _cairo_fixed_to_double (tangent->dx);
1043 slope_dy = _cairo_fixed_to_double (tangent->dy);
1045 if (! _compute_normalized_device_slope (&slope_dx, &slope_dy,
1046 stroker->ctm_inverse, NULL))
1047 return CAIRO_STATUS_SUCCESS;
1049 _compute_face (point, tangent,
1051 stroker, &new_face);
1053 assert(stroker->has_current_face);
1055 if (_cairo_stroke_segment_intersect (&stroker->current_face.cw,
1056 &stroker->current_face.ccw,
1059 &intersect_point)) {
1060 points[0] = stroker->current_face.ccw;
1061 points[1] = new_face.ccw;
1062 points[2] = intersect_point;
1063 stroker->add_triangle (stroker->closure, points);
1065 points[0] = stroker->current_face.cw;
1066 points[1] = new_face.cw;
1067 stroker->add_triangle (stroker->closure, points);
1070 points[0] = stroker->current_face.ccw;
1071 points[1] = stroker->current_face.cw;
1072 points[2] = new_face.cw;
1073 stroker->add_triangle (stroker->closure, points);
1075 points[0] = stroker->current_face.ccw;
1076 points[1] = new_face.cw;
1077 points[2] = new_face.ccw;
1078 stroker->add_triangle (stroker->closure, points);
1081 stroker->current_face = new_face;
1082 stroker->has_current_face = TRUE;
1083 stroker->current_point = *point;
1085 return CAIRO_STATUS_SUCCESS;
1089 * Dashed lines. Cap each dash end, join around turns when on
1091 static cairo_status_t
1092 _cairo_stroker_line_to_dashed (void *closure,
1093 const cairo_point_t *p2)
1095 cairo_stroker_t *stroker = closure;
1096 double mag, remain, step_length = 0;
1097 double slope_dx, slope_dy;
1099 cairo_stroke_face_t sub_start, sub_end;
1100 cairo_point_t *p1 = &stroker->current_point;
1101 cairo_slope_t dev_slope;
1102 cairo_line_t segment;
1103 cairo_bool_t fully_in_bounds;
1104 cairo_status_t status;
1106 stroker->has_initial_sub_path = stroker->dash.dash_starts_on;
1108 if (p1->x == p2->x && p1->y == p2->y)
1109 return CAIRO_STATUS_SUCCESS;
1111 fully_in_bounds = TRUE;
1112 if (stroker->has_bounds &&
1113 (! _cairo_box_contains_point (&stroker->bounds, p1) ||
1114 ! _cairo_box_contains_point (&stroker->bounds, p2)))
1116 fully_in_bounds = FALSE;
1119 _cairo_slope_init (&dev_slope, p1, p2);
1121 slope_dx = _cairo_fixed_to_double (p2->x - p1->x);
1122 slope_dy = _cairo_fixed_to_double (p2->y - p1->y);
1124 if (! _compute_normalized_device_slope (&slope_dx, &slope_dy,
1125 stroker->ctm_inverse, &mag))
1127 return CAIRO_STATUS_SUCCESS;
1133 step_length = MIN (stroker->dash.dash_remain, remain);
1134 remain -= step_length;
1135 dx2 = slope_dx * (mag - remain);
1136 dy2 = slope_dy * (mag - remain);
1137 cairo_matrix_transform_distance (stroker->ctm, &dx2, &dy2);
1138 segment.p2.x = _cairo_fixed_from_double (dx2) + p1->x;
1139 segment.p2.y = _cairo_fixed_from_double (dy2) + p1->y;
1141 if (stroker->dash.dash_on &&
1143 (! stroker->has_first_face && stroker->dash.dash_starts_on) ||
1144 _cairo_box_intersects_line_segment (&stroker->bounds, &segment)))
1146 status = _cairo_stroker_add_sub_edge (stroker,
1147 &segment.p1, &segment.p2,
1150 &sub_start, &sub_end);
1151 if (unlikely (status))
1154 if (stroker->has_current_face)
1156 /* Join with final face from previous segment */
1157 status = _cairo_stroker_join (stroker,
1158 &stroker->current_face,
1160 if (unlikely (status))
1163 stroker->has_current_face = FALSE;
1165 else if (! stroker->has_first_face &&
1166 stroker->dash.dash_starts_on)
1168 /* Save sub path's first face in case needed for closing join */
1169 stroker->first_face = sub_start;
1170 stroker->has_first_face = TRUE;
1174 /* Cap dash start if not connecting to a previous segment */
1175 status = _cairo_stroker_add_leading_cap (stroker, &sub_start);
1176 if (unlikely (status))
1181 /* Cap dash end if not at end of segment */
1182 status = _cairo_stroker_add_trailing_cap (stroker, &sub_end);
1183 if (unlikely (status))
1186 stroker->current_face = sub_end;
1187 stroker->has_current_face = TRUE;
1190 if (stroker->has_current_face) {
1191 /* Cap final face from previous segment */
1192 status = _cairo_stroker_add_trailing_cap (stroker,
1193 &stroker->current_face);
1194 if (unlikely (status))
1197 stroker->has_current_face = FALSE;
1201 _cairo_stroker_dash_step (&stroker->dash, step_length);
1202 segment.p1 = segment.p2;
1205 if (stroker->dash.dash_on && ! stroker->has_current_face) {
1206 /* This segment ends on a transition to dash_on, compute a new face
1207 * and add cap for the beginning of the next dash_on step.
1209 * Note: this will create a degenerate cap if this is not the last line
1210 * in the path. Whether this behaviour is desirable or not is debatable.
1211 * On one side these degenerate caps can not be reproduced with regular
1213 * On the other hand, Acroread 7 also produces the degenerate caps.
1215 _compute_face (p2, &dev_slope,
1218 &stroker->current_face);
1220 status = _cairo_stroker_add_leading_cap (stroker,
1221 &stroker->current_face);
1222 if (unlikely (status))
1225 stroker->has_current_face = TRUE;
1228 stroker->current_point = *p2;
1230 return CAIRO_STATUS_SUCCESS;
1232 static cairo_status_t
1233 _cairo_stroker_curve_to (void *closure,
1234 const cairo_point_t *b,
1235 const cairo_point_t *c,
1236 const cairo_point_t *d)
1238 cairo_stroker_t *stroker = closure;
1239 cairo_spline_t spline;
1240 cairo_line_join_t line_join_save;
1241 cairo_stroke_face_t face;
1242 double slope_dx, slope_dy;
1243 cairo_spline_add_point_func_t line_to;
1244 cairo_spline_add_point_func_t spline_to;
1245 cairo_status_t status = CAIRO_STATUS_SUCCESS;
1247 line_to = stroker->dash.dashed ?
1248 (cairo_spline_add_point_func_t) _cairo_stroker_line_to_dashed :
1249 (cairo_spline_add_point_func_t) _cairo_stroker_line_to;
1251 /* spline_to is only capable of rendering non-degenerate splines. */
1252 spline_to = stroker->dash.dashed ?
1253 (cairo_spline_add_point_func_t) _cairo_stroker_line_to_dashed :
1254 (cairo_spline_add_point_func_t) _cairo_stroker_spline_to;
1256 if (! _cairo_spline_init (&spline,
1259 &stroker->current_point, b, c, d))
1261 cairo_slope_t fallback_slope;
1262 _cairo_slope_init (&fallback_slope, &stroker->current_point, d);
1263 return line_to (closure, d, &fallback_slope);
1266 /* If the line width is so small that the pen is reduced to a
1267 single point, then we have nothing to do. */
1268 if (stroker->pen.num_vertices <= 1)
1269 return CAIRO_STATUS_SUCCESS;
1271 /* Compute the initial face */
1272 if (! stroker->dash.dashed || stroker->dash.dash_on) {
1273 slope_dx = _cairo_fixed_to_double (spline.initial_slope.dx);
1274 slope_dy = _cairo_fixed_to_double (spline.initial_slope.dy);
1275 if (_compute_normalized_device_slope (&slope_dx, &slope_dy,
1276 stroker->ctm_inverse, NULL))
1278 _compute_face (&stroker->current_point,
1279 &spline.initial_slope,
1283 if (stroker->has_current_face) {
1284 status = _cairo_stroker_join (stroker,
1285 &stroker->current_face, &face);
1286 if (unlikely (status))
1288 } else if (! stroker->has_first_face) {
1289 stroker->first_face = face;
1290 stroker->has_first_face = TRUE;
1293 stroker->current_face = face;
1294 stroker->has_current_face = TRUE;
1297 /* Temporarily modify the stroker to use round joins to guarantee
1298 * smooth stroked curves. */
1299 line_join_save = stroker->style.line_join;
1300 stroker->style.line_join = CAIRO_LINE_JOIN_ROUND;
1302 status = _cairo_spline_decompose (&spline, stroker->tolerance);
1303 if (unlikely (status))
1306 /* And join the final face */
1307 if (! stroker->dash.dashed || stroker->dash.dash_on) {
1308 slope_dx = _cairo_fixed_to_double (spline.final_slope.dx);
1309 slope_dy = _cairo_fixed_to_double (spline.final_slope.dy);
1310 if (_compute_normalized_device_slope (&slope_dx, &slope_dy,
1311 stroker->ctm_inverse, NULL))
1313 _compute_face (&stroker->current_point,
1314 &spline.final_slope,
1319 status = _cairo_stroker_join (stroker, &stroker->current_face, &face);
1320 if (unlikely (status))
1323 stroker->current_face = face;
1326 stroker->style.line_join = line_join_save;
1328 return CAIRO_STATUS_SUCCESS;
1331 static cairo_status_t
1332 _cairo_stroker_close_path (void *closure)
1334 cairo_stroker_t *stroker = closure;
1335 cairo_status_t status;
1337 if (stroker->dash.dashed)
1338 status = _cairo_stroker_line_to_dashed (stroker, &stroker->first_point);
1340 status = _cairo_stroker_line_to (stroker, &stroker->first_point);
1341 if (unlikely (status))
1344 if (stroker->has_first_face && stroker->has_current_face) {
1345 /* Join first and final faces of sub path */
1346 status = _cairo_stroker_join (stroker,
1347 &stroker->current_face,
1348 &stroker->first_face);
1349 if (unlikely (status))
1352 /* Cap the start and end of the sub path as needed */
1353 status = _cairo_stroker_add_caps (stroker);
1354 if (unlikely (status))
1358 stroker->has_initial_sub_path = FALSE;
1359 stroker->has_first_face = FALSE;
1360 stroker->has_current_face = FALSE;
1362 return CAIRO_STATUS_SUCCESS;
1366 _cairo_path_fixed_stroke_to_shaper (cairo_path_fixed_t *path,
1367 const cairo_stroke_style_t *stroke_style,
1368 const cairo_matrix_t *ctm,
1369 const cairo_matrix_t *ctm_inverse,
1371 cairo_status_t (*add_triangle) (void *closure,
1372 const cairo_point_t triangle[3]),
1373 cairo_status_t (*add_triangle_fan) (void *closure,
1374 const cairo_point_t *midpt,
1375 const cairo_point_t *points,
1377 cairo_status_t (*add_convex_quad) (void *closure,
1378 const cairo_point_t quad[4]),
1381 cairo_stroker_t stroker;
1382 cairo_status_t status;
1384 status = _cairo_stroker_init (&stroker, path, stroke_style,
1385 ctm, ctm_inverse, tolerance,
1387 if (unlikely (status))
1390 stroker.add_triangle = add_triangle;
1391 stroker.add_triangle_fan = add_triangle_fan;
1392 stroker.add_convex_quad = add_convex_quad;
1393 stroker.closure = closure;
1395 status = _cairo_path_fixed_interpret (path,
1396 _cairo_stroker_move_to,
1397 stroker.dash.dashed ?
1398 _cairo_stroker_line_to_dashed :
1399 _cairo_stroker_line_to,
1400 _cairo_stroker_curve_to,
1401 _cairo_stroker_close_path,
1404 if (unlikely (status))
1407 /* Cap the start and end of the final sub path as needed */
1408 status = _cairo_stroker_add_caps (&stroker);
1411 _cairo_stroker_fini (&stroker);
1417 _cairo_path_fixed_stroke_dashed_to_polygon (const cairo_path_fixed_t *path,
1418 const cairo_stroke_style_t *stroke_style,
1419 const cairo_matrix_t *ctm,
1420 const cairo_matrix_t *ctm_inverse,
1422 cairo_polygon_t *polygon)
1424 cairo_stroker_t stroker;
1425 cairo_status_t status;
1427 status = _cairo_stroker_init (&stroker, path, stroke_style,
1428 ctm, ctm_inverse, tolerance,
1429 polygon->limits, polygon->num_limits);
1430 if (unlikely (status))
1433 stroker.add_external_edge = _cairo_polygon_add_external_edge,
1434 stroker.closure = polygon;
1436 status = _cairo_path_fixed_interpret (path,
1437 _cairo_stroker_move_to,
1438 stroker.dash.dashed ?
1439 _cairo_stroker_line_to_dashed :
1440 _cairo_stroker_line_to,
1441 _cairo_stroker_curve_to,
1442 _cairo_stroker_close_path,
1445 if (unlikely (status))
1448 /* Cap the start and end of the final sub path as needed */
1449 status = _cairo_stroker_add_caps (&stroker);
1452 _cairo_stroker_fini (&stroker);
1458 _cairo_path_fixed_stroke_to_traps (const cairo_path_fixed_t *path,
1459 const cairo_stroke_style_t *stroke_style,
1460 const cairo_matrix_t *ctm,
1461 const cairo_matrix_t *ctm_inverse,
1463 cairo_traps_t *traps)
1465 cairo_int_status_t status;
1466 cairo_polygon_t polygon;
1468 _cairo_polygon_init (&polygon, traps->limits, traps->num_limits);
1469 status = _cairo_path_fixed_stroke_to_polygon (path,
1475 if (unlikely (status))
1478 status = _cairo_polygon_status (&polygon);
1479 if (unlikely (status))
1482 status = _cairo_bentley_ottmann_tessellate_polygon (traps, &polygon,
1483 CAIRO_FILL_RULE_WINDING);
1486 _cairo_polygon_fini (&polygon);