2 * Copyright © 2004 Carl Worth
3 * Copyright © 2006 Red Hat, Inc.
4 * Copyright © 2008 Chris Wilson
6 * This library is free software; you can redistribute it and/or
7 * modify it either under the terms of the GNU Lesser General Public
8 * License version 2.1 as published by the Free Software Foundation
9 * (the "LGPL") or, at your option, under the terms of the Mozilla
10 * Public License Version 1.1 (the "MPL"). If you do not alter this
11 * notice, a recipient may use your version of this file under either
12 * the MPL or the LGPL.
14 * You should have received a copy of the LGPL along with this library
15 * in the file COPYING-LGPL-2.1; if not, write to the Free Software
16 * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
17 * You should have received a copy of the MPL along with this library
18 * in the file COPYING-MPL-1.1
20 * The contents of this file are subject to the Mozilla Public License
21 * Version 1.1 (the "License"); you may not use this file except in
22 * compliance with the License. You may obtain a copy of the License at
23 * http://www.mozilla.org/MPL/
25 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
26 * OF ANY KIND, either express or implied. See the LGPL or the MPL for
27 * the specific language governing rights and limitations.
29 * The Original Code is the cairo graphics library.
31 * The Initial Developer of the Original Code is Carl Worth
34 * Carl D. Worth <cworth@cworth.org>
35 * Chris Wilson <chris@chris-wilson.co.uk>
38 /* Provide definitions for standalone compilation */
41 #include "cairo-error-private.h"
42 #include "cairo-freelist-private.h"
43 #include "cairo-combsort-inline.h"
46 typedef struct _cairo_bo_intersect_ordinate
{
48 enum { EXCESS
= -1, EXACT
= 0, DEFAULT
= 1 } approx
;
49 } cairo_bo_intersect_ordinate_t
;
51 typedef struct _cairo_bo_intersect_point
{
52 cairo_bo_intersect_ordinate_t x
;
53 cairo_bo_intersect_ordinate_t y
;
54 } cairo_bo_intersect_point_t
;
56 typedef struct _cairo_bo_edge cairo_bo_edge_t
;
58 typedef struct _cairo_bo_deferred
{
59 cairo_bo_edge_t
*other
;
61 } cairo_bo_deferred_t
;
63 struct _cairo_bo_edge
{
66 cairo_bo_edge_t
*prev
;
67 cairo_bo_edge_t
*next
;
68 cairo_bo_deferred_t deferred
;
71 /* the parent is always given by index/2 */
72 #define PQ_PARENT_INDEX(i) ((i) >> 1)
73 #define PQ_FIRST_ENTRY 1
75 /* left and right children are index * 2 and (index * 2) +1 respectively */
76 #define PQ_LEFT_CHILD_INDEX(i) ((i) << 1)
79 CAIRO_BO_EVENT_TYPE_STOP
= -1,
80 CAIRO_BO_EVENT_TYPE_INTERSECTION
,
81 CAIRO_BO_EVENT_TYPE_START
82 } cairo_bo_event_type_t
;
84 typedef struct _cairo_bo_event
{
85 cairo_bo_event_type_t type
;
86 cairo_bo_intersect_point_t point
;
89 typedef struct _cairo_bo_start_event
{
90 cairo_bo_event_type_t type
;
91 cairo_bo_intersect_point_t point
;
93 } cairo_bo_start_event_t
;
95 typedef struct _cairo_bo_queue_event
{
96 cairo_bo_event_type_t type
;
97 cairo_bo_intersect_point_t point
;
100 } cairo_bo_queue_event_t
;
102 typedef struct _pqueue
{
105 cairo_bo_event_t
**elements
;
106 cairo_bo_event_t
*elements_embedded
[1024];
109 typedef struct _cairo_bo_event_queue
{
110 cairo_freepool_t pool
;
112 cairo_bo_event_t
**start_events
;
113 } cairo_bo_event_queue_t
;
115 typedef struct _cairo_bo_sweep_line
{
116 cairo_bo_edge_t
*head
;
118 cairo_bo_edge_t
*current_edge
;
119 } cairo_bo_sweep_line_t
;
122 _line_compute_intersection_x_for_y (const cairo_line_t
*line
,
133 dy
= line
->p2
.y
- line
->p1
.y
;
135 x
+= _cairo_fixed_mul_div_floor (y
- line
->p1
.y
,
136 line
->p2
.x
- line
->p1
.x
,
144 _cairo_bo_point32_compare (cairo_bo_intersect_point_t
const *a
,
145 cairo_bo_intersect_point_t
const *b
)
149 cmp
= a
->y
.ordinate
- b
->y
.ordinate
;
153 cmp
= a
->y
.approx
- b
->y
.approx
;
157 return a
->x
.ordinate
- b
->x
.ordinate
;
160 /* Compare the slope of a to the slope of b, returning 1, 0, -1 if the
161 * slope a is respectively greater than, equal to, or less than the
164 * For each edge, consider the direction vector formed from:
170 * (dx, dy) = (line.p2.x - line.p1.x, line.p2.y - line.p1.y)
172 * We then define the slope of each edge as dx/dy, (which is the
173 * inverse of the slope typically used in math instruction). We never
174 * compute a slope directly as the value approaches infinity, but we
175 * can derive a slope comparison without division as follows, (where
176 * the ? represents our compare operator).
178 * 1. slope(a) ? slope(b)
179 * 2. adx/ady ? bdx/bdy
180 * 3. (adx * bdy) ? (bdx * ady)
182 * Note that from step 2 to step 3 there is no change needed in the
183 * sign of the result since both ady and bdy are guaranteed to be
184 * greater than or equal to 0.
186 * When using this slope comparison to sort edges, some care is needed
187 * when interpreting the results. Since the slope compare operates on
188 * distance vectors from top to bottom it gives a correct left to
189 * right sort for edges that have a common top point, (such as two
190 * edges with start events at the same location). On the other hand,
191 * the sense of the result will be exactly reversed for two edges that
192 * have a common stop point.
195 _slope_compare (const cairo_bo_edge_t
*a
,
196 const cairo_bo_edge_t
*b
)
198 /* XXX: We're assuming here that dx and dy will still fit in 32
199 * bits. That's not true in general as there could be overflow. We
200 * should prevent that before the tessellation algorithm
203 int32_t adx
= a
->edge
.line
.p2
.x
- a
->edge
.line
.p1
.x
;
204 int32_t bdx
= b
->edge
.line
.p2
.x
- b
->edge
.line
.p1
.x
;
206 /* Since the dy's are all positive by construction we can fast
207 * path several common cases.
210 /* First check for vertical lines. */
216 /* Then where the two edges point in different directions wrt x. */
220 /* Finally we actually need to do the general comparison. */
222 int32_t ady
= a
->edge
.line
.p2
.y
- a
->edge
.line
.p1
.y
;
223 int32_t bdy
= b
->edge
.line
.p2
.y
- b
->edge
.line
.p1
.y
;
224 cairo_int64_t adx_bdy
= _cairo_int32x32_64_mul (adx
, bdy
);
225 cairo_int64_t bdx_ady
= _cairo_int32x32_64_mul (bdx
, ady
);
227 return _cairo_int64_cmp (adx_bdy
, bdx_ady
);
232 * We need to compare the x-coordinates of a pair of lines for a particular y,
233 * without loss of precision.
235 * The x-coordinate along an edge for a given y is:
236 * X = A_x + (Y - A_y) * A_dx / A_dy
238 * So the inequality we wish to test is:
239 * A_x + (Y - A_y) * A_dx / A_dy ∘ B_x + (Y - B_y) * B_dx / B_dy,
240 * where ∘ is our inequality operator.
242 * By construction, we know that A_dy and B_dy (and (Y - A_y), (Y - B_y)) are
243 * all positive, so we can rearrange it thus without causing a sign change:
244 * A_dy * B_dy * (A_x - B_x) ∘ (Y - B_y) * B_dx * A_dy
245 * - (Y - A_y) * A_dx * B_dy
247 * Given the assumption that all the deltas fit within 32 bits, we can compute
248 * this comparison directly using 128 bit arithmetic. For certain, but common,
249 * input we can reduce this down to a single 32 bit compare by inspecting the
252 * (And put the burden of the work on developing fast 128 bit ops, which are
253 * required throughout the tessellator.)
255 * See the similar discussion for _slope_compare().
258 edges_compare_x_for_y_general (const cairo_bo_edge_t
*a
,
259 const cairo_bo_edge_t
*b
,
262 /* XXX: We're assuming here that dx and dy will still fit in 32
263 * bits. That's not true in general as there could be overflow. We
264 * should prevent that before the tessellation algorithm
274 HAVE_DX_ADX
= HAVE_DX
| HAVE_ADX
,
276 HAVE_DX_BDX
= HAVE_DX
| HAVE_BDX
,
277 HAVE_ADX_BDX
= HAVE_ADX
| HAVE_BDX
,
278 HAVE_ALL
= HAVE_DX
| HAVE_ADX
| HAVE_BDX
279 } have_dx_adx_bdx
= HAVE_ALL
;
281 /* don't bother solving for abscissa if the edges' bounding boxes
282 * can be used to order them. */
286 if (a
->edge
.line
.p1
.x
< a
->edge
.line
.p2
.x
) {
287 amin
= a
->edge
.line
.p1
.x
;
288 amax
= a
->edge
.line
.p2
.x
;
290 amin
= a
->edge
.line
.p2
.x
;
291 amax
= a
->edge
.line
.p1
.x
;
293 if (b
->edge
.line
.p1
.x
< b
->edge
.line
.p2
.x
) {
294 bmin
= b
->edge
.line
.p1
.x
;
295 bmax
= b
->edge
.line
.p2
.x
;
297 bmin
= b
->edge
.line
.p2
.x
;
298 bmax
= b
->edge
.line
.p1
.x
;
300 if (amax
< bmin
) return -1;
301 if (amin
> bmax
) return +1;
304 ady
= a
->edge
.line
.p2
.y
- a
->edge
.line
.p1
.y
;
305 adx
= a
->edge
.line
.p2
.x
- a
->edge
.line
.p1
.x
;
307 have_dx_adx_bdx
&= ~HAVE_ADX
;
309 bdy
= b
->edge
.line
.p2
.y
- b
->edge
.line
.p1
.y
;
310 bdx
= b
->edge
.line
.p2
.x
- b
->edge
.line
.p1
.x
;
312 have_dx_adx_bdx
&= ~HAVE_BDX
;
314 dx
= a
->edge
.line
.p1
.x
- b
->edge
.line
.p1
.x
;
316 have_dx_adx_bdx
&= ~HAVE_DX
;
318 #define L _cairo_int64x32_128_mul (_cairo_int32x32_64_mul (ady, bdy), dx)
319 #define A _cairo_int64x32_128_mul (_cairo_int32x32_64_mul (adx, bdy), y - a->edge.line.p1.y)
320 #define B _cairo_int64x32_128_mul (_cairo_int32x32_64_mul (bdx, ady), y - b->edge.line.p1.y)
321 switch (have_dx_adx_bdx
) {
326 /* A_dy * B_dy * (A_x - B_x) ∘ 0 */
327 return dx
; /* ady * bdy is positive definite */
329 /* 0 ∘ - (Y - A_y) * A_dx * B_dy */
330 return adx
; /* bdy * (y - a->top.y) is positive definite */
332 /* 0 ∘ (Y - B_y) * B_dx * A_dy */
333 return -bdx
; /* ady * (y - b->top.y) is positive definite */
335 /* 0 ∘ (Y - B_y) * B_dx * A_dy - (Y - A_y) * A_dx * B_dy */
336 if ((adx
^ bdx
) < 0) {
338 } else if (a
->edge
.line
.p1
.y
== b
->edge
.line
.p1
.y
) { /* common origin */
339 cairo_int64_t adx_bdy
, bdx_ady
;
341 /* ∴ A_dx * B_dy ∘ B_dx * A_dy */
343 adx_bdy
= _cairo_int32x32_64_mul (adx
, bdy
);
344 bdx_ady
= _cairo_int32x32_64_mul (bdx
, ady
);
346 return _cairo_int64_cmp (adx_bdy
, bdx_ady
);
348 return _cairo_int128_cmp (A
, B
);
350 /* A_dy * (A_x - B_x) ∘ - (Y - A_y) * A_dx */
351 if ((-adx
^ dx
) < 0) {
354 cairo_int64_t ady_dx
, dy_adx
;
356 ady_dx
= _cairo_int32x32_64_mul (ady
, dx
);
357 dy_adx
= _cairo_int32x32_64_mul (a
->edge
.line
.p1
.y
- y
, adx
);
359 return _cairo_int64_cmp (ady_dx
, dy_adx
);
362 /* B_dy * (A_x - B_x) ∘ (Y - B_y) * B_dx */
363 if ((bdx
^ dx
) < 0) {
366 cairo_int64_t bdy_dx
, dy_bdx
;
368 bdy_dx
= _cairo_int32x32_64_mul (bdy
, dx
);
369 dy_bdx
= _cairo_int32x32_64_mul (y
- b
->edge
.line
.p1
.y
, bdx
);
371 return _cairo_int64_cmp (bdy_dx
, dy_bdx
);
374 /* XXX try comparing (a->edge.line.p2.x - b->edge.line.p2.x) et al */
375 return _cairo_int128_cmp (L
, _cairo_int128_sub (B
, A
));
383 * We need to compare the x-coordinate of a line for a particular y wrt to a
384 * given x, without loss of precision.
386 * The x-coordinate along an edge for a given y is:
387 * X = A_x + (Y - A_y) * A_dx / A_dy
389 * So the inequality we wish to test is:
390 * A_x + (Y - A_y) * A_dx / A_dy ∘ X
391 * where ∘ is our inequality operator.
393 * By construction, we know that A_dy (and (Y - A_y)) are
394 * all positive, so we can rearrange it thus without causing a sign change:
395 * (Y - A_y) * A_dx ∘ (X - A_x) * A_dy
397 * Given the assumption that all the deltas fit within 32 bits, we can compute
398 * this comparison directly using 64 bit arithmetic.
400 * See the similar discussion for _slope_compare() and
401 * edges_compare_x_for_y_general().
404 edge_compare_for_y_against_x (const cairo_bo_edge_t
*a
,
412 if (x
< a
->edge
.line
.p1
.x
&& x
< a
->edge
.line
.p2
.x
)
414 if (x
> a
->edge
.line
.p1
.x
&& x
> a
->edge
.line
.p2
.x
)
417 adx
= a
->edge
.line
.p2
.x
- a
->edge
.line
.p1
.x
;
418 dx
= x
- a
->edge
.line
.p1
.x
;
422 if (dx
== 0 || (adx
^ dx
) < 0)
425 dy
= y
- a
->edge
.line
.p1
.y
;
426 ady
= a
->edge
.line
.p2
.y
- a
->edge
.line
.p1
.y
;
428 L
= _cairo_int32x32_64_mul (dy
, adx
);
429 R
= _cairo_int32x32_64_mul (dx
, ady
);
431 return _cairo_int64_cmp (L
, R
);
435 edges_compare_x_for_y (const cairo_bo_edge_t
*a
,
436 const cairo_bo_edge_t
*b
,
439 /* If the sweep-line is currently on an end-point of a line,
440 * then we know its precise x value (and considering that we often need to
441 * compare events at end-points, this happens frequently enough to warrant
448 HAVE_BOTH
= HAVE_AX
| HAVE_BX
449 } have_ax_bx
= HAVE_BOTH
;
452 if (y
== a
->edge
.line
.p1
.y
)
453 ax
= a
->edge
.line
.p1
.x
;
454 else if (y
== a
->edge
.line
.p2
.y
)
455 ax
= a
->edge
.line
.p2
.x
;
457 have_ax_bx
&= ~HAVE_AX
;
459 if (y
== b
->edge
.line
.p1
.y
)
460 bx
= b
->edge
.line
.p1
.x
;
461 else if (y
== b
->edge
.line
.p2
.y
)
462 bx
= b
->edge
.line
.p2
.x
;
464 have_ax_bx
&= ~HAVE_BX
;
466 switch (have_ax_bx
) {
469 return edges_compare_x_for_y_general (a
, b
, y
);
471 return -edge_compare_for_y_against_x (b
, y
, ax
);
473 return edge_compare_for_y_against_x (a
, y
, bx
);
480 _line_equal (const cairo_line_t
*a
, const cairo_line_t
*b
)
482 return a
->p1
.x
== b
->p1
.x
&& a
->p1
.y
== b
->p1
.y
&&
483 a
->p2
.x
== b
->p2
.x
&& a
->p2
.y
== b
->p2
.y
;
487 _cairo_bo_sweep_line_compare_edges (cairo_bo_sweep_line_t
*sweep_line
,
488 const cairo_bo_edge_t
*a
,
489 const cairo_bo_edge_t
*b
)
493 /* compare the edges if not identical */
494 if (! _line_equal (&a
->edge
.line
, &b
->edge
.line
)) {
495 cmp
= edges_compare_x_for_y (a
, b
, sweep_line
->current_y
);
499 /* The two edges intersect exactly at y, so fall back on slope
500 * comparison. We know that this compare_edges function will be
501 * called only when starting a new edge, (not when stopping an
502 * edge), so we don't have to worry about conditionally inverting
503 * the sense of _slope_compare. */
504 cmp
= _slope_compare (a
, b
);
509 /* We've got two collinear edges now. */
510 return b
->edge
.bottom
- a
->edge
.bottom
;
513 static inline cairo_int64_t
514 det32_64 (int32_t a
, int32_t b
,
515 int32_t c
, int32_t d
)
517 /* det = a * d - b * c */
518 return _cairo_int64_sub (_cairo_int32x32_64_mul (a
, d
),
519 _cairo_int32x32_64_mul (b
, c
));
522 static inline cairo_int128_t
523 det64x32_128 (cairo_int64_t a
, int32_t b
,
524 cairo_int64_t c
, int32_t d
)
526 /* det = a * d - b * c */
527 return _cairo_int128_sub (_cairo_int64x32_128_mul (a
, d
),
528 _cairo_int64x32_128_mul (c
, b
));
531 static inline cairo_bo_intersect_ordinate_t
532 round_to_nearest (cairo_quorem64_t d
,
535 cairo_bo_intersect_ordinate_t ordinate
;
537 cairo_int64_t drem_2
= _cairo_int64_mul (d
.rem
, _cairo_int32_to_int64 (2));
539 /* assert (! _cairo_int64_negative (den));*/
541 if (_cairo_int64_lt (drem_2
, _cairo_int64_negate (den
))) {
543 drem_2
= _cairo_int64_negate (drem_2
);
544 } else if (_cairo_int64_le (den
, drem_2
)) {
546 drem_2
= _cairo_int64_negate (drem_2
);
549 ordinate
.ordinate
= quo
;
550 ordinate
.approx
= _cairo_int64_is_zero (drem_2
) ? EXACT
: _cairo_int64_negative (drem_2
) ? EXCESS
: DEFAULT
;
555 /* Compute the intersection of two lines as defined by two edges. The
556 * result is provided as a coordinate pair of 128-bit integers.
558 * Returns %CAIRO_BO_STATUS_INTERSECTION if there is an intersection or
559 * %CAIRO_BO_STATUS_PARALLEL if the two lines are exactly parallel.
562 intersect_lines (cairo_bo_edge_t
*a
,
564 cairo_bo_intersect_point_t
*intersection
)
566 cairo_int64_t a_det
, b_det
;
568 /* XXX: We're assuming here that dx and dy will still fit in 32
569 * bits. That's not true in general as there could be overflow. We
570 * should prevent that before the tessellation algorithm begins.
571 * What we're doing to mitigate this is to perform clamping in
572 * cairo_bo_tessellate_polygon().
574 int32_t dx1
= a
->edge
.line
.p1
.x
- a
->edge
.line
.p2
.x
;
575 int32_t dy1
= a
->edge
.line
.p1
.y
- a
->edge
.line
.p2
.y
;
577 int32_t dx2
= b
->edge
.line
.p1
.x
- b
->edge
.line
.p2
.x
;
578 int32_t dy2
= b
->edge
.line
.p1
.y
- b
->edge
.line
.p2
.y
;
580 cairo_int64_t den_det
;
584 den_det
= det32_64 (dx1
, dy1
, dx2
, dy2
);
586 /* Q: Can we determine that the lines do not intersect (within range)
587 * much more cheaply than computing the intersection point i.e. by
588 * avoiding the division?
590 * X = ax + t * adx = bx + s * bdx;
591 * Y = ay + t * ady = by + s * bdy;
592 * ∴ t * (ady*bdx - bdy*adx) = bdx * (by - ay) + bdy * (ax - bx)
595 * Therefore we can reject any intersection (under the criteria for
596 * valid intersection events) if:
597 * L^R < 0 => t < 0, or
600 * (where top/bottom must at least extend to the line endpoints).
602 * A similar substitution can be performed for s, yielding:
603 * s * (ady*bdx - bdy*adx) = ady * (ax - bx) - adx * (ay - by)
605 R
= det32_64 (dx2
, dy2
,
606 b
->edge
.line
.p1
.x
- a
->edge
.line
.p1
.x
,
607 b
->edge
.line
.p1
.y
- a
->edge
.line
.p1
.y
);
608 if (_cairo_int64_le (den_det
, R
))
611 R
= det32_64 (dy1
, dx1
,
612 a
->edge
.line
.p1
.y
- b
->edge
.line
.p1
.y
,
613 a
->edge
.line
.p1
.x
- b
->edge
.line
.p1
.x
);
614 if (_cairo_int64_le (den_det
, R
))
617 /* We now know that the two lines should intersect within range. */
619 a_det
= det32_64 (a
->edge
.line
.p1
.x
, a
->edge
.line
.p1
.y
,
620 a
->edge
.line
.p2
.x
, a
->edge
.line
.p2
.y
);
621 b_det
= det32_64 (b
->edge
.line
.p1
.x
, b
->edge
.line
.p1
.y
,
622 b
->edge
.line
.p2
.x
, b
->edge
.line
.p2
.y
);
624 /* x = det (a_det, dx1, b_det, dx2) / den_det */
625 qr
= _cairo_int_96by64_32x64_divrem (det64x32_128 (a_det
, dx1
,
628 if (_cairo_int64_eq (qr
.rem
, den_det
))
631 intersection
->x
= round_to_nearest (qr
, den_det
);
633 /* y = det (a_det, dy1, b_det, dy2) / den_det */
634 qr
= _cairo_int_96by64_32x64_divrem (det64x32_128 (a_det
, dy1
,
637 if (_cairo_int64_eq (qr
.rem
, den_det
))
640 intersection
->y
= round_to_nearest (qr
, den_det
);
646 _cairo_bo_intersect_ordinate_32_compare (cairo_bo_intersect_ordinate_t a
,
649 /* First compare the quotient */
655 return a
.approx
; /* == EXCESS ? -1 : a.approx == EXACT ? 0 : 1;*/
658 /* Does the given edge contain the given point. The point must already
659 * be known to be contained within the line determined by the edge,
660 * (most likely the point results from an intersection of this edge
663 * If we had exact arithmetic, then this function would simply be a
664 * matter of examining whether the y value of the point lies within
665 * the range of y values of the edge. But since intersection points
666 * are not exact due to being rounded to the nearest integer within
667 * the available precision, we must also examine the x value of the
670 * The definition of "contains" here is that the given intersection
671 * point will be seen by the sweep line after the start event for the
672 * given edge and before the stop event for the edge. See the comments
673 * in the implementation for more details.
676 _cairo_bo_edge_contains_intersect_point (cairo_bo_edge_t
*edge
,
677 cairo_bo_intersect_point_t
*point
)
679 return _cairo_bo_intersect_ordinate_32_compare (point
->y
,
680 edge
->edge
.bottom
) < 0;
683 /* Compute the intersection of two edges. The result is provided as a
684 * coordinate pair of 128-bit integers.
686 * Returns %CAIRO_BO_STATUS_INTERSECTION if there is an intersection
687 * that is within both edges, %CAIRO_BO_STATUS_NO_INTERSECTION if the
688 * intersection of the lines defined by the edges occurs outside of
689 * one or both edges, and %CAIRO_BO_STATUS_PARALLEL if the two edges
690 * are exactly parallel.
692 * Note that when determining if a candidate intersection is "inside"
693 * an edge, we consider both the infinitesimal shortening and the
694 * infinitesimal tilt rules described by John Hobby. Specifically, if
695 * the intersection is exactly the same as an edge point, it is
696 * effectively outside (no intersection is returned). Also, if the
697 * intersection point has the same
700 _cairo_bo_edge_intersect (cairo_bo_edge_t
*a
,
702 cairo_bo_intersect_point_t
*intersection
)
704 if (! intersect_lines (a
, b
, intersection
))
707 if (! _cairo_bo_edge_contains_intersect_point (a
, intersection
))
710 if (! _cairo_bo_edge_contains_intersect_point (b
, intersection
))
717 cairo_bo_event_compare (const cairo_bo_event_t
*a
,
718 const cairo_bo_event_t
*b
)
722 cmp
= _cairo_bo_point32_compare (&a
->point
, &b
->point
);
726 cmp
= a
->type
- b
->type
;
730 return a
< b
? -1 : a
== b
? 0 : 1;
734 _pqueue_init (pqueue_t
*pq
)
736 pq
->max_size
= ARRAY_LENGTH (pq
->elements_embedded
);
739 pq
->elements
= pq
->elements_embedded
;
743 _pqueue_fini (pqueue_t
*pq
)
745 if (pq
->elements
!= pq
->elements_embedded
)
749 static cairo_status_t
750 _pqueue_grow (pqueue_t
*pq
)
752 cairo_bo_event_t
**new_elements
;
755 if (pq
->elements
== pq
->elements_embedded
) {
756 new_elements
= _cairo_malloc_ab (pq
->max_size
,
757 sizeof (cairo_bo_event_t
*));
758 if (unlikely (new_elements
== NULL
))
759 return _cairo_error (CAIRO_STATUS_NO_MEMORY
);
761 memcpy (new_elements
, pq
->elements_embedded
,
762 sizeof (pq
->elements_embedded
));
764 new_elements
= _cairo_realloc_ab (pq
->elements
,
766 sizeof (cairo_bo_event_t
*));
767 if (unlikely (new_elements
== NULL
))
768 return _cairo_error (CAIRO_STATUS_NO_MEMORY
);
771 pq
->elements
= new_elements
;
772 return CAIRO_STATUS_SUCCESS
;
775 static inline cairo_status_t
776 _pqueue_push (pqueue_t
*pq
, cairo_bo_event_t
*event
)
778 cairo_bo_event_t
**elements
;
781 if (unlikely (pq
->size
+ 1 == pq
->max_size
)) {
782 cairo_status_t status
;
784 status
= _pqueue_grow (pq
);
785 if (unlikely (status
))
789 elements
= pq
->elements
;
792 i
!= PQ_FIRST_ENTRY
&&
793 cairo_bo_event_compare (event
,
794 elements
[parent
= PQ_PARENT_INDEX (i
)]) < 0;
797 elements
[i
] = elements
[parent
];
802 return CAIRO_STATUS_SUCCESS
;
806 _pqueue_pop (pqueue_t
*pq
)
808 cairo_bo_event_t
**elements
= pq
->elements
;
809 cairo_bo_event_t
*tail
;
812 tail
= elements
[pq
->size
--];
814 elements
[PQ_FIRST_ENTRY
] = NULL
;
818 for (i
= PQ_FIRST_ENTRY
;
819 (child
= PQ_LEFT_CHILD_INDEX (i
)) <= pq
->size
;
822 if (child
!= pq
->size
&&
823 cairo_bo_event_compare (elements
[child
+1],
824 elements
[child
]) < 0)
829 if (cairo_bo_event_compare (elements
[child
], tail
) >= 0)
832 elements
[i
] = elements
[child
];
837 static inline cairo_status_t
838 _cairo_bo_event_queue_insert (cairo_bo_event_queue_t
*queue
,
839 cairo_bo_event_type_t type
,
842 const cairo_bo_intersect_point_t
*point
)
844 cairo_bo_queue_event_t
*event
;
846 event
= _cairo_freepool_alloc (&queue
->pool
);
847 if (unlikely (event
== NULL
))
848 return _cairo_error (CAIRO_STATUS_NO_MEMORY
);
853 event
->point
= *point
;
855 return _pqueue_push (&queue
->pqueue
, (cairo_bo_event_t
*) event
);
859 _cairo_bo_event_queue_delete (cairo_bo_event_queue_t
*queue
,
860 cairo_bo_event_t
*event
)
862 _cairo_freepool_free (&queue
->pool
, event
);
865 static cairo_bo_event_t
*
866 _cairo_bo_event_dequeue (cairo_bo_event_queue_t
*event_queue
)
868 cairo_bo_event_t
*event
, *cmp
;
870 event
= event_queue
->pqueue
.elements
[PQ_FIRST_ENTRY
];
871 cmp
= *event_queue
->start_events
;
873 (cmp
!= NULL
&& cairo_bo_event_compare (cmp
, event
) < 0))
876 event_queue
->start_events
++;
880 _pqueue_pop (&event_queue
->pqueue
);
886 CAIRO_COMBSORT_DECLARE (_cairo_bo_event_queue_sort
,
888 cairo_bo_event_compare
)
891 _cairo_bo_event_queue_init (cairo_bo_event_queue_t
*event_queue
,
892 cairo_bo_event_t
**start_events
,
895 _cairo_bo_event_queue_sort (start_events
, num_events
);
896 start_events
[num_events
] = NULL
;
898 event_queue
->start_events
= start_events
;
900 _cairo_freepool_init (&event_queue
->pool
,
901 sizeof (cairo_bo_queue_event_t
));
902 _pqueue_init (&event_queue
->pqueue
);
903 event_queue
->pqueue
.elements
[PQ_FIRST_ENTRY
] = NULL
;
906 static cairo_status_t
907 event_queue_insert_stop (cairo_bo_event_queue_t
*event_queue
,
908 cairo_bo_edge_t
*edge
)
910 cairo_bo_intersect_point_t point
;
912 point
.y
.ordinate
= edge
->edge
.bottom
;
913 point
.y
.approx
= EXACT
;
914 point
.x
.ordinate
= _line_compute_intersection_x_for_y (&edge
->edge
.line
,
916 point
.x
.approx
= EXACT
;
918 return _cairo_bo_event_queue_insert (event_queue
,
919 CAIRO_BO_EVENT_TYPE_STOP
,
925 _cairo_bo_event_queue_fini (cairo_bo_event_queue_t
*event_queue
)
927 _pqueue_fini (&event_queue
->pqueue
);
928 _cairo_freepool_fini (&event_queue
->pool
);
931 static inline cairo_status_t
932 event_queue_insert_if_intersect_below_current_y (cairo_bo_event_queue_t
*event_queue
,
933 cairo_bo_edge_t
*left
,
934 cairo_bo_edge_t
*right
)
936 cairo_bo_intersect_point_t intersection
;
938 if (_line_equal (&left
->edge
.line
, &right
->edge
.line
))
939 return CAIRO_STATUS_SUCCESS
;
941 /* The names "left" and "right" here are correct descriptions of
942 * the order of the two edges within the active edge list. So if a
943 * slope comparison also puts left less than right, then we know
944 * that the intersection of these two segments has already
945 * occurred before the current sweep line position. */
946 if (_slope_compare (left
, right
) <= 0)
947 return CAIRO_STATUS_SUCCESS
;
949 if (! _cairo_bo_edge_intersect (left
, right
, &intersection
))
950 return CAIRO_STATUS_SUCCESS
;
952 return _cairo_bo_event_queue_insert (event_queue
,
953 CAIRO_BO_EVENT_TYPE_INTERSECTION
,
959 _cairo_bo_sweep_line_init (cairo_bo_sweep_line_t
*sweep_line
)
961 sweep_line
->head
= NULL
;
962 sweep_line
->current_y
= INT32_MIN
;
963 sweep_line
->current_edge
= NULL
;
966 static cairo_status_t
967 sweep_line_insert (cairo_bo_sweep_line_t
*sweep_line
,
968 cairo_bo_edge_t
*edge
)
970 if (sweep_line
->current_edge
!= NULL
) {
971 cairo_bo_edge_t
*prev
, *next
;
974 cmp
= _cairo_bo_sweep_line_compare_edges (sweep_line
,
975 sweep_line
->current_edge
,
978 prev
= sweep_line
->current_edge
;
980 while (next
!= NULL
&&
981 _cairo_bo_sweep_line_compare_edges (sweep_line
,
984 prev
= next
, next
= prev
->next
;
992 } else if (cmp
> 0) {
993 next
= sweep_line
->current_edge
;
995 while (prev
!= NULL
&&
996 _cairo_bo_sweep_line_compare_edges (sweep_line
,
999 next
= prev
, prev
= next
->prev
;
1008 sweep_line
->head
= edge
;
1010 prev
= sweep_line
->current_edge
;
1012 edge
->next
= prev
->next
;
1013 if (prev
->next
!= NULL
)
1014 prev
->next
->prev
= edge
;
1018 sweep_line
->head
= edge
;
1021 sweep_line
->current_edge
= edge
;
1023 return CAIRO_STATUS_SUCCESS
;
1027 _cairo_bo_sweep_line_delete (cairo_bo_sweep_line_t
*sweep_line
,
1028 cairo_bo_edge_t
*edge
)
1030 if (edge
->prev
!= NULL
)
1031 edge
->prev
->next
= edge
->next
;
1033 sweep_line
->head
= edge
->next
;
1035 if (edge
->next
!= NULL
)
1036 edge
->next
->prev
= edge
->prev
;
1038 if (sweep_line
->current_edge
== edge
)
1039 sweep_line
->current_edge
= edge
->prev
? edge
->prev
: edge
->next
;
1043 _cairo_bo_sweep_line_swap (cairo_bo_sweep_line_t
*sweep_line
,
1044 cairo_bo_edge_t
*left
,
1045 cairo_bo_edge_t
*right
)
1047 if (left
->prev
!= NULL
)
1048 left
->prev
->next
= right
;
1050 sweep_line
->head
= right
;
1052 if (right
->next
!= NULL
)
1053 right
->next
->prev
= left
;
1055 left
->next
= right
->next
;
1058 right
->prev
= left
->prev
;
1062 static inline cairo_bool_t
1063 edges_colinear (const cairo_bo_edge_t
*a
, const cairo_bo_edge_t
*b
)
1065 if (_line_equal (&a
->edge
.line
, &b
->edge
.line
))
1068 if (_slope_compare (a
, b
))
1071 /* The choice of y is not truly arbitrary since we must guarantee that it
1072 * is greater than the start of either line.
1074 if (a
->edge
.line
.p1
.y
== b
->edge
.line
.p1
.y
) {
1075 return a
->edge
.line
.p1
.x
== b
->edge
.line
.p1
.x
;
1076 } else if (a
->edge
.line
.p1
.y
< b
->edge
.line
.p1
.y
) {
1077 return edge_compare_for_y_against_x (b
,
1079 a
->edge
.line
.p1
.x
) == 0;
1081 return edge_compare_for_y_against_x (a
,
1083 b
->edge
.line
.p1
.x
) == 0;
1088 edges_end (cairo_bo_edge_t
*left
,
1090 cairo_polygon_t
*polygon
)
1092 cairo_bo_deferred_t
*l
= &left
->deferred
;
1093 cairo_bo_edge_t
*right
= l
->other
;
1095 assert(right
->deferred
.other
== NULL
);
1096 if (likely (l
->top
< bot
)) {
1097 _cairo_polygon_add_line (polygon
, &left
->edge
.line
, l
->top
, bot
, 1);
1098 _cairo_polygon_add_line (polygon
, &right
->edge
.line
, l
->top
, bot
, -1);
1105 edges_start_or_continue (cairo_bo_edge_t
*left
,
1106 cairo_bo_edge_t
*right
,
1108 cairo_polygon_t
*polygon
)
1110 assert (right
->deferred
.other
== NULL
);
1112 if (left
->deferred
.other
== right
)
1115 if (left
->deferred
.other
!= NULL
) {
1116 if (right
!= NULL
&& edges_colinear (left
->deferred
.other
, right
)) {
1117 cairo_bo_edge_t
*old
= left
->deferred
.other
;
1119 /* continuation on right, extend right to cover both */
1120 assert (old
->deferred
.other
== NULL
);
1121 assert (old
->edge
.line
.p2
.y
> old
->edge
.line
.p1
.y
);
1123 if (old
->edge
.line
.p1
.y
< right
->edge
.line
.p1
.y
)
1124 right
->edge
.line
.p1
= old
->edge
.line
.p1
;
1125 if (old
->edge
.line
.p2
.y
> right
->edge
.line
.p2
.y
)
1126 right
->edge
.line
.p2
= old
->edge
.line
.p2
;
1127 left
->deferred
.other
= right
;
1131 edges_end (left
, top
, polygon
);
1134 if (right
!= NULL
&& ! edges_colinear (left
, right
)) {
1135 left
->deferred
.top
= top
;
1136 left
->deferred
.other
= right
;
1140 #define is_zero(w) ((w)[0] == 0 || (w)[1] == 0)
1143 active_edges (cairo_bo_edge_t
*left
,
1145 cairo_polygon_t
*polygon
)
1147 cairo_bo_edge_t
*right
;
1148 int winding
[2] = {0, 0};
1150 /* Yes, this is naive. Consider this a placeholder. */
1152 while (left
!= NULL
) {
1153 assert (is_zero (winding
));
1156 winding
[left
->a_or_b
] += left
->edge
.dir
;
1157 if (! is_zero (winding
))
1160 if unlikely ((left
->deferred
.other
))
1161 edges_end (left
, top
, polygon
);
1170 if unlikely ((right
->deferred
.other
))
1171 edges_end (right
, top
, polygon
);
1173 winding
[right
->a_or_b
] += right
->edge
.dir
;
1174 if (is_zero (winding
)) {
1175 if (right
->next
== NULL
||
1176 ! edges_colinear (right
, right
->next
))
1180 right
= right
->next
;
1183 edges_start_or_continue (left
, right
, top
, polygon
);
1189 static cairo_status_t
1190 intersection_sweep (cairo_bo_event_t
**start_events
,
1192 cairo_polygon_t
*polygon
)
1194 cairo_status_t status
= CAIRO_STATUS_SUCCESS
; /* silence compiler */
1195 cairo_bo_event_queue_t event_queue
;
1196 cairo_bo_sweep_line_t sweep_line
;
1197 cairo_bo_event_t
*event
;
1198 cairo_bo_edge_t
*left
, *right
;
1199 cairo_bo_edge_t
*e1
, *e2
;
1201 _cairo_bo_event_queue_init (&event_queue
, start_events
, num_events
);
1202 _cairo_bo_sweep_line_init (&sweep_line
);
1204 while ((event
= _cairo_bo_event_dequeue (&event_queue
))) {
1205 if (event
->point
.y
.ordinate
!= sweep_line
.current_y
) {
1206 active_edges (sweep_line
.head
,
1207 sweep_line
.current_y
,
1209 sweep_line
.current_y
= event
->point
.y
.ordinate
;
1212 switch (event
->type
) {
1213 case CAIRO_BO_EVENT_TYPE_START
:
1214 e1
= &((cairo_bo_start_event_t
*) event
)->edge
;
1216 status
= sweep_line_insert (&sweep_line
, e1
);
1217 if (unlikely (status
))
1220 status
= event_queue_insert_stop (&event_queue
, e1
);
1221 if (unlikely (status
))
1228 status
= event_queue_insert_if_intersect_below_current_y (&event_queue
, left
, e1
);
1229 if (unlikely (status
))
1233 if (right
!= NULL
) {
1234 status
= event_queue_insert_if_intersect_below_current_y (&event_queue
, e1
, right
);
1235 if (unlikely (status
))
1241 case CAIRO_BO_EVENT_TYPE_STOP
:
1242 e1
= ((cairo_bo_queue_event_t
*) event
)->e1
;
1243 _cairo_bo_event_queue_delete (&event_queue
, event
);
1245 if (e1
->deferred
.other
)
1246 edges_end (e1
, sweep_line
.current_y
, polygon
);
1251 _cairo_bo_sweep_line_delete (&sweep_line
, e1
);
1253 if (left
!= NULL
&& right
!= NULL
) {
1254 status
= event_queue_insert_if_intersect_below_current_y (&event_queue
, left
, right
);
1255 if (unlikely (status
))
1261 case CAIRO_BO_EVENT_TYPE_INTERSECTION
:
1262 e1
= ((cairo_bo_queue_event_t
*) event
)->e1
;
1263 e2
= ((cairo_bo_queue_event_t
*) event
)->e2
;
1264 _cairo_bo_event_queue_delete (&event_queue
, event
);
1266 /* skip this intersection if its edges are not adjacent */
1270 if (e1
->deferred
.other
)
1271 edges_end (e1
, sweep_line
.current_y
, polygon
);
1272 if (e2
->deferred
.other
)
1273 edges_end (e2
, sweep_line
.current_y
, polygon
);
1278 _cairo_bo_sweep_line_swap (&sweep_line
, e1
, e2
);
1280 /* after the swap e2 is left of e1 */
1283 status
= event_queue_insert_if_intersect_below_current_y (&event_queue
, left
, e2
);
1284 if (unlikely (status
))
1288 if (right
!= NULL
) {
1289 status
= event_queue_insert_if_intersect_below_current_y (&event_queue
, e1
, right
);
1290 if (unlikely (status
))
1299 _cairo_bo_event_queue_fini (&event_queue
);
1305 _cairo_polygon_intersect (cairo_polygon_t
*a
, int winding_a
,
1306 cairo_polygon_t
*b
, int winding_b
)
1308 cairo_status_t status
;
1309 cairo_bo_start_event_t stack_events
[CAIRO_STACK_ARRAY_LENGTH (cairo_bo_start_event_t
)];
1310 cairo_bo_start_event_t
*events
;
1311 cairo_bo_event_t
*stack_event_ptrs
[ARRAY_LENGTH (stack_events
) + 1];
1312 cairo_bo_event_t
**event_ptrs
;
1317 if (winding_a
!= CAIRO_FILL_RULE_WINDING
) {
1318 status
= _cairo_polygon_reduce (a
, winding_a
);
1319 if (unlikely (status
))
1323 if (winding_b
!= CAIRO_FILL_RULE_WINDING
) {
1324 status
= _cairo_polygon_reduce (b
, winding_b
);
1325 if (unlikely (status
))
1329 if (unlikely (0 == a
->num_edges
))
1330 return CAIRO_STATUS_SUCCESS
;
1332 if (unlikely (0 == b
->num_edges
)) {
1334 return CAIRO_STATUS_SUCCESS
;
1337 events
= stack_events
;
1338 event_ptrs
= stack_event_ptrs
;
1339 num_events
= a
->num_edges
+ b
->num_edges
;
1340 if (num_events
> ARRAY_LENGTH (stack_events
)) {
1341 events
= _cairo_malloc_ab_plus_c (num_events
,
1342 sizeof (cairo_bo_start_event_t
) +
1343 sizeof (cairo_bo_event_t
*),
1344 sizeof (cairo_bo_event_t
*));
1345 if (unlikely (events
== NULL
))
1346 return _cairo_error (CAIRO_STATUS_NO_MEMORY
);
1348 event_ptrs
= (cairo_bo_event_t
**) (events
+ num_events
);
1352 for (i
= 0; i
< a
->num_edges
; i
++) {
1353 event_ptrs
[j
] = (cairo_bo_event_t
*) &events
[j
];
1355 events
[j
].type
= CAIRO_BO_EVENT_TYPE_START
;
1356 events
[j
].point
.y
.ordinate
= a
->edges
[i
].top
;
1357 events
[j
].point
.y
.approx
= EXACT
;
1358 events
[j
].point
.x
.ordinate
=
1359 _line_compute_intersection_x_for_y (&a
->edges
[i
].line
,
1360 events
[j
].point
.y
.ordinate
);
1361 events
[j
].point
.x
.approx
= EXACT
;
1363 events
[j
].edge
.a_or_b
= 0;
1364 events
[j
].edge
.edge
= a
->edges
[i
];
1365 events
[j
].edge
.deferred
.other
= NULL
;
1366 events
[j
].edge
.prev
= NULL
;
1367 events
[j
].edge
.next
= NULL
;
1371 for (i
= 0; i
< b
->num_edges
; i
++) {
1372 event_ptrs
[j
] = (cairo_bo_event_t
*) &events
[j
];
1374 events
[j
].type
= CAIRO_BO_EVENT_TYPE_START
;
1375 events
[j
].point
.y
.ordinate
= b
->edges
[i
].top
;
1376 events
[j
].point
.y
.approx
= EXACT
;
1377 events
[j
].point
.x
.ordinate
=
1378 _line_compute_intersection_x_for_y (&b
->edges
[i
].line
,
1379 events
[j
].point
.y
.ordinate
);
1380 events
[j
].point
.x
.approx
= EXACT
;
1382 events
[j
].edge
.a_or_b
= 1;
1383 events
[j
].edge
.edge
= b
->edges
[i
];
1384 events
[j
].edge
.deferred
.other
= NULL
;
1385 events
[j
].edge
.prev
= NULL
;
1386 events
[j
].edge
.next
= NULL
;
1389 assert (j
== num_events
);
1393 FILE *file
= fopen ("clip_a.txt", "w");
1394 _cairo_debug_print_polygon (file
, a
);
1398 FILE *file
= fopen ("clip_b.txt", "w");
1399 _cairo_debug_print_polygon (file
, b
);
1405 status
= intersection_sweep (event_ptrs
, num_events
, a
);
1406 if (events
!= stack_events
)
1411 FILE *file
= fopen ("clip_result.txt", "w");
1412 _cairo_debug_print_polygon (file
, a
);
1421 _cairo_polygon_intersect_with_boxes (cairo_polygon_t
*polygon
,
1422 cairo_fill_rule_t
*winding
,
1427 cairo_status_t status
;
1430 if (num_boxes
== 0) {
1431 polygon
->num_edges
= 0;
1432 return CAIRO_STATUS_SUCCESS
;
1435 for (n
= 0; n
< num_boxes
; n
++) {
1436 if (polygon
->extents
.p1
.x
>= boxes
[n
].p1
.x
&&
1437 polygon
->extents
.p2
.x
<= boxes
[n
].p2
.x
&&
1438 polygon
->extents
.p1
.y
>= boxes
[n
].p1
.y
&&
1439 polygon
->extents
.p2
.y
<= boxes
[n
].p2
.y
)
1441 return CAIRO_STATUS_SUCCESS
;
1445 _cairo_polygon_init (&b
, NULL
, 0);
1446 for (n
= 0; n
< num_boxes
; n
++) {
1447 if (boxes
[n
].p2
.x
> polygon
->extents
.p1
.x
&&
1448 boxes
[n
].p1
.x
< polygon
->extents
.p2
.x
&&
1449 boxes
[n
].p2
.y
> polygon
->extents
.p1
.y
&&
1450 boxes
[n
].p1
.y
< polygon
->extents
.p2
.y
)
1452 cairo_point_t p1
, p2
;
1454 p1
.y
= boxes
[n
].p1
.y
;
1455 p2
.y
= boxes
[n
].p2
.y
;
1457 p2
.x
= p1
.x
= boxes
[n
].p1
.x
;
1458 _cairo_polygon_add_external_edge (&b
, &p1
, &p2
);
1460 p2
.x
= p1
.x
= boxes
[n
].p2
.x
;
1461 _cairo_polygon_add_external_edge (&b
, &p2
, &p1
);
1465 status
= _cairo_polygon_intersect (polygon
, *winding
,
1466 &b
, CAIRO_FILL_RULE_WINDING
);
1467 _cairo_polygon_fini (&b
);
1469 *winding
= CAIRO_FILL_RULE_WINDING
;