src/cairo-polygon-reduce.c

   1 /*
   2  * Copyright © 2004 Carl Worth
   3  * Copyright © 2006 Red Hat, Inc.
   4  * Copyright © 2008 Chris Wilson
   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
  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
  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 Carl Worth
  32  *
  33  * Contributor(s):
  34  *      Carl D. Worth <cworth@cworth.org>
  35  *      Chris Wilson <chris@chris-wilson.co.uk>
  36  */
  37
  38 /* Provide definitions for standalone compilation */
  39 #include "cairoint.h"
  40
  41 #include "cairo-error-private.h"
  42 #include "cairo-freelist-private.h"
  43 #include "cairo-combsort-inline.h"
  44
  45 #define DEBUG_POLYGON 0
  46
  47 typedef cairo_point_t cairo_bo_point32_t;
  48
  49 typedef struct _cairo_bo_intersect_ordinate {
  50     int32_t ordinate;
  51     enum { EXACT, INEXACT } exactness;
  52 } cairo_bo_intersect_ordinate_t;
  53
  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;
  58
  59 typedef struct _cairo_bo_edge cairo_bo_edge_t;
  60
  61 typedef struct _cairo_bo_deferred {
  62     cairo_bo_edge_t *right;
  63     int32_t top;
  64 } cairo_bo_deferred_t;
  65
  66 struct _cairo_bo_edge {
  67     cairo_edge_t edge;
  68     cairo_bo_edge_t *prev;
  69     cairo_bo_edge_t *next;
  70     cairo_bo_deferred_t deferred;
  71 };
  72
  73 /* the parent is always given by index/2 */
  74 #define PQ_PARENT_INDEX(i) ((i) >> 1)
  75 #define PQ_FIRST_ENTRY 1
  76
  77 /* left and right children are index * 2 and (index * 2) +1 respectively */
  78 #define PQ_LEFT_CHILD_INDEX(i) ((i) << 1)
  79
  80 typedef enum {
  81     CAIRO_BO_EVENT_TYPE_STOP,
  82     CAIRO_BO_EVENT_TYPE_INTERSECTION,
  83     CAIRO_BO_EVENT_TYPE_START
  84 } cairo_bo_event_type_t;
  85
  86 typedef struct _cairo_bo_event {
  87     cairo_bo_event_type_t type;
  88     cairo_point_t point;
  89 } cairo_bo_event_t;
  90
  91 typedef struct _cairo_bo_start_event {
  92     cairo_bo_event_type_t type;
  93     cairo_point_t point;
  94     cairo_bo_edge_t edge;
  95 } cairo_bo_start_event_t;
  96
  97 typedef struct _cairo_bo_queue_event {
  98     cairo_bo_event_type_t type;
  99     cairo_point_t point;
 100     cairo_bo_edge_t *e1;
 101     cairo_bo_edge_t *e2;
 102 } cairo_bo_queue_event_t;
 103
 104 typedef struct _pqueue {
 105     int size, max_size;
 106
 107     cairo_bo_event_t **elements;
 108     cairo_bo_event_t *elements_embedded[1024];
 109 } pqueue_t;
 110
 111 typedef struct _cairo_bo_event_queue {
 112     cairo_freepool_t pool;
 113     pqueue_t pqueue;
 114     cairo_bo_event_t **start_events;
 115 } cairo_bo_event_queue_t;
 116
 117 typedef struct _cairo_bo_sweep_line {
 118     cairo_bo_edge_t *head;
 119     int32_t current_y;
 120     cairo_bo_edge_t *current_edge;
 121 } cairo_bo_sweep_line_t;
 122
 123 static cairo_fixed_t
 124 _line_compute_intersection_x_for_y (const cairo_line_t *line,
 125                                     cairo_fixed_t y)
 126 {
 127     cairo_fixed_t x, dy;
 128
 129     if (y == line->p1.y)
 130         return line->p1.x;
 131     if (y == line->p2.y)
 132         return line->p2.x;
 133
 134     x = line->p1.x;
 135     dy = line->p2.y - line->p1.y;
 136     if (dy != 0) {
 137         x += _cairo_fixed_mul_div_floor (y - line->p1.y,
 138                                          line->p2.x - line->p1.x,
 139                                          dy);
 140     }
 141
 142     return x;
 143 }
 144
 145 static inline int
 146 _cairo_bo_point32_compare (cairo_bo_point32_t const *a,
 147                            cairo_bo_point32_t const *b)
 148 {
 149     int cmp;
 150
 151     cmp = a->y - b->y;
 152     if (cmp)
 153         return cmp;
 154
 155     return a->x - b->x;
 156 }
 157
 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
 160  * slope of b.
 161  *
 162  * For each edge, consider the direction vector formed from:
 163  *
 164  *      top -> bottom
 165  *
 166  * which is:
 167  *
 168  *      (dx, dy) = (line.p2.x - line.p1.x, line.p2.y - line.p1.y)
 169  *
 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).
 175  *
 176  * 1.      slope(a) ? slope(b)
 177  * 2.       adx/ady ? bdx/bdy
 178  * 3.   (adx * bdy) ? (bdx * ady)
 179  *
 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.
 183  *
 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.
 191  */
 192 static inline int
 193 _slope_compare (const cairo_bo_edge_t *a,
 194                 const cairo_bo_edge_t *b)
 195 {
 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
 199      * begins.
 200      */
 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;
 203
 204     /* Since the dy's are all positive by construction we can fast
 205      * path several common cases.
 206      */
 207
 208     /* First check for vertical lines. */
 209     if (adx == 0)
 210         return -bdx;
 211     if (bdx == 0)
 212         return adx;
 213
 214     /* Then where the two edges point in different directions wrt x. */
 215     if ((adx ^ bdx) < 0)
 216         return adx;
 217
 218     /* Finally we actually need to do the general comparison. */
 219     {
 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);
 224
 225         return _cairo_int64_cmp (adx_bdy, bdx_ady);
 226     }
 227 }
 228
 229 /*
 230  * We need to compare the x-coordinates of a pair of lines for a particular y,
 231  * without loss of precision.
 232  *
 233  * The x-coordinate along an edge for a given y is:
 234  *   X = A_x + (Y - A_y) * A_dx / A_dy
 235  *
 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.
 239  *
 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
 244  *
 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
 248  * deltas.
 249  *
 250  * (And put the burden of the work on developing fast 128 bit ops, which are
 251  * required throughout the tessellator.)
 252  *
 253  * See the similar discussion for _slope_compare().
 254  */
 255 static int
 256 edges_compare_x_for_y_general (const cairo_bo_edge_t *a,
 257                                const cairo_bo_edge_t *b,
 258                                int32_t y)
 259 {
 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
 263      * begins.
 264      */
 265     int32_t dx;
 266     int32_t adx, ady;
 267     int32_t bdx, bdy;
 268     enum {
 269        HAVE_NONE    = 0x0,
 270        HAVE_DX      = 0x1,
 271        HAVE_ADX     = 0x2,
 272        HAVE_DX_ADX  = HAVE_DX | HAVE_ADX,
 273        HAVE_BDX     = 0x4,
 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;
 278
 279     /* don't bother solving for abscissa if the edges' bounding boxes
 280      * can be used to order them. */
 281     {
 282            int32_t amin, amax;
 283            int32_t bmin, bmax;
 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;
 287            } else {
 288                    amin = a->edge.line.p2.x;
 289                    amax = a->edge.line.p1.x;
 290            }
 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;
 294            } else {
 295                    bmin = b->edge.line.p2.x;
 296                    bmax = b->edge.line.p1.x;
 297            }
 298            if (amax < bmin) return -1;
 299            if (amin > bmax) return +1;
 300     }
 301
 302     ady = a->edge.line.p2.y - a->edge.line.p1.y;
 303     adx = a->edge.line.p2.x - a->edge.line.p1.x;
 304     if (adx == 0)
 305         have_dx_adx_bdx &= ~HAVE_ADX;
 306
 307     bdy = b->edge.line.p2.y - b->edge.line.p1.y;
 308     bdx = b->edge.line.p2.x - b->edge.line.p1.x;
 309     if (bdx == 0)
 310         have_dx_adx_bdx &= ~HAVE_BDX;
 311
 312     dx = a->edge.line.p1.x - b->edge.line.p1.x;
 313     if (dx == 0)
 314         have_dx_adx_bdx &= ~HAVE_DX;
 315
 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) {
 320     default:
 321     case HAVE_NONE:
 322         return 0;
 323     case HAVE_DX:
 324         /* A_dy * B_dy * (A_x - B_x) ∘ 0 */
 325         return dx; /* ady * bdy is positive definite */
 326     case HAVE_ADX:
 327         /* 0 ∘  - (Y - A_y) * A_dx * B_dy */
 328         return adx; /* bdy * (y - a->top.y) is positive definite */
 329     case HAVE_BDX:
 330         /* 0 ∘ (Y - B_y) * B_dx * A_dy */
 331         return -bdx; /* ady * (y - b->top.y) is positive definite */
 332     case HAVE_ADX_BDX:
 333         /*  0 ∘ (Y - B_y) * B_dx * A_dy - (Y - A_y) * A_dx * B_dy */
 334         if ((adx ^ bdx) < 0) {
 335             return adx;
 336         } else if (a->edge.line.p1.y == b->edge.line.p1.y) { /* common origin */
 337             cairo_int64_t adx_bdy, bdx_ady;
 338
 339             /* ∴ A_dx * B_dy ∘ B_dx * A_dy */
 340
 341             adx_bdy = _cairo_int32x32_64_mul (adx, bdy);
 342             bdx_ady = _cairo_int32x32_64_mul (bdx, ady);
 343
 344             return _cairo_int64_cmp (adx_bdy, bdx_ady);
 345         } else
 346             return _cairo_int128_cmp (A, B);
 347     case HAVE_DX_ADX:
 348         /* A_dy * (A_x - B_x) ∘ - (Y - A_y) * A_dx */
 349         if ((-adx ^ dx) < 0) {
 350             return dx;
 351         } else {
 352             cairo_int64_t ady_dx, dy_adx;
 353
 354             ady_dx = _cairo_int32x32_64_mul (ady, dx);
 355             dy_adx = _cairo_int32x32_64_mul (a->edge.line.p1.y - y, adx);
 356
 357             return _cairo_int64_cmp (ady_dx, dy_adx);
 358         }
 359     case HAVE_DX_BDX:
 360         /* B_dy * (A_x - B_x) ∘ (Y - B_y) * B_dx */
 361         if ((bdx ^ dx) < 0) {
 362             return dx;
 363         } else {
 364             cairo_int64_t bdy_dx, dy_bdx;
 365
 366             bdy_dx = _cairo_int32x32_64_mul (bdy, dx);
 367             dy_bdx = _cairo_int32x32_64_mul (y - b->edge.line.p1.y, bdx);
 368
 369             return _cairo_int64_cmp (bdy_dx, dy_bdx);
 370         }
 371     case HAVE_ALL:
 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));
 374     }
 375 #undef B
 376 #undef A
 377 #undef L
 378 }
 379
 380 /*
 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.
 383  *
 384  * The x-coordinate along an edge for a given y is:
 385  *   X = A_x + (Y - A_y) * A_dx / A_dy
 386  *
 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.
 390  *
 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
 394  *
 395  * Given the assumption that all the deltas fit within 32 bits, we can compute
 396  * this comparison directly using 64 bit arithmetic.
 397  *
 398  * See the similar discussion for _slope_compare() and
 399  * edges_compare_x_for_y_general().
 400  */
 401 static int
 402 edge_compare_for_y_against_x (const cairo_bo_edge_t *a,
 403                               int32_t y,
 404                               int32_t x)
 405 {
 406     int32_t adx, ady;
 407     int32_t dx, dy;
 408     cairo_int64_t L, R;
 409
 410     if (x < a->edge.line.p1.x && x < a->edge.line.p2.x)
 411         return 1;
 412     if (x > a->edge.line.p1.x && x > a->edge.line.p2.x)
 413         return -1;
 414
 415     adx = a->edge.line.p2.x - a->edge.line.p1.x;
 416     dx = x - a->edge.line.p1.x;
 417
 418     if (adx == 0)
 419         return -dx;
 420     if (dx == 0 || (adx ^ dx) < 0)
 421         return adx;
 422
 423     dy = y - a->edge.line.p1.y;
 424     ady = a->edge.line.p2.y - a->edge.line.p1.y;
 425
 426     L = _cairo_int32x32_64_mul (dy, adx);
 427     R = _cairo_int32x32_64_mul (dx, ady);
 428
 429     return _cairo_int64_cmp (L, R);
 430 }
 431
 432 static int
 433 edges_compare_x_for_y (const cairo_bo_edge_t *a,
 434                        const cairo_bo_edge_t *b,
 435                        int32_t y)
 436 {
 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
 440      * special casing).
 441      */
 442     enum {
 443        HAVE_NEITHER = 0x0,
 444        HAVE_AX      = 0x1,
 445        HAVE_BX      = 0x2,
 446        HAVE_BOTH    = HAVE_AX | HAVE_BX
 447     } have_ax_bx = HAVE_BOTH;
 448     int32_t ax, bx;
 449
 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;
 454     else
 455         have_ax_bx &= ~HAVE_AX;
 456
 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;
 461     else
 462         have_ax_bx &= ~HAVE_BX;
 463
 464     switch (have_ax_bx) {
 465     default:
 466     case HAVE_NEITHER:
 467         return edges_compare_x_for_y_general (a, b, y);
 468     case HAVE_AX:
 469         return -edge_compare_for_y_against_x (b, y, ax);
 470     case HAVE_BX:
 471         return edge_compare_for_y_against_x (a, y, bx);
 472     case HAVE_BOTH:
 473         return ax - bx;
 474     }
 475 }
 476
 477 static inline int
 478 _line_equal (const cairo_line_t *a, const cairo_line_t *b)
 479 {
 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);
 482 }
 483
 484 static int
 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)
 488 {
 489     int cmp;
 490
 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);
 494         if (cmp)
 495             return cmp;
 496
 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);
 503         if (cmp)
 504             return cmp;
 505     }
 506
 507     /* We've got two collinear edges now. */
 508     return b->edge.bottom - a->edge.bottom;
 509 }
 510
 511 static inline cairo_int64_t
 512 det32_64 (int32_t a, int32_t b,
 513           int32_t c, int32_t d)
 514 {
 515     /* det = a * d - b * c */
 516     return _cairo_int64_sub (_cairo_int32x32_64_mul (a, d),
 517                              _cairo_int32x32_64_mul (b, c));
 518 }
 519
 520 static inline cairo_int128_t
 521 det64x32_128 (cairo_int64_t a, int32_t       b,
 522               cairo_int64_t c, int32_t       d)
 523 {
 524     /* det = a * d - b * c */
 525     return _cairo_int128_sub (_cairo_int64x32_128_mul (a, d),
 526                               _cairo_int64x32_128_mul (c, b));
 527 }
 528
 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.
 531  *
 532  * Returns %CAIRO_BO_STATUS_INTERSECTION if there is an intersection or
 533  * %CAIRO_BO_STATUS_PARALLEL if the two lines are exactly parallel.
 534  */
 535 static cairo_bool_t
 536 intersect_lines (cairo_bo_edge_t                *a,
 537                  cairo_bo_edge_t                *b,
 538                  cairo_bo_intersect_point_t     *intersection)
 539 {
 540     cairo_int64_t a_det, b_det;
 541
 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().
 547      */
 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;
 550
 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;
 553
 554     cairo_int64_t den_det;
 555     cairo_int64_t R;
 556     cairo_quorem64_t qr;
 557
 558     den_det = det32_64 (dx1, dy1, dx2, dy2);
 559
 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?
 563       *
 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)
 567       *   => t * L = R
 568       *
 569       * Therefore we can reject any intersection (under the criteria for
 570       * valid intersection events) if:
 571       *   L^R < 0 => t < 0, or
 572       *   L<R => t > 1
 573       *
 574       * (where top/bottom must at least extend to the line endpoints).
 575       *
 576       * A similar substitution can be performed for s, yielding:
 577       *   s * (ady*bdx - bdy*adx) = ady * (ax - bx) - adx * (ay - by)
 578       */
 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))
 584             return FALSE;
 585     } else {
 586         if (_cairo_int64_le (den_det, R))
 587             return FALSE;
 588     }
 589
 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))
 595             return FALSE;
 596     } else {
 597         if (_cairo_int64_le (den_det, R))
 598             return FALSE;
 599     }
 600
 601     /* We now know that the two lines should intersect within range. */
 602
 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);
 607
 608     /* x = det (a_det, dx1, b_det, dx2) / den_det */
 609     qr = _cairo_int_96by64_32x64_divrem (det64x32_128 (a_det, dx1,
 610                                                        b_det, dx2),
 611                                          den_det);
 612     if (_cairo_int64_eq (qr.rem, den_det))
 613         return FALSE;
 614 #if 0
 615     intersection->x.exactness = _cairo_int64_is_zero (qr.rem) ? EXACT : INEXACT;
 616 #else
 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));
 625         } else
 626             intersection->x.exactness = INEXACT;
 627     }
 628 #endif
 629     intersection->x.ordinate = _cairo_int64_to_int32 (qr.quo);
 630
 631     /* y = det (a_det, dy1, b_det, dy2) / den_det */
 632     qr = _cairo_int_96by64_32x64_divrem (det64x32_128 (a_det, dy1,
 633                                                        b_det, dy2),
 634                                          den_det);
 635     if (_cairo_int64_eq (qr.rem, den_det))
 636         return FALSE;
 637 #if 0
 638     intersection->y.exactness = _cairo_int64_is_zero (qr.rem) ? EXACT : INEXACT;
 639 #else
 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));
 648         } else
 649             intersection->y.exactness = INEXACT;
 650     }
 651 #endif
 652     intersection->y.ordinate = _cairo_int64_to_int32 (qr.quo);
 653
 654     return TRUE;
 655 }
 656
 657 static int
 658 _cairo_bo_intersect_ordinate_32_compare (cairo_bo_intersect_ordinate_t  a,
 659                                          int32_t                        b)
 660 {
 661     /* First compare the quotient */
 662     if (a.ordinate > b)
 663         return +1;
 664     if (a.ordinate < b)
 665         return -1;
 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;
 669 }
 670
 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
 674  * with another).
 675  *
 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
 681  * point.
 682  *
 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.
 687  */
 688 static cairo_bool_t
 689 _cairo_bo_edge_contains_intersect_point (cairo_bo_edge_t                *edge,
 690                                          cairo_bo_intersect_point_t     *point)
 691 {
 692     int cmp_top, cmp_bottom;
 693
 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.
 699      */
 700
 701     cmp_top = _cairo_bo_intersect_ordinate_32_compare (point->y,
 702                                                        edge->edge.top);
 703     cmp_bottom = _cairo_bo_intersect_ordinate_32_compare (point->y,
 704                                                           edge->edge.bottom);
 705
 706     if (cmp_top < 0 || cmp_bottom > 0)
 707     {
 708         return FALSE;
 709     }
 710
 711     if (cmp_top > 0 && cmp_bottom < 0)
 712     {
 713         return TRUE;
 714     }
 715
 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. */
 719
 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. */
 726
 727     if (cmp_top == 0) {
 728         cairo_fixed_t top_x;
 729
 730         top_x = _line_compute_intersection_x_for_y (&edge->edge.line,
 731                                                     edge->edge.top);
 732         return _cairo_bo_intersect_ordinate_32_compare (point->x, top_x) > 0;
 733     } else { /* cmp_bottom == 0 */
 734         cairo_fixed_t bot_x;
 735
 736         bot_x = _line_compute_intersection_x_for_y (&edge->edge.line,
 737                                                     edge->edge.bottom);
 738         return _cairo_bo_intersect_ordinate_32_compare (point->x, bot_x) < 0;
 739     }
 740 }
 741
 742 /* Compute the intersection of two edges. The result is provided as a
 743  * coordinate pair of 128-bit integers.
 744  *
 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.
 750  *
 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
 757  */
 758 static cairo_bool_t
 759 _cairo_bo_edge_intersect (cairo_bo_edge_t       *a,
 760                           cairo_bo_edge_t       *b,
 761                           cairo_bo_point32_t    *intersection)
 762 {
 763     cairo_bo_intersect_point_t quorem;
 764
 765     if (! intersect_lines (a, b, &quorem))
 766         return FALSE;
 767
 768     if (! _cairo_bo_edge_contains_intersect_point (a, &quorem))
 769         return FALSE;
 770
 771     if (! _cairo_bo_edge_contains_intersect_point (b, &quorem))
 772         return FALSE;
 773
 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;
 781
 782     return TRUE;
 783 }
 784
 785 static inline int
 786 cairo_bo_event_compare (const cairo_bo_event_t *a,
 787                         const cairo_bo_event_t *b)
 788 {
 789     int cmp;
 790
 791     cmp = _cairo_bo_point32_compare (&a->point, &b->point);
 792     if (cmp)
 793         return cmp;
 794
 795     cmp = a->type - b->type;
 796     if (cmp)
 797         return cmp;
 798
 799     return a - b;
 800 }
 801
 802 static inline void
 803 _pqueue_init (pqueue_t *pq)
 804 {
 805     pq->max_size = ARRAY_LENGTH (pq->elements_embedded);
 806     pq->size = 0;
 807
 808     pq->elements = pq->elements_embedded;
 809 }
 810
 811 static inline void
 812 _pqueue_fini (pqueue_t *pq)
 813 {
 814     if (pq->elements != pq->elements_embedded)
 815         free (pq->elements);
 816 }
 817
 818 static cairo_status_t
 819 _pqueue_grow (pqueue_t *pq)
 820 {
 821     cairo_bo_event_t **new_elements;
 822     pq->max_size *= 2;
 823
 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);
 829
 830         memcpy (new_elements, pq->elements_embedded,
 831                 sizeof (pq->elements_embedded));
 832     } else {
 833         new_elements = _cairo_realloc_ab (pq->elements,
 834                                           pq->max_size,
 835                                           sizeof (cairo_bo_event_t *));
 836         if (unlikely (new_elements == NULL))
 837             return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 838     }
 839
 840     pq->elements = new_elements;
 841     return CAIRO_STATUS_SUCCESS;
 842 }
 843
 844 static inline cairo_status_t
 845 _pqueue_push (pqueue_t *pq, cairo_bo_event_t *event)
 846 {
 847     cairo_bo_event_t **elements;
 848     int i, parent;
 849
 850     if (unlikely (pq->size + 1 == pq->max_size)) {
 851         cairo_status_t status;
 852
 853         status = _pqueue_grow (pq);
 854         if (unlikely (status))
 855             return status;
 856     }
 857
 858     elements = pq->elements;
 859
 860     for (i = ++pq->size;
 861          i != PQ_FIRST_ENTRY &&
 862          cairo_bo_event_compare (event,
 863                                  elements[parent = PQ_PARENT_INDEX (i)]) < 0;
 864          i = parent)
 865     {
 866         elements[i] = elements[parent];
 867     }
 868
 869     elements[i] = event;
 870
 871     return CAIRO_STATUS_SUCCESS;
 872 }
 873
 874 static inline void
 875 _pqueue_pop (pqueue_t *pq)
 876 {
 877     cairo_bo_event_t **elements = pq->elements;
 878     cairo_bo_event_t *tail;
 879     int child, i;
 880
 881     tail = elements[pq->size--];
 882     if (pq->size == 0) {
 883         elements[PQ_FIRST_ENTRY] = NULL;
 884         return;
 885     }
 886
 887     for (i = PQ_FIRST_ENTRY;
 888          (child = PQ_LEFT_CHILD_INDEX (i)) <= pq->size;
 889          i = child)
 890     {
 891         if (child != pq->size &&
 892             cairo_bo_event_compare (elements[child+1],
 893                                     elements[child]) < 0)
 894         {
 895             child++;
 896         }
 897
 898         if (cairo_bo_event_compare (elements[child], tail) >= 0)
 899             break;
 900
 901         elements[i] = elements[child];
 902     }
 903     elements[i] = tail;
 904 }
 905
 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,
 909                               cairo_bo_edge_t           *e1,
 910                               cairo_bo_edge_t           *e2,
 911                               const cairo_point_t        *point)
 912 {
 913     cairo_bo_queue_event_t *event;
 914
 915     event = _cairo_freepool_alloc (&queue->pool);
 916     if (unlikely (event == NULL))
 917         return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 918
 919     event->type = type;
 920     event->e1 = e1;
 921     event->e2 = e2;
 922     event->point = *point;
 923
 924     return _pqueue_push (&queue->pqueue, (cairo_bo_event_t *) event);
 925 }
 926
 927 static void
 928 _cairo_bo_event_queue_delete (cairo_bo_event_queue_t *queue,
 929                               cairo_bo_event_t       *event)
 930 {
 931     _cairo_freepool_free (&queue->pool, event);
 932 }
 933
 934 static cairo_bo_event_t *
 935 _cairo_bo_event_dequeue (cairo_bo_event_queue_t *event_queue)
 936 {
 937     cairo_bo_event_t *event, *cmp;
 938
 939     event = event_queue->pqueue.elements[PQ_FIRST_ENTRY];
 940     cmp = *event_queue->start_events;
 941     if (event == NULL ||
 942         (cmp != NULL && cairo_bo_event_compare (cmp, event) < 0))
 943     {
 944         event = cmp;
 945         event_queue->start_events++;
 946     }
 947     else
 948     {
 949         _pqueue_pop (&event_queue->pqueue);
 950     }
 951
 952     return event;
 953 }
 954
 955 CAIRO_COMBSORT_DECLARE (_cairo_bo_event_queue_sort,
 956                         cairo_bo_event_t *,
 957                         cairo_bo_event_compare)
 958
 959 static void
 960 _cairo_bo_event_queue_init (cairo_bo_event_queue_t       *event_queue,
 961                             cairo_bo_event_t            **start_events,
 962                             int                           num_events)
 963 {
 964     _cairo_bo_event_queue_sort (start_events, num_events);
 965     start_events[num_events] = NULL;
 966
 967     event_queue->start_events = start_events;
 968
 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;
 973 }
 974
 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)
 978 {
 979     cairo_bo_point32_t point;
 980
 981     point.y = edge->edge.bottom;
 982     point.x = _line_compute_intersection_x_for_y (&edge->edge.line,
 983                                                   point.y);
 984     return _cairo_bo_event_queue_insert (event_queue,
 985                                          CAIRO_BO_EVENT_TYPE_STOP,
 986                                          edge, NULL,
 987                                          &point);
 988 }
 989
 990 static void
 991 _cairo_bo_event_queue_fini (cairo_bo_event_queue_t *event_queue)
 992 {
 993     _pqueue_fini (&event_queue->pqueue);
 994     _cairo_freepool_fini (&event_queue->pool);
 995 }
 996
 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)
