Subversion Repositories Scribus

Rev

Rev 14952 | Details | Compare with Previous | Last modification | View Log | RSS feed

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