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"
45 #define DEBUG_POLYGON 0
47 typedef cairo_point_t cairo_bo_point32_t
;
49 typedef struct _cairo_bo_intersect_ordinate
{
51 enum { EXACT
, INEXACT
} exactness
;
52 } cairo_bo_intersect_ordinate_t
;
54 typedef struct _cairo_bo_intersect_point
{
55 cairo_bo_intersect_ordinate_t x
;
56 cairo_bo_intersect_ordinate_t y
;
57 } cairo_bo_intersect_point_t
;
59 typedef struct _cairo_bo_edge cairo_bo_edge_t
;
61 typedef struct _cairo_bo_deferred
{
62 cairo_bo_edge_t
*right
;
64 } cairo_bo_deferred_t
;
66 struct _cairo_bo_edge
{
68 cairo_bo_edge_t
*prev
;
69 cairo_bo_edge_t
*next
;
70 cairo_bo_deferred_t deferred
;
73 /* the parent is always given by index/2 */
74 #define PQ_PARENT_INDEX(i) ((i) >> 1)
75 #define PQ_FIRST_ENTRY 1
77 /* left and right children are index * 2 and (index * 2) +1 respectively */
78 #define PQ_LEFT_CHILD_INDEX(i) ((i) << 1)
81 CAIRO_BO_EVENT_TYPE_STOP
,
82 CAIRO_BO_EVENT_TYPE_INTERSECTION
,
83 CAIRO_BO_EVENT_TYPE_START
84 } cairo_bo_event_type_t
;
86 typedef struct _cairo_bo_event
{
87 cairo_bo_event_type_t type
;
91 typedef struct _cairo_bo_start_event
{
92 cairo_bo_event_type_t type
;
95 } cairo_bo_start_event_t
;
97 typedef struct _cairo_bo_queue_event
{
98 cairo_bo_event_type_t type
;
102 } cairo_bo_queue_event_t
;
104 typedef struct _pqueue
{
107 cairo_bo_event_t
**elements
;
108 cairo_bo_event_t
*elements_embedded
[1024];
111 typedef struct _cairo_bo_event_queue
{
112 cairo_freepool_t pool
;
114 cairo_bo_event_t
**start_events
;
115 } cairo_bo_event_queue_t
;
117 typedef struct _cairo_bo_sweep_line
{
118 cairo_bo_edge_t
*head
;
120 cairo_bo_edge_t
*current_edge
;
121 } cairo_bo_sweep_line_t
;
124 _line_compute_intersection_x_for_y (const cairo_line_t
*line
,
135 dy
= line
->p2
.y
- line
->p1
.y
;
137 x
+= _cairo_fixed_mul_div_floor (y
- line
->p1
.y
,
138 line
->p2
.x
- line
->p1
.x
,
146 _cairo_bo_point32_compare (cairo_bo_point32_t
const *a
,
147 cairo_bo_point32_t
const *b
)
158 /* Compare the slope of a to the slope of b, returning 1, 0, -1 if the
159 * slope a is respectively greater than, equal to, or less than the
162 * For each edge, consider the direction vector formed from:
168 * (dx, dy) = (line.p2.x - line.p1.x, line.p2.y - line.p1.y)
170 * We then define the slope of each edge as dx/dy, (which is the
171 * inverse of the slope typically used in math instruction). We never
172 * compute a slope directly as the value approaches infinity, but we
173 * can derive a slope comparison without division as follows, (where
174 * the ? represents our compare operator).
176 * 1. slope(a) ? slope(b)
177 * 2. adx/ady ? bdx/bdy
178 * 3. (adx * bdy) ? (bdx * ady)
180 * Note that from step 2 to step 3 there is no change needed in the
181 * sign of the result since both ady and bdy are guaranteed to be
182 * greater than or equal to 0.
184 * When using this slope comparison to sort edges, some care is needed
185 * when interpreting the results. Since the slope compare operates on
186 * distance vectors from top to bottom it gives a correct left to
187 * right sort for edges that have a common top point, (such as two
188 * edges with start events at the same location). On the other hand,
189 * the sense of the result will be exactly reversed for two edges that
190 * have a common stop point.
193 _slope_compare (const cairo_bo_edge_t
*a
,
194 const cairo_bo_edge_t
*b
)
196 /* XXX: We're assuming here that dx and dy will still fit in 32
197 * bits. That's not true in general as there could be overflow. We
198 * should prevent that before the tessellation algorithm
201 int32_t adx
= a
->edge
.line
.p2
.x
- a
->edge
.line
.p1
.x
;
202 int32_t bdx
= b
->edge
.line
.p2
.x
- b
->edge
.line
.p1
.x
;
204 /* Since the dy's are all positive by construction we can fast
205 * path several common cases.
208 /* First check for vertical lines. */
214 /* Then where the two edges point in different directions wrt x. */
218 /* Finally we actually need to do the general comparison. */
220 int32_t ady
= a
->edge
.line
.p2
.y
- a
->edge
.line
.p1
.y
;
221 int32_t bdy
= b
->edge
.line
.p2
.y
- b
->edge
.line
.p1
.y
;
222 cairo_int64_t adx_bdy
= _cairo_int32x32_64_mul (adx
, bdy
);
223 cairo_int64_t bdx_ady
= _cairo_int32x32_64_mul (bdx
, ady
);
225 return _cairo_int64_cmp (adx_bdy
, bdx_ady
);
230 * We need to compare the x-coordinates of a pair of lines for a particular y,
231 * without loss of precision.
233 * The x-coordinate along an edge for a given y is:
234 * X = A_x + (Y - A_y) * A_dx / A_dy
236 * So the inequality we wish to test is:
237 * A_x + (Y - A_y) * A_dx / A_dy ∘ B_x + (Y - B_y) * B_dx / B_dy,
238 * where ∘ is our inequality operator.
240 * By construction, we know that A_dy and B_dy (and (Y - A_y), (Y - B_y)) are
241 * all positive, so we can rearrange it thus without causing a sign change:
242 * A_dy * B_dy * (A_x - B_x) ∘ (Y - B_y) * B_dx * A_dy
243 * - (Y - A_y) * A_dx * B_dy
245 * Given the assumption that all the deltas fit within 32 bits, we can compute
246 * this comparison directly using 128 bit arithmetic. For certain, but common,
247 * input we can reduce this down to a single 32 bit compare by inspecting the
250 * (And put the burden of the work on developing fast 128 bit ops, which are
251 * required throughout the tessellator.)
253 * See the similar discussion for _slope_compare().
256 edges_compare_x_for_y_general (const cairo_bo_edge_t
*a
,
257 const cairo_bo_edge_t
*b
,
260 /* XXX: We're assuming here that dx and dy will still fit in 32
261 * bits. That's not true in general as there could be overflow. We
262 * should prevent that before the tessellation algorithm
272 HAVE_DX_ADX
= HAVE_DX
| HAVE_ADX
,
274 HAVE_DX_BDX
= HAVE_DX
| HAVE_BDX
,
275 HAVE_ADX_BDX
= HAVE_ADX
| HAVE_BDX
,
276 HAVE_ALL
= HAVE_DX
| HAVE_ADX
| HAVE_BDX
277 } have_dx_adx_bdx
= HAVE_ALL
;
279 /* don't bother solving for abscissa if the edges' bounding boxes
280 * can be used to order them. */
284 if (a
->edge
.line
.p1
.x
< a
->edge
.line
.p2
.x
) {
285 amin
= a
->edge
.line
.p1
.x
;
286 amax
= a
->edge
.line
.p2
.x
;
288 amin
= a
->edge
.line
.p2
.x
;
289 amax
= a
->edge
.line
.p1
.x
;
291 if (b
->edge
.line
.p1
.x
< b
->edge
.line
.p2
.x
) {
292 bmin
= b
->edge
.line
.p1
.x
;
293 bmax
= b
->edge
.line
.p2
.x
;
295 bmin
= b
->edge
.line
.p2
.x
;
296 bmax
= b
->edge
.line
.p1
.x
;
298 if (amax
< bmin
) return -1;
299 if (amin
> bmax
) return +1;
302 ady
= a
->edge
.line
.p2
.y
- a
->edge
.line
.p1
.y
;
303 adx
= a
->edge
.line
.p2
.x
- a
->edge
.line
.p1
.x
;
305 have_dx_adx_bdx
&= ~HAVE_ADX
;
307 bdy
= b
->edge
.line
.p2
.y
- b
->edge
.line
.p1
.y
;
308 bdx
= b
->edge
.line
.p2
.x
- b
->edge
.line
.p1
.x
;
310 have_dx_adx_bdx
&= ~HAVE_BDX
;
312 dx
= a
->edge
.line
.p1
.x
- b
->edge
.line
.p1
.x
;
314 have_dx_adx_bdx
&= ~HAVE_DX
;
316 #define L _cairo_int64x32_128_mul (_cairo_int32x32_64_mul (ady, bdy), dx)
317 #define A _cairo_int64x32_128_mul (_cairo_int32x32_64_mul (adx, bdy), y - a->edge.line.p1.y)
318 #define B _cairo_int64x32_128_mul (_cairo_int32x32_64_mul (bdx, ady), y - b->edge.line.p1.y)
319 switch (have_dx_adx_bdx
) {
324 /* A_dy * B_dy * (A_x - B_x) ∘ 0 */
325 return dx
; /* ady * bdy is positive definite */
327 /* 0 ∘ - (Y - A_y) * A_dx * B_dy */
328 return adx
; /* bdy * (y - a->top.y) is positive definite */
330 /* 0 ∘ (Y - B_y) * B_dx * A_dy */
331 return -bdx
; /* ady * (y - b->top.y) is positive definite */
333 /* 0 ∘ (Y - B_y) * B_dx * A_dy - (Y - A_y) * A_dx * B_dy */
334 if ((adx
^ bdx
) < 0) {
336 } else if (a
->edge
.line
.p1
.y
== b
->edge
.line
.p1
.y
) { /* common origin */
337 cairo_int64_t adx_bdy
, bdx_ady
;
339 /* ∴ A_dx * B_dy ∘ B_dx * A_dy */
341 adx_bdy
= _cairo_int32x32_64_mul (adx
, bdy
);
342 bdx_ady
= _cairo_int32x32_64_mul (bdx
, ady
);
344 return _cairo_int64_cmp (adx_bdy
, bdx_ady
);
346 return _cairo_int128_cmp (A
, B
);
348 /* A_dy * (A_x - B_x) ∘ - (Y - A_y) * A_dx */
349 if ((-adx
^ dx
) < 0) {
352 cairo_int64_t ady_dx
, dy_adx
;
354 ady_dx
= _cairo_int32x32_64_mul (ady
, dx
);
355 dy_adx
= _cairo_int32x32_64_mul (a
->edge
.line
.p1
.y
- y
, adx
);
357 return _cairo_int64_cmp (ady_dx
, dy_adx
);
360 /* B_dy * (A_x - B_x) ∘ (Y - B_y) * B_dx */
361 if ((bdx
^ dx
) < 0) {
364 cairo_int64_t bdy_dx
, dy_bdx
;
366 bdy_dx
= _cairo_int32x32_64_mul (bdy
, dx
);
367 dy_bdx
= _cairo_int32x32_64_mul (y
- b
->edge
.line
.p1
.y
, bdx
);
369 return _cairo_int64_cmp (bdy_dx
, dy_bdx
);
372 /* XXX try comparing (a->edge.line.p2.x - b->edge.line.p2.x) et al */
373 return _cairo_int128_cmp (L
, _cairo_int128_sub (B
, A
));
381 * We need to compare the x-coordinate of a line for a particular y wrt to a
382 * given x, without loss of precision.
384 * The x-coordinate along an edge for a given y is:
385 * X = A_x + (Y - A_y) * A_dx / A_dy
387 * So the inequality we wish to test is:
388 * A_x + (Y - A_y) * A_dx / A_dy ∘ X
389 * where ∘ is our inequality operator.
391 * By construction, we know that A_dy (and (Y - A_y)) are
392 * all positive, so we can rearrange it thus without causing a sign change:
393 * (Y - A_y) * A_dx ∘ (X - A_x) * A_dy
395 * Given the assumption that all the deltas fit within 32 bits, we can compute
396 * this comparison directly using 64 bit arithmetic.
398 * See the similar discussion for _slope_compare() and
399 * edges_compare_x_for_y_general().
402 edge_compare_for_y_against_x (const cairo_bo_edge_t
*a
,
410 if (x
< a
->edge
.line
.p1
.x
&& x
< a
->edge
.line
.p2
.x
)
412 if (x
> a
->edge
.line
.p1
.x
&& x
> a
->edge
.line
.p2
.x
)
415 adx
= a
->edge
.line
.p2
.x
- a
->edge
.line
.p1
.x
;
416 dx
= x
- a
->edge
.line
.p1
.x
;
420 if (dx
== 0 || (adx
^ dx
) < 0)
423 dy
= y
- a
->edge
.line
.p1
.y
;
424 ady
= a
->edge
.line
.p2
.y
- a
->edge
.line
.p1
.y
;
426 L
= _cairo_int32x32_64_mul (dy
, adx
);
427 R
= _cairo_int32x32_64_mul (dx
, ady
);
429 return _cairo_int64_cmp (L
, R
);
433 edges_compare_x_for_y (const cairo_bo_edge_t
*a
,
434 const cairo_bo_edge_t
*b
,
437 /* If the sweep-line is currently on an end-point of a line,
438 * then we know its precise x value (and considering that we often need to
439 * compare events at end-points, this happens frequently enough to warrant
446 HAVE_BOTH
= HAVE_AX
| HAVE_BX
447 } have_ax_bx
= HAVE_BOTH
;
450 if (y
== a
->edge
.line
.p1
.y
)
451 ax
= a
->edge
.line
.p1
.x
;
452 else if (y
== a
->edge
.line
.p2
.y
)
453 ax
= a
->edge
.line
.p2
.x
;
455 have_ax_bx
&= ~HAVE_AX
;
457 if (y
== b
->edge
.line
.p1
.y
)
458 bx
= b
->edge
.line
.p1
.x
;
459 else if (y
== b
->edge
.line
.p2
.y
)
460 bx
= b
->edge
.line
.p2
.x
;
462 have_ax_bx
&= ~HAVE_BX
;
464 switch (have_ax_bx
) {
467 return edges_compare_x_for_y_general (a
, b
, y
);
469 return -edge_compare_for_y_against_x (b
, y
, ax
);
471 return edge_compare_for_y_against_x (a
, y
, bx
);
478 _line_equal (const cairo_line_t
*a
, const cairo_line_t
*b
)
480 return (a
->p1
.x
== b
->p1
.x
&& a
->p1
.y
== b
->p1
.y
&&
481 a
->p2
.x
== b
->p2
.x
&& a
->p2
.y
== b
->p2
.y
);
485 _cairo_bo_sweep_line_compare_edges (cairo_bo_sweep_line_t
*sweep_line
,
486 const cairo_bo_edge_t
*a
,
487 const cairo_bo_edge_t
*b
)
491 /* compare the edges if not identical */
492 if (! _line_equal (&a
->edge
.line
, &b
->edge
.line
)) {
493 cmp
= edges_compare_x_for_y (a
, b
, sweep_line
->current_y
);
497 /* The two edges intersect exactly at y, so fall back on slope
498 * comparison. We know that this compare_edges function will be
499 * called only when starting a new edge, (not when stopping an
500 * edge), so we don't have to worry about conditionally inverting
501 * the sense of _slope_compare. */
502 cmp
= _slope_compare (a
, b
);
507 /* We've got two collinear edges now. */
508 return b
->edge
.bottom
- a
->edge
.bottom
;
511 static inline cairo_int64_t
512 det32_64 (int32_t a
, int32_t b
,
513 int32_t c
, int32_t d
)
515 /* det = a * d - b * c */
516 return _cairo_int64_sub (_cairo_int32x32_64_mul (a
, d
),
517 _cairo_int32x32_64_mul (b
, c
));
520 static inline cairo_int128_t
521 det64x32_128 (cairo_int64_t a
, int32_t b
,
522 cairo_int64_t c
, int32_t d
)
524 /* det = a * d - b * c */
525 return _cairo_int128_sub (_cairo_int64x32_128_mul (a
, d
),
526 _cairo_int64x32_128_mul (c
, b
));
529 /* Compute the intersection of two lines as defined by two edges. The
530 * result is provided as a coordinate pair of 128-bit integers.
532 * Returns %CAIRO_BO_STATUS_INTERSECTION if there is an intersection or
533 * %CAIRO_BO_STATUS_PARALLEL if the two lines are exactly parallel.
536 intersect_lines (cairo_bo_edge_t
*a
,
538 cairo_bo_intersect_point_t
*intersection
)
540 cairo_int64_t a_det
, b_det
;
542 /* XXX: We're assuming here that dx and dy will still fit in 32
543 * bits. That's not true in general as there could be overflow. We
544 * should prevent that before the tessellation algorithm begins.
545 * What we're doing to mitigate this is to perform clamping in
546 * cairo_bo_tessellate_polygon().
548 int32_t dx1
= a
->edge
.line
.p1
.x
- a
->edge
.line
.p2
.x
;
549 int32_t dy1
= a
->edge
.line
.p1
.y
- a
->edge
.line
.p2
.y
;
551 int32_t dx2
= b
->edge
.line
.p1
.x
- b
->edge
.line
.p2
.x
;
552 int32_t dy2
= b
->edge
.line
.p1
.y
- b
->edge
.line
.p2
.y
;
554 cairo_int64_t den_det
;
558 den_det
= det32_64 (dx1
, dy1
, dx2
, dy2
);
560 /* Q: Can we determine that the lines do not intersect (within range)
561 * much more cheaply than computing the intersection point i.e. by
562 * avoiding the division?
564 * X = ax + t * adx = bx + s * bdx;
565 * Y = ay + t * ady = by + s * bdy;
566 * ∴ t * (ady*bdx - bdy*adx) = bdx * (by - ay) + bdy * (ax - bx)
569 * Therefore we can reject any intersection (under the criteria for
570 * valid intersection events) if:
571 * L^R < 0 => t < 0, or
574 * (where top/bottom must at least extend to the line endpoints).
576 * A similar substitution can be performed for s, yielding:
577 * s * (ady*bdx - bdy*adx) = ady * (ax - bx) - adx * (ay - by)
579 R
= det32_64 (dx2
, dy2
,
580 b
->edge
.line
.p1
.x
- a
->edge
.line
.p1
.x
,
581 b
->edge
.line
.p1
.y
- a
->edge
.line
.p1
.y
);
582 if (_cairo_int64_negative (den_det
)) {
583 if (_cairo_int64_ge (den_det
, R
))
586 if (_cairo_int64_le (den_det
, R
))
590 R
= det32_64 (dy1
, dx1
,
591 a
->edge
.line
.p1
.y
- b
->edge
.line
.p1
.y
,
592 a
->edge
.line
.p1
.x
- b
->edge
.line
.p1
.x
);
593 if (_cairo_int64_negative (den_det
)) {
594 if (_cairo_int64_ge (den_det
, R
))
597 if (_cairo_int64_le (den_det
, R
))
601 /* We now know that the two lines should intersect within range. */
603 a_det
= det32_64 (a
->edge
.line
.p1
.x
, a
->edge
.line
.p1
.y
,
604 a
->edge
.line
.p2
.x
, a
->edge
.line
.p2
.y
);
605 b_det
= det32_64 (b
->edge
.line
.p1
.x
, b
->edge
.line
.p1
.y
,
606 b
->edge
.line
.p2
.x
, b
->edge
.line
.p2
.y
);
608 /* x = det (a_det, dx1, b_det, dx2) / den_det */
609 qr
= _cairo_int_96by64_32x64_divrem (det64x32_128 (a_det
, dx1
,
612 if (_cairo_int64_eq (qr
.rem
, den_det
))
615 intersection
->x
.exactness
= _cairo_int64_is_zero (qr
.rem
) ? EXACT
: INEXACT
;
617 intersection
->x
.exactness
= EXACT
;
618 if (! _cairo_int64_is_zero (qr
.rem
)) {
619 if (_cairo_int64_negative (den_det
) ^ _cairo_int64_negative (qr
.rem
))
620 qr
.rem
= _cairo_int64_negate (qr
.rem
);
621 qr
.rem
= _cairo_int64_mul (qr
.rem
, _cairo_int32_to_int64 (2));
622 if (_cairo_int64_ge (qr
.rem
, den_det
)) {
623 qr
.quo
= _cairo_int64_add (qr
.quo
,
624 _cairo_int32_to_int64 (_cairo_int64_negative (qr
.quo
) ? -1 : 1));
626 intersection
->x
.exactness
= INEXACT
;
629 intersection
->x
.ordinate
= _cairo_int64_to_int32 (qr
.quo
);
631 /* y = det (a_det, dy1, b_det, dy2) / den_det */
632 qr
= _cairo_int_96by64_32x64_divrem (det64x32_128 (a_det
, dy1
,
635 if (_cairo_int64_eq (qr
.rem
, den_det
))
638 intersection
->y
.exactness
= _cairo_int64_is_zero (qr
.rem
) ? EXACT
: INEXACT
;
640 intersection
->y
.exactness
= EXACT
;
641 if (! _cairo_int64_is_zero (qr
.rem
)) {
642 if (_cairo_int64_negative (den_det
) ^ _cairo_int64_negative (qr
.rem
))
643 qr
.rem
= _cairo_int64_negate (qr
.rem
);
644 qr
.rem
= _cairo_int64_mul (qr
.rem
, _cairo_int32_to_int64 (2));
645 if (_cairo_int64_ge (qr
.rem
, den_det
)) {
646 qr
.quo
= _cairo_int64_add (qr
.quo
,
647 _cairo_int32_to_int64 (_cairo_int64_negative (qr
.quo
) ? -1 : 1));
649 intersection
->y
.exactness
= INEXACT
;
652 intersection
->y
.ordinate
= _cairo_int64_to_int32 (qr
.quo
);
658 _cairo_bo_intersect_ordinate_32_compare (cairo_bo_intersect_ordinate_t a
,
661 /* First compare the quotient */
666 /* With quotient identical, if remainder is 0 then compare equal */
667 /* Otherwise, the non-zero remainder makes a > b */
668 return INEXACT
== a
.exactness
;
671 /* Does the given edge contain the given point. The point must already
672 * be known to be contained within the line determined by the edge,
673 * (most likely the point results from an intersection of this edge
676 * If we had exact arithmetic, then this function would simply be a
677 * matter of examining whether the y value of the point lies within
678 * the range of y values of the edge. But since intersection points
679 * are not exact due to being rounded to the nearest integer within
680 * the available precision, we must also examine the x value of the
683 * The definition of "contains" here is that the given intersection
684 * point will be seen by the sweep line after the start event for the
685 * given edge and before the stop event for the edge. See the comments
686 * in the implementation for more details.
689 _cairo_bo_edge_contains_intersect_point (cairo_bo_edge_t
*edge
,
690 cairo_bo_intersect_point_t
*point
)
692 int cmp_top
, cmp_bottom
;
694 /* XXX: When running the actual algorithm, we don't actually need to
695 * compare against edge->top at all here, since any intersection above
696 * top is eliminated early via a slope comparison. We're leaving these
697 * here for now only for the sake of the quadratic-time intersection
698 * finder which needs them.
701 cmp_top
= _cairo_bo_intersect_ordinate_32_compare (point
->y
,
703 cmp_bottom
= _cairo_bo_intersect_ordinate_32_compare (point
->y
,
706 if (cmp_top
< 0 || cmp_bottom
> 0)
711 if (cmp_top
> 0 && cmp_bottom
< 0)
716 /* At this stage, the point lies on the same y value as either
717 * edge->top or edge->bottom, so we have to examine the x value in
718 * order to properly determine containment. */
720 /* If the y value of the point is the same as the y value of the
721 * top of the edge, then the x value of the point must be greater
722 * to be considered as inside the edge. Similarly, if the y value
723 * of the point is the same as the y value of the bottom of the
724 * edge, then the x value of the point must be less to be
725 * considered as inside. */
730 top_x
= _line_compute_intersection_x_for_y (&edge
->edge
.line
,
732 return _cairo_bo_intersect_ordinate_32_compare (point
->x
, top_x
) > 0;
733 } else { /* cmp_bottom == 0 */
736 bot_x
= _line_compute_intersection_x_for_y (&edge
->edge
.line
,
738 return _cairo_bo_intersect_ordinate_32_compare (point
->x
, bot_x
) < 0;
742 /* Compute the intersection of two edges. The result is provided as a
743 * coordinate pair of 128-bit integers.
745 * Returns %CAIRO_BO_STATUS_INTERSECTION if there is an intersection
746 * that is within both edges, %CAIRO_BO_STATUS_NO_INTERSECTION if the
747 * intersection of the lines defined by the edges occurs outside of
748 * one or both edges, and %CAIRO_BO_STATUS_PARALLEL if the two edges
749 * are exactly parallel.
751 * Note that when determining if a candidate intersection is "inside"
752 * an edge, we consider both the infinitesimal shortening and the
753 * infinitesimal tilt rules described by John Hobby. Specifically, if
754 * the intersection is exactly the same as an edge point, it is
755 * effectively outside (no intersection is returned). Also, if the
756 * intersection point has the same
759 _cairo_bo_edge_intersect (cairo_bo_edge_t
*a
,
761 cairo_bo_point32_t
*intersection
)
763 cairo_bo_intersect_point_t quorem
;
765 if (! intersect_lines (a
, b
, &quorem
))
768 if (! _cairo_bo_edge_contains_intersect_point (a
, &quorem
))
771 if (! _cairo_bo_edge_contains_intersect_point (b
, &quorem
))
774 /* Now that we've correctly compared the intersection point and
775 * determined that it lies within the edge, then we know that we
776 * no longer need any more bits of storage for the intersection
777 * than we do for our edge coordinates. We also no longer need the
778 * remainder from the division. */
779 intersection
->x
= quorem
.x
.ordinate
;
780 intersection
->y
= quorem
.y
.ordinate
;
786 cairo_bo_event_compare (const cairo_bo_event_t
*a
,
787 const cairo_bo_event_t
*b
)
791 cmp
= _cairo_bo_point32_compare (&a
->point
, &b
->point
);
795 cmp
= a
->type
- b
->type
;
803 _pqueue_init (pqueue_t
*pq
)
805 pq
->max_size
= ARRAY_LENGTH (pq
->elements_embedded
);
808 pq
->elements
= pq
->elements_embedded
;
812 _pqueue_fini (pqueue_t
*pq
)
814 if (pq
->elements
!= pq
->elements_embedded
)
818 static cairo_status_t
819 _pqueue_grow (pqueue_t
*pq
)
821 cairo_bo_event_t
**new_elements
;
824 if (pq
->elements
== pq
->elements_embedded
) {
825 new_elements
= _cairo_malloc_ab (pq
->max_size
,
826 sizeof (cairo_bo_event_t
*));
827 if (unlikely (new_elements
== NULL
))
828 return _cairo_error (CAIRO_STATUS_NO_MEMORY
);
830 memcpy (new_elements
, pq
->elements_embedded
,
831 sizeof (pq
->elements_embedded
));
833 new_elements
= _cairo_realloc_ab (pq
->elements
,
835 sizeof (cairo_bo_event_t
*));
836 if (unlikely (new_elements
== NULL
))
837 return _cairo_error (CAIRO_STATUS_NO_MEMORY
);
840 pq
->elements
= new_elements
;
841 return CAIRO_STATUS_SUCCESS
;
844 static inline cairo_status_t
845 _pqueue_push (pqueue_t
*pq
, cairo_bo_event_t
*event
)
847 cairo_bo_event_t
**elements
;
850 if (unlikely (pq
->size
+ 1 == pq
->max_size
)) {
851 cairo_status_t status
;
853 status
= _pqueue_grow (pq
);
854 if (unlikely (status
))
858 elements
= pq
->elements
;
861 i
!= PQ_FIRST_ENTRY
&&
862 cairo_bo_event_compare (event
,
863 elements
[parent
= PQ_PARENT_INDEX (i
)]) < 0;
866 elements
[i
] = elements
[parent
];
871 return CAIRO_STATUS_SUCCESS
;
875 _pqueue_pop (pqueue_t
*pq
)
877 cairo_bo_event_t
**elements
= pq
->elements
;
878 cairo_bo_event_t
*tail
;
881 tail
= elements
[pq
->size
--];
883 elements
[PQ_FIRST_ENTRY
] = NULL
;
887 for (i
= PQ_FIRST_ENTRY
;
888 (child
= PQ_LEFT_CHILD_INDEX (i
)) <= pq
->size
;
891 if (child
!= pq
->size
&&
892 cairo_bo_event_compare (elements
[child
+1],
893 elements
[child
]) < 0)
898 if (cairo_bo_event_compare (elements
[child
], tail
) >= 0)
901 elements
[i
] = elements
[child
];
906 static inline cairo_status_t
907 _cairo_bo_event_queue_insert (cairo_bo_event_queue_t
*queue
,
908 cairo_bo_event_type_t type
,
911 const cairo_point_t
*point
)
913 cairo_bo_queue_event_t
*event
;
915 event
= _cairo_freepool_alloc (&queue
->pool
);
916 if (unlikely (event
== NULL
))
917 return _cairo_error (CAIRO_STATUS_NO_MEMORY
);
922 event
->point
= *point
;
924 return _pqueue_push (&queue
->pqueue
, (cairo_bo_event_t
*) event
);
928 _cairo_bo_event_queue_delete (cairo_bo_event_queue_t
*queue
,
929 cairo_bo_event_t
*event
)
931 _cairo_freepool_free (&queue
->pool
, event
);
934 static cairo_bo_event_t
*
935 _cairo_bo_event_dequeue (cairo_bo_event_queue_t
*event_queue
)
937 cairo_bo_event_t
*event
, *cmp
;
939 event
= event_queue
->pqueue
.elements
[PQ_FIRST_ENTRY
];
940 cmp
= *event_queue
->start_events
;
942 (cmp
!= NULL
&& cairo_bo_event_compare (cmp
, event
) < 0))
945 event_queue
->start_events
++;
949 _pqueue_pop (&event_queue
->pqueue
);
955 CAIRO_COMBSORT_DECLARE (_cairo_bo_event_queue_sort
,
957 cairo_bo_event_compare
)
960 _cairo_bo_event_queue_init (cairo_bo_event_queue_t
*event_queue
,
961 cairo_bo_event_t
**start_events
,
964 _cairo_bo_event_queue_sort (start_events
, num_events
);
965 start_events
[num_events
] = NULL
;
967 event_queue
->start_events
= start_events
;
969 _cairo_freepool_init (&event_queue
->pool
,
970 sizeof (cairo_bo_queue_event_t
));
971 _pqueue_init (&event_queue
->pqueue
);
972 event_queue
->pqueue
.elements
[PQ_FIRST_ENTRY
] = NULL
;
975 static cairo_status_t
976 _cairo_bo_event_queue_insert_stop (cairo_bo_event_queue_t
*event_queue
,
977 cairo_bo_edge_t
*edge
)
979 cairo_bo_point32_t point
;
981 point
.y
= edge
->edge
.bottom
;
982 point
.x
= _line_compute_intersection_x_for_y (&edge
->edge
.line
,
984 return _cairo_bo_event_queue_insert (event_queue
,
985 CAIRO_BO_EVENT_TYPE_STOP
,
991 _cairo_bo_event_queue_fini (cairo_bo_event_queue_t
*event_queue
)
993 _pqueue_fini (&event_queue
->pqueue
);
994 _cairo_freepool_fini (&event_queue
->pool
);
997 static inline cairo_status_t
998 _cairo_bo_event_queue_insert_if_intersect_below_current_y (cairo_bo_event_queue_t
*event_queue
,
999 cairo_bo_edge_t
*left
,
1000 cairo_bo_edge_t
*right
)
1002 cairo_bo_point32_t intersection
;
1004 if (_line_equal (&left
->edge
.line
, &right
->edge
.line
))
1005 return CAIRO_STATUS_SUCCESS
;
1007 /* The names "left" and "right" here are correct descriptions of
1008 * the order of the two edges within the active edge list. So if a
1009 * slope comparison also puts left less than right, then we know
1010 * that the intersection of these two segments has already
1011 * occurred before the current sweep line position. */
1012 if (_slope_compare (left
, right
) <= 0)
1013 return CAIRO_STATUS_SUCCESS
;
1015 if (! _cairo_bo_edge_intersect (left
, right
, &intersection
))
1016 return CAIRO_STATUS_SUCCESS
;
1018 return _cairo_bo_event_queue_insert (event_queue
,
1019 CAIRO_BO_EVENT_TYPE_INTERSECTION
,
1025 _cairo_bo_sweep_line_init (cairo_bo_sweep_line_t
*sweep_line
)
1027 sweep_line
->head
= NULL
;
1028 sweep_line
->current_y
= INT32_MIN
;
1029 sweep_line
->current_edge
= NULL
;
1032 static cairo_status_t
1033 _cairo_bo_sweep_line_insert (cairo_bo_sweep_line_t
*sweep_line
,
1034 cairo_bo_edge_t
*edge
)
1036 if (sweep_line
->current_edge
!= NULL
) {
1037 cairo_bo_edge_t
*prev
, *next
;
1040 cmp
= _cairo_bo_sweep_line_compare_edges (sweep_line
,
1041 sweep_line
->current_edge
,
1044 prev
= sweep_line
->current_edge
;
1046 while (next
!= NULL
&&
1047 _cairo_bo_sweep_line_compare_edges (sweep_line
,
1050 prev
= next
, next
= prev
->next
;
1058 } else if (cmp
> 0) {
1059 next
= sweep_line
->current_edge
;
1061 while (prev
!= NULL
&&
1062 _cairo_bo_sweep_line_compare_edges (sweep_line
,
1065 next
= prev
, prev
= next
->prev
;
1074 sweep_line
->head
= edge
;
1076 prev
= sweep_line
->current_edge
;
1078 edge
->next
= prev
->next
;
1079 if (prev
->next
!= NULL
)
1080 prev
->next
->prev
= edge
;
1084 sweep_line
->head
= edge
;
1087 sweep_line
->current_edge
= edge
;
1089 return CAIRO_STATUS_SUCCESS
;
1093 _cairo_bo_sweep_line_delete (cairo_bo_sweep_line_t
*sweep_line
,
1094 cairo_bo_edge_t
*edge
)
1096 if (edge
->prev
!= NULL
)
1097 edge
->prev
->next
= edge
->next
;
1099 sweep_line
->head
= edge
->next
;
1101 if (edge
->next
!= NULL
)
1102 edge
->next
->prev
= edge
->prev
;
1104 if (sweep_line
->current_edge
== edge
)
1105 sweep_line
->current_edge
= edge
->prev
? edge
->prev
: edge
->next
;
1109 _cairo_bo_sweep_line_swap (cairo_bo_sweep_line_t
*sweep_line
,
1110 cairo_bo_edge_t
*left
,
1111 cairo_bo_edge_t
*right
)
1113 if (left
->prev
!= NULL
)
1114 left
->prev
->next
= right
;
1116 sweep_line
->head
= right
;
1118 if (right
->next
!= NULL
)
1119 right
->next
->prev
= left
;
1121 left
->next
= right
->next
;
1124 right
->prev
= left
->prev
;
1128 static inline cairo_bool_t
1129 edges_colinear (const cairo_bo_edge_t
*a
, const cairo_bo_edge_t
*b
)
1131 if (_line_equal (&a
->edge
.line
, &b
->edge
.line
))
1134 if (_slope_compare (a
, b
))
1137 /* The choice of y is not truly arbitrary since we must guarantee that it
1138 * is greater than the start of either line.
1140 if (a
->edge
.line
.p1
.y
== b
->edge
.line
.p1
.y
) {
1141 return a
->edge
.line
.p1
.x
== b
->edge
.line
.p1
.x
;
1142 } else if (a
->edge
.line
.p2
.y
== b
->edge
.line
.p2
.y
) {
1143 return a
->edge
.line
.p2
.x
== b
->edge
.line
.p2
.x
;
1144 } else if (a
->edge
.line
.p1
.y
< b
->edge
.line
.p1
.y
) {
1145 return edge_compare_for_y_against_x (b
,
1147 a
->edge
.line
.p1
.x
) == 0;
1149 return edge_compare_for_y_against_x (a
,
1151 b
->edge
.line
.p1
.x
) == 0;
1156 _cairo_bo_edge_end (cairo_bo_edge_t
*left
,
1158 cairo_polygon_t
*polygon
)
1160 cairo_bo_deferred_t
*d
= &left
->deferred
;
1162 if (likely (d
->top
< bot
)) {
1163 _cairo_polygon_add_line (polygon
,
1167 _cairo_polygon_add_line (polygon
,
1168 &d
->right
->edge
.line
,
1178 _cairo_bo_edge_start_or_continue (cairo_bo_edge_t
*left
,
1179 cairo_bo_edge_t
*right
,
1181 cairo_polygon_t
*polygon
)
1183 if (left
->deferred
.right
== right
)
1186 if (left
->deferred
.right
!= NULL
) {
1187 if (right
!= NULL
&& edges_colinear (left
->deferred
.right
, right
))
1189 /* continuation on right, so just swap edges */
1190 left
->deferred
.right
= right
;
1194 _cairo_bo_edge_end (left
, top
, polygon
);
1197 if (right
!= NULL
&& ! edges_colinear (left
, right
)) {
1198 left
->deferred
.top
= top
;
1199 left
->deferred
.right
= right
;
1204 _active_edges_to_polygon (cairo_bo_edge_t
*left
,
1206 cairo_fill_rule_t fill_rule
,
1207 cairo_polygon_t
*polygon
)
1209 cairo_bo_edge_t
*right
;
1212 if (fill_rule
== CAIRO_FILL_RULE_WINDING
)
1217 while (left
!= NULL
) {
1218 int in_out
= left
->edge
.dir
;
1221 if (left
->deferred
.right
== NULL
) {
1222 while (right
!= NULL
&& right
->deferred
.right
== NULL
)
1223 right
= right
->next
;
1225 if (right
!= NULL
&& edges_colinear (left
, right
)) {
1226 /* continuation on left */
1227 left
->deferred
= right
->deferred
;
1228 right
->deferred
.right
= NULL
;
1233 while (right
!= NULL
) {
1234 if (right
->deferred
.right
!= NULL
)
1235 _cairo_bo_edge_end (right
, top
, polygon
);
1237 in_out
+= right
->edge
.dir
;
1238 if ((in_out
& mask
) == 0) {
1239 /* skip co-linear edges */
1240 if (right
->next
== NULL
|| !edges_colinear (right
, right
->next
))
1244 right
= right
->next
;
1247 _cairo_bo_edge_start_or_continue (left
, right
, top
, polygon
);
1256 static cairo_status_t
1257 _cairo_bentley_ottmann_tessellate_bo_edges (cairo_bo_event_t
**start_events
,
1259 cairo_fill_rule_t fill_rule
,
1260 cairo_polygon_t
*polygon
)
1262 cairo_status_t status
= CAIRO_STATUS_SUCCESS
; /* silence compiler */
1263 cairo_bo_event_queue_t event_queue
;
1264 cairo_bo_sweep_line_t sweep_line
;
1265 cairo_bo_event_t
*event
;
1266 cairo_bo_edge_t
*left
, *right
;
1267 cairo_bo_edge_t
*e1
, *e2
;
1269 _cairo_bo_event_queue_init (&event_queue
, start_events
, num_events
);
1270 _cairo_bo_sweep_line_init (&sweep_line
);
1272 while ((event
= _cairo_bo_event_dequeue (&event_queue
))) {
1273 if (event
->point
.y
!= sweep_line
.current_y
) {
1274 _active_edges_to_polygon (sweep_line
.head
,
1275 sweep_line
.current_y
,
1276 fill_rule
, polygon
);
1278 sweep_line
.current_y
= event
->point
.y
;
1281 switch (event
->type
) {
1282 case CAIRO_BO_EVENT_TYPE_START
:
1283 e1
= &((cairo_bo_start_event_t
*) event
)->edge
;
1285 status
= _cairo_bo_sweep_line_insert (&sweep_line
, e1
);
1286 if (unlikely (status
))
1289 status
= _cairo_bo_event_queue_insert_stop (&event_queue
, e1
);
1290 if (unlikely (status
))
1297 status
= _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue
, left
, e1
);
1298 if (unlikely (status
))
1302 if (right
!= NULL
) {
1303 status
= _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue
, e1
, right
);
1304 if (unlikely (status
))
1310 case CAIRO_BO_EVENT_TYPE_STOP
:
1311 e1
= ((cairo_bo_queue_event_t
*) event
)->e1
;
1312 _cairo_bo_event_queue_delete (&event_queue
, event
);
1317 _cairo_bo_sweep_line_delete (&sweep_line
, e1
);
1319 if (e1
->deferred
.right
!= NULL
)
1320 _cairo_bo_edge_end (e1
, e1
->edge
.bottom
, polygon
);
1322 if (left
!= NULL
&& right
!= NULL
) {
1323 status
= _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue
, left
, right
);
1324 if (unlikely (status
))
1330 case CAIRO_BO_EVENT_TYPE_INTERSECTION
:
1331 e1
= ((cairo_bo_queue_event_t
*) event
)->e1
;
1332 e2
= ((cairo_bo_queue_event_t
*) event
)->e2
;
1333 _cairo_bo_event_queue_delete (&event_queue
, event
);
1335 /* skip this intersection if its edges are not adjacent */
1342 _cairo_bo_sweep_line_swap (&sweep_line
, e1
, e2
);
1344 /* after the swap e2 is left of e1 */
1347 status
= _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue
, left
, e2
);
1348 if (unlikely (status
))
1352 if (right
!= NULL
) {
1353 status
= _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue
, e1
, right
);
1354 if (unlikely (status
))
1363 _cairo_bo_event_queue_fini (&event_queue
);
1369 _cairo_polygon_reduce (cairo_polygon_t
*polygon
,
1370 cairo_fill_rule_t fill_rule
)
1372 cairo_status_t status
;
1373 cairo_bo_start_event_t stack_events
[CAIRO_STACK_ARRAY_LENGTH (cairo_bo_start_event_t
)];
1374 cairo_bo_start_event_t
*events
;
1375 cairo_bo_event_t
*stack_event_ptrs
[ARRAY_LENGTH (stack_events
) + 1];
1376 cairo_bo_event_t
**event_ptrs
;
1381 num_events
= polygon
->num_edges
;
1382 if (unlikely (0 == num_events
))
1383 return CAIRO_STATUS_SUCCESS
;
1385 if (DEBUG_POLYGON
) {
1386 FILE *file
= fopen ("reduce_in.txt", "w");
1387 _cairo_debug_print_polygon (file
, polygon
);
1391 events
= stack_events
;
1392 event_ptrs
= stack_event_ptrs
;
1393 if (num_events
> ARRAY_LENGTH (stack_events
)) {
1394 events
= _cairo_malloc_ab_plus_c (num_events
,
1395 sizeof (cairo_bo_start_event_t
) +
1396 sizeof (cairo_bo_event_t
*),
1397 sizeof (cairo_bo_event_t
*));
1398 if (unlikely (events
== NULL
))
1399 return _cairo_error (CAIRO_STATUS_NO_MEMORY
);
1401 event_ptrs
= (cairo_bo_event_t
**) (events
+ num_events
);
1404 for (i
= 0; i
< num_events
; i
++) {
1405 event_ptrs
[i
] = (cairo_bo_event_t
*) &events
[i
];
1407 events
[i
].type
= CAIRO_BO_EVENT_TYPE_START
;
1408 events
[i
].point
.y
= polygon
->edges
[i
].top
;
1410 _line_compute_intersection_x_for_y (&polygon
->edges
[i
].line
,
1413 events
[i
].edge
.edge
= polygon
->edges
[i
];
1414 events
[i
].edge
.deferred
.right
= NULL
;
1415 events
[i
].edge
.prev
= NULL
;
1416 events
[i
].edge
.next
= NULL
;
1419 num_limits
= polygon
->num_limits
; polygon
->num_limits
= 0;
1420 polygon
->num_edges
= 0;
1422 status
= _cairo_bentley_ottmann_tessellate_bo_edges (event_ptrs
,
1426 polygon
->num_limits
= num_limits
;
1428 if (events
!= stack_events
)
1431 if (DEBUG_POLYGON
) {
1432 FILE *file
= fopen ("reduce_out.txt", "w");
1433 _cairo_debug_print_polygon (file
, polygon
);