src/cairo-bentley-ottmann.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-combsort-inline.h"
  42 #include "cairo-error-private.h"
  43 #include "cairo-freelist-private.h"
  44 #include "cairo-line-inline.h"
  45 #include "cairo-traps-private.h"
  46
  47 #define DEBUG_PRINT_STATE 0
  48 #define DEBUG_EVENTS 0
  49 #define DEBUG_TRAPS 0
  50
  51 typedef cairo_point_t cairo_bo_point32_t;
  52
  53 typedef struct _cairo_bo_intersect_ordinate {
  54     int32_t ordinate;
  55     enum { EXACT, INEXACT } exactness;
  56 } cairo_bo_intersect_ordinate_t;
  57
  58 typedef struct _cairo_bo_intersect_point {
  59     cairo_bo_intersect_ordinate_t x;
  60     cairo_bo_intersect_ordinate_t y;
  61 } cairo_bo_intersect_point_t;
  62
  63 typedef struct _cairo_bo_edge cairo_bo_edge_t;
  64 typedef struct _cairo_bo_trap cairo_bo_trap_t;
  65
  66 /* A deferred trapezoid of an edge */
  67 struct _cairo_bo_trap {
  68     cairo_bo_edge_t *right;
  69     int32_t top;
  70 };
  71
  72 struct _cairo_bo_edge {
  73     cairo_edge_t edge;
  74     cairo_bo_edge_t *prev;
  75     cairo_bo_edge_t *next;
  76     cairo_bo_edge_t *colinear;
  77     cairo_bo_trap_t deferred_trap;
  78 };
  79
  80 /* the parent is always given by index/2 */
  81 #define PQ_PARENT_INDEX(i) ((i) >> 1)
  82 #define PQ_FIRST_ENTRY 1
  83
  84 /* left and right children are index * 2 and (index * 2) +1 respectively */
  85 #define PQ_LEFT_CHILD_INDEX(i) ((i) << 1)
  86
  87 typedef enum {
  88     CAIRO_BO_EVENT_TYPE_STOP,
  89     CAIRO_BO_EVENT_TYPE_INTERSECTION,
  90     CAIRO_BO_EVENT_TYPE_START
  91 } cairo_bo_event_type_t;
  92
  93 typedef struct _cairo_bo_event {
  94     cairo_bo_event_type_t type;
  95     cairo_point_t point;
  96 } cairo_bo_event_t;
  97
  98 typedef struct _cairo_bo_start_event {
  99     cairo_bo_event_type_t type;
 100     cairo_point_t point;
 101     cairo_bo_edge_t edge;
 102 } cairo_bo_start_event_t;
 103
 104 typedef struct _cairo_bo_queue_event {
 105     cairo_bo_event_type_t type;
 106     cairo_point_t point;
 107     cairo_bo_edge_t *e1;
 108     cairo_bo_edge_t *e2;
 109 } cairo_bo_queue_event_t;
 110
 111 typedef struct _pqueue {
 112     int size, max_size;
 113
 114     cairo_bo_event_t **elements;
 115     cairo_bo_event_t *elements_embedded[1024];
 116 } pqueue_t;
 117
 118 typedef struct _cairo_bo_event_queue {
 119     cairo_freepool_t pool;
 120     pqueue_t pqueue;
 121     cairo_bo_event_t **start_events;
 122 } cairo_bo_event_queue_t;
 123
 124 typedef struct _cairo_bo_sweep_line {
 125     cairo_bo_edge_t *head;
 126     cairo_bo_edge_t *stopped;
 127     int32_t current_y;
 128     cairo_bo_edge_t *current_edge;
 129 } cairo_bo_sweep_line_t;
 130
 131 #if DEBUG_TRAPS
 132 static void
 133 dump_traps (cairo_traps_t *traps, const char *filename)
 134 {
 135     FILE *file;
 136     cairo_box_t extents;
 137     int n;
 138
 139     if (getenv ("CAIRO_DEBUG_TRAPS") == NULL)
 140         return;
 141
 142 #if 0
 143     if (traps->has_limits) {
 144         printf ("%s: limits=(%d, %d, %d, %d)\n",
 145                 filename,
 146                 traps->limits.p1.x, traps->limits.p1.y,
 147                 traps->limits.p2.x, traps->limits.p2.y);
 148     }
 149 #endif
 150     _cairo_traps_extents (traps, &extents);
 151     printf ("%s: extents=(%d, %d, %d, %d)\n",
 152             filename,
 153             extents.p1.x, extents.p1.y,
 154             extents.p2.x, extents.p2.y);
 155
 156     file = fopen (filename, "a");
 157     if (file != NULL) {
 158         for (n = 0; n < traps->num_traps; n++) {
 159             fprintf (file, "%d %d L:(%d, %d), (%d, %d) R:(%d, %d), (%d, %d)\n",
 160                      traps->traps[n].top,
 161                      traps->traps[n].bottom,
 162                      traps->traps[n].left.p1.x,
 163                      traps->traps[n].left.p1.y,
 164                      traps->traps[n].left.p2.x,
 165                      traps->traps[n].left.p2.y,
 166                      traps->traps[n].right.p1.x,
 167                      traps->traps[n].right.p1.y,
 168                      traps->traps[n].right.p2.x,
 169                      traps->traps[n].right.p2.y);
 170         }
 171         fprintf (file, "\n");
 172         fclose (file);
 173     }
 174 }
 175
 176 static void
 177 dump_edges (cairo_bo_start_event_t *events,
 178             int num_edges,
 179             const char *filename)
 180 {
 181     FILE *file;
 182     int n;
 183
 184     if (getenv ("CAIRO_DEBUG_TRAPS") == NULL)
 185         return;
 186
 187     file = fopen (filename, "a");
 188     if (file != NULL) {
 189         for (n = 0; n < num_edges; n++) {
 190             fprintf (file, "(%d, %d), (%d, %d) %d %d %d\n",
 191                      events[n].edge.edge.line.p1.x,
 192                      events[n].edge.edge.line.p1.y,
 193                      events[n].edge.edge.line.p2.x,
 194                      events[n].edge.edge.line.p2.y,
 195                      events[n].edge.edge.top,
 196                      events[n].edge.edge.bottom,
 197                      events[n].edge.edge.dir);
 198         }
 199         fprintf (file, "\n");
 200         fclose (file);
 201     }
 202 }
 203 #endif
 204
 205 static cairo_fixed_t
 206 _line_compute_intersection_x_for_y (const cairo_line_t *line,
 207                                     cairo_fixed_t y)
 208 {
 209     cairo_fixed_t x, dy;
 210
 211     if (y == line->p1.y)
 212         return line->p1.x;
 213     if (y == line->p2.y)
 214         return line->p2.x;
 215
 216     x = line->p1.x;
 217     dy = line->p2.y - line->p1.y;
 218     if (dy != 0) {
 219         x += _cairo_fixed_mul_div_floor (y - line->p1.y,
 220                                          line->p2.x - line->p1.x,
 221                                          dy);
 222     }
 223
 224     return x;
 225 }
 226
 227 static inline int
 228 _cairo_bo_point32_compare (cairo_bo_point32_t const *a,
 229                            cairo_bo_point32_t const *b)
 230 {
 231     int cmp;
 232
 233     cmp = a->y - b->y;
 234     if (cmp)
 235         return cmp;
 236
 237     return a->x - b->x;
 238 }
 239
 240 /* Compare the slope of a to the slope of b, returning 1, 0, -1 if the
 241  * slope a is respectively greater than, equal to, or less than the
 242  * slope of b.
 243  *
 244  * For each edge, consider the direction vector formed from:
 245  *
 246  *      top -> bottom
 247  *
 248  * which is:
 249  *
 250  *      (dx, dy) = (line.p2.x - line.p1.x, line.p2.y - line.p1.y)
 251  *
 252  * We then define the slope of each edge as dx/dy, (which is the
 253  * inverse of the slope typically used in math instruction). We never
 254  * compute a slope directly as the value approaches infinity, but we
 255  * can derive a slope comparison without division as follows, (where
 256  * the ? represents our compare operator).
 257  *
 258  * 1.      slope(a) ? slope(b)
 259  * 2.       adx/ady ? bdx/bdy
 260  * 3.   (adx * bdy) ? (bdx * ady)
 261  *
 262  * Note that from step 2 to step 3 there is no change needed in the
 263  * sign of the result since both ady and bdy are guaranteed to be
 264  * greater than or equal to 0.
 265  *
 266  * When using this slope comparison to sort edges, some care is needed
 267  * when interpreting the results. Since the slope compare operates on
 268  * distance vectors from top to bottom it gives a correct left to
 269  * right sort for edges that have a common top point, (such as two
 270  * edges with start events at the same location). On the other hand,
 271  * the sense of the result will be exactly reversed for two edges that
 272  * have a common stop point.
 273  */
 274 static inline int
 275 _slope_compare (const cairo_bo_edge_t *a,
 276                 const cairo_bo_edge_t *b)
 277 {
 278     /* XXX: We're assuming here that dx and dy will still fit in 32
 279      * bits. That's not true in general as there could be overflow. We
 280      * should prevent that before the tessellation algorithm
 281      * begins.
 282      */
 283     int32_t adx = a->edge.line.p2.x - a->edge.line.p1.x;
 284     int32_t bdx = b->edge.line.p2.x - b->edge.line.p1.x;
 285
 286     /* Since the dy's are all positive by construction we can fast
 287      * path several common cases.
 288      */
 289
 290     /* First check for vertical lines. */
 291     if (adx == 0)
 292         return -bdx;
 293     if (bdx == 0)
 294         return adx;
 295
 296     /* Then where the two edges point in different directions wrt x. */
 297     if ((adx ^ bdx) < 0)
 298         return adx;
 299
 300     /* Finally we actually need to do the general comparison. */
 301     {
 302         int32_t ady = a->edge.line.p2.y - a->edge.line.p1.y;
 303         int32_t bdy = b->edge.line.p2.y - b->edge.line.p1.y;
 304         cairo_int64_t adx_bdy = _cairo_int32x32_64_mul (adx, bdy);
 305         cairo_int64_t bdx_ady = _cairo_int32x32_64_mul (bdx, ady);
 306
 307         return _cairo_int64_cmp (adx_bdy, bdx_ady);
 308     }
 309 }
 310
 311
 312 /*
 313  * We need to compare the x-coordinate of a line for a particular y wrt to a
 314  * given x, without loss of precision.
 315  *
 316  * The x-coordinate along an edge for a given y is:
 317  *   X = A_x + (Y - A_y) * A_dx / A_dy
 318  *
 319  * So the inequality we wish to test is:
 320  *   A_x + (Y - A_y) * A_dx / A_dy ∘ X
 321  * where ∘ is our inequality operator.
 322  *
 323  * By construction, we know that A_dy (and (Y - A_y)) are
 324  * all positive, so we can rearrange it thus without causing a sign change:
 325  *   (Y - A_y) * A_dx ∘ (X - A_x) * A_dy
 326  *
 327  * Given the assumption that all the deltas fit within 32 bits, we can compute
 328  * this comparison directly using 64 bit arithmetic.
 329  *
 330  * See the similar discussion for _slope_compare() and
 331  * edges_compare_x_for_y_general().
 332  */
 333 static int
 334 edge_compare_for_y_against_x (const cairo_bo_edge_t *a,
 335                               int32_t y,
 336                               int32_t x)
 337 {
 338     int32_t adx, ady;
 339     int32_t dx, dy;
 340     cairo_int64_t L, R;
 341
 342     if (x < a->edge.line.p1.x && x < a->edge.line.p2.x)
 343         return 1;
 344     if (x > a->edge.line.p1.x && x > a->edge.line.p2.x)
 345         return -1;
 346
 347     adx = a->edge.line.p2.x - a->edge.line.p1.x;
 348     dx = x - a->edge.line.p1.x;
 349
 350     if (adx == 0)
 351         return -dx;
 352     if (dx == 0 || (adx ^ dx) < 0)
 353         return adx;
 354
 355     dy = y - a->edge.line.p1.y;
 356     ady = a->edge.line.p2.y - a->edge.line.p1.y;
 357
 358     L = _cairo_int32x32_64_mul (dy, adx);
 359     R = _cairo_int32x32_64_mul (dx, ady);
 360
 361     return _cairo_int64_cmp (L, R);
 362 }
 363
 364 static inline int
 365 _cairo_bo_sweep_line_compare_edges (const cairo_bo_sweep_line_t *sweep_line,
 366                                     const cairo_bo_edge_t       *a,
 367                                     const cairo_bo_edge_t       *b)
 368 {
 369     int cmp;
 370
 371     cmp = cairo_lines_compare_at_y (&a->edge.line,
 372                                     &b->edge.line,
 373                                     sweep_line->current_y);
 374     if (cmp)
 375             return cmp;
 376
 377     /* We've got two collinear edges now. */
 378     return b->edge.bottom - a->edge.bottom;
 379 }
 380
 381 static inline cairo_int64_t
 382 det32_64 (int32_t a, int32_t b,
 383           int32_t c, int32_t d)
 384 {
 385     /* det = a * d - b * c */
 386     return _cairo_int64_sub (_cairo_int32x32_64_mul (a, d),
 387                              _cairo_int32x32_64_mul (b, c));
 388 }
 389
 390 static inline cairo_int128_t
 391 det64x32_128 (cairo_int64_t a, int32_t       b,
 392               cairo_int64_t c, int32_t       d)
 393 {
 394     /* det = a * d - b * c */
 395     return _cairo_int128_sub (_cairo_int64x32_128_mul (a, d),
 396                               _cairo_int64x32_128_mul (c, b));
 397 }
 398
 399 /* Compute the intersection of two lines as defined by two edges. The
 400  * result is provided as a coordinate pair of 128-bit integers.
 401  *
 402  * Returns %CAIRO_BO_STATUS_INTERSECTION if there is an intersection or
 403  * %CAIRO_BO_STATUS_PARALLEL if the two lines are exactly parallel.
 404  */
 405 static cairo_bool_t
 406 intersect_lines (cairo_bo_edge_t                *a,
 407                  cairo_bo_edge_t                *b,
 408                  cairo_bo_intersect_point_t     *intersection)
 409 {
 410     cairo_int64_t a_det, b_det;
 411
 412     /* XXX: We're assuming here that dx and dy will still fit in 32
 413      * bits. That's not true in general as there could be overflow. We
 414      * should prevent that before the tessellation algorithm begins.
 415      * What we're doing to mitigate this is to perform clamping in
 416      * cairo_bo_tessellate_polygon().
 417      */
 418     int32_t dx1 = a->edge.line.p1.x - a->edge.line.p2.x;
 419     int32_t dy1 = a->edge.line.p1.y - a->edge.line.p2.y;
 420
 421     int32_t dx2 = b->edge.line.p1.x - b->edge.line.p2.x;
 422     int32_t dy2 = b->edge.line.p1.y - b->edge.line.p2.y;
 423
 424     cairo_int64_t den_det;
 425     cairo_int64_t R;
 426     cairo_quorem64_t qr;
 427
 428     den_det = det32_64 (dx1, dy1, dx2, dy2);
 429
 430      /* Q: Can we determine that the lines do not intersect (within range)
 431       * much more cheaply than computing the intersection point i.e. by
 432       * avoiding the division?
 433       *
 434       *   X = ax + t * adx = bx + s * bdx;
 435       *   Y = ay + t * ady = by + s * bdy;
 436       *   ∴ t * (ady*bdx - bdy*adx) = bdx * (by - ay) + bdy * (ax - bx)
 437       *   => t * L = R
 438       *
 439       * Therefore we can reject any intersection (under the criteria for
 440       * valid intersection events) if:
 441       *   L^R < 0 => t < 0, or
 442       *   L<R => t > 1
 443       *
 444       * (where top/bottom must at least extend to the line endpoints).
 445       *
 446       * A similar substitution can be performed for s, yielding:
 447       *   s * (ady*bdx - bdy*adx) = ady * (ax - bx) - adx * (ay - by)
 448       */
 449     R = det32_64 (dx2, dy2,
 450                   b->edge.line.p1.x - a->edge.line.p1.x,
 451                   b->edge.line.p1.y - a->edge.line.p1.y);
 452     if (_cairo_int64_negative (den_det)) {
 453         if (_cairo_int64_ge (den_det, R))
 454             return FALSE;
 455     } else {
 456         if (_cairo_int64_le (den_det, R))
 457             return FALSE;
 458     }
 459
 460     R = det32_64 (dy1, dx1,
 461                   a->edge.line.p1.y - b->edge.line.p1.y,
 462                   a->edge.line.p1.x - b->edge.line.p1.x);
 463     if (_cairo_int64_negative (den_det)) {
 464         if (_cairo_int64_ge (den_det, R))
 465             return FALSE;
 466     } else {
 467         if (_cairo_int64_le (den_det, R))
 468             return FALSE;
 469     }
 470
 471     /* We now know that the two lines should intersect within range. */
 472
 473     a_det = det32_64 (a->edge.line.p1.x, a->edge.line.p1.y,
 474                       a->edge.line.p2.x, a->edge.line.p2.y);
 475     b_det = det32_64 (b->edge.line.p1.x, b->edge.line.p1.y,
 476                       b->edge.line.p2.x, b->edge.line.p2.y);
 477
 478     /* x = det (a_det, dx1, b_det, dx2) / den_det */
 479     qr = _cairo_int_96by64_32x64_divrem (det64x32_128 (a_det, dx1,
 480                                                        b_det, dx2),
 481                                          den_det);
 482     if (_cairo_int64_eq (qr.rem, den_det))
 483         return FALSE;
 484 #if 0
 485     intersection->x.exactness = _cairo_int64_is_zero (qr.rem) ? EXACT : INEXACT;
 486 #else
 487     intersection->x.exactness = EXACT;
 488     if (! _cairo_int64_is_zero (qr.rem)) {
 489         if (_cairo_int64_negative (den_det) ^ _cairo_int64_negative (qr.rem))
 490             qr.rem = _cairo_int64_negate (qr.rem);
 491         qr.rem = _cairo_int64_mul (qr.rem, _cairo_int32_to_int64 (2));
 492         if (_cairo_int64_ge (qr.rem, den_det)) {
 493             qr.quo = _cairo_int64_add (qr.quo,
 494                                        _cairo_int32_to_int64 (_cairo_int64_negative (qr.quo) ? -1 : 1));
 495         } else
 496             intersection->x.exactness = INEXACT;
 497     }
 498 #endif
 499     intersection->x.ordinate = _cairo_int64_to_int32 (qr.quo);
 500
 501     /* y = det (a_det, dy1, b_det, dy2) / den_det */
 502     qr = _cairo_int_96by64_32x64_divrem (det64x32_128 (a_det, dy1,
 503                                                        b_det, dy2),
 504                                          den_det);
 505     if (_cairo_int64_eq (qr.rem, den_det))
 506         return FALSE;
 507 #if 0
 508     intersection->y.exactness = _cairo_int64_is_zero (qr.rem) ? EXACT : INEXACT;
 509 #else
 510     intersection->y.exactness = EXACT;
 511     if (! _cairo_int64_is_zero (qr.rem)) {
 512         if (_cairo_int64_negative (den_det) ^ _cairo_int64_negative (qr.rem))
 513             qr.rem = _cairo_int64_negate (qr.rem);
 514         qr.rem = _cairo_int64_mul (qr.rem, _cairo_int32_to_int64 (2));
 515         if (_cairo_int64_ge (qr.rem, den_det)) {
 516             qr.quo = _cairo_int64_add (qr.quo,
 517                                        _cairo_int32_to_int64 (_cairo_int64_negative (qr.quo) ? -1 : 1));
 518         } else
 519             intersection->y.exactness = INEXACT;
 520     }
 521 #endif
 522     intersection->y.ordinate = _cairo_int64_to_int32 (qr.quo);
 523
 524     return TRUE;
 525 }
 526
 527 static int
 528 _cairo_bo_intersect_ordinate_32_compare (cairo_bo_intersect_ordinate_t  a,
 529                                          int32_t                        b)
 530 {
 531     /* First compare the quotient */
 532     if (a.ordinate > b)
 533         return +1;
 534     if (a.ordinate < b)
 535         return -1;
 536     /* With quotient identical, if remainder is 0 then compare equal */
 537     /* Otherwise, the non-zero remainder makes a > b */
 538     return INEXACT == a.exactness;
 539 }
 540
 541 /* Does the given edge contain the given point. The point must already
 542  * be known to be contained within the line determined by the edge,
 543  * (most likely the point results from an intersection of this edge
 544  * with another).
 545  *
 546  * If we had exact arithmetic, then this function would simply be a
 547  * matter of examining whether the y value of the point lies within
 548  * the range of y values of the edge. But since intersection points
 549  * are not exact due to being rounded to the nearest integer within
 550  * the available precision, we must also examine the x value of the
 551  * point.
 552  *
 553  * The definition of "contains" here is that the given intersection
 554  * point will be seen by the sweep line after the start event for the
 555  * given edge and before the stop event for the edge. See the comments
 556  * in the implementation for more details.
 557  */
 558 static cairo_bool_t
 559 _cairo_bo_edge_contains_intersect_point (cairo_bo_edge_t                *edge,
 560                                          cairo_bo_intersect_point_t     *point)
 561 {
 562     int cmp_top, cmp_bottom;
 563
 564     /* XXX: When running the actual algorithm, we don't actually need to
 565      * compare against edge->top at all here, since any intersection above
 566      * top is eliminated early via a slope comparison. We're leaving these
 567      * here for now only for the sake of the quadratic-time intersection
 568      * finder which needs them.
 569      */
 570
 571     cmp_top = _cairo_bo_intersect_ordinate_32_compare (point->y,
 572                                                        edge->edge.top);
 573     cmp_bottom = _cairo_bo_intersect_ordinate_32_compare (point->y,
 574                                                           edge->edge.bottom);
 575
 576     if (cmp_top < 0 || cmp_bottom > 0)
 577     {
 578         return FALSE;
 579     }
 580
 581     if (cmp_top > 0 && cmp_bottom < 0)
 582     {
 583         return TRUE;
 584     }
 585
 586     /* At this stage, the point lies on the same y value as either
 587      * edge->top or edge->bottom, so we have to examine the x value in
 588      * order to properly determine containment. */
 589
 590     /* If the y value of the point is the same as the y value of the
 591      * top of the edge, then the x value of the point must be greater
 592      * to be considered as inside the edge. Similarly, if the y value
 593      * of the point is the same as the y value of the bottom of the
 594      * edge, then the x value of the point must be less to be
 595      * considered as inside. */
 596
 597     if (cmp_top == 0) {
 598         cairo_fixed_t top_x;
 599
 600         top_x = _line_compute_intersection_x_for_y (&edge->edge.line,
 601                                                     edge->edge.top);
 602         return _cairo_bo_intersect_ordinate_32_compare (point->x, top_x) > 0;
 603     } else { /* cmp_bottom == 0 */
 604         cairo_fixed_t bot_x;
 605
 606         bot_x = _line_compute_intersection_x_for_y (&edge->edge.line,
 607                                                     edge->edge.bottom);
 608         return _cairo_bo_intersect_ordinate_32_compare (point->x, bot_x) < 0;
 609     }
 610 }
 611
 612 /* Compute the intersection of two edges. The result is provided as a
 613  * coordinate pair of 128-bit integers.
 614  *
 615  * Returns %CAIRO_BO_STATUS_INTERSECTION if there is an intersection
 616  * that is within both edges, %CAIRO_BO_STATUS_NO_INTERSECTION if the
 617  * intersection of the lines defined by the edges occurs outside of
 618  * one or both edges, and %CAIRO_BO_STATUS_PARALLEL if the two edges
 619  * are exactly parallel.
 620  *
 621  * Note that when determining if a candidate intersection is "inside"
 622  * an edge, we consider both the infinitesimal shortening and the
 623  * infinitesimal tilt rules described by John Hobby. Specifically, if
 624  * the intersection is exactly the same as an edge point, it is
 625  * effectively outside (no intersection is returned). Also, if the
 626  * intersection point has the same
 627  */
 628 static cairo_bool_t
 629 _cairo_bo_edge_intersect (cairo_bo_edge_t       *a,
 630                           cairo_bo_edge_t       *b,
 631                           cairo_bo_point32_t    *intersection)
 632 {
 633     cairo_bo_intersect_point_t quorem;
 634
 635     if (! intersect_lines (a, b, &quorem))
 636         return FALSE;
 637
 638     if (! _cairo_bo_edge_contains_intersect_point (a, &quorem))
 639         return FALSE;
 640
 641     if (! _cairo_bo_edge_contains_intersect_point (b, &quorem))
 642         return FALSE;
 643
 644     /* Now that we've correctly compared the intersection point and
 645      * determined that it lies within the edge, then we know that we
 646      * no longer need any more bits of storage for the intersection
 647      * than we do for our edge coordinates. We also no longer need the
 648      * remainder from the division. */
 649     intersection->x = quorem.x.ordinate;
 650     intersection->y = quorem.y.ordinate;
 651
 652     return TRUE;
 653 }
 654
 655 static inline int
 656 cairo_bo_event_compare (const cairo_bo_event_t *a,
 657                         const cairo_bo_event_t *b)
 658 {
 659     int cmp;
 660
 661     cmp = _cairo_bo_point32_compare (&a->point, &b->point);
 662     if (cmp)
 663         return cmp;
 664
 665     cmp = a->type - b->type;
 666     if (cmp)
 667         return cmp;
 668
 669     return a - b;
 670 }
 671
 672 static inline void
 673 _pqueue_init (pqueue_t *pq)
 674 {
 675     pq->max_size = ARRAY_LENGTH (pq->elements_embedded);
 676     pq->size = 0;
 677
 678     pq->elements = pq->elements_embedded;
 679 }
 680
 681 static inline void
 682 _pqueue_fini (pqueue_t *pq)
 683 {
 684     if (pq->elements != pq->elements_embedded)
 685         free (pq->elements);
 686 }
 687
 688 static cairo_status_t
 689 _pqueue_grow (pqueue_t *pq)
 690 {
 691     cairo_bo_event_t **new_elements;
 692     pq->max_size *= 2;
 693
 694     if (pq->elements == pq->elements_embedded) {
 695         new_elements = _cairo_malloc_ab (pq->max_size,
 696                                          sizeof (cairo_bo_event_t *));
 697         if (unlikely (new_elements == NULL))
 698             return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 699
 700         memcpy (new_elements, pq->elements_embedded,
 701                 sizeof (pq->elements_embedded));
 702     } else {
 703         new_elements = _cairo_realloc_ab (pq->elements,
 704                                           pq->max_size,
 705                                           sizeof (cairo_bo_event_t *));
 706         if (unlikely (new_elements == NULL))
 707             return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 708     }
 709
 710     pq->elements = new_elements;
 711     return CAIRO_STATUS_SUCCESS;
 712 }
 713
 714 static inline cairo_status_t
 715 _pqueue_push (pqueue_t *pq, cairo_bo_event_t *event)
 716 {
 717     cairo_bo_event_t **elements;
 718     int i, parent;
 719
 720     if (unlikely (pq->size + 1 == pq->max_size)) {
 721         cairo_status_t status;
 722
 723         status = _pqueue_grow (pq);
 724         if (unlikely (status))
 725             return status;
 726     }
 727
 728     elements = pq->elements;
 729
 730     for (i = ++pq->size;
 731          i != PQ_FIRST_ENTRY &&
 732          cairo_bo_event_compare (event,
 733                                  elements[parent = PQ_PARENT_INDEX (i)]) < 0;
 734          i = parent)
 735     {
 736         elements[i] = elements[parent];
 737     }
 738
 739     elements[i] = event;
 740
 741     return CAIRO_STATUS_SUCCESS;
 742 }
 743
 744 static inline void
 745 _pqueue_pop (pqueue_t *pq)
 746 {
 747     cairo_bo_event_t **elements = pq->elements;
 748     cairo_bo_event_t *tail;
 749     int child, i;
 750
 751     tail = elements[pq->size--];
 752     if (pq->size == 0) {
 753         elements[PQ_FIRST_ENTRY] = NULL;
 754         return;
 755     }
 756
 757     for (i = PQ_FIRST_ENTRY;
 758          (child = PQ_LEFT_CHILD_INDEX (i)) <= pq->size;
 759          i = child)
 760     {
 761         if (child != pq->size &&
 762             cairo_bo_event_compare (elements[child+1],
 763                                     elements[child]) < 0)
 764         {
 765             child++;
 766         }
 767
 768         if (cairo_bo_event_compare (elements[child], tail) >= 0)
 769             break;
 770
 771         elements[i] = elements[child];
 772     }
 773     elements[i] = tail;
 774 }
 775
 776 static inline cairo_status_t
 777 _cairo_bo_event_queue_insert (cairo_bo_event_queue_t    *queue,
 778                               cairo_bo_event_type_t      type,
 779                               cairo_bo_edge_t           *e1,
 780                               cairo_bo_edge_t           *e2,
 781                               const cairo_point_t        *point)
 782 {
 783     cairo_bo_queue_event_t *event;
 784
 785     event = _cairo_freepool_alloc (&queue->pool);
 786     if (unlikely (event == NULL))
 787         return _cairo_error (CAIRO_STATUS_NO_MEMORY);
 788
 789     event->type = type;
 790     event->e1 = e1;
 791     event->e2 = e2;
 792     event->point = *point;
 793
 794     return _pqueue_push (&queue->pqueue, (cairo_bo_event_t *) event);
 795 }
 796
 797 static void
 798 _cairo_bo_event_queue_delete (cairo_bo_event_queue_t *queue,
 799                               cairo_bo_event_t       *event)
 800 {
 801     _cairo_freepool_free (&queue->pool, event);
 802 }
 803
 804 static cairo_bo_event_t *
 805 _cairo_bo_event_dequeue (cairo_bo_event_queue_t *event_queue)
 806 {
 807     cairo_bo_event_t *event, *cmp;
 808
 809     event = event_queue->pqueue.elements[PQ_FIRST_ENTRY];
 810     cmp = *event_queue->start_events;
 811     if (event == NULL ||
 812         (cmp != NULL && cairo_bo_event_compare (cmp, event) < 0))
 813     {
 814         event = cmp;
 815         event_queue->start_events++;
 816     }
 817     else
 818     {
 819         _pqueue_pop (&event_queue->pqueue);
 820     }
 821
 822     return event;
 823 }
 824
 825 CAIRO_COMBSORT_DECLARE (_cairo_bo_event_queue_sort,
 826                         cairo_bo_event_t *,
 827                         cairo_bo_event_compare)
 828
 829 static void
 830 _cairo_bo_event_queue_init (cairo_bo_event_queue_t       *event_queue,
 831                             cairo_bo_event_t            **start_events,
 832                             int                           num_events)
 833 {
 834     event_queue->start_events = start_events;
 835
 836     _cairo_freepool_init (&event_queue->pool,
 837                           sizeof (cairo_bo_queue_event_t));
 838     _pqueue_init (&event_queue->pqueue);
 839     event_queue->pqueue.elements[PQ_FIRST_ENTRY] = NULL;
 840 }
 841
 842 static cairo_status_t
 843 _cairo_bo_event_queue_insert_stop (cairo_bo_event_queue_t       *event_queue,
 844                                    cairo_bo_edge_t              *edge)
 845 {
 846     cairo_bo_point32_t point;
 847
 848     point.y = edge->edge.bottom;
 849     point.x = _line_compute_intersection_x_for_y (&edge->edge.line,
 850                                                   point.y);
 851     return _cairo_bo_event_queue_insert (event_queue,
 852                                          CAIRO_BO_EVENT_TYPE_STOP,
 853                                          edge, NULL,
 854                                          &point);
 855 }
 856
 857 static void
 858 _cairo_bo_event_queue_fini (cairo_bo_event_queue_t *event_queue)
 859 {
 860     _pqueue_fini (&event_queue->pqueue);
 861     _cairo_freepool_fini (&event_queue->pool);
 862 }
 863
 864 static inline cairo_status_t
 865 _cairo_bo_event_queue_insert_if_intersect_below_current_y (cairo_bo_event_queue_t       *event_queue,
 866                                                            cairo_bo_edge_t      *left,
 867                                                            cairo_bo_edge_t *right)
 868 {
 869     cairo_bo_point32_t intersection;
 870
 871     if (MAX (left->edge.line.p1.x, left->edge.line.p2.x) <=
 872         MIN (right->edge.line.p1.x, right->edge.line.p2.x))
 873         return CAIRO_STATUS_SUCCESS;
 874
 875     if (cairo_lines_equal (&left->edge.line, &right->edge.line))
 876         return CAIRO_STATUS_SUCCESS;
 877
 878     /* The names "left" and "right" here are correct descriptions of
 879      * the order of the two edges within the active edge list. So if a
 880      * slope comparison also puts left less than right, then we know
 881      * that the intersection of these two segments has already
 882      * occurred before the current sweep line position. */
 883     if (_slope_compare (left, right) <= 0)
 884         return CAIRO_STATUS_SUCCESS;
 885
 886     if (! _cairo_bo_edge_intersect (left, right, &intersection))
 887         return CAIRO_STATUS_SUCCESS;
 888
 889     return _cairo_bo_event_queue_insert (event_queue,
 890                                          CAIRO_BO_EVENT_TYPE_INTERSECTION,
 891                                          left, right,
 892                                          &intersection);
 893 }
 894
 895 static void
 896 _cairo_bo_sweep_line_init (cairo_bo_sweep_line_t *sweep_line)
 897 {
 898     sweep_line->head = NULL;
 899     sweep_line->stopped = NULL;
 900     sweep_line->current_y = INT32_MIN;
 901     sweep_line->current_edge = NULL;
 902 }
 903
 904 static void
 905 _cairo_bo_sweep_line_insert (cairo_bo_sweep_line_t      *sweep_line,
 906                              cairo_bo_edge_t            *edge)
 907 {
 908     if (sweep_line->current_edge != NULL) {
 909         cairo_bo_edge_t *prev, *next;
 910         int cmp;
 911
 912         cmp = _cairo_bo_sweep_line_compare_edges (sweep_line,
 913                                                   sweep_line->current_edge,
 914                                                   edge);
 915         if (cmp < 0) {
 916             prev = sweep_line->current_edge;
 917             next = prev->next;
 918             while (next != NULL &&
 919                    _cairo_bo_sweep_line_compare_edges (sweep_line,
 920                                                        next, edge) < 0)
 921             {
 922                 prev = next, next = prev->next;
 923             }
 924
 925             prev->next = edge;
 926             edge->prev = prev;
 927             edge->next = next;
 928             if (next != NULL)
 929                 next->prev = edge;
 930         } else if (cmp > 0) {
 931             next = sweep_line->current_edge;
 932             prev = next->prev;
 933             while (prev != NULL &&
 934                    _cairo_bo_sweep_line_compare_edges (sweep_line,
 935                                                        prev, edge) > 0)
 936             {
 937                 next = prev, prev = next->prev;
 938             }
 939
 940             next->prev = edge;
 941             edge->next = next;
 942             edge->prev = prev;
 943             if (prev != NULL)
 944                 prev->next = edge;
 945             else
 946                 sweep_line->head = edge;
 947         } else {
 948             prev = sweep_line->current_edge;
 949             edge->prev = prev;
 950             edge->next = prev->next;
 951             if (prev->next != NULL)
 952                 prev->next->prev = edge;
 953             prev->next = edge;
 954         }
 955     } else {
 956         sweep_line->head = edge;
 957         edge->next = NULL;
 958     }
 959
 960     sweep_line->current_edge = edge;
 961 }
 962
 963 static void
 964 _cairo_bo_sweep_line_delete (cairo_bo_sweep_line_t      *sweep_line,
 965                              cairo_bo_edge_t    *edge)
 966 {
 967     if (edge->prev != NULL)
 968         edge->prev->next = edge->next;
 969     else
 970         sweep_line->head = edge->next;
 971
 972     if (edge->next != NULL)
 973         edge->next->prev = edge->prev;
 974
 975     if (sweep_line->current_edge == edge)
 976         sweep_line->current_edge = edge->prev ? edge->prev : edge->next;
 977 }
 978
 979 static void
 980 _cairo_bo_sweep_line_swap (cairo_bo_sweep_line_t        *sweep_line,
 981                            cairo_bo_edge_t              *left,
 982                            cairo_bo_edge_t              *right)
 983 {
 984     if (left->prev != NULL)
 985         left->prev->next = right;
 986     else
 987         sweep_line->head = right;
 988
 989     if (right->next != NULL)
 990         right->next->prev = left;
 991
 992     left->next = right->next;
 993     right->next = left;
 994
 995     right->prev = left->prev;
 996     left->prev = right;
 997 }
 998
 999 #if DEBUG_PRINT_STATE
