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
5 * Copyright © 2011 Intel Corporation
7 * This library is free software; you can redistribute it and/or
8 * modify it either under the terms of the GNU Lesser General Public
9 * License version 2.1 as published by the Free Software Foundation
10 * (the "LGPL") or, at your option, under the terms of the Mozilla
11 * Public License Version 1.1 (the "MPL"). If you do not alter this
12 * notice, a recipient may use your version of this file under either
13 * the MPL or the LGPL.
15 * You should have received a copy of the LGPL along with this library
16 * in the file COPYING-LGPL-2.1; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
18 * You should have received a copy of the MPL along with this library
19 * in the file COPYING-MPL-1.1
21 * The contents of this file are subject to the Mozilla Public License
22 * Version 1.1 (the "License"); you may not use this file except in
23 * compliance with the License. You may obtain a copy of the License at
24 * http://www.mozilla.org/MPL/
26 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
27 * OF ANY KIND, either express or implied. See the LGPL or the MPL for
28 * the specific language governing rights and limitations.
30 * The Original Code is the cairo graphics library.
32 * The Initial Developer of the Original Code is University of Southern
36 * Carl D. Worth <cworth@cworth.org>
37 * Chris Wilson <chris@chris-wilson.co.uk>
40 #define _BSD_SOURCE /* for hypot() */
43 #include "cairo-box-inline.h"
44 #include "cairo-boxes-private.h"
45 #include "cairo-contour-inline.h"
46 #include "cairo-contour-private.h"
47 #include "cairo-error-private.h"
48 #include "cairo-path-fixed-private.h"
49 #include "cairo-slope-private.h"
54 cairo_stroke_style_t style
;
60 struct stroke_contour
{
61 /* Note that these are not strictly contours as they may intersect */
62 cairo_contour_t contour
;
64 cairo_uint64_t contour_tolerance
;
65 cairo_polygon_t
*polygon
;
67 const cairo_matrix_t
*ctm
;
68 const cairo_matrix_t
*ctm_inverse
;
70 double spline_cusp_tolerance
;
71 double half_line_width
;
72 cairo_bool_t ctm_det_positive
;
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_bool_t has_bounds
;
91 normalize_slope (double *dx
, double *dy
);
94 compute_face (const cairo_point_t
*point
,
95 const cairo_slope_t
*dev_slope
,
96 struct stroker
*stroker
,
97 cairo_stroke_face_t
*face
);
100 point_distance_sq (const cairo_point_t
*p1
,
101 const cairo_point_t
*p2
)
103 int32_t dx
= p1
->x
- p2
->x
;
104 int32_t dy
= p1
->y
- p2
->y
;
105 return _cairo_int32x32_64_mul (dx
, dx
) + _cairo_int32x32_64_mul (dy
, dy
);
109 within_tolerance (const cairo_point_t
*p1
,
110 const cairo_point_t
*p2
,
111 cairo_uint64_t tolerance
)
114 return _cairo_int64_lt (point_distance_sq (p1
, p2
), tolerance
);
118 contour_add_point (struct stroker
*stroker
,
119 struct stroke_contour
*c
,
120 const cairo_point_t
*point
)
122 if (! within_tolerance (point
, _cairo_contour_last_point (&c
->contour
),
123 stroker
->contour_tolerance
))
124 _cairo_contour_add_point (&c
->contour
, point
);
125 //*_cairo_contour_last_point (&c->contour) = *point;
129 translate_point (cairo_point_t
*point
, const cairo_point_t
*offset
)
131 point
->x
+= offset
->x
;
132 point
->y
+= offset
->y
;
136 slope_compare_sgn (double dx1
, double dy1
, double dx2
, double dy2
)
138 double c
= (dx1
* dy2
- dx2
* dy1
);
141 if (c
< 0) return -1;
146 range_step (int i
, int step
, int max
)
157 * Construct a fan around the midpoint using the vertices from pen between
161 add_fan (struct stroker
*stroker
,
162 const cairo_slope_t
*in_vector
,
163 const cairo_slope_t
*out_vector
,
164 const cairo_point_t
*midpt
,
165 cairo_bool_t clockwise
,
166 struct stroke_contour
*c
)
168 cairo_pen_t
*pen
= &stroker
->pen
;
171 if (stroker
->has_bounds
&&
172 ! _cairo_box_contains_point (&stroker
->bounds
, midpt
))
175 assert (stroker
->pen
.num_vertices
);
178 _cairo_pen_find_active_cw_vertices (pen
,
179 in_vector
, out_vector
,
181 while (start
!= stop
) {
182 cairo_point_t p
= *midpt
;
183 translate_point (&p
, &pen
->vertices
[start
].point
);
184 contour_add_point (stroker
, c
, &p
);
186 if (++start
== pen
->num_vertices
)
190 _cairo_pen_find_active_ccw_vertices (pen
,
191 in_vector
, out_vector
,
193 while (start
!= stop
) {
194 cairo_point_t p
= *midpt
;
195 translate_point (&p
, &pen
->vertices
[start
].point
);
196 contour_add_point (stroker
, c
, &p
);
199 start
+= pen
->num_vertices
;
205 join_is_clockwise (const cairo_stroke_face_t
*in
,
206 const cairo_stroke_face_t
*out
)
208 return _cairo_slope_compare (&in
->dev_vector
, &out
->dev_vector
) < 0;
212 inner_join (struct stroker
*stroker
,
213 const cairo_stroke_face_t
*in
,
214 const cairo_stroke_face_t
*out
,
219 const cairo_point_t
*p
, *outpt
;
220 struct stroke_contour
*inner
;
221 cairo_int64_t d_p
, d_last
;
222 cairo_int64_t half_line_width
;
225 /* XXX line segments shorter than line-width */
228 inner
= &stroker
->ccw
;
232 inner
= &stroker
->cw
;
237 half_line_width
= CAIRO_FIXED_ONE
*CAIRO_FIXED_ONE
/2 * stroker
->style
.line_width
* out
->length
+ .5;
239 /* On the inside, the previous end-point is always
240 * closer to the new face by definition.
242 last
= *_cairo_contour_last_point (&inner
->contour
);
243 d_last
= distance_from_face (out
, &last
, negate
);
244 _cairo_contour_remove_last_point (&inner
->contour
);
247 if (inner
->contour
.chain
.num_points
== 0) {
248 contour_add_point (stroker
, inner
, outpt
);
251 p
= _cairo_contour_last_point (&inner
->contour
);
252 d_p
= distance_from_face (out
, p
, negate
);
253 if (_cairo_int64_lt (d_p
, half_line_width
) &&
254 !_cairo_int64_negative (distance_along_face (out
, p
)))
258 _cairo_contour_remove_last_point (&inner
->contour
);
262 compute_inner_joint (&last
, d_last
, p
, d_p
, half_line_width
);
263 contour_add_point (stroker
, inner
, &last
);
265 const cairo_point_t
*outpt
;
266 struct stroke_contour
*inner
;
269 inner
= &stroker
->ccw
;
272 inner
= &stroker
->cw
;
275 contour_add_point (stroker
, inner
, &in
->point
);
276 contour_add_point (stroker
, inner
, outpt
);
281 inner_close (struct stroker
*stroker
,
282 const cairo_stroke_face_t
*in
,
283 cairo_stroke_face_t
*out
)
287 const cairo_point_t
*p
, *outpt
, *inpt
;
288 struct stroke_contour
*inner
;
289 struct _cairo_contour_chain
*chain
;
291 /* XXX line segments shorter than line-width */
293 if (join_is_clockwise (in
, out
)) {
294 inner
= &stroker
->ccw
;
298 inner
= &stroker
->cw
;
303 if (inner
->contour
.chain
.num_points
== 0) {
304 contour_add_point (stroker
, inner
, &in
->point
);
305 contour_add_point (stroker
, inner
, inpt
);
306 *_cairo_contour_first_point (&inner
->contour
) =
307 *_cairo_contour_last_point (&inner
->contour
);
311 line_width
= stroker
->style
.line_width
/2;
312 line_width
*= CAIRO_FIXED_ONE
;
314 d_last
= sign
* distance_from_face (out
, outpt
);
317 for (chain
= &inner
->contour
.chain
; chain
; chain
= chain
->next
) {
318 for (i
= 0; i
< chain
->num_points
; i
++) {
319 p
= &chain
->points
[i
];
320 if ((d_p
= sign
* distance_from_face (in
, p
)) >= line_width
&&
321 distance_from_edge (stroker
, inpt
, &last
, p
) < line_width
)
326 if (p
->x
!= last
.x
|| p
->y
!= last
.y
) {
335 double dot
= (line_width
- d_last
) / (d_p
- d_last
);
336 last
.x
+= dot
* (p
->x
- last
.x
);
337 last
.y
+= dot
* (p
->y
- last
.y
);
339 *_cairo_contour_last_point (&inner
->contour
) = last
;
341 for (chain
= &inner
->contour
.chain
; chain
; chain
= chain
->next
) {
342 for (i
= 0; i
< chain
->num_points
; i
++) {
343 cairo_point_t
*pp
= &chain
->points
[i
];
350 const cairo_point_t
*inpt
;
351 struct stroke_contour
*inner
;
353 if (join_is_clockwise (in
, out
)) {
354 inner
= &stroker
->ccw
;
357 inner
= &stroker
->cw
;
361 contour_add_point (stroker
, inner
, &in
->point
);
362 contour_add_point (stroker
, inner
, inpt
);
363 *_cairo_contour_first_point (&inner
->contour
) =
364 *_cairo_contour_last_point (&inner
->contour
);
369 outer_close (struct stroker
*stroker
,
370 const cairo_stroke_face_t
*in
,
371 const cairo_stroke_face_t
*out
)
373 const cairo_point_t
*inpt
, *outpt
;
374 struct stroke_contour
*outer
;
377 if (in
->cw
.x
== out
->cw
.x
&& in
->cw
.y
== out
->cw
.y
&&
378 in
->ccw
.x
== out
->ccw
.x
&& in
->ccw
.y
== out
->ccw
.y
)
383 clockwise
= join_is_clockwise (in
, out
);
387 outer
= &stroker
->cw
;
391 outer
= &stroker
->ccw
;
394 if (within_tolerance (inpt
, outpt
, stroker
->contour_tolerance
)) {
395 *_cairo_contour_first_point (&outer
->contour
) =
396 *_cairo_contour_last_point (&outer
->contour
);
400 switch (stroker
->style
.line_join
) {
401 case CAIRO_LINE_JOIN_ROUND
:
402 /* construct a fan around the common midpoint */
403 if ((in
->dev_slope
.x
* out
->dev_slope
.x
+
404 in
->dev_slope
.y
* out
->dev_slope
.y
) < stroker
->spline_cusp_tolerance
)
407 &in
->dev_vector
, &out
->dev_vector
, &in
->point
,
412 case CAIRO_LINE_JOIN_MITER
:
414 /* dot product of incoming slope vector with outgoing slope vector */
415 double in_dot_out
= in
->dev_slope
.x
* out
->dev_slope
.x
+
416 in
->dev_slope
.y
* out
->dev_slope
.y
;
417 double ml
= stroker
->style
.miter_limit
;
419 /* Check the miter limit -- lines meeting at an acute angle
420 * can generate long miters, the limit converts them to bevel
422 * Consider the miter join formed when two line segments
423 * meet at an angle psi:
430 * We can zoom in on the right half of that to see:
448 * The right triangle in that figure, (the line-width side is
449 * shown faintly with three '.' characters), gives us the
450 * following expression relating miter length, angle and line
453 * 1 /sin (psi/2) = miter_length / line_width
455 * The right-hand side of this relationship is the same ratio
456 * in which the miter limit (ml) is expressed. We want to know
457 * when the miter length is within the miter limit. That is
458 * when the following condition holds:
462 * 1 <= ml² sin²(psi/2)
463 * 2 <= ml² 2 sin²(psi/2)
464 * 2·sin²(psi/2) = 1-cos(psi)
465 * 2 <= ml² (1-cos(psi))
467 * in · out = |in| |out| cos (psi)
469 * in and out are both unit vectors, so:
471 * in · out = cos (psi)
473 * 2 <= ml² (1 - in · out)
476 if (2 <= ml
* ml
* (1 + in_dot_out
)) {
477 double x1
, y1
, x2
, y2
;
479 double dx1
, dx2
, dy1
, dy2
;
481 double fdx1
, fdy1
, fdx2
, fdy2
;
485 * we've got the points already transformed to device
486 * space, but need to do some computation with them and
487 * also need to transform the slope from user space to
490 /* outer point of incoming line face */
491 x1
= _cairo_fixed_to_double (inpt
->x
);
492 y1
= _cairo_fixed_to_double (inpt
->y
);
493 dx1
= in
->dev_slope
.x
;
494 dy1
= in
->dev_slope
.y
;
496 /* outer point of outgoing line face */
497 x2
= _cairo_fixed_to_double (outpt
->x
);
498 y2
= _cairo_fixed_to_double (outpt
->y
);
499 dx2
= out
->dev_slope
.x
;
500 dy2
= out
->dev_slope
.y
;
503 * Compute the location of the outer corner of the miter.
504 * That's pretty easy -- just the intersection of the two
505 * outer edges. We've got slopes and points on each
506 * of those edges. Compute my directly, then compute
507 * mx by using the edge with the larger dy; that avoids
508 * dividing by values close to zero.
510 my
= (((x2
- x1
) * dy1
* dy2
- y2
* dx2
* dy1
+ y1
* dx1
* dy2
) /
511 (dx1
* dy2
- dx2
* dy1
));
512 if (fabs (dy1
) >= fabs (dy2
))
513 mx
= (my
- y1
) * dx1
/ dy1
+ x1
;
515 mx
= (my
- y2
) * dx2
/ dy2
+ x2
;
518 * When the two outer edges are nearly parallel, slight
519 * perturbations in the position of the outer points of the lines
520 * caused by representing them in fixed point form can cause the
521 * intersection point of the miter to move a large amount. If
522 * that moves the miter intersection from between the two faces,
523 * then draw a bevel instead.
526 ix
= _cairo_fixed_to_double (in
->point
.x
);
527 iy
= _cairo_fixed_to_double (in
->point
.y
);
529 /* slope of one face */
530 fdx1
= x1
- ix
; fdy1
= y1
- iy
;
532 /* slope of the other face */
533 fdx2
= x2
- ix
; fdy2
= y2
- iy
;
535 /* slope from the intersection to the miter point */
536 mdx
= mx
- ix
; mdy
= my
- iy
;
539 * Make sure the miter point line lies between the two
540 * faces by comparing the slopes
542 if (slope_compare_sgn (fdx1
, fdy1
, mdx
, mdy
) !=
543 slope_compare_sgn (fdx2
, fdy2
, mdx
, mdy
))
547 p
.x
= _cairo_fixed_from_double (mx
);
548 p
.y
= _cairo_fixed_from_double (my
);
550 *_cairo_contour_last_point (&outer
->contour
) = p
;
551 *_cairo_contour_first_point (&outer
->contour
) = p
;
558 case CAIRO_LINE_JOIN_BEVEL
:
561 contour_add_point (stroker
, outer
, outpt
);
565 outer_join (struct stroker
*stroker
,
566 const cairo_stroke_face_t
*in
,
567 const cairo_stroke_face_t
*out
,
570 const cairo_point_t
*inpt
, *outpt
;
571 struct stroke_contour
*outer
;
573 if (in
->cw
.x
== out
->cw
.x
&& in
->cw
.y
== out
->cw
.y
&&
574 in
->ccw
.x
== out
->ccw
.x
&& in
->ccw
.y
== out
->ccw
.y
)
581 outer
= &stroker
->cw
;
585 outer
= &stroker
->ccw
;
588 switch (stroker
->style
.line_join
) {
589 case CAIRO_LINE_JOIN_ROUND
:
590 /* construct a fan around the common midpoint */
592 &in
->dev_vector
, &out
->dev_vector
, &in
->point
,
596 case CAIRO_LINE_JOIN_MITER
:
598 /* dot product of incoming slope vector with outgoing slope vector */
599 double in_dot_out
= in
->dev_slope
.x
* out
->dev_slope
.x
+
600 in
->dev_slope
.y
* out
->dev_slope
.y
;
601 double ml
= stroker
->style
.miter_limit
;
603 /* Check the miter limit -- lines meeting at an acute angle
604 * can generate long miters, the limit converts them to bevel
606 * Consider the miter join formed when two line segments
607 * meet at an angle psi:
614 * We can zoom in on the right half of that to see:
632 * The right triangle in that figure, (the line-width side is
633 * shown faintly with three '.' characters), gives us the
634 * following expression relating miter length, angle and line
637 * 1 /sin (psi/2) = miter_length / line_width
639 * The right-hand side of this relationship is the same ratio
640 * in which the miter limit (ml) is expressed. We want to know
641 * when the miter length is within the miter limit. That is
642 * when the following condition holds:
646 * 1 <= ml² sin²(psi/2)
647 * 2 <= ml² 2 sin²(psi/2)
648 * 2·sin²(psi/2) = 1-cos(psi)
649 * 2 <= ml² (1-cos(psi))
651 * in · out = |in| |out| cos (psi)
653 * in and out are both unit vectors, so:
655 * in · out = cos (psi)
657 * 2 <= ml² (1 - in · out)
660 if (2 <= ml
* ml
* (1 + in_dot_out
)) {
661 double x1
, y1
, x2
, y2
;
663 double dx1
, dx2
, dy1
, dy2
;
665 double fdx1
, fdy1
, fdx2
, fdy2
;
669 * we've got the points already transformed to device
670 * space, but need to do some computation with them and
671 * also need to transform the slope from user space to
674 /* outer point of incoming line face */
675 x1
= _cairo_fixed_to_double (inpt
->x
);
676 y1
= _cairo_fixed_to_double (inpt
->y
);
677 dx1
= in
->dev_slope
.x
;
678 dy1
= in
->dev_slope
.y
;
680 /* outer point of outgoing line face */
681 x2
= _cairo_fixed_to_double (outpt
->x
);
682 y2
= _cairo_fixed_to_double (outpt
->y
);
683 dx2
= out
->dev_slope
.x
;
684 dy2
= out
->dev_slope
.y
;
687 * Compute the location of the outer corner of the miter.
688 * That's pretty easy -- just the intersection of the two
689 * outer edges. We've got slopes and points on each
690 * of those edges. Compute my directly, then compute
691 * mx by using the edge with the larger dy; that avoids
692 * dividing by values close to zero.
694 my
= (((x2
- x1
) * dy1
* dy2
- y2
* dx2
* dy1
+ y1
* dx1
* dy2
) /
695 (dx1
* dy2
- dx2
* dy1
));
696 if (fabs (dy1
) >= fabs (dy2
))
697 mx
= (my
- y1
) * dx1
/ dy1
+ x1
;
699 mx
= (my
- y2
) * dx2
/ dy2
+ x2
;
702 * When the two outer edges are nearly parallel, slight
703 * perturbations in the position of the outer points of the lines
704 * caused by representing them in fixed point form can cause the
705 * intersection point of the miter to move a large amount. If
706 * that moves the miter intersection from between the two faces,
707 * then draw a bevel instead.
710 ix
= _cairo_fixed_to_double (in
->point
.x
);
711 iy
= _cairo_fixed_to_double (in
->point
.y
);
713 /* slope of one face */
714 fdx1
= x1
- ix
; fdy1
= y1
- iy
;
716 /* slope of the other face */
717 fdx2
= x2
- ix
; fdy2
= y2
- iy
;
719 /* slope from the intersection to the miter point */
720 mdx
= mx
- ix
; mdy
= my
- iy
;
723 * Make sure the miter point line lies between the two
724 * faces by comparing the slopes
726 if (slope_compare_sgn (fdx1
, fdy1
, mdx
, mdy
) !=
727 slope_compare_sgn (fdx2
, fdy2
, mdx
, mdy
))
731 p
.x
= _cairo_fixed_from_double (mx
);
732 p
.y
= _cairo_fixed_from_double (my
);
734 *_cairo_contour_last_point (&outer
->contour
) = p
;
741 case CAIRO_LINE_JOIN_BEVEL
:
744 contour_add_point (stroker
,outer
, outpt
);
748 add_cap (struct stroker
*stroker
,
749 const cairo_stroke_face_t
*f
,
750 struct stroke_contour
*c
)
752 switch (stroker
->style
.line_cap
) {
753 case CAIRO_LINE_CAP_ROUND
: {
756 slope
.dx
= -f
->dev_vector
.dx
;
757 slope
.dy
= -f
->dev_vector
.dy
;
759 add_fan (stroker
, &f
->dev_vector
, &slope
, &f
->point
, FALSE
, c
);
763 case CAIRO_LINE_CAP_SQUARE
: {
764 cairo_slope_t fvector
;
768 dx
= f
->usr_vector
.x
;
769 dy
= f
->usr_vector
.y
;
770 dx
*= stroker
->half_line_width
;
771 dy
*= stroker
->half_line_width
;
772 cairo_matrix_transform_distance (stroker
->ctm
, &dx
, &dy
);
773 fvector
.dx
= _cairo_fixed_from_double (dx
);
774 fvector
.dy
= _cairo_fixed_from_double (dy
);
776 p
.x
= f
->ccw
.x
+ fvector
.dx
;
777 p
.y
= f
->ccw
.y
+ fvector
.dy
;
778 contour_add_point (stroker
, c
, &p
);
780 p
.x
= f
->cw
.x
+ fvector
.dx
;
781 p
.y
= f
->cw
.y
+ fvector
.dy
;
782 contour_add_point (stroker
, c
, &p
);
785 case CAIRO_LINE_CAP_BUTT
:
789 contour_add_point (stroker
, c
, &f
->cw
);
793 add_leading_cap (struct stroker
*stroker
,
794 const cairo_stroke_face_t
*face
,
795 struct stroke_contour
*c
)
797 cairo_stroke_face_t reversed
;
802 /* The initial cap needs an outward facing vector. Reverse everything */
803 reversed
.usr_vector
.x
= -reversed
.usr_vector
.x
;
804 reversed
.usr_vector
.y
= -reversed
.usr_vector
.y
;
805 reversed
.dev_vector
.dx
= -reversed
.dev_vector
.dx
;
806 reversed
.dev_vector
.dy
= -reversed
.dev_vector
.dy
;
809 reversed
.cw
= reversed
.ccw
;
812 add_cap (stroker
, &reversed
, c
);
816 add_trailing_cap (struct stroker
*stroker
,
817 const cairo_stroke_face_t
*face
,
818 struct stroke_contour
*c
)
820 add_cap (stroker
, face
, c
);
824 normalize_slope (double *dx
, double *dy
)
826 double dx0
= *dx
, dy0
= *dy
;
829 assert (dx0
!= 0.0 || dy0
!= 0.0);
840 } else if (dy0
== 0.0) {
850 mag
= hypot (dx0
, dy0
);
859 compute_face (const cairo_point_t
*point
,
860 const cairo_slope_t
*dev_slope
,
861 struct stroker
*stroker
,
862 cairo_stroke_face_t
*face
)
864 double face_dx
, face_dy
;
865 cairo_point_t offset_ccw
, offset_cw
;
866 double slope_dx
, slope_dy
;
868 slope_dx
= _cairo_fixed_to_double (dev_slope
->dx
);
869 slope_dy
= _cairo_fixed_to_double (dev_slope
->dy
);
870 face
->length
= normalize_slope (&slope_dx
, &slope_dy
);
871 face
->dev_slope
.x
= slope_dx
;
872 face
->dev_slope
.y
= slope_dy
;
875 * rotate to get a line_width/2 vector along the face, note that
876 * the vector must be rotated the right direction in device space,
877 * but by 90° in user space. So, the rotation depends on
878 * whether the ctm reflects or not, and that can be determined
879 * by looking at the determinant of the matrix.
881 if (! _cairo_matrix_is_identity (stroker
->ctm_inverse
)) {
882 /* Normalize the matrix! */
883 cairo_matrix_transform_distance (stroker
->ctm_inverse
,
884 &slope_dx
, &slope_dy
);
885 normalize_slope (&slope_dx
, &slope_dy
);
887 if (stroker
->ctm_det_positive
) {
888 face_dx
= - slope_dy
* stroker
->half_line_width
;
889 face_dy
= slope_dx
* stroker
->half_line_width
;
891 face_dx
= slope_dy
* stroker
->half_line_width
;
892 face_dy
= - slope_dx
* stroker
->half_line_width
;
895 /* back to device space */
896 cairo_matrix_transform_distance (stroker
->ctm
, &face_dx
, &face_dy
);
898 face_dx
= - slope_dy
* stroker
->half_line_width
;
899 face_dy
= slope_dx
* stroker
->half_line_width
;
902 offset_ccw
.x
= _cairo_fixed_from_double (face_dx
);
903 offset_ccw
.y
= _cairo_fixed_from_double (face_dy
);
904 offset_cw
.x
= -offset_ccw
.x
;
905 offset_cw
.y
= -offset_ccw
.y
;
908 translate_point (&face
->ccw
, &offset_ccw
);
910 face
->point
= *point
;
913 translate_point (&face
->cw
, &offset_cw
);
915 face
->usr_vector
.x
= slope_dx
;
916 face
->usr_vector
.y
= slope_dy
;
918 face
->dev_vector
= *dev_slope
;
922 add_caps (struct stroker
*stroker
)
924 /* check for a degenerative sub_path */
925 if (stroker
->has_initial_sub_path
&&
926 ! stroker
->has_first_face
&&
927 ! stroker
->has_current_face
&&
928 stroker
->style
.line_cap
== CAIRO_LINE_CAP_ROUND
)
930 /* pick an arbitrary slope to use */
931 cairo_slope_t slope
= { CAIRO_FIXED_ONE
, 0 };
932 cairo_stroke_face_t face
;
934 /* arbitrarily choose first_point */
935 compute_face (&stroker
->first_point
, &slope
, stroker
, &face
);
937 add_leading_cap (stroker
, &face
, &stroker
->ccw
);
938 add_trailing_cap (stroker
, &face
, &stroker
->ccw
);
940 /* ensure the circle is complete */
941 _cairo_contour_add_point (&stroker
->ccw
.contour
,
942 _cairo_contour_first_point (&stroker
->ccw
.contour
));
944 _cairo_polygon_add_contour (stroker
->polygon
, &stroker
->ccw
.contour
);
945 _cairo_contour_reset (&stroker
->ccw
.contour
);
947 if (stroker
->has_current_face
)
948 add_trailing_cap (stroker
, &stroker
->current_face
, &stroker
->ccw
);
952 FILE *file
= fopen ("contours.txt", "a");
953 _cairo_debug_print_contour (file
, &stroker
->path
);
954 _cairo_debug_print_contour (file
, &stroker
->cw
.contour
);
955 _cairo_debug_print_contour (file
, &stroker
->ccw
.contour
);
957 _cairo_contour_reset (&stroker
->path
);
961 _cairo_polygon_add_contour (stroker
->polygon
, &stroker
->ccw
.contour
);
962 _cairo_contour_reset (&stroker
->ccw
.contour
);
964 if (stroker
->has_first_face
) {
965 _cairo_contour_add_point (&stroker
->ccw
.contour
,
966 &stroker
->first_face
.cw
);
967 add_leading_cap (stroker
, &stroker
->first_face
, &stroker
->ccw
);
970 FILE *file
= fopen ("contours.txt", "a");
971 _cairo_debug_print_contour (file
, &stroker
->ccw
.contour
);
976 _cairo_polygon_add_contour (stroker
->polygon
,
977 &stroker
->ccw
.contour
);
978 _cairo_contour_reset (&stroker
->ccw
.contour
);
981 _cairo_polygon_add_contour (stroker
->polygon
, &stroker
->cw
.contour
);
982 _cairo_contour_reset (&stroker
->cw
.contour
);
986 static cairo_status_t
987 close_path (void *closure
);
989 static cairo_status_t
990 move_to (void *closure
,
991 const cairo_point_t
*point
)
993 struct stroker
*stroker
= closure
;
995 /* Cap the start and end of the previous sub path as needed */
998 stroker
->has_first_face
= FALSE
;
999 stroker
->has_current_face
= FALSE
;
1000 stroker
->has_initial_sub_path
= FALSE
;
1002 stroker
->first_point
= *point
;
1005 _cairo_contour_add_point (&stroker
->path
, point
);
1008 stroker
->current_face
.point
= *point
;
1010 return CAIRO_STATUS_SUCCESS
;
1013 static cairo_status_t
1014 line_to (void *closure
,
1015 const cairo_point_t
*point
)
1017 struct stroker
*stroker
= closure
;
1018 cairo_stroke_face_t start
;
1019 cairo_point_t
*p1
= &stroker
->current_face
.point
;
1020 cairo_slope_t dev_slope
;
1022 stroker
->has_initial_sub_path
= TRUE
;
1024 if (p1
->x
== point
->x
&& p1
->y
== point
->y
)
1025 return CAIRO_STATUS_SUCCESS
;
1028 _cairo_contour_add_point (&stroker
->path
, point
);
1031 _cairo_slope_init (&dev_slope
, p1
, point
);
1032 compute_face (p1
, &dev_slope
, stroker
, &start
);
1034 if (stroker
->has_current_face
) {
1035 int clockwise
= _cairo_slope_compare (&stroker
->current_face
.dev_vector
,
1038 clockwise
= clockwise
< 0;
1039 /* Join with final face from previous segment */
1040 if (! within_tolerance (&stroker
->current_face
.ccw
, &start
.ccw
,
1041 stroker
->contour_tolerance
) ||
1042 ! within_tolerance (&stroker
->current_face
.cw
, &start
.cw
,
1043 stroker
->contour_tolerance
))
1045 outer_join (stroker
, &stroker
->current_face
, &start
, clockwise
);
1046 inner_join (stroker
, &stroker
->current_face
, &start
, clockwise
);
1050 if (! stroker
->has_first_face
) {
1051 /* Save sub path's first face in case needed for closing join */
1052 stroker
->first_face
= start
;
1053 stroker
->has_first_face
= TRUE
;
1055 stroker
->has_current_face
= TRUE
;
1057 contour_add_point (stroker
, &stroker
->cw
, &start
.cw
);
1058 contour_add_point (stroker
, &stroker
->ccw
, &start
.ccw
);
1061 stroker
->current_face
= start
;
1062 stroker
->current_face
.point
= *point
;
1063 stroker
->current_face
.ccw
.x
+= dev_slope
.dx
;
1064 stroker
->current_face
.ccw
.y
+= dev_slope
.dy
;
1065 stroker
->current_face
.cw
.x
+= dev_slope
.dx
;
1066 stroker
->current_face
.cw
.y
+= dev_slope
.dy
;
1068 contour_add_point (stroker
, &stroker
->cw
, &stroker
->current_face
.cw
);
1069 contour_add_point (stroker
, &stroker
->ccw
, &stroker
->current_face
.ccw
);
1071 return CAIRO_STATUS_SUCCESS
;
1074 static cairo_status_t
1075 spline_to (void *closure
,
1076 const cairo_point_t
*point
,
1077 const cairo_slope_t
*tangent
)
1079 struct stroker
*stroker
= closure
;
1080 cairo_stroke_face_t face
;
1083 _cairo_contour_add_point (&stroker
->path
, point
);
1085 if ((tangent
->dx
| tangent
->dy
) == 0) {
1086 struct stroke_contour
*outer
;
1090 face
= stroker
->current_face
;
1092 face
.usr_vector
.x
= -face
.usr_vector
.x
;
1093 face
.usr_vector
.y
= -face
.usr_vector
.y
;
1094 face
.dev_vector
.dx
= -face
.dev_vector
.dx
;
1095 face
.dev_vector
.dy
= -face
.dev_vector
.dy
;
1101 clockwise
= join_is_clockwise (&stroker
->current_face
, &face
);
1103 outer
= &stroker
->cw
;
1105 outer
= &stroker
->ccw
;
1109 &stroker
->current_face
.dev_vector
,
1111 &stroker
->current_face
.point
,
1114 compute_face (point
, tangent
, stroker
, &face
);
1116 if ((face
.dev_slope
.x
* stroker
->current_face
.dev_slope
.x
+
1117 face
.dev_slope
.y
* stroker
->current_face
.dev_slope
.y
) < stroker
->spline_cusp_tolerance
)
1119 struct stroke_contour
*outer
;
1120 int clockwise
= join_is_clockwise (&stroker
->current_face
, &face
);
1122 stroker
->current_face
.cw
.x
+= face
.point
.x
- stroker
->current_face
.point
.x
;
1123 stroker
->current_face
.cw
.y
+= face
.point
.y
- stroker
->current_face
.point
.y
;
1124 contour_add_point (stroker
, &stroker
->cw
, &stroker
->current_face
.cw
);
1126 stroker
->current_face
.ccw
.x
+= face
.point
.x
- stroker
->current_face
.point
.x
;
1127 stroker
->current_face
.ccw
.y
+= face
.point
.y
- stroker
->current_face
.point
.y
;
1128 contour_add_point (stroker
, &stroker
->ccw
, &stroker
->current_face
.ccw
);
1131 outer
= &stroker
->cw
;
1133 outer
= &stroker
->ccw
;
1136 &stroker
->current_face
.dev_vector
,
1138 &stroker
->current_face
.point
,
1142 contour_add_point (stroker
, &stroker
->cw
, &face
.cw
);
1143 contour_add_point (stroker
, &stroker
->ccw
, &face
.ccw
);
1146 stroker
->current_face
= face
;
1148 return CAIRO_STATUS_SUCCESS
;
1151 static cairo_status_t
1152 curve_to (void *closure
,
1153 const cairo_point_t
*b
,
1154 const cairo_point_t
*c
,
1155 const cairo_point_t
*d
)
1157 struct stroker
*stroker
= closure
;
1158 cairo_spline_t spline
;
1159 cairo_stroke_face_t face
;
1161 if (stroker
->has_bounds
&&
1162 ! _cairo_spline_intersects (&stroker
->current_face
.point
, b
, c
, d
,
1164 return line_to (closure
, d
);
1166 if (! _cairo_spline_init (&spline
, spline_to
, stroker
,
1167 &stroker
->current_face
.point
, b
, c
, d
))
1168 return line_to (closure
, d
);
1170 compute_face (&stroker
->current_face
.point
, &spline
.initial_slope
,
1173 if (stroker
->has_current_face
) {
1174 int clockwise
= join_is_clockwise (&stroker
->current_face
, &face
);
1175 /* Join with final face from previous segment */
1176 outer_join (stroker
, &stroker
->current_face
, &face
, clockwise
);
1177 inner_join (stroker
, &stroker
->current_face
, &face
, clockwise
);
1179 if (! stroker
->has_first_face
) {
1180 /* Save sub path's first face in case needed for closing join */
1181 stroker
->first_face
= face
;
1182 stroker
->has_first_face
= TRUE
;
1184 stroker
->has_current_face
= TRUE
;
1186 contour_add_point (stroker
, &stroker
->cw
, &face
.cw
);
1187 contour_add_point (stroker
, &stroker
->ccw
, &face
.ccw
);
1189 stroker
->current_face
= face
;
1191 return _cairo_spline_decompose (&spline
, stroker
->tolerance
);
1194 static cairo_status_t
1195 close_path (void *closure
)
1197 struct stroker
*stroker
= closure
;
1198 cairo_status_t status
;
1200 status
= line_to (stroker
, &stroker
->first_point
);
1201 if (unlikely (status
))
1204 if (stroker
->has_first_face
&& stroker
->has_current_face
) {
1205 /* Join first and final faces of sub path */
1206 outer_close (stroker
, &stroker
->current_face
, &stroker
->first_face
);
1207 inner_close (stroker
, &stroker
->current_face
, &stroker
->first_face
);
1209 *_cairo_contour_first_point (&stroker
->ccw
.contour
) =
1210 *_cairo_contour_last_point (&stroker
->ccw
.contour
);
1212 *_cairo_contour_first_point (&stroker
->cw
.contour
) =
1213 *_cairo_contour_last_point (&stroker
->cw
.contour
);
1216 _cairo_polygon_add_contour (stroker
->polygon
, &stroker
->cw
.contour
);
1217 _cairo_polygon_add_contour (stroker
->polygon
, &stroker
->ccw
.contour
);
1221 FILE *file
= fopen ("contours.txt", "a");
1222 _cairo_debug_print_contour (file
, &stroker
->path
);
1223 _cairo_debug_print_contour (file
, &stroker
->cw
.contour
);
1224 _cairo_debug_print_contour (file
, &stroker
->ccw
.contour
);
1227 _cairo_contour_reset (&stroker
->path
);
1230 _cairo_contour_reset (&stroker
->cw
.contour
);
1231 _cairo_contour_reset (&stroker
->ccw
.contour
);
1233 /* Cap the start and end of the sub path as needed */
1237 stroker
->has_initial_sub_path
= FALSE
;
1238 stroker
->has_first_face
= FALSE
;
1239 stroker
->has_current_face
= FALSE
;
1241 return CAIRO_STATUS_SUCCESS
;
1245 _cairo_path_fixed_stroke_to_polygon (const cairo_path_fixed_t
*path
,
1246 const cairo_stroke_style_t
*style
,
1247 const cairo_matrix_t
*ctm
,
1248 const cairo_matrix_t
*ctm_inverse
,
1250 cairo_polygon_t
*polygon
)
1252 struct stroker stroker
;
1253 cairo_status_t status
;
1255 if (style
->num_dashes
) {
1256 return _cairo_path_fixed_stroke_dashed_to_polygon (path
,
1264 stroker
.has_bounds
= polygon
->num_limits
;
1265 if (stroker
.has_bounds
) {
1266 /* Extend the bounds in each direction to account for the maximum area
1267 * we might generate trapezoids, to capture line segments that are
1268 * outside of the bounds but which might generate rendering that's
1272 cairo_fixed_t fdx
, fdy
;
1275 stroker
.bounds
= polygon
->limits
[0];
1276 for (i
= 1; i
< polygon
->num_limits
; i
++)
1277 _cairo_box_add_box (&stroker
.bounds
, &polygon
->limits
[i
]);
1279 _cairo_stroke_style_max_distance_from_path (style
, path
, ctm
, &dx
, &dy
);
1280 fdx
= _cairo_fixed_from_double (dx
);
1281 fdy
= _cairo_fixed_from_double (dy
);
1283 stroker
.bounds
.p1
.x
-= fdx
;
1284 stroker
.bounds
.p2
.x
+= fdx
;
1285 stroker
.bounds
.p1
.y
-= fdy
;
1286 stroker
.bounds
.p2
.y
+= fdy
;
1289 stroker
.style
= *style
;
1291 stroker
.ctm_inverse
= ctm_inverse
;
1292 stroker
.tolerance
= tolerance
;
1293 stroker
.half_line_width
= style
->line_width
/ 2.;
1294 /* To test whether we need to join two segments of a spline using
1295 * a round-join or a bevel-join, we can inspect the angle between the
1296 * two segments. If the difference between the chord distance
1297 * (half-line-width times the cosine of the bisection angle) and the
1298 * half-line-width itself is greater than tolerance then we need to
1301 stroker
.spline_cusp_tolerance
= 1 - tolerance
/ stroker
.half_line_width
;
1302 stroker
.spline_cusp_tolerance
*= stroker
.spline_cusp_tolerance
;
1303 stroker
.spline_cusp_tolerance
*= 2;
1304 stroker
.spline_cusp_tolerance
-= 1;
1305 stroker
.ctm_det_positive
=
1306 _cairo_matrix_compute_determinant (ctm
) >= 0.0;
1308 stroker
.pen
.num_vertices
= 0;
1309 if (path
->has_curve_to
||
1310 style
->line_join
== CAIRO_LINE_JOIN_ROUND
||
1311 style
->line_cap
== CAIRO_LINE_CAP_ROUND
) {
1312 status
= _cairo_pen_init (&stroker
.pen
,
1313 stroker
.half_line_width
,
1315 if (unlikely (status
))
1318 /* If the line width is so small that the pen is reduced to a
1319 single point, then we have nothing to do. */
1320 if (stroker
.pen
.num_vertices
<= 1)
1321 return CAIRO_STATUS_SUCCESS
;
1324 stroker
.has_current_face
= FALSE
;
1325 stroker
.has_first_face
= FALSE
;
1326 stroker
.has_initial_sub_path
= FALSE
;
1329 remove ("contours.txt");
1330 remove ("polygons.txt");
1331 _cairo_contour_init (&stroker
.path
, 0);
1333 _cairo_contour_init (&stroker
.cw
.contour
, 1);
1334 _cairo_contour_init (&stroker
.ccw
.contour
, -1);
1335 tolerance
*= CAIRO_FIXED_ONE
;
1336 tolerance
*= tolerance
;
1337 stroker
.contour_tolerance
= tolerance
;
1338 stroker
.polygon
= polygon
;
1340 status
= _cairo_path_fixed_interpret (path
,
1346 /* Cap the start and end of the final sub path as needed */
1347 if (likely (status
== CAIRO_STATUS_SUCCESS
))
1348 add_caps (&stroker
);
1350 _cairo_contour_fini (&stroker
.cw
.contour
);
1351 _cairo_contour_fini (&stroker
.ccw
.contour
);
1352 if (stroker
.pen
.num_vertices
)
1353 _cairo_pen_fini (&stroker
.pen
);
1357 FILE *file
= fopen ("polygons.txt", "a");
1358 _cairo_debug_print_polygon (file
, polygon
);