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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 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>
39
#include "cairo-path-fixed-private.h"
41
typedef struct cairo_stroker {
42
cairo_stroke_style_t *style;
45
cairo_matrix_t *ctm_inverse;
47
double ctm_determinant;
48
cairo_bool_t ctm_det_positive;
54
cairo_point_t current_point;
55
cairo_point_t first_point;
57
cairo_bool_t has_initial_sub_path;
59
cairo_bool_t has_current_face;
60
cairo_stroke_face_t current_face;
62
cairo_bool_t has_first_face;
63
cairo_stroke_face_t first_face;
66
unsigned int dash_index;
68
cairo_bool_t dash_starts_on;
71
cairo_bool_t has_bounds;
75
/* private functions */
77
_cairo_stroker_init (cairo_stroker_t *stroker,
78
cairo_stroke_style_t *stroke_style,
80
cairo_matrix_t *ctm_inverse,
82
cairo_traps_t *traps);
85
_cairo_stroker_fini (cairo_stroker_t *stroker);
88
_cairo_stroker_move_to (void *closure, cairo_point_t *point);
91
_cairo_stroker_line_to (void *closure, cairo_point_t *point);
94
_cairo_stroker_line_to_dashed (void *closure, cairo_point_t *point);
97
_cairo_stroker_curve_to (void *closure,
102
static cairo_status_t
103
_cairo_stroker_curve_to_dashed (void *closure,
108
static cairo_status_t
109
_cairo_stroker_close_path (void *closure);
112
_translate_point (cairo_point_t *point, cairo_point_t *offset);
115
_cairo_stroker_face_clockwise (cairo_stroke_face_t *in, cairo_stroke_face_t *out);
117
static cairo_status_t
118
_cairo_stroker_join (cairo_stroker_t *stroker, cairo_stroke_face_t *in, cairo_stroke_face_t *out);
121
_cairo_stroker_start_dash (cairo_stroker_t *stroker)
124
cairo_bool_t on = TRUE;
127
offset = stroker->style->dash_offset;
129
/* We stop searching for a starting point as soon as the
130
offset reaches zero. Otherwise when an initial dash
131
segment shrinks to zero it will be skipped over. */
132
while (offset > 0.0 && offset >= stroker->style->dash[i]) {
133
offset -= stroker->style->dash[i];
135
if (++i == stroker->style->num_dashes)
138
stroker->dashed = TRUE;
139
stroker->dash_index = i;
140
stroker->dash_on = stroker->dash_starts_on = on;
141
stroker->dash_remain = stroker->style->dash[i] - offset;
145
_cairo_stroker_step_dash (cairo_stroker_t *stroker, double step)
147
stroker->dash_remain -= step;
148
if (stroker->dash_remain <= 0) {
149
stroker->dash_index++;
150
if (stroker->dash_index == stroker->style->num_dashes)
151
stroker->dash_index = 0;
152
stroker->dash_on = !stroker->dash_on;
153
stroker->dash_remain = stroker->style->dash[stroker->dash_index];
157
static cairo_status_t
158
_cairo_stroker_init (cairo_stroker_t *stroker,
159
cairo_stroke_style_t *stroke_style,
161
cairo_matrix_t *ctm_inverse,
163
cairo_traps_t *traps)
165
cairo_status_t status;
166
stroker->style = stroke_style;
168
stroker->ctm_inverse = ctm_inverse;
169
stroker->tolerance = tolerance;
170
stroker->traps = traps;
172
stroker->ctm_determinant = _cairo_matrix_compute_determinant (stroker->ctm);
173
stroker->ctm_det_positive = stroker->ctm_determinant >= 0.0;
175
status = _cairo_pen_init (&stroker->pen,
176
stroke_style->line_width / 2.0,
181
stroker->has_current_face = FALSE;
182
stroker->has_first_face = FALSE;
183
stroker->has_initial_sub_path = FALSE;
185
if (stroker->style->dash)
186
_cairo_stroker_start_dash (stroker);
188
stroker->dashed = FALSE;
190
stroker->has_bounds = _cairo_traps_get_limit (traps, &stroker->bounds);
191
if (stroker->has_bounds) {
192
/* Extend the bounds in each direction to account for the maximum area
193
* we might generate trapezoids, to capture line segments that are outside
194
* of the bounds but which might generate rendering that's within bounds.
197
cairo_fixed_t fdx, fdy;
199
_cairo_stroke_style_max_distance_from_path (stroker->style, stroker->ctm, &dx, &dy);
201
fdx = _cairo_fixed_from_double (dx);
202
fdy = _cairo_fixed_from_double (dy);
204
stroker->bounds.p1.x -= fdx;
205
stroker->bounds.p2.x += fdx;
207
stroker->bounds.p1.y -= fdy;
208
stroker->bounds.p2.y += fdy;
211
return CAIRO_STATUS_SUCCESS;
215
_cairo_stroker_fini (cairo_stroker_t *stroker)
217
_cairo_pen_fini (&stroker->pen);
221
_translate_point (cairo_point_t *point, cairo_point_t *offset)
223
point->x += offset->x;
224
point->y += offset->y;
228
_cairo_stroker_face_clockwise (cairo_stroke_face_t *in, cairo_stroke_face_t *out)
230
cairo_slope_t in_slope, out_slope;
232
_cairo_slope_init (&in_slope, &in->point, &in->cw);
233
_cairo_slope_init (&out_slope, &out->point, &out->cw);
235
return _cairo_slope_compare (&in_slope, &out_slope) < 0;
239
* _cairo_slope_compare_sgn
241
* Return -1, 0 or 1 depending on the relative slopes of
245
_cairo_slope_compare_sgn (double dx1, double dy1, double dx2, double dy2)
247
double c = (dx1 * dy2 - dx2 * dy1);
250
if (c < 0) return -1;
254
static cairo_status_t
255
_cairo_stroker_join (cairo_stroker_t *stroker, cairo_stroke_face_t *in, cairo_stroke_face_t *out)
257
int clockwise = _cairo_stroker_face_clockwise (out, in);
258
cairo_point_t *inpt, *outpt;
259
cairo_status_t status;
261
if (in->cw.x == out->cw.x
262
&& in->cw.y == out->cw.y
263
&& in->ccw.x == out->ccw.x
264
&& in->ccw.y == out->ccw.y)
266
return CAIRO_STATUS_SUCCESS;
277
switch (stroker->style->line_join) {
278
case CAIRO_LINE_JOIN_ROUND: {
280
int start, step, stop;
281
cairo_point_t tri[3];
282
cairo_pen_t *pen = &stroker->pen;
286
_cairo_pen_find_active_ccw_vertex_index (pen, &in->dev_vector, &start);
288
_cairo_pen_find_active_ccw_vertex_index (pen, &out->dev_vector, &stop);
290
_cairo_pen_find_active_cw_vertex_index (pen, &in->dev_vector, &start);
292
_cairo_pen_find_active_cw_vertex_index (pen, &out->dev_vector, &stop);
299
_translate_point (&tri[2], &pen->vertices[i].point);
300
status = _cairo_traps_tessellate_triangle (stroker->traps, tri);
306
i = pen->num_vertices - 1;
307
if (i >= pen->num_vertices)
313
return _cairo_traps_tessellate_triangle (stroker->traps, tri);
315
case CAIRO_LINE_JOIN_MITER:
317
/* dot product of incoming slope vector with outgoing slope vector */
318
double in_dot_out = ((-in->usr_vector.x * out->usr_vector.x)+
319
(-in->usr_vector.y * out->usr_vector.y));
320
double ml = stroker->style->miter_limit;
322
/* Check the miter limit -- lines meeting at an acute angle
323
* can generate long miters, the limit converts them to bevel
325
* Consider the miter join formed when two line segments
326
* meet at an angle psi:
333
* We can zoom in on the right half of that to see:
351
* The right triangle in that figure, (the line-width side is
352
* shown faintly with three '.' characters), gives us the
353
* following expression relating miter length, angle and line
356
* 1 /sin (psi/2) = miter_length / line_width
358
* The right-hand side of this relationship is the same ratio
359
* in which the miter limit (ml) is expressed. We want to know
360
* when the miter length is within the miter limit. That is
361
* when the following condition holds:
365
* 1 <= ml² sin²(psi/2)
366
* 2 <= ml² 2 sin²(psi/2)
367
* 2·sin²(psi/2) = 1-cos(psi)
368
* 2 <= ml² (1-cos(psi))
370
* in · out = |in| |out| cos (psi)
372
* in and out are both unit vectors, so:
374
* in · out = cos (psi)
376
* 2 <= ml² (1 - in · out)
379
if (2 <= ml * ml * (1 - in_dot_out))
381
double x1, y1, x2, y2;
383
double dx1, dx2, dy1, dy2;
385
cairo_point_t quad[4];
387
double fdx1, fdy1, fdx2, fdy2;
391
* we've got the points already transformed to device
392
* space, but need to do some computation with them and
393
* also need to transform the slope from user space to
396
/* outer point of incoming line face */
397
x1 = _cairo_fixed_to_double (inpt->x);
398
y1 = _cairo_fixed_to_double (inpt->y);
399
dx1 = in->usr_vector.x;
400
dy1 = in->usr_vector.y;
401
cairo_matrix_transform_distance (stroker->ctm, &dx1, &dy1);
403
/* outer point of outgoing line face */
404
x2 = _cairo_fixed_to_double (outpt->x);
405
y2 = _cairo_fixed_to_double (outpt->y);
406
dx2 = out->usr_vector.x;
407
dy2 = out->usr_vector.y;
408
cairo_matrix_transform_distance (stroker->ctm, &dx2, &dy2);
411
* Compute the location of the outer corner of the miter.
412
* That's pretty easy -- just the intersection of the two
413
* outer edges. We've got slopes and points on each
414
* of those edges. Compute my directly, then compute
415
* mx by using the edge with the larger dy; that avoids
416
* dividing by values close to zero.
418
my = (((x2 - x1) * dy1 * dy2 - y2 * dx2 * dy1 + y1 * dx1 * dy2) /
419
(dx1 * dy2 - dx2 * dy1));
420
if (fabs (dy1) >= fabs (dy2))
421
mx = (my - y1) * dx1 / dy1 + x1;
423
mx = (my - y2) * dx2 / dy2 + x2;
426
* When the two outer edges are nearly parallel, slight
427
* perturbations in the position of the outer points of the lines
428
* caused by representing them in fixed point form can cause the
429
* intersection point of the miter to move a large amount. If
430
* that moves the miter intersection from between the two faces,
431
* then draw a bevel instead.
434
ix = _cairo_fixed_to_double (in->point.x);
435
iy = _cairo_fixed_to_double (in->point.y);
437
/* slope of one face */
438
fdx1 = x1 - ix; fdy1 = y1 - iy;
440
/* slope of the other face */
441
fdx2 = x2 - ix; fdy2 = y2 - iy;
443
/* slope from the intersection to the miter point */
444
mdx = mx - ix; mdy = my - iy;
447
* Make sure the miter point line lies between the two
448
* faces by comparing the slopes
450
if (_cairo_slope_compare_sgn (fdx1, fdy1, mdx, mdy) !=
451
_cairo_slope_compare_sgn (fdx2, fdy2, mdx, mdy))
454
* Draw the quadrilateral
456
outer.x = _cairo_fixed_from_double (mx);
457
outer.y = _cairo_fixed_from_double (my);
464
return _cairo_traps_tessellate_convex_quad (stroker->traps, quad);
467
/* fall through ... */
469
case CAIRO_LINE_JOIN_BEVEL: {
470
cairo_point_t tri[3];
475
return _cairo_traps_tessellate_triangle (stroker->traps, tri);
480
static cairo_status_t
481
_cairo_stroker_add_cap (cairo_stroker_t *stroker, cairo_stroke_face_t *f)
483
cairo_status_t status;
485
if (stroker->style->line_cap == CAIRO_LINE_CAP_BUTT)
486
return CAIRO_STATUS_SUCCESS;
488
switch (stroker->style->line_cap) {
489
case CAIRO_LINE_CAP_ROUND: {
493
cairo_point_t tri[3];
494
cairo_pen_t *pen = &stroker->pen;
496
slope = f->dev_vector;
497
_cairo_pen_find_active_cw_vertex_index (pen, &slope, &start);
498
slope.dx = -slope.dx;
499
slope.dy = -slope.dy;
500
_cairo_pen_find_active_cw_vertex_index (pen, &slope, &stop);
504
for (i=start; i != stop; i = (i+1) % pen->num_vertices) {
506
_translate_point (&tri[2], &pen->vertices[i].point);
507
status = _cairo_traps_tessellate_triangle (stroker->traps, tri);
514
return _cairo_traps_tessellate_triangle (stroker->traps, tri);
516
case CAIRO_LINE_CAP_SQUARE: {
518
cairo_slope_t fvector;
519
cairo_point_t occw, ocw;
520
cairo_polygon_t polygon;
522
dx = f->usr_vector.x;
523
dy = f->usr_vector.y;
524
dx *= stroker->style->line_width / 2.0;
525
dy *= stroker->style->line_width / 2.0;
526
cairo_matrix_transform_distance (stroker->ctm, &dx, &dy);
527
fvector.dx = _cairo_fixed_from_double (dx);
528
fvector.dy = _cairo_fixed_from_double (dy);
529
occw.x = f->ccw.x + fvector.dx;
530
occw.y = f->ccw.y + fvector.dy;
531
ocw.x = f->cw.x + fvector.dx;
532
ocw.y = f->cw.y + fvector.dy;
534
_cairo_polygon_init (&polygon);
535
_cairo_polygon_move_to (&polygon, &f->cw);
536
_cairo_polygon_line_to (&polygon, &ocw);
537
_cairo_polygon_line_to (&polygon, &occw);
538
_cairo_polygon_line_to (&polygon, &f->ccw);
539
_cairo_polygon_close (&polygon);
540
status = _cairo_polygon_status (&polygon);
542
if (status == CAIRO_STATUS_SUCCESS) {
543
status = _cairo_bentley_ottmann_tessellate_polygon (stroker->traps,
545
CAIRO_FILL_RULE_WINDING);
548
_cairo_polygon_fini (&polygon);
552
case CAIRO_LINE_CAP_BUTT:
554
return CAIRO_STATUS_SUCCESS;
558
static cairo_status_t
559
_cairo_stroker_add_leading_cap (cairo_stroker_t *stroker,
560
cairo_stroke_face_t *face)
562
cairo_stroke_face_t reversed;
567
/* The initial cap needs an outward facing vector. Reverse everything */
568
reversed.usr_vector.x = -reversed.usr_vector.x;
569
reversed.usr_vector.y = -reversed.usr_vector.y;
570
reversed.dev_vector.dx = -reversed.dev_vector.dx;
571
reversed.dev_vector.dy = -reversed.dev_vector.dy;
573
reversed.cw = reversed.ccw;
576
return _cairo_stroker_add_cap (stroker, &reversed);
579
static cairo_status_t
580
_cairo_stroker_add_trailing_cap (cairo_stroker_t *stroker,
581
cairo_stroke_face_t *face)
583
return _cairo_stroker_add_cap (stroker, face);
586
static inline cairo_bool_t
587
_compute_normalized_device_slope (double *dx, double *dy, cairo_matrix_t *ctm_inverse, double *mag_out)
589
double dx0 = *dx, dy0 = *dy;
592
cairo_matrix_transform_distance (ctm_inverse, &dx0, &dy0);
594
if (dx0 == 0.0 && dy0 == 0.0) {
609
} else if (dy0 == 0.0) {
619
mag = sqrt (dx0 * dx0 + dy0 * dy0);
631
_compute_face (cairo_point_t *point, cairo_slope_t *dev_slope,
632
double slope_dx, double slope_dy,
633
cairo_stroker_t *stroker, cairo_stroke_face_t *face);
635
static cairo_status_t
636
_cairo_stroker_add_caps (cairo_stroker_t *stroker)
638
cairo_status_t status;
639
/* check for a degenerative sub_path */
640
if (stroker->has_initial_sub_path
641
&& !stroker->has_first_face
642
&& !stroker->has_current_face
643
&& stroker->style->line_cap == CAIRO_LINE_JOIN_ROUND)
645
/* pick an arbitrary slope to use */
646
double dx = 1.0, dy = 0.0;
647
cairo_slope_t slope = { CAIRO_FIXED_ONE, 0 };
648
cairo_stroke_face_t face;
650
_compute_normalized_device_slope (&dx, &dy, stroker->ctm_inverse, NULL);
652
/* arbitrarily choose first_point
653
* first_point and current_point should be the same */
654
_compute_face (&stroker->first_point, &slope, dx, dy, stroker, &face);
656
status = _cairo_stroker_add_leading_cap (stroker, &face);
659
status = _cairo_stroker_add_trailing_cap (stroker, &face);
664
if (stroker->has_first_face) {
665
status = _cairo_stroker_add_leading_cap (stroker, &stroker->first_face);
670
if (stroker->has_current_face) {
671
status = _cairo_stroker_add_trailing_cap (stroker, &stroker->current_face);
676
return CAIRO_STATUS_SUCCESS;
680
_compute_face (cairo_point_t *point, cairo_slope_t *dev_slope,
681
double slope_dx, double slope_dy,
682
cairo_stroker_t *stroker, cairo_stroke_face_t *face)
684
double face_dx, face_dy;
685
cairo_point_t offset_ccw, offset_cw;
688
* rotate to get a line_width/2 vector along the face, note that
689
* the vector must be rotated the right direction in device space,
690
* but by 90° in user space. So, the rotation depends on
691
* whether the ctm reflects or not, and that can be determined
692
* by looking at the determinant of the matrix.
694
if (stroker->ctm_det_positive)
696
face_dx = - slope_dy * (stroker->style->line_width / 2.0);
697
face_dy = slope_dx * (stroker->style->line_width / 2.0);
701
face_dx = slope_dy * (stroker->style->line_width / 2.0);
702
face_dy = - slope_dx * (stroker->style->line_width / 2.0);
705
/* back to device space */
706
cairo_matrix_transform_distance (stroker->ctm, &face_dx, &face_dy);
708
offset_ccw.x = _cairo_fixed_from_double (face_dx);
709
offset_ccw.y = _cairo_fixed_from_double (face_dy);
710
offset_cw.x = -offset_ccw.x;
711
offset_cw.y = -offset_ccw.y;
714
_translate_point (&face->ccw, &offset_ccw);
716
face->point = *point;
719
_translate_point (&face->cw, &offset_cw);
721
face->usr_vector.x = slope_dx;
722
face->usr_vector.y = slope_dy;
724
face->dev_vector = *dev_slope;
727
static cairo_status_t
728
_cairo_stroker_add_sub_edge (cairo_stroker_t *stroker, cairo_point_t *p1, cairo_point_t *p2,
729
cairo_slope_t *dev_slope, double slope_dx, double slope_dy,
730
cairo_stroke_face_t *start, cairo_stroke_face_t *end)
732
cairo_point_t rectangle[4];
734
_compute_face (p1, dev_slope, slope_dx, slope_dy, stroker, start);
736
/* XXX: This could be optimized slightly by not calling
737
_compute_face again but rather translating the relevant
738
fields from start. */
739
_compute_face (p2, dev_slope, slope_dx, slope_dy, stroker, end);
741
if (p1->x == p2->x && p1->y == p2->y)
742
return CAIRO_STATUS_SUCCESS;
744
rectangle[0] = start->cw;
745
rectangle[1] = start->ccw;
746
rectangle[2] = end->ccw;
747
rectangle[3] = end->cw;
749
return _cairo_traps_tessellate_convex_quad (stroker->traps, rectangle);
752
static cairo_status_t
753
_cairo_stroker_move_to (void *closure, cairo_point_t *point)
755
cairo_status_t status;
756
cairo_stroker_t *stroker = closure;
758
/* Cap the start and end of the previous sub path as needed */
759
status = _cairo_stroker_add_caps (stroker);
763
stroker->first_point = *point;
764
stroker->current_point = *point;
766
stroker->has_first_face = FALSE;
767
stroker->has_current_face = FALSE;
768
stroker->has_initial_sub_path = FALSE;
770
return CAIRO_STATUS_SUCCESS;
773
static cairo_status_t
774
_cairo_stroker_move_to_dashed (void *closure, cairo_point_t *point)
776
/* reset the dash pattern for new sub paths */
777
cairo_stroker_t *stroker = closure;
778
_cairo_stroker_start_dash (stroker);
780
return _cairo_stroker_move_to (closure, point);
783
static cairo_status_t
784
_cairo_stroker_line_to (void *closure, cairo_point_t *point)
786
cairo_status_t status;
787
cairo_stroker_t *stroker = closure;
788
cairo_stroke_face_t start, end;
789
cairo_point_t *p1 = &stroker->current_point;
790
cairo_point_t *p2 = point;
791
cairo_slope_t dev_slope;
792
double slope_dx, slope_dy;
794
stroker->has_initial_sub_path = TRUE;
796
if (p1->x == p2->x && p1->y == p2->y)
797
return CAIRO_STATUS_SUCCESS;
799
_cairo_slope_init (&dev_slope, p1, p2);
800
slope_dx = _cairo_fixed_to_double (p2->x - p1->x);
801
slope_dy = _cairo_fixed_to_double (p2->y - p1->y);
802
_compute_normalized_device_slope (&slope_dx, &slope_dy, stroker->ctm_inverse, NULL);
804
status = _cairo_stroker_add_sub_edge (stroker, p1, p2, &dev_slope, slope_dx, slope_dy, &start, &end);
808
if (stroker->has_current_face) {
809
/* Join with final face from previous segment */
810
status = _cairo_stroker_join (stroker, &stroker->current_face, &start);
813
} else if (!stroker->has_first_face) {
814
/* Save sub path's first face in case needed for closing join */
815
stroker->first_face = start;
816
stroker->has_first_face = TRUE;
818
stroker->current_face = end;
819
stroker->has_current_face = TRUE;
821
stroker->current_point = *point;
823
return CAIRO_STATUS_SUCCESS;
827
* Dashed lines. Cap each dash end, join around turns when on
829
static cairo_status_t
830
_cairo_stroker_line_to_dashed (void *closure, cairo_point_t *point)
832
cairo_status_t status = CAIRO_STATUS_SUCCESS;
833
cairo_stroker_t *stroker = closure;
834
double mag, remain, step_length = 0;
835
double slope_dx, slope_dy;
837
cairo_stroke_face_t sub_start, sub_end;
838
cairo_point_t *p1 = &stroker->current_point;
839
cairo_point_t *p2 = point;
840
cairo_slope_t dev_slope;
841
cairo_bool_t fully_in_bounds = TRUE;
842
cairo_line_t segment;
844
stroker->has_initial_sub_path = stroker->dash_starts_on;
846
if (p1->x == p2->x && p1->y == p2->y)
847
return CAIRO_STATUS_SUCCESS;
849
if (stroker->has_bounds &&
850
(!_cairo_box_contains_point (&stroker->bounds, p1) ||
851
!_cairo_box_contains_point (&stroker->bounds, p2)))
853
fully_in_bounds = FALSE;
856
_cairo_slope_init (&dev_slope, p1, p2);
858
slope_dx = _cairo_fixed_to_double (p2->x - p1->x);
859
slope_dy = _cairo_fixed_to_double (p2->y - p1->y);
861
if (!_compute_normalized_device_slope (&slope_dx, &slope_dy, stroker->ctm_inverse, &mag))
862
return CAIRO_STATUS_SUCCESS;
867
step_length = MIN (stroker->dash_remain, remain);
868
remain -= step_length;
869
dx2 = slope_dx * (mag - remain);
870
dy2 = slope_dy * (mag - remain);
871
cairo_matrix_transform_distance (stroker->ctm, &dx2, &dy2);
872
segment.p2.x = _cairo_fixed_from_double (dx2) + p1->x;
873
segment.p2.y = _cairo_fixed_from_double (dy2) + p1->y;
875
if (fully_in_bounds ||
876
_cairo_box_intersects_line_segment (&stroker->bounds, &segment))
878
if (stroker->dash_on) {
879
status = _cairo_stroker_add_sub_edge (stroker, &segment.p1, &segment.p2, &dev_slope, slope_dx, slope_dy, &sub_start, &sub_end);
883
if (stroker->has_current_face) {
884
/* Join with final face from previous segment */
885
status = _cairo_stroker_join (stroker, &stroker->current_face, &sub_start);
886
stroker->has_current_face = FALSE;
889
} else if (!stroker->has_first_face && stroker->dash_starts_on) {
890
/* Save sub path's first face in case needed for closing join */
891
stroker->first_face = sub_start;
892
stroker->has_first_face = TRUE;
894
/* Cap dash start if not connecting to a previous segment */
895
status = _cairo_stroker_add_leading_cap (stroker, &sub_start);
901
/* Cap dash end if not at end of segment */
902
status = _cairo_stroker_add_trailing_cap (stroker, &sub_end);
906
stroker->current_face = sub_end;
907
stroker->has_current_face = TRUE;
910
if (stroker->has_current_face) {
911
/* Cap final face from previous segment */
912
status = _cairo_stroker_add_trailing_cap (stroker, &stroker->current_face);
915
stroker->has_current_face = FALSE;
919
if (stroker->has_current_face) {
920
/* Cap final face from previous segment */
921
status = _cairo_stroker_add_trailing_cap (stroker, &stroker->current_face);
924
stroker->has_current_face = FALSE;
928
_cairo_stroker_step_dash (stroker, step_length);
929
segment.p1 = segment.p2;
932
if (stroker->dash_on && !stroker->has_current_face) {
933
/* This segment ends on a transition to dash_on, compute a new face
934
* and add cap for the begining of the next dash_on step.
936
* Note: this will create a degenerate cap if this is not the last line
937
* in the path. Whether this behaviour is desirable or not is debatable.
938
* On one side these degnerate caps can not be reproduced with regular path stroking.
939
* On the other side Acroread 7 also produces the degenerate caps. */
940
_compute_face (point, &dev_slope, slope_dx, slope_dy, stroker, &stroker->current_face);
941
stroker->has_current_face = TRUE;
942
status = _cairo_stroker_add_leading_cap (stroker, &stroker->current_face);
947
stroker->current_point = *point;
952
static cairo_status_t
953
_cairo_stroker_curve_to (void *closure,
958
cairo_status_t status = CAIRO_STATUS_SUCCESS;
959
cairo_stroker_t *stroker = closure;
960
cairo_spline_t spline;
962
cairo_stroke_face_t start, end;
963
cairo_point_t extra_points[4];
964
cairo_point_t *a = &stroker->current_point;
965
double initial_slope_dx, initial_slope_dy;
966
double final_slope_dx, final_slope_dy;
968
status = _cairo_spline_init (&spline, a, b, c, d);
969
if (status == CAIRO_INT_STATUS_DEGENERATE)
970
return _cairo_stroker_line_to (closure, d);
972
status = _cairo_pen_init_copy (&pen, &stroker->pen);
976
initial_slope_dx = _cairo_fixed_to_double (spline.initial_slope.dx);
977
initial_slope_dy = _cairo_fixed_to_double (spline.initial_slope.dy);
978
final_slope_dx = _cairo_fixed_to_double (spline.final_slope.dx);
979
final_slope_dy = _cairo_fixed_to_double (spline.final_slope.dy);
981
if (_compute_normalized_device_slope (&initial_slope_dx, &initial_slope_dy, stroker->ctm_inverse, NULL))
982
_compute_face (a, &spline.initial_slope, initial_slope_dx, initial_slope_dy, stroker, &start);
984
if (_compute_normalized_device_slope (&final_slope_dx, &final_slope_dy, stroker->ctm_inverse, NULL))
985
_compute_face (d, &spline.final_slope, final_slope_dx, final_slope_dy, stroker, &end);
987
if (stroker->has_current_face) {
988
status = _cairo_stroker_join (stroker, &stroker->current_face, &start);
991
} else if (!stroker->has_first_face) {
992
stroker->first_face = start;
993
stroker->has_first_face = TRUE;
995
stroker->current_face = end;
996
stroker->has_current_face = TRUE;
998
extra_points[0] = start.cw;
999
extra_points[0].x -= start.point.x;
1000
extra_points[0].y -= start.point.y;
1001
extra_points[1] = start.ccw;
1002
extra_points[1].x -= start.point.x;
1003
extra_points[1].y -= start.point.y;
1004
extra_points[2] = end.cw;
1005
extra_points[2].x -= end.point.x;
1006
extra_points[2].y -= end.point.y;
1007
extra_points[3] = end.ccw;
1008
extra_points[3].x -= end.point.x;
1009
extra_points[3].y -= end.point.y;
1011
status = _cairo_pen_add_points (&pen, extra_points, 4);
1015
status = _cairo_pen_stroke_spline (&pen, &spline, stroker->tolerance, stroker->traps);
1020
_cairo_pen_fini (&pen);
1022
_cairo_spline_fini (&spline);
1024
stroker->current_point = *d;
1029
/* We're using two different algorithms here for dashed and un-dashed
1030
* splines. The dashed algorithm uses the existing line dashing
1031
* code. It's linear in path length, but gets subtly wrong results for
1032
* self-intersecting paths (an outstanding but for self-intersecting
1033
* non-curved paths as well). The non-dashed algorithm tessellates a
1034
* single polygon for the whole curve. It handles the
1035
* self-intersecting problem, but it's (unsurprisingly) not O(n) and
1036
* more significantly, it doesn't yet handle dashes.
1038
* The only reason we're doing split algorithms here is to
1039
* minimize the impact of fixing the splines-aren't-dashed bug for
1040
* 1.0.2. Long-term the right answer is to rewrite the whole pile
1041
* of stroking code so that the entire result is computed as a
1042
* single polygon that is tessellated, (that is, stroking can be
1043
* built on top of filling). That will solve the self-intersecting
1044
* problem. It will also increase the importance of implementing
1045
* an efficient and more robust tessellator.
1047
static cairo_status_t
1048
_cairo_stroker_curve_to_dashed (void *closure,
1053
cairo_status_t status = CAIRO_STATUS_SUCCESS;
1054
cairo_stroker_t *stroker = closure;
1055
cairo_spline_t spline;
1056
cairo_point_t *a = &stroker->current_point;
1057
cairo_line_join_t line_join_save;
1060
status = _cairo_spline_init (&spline, a, b, c, d);
1061
if (status == CAIRO_INT_STATUS_DEGENERATE)
1062
return _cairo_stroker_line_to_dashed (closure, d);
1064
/* If the line width is so small that the pen is reduced to a
1065
single point, then we have nothing to do. */
1066
if (stroker->pen.num_vertices <= 1)
1067
goto CLEANUP_SPLINE;
1069
/* Temporarily modify the stroker to use round joins to guarantee
1070
* smooth stroked curves. */
1071
line_join_save = stroker->style->line_join;
1072
stroker->style->line_join = CAIRO_LINE_JOIN_ROUND;
1074
status = _cairo_spline_decompose (&spline, stroker->tolerance);
1076
goto CLEANUP_GSTATE;
1078
for (i = 1; i < spline.num_points; i++) {
1079
if (stroker->dashed)
1080
status = _cairo_stroker_line_to_dashed (stroker, &spline.points[i]);
1082
status = _cairo_stroker_line_to (stroker, &spline.points[i]);
1088
stroker->style->line_join = line_join_save;
1091
_cairo_spline_fini (&spline);
1096
static cairo_status_t
1097
_cairo_stroker_close_path (void *closure)
1099
cairo_status_t status;
1100
cairo_stroker_t *stroker = closure;
1102
if (stroker->dashed)
1103
status = _cairo_stroker_line_to_dashed (stroker, &stroker->first_point);
1105
status = _cairo_stroker_line_to (stroker, &stroker->first_point);
1109
if (stroker->has_first_face && stroker->has_current_face) {
1110
/* Join first and final faces of sub path */
1111
status = _cairo_stroker_join (stroker, &stroker->current_face, &stroker->first_face);
1115
/* Cap the start and end of the sub path as needed */
1116
status = _cairo_stroker_add_caps (stroker);
1121
stroker->has_initial_sub_path = FALSE;
1122
stroker->has_first_face = FALSE;
1123
stroker->has_current_face = FALSE;
1125
return CAIRO_STATUS_SUCCESS;
1128
static cairo_int_status_t
1129
_cairo_path_fixed_stroke_rectilinear (cairo_path_fixed_t *path,
1130
cairo_stroke_style_t *stroke_style,
1131
cairo_matrix_t *ctm,
1132
cairo_traps_t *traps);
1135
_cairo_path_fixed_stroke_to_traps (cairo_path_fixed_t *path,
1136
cairo_stroke_style_t *stroke_style,
1137
cairo_matrix_t *ctm,
1138
cairo_matrix_t *ctm_inverse,
1140
cairo_traps_t *traps)
1142
cairo_status_t status;
1143
cairo_stroker_t stroker;
1145
/* Before we do anything else, we attempt the rectilinear
1146
* stroker. It's careful to generate trapezoids that align to
1147
* device-pixel boundaries when possible. Many backends can render
1148
* those much faster than non-aligned trapezoids, (by using clip
1150
status = _cairo_path_fixed_stroke_rectilinear (path,
1154
if (status != CAIRO_INT_STATUS_UNSUPPORTED)
1157
status = _cairo_stroker_init (&stroker, stroke_style,
1158
ctm, ctm_inverse, tolerance,
1163
if (stroker.style->dash)
1164
status = _cairo_path_fixed_interpret (path,
1165
CAIRO_DIRECTION_FORWARD,
1166
_cairo_stroker_move_to_dashed,
1167
_cairo_stroker_line_to_dashed,
1168
_cairo_stroker_curve_to_dashed,
1169
_cairo_stroker_close_path,
1172
status = _cairo_path_fixed_interpret (path,
1173
CAIRO_DIRECTION_FORWARD,
1174
_cairo_stroker_move_to,
1175
_cairo_stroker_line_to,
1176
_cairo_stroker_curve_to,
1177
_cairo_stroker_close_path,
1182
/* Cap the start and end of the final sub path as needed */
1183
status = _cairo_stroker_add_caps (&stroker);
1186
_cairo_stroker_fini (&stroker);
1191
typedef struct _cairo_rectilinear_stroker
1193
cairo_stroke_style_t *stroke_style;
1194
cairo_fixed_t half_line_width;
1195
cairo_traps_t *traps;
1196
cairo_point_t current_point;
1197
cairo_point_t first_point;
1198
cairo_bool_t open_sub_path;
1201
cairo_line_t *segments;
1202
cairo_line_t segments_embedded[8]; /* common case is a single rectangle */
1203
} cairo_rectilinear_stroker_t;
1206
_cairo_rectilinear_stroker_init (cairo_rectilinear_stroker_t *stroker,
1207
cairo_stroke_style_t *stroke_style,
1208
cairo_traps_t *traps)
1210
stroker->stroke_style = stroke_style;
1211
stroker->half_line_width =
1212
_cairo_fixed_from_double (stroke_style->line_width / 2.0);
1213
stroker->traps = traps;
1214
stroker->open_sub_path = FALSE;
1215
stroker->segments = stroker->segments_embedded;
1216
stroker->segments_size = ARRAY_LENGTH (stroker->segments_embedded);
1217
stroker->num_segments = 0;
1221
_cairo_rectilinear_stroker_fini (cairo_rectilinear_stroker_t *stroker)
1223
if (stroker->segments != stroker->segments_embedded)
1224
free (stroker->segments);
1227
static cairo_status_t
1228
_cairo_rectilinear_stroker_add_segment (cairo_rectilinear_stroker_t *stroker,
1233
if (stroker->num_segments == stroker->segments_size) {
1234
int new_size = stroker->segments_size * 2;
1235
cairo_line_t *new_segments;
1237
if (stroker->segments == stroker->segments_embedded) {
1238
new_segments = _cairo_malloc_ab (new_size, sizeof (cairo_line_t));
1239
if (new_segments == NULL)
1240
return _cairo_error (CAIRO_STATUS_NO_MEMORY);
1242
memcpy (new_segments, stroker->segments,
1243
stroker->num_segments * sizeof (cairo_line_t));
1245
new_segments = _cairo_realloc_ab (stroker->segments,
1246
new_size, sizeof (cairo_line_t));
1247
if (new_segments == NULL)
1248
return _cairo_error (CAIRO_STATUS_NO_MEMORY);
1251
stroker->segments_size = new_size;
1252
stroker->segments = new_segments;
1255
stroker->segments[stroker->num_segments].p1 = *p1;
1256
stroker->segments[stroker->num_segments].p2 = *p2;
1257
stroker->num_segments++;
1259
return CAIRO_STATUS_SUCCESS;
1262
static cairo_status_t
1263
_cairo_rectilinear_stroker_emit_segments (cairo_rectilinear_stroker_t *stroker)
1265
cairo_status_t status;
1266
cairo_line_cap_t line_cap = stroker->stroke_style->line_cap;
1267
cairo_fixed_t half_line_width = stroker->half_line_width;
1270
for (i = 0; i < stroker->num_segments; i++) {
1271
cairo_point_t *a, *b;
1272
cairo_bool_t lengthen_initial, shorten_final, lengthen_final;
1274
a = &stroker->segments[i].p1;
1275
b = &stroker->segments[i].p2;
1277
/* For each segment we generate a single rectangular
1278
* trapezoid. This rectangle is based on a perpendicular
1279
* extension (by half the line width) of the segment endpoints
1280
* after some adjustments of the endpoints to account for caps
1284
/* We adjust the initial point of the segment to extend the
1285
* rectangle to include the previous cap or join, (this
1286
* adjustment applies to all segments except for the first
1287
* segment of open, butt-capped paths).
1289
lengthen_initial = TRUE;
1290
if (i == 0 && stroker->open_sub_path && line_cap == CAIRO_LINE_CAP_BUTT)
1291
lengthen_initial = FALSE;
1293
/* The adjustment of the final point is trickier. For all but
1294
* the last segment we shorten the segment at the final
1295
* endpoint to not overlap with the subsequent join. For the
1296
* last segment we do the same shortening if the path is
1297
* closed. If the path is open and butt-capped we do no
1298
* adjustment, while if it's open and square-capped we do a
1299
* lengthening adjustment instead to include the cap.
1301
shorten_final = TRUE;
1302
lengthen_final = FALSE;
1303
if (i == stroker->num_segments - 1 && stroker->open_sub_path) {
1304
shorten_final = FALSE;
1305
if (line_cap == CAIRO_LINE_CAP_SQUARE)
1306
lengthen_final = TRUE;
1309
/* Perform the adjustments of the endpoints. */
1312
if (lengthen_initial)
1313
a->x -= half_line_width;
1315
b->x -= half_line_width;
1316
else if (lengthen_final)
1317
b->x += half_line_width;
1319
if (lengthen_initial)
1320
a->x += half_line_width;
1322
b->x += half_line_width;
1323
else if (lengthen_final)
1324
b->x -= half_line_width;
1336
if (lengthen_initial)
1337
a->y -= half_line_width;
1339
b->y -= half_line_width;
1340
else if (lengthen_final)
1341
b->y += half_line_width;
1343
if (lengthen_initial)
1344
a->y += half_line_width;
1346
b->y += half_line_width;
1347
else if (lengthen_final)
1348
b->y -= half_line_width;
1360
/* Form the rectangle by expanding by half the line width in
1361
* either perpendicular direction. */
1363
a->y -= half_line_width;
1364
b->y += half_line_width;
1366
a->x -= half_line_width;
1367
b->x += half_line_width;
1370
status = _cairo_traps_tessellate_rectangle (stroker->traps, a, b);
1375
stroker->num_segments = 0;
1377
return CAIRO_STATUS_SUCCESS;
1380
static cairo_status_t
1381
_cairo_rectilinear_stroker_move_to (void *closure,
1382
cairo_point_t *point)
1384
cairo_rectilinear_stroker_t *stroker = closure;
1385
cairo_status_t status;
1387
status = _cairo_rectilinear_stroker_emit_segments (stroker);
1391
stroker->current_point = *point;
1392
stroker->first_point = *point;
1394
return CAIRO_STATUS_SUCCESS;
1397
static cairo_status_t
1398
_cairo_rectilinear_stroker_line_to (void *closure,
1399
cairo_point_t *point)
1401
cairo_rectilinear_stroker_t *stroker = closure;
1402
cairo_point_t *a = &stroker->current_point;
1403
cairo_point_t *b = point;
1404
cairo_status_t status;
1406
/* We only support horizontal or vertical elements. */
1407
if (! (a->x == b->x || a->y == b->y))
1408
return CAIRO_INT_STATUS_UNSUPPORTED;
1410
/* We don't draw anything for degenerate paths. */
1411
if (a->x == b->x && a->y == b->y)
1412
return CAIRO_STATUS_SUCCESS;
1414
status = _cairo_rectilinear_stroker_add_segment (stroker, a, b);
1416
stroker->current_point = *point;
1417
stroker->open_sub_path = TRUE;
1422
static cairo_status_t
1423
_cairo_rectilinear_stroker_close_path (void *closure)
1425
cairo_rectilinear_stroker_t *stroker = closure;
1426
cairo_status_t status;
1428
/* We don't draw anything for degenerate paths. */
1429
if (! stroker->open_sub_path)
1430
return CAIRO_STATUS_SUCCESS;
1432
status = _cairo_rectilinear_stroker_line_to (stroker,
1433
&stroker->first_point);
1437
stroker->open_sub_path = FALSE;
1439
status = _cairo_rectilinear_stroker_emit_segments (stroker);
1443
return CAIRO_STATUS_SUCCESS;
1446
static cairo_int_status_t
1447
_cairo_path_fixed_stroke_rectilinear (cairo_path_fixed_t *path,
1448
cairo_stroke_style_t *stroke_style,
1449
cairo_matrix_t *ctm,
1450
cairo_traps_t *traps)
1452
cairo_rectilinear_stroker_t rectilinear_stroker;
1453
cairo_int_status_t status;
1455
/* This special-case rectilinear stroker only supports
1456
* miter-joined lines (not curves) and no dashing and a
1457
* translation-only matrix (though it could probably be extended
1458
* to support a matrix with uniform, integer scaling).
1460
* It also only supports horizontal and vertical line_to
1461
* elements. But we don't catch that here, but instead return
1462
* UNSUPPORTED from _cairo_rectilinear_stroker_line_to if any
1463
* non-rectilinear line_to is encountered.
1465
if (path->has_curve_to)
1466
return CAIRO_INT_STATUS_UNSUPPORTED;
1467
if (stroke_style->line_join != CAIRO_LINE_JOIN_MITER)
1468
return CAIRO_INT_STATUS_UNSUPPORTED;
1469
/* If the miter limit turns right angles into bevels, then we
1470
* can't use this optimization. Remember, the ratio is
1471
* 1/sin(ɸ/2). So the cutoff is 1/sin(π/4.0) or ⎷2,
1472
* which we round for safety. */
1473
if (stroke_style->miter_limit < M_SQRT2)
1474
return CAIRO_INT_STATUS_UNSUPPORTED;
1475
if (stroke_style->dash)
1476
return CAIRO_INT_STATUS_UNSUPPORTED;
1477
if (! (stroke_style->line_cap == CAIRO_LINE_CAP_BUTT ||
1478
stroke_style->line_cap == CAIRO_LINE_CAP_SQUARE))
1480
return CAIRO_INT_STATUS_UNSUPPORTED;
1482
if (! (_cairo_matrix_is_identity (ctm) ||
1483
_cairo_matrix_is_translation (ctm)))
1485
return CAIRO_INT_STATUS_UNSUPPORTED;
1488
_cairo_rectilinear_stroker_init (&rectilinear_stroker, stroke_style, traps);
1490
status = _cairo_path_fixed_interpret (path,
1491
CAIRO_DIRECTION_FORWARD,
1492
_cairo_rectilinear_stroker_move_to,
1493
_cairo_rectilinear_stroker_line_to,
1495
_cairo_rectilinear_stroker_close_path,
1496
&rectilinear_stroker);
1500
status = _cairo_rectilinear_stroker_emit_segments (&rectilinear_stroker);
1503
_cairo_rectilinear_stroker_fini (&rectilinear_stroker);
1506
_cairo_traps_clear (traps);
added
removed
cairo/src/cairo-path-stroke.c