1000 static void
1001 _cairo_bo_edge_print (cairo_bo_edge_t *edge)
1002 {
1003     printf ("(0x%x, 0x%x)-(0x%x, 0x%x)",
1004             edge->edge.line.p1.x, edge->edge.line.p1.y,
1005             edge->edge.line.p2.x, edge->edge.line.p2.y);
1006 }
1007
1008 static void
1009 _cairo_bo_event_print (cairo_bo_event_t *event)
1010 {
1011     switch (event->type) {
1012     case CAIRO_BO_EVENT_TYPE_START:
1013         printf ("Start: ");
1014         break;
1015     case CAIRO_BO_EVENT_TYPE_STOP:
1016         printf ("Stop: ");
1017         break;
1018     case CAIRO_BO_EVENT_TYPE_INTERSECTION:
1019         printf ("Intersection: ");
1020         break;
1021     }
1022     printf ("(%d, %d)\t", event->point.x, event->point.y);
1023     _cairo_bo_edge_print (event->e1);
1024     if (event->type == CAIRO_BO_EVENT_TYPE_INTERSECTION) {
1025         printf (" X ");
1026         _cairo_bo_edge_print (event->e2);
1027     }
1028     printf ("\n");
1029 }
1030
1031 static void
1032 _cairo_bo_event_queue_print (cairo_bo_event_queue_t *event_queue)
1033 {
1034     /* XXX: fixme to print the start/stop array too. */
1035     printf ("Event queue:\n");
1036 }
1037
1038 static void
1039 _cairo_bo_sweep_line_print (cairo_bo_sweep_line_t *sweep_line)
1040 {
1041     cairo_bool_t first = TRUE;
1042     cairo_bo_edge_t *edge;
1043
1044     printf ("Sweep line from edge list: ");
1045     first = TRUE;
1046     for (edge = sweep_line->head;
1047          edge;
1048          edge = edge->next)
1049     {
1050         if (!first)
1051             printf (", ");
1052         _cairo_bo_edge_print (edge);
1053         first = FALSE;
1054     }
1055     printf ("\n");
1056 }
1057
1058 static void
1059 print_state (const char                 *msg,
1060              cairo_bo_event_t           *event,
1061              cairo_bo_event_queue_t     *event_queue,
1062              cairo_bo_sweep_line_t      *sweep_line)
1063 {
1064     printf ("%s ", msg);
1065     _cairo_bo_event_print (event);
1066     _cairo_bo_event_queue_print (event_queue);
1067     _cairo_bo_sweep_line_print (sweep_line);
1068     printf ("\n");
1069 }
1070 #endif
1071
1072 #if DEBUG_EVENTS
1073 static void CAIRO_PRINTF_FORMAT (1, 2)
1074 event_log (const char *fmt, ...)
1075 {
1076     FILE *file;
1077
1078     if (getenv ("CAIRO_DEBUG_EVENTS") == NULL)
1079         return;
1080
1081     file = fopen ("bo-events.txt", "a");
1082     if (file != NULL) {
1083         va_list ap;
1084
1085         va_start (ap, fmt);
1086         vfprintf (file, fmt, ap);
1087         va_end (ap);
1088
1089         fclose (file);
1090     }
1091 }
1092 #endif
1093
1094 #define HAS_COLINEAR(a, b) ((cairo_bo_edge_t *)(((uintptr_t)(a))&~1) == (b))
1095 #define IS_COLINEAR(e) (((uintptr_t)(e))&1)
1096 #define MARK_COLINEAR(e, v) ((cairo_bo_edge_t *)(((uintptr_t)(e))|(v)))
1097
1098 static inline cairo_bool_t
1099 edges_colinear (cairo_bo_edge_t *a, const cairo_bo_edge_t *b)
1100 {
1101     unsigned p;
1102
1103     if (HAS_COLINEAR(a->colinear, b))
1104         return IS_COLINEAR(a->colinear);
1105
1106     if (HAS_COLINEAR(b->colinear, a)) {
1107         p = IS_COLINEAR(b->colinear);
1108         a->colinear = MARK_COLINEAR(b, p);
1109         return p;
1110     }
1111
1112     p = 0;
1113     p |= (a->edge.line.p1.x == b->edge.line.p1.x) << 0;
1114     p |= (a->edge.line.p1.y == b->edge.line.p1.y) << 1;
1115     p |= (a->edge.line.p2.x == b->edge.line.p2.x) << 3;
1116     p |= (a->edge.line.p2.y == b->edge.line.p2.y) << 4;
1117     if (p == ((1 << 0) | (1 << 1) | (1 << 3) | (1 << 4))) {
1118         a->colinear = MARK_COLINEAR(b, 1);
1119         return TRUE;
1120     }
1121
1122     if (_slope_compare (a, b)) {
1123         a->colinear = MARK_COLINEAR(b, 0);
1124         return FALSE;
1125     }
1126
1127     /* The choice of y is not truly arbitrary since we must guarantee that it
1128      * is greater than the start of either line.
1129      */
1130     if (p != 0) {
1131         /* colinear if either end-point are coincident */
1132         p = (((p >> 1) & p) & 5) != 0;
1133     } else if (a->edge.line.p1.y < b->edge.line.p1.y) {
1134         p = edge_compare_for_y_against_x (b,
1135                                           a->edge.line.p1.y,
1136                                           a->edge.line.p1.x) == 0;
1137     } else {
1138         p = edge_compare_for_y_against_x (a,
1139                                           b->edge.line.p1.y,
1140                                           b->edge.line.p1.x) == 0;
1141     }
1142
1143     a->colinear = MARK_COLINEAR(b, p);
1144     return p;
1145 }
1146
1147 /* Adds the trapezoid, if any, of the left edge to the #cairo_traps_t */
1148 static void
1149 _cairo_bo_edge_end_trap (cairo_bo_edge_t        *left,
1150                          int32_t                 bot,
1151                          cairo_traps_t          *traps)
1152 {
1153     cairo_bo_trap_t *trap = &left->deferred_trap;
1154
1155     /* Only emit (trivial) non-degenerate trapezoids with positive height. */
1156     if (likely (trap->top < bot)) {
1157         _cairo_traps_add_trap (traps,
1158                                trap->top, bot,
1159                                &left->edge.line, &trap->right->edge.line);
1160
1161 #if DEBUG_PRINT_STATE
1162         printf ("Deferred trap: left=(%x, %x)-(%x,%x) "
1163                 "right=(%x,%x)-(%x,%x) top=%x, bot=%x\n",
1164                 left->edge.line.p1.x, left->edge.line.p1.y,
1165                 left->edge.line.p2.x, left->edge.line.p2.y,
1166                 trap->right->edge.line.p1.x, trap->right->edge.line.p1.y,
1167                 trap->right->edge.line.p2.x, trap->right->edge.line.p2.y,
1168                 trap->top, bot);
1169 #endif
1170 #if DEBUG_EVENTS
1171         event_log ("end trap: %lu %lu %d %d\n",
1172                    (long) left,
1173                    (long) trap->right,
1174                    trap->top,
1175                    bot);
1176 #endif
1177     }
1178
1179     trap->right = NULL;
1180 }
1181
1182
1183 /* Start a new trapezoid at the given top y coordinate, whose edges
1184  * are `edge' and `edge->next'. If `edge' already has a trapezoid,
1185  * then either add it to the traps in `traps', if the trapezoid's
1186  * right edge differs from `edge->next', or do nothing if the new
1187  * trapezoid would be a continuation of the existing one. */
1188 static inline void
1189 _cairo_bo_edge_start_or_continue_trap (cairo_bo_edge_t  *left,
1190                                        cairo_bo_edge_t  *right,
1191                                        int               top,
1192                                        cairo_traps_t    *traps)
1193 {
1194     if (left->deferred_trap.right == right)
1195         return;
1196
1197     assert (right);
1198     if (left->deferred_trap.right != NULL) {
1199         if (edges_colinear (left->deferred_trap.right, right))
1200         {
1201             /* continuation on right, so just swap edges */
1202             left->deferred_trap.right = right;
1203             return;
1204         }
1205
1206         _cairo_bo_edge_end_trap (left, top, traps);
1207     }
1208
1209     if (! edges_colinear (left, right)) {
1210         left->deferred_trap.top = top;
1211         left->deferred_trap.right = right;
1212
1213 #if DEBUG_EVENTS
1214         event_log ("begin trap: %lu %lu %d\n",
1215                    (long) left,
1216                    (long) right,
1217                    top);
1218 #endif
1219     }
1220 }
1221
1222 static inline void
1223 _active_edges_to_traps (cairo_bo_edge_t *pos,
1224                         int32_t          top,
1225                         unsigned         mask,
1226                         cairo_traps_t        *traps)
1227 {
1228     cairo_bo_edge_t *left;
1229     int in_out;
1230
1231
1232 #if DEBUG_PRINT_STATE
1233     printf ("Processing active edges for %x\n", top);
1234 #endif
1235
1236     in_out = 0;
1237     left = pos;
1238     while (pos != NULL) {
1239         if (pos != left && pos->deferred_trap.right) {
1240             /* XXX It shouldn't be possible to here with 2 deferred traps
1241              * on colinear edges... See bug-bo-rictoz.
1242              */
1243             if (left->deferred_trap.right == NULL &&
1244                 edges_colinear (left, pos))
1245             {
1246                 /* continuation on left */
1247                 left->deferred_trap = pos->deferred_trap;
1248                 pos->deferred_trap.right = NULL;
1249             }
1250             else
1251             {
1252                 _cairo_bo_edge_end_trap (pos, top, traps);
1253             }
1254         }
1255
1256         in_out += pos->edge.dir;
1257         if ((in_out & mask) == 0) {
1258             /* skip co-linear edges */
1259             if (pos->next == NULL || ! edges_colinear (pos, pos->next)) {
1260                 _cairo_bo_edge_start_or_continue_trap (left, pos, top, traps);
1261                 left = pos->next;
1262             }
1263         }
1264
1265         pos = pos->next;
1266     }
1267 }
1268
1269 /* Execute a single pass of the Bentley-Ottmann algorithm on edges,
1270  * generating trapezoids according to the fill_rule and appending them
1271  * to traps. */
1272 static cairo_status_t
1273 _cairo_bentley_ottmann_tessellate_bo_edges (cairo_bo_event_t   **start_events,
1274                                             int                  num_events,
1275                                             unsigned             fill_rule,
1276                                             cairo_traps_t       *traps,
1277                                             int                 *num_intersections)
1278 {
1279     cairo_status_t status;
1280     int intersection_count = 0;
1281     cairo_bo_event_queue_t event_queue;
1282     cairo_bo_sweep_line_t sweep_line;
1283     cairo_bo_event_t *event;
1284     cairo_bo_edge_t *left, *right;
1285     cairo_bo_edge_t *e1, *e2;
1286
1287     /* convert the fill_rule into a winding mask */
1288     if (fill_rule == CAIRO_FILL_RULE_WINDING)
1289         fill_rule = (unsigned) -1;
1290     else
1291         fill_rule = 1;
1292
1293 #if DEBUG_EVENTS
1294     {
1295         int i;
1296
1297         for (i = 0; i < num_events; i++) {
1298             cairo_bo_start_event_t *event =
1299                 ((cairo_bo_start_event_t **) start_events)[i];
1300             event_log ("edge: %lu (%d, %d) (%d, %d) (%d, %d) %d\n",
1301                        (long) &events[i].edge,
1302                        event->edge.edge.line.p1.x,
1303                        event->edge.edge.line.p1.y,
1304                        event->edge.edge.line.p2.x,
1305                        event->edge.edge.line.p2.y,
1306                        event->edge.top,
1307                        event->edge.bottom,
1308                        event->edge.edge.dir);
1309         }
1310     }
1311 #endif
1312
1313     _cairo_bo_event_queue_init (&event_queue, start_events, num_events);
1314     _cairo_bo_sweep_line_init (&sweep_line);
1315
1316     while ((event = _cairo_bo_event_dequeue (&event_queue))) {
1317         if (event->point.y != sweep_line.current_y) {
1318             for (e1 = sweep_line.stopped; e1; e1 = e1->next) {
1319                 if (e1->deferred_trap.right != NULL) {
1320                     _cairo_bo_edge_end_trap (e1,
1321                                              e1->edge.bottom,
1322                                              traps);
1323                 }
1324             }
1325             sweep_line.stopped = NULL;
1326
1327             _active_edges_to_traps (sweep_line.head,
1328                                     sweep_line.current_y,
1329                                     fill_rule, traps);
1330
1331             sweep_line.current_y = event->point.y;
1332         }
1333
1334 #if DEBUG_EVENTS
1335         event_log ("event: %d (%ld, %ld) %lu, %lu\n",
1336                    event->type,
1337                    (long) event->point.x,
1338                    (long) event->point.y,
1339                    (long) event->e1,
1340                    (long) event->e2);
1341 #endif
1342
1343         switch (event->type) {
1344         case CAIRO_BO_EVENT_TYPE_START:
1345             e1 = &((cairo_bo_start_event_t *) event)->edge;
1346
1347             _cairo_bo_sweep_line_insert (&sweep_line, e1);
1348
1349             status = _cairo_bo_event_queue_insert_stop (&event_queue, e1);
1350             if (unlikely (status))
1351                 goto unwind;
1352
1353             /* check to see if this is a continuation of a stopped edge */
1354             /* XXX change to an infinitesimal lengthening rule */
1355             for (left = sweep_line.stopped; left; left = left->next) {
1356                 if (e1->edge.top <= left->edge.bottom &&
1357                     edges_colinear (e1, left))
1358                 {
1359                     e1->deferred_trap = left->deferred_trap;
1360                     if (left->prev != NULL)
1361                         left->prev = left->next;
1362                     else
1363                         sweep_line.stopped = left->next;
1364                     if (left->next != NULL)
1365                         left->next->prev = left->prev;
1366                     break;
1367                 }
1368             }
1369
1370             left = e1->prev;
1371             right = e1->next;
1372
1373             if (left != NULL) {
1374                 status = _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, left, e1);
1375                 if (unlikely (status))
1376                     goto unwind;
1377             }
1378
1379             if (right != NULL) {
1380                 status = _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, e1, right);
1381                 if (unlikely (status))
1382                     goto unwind;
1383             }
1384
1385             break;
1386
1387         case CAIRO_BO_EVENT_TYPE_STOP:
1388             e1 = ((cairo_bo_queue_event_t *) event)->e1;
1389             _cairo_bo_event_queue_delete (&event_queue, event);
1390
1391             left = e1->prev;
1392             right = e1->next;
1393
1394             _cairo_bo_sweep_line_delete (&sweep_line, e1);
1395
1396             /* first, check to see if we have a continuation via a fresh edge */
1397             if (e1->deferred_trap.right != NULL) {
1398                 e1->next = sweep_line.stopped;
1399                 if (sweep_line.stopped != NULL)
1400                     sweep_line.stopped->prev = e1;
1401                 sweep_line.stopped = e1;
1402                 e1->prev = NULL;
1403             }
1404
1405             if (left != NULL && right != NULL) {
1406                 status = _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, left, right);
1407                 if (unlikely (status))
1408                     goto unwind;
1409             }
1410
1411             break;
1412
1413         case CAIRO_BO_EVENT_TYPE_INTERSECTION:
1414             e1 = ((cairo_bo_queue_event_t *) event)->e1;
1415             e2 = ((cairo_bo_queue_event_t *) event)->e2;
1416             _cairo_bo_event_queue_delete (&event_queue, event);
1417
1418             /* skip this intersection if its edges are not adjacent */
1419             if (e2 != e1->next)
1420                 break;
1421
1422             intersection_count++;
1423
1424             left = e1->prev;
1425             right = e2->next;
1426
1427             _cairo_bo_sweep_line_swap (&sweep_line, e1, e2);
1428
1429             /* after the swap e2 is left of e1 */
1430
1431             if (left != NULL) {
1432                 status = _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, left, e2);
1433                 if (unlikely (status))
1434                     goto unwind;
1435             }
1436
1437             if (right != NULL) {
1438                 status = _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, e1, right);
1439                 if (unlikely (status))
1440                     goto unwind;
1441             }
1442
1443             break;
1444         }
1445     }
1446
1447     *num_intersections = intersection_count;
1448     for (e1 = sweep_line.stopped; e1; e1 = e1->next) {
1449         if (e1->deferred_trap.right != NULL) {
1450             _cairo_bo_edge_end_trap (e1, e1->edge.bottom, traps);
1451         }
1452     }
1453     status = traps->status;
1454  unwind:
1455     _cairo_bo_event_queue_fini (&event_queue);
1456
1457 #if DEBUG_EVENTS
1458     event_log ("\n");
1459 #endif
1460
1461     return status;
1462 }
1463
1464 cairo_status_t
1465 _cairo_bentley_ottmann_tessellate_polygon (cairo_traps_t         *traps,
1466                                            const cairo_polygon_t *polygon,
1467                                            cairo_fill_rule_t      fill_rule)
1468 {
1469     int intersections;
1470     cairo_bo_start_event_t stack_events[CAIRO_STACK_ARRAY_LENGTH (cairo_bo_start_event_t)];
1471     cairo_bo_start_event_t *events;
1472     cairo_bo_event_t *stack_event_ptrs[ARRAY_LENGTH (stack_events) + 1];
1473     cairo_bo_event_t **event_ptrs;
1474     cairo_bo_start_event_t *stack_event_y[64];
1475     cairo_bo_start_event_t **event_y = NULL;
1476     int i, num_events, y, ymin, ymax;
1477     cairo_status_t status;
1478
1479     num_events = polygon->num_edges;
1480     if (unlikely (0 == num_events))
1481         return CAIRO_STATUS_SUCCESS;
1482
1483     if (polygon->num_limits) {
1484         ymin = _cairo_fixed_integer_floor (polygon->limit.p1.y);
1485         ymax = _cairo_fixed_integer_ceil (polygon->limit.p2.y) - ymin;
1486
1487         if (ymax > 64) {
1488             event_y = _cairo_malloc_ab(sizeof (cairo_bo_event_t*), ymax);
1489             if (unlikely (event_y == NULL))
1490                 return _cairo_error (CAIRO_STATUS_NO_MEMORY);
1491         } else {
1492             event_y = stack_event_y;
1493         }
1494         memset (event_y, 0, ymax * sizeof(cairo_bo_event_t *));
1495     }
1496
1497     events = stack_events;
1498     event_ptrs = stack_event_ptrs;
1499     if (num_events > ARRAY_LENGTH (stack_events)) {
1500         events = _cairo_malloc_ab_plus_c (num_events,
1501                                           sizeof (cairo_bo_start_event_t) +
1502                                           sizeof (cairo_bo_event_t *),
1503                                           sizeof (cairo_bo_event_t *));
1504         if (unlikely (events == NULL)) {
1505             if (event_y != stack_event_y)
1506                 free (event_y);
1507             return _cairo_error (CAIRO_STATUS_NO_MEMORY);
1508         }
1509
1510         event_ptrs = (cairo_bo_event_t **) (events + num_events);
1511     }
1512
1513     for (i = 0; i < num_events; i++) {
1514         events[i].type = CAIRO_BO_EVENT_TYPE_START;
1515         events[i].point.y = polygon->edges[i].top;
1516         events[i].point.x =
1517             _line_compute_intersection_x_for_y (&polygon->edges[i].line,
1518                                                 events[i].point.y);
1519
1520         events[i].edge.edge = polygon->edges[i];
1521         events[i].edge.deferred_trap.right = NULL;
1522         events[i].edge.prev = NULL;
1523         events[i].edge.next = NULL;
1524         events[i].edge.colinear = NULL;
1525
1526         if (event_y) {
1527             y = _cairo_fixed_integer_floor (events[i].point.y) - ymin;
1528             events[i].edge.next = (cairo_bo_edge_t *) event_y[y];
1529             event_y[y] = (cairo_bo_start_event_t *) &events[i];
1530         } else
1531             event_ptrs[i] = (cairo_bo_event_t *) &events[i];
1532     }
1533
1534     if (event_y) {
1535         for (y = i = 0; y < ymax && i < num_events; y++) {
1536             cairo_bo_start_event_t *e;
1537             int j = i;
1538             for (e = event_y[y]; e; e = (cairo_bo_start_event_t *)e->edge.next)
1539                 event_ptrs[i++] = (cairo_bo_event_t *) e;
1540             if (i > j + 1)
1541                 _cairo_bo_event_queue_sort (event_ptrs+j, i-j);
1542         }
1543         if (event_y != stack_event_y)
1544             free (event_y);
1545     } else
1546         _cairo_bo_event_queue_sort (event_ptrs, i);
1547     event_ptrs[i] = NULL;
1548
1549 #if DEBUG_TRAPS
1550     dump_edges (events, num_events, "bo-polygon-edges.txt");
1551 #endif
1552
1553     /* XXX: This would be the convenient place to throw in multiple
1554      * passes of the Bentley-Ottmann algorithm. It would merely
1555      * require storing the results of each pass into a temporary
1556      * cairo_traps_t. */
1557     status = _cairo_bentley_ottmann_tessellate_bo_edges (event_ptrs, num_events,
1558                                                          fill_rule, traps,
1559                                                          &intersections);
1560 #if DEBUG_TRAPS
1561     dump_traps (traps, "bo-polygon-out.txt");
1562 #endif
1563
1564     if (events != stack_events)
1565         free (events);
1566
1567     return status;
1568 }
1569
1570 cairo_status_t
1571 _cairo_bentley_ottmann_tessellate_traps (cairo_traps_t *traps,
1572                                          cairo_fill_rule_t fill_rule)
1573 {
1574     cairo_status_t status;
1575     cairo_polygon_t polygon;
1576     int i;
1577
1578     if (unlikely (0 == traps->num_traps))
1579         return CAIRO_STATUS_SUCCESS;
1580
1581 #if DEBUG_TRAPS
1582     dump_traps (traps, "bo-traps-in.txt");
1583 #endif
1584
1585     _cairo_polygon_init (&polygon, traps->limits, traps->num_limits);
1586
1587     for (i = 0; i < traps->num_traps; i++) {
1588         status = _cairo_polygon_add_line (&polygon,
1589                                           &traps->traps[i].left,
1590                                           traps->traps[i].top,
1591                                           traps->traps[i].bottom,
1592                                           1);
1593         if (unlikely (status))
1594             goto CLEANUP;
1595
1596         status = _cairo_polygon_add_line (&polygon,
1597                                           &traps->traps[i].right,
1598                                           traps->traps[i].top,
1599                                           traps->traps[i].bottom,
1600                                           -1);
1601         if (unlikely (status))
1602             goto CLEANUP;
1603     }
1604
1605     _cairo_traps_clear (traps);
1606     status = _cairo_bentley_ottmann_tessellate_polygon (traps,
1607                                                         &polygon,
1608                                                         fill_rule);
1609
1610 #if DEBUG_TRAPS
1611     dump_traps (traps, "bo-traps-out.txt");
1612 #endif
1613
1614   CLEANUP:
1615     _cairo_polygon_fini (&polygon);
1616
1617     return status;
1618 }
1619
1620 #if 0
1621 static cairo_bool_t
1622 edges_have_an_intersection_quadratic (cairo_bo_edge_t   *edges,
1623                                       int                num_edges)
1624
1625 {
1626     int i, j;
1627     cairo_bo_edge_t *a, *b;
1628     cairo_bo_point32_t intersection;
1629
1630     /* We must not be given any upside-down edges. */
1631     for (i = 0; i < num_edges; i++) {
1632         assert (_cairo_bo_point32_compare (&edges[i].top, &edges[i].bottom) < 0);
1633         edges[i].line.p1.x <<= CAIRO_BO_GUARD_BITS;
1634         edges[i].line.p1.y <<= CAIRO_BO_GUARD_BITS;
1635         edges[i].line.p2.x <<= CAIRO_BO_GUARD_BITS;
1636         edges[i].line.p2.y <<= CAIRO_BO_GUARD_BITS;
1637     }
1638
1639     for (i = 0; i < num_edges; i++) {
1640         for (j = 0; j < num_edges; j++) {
1641             if (i == j)
1642                 continue;
1643
1644             a = &edges[i];
1645             b = &edges[j];
1646
1647             if (! _cairo_bo_edge_intersect (a, b, &intersection))
1648                 continue;
1649
1650             printf ("Found intersection (%d,%d) between (%d,%d)-(%d,%d) and (%d,%d)-(%d,%d)\n",
1651                     intersection.x,
1652                     intersection.y,
1653                     a->line.p1.x, a->line.p1.y,
1654                     a->line.p2.x, a->line.p2.y,
1655                     b->line.p1.x, b->line.p1.y,
1656                     b->line.p2.x, b->line.p2.y);
1657
1658             return TRUE;
1659         }
1660     }
1661     return FALSE;
1662 }
1663
1664 #define TEST_MAX_EDGES 10
1665
1666 typedef struct test {
1667     const char *name;
1668     const char *description;
1669     int num_edges;
1670     cairo_bo_edge_t edges[TEST_MAX_EDGES];
1671 } test_t;
1672
1673 static test_t
1674 tests[] = {
1675     {
1676         "3 near misses",
1677         "3 edges all intersecting very close to each other",
1678         3,
1679         {
1680             { { 4, 2}, {0, 0}, { 9, 9}, NULL, NULL },
1681             { { 7, 2}, {0, 0}, { 2, 3}, NULL, NULL },
1682             { { 5, 2}, {0, 0}, { 1, 7}, NULL, NULL }
1683         }
1684     },
1685     {
1686         "inconsistent data",
1687         "Derived from random testing---was leading to skip list and edge list disagreeing.",
1688         2,
1689         {
1690             { { 2, 3}, {0, 0}, { 8, 9}, NULL, NULL },
1691             { { 2, 3}, {0, 0}, { 6, 7}, NULL, NULL }
1692         }
1693     },
1694     {
1695         "failed sort",
1696         "A test derived from random testing that leads to an inconsistent sort --- looks like we just can't attempt to validate the sweep line with edge_compare?",
1697         3,
1698         {
1699             { { 6, 2}, {0, 0}, { 6, 5}, NULL, NULL },
1700             { { 3, 5}, {0, 0}, { 5, 6}, NULL, NULL },
1701             { { 9, 2}, {0, 0}, { 5, 6}, NULL, NULL },
1702         }
1703     },
1704     {
1705         "minimal-intersection",
1706         "Intersection of a two from among the smallest possible edges.",
1707         2,
1708         {
1709             { { 0, 0}, {0, 0}, { 1, 1}, NULL, NULL },
1710             { { 1, 0}, {0, 0}, { 0, 1}, NULL, NULL }
1711         }
1712     },
1713     {
1714         "simple",
1715         "A simple intersection of two edges at an integer (2,2).",
1716         2,
1717         {
1718             { { 1, 1}, {0, 0}, { 3, 3}, NULL, NULL },
1719             { { 2, 1}, {0, 0}, { 2, 3}, NULL, NULL }
1720         }
1721     },
1722     {
1723         "bend-to-horizontal",
1724         "With intersection truncation one edge bends to horizontal",
1725         2,
1726         {
1727             { { 9, 1}, {0, 0}, {3, 7}, NULL, NULL },
1728             { { 3, 5}, {0, 0}, {9, 9}, NULL, NULL }
1729         }
1730     }
1731 };
1732
1733 /*
1734     {
1735         "endpoint",
1736         "An intersection that occurs at the endpoint of a segment.",
1737         {
1738             { { 4, 6}, { 5, 6}, NULL, { { NULL }} },
1739             { { 4, 5}, { 5, 7}, NULL, { { NULL }} },
1740             { { 0, 0}, { 0, 0}, NULL, { { NULL }} },
1741         }
1742     }
1743     {
1744         name = "overlapping",
1745         desc = "Parallel segments that share an endpoint, with different slopes.",
1746         edges = {
1747             { top = { x = 2, y = 0}, bottom = { x = 1, y = 1}},
1748             { top = { x = 2, y = 0}, bottom = { x = 0, y = 2}},
1749             { top = { x = 0, y = 3}, bottom = { x = 1, y = 3}},
1750             { top = { x = 0, y = 3}, bottom = { x = 2, y = 3}},
1751             { top = { x = 0, y = 4}, bottom = { x = 0, y = 6}},
1752             { top = { x = 0, y = 5}, bottom = { x = 0, y = 6}}
1753         }
1754     },
1755     {
1756         name = "hobby_stage_3",
1757         desc = "A particularly tricky part of the 3rd stage of the 'hobby' test below.",
1758         edges = {
1759             { top = { x = -1, y = -2}, bottom = { x =  4, y = 2}},
1760             { top = { x =  5, y =  3}, bottom = { x =  9, y = 5}},
1761             { top = { x =  5, y =  3}, bottom = { x =  6, y = 3}},
1762         }
1763     },
1764     {
1765         name = "hobby",
1766         desc = "Example from John Hobby's paper. Requires 3 passes of the iterative algorithm.",
1767         edges = {
1768             { top = { x =   0, y =   0}, bottom = { x =   9, y =   5}},
1769             { top = { x =   0, y =   0}, bottom = { x =  13, y =   6}},
1770             { top = { x =  -1, y =  -2}, bottom = { x =   9, y =   5}}
1771         }
1772     },
1773     {
1774         name = "slope",
1775         desc = "Edges with same start/stop points but different slopes",
1776         edges = {
1777             { top = { x = 4, y = 1}, bottom = { x = 6, y = 3}},
1778             { top = { x = 4, y = 1}, bottom = { x = 2, y = 3}},
1779             { top = { x = 2, y = 4}, bottom = { x = 4, y = 6}},
1780             { top = { x = 6, y = 4}, bottom = { x = 4, y = 6}}
1781         }
1782     },
1783     {
1784         name = "horizontal",
1785         desc = "Test of a horizontal edge",
1786         edges = {
1787             { top = { x = 1, y = 1}, bottom = { x = 6, y = 6}},
1788             { top = { x = 2, y = 3}, bottom = { x = 5, y = 3}}
1789         }
1790     },
1791     {
1792         name = "vertical",
1793         desc = "Test of a vertical edge",
1794         edges = {
1795             { top = { x = 5, y = 1}, bottom = { x = 5, y = 7}},
1796             { top = { x = 2, y = 4}, bottom = { x = 8, y = 5}}
1797         }
1798     },
1799     {
1800         name = "congruent",
1801         desc = "Two overlapping edges with the same slope",
1802         edges = {
1803             { top = { x = 5, y = 1}, bottom = { x = 5, y = 7}},
1804             { top = { x = 5, y = 2}, bottom = { x = 5, y = 6}},
1805             { top = { x = 2, y = 4}, bottom = { x = 8, y = 5}}
1806         }
1807     },
1808     {
1809         name = "multi",
1810         desc = "Several segments with a common intersection point",
1811         edges = {
1812             { top = { x = 1, y = 2}, bottom = { x = 5, y = 4} },
1813             { top = { x = 1, y = 1}, bottom = { x = 5, y = 5} },
1814             { top = { x = 2, y = 1}, bottom = { x = 4, y = 5} },
1815             { top = { x = 4, y = 1}, bottom = { x = 2, y = 5} },
1816             { top = { x = 5, y = 1}, bottom = { x = 1, y = 5} },
1817             { top = { x = 5, y = 2}, bottom = { x = 1, y = 4} }
1818         }
1819     }
1820 };
1821 */
1822
1823 static int
1824 run_test (const char            *test_name,
1825           cairo_bo_edge_t       *test_edges,
1826           int                    num_edges)
1827 {
1828     int i, intersections, passes;
1829     cairo_bo_edge_t *edges;
1830     cairo_array_t intersected_edges;
1831
1832     printf ("Testing: %s\n", test_name);
1833
1834     _cairo_array_init (&intersected_edges, sizeof (cairo_bo_edge_t));
1835
1836     intersections = _cairo_bentley_ottmann_intersect_edges (test_edges, num_edges, &intersected_edges);
1837     if (intersections)
1838         printf ("Pass 1 found %d intersections:\n", intersections);
1839
1840
1841     /* XXX: Multi-pass Bentley-Ottmmann. Preferable would be to add a
1842      * pass of Hobby's tolerance-square algorithm instead. */
1843     passes = 1;
1844     while (intersections) {
1845         int num_edges = _cairo_array_num_elements (&intersected_edges);
1846         passes++;
1847         edges = _cairo_malloc_ab (num_edges, sizeof (cairo_bo_edge_t));
1848         assert (edges != NULL);
1849         memcpy (edges, _cairo_array_index (&intersected_edges, 0), num_edges * sizeof (cairo_bo_edge_t));
1850         _cairo_array_fini (&intersected_edges);
1851         _cairo_array_init (&intersected_edges, sizeof (cairo_bo_edge_t));
1852         intersections = _cairo_bentley_ottmann_intersect_edges (edges, num_edges, &intersected_edges);
1853         free (edges);
1854
1855         if (intersections){
1856             printf ("Pass %d found %d remaining intersections:\n", passes, intersections);
1857         } else {
1858             if (passes > 3)
1859                 for (i = 0; i < passes; i++)
1860                     printf ("*");
1861             printf ("No remainining intersections found after pass %d\n", passes);
1862         }
1863     }
1864
1865     if (edges_have_an_intersection_quadratic (_cairo_array_index (&intersected_edges, 0),
1866                                               _cairo_array_num_elements (&intersected_edges)))
1867         printf ("*** FAIL ***\n");
1868     else
1869         printf ("PASS\n");
1870
1871     _cairo_array_fini (&intersected_edges);
1872
1873     return 0;
1874 }
1875
1876 #define MAX_RANDOM 300
1877
1878 int
1879 main (void)
1880 {
1881     char random_name[] = "random-XX";
1882     cairo_bo_edge_t random_edges[MAX_RANDOM], *edge;
1883     unsigned int i, num_random;
1884     test_t *test;
1885
1886     for (i = 0; i < ARRAY_LENGTH (tests); i++) {
1887         test = &tests[i];
1888         run_test (test->name, test->edges, test->num_edges);
1889     }
1890
1891     for (num_random = 0; num_random < MAX_RANDOM; num_random++) {
1892         srand (0);
1893         for (i = 0; i < num_random; i++) {
1894             do {
1895                 edge = &random_edges[i];
1896                 edge->line.p1.x = (int32_t) (10.0 * (rand() / (RAND_MAX + 1.0)));
1897                 edge->line.p1.y = (int32_t) (10.0 * (rand() / (RAND_MAX + 1.0)));
1898                 edge->line.p2.x = (int32_t) (10.0 * (rand() / (RAND_MAX + 1.0)));
1899                 edge->line.p2.y = (int32_t) (10.0 * (rand() / (RAND_MAX + 1.0)));
1900                 if (edge->line.p1.y > edge->line.p2.y) {
1901                     int32_t tmp = edge->line.p1.y;
1902                     edge->line.p1.y = edge->line.p2.y;
1903                     edge->line.p2.y = tmp;
1904                 }
1905             } while (edge->line.p1.y == edge->line.p2.y);
1906         }
1907
1908         sprintf (random_name, "random-%02d", num_random);
1909
1910         run_test (random_name, random_edges, num_random);
1911     }
1912
1913     return 0;
1914 }
1915 #endif