1001 {
1002     cairo_bo_point32_t intersection;
1003
1004     if (_line_equal (&left->edge.line, &right->edge.line))
1005         return CAIRO_STATUS_SUCCESS;
1006
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;
1014
1015     if (! _cairo_bo_edge_intersect (left, right, &intersection))
1016         return CAIRO_STATUS_SUCCESS;
1017
1018     return _cairo_bo_event_queue_insert (event_queue,
1019                                          CAIRO_BO_EVENT_TYPE_INTERSECTION,
1020                                          left, right,
1021                                          &intersection);
1022 }
1023
1024 static void
1025 _cairo_bo_sweep_line_init (cairo_bo_sweep_line_t *sweep_line)
1026 {
1027     sweep_line->head = NULL;
1028     sweep_line->current_y = INT32_MIN;
1029     sweep_line->current_edge = NULL;
1030 }
1031
1032 static cairo_status_t
1033 _cairo_bo_sweep_line_insert (cairo_bo_sweep_line_t      *sweep_line,
1034                              cairo_bo_edge_t            *edge)
1035 {
1036     if (sweep_line->current_edge != NULL) {
1037         cairo_bo_edge_t *prev, *next;
1038         int cmp;
1039
1040         cmp = _cairo_bo_sweep_line_compare_edges (sweep_line,
1041                                                   sweep_line->current_edge,
1042                                                   edge);
1043         if (cmp < 0) {
1044             prev = sweep_line->current_edge;
1045             next = prev->next;
1046             while (next != NULL &&
1047                    _cairo_bo_sweep_line_compare_edges (sweep_line,
1048                                                        next, edge) < 0)
1049             {
1050                 prev = next, next = prev->next;
1051             }
1052
1053             prev->next = edge;
1054             edge->prev = prev;
1055             edge->next = next;
1056             if (next != NULL)
1057                 next->prev = edge;
1058         } else if (cmp > 0) {
1059             next = sweep_line->current_edge;
1060             prev = next->prev;
1061             while (prev != NULL &&
1062                    _cairo_bo_sweep_line_compare_edges (sweep_line,
1063                                                        prev, edge) > 0)
1064             {
1065                 next = prev, prev = next->prev;
1066             }
1067
1068             next->prev = edge;
1069             edge->next = next;
1070             edge->prev = prev;
1071             if (prev != NULL)
1072                 prev->next = edge;
1073             else
1074                 sweep_line->head = edge;
1075         } else {
1076             prev = sweep_line->current_edge;
1077             edge->prev = prev;
1078             edge->next = prev->next;
1079             if (prev->next != NULL)
1080                 prev->next->prev = edge;
1081             prev->next = edge;
1082         }
1083     } else {
1084         sweep_line->head = edge;
1085     }
1086
1087     sweep_line->current_edge = edge;
1088
1089     return CAIRO_STATUS_SUCCESS;
1090 }
1091
1092 static void
1093 _cairo_bo_sweep_line_delete (cairo_bo_sweep_line_t      *sweep_line,
1094                              cairo_bo_edge_t    *edge)
1095 {
1096     if (edge->prev != NULL)
1097         edge->prev->next = edge->next;
1098     else
1099         sweep_line->head = edge->next;
1100
1101     if (edge->next != NULL)
1102         edge->next->prev = edge->prev;
1103
1104     if (sweep_line->current_edge == edge)
1105         sweep_line->current_edge = edge->prev ? edge->prev : edge->next;
1106 }
1107
1108 static void
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)
1112 {
1113     if (left->prev != NULL)
1114         left->prev->next = right;
1115     else
1116         sweep_line->head = right;
1117
1118     if (right->next != NULL)
1119         right->next->prev = left;
1120
1121     left->next = right->next;
1122     right->next = left;
1123
1124     right->prev = left->prev;
1125     left->prev = right;
1126 }
1127
1128 static inline cairo_bool_t
1129 edges_colinear (const cairo_bo_edge_t *a, const cairo_bo_edge_t *b)
1130 {
1131     if (_line_equal (&a->edge.line, &b->edge.line))
1132         return TRUE;
1133
1134     if (_slope_compare (a, b))
1135         return FALSE;
1136
1137     /* The choice of y is not truly arbitrary since we must guarantee that it
1138      * is greater than the start of either line.
1139      */
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,
1146                                              a->edge.line.p1.y,
1147                                              a->edge.line.p1.x) == 0;
1148     } else {
1149         return edge_compare_for_y_against_x (a,
1150                                              b->edge.line.p1.y,
1151                                              b->edge.line.p1.x) == 0;
1152     }
1153 }
1154
1155 static void
1156 _cairo_bo_edge_end (cairo_bo_edge_t     *left,
1157                     int32_t              bot,
1158                     cairo_polygon_t     *polygon)
1159 {
1160     cairo_bo_deferred_t *d = &left->deferred;
1161
1162     if (likely (d->top < bot)) {
1163         _cairo_polygon_add_line (polygon,
1164                                  &left->edge.line,
1165                                  d->top, bot,
1166                                  1);
1167         _cairo_polygon_add_line (polygon,
1168                                  &d->right->edge.line,
1169                                  d->top, bot,
1170                                  -1);
1171     }
1172
1173     d->right = NULL;
1174 }
1175
1176
1177 static inline void
1178 _cairo_bo_edge_start_or_continue (cairo_bo_edge_t       *left,
1179                                   cairo_bo_edge_t       *right,
1180                                   int                    top,
1181                                   cairo_polygon_t       *polygon)
1182 {
1183     if (left->deferred.right == right)
1184         return;
1185
1186     if (left->deferred.right != NULL) {
1187         if (right != NULL && edges_colinear (left->deferred.right, right))
1188         {
1189             /* continuation on right, so just swap edges */
1190             left->deferred.right = right;
1191             return;
1192         }
1193
1194         _cairo_bo_edge_end (left, top, polygon);
1195     }
1196
1197     if (right != NULL && ! edges_colinear (left, right)) {
1198         left->deferred.top = top;
1199         left->deferred.right = right;
1200     }
1201 }
1202
1203 static inline void
1204 _active_edges_to_polygon (cairo_bo_edge_t               *left,
1205                           int32_t                        top,
1206                           cairo_fill_rule_t              fill_rule,
1207                           cairo_polygon_t               *polygon)
1208 {
1209     cairo_bo_edge_t *right;
1210     unsigned int mask;
1211
1212     if (fill_rule == CAIRO_FILL_RULE_WINDING)
1213         mask = ~0;
1214     else
1215         mask = 1;
1216
1217     while (left != NULL) {
1218         int in_out = left->edge.dir;
1219
1220         right = left->next;
1221         if (left->deferred.right == NULL) {
1222             while (right != NULL && right->deferred.right == NULL)
1223                 right = right->next;
1224
1225             if (right != NULL && edges_colinear (left, right)) {
1226                 /* continuation on left */
1227                 left->deferred = right->deferred;
1228                 right->deferred.right = NULL;
1229             }
1230         }
1231
1232         right = left->next;
1233         while (right != NULL) {
1234             if (right->deferred.right != NULL)
1235                 _cairo_bo_edge_end (right, top, polygon);
1236
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))
1241                     break;
1242             }
1243
1244             right = right->next;
1245         }
1246
1247         _cairo_bo_edge_start_or_continue (left, right, top, polygon);
1248
1249         left = right;
1250         if (left != NULL)
1251             left = left->next;
1252     }
1253 }
1254
1255
1256 static cairo_status_t
1257 _cairo_bentley_ottmann_tessellate_bo_edges (cairo_bo_event_t   **start_events,
1258                                             int                  num_events,
1259                                             cairo_fill_rule_t    fill_rule,
1260                                             cairo_polygon_t     *polygon)
1261 {
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;
1268
1269     _cairo_bo_event_queue_init (&event_queue, start_events, num_events);
1270     _cairo_bo_sweep_line_init (&sweep_line);
1271
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);
1277
1278             sweep_line.current_y = event->point.y;
1279         }
1280
1281         switch (event->type) {
1282         case CAIRO_BO_EVENT_TYPE_START:
1283             e1 = &((cairo_bo_start_event_t *) event)->edge;
1284
1285             status = _cairo_bo_sweep_line_insert (&sweep_line, e1);
1286             if (unlikely (status))
1287                 goto unwind;
1288
1289             status = _cairo_bo_event_queue_insert_stop (&event_queue, e1);
1290             if (unlikely (status))
1291                 goto unwind;
1292
1293             left = e1->prev;
1294             right = e1->next;
1295
1296             if (left != NULL) {
1297                 status = _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, left, e1);
1298                 if (unlikely (status))
1299                     goto unwind;
1300             }
1301
1302             if (right != NULL) {
1303                 status = _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, e1, right);
1304                 if (unlikely (status))
1305                     goto unwind;
1306             }
1307
1308             break;
1309
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);
1313
1314             left = e1->prev;
1315             right = e1->next;
1316
1317             _cairo_bo_sweep_line_delete (&sweep_line, e1);
1318
1319             if (e1->deferred.right != NULL)
1320                 _cairo_bo_edge_end (e1, e1->edge.bottom, polygon);
1321
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))
1325                     goto unwind;
1326             }
1327
1328             break;
1329
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);
1334
1335             /* skip this intersection if its edges are not adjacent */
1336             if (e2 != e1->next)
1337                 break;
1338
1339             left = e1->prev;
1340             right = e2->next;
1341
1342             _cairo_bo_sweep_line_swap (&sweep_line, e1, e2);
1343
1344             /* after the swap e2 is left of e1 */
1345
1346             if (left != NULL) {
1347                 status = _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, left, e2);
1348                 if (unlikely (status))
1349                     goto unwind;
1350             }
1351
1352             if (right != NULL) {
1353                 status = _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, e1, right);
1354                 if (unlikely (status))
1355                     goto unwind;
1356             }
1357
1358             break;
1359         }
1360     }
1361
1362  unwind:
1363     _cairo_bo_event_queue_fini (&event_queue);
1364
1365     return status;
1366 }
1367
1368 cairo_status_t
1369 _cairo_polygon_reduce (cairo_polygon_t *polygon,
1370                        cairo_fill_rule_t fill_rule)
1371 {
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;
1377     int num_limits;
1378     int num_events;
1379     int i;
1380
1381     num_events = polygon->num_edges;
1382     if (unlikely (0 == num_events))
1383         return CAIRO_STATUS_SUCCESS;
1384
1385     if (DEBUG_POLYGON) {
1386         FILE *file = fopen ("reduce_in.txt", "w");
1387         _cairo_debug_print_polygon (file, polygon);
1388         fclose (file);
1389     }
1390
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);
1400
1401         event_ptrs = (cairo_bo_event_t **) (events + num_events);
1402     }
1403
1404     for (i = 0; i < num_events; i++) {
1405         event_ptrs[i] = (cairo_bo_event_t *) &events[i];
1406
1407         events[i].type = CAIRO_BO_EVENT_TYPE_START;
1408         events[i].point.y = polygon->edges[i].top;
1409         events[i].point.x =
1410             _line_compute_intersection_x_for_y (&polygon->edges[i].line,
1411                                                 events[i].point.y);
1412
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;
1417     }
1418
1419     num_limits = polygon->num_limits; polygon->num_limits = 0;
1420     polygon->num_edges = 0;
1421
1422     status = _cairo_bentley_ottmann_tessellate_bo_edges (event_ptrs,
1423                                                          num_events,
1424                                                          fill_rule,
1425                                                          polygon);
1426     polygon->num_limits = num_limits;
1427
1428     if (events != stack_events)
1429         free (events);
1430
1431     if (DEBUG_POLYGON) {
1432         FILE *file = fopen ("reduce_out.txt", "w");
1433         _cairo_debug_print_polygon (file, polygon);
1434         fclose (file);
1435     }
1436
1437     return status;
1438 }