Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | Download | RSS feed

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