Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | 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-inline.h"
  44.  
  45. #define DEBUG_POLYGON 0
  46.  
  47. typedef cairo_point_t cairo_bo_point32_t;
  48.  
  49. typedef struct _cairo_bo_intersect_ordinate {
  50.     int32_t ordinate;
  51.     enum { EXACT, INEXACT } exactness;
  52. } cairo_bo_intersect_ordinate_t;
  53.  
  54. typedef struct _cairo_bo_intersect_point {
  55.     cairo_bo_intersect_ordinate_t x;
  56.     cairo_bo_intersect_ordinate_t y;
  57. } cairo_bo_intersect_point_t;
  58.  
  59. typedef struct _cairo_bo_edge cairo_bo_edge_t;
  60.  
  61. typedef struct _cairo_bo_deferred {
  62.     cairo_bo_edge_t *right;
  63.     int32_t top;
  64. } cairo_bo_deferred_t;
  65.  
  66. struct _cairo_bo_edge {
  67.     cairo_edge_t edge;
  68.     cairo_bo_edge_t *prev;
  69.     cairo_bo_edge_t *next;
  70.     cairo_bo_deferred_t deferred;
  71. };
  72.  
  73. /* the parent is always given by index/2 */
  74. #define PQ_PARENT_INDEX(i) ((i) >> 1)
  75. #define PQ_FIRST_ENTRY 1
  76.  
  77. /* left and right children are index * 2 and (index * 2) +1 respectively */
  78. #define PQ_LEFT_CHILD_INDEX(i) ((i) << 1)
  79.  
  80. typedef enum {
  81.     CAIRO_BO_EVENT_TYPE_STOP,
  82.     CAIRO_BO_EVENT_TYPE_INTERSECTION,
  83.     CAIRO_BO_EVENT_TYPE_START
  84. } cairo_bo_event_type_t;
  85.  
  86. typedef struct _cairo_bo_event {
  87.     cairo_bo_event_type_t type;
  88.     cairo_point_t point;
  89. } cairo_bo_event_t;
  90.  
  91. typedef struct _cairo_bo_start_event {
  92.     cairo_bo_event_type_t type;
  93.     cairo_point_t point;
  94.     cairo_bo_edge_t edge;
  95. } cairo_bo_start_event_t;
  96.  
  97. typedef struct _cairo_bo_queue_event {
  98.     cairo_bo_event_type_t type;
  99.     cairo_point_t point;
  100.     cairo_bo_edge_t *e1;
  101.     cairo_bo_edge_t *e2;
  102. } cairo_bo_queue_event_t;
  103.  
  104. typedef struct _pqueue {
  105.     int size, max_size;
  106.  
  107.     cairo_bo_event_t **elements;
  108.     cairo_bo_event_t *elements_embedded[1024];
  109. } pqueue_t;
  110.  
  111. typedef struct _cairo_bo_event_queue {
  112.     cairo_freepool_t pool;
  113.     pqueue_t pqueue;
  114.     cairo_bo_event_t **start_events;
  115. } cairo_bo_event_queue_t;
  116.  
  117. typedef struct _cairo_bo_sweep_line {
  118.     cairo_bo_edge_t *head;
  119.     int32_t current_y;
  120.     cairo_bo_edge_t *current_edge;
  121. } cairo_bo_sweep_line_t;
  122.  
  123. static cairo_fixed_t
  124. _line_compute_intersection_x_for_y (const cairo_line_t *line,
  125.                                     cairo_fixed_t y)
  126. {
  127.     cairo_fixed_t x, dy;
  128.  
  129.     if (y == line->p1.y)
  130.         return line->p1.x;
  131.     if (y == line->p2.y)
  132.         return line->p2.x;
  133.  
  134.     x = line->p1.x;
  135.     dy = line->p2.y - line->p1.y;
  136.     if (dy != 0) {
  137.         x += _cairo_fixed_mul_div_floor (y - line->p1.y,
  138.                                          line->p2.x - line->p1.x,
  139.                                          dy);
  140.     }
  141.  
  142.     return x;
  143. }
  144.  
  145. static inline int
  146. _cairo_bo_point32_compare (cairo_bo_point32_t const *a,
  147.                            cairo_bo_point32_t const *b)
  148. {
  149.     int cmp;
  150.  
  151.     cmp = a->y - b->y;
  152.     if (cmp)
  153.         return cmp;
  154.  
  155.     return a->x - b->x;
  156. }
  157.  
  158. /* Compare the slope of a to the slope of b, returning 1, 0, -1 if the
  159.  * slope a is respectively greater than, equal to, or less than the
  160.  * slope of b.
  161.  *
  162.  * For each edge, consider the direction vector formed from:
  163.  *
  164.  *      top -> bottom
  165.  *
  166.  * which is:
  167.  *
  168.  *      (dx, dy) = (line.p2.x - line.p1.x, line.p2.y - line.p1.y)
  169.  *
  170.  * We then define the slope of each edge as dx/dy, (which is the
  171.  * inverse of the slope typically used in math instruction). We never
  172.  * compute a slope directly as the value approaches infinity, but we
  173.  * can derive a slope comparison without division as follows, (where
  174.  * the ? represents our compare operator).
  175.  *
  176.  * 1.      slope(a) ? slope(b)
  177.  * 2.       adx/ady ? bdx/bdy
  178.  * 3.   (adx * bdy) ? (bdx * ady)
  179.  *
  180.  * Note that from step 2 to step 3 there is no change needed in the
  181.  * sign of the result since both ady and bdy are guaranteed to be
  182.  * greater than or equal to 0.
  183.  *
  184.  * When using this slope comparison to sort edges, some care is needed
  185.  * when interpreting the results. Since the slope compare operates on
  186.  * distance vectors from top to bottom it gives a correct left to
  187.  * right sort for edges that have a common top point, (such as two
  188.  * edges with start events at the same location). On the other hand,
  189.  * the sense of the result will be exactly reversed for two edges that
  190.  * have a common stop point.
  191.  */
  192. static inline int
  193. _slope_compare (const cairo_bo_edge_t *a,
  194.                 const cairo_bo_edge_t *b)
  195. {
  196.     /* XXX: We're assuming here that dx and dy will still fit in 32
  197.      * bits. That's not true in general as there could be overflow. We
  198.      * should prevent that before the tessellation algorithm
  199.      * begins.
  200.      */
  201.     int32_t adx = a->edge.line.p2.x - a->edge.line.p1.x;
  202.     int32_t bdx = b->edge.line.p2.x - b->edge.line.p1.x;
  203.  
  204.     /* Since the dy's are all positive by construction we can fast
  205.      * path several common cases.
  206.      */
  207.  
  208.     /* First check for vertical lines. */
  209.     if (adx == 0)
  210.         return -bdx;
  211.     if (bdx == 0)
  212.         return adx;
  213.  
  214.     /* Then where the two edges point in different directions wrt x. */
  215.     if ((adx ^ bdx) < 0)
  216.         return adx;
  217.  
  218.     /* Finally we actually need to do the general comparison. */
  219.     {
  220.         int32_t ady = a->edge.line.p2.y - a->edge.line.p1.y;
  221.         int32_t bdy = b->edge.line.p2.y - b->edge.line.p1.y;
  222.         cairo_int64_t adx_bdy = _cairo_int32x32_64_mul (adx, bdy);
  223.         cairo_int64_t bdx_ady = _cairo_int32x32_64_mul (bdx, ady);
  224.  
  225.         return _cairo_int64_cmp (adx_bdy, bdx_ady);
  226.     }
  227. }
  228.  
  229. /*
  230.  * We need to compare the x-coordinates of a pair of lines for a particular y,
  231.  * without loss of precision.
  232.  *
  233.  * The x-coordinate along an edge for a given y is:
  234.  *   X = A_x + (Y - A_y) * A_dx / A_dy
  235.  *
  236.  * So the inequality we wish to test is:
  237.  *   A_x + (Y - A_y) * A_dx / A_dy ∘ B_x + (Y - B_y) * B_dx / B_dy,
  238.  * where ∘ is our inequality operator.
  239.  *
  240.  * By construction, we know that A_dy and B_dy (and (Y - A_y), (Y - B_y)) are
  241.  * all positive, so we can rearrange it thus without causing a sign change:
  242.  *   A_dy * B_dy * (A_x - B_x) ∘ (Y - B_y) * B_dx * A_dy
  243.  *                                 - (Y - A_y) * A_dx * B_dy
  244.  *
  245.  * Given the assumption that all the deltas fit within 32 bits, we can compute
  246.  * this comparison directly using 128 bit arithmetic. For certain, but common,
  247.  * input we can reduce this down to a single 32 bit compare by inspecting the
  248.  * deltas.
  249.  *
  250.  * (And put the burden of the work on developing fast 128 bit ops, which are
  251.  * required throughout the tessellator.)
  252.  *
  253.  * See the similar discussion for _slope_compare().
  254.  */
  255. static int
  256. edges_compare_x_for_y_general (const cairo_bo_edge_t *a,
  257.                                const cairo_bo_edge_t *b,
  258.                                int32_t y)
  259. {
  260.     /* XXX: We're assuming here that dx and dy will still fit in 32
  261.      * bits. That's not true in general as there could be overflow. We
  262.      * should prevent that before the tessellation algorithm
  263.      * begins.
  264.      */
  265.     int32_t dx;
  266.     int32_t adx, ady;
  267.     int32_t bdx, bdy;
  268.     enum {
  269.        HAVE_NONE    = 0x0,
  270.        HAVE_DX      = 0x1,
  271.        HAVE_ADX     = 0x2,
  272.        HAVE_DX_ADX  = HAVE_DX | HAVE_ADX,
  273.        HAVE_BDX     = 0x4,
  274.        HAVE_DX_BDX  = HAVE_DX | HAVE_BDX,
  275.        HAVE_ADX_BDX = HAVE_ADX | HAVE_BDX,
  276.        HAVE_ALL     = HAVE_DX | HAVE_ADX | HAVE_BDX
  277.     } have_dx_adx_bdx = HAVE_ALL;
  278.  
  279.     /* don't bother solving for abscissa if the edges' bounding boxes
  280.      * can be used to order them. */
  281.     {
  282.            int32_t amin, amax;
  283.            int32_t bmin, bmax;
  284.            if (a->edge.line.p1.x < a->edge.line.p2.x) {
  285.                    amin = a->edge.line.p1.x;
  286.                    amax = a->edge.line.p2.x;
  287.            } else {
  288.                    amin = a->edge.line.p2.x;
  289.                    amax = a->edge.line.p1.x;
  290.            }
  291.            if (b->edge.line.p1.x < b->edge.line.p2.x) {
  292.                    bmin = b->edge.line.p1.x;
  293.                    bmax = b->edge.line.p2.x;
  294.            } else {
  295.                    bmin = b->edge.line.p2.x;
  296.                    bmax = b->edge.line.p1.x;
  297.            }
  298.            if (amax < bmin) return -1;
  299.            if (amin > bmax) return +1;
  300.     }
  301.  
  302.     ady = a->edge.line.p2.y - a->edge.line.p1.y;
  303.     adx = a->edge.line.p2.x - a->edge.line.p1.x;
  304.     if (adx == 0)
  305.         have_dx_adx_bdx &= ~HAVE_ADX;
  306.  
  307.     bdy = b->edge.line.p2.y - b->edge.line.p1.y;
  308.     bdx = b->edge.line.p2.x - b->edge.line.p1.x;
  309.     if (bdx == 0)
  310.         have_dx_adx_bdx &= ~HAVE_BDX;
  311.  
  312.     dx = a->edge.line.p1.x - b->edge.line.p1.x;
  313.     if (dx == 0)
  314.         have_dx_adx_bdx &= ~HAVE_DX;
  315.  
  316. #define L _cairo_int64x32_128_mul (_cairo_int32x32_64_mul (ady, bdy), dx)
  317. #define A _cairo_int64x32_128_mul (_cairo_int32x32_64_mul (adx, bdy), y - a->edge.line.p1.y)
  318. #define B _cairo_int64x32_128_mul (_cairo_int32x32_64_mul (bdx, ady), y - b->edge.line.p1.y)
  319.     switch (have_dx_adx_bdx) {
  320.     default:
  321.     case HAVE_NONE:
  322.         return 0;
  323.     case HAVE_DX:
  324.         /* A_dy * B_dy * (A_x - B_x) ∘ 0 */
  325.         return dx; /* ady * bdy is positive definite */
  326.     case HAVE_ADX:
  327.         /* 0 ∘  - (Y - A_y) * A_dx * B_dy */
  328.         return adx; /* bdy * (y - a->top.y) is positive definite */
  329.     case HAVE_BDX:
  330.         /* 0 ∘ (Y - B_y) * B_dx * A_dy */
  331.         return -bdx; /* ady * (y - b->top.y) is positive definite */
  332.     case HAVE_ADX_BDX:
  333.         /*  0 ∘ (Y - B_y) * B_dx * A_dy - (Y - A_y) * A_dx * B_dy */
  334.         if ((adx ^ bdx) < 0) {
  335.             return adx;
  336.         } else if (a->edge.line.p1.y == b->edge.line.p1.y) { /* common origin */
  337.             cairo_int64_t adx_bdy, bdx_ady;
  338.  
  339.             /* ∴ A_dx * B_dy ∘ B_dx * A_dy */
  340.  
  341.             adx_bdy = _cairo_int32x32_64_mul (adx, bdy);
  342.             bdx_ady = _cairo_int32x32_64_mul (bdx, ady);
  343.  
  344.             return _cairo_int64_cmp (adx_bdy, bdx_ady);
  345.         } else
  346.             return _cairo_int128_cmp (A, B);
  347.     case HAVE_DX_ADX:
  348.         /* A_dy * (A_x - B_x) ∘ - (Y - A_y) * A_dx */
  349.         if ((-adx ^ dx) < 0) {
  350.             return dx;
  351.         } else {
  352.             cairo_int64_t ady_dx, dy_adx;
  353.  
  354.             ady_dx = _cairo_int32x32_64_mul (ady, dx);
  355.             dy_adx = _cairo_int32x32_64_mul (a->edge.line.p1.y - y, adx);
  356.  
  357.             return _cairo_int64_cmp (ady_dx, dy_adx);
  358.         }
  359.     case HAVE_DX_BDX:
  360.         /* B_dy * (A_x - B_x) ∘ (Y - B_y) * B_dx */
  361.         if ((bdx ^ dx) < 0) {
  362.             return dx;
  363.         } else {
  364.             cairo_int64_t bdy_dx, dy_bdx;
  365.  
  366.             bdy_dx = _cairo_int32x32_64_mul (bdy, dx);
  367.             dy_bdx = _cairo_int32x32_64_mul (y - b->edge.line.p1.y, bdx);
  368.  
  369.             return _cairo_int64_cmp (bdy_dx, dy_bdx);
  370.         }
  371.     case HAVE_ALL:
  372.         /* XXX try comparing (a->edge.line.p2.x - b->edge.line.p2.x) et al */
  373.         return _cairo_int128_cmp (L, _cairo_int128_sub (B, A));
  374.     }
  375. #undef B
  376. #undef A
  377. #undef L
  378. }
  379.  
  380. /*
  381.  * We need to compare the x-coordinate of a line for a particular y wrt to a
  382.  * given x, without loss of precision.
  383.  *
  384.  * The x-coordinate along an edge for a given y is:
  385.  *   X = A_x + (Y - A_y) * A_dx / A_dy
  386.  *
  387.  * So the inequality we wish to test is:
  388.  *   A_x + (Y - A_y) * A_dx / A_dy ∘ X
  389.  * where ∘ is our inequality operator.
  390.  *
  391.  * By construction, we know that A_dy (and (Y - A_y)) are
  392.  * all positive, so we can rearrange it thus without causing a sign change:
  393.  *   (Y - A_y) * A_dx ∘ (X - A_x) * A_dy
  394.  *
  395.  * Given the assumption that all the deltas fit within 32 bits, we can compute
  396.  * this comparison directly using 64 bit arithmetic.
  397.  *
  398.  * See the similar discussion for _slope_compare() and
  399.  * edges_compare_x_for_y_general().
  400.  */
  401. static int
  402. edge_compare_for_y_against_x (const cairo_bo_edge_t *a,
  403.                               int32_t y,
  404.                               int32_t x)
  405. {
  406.     int32_t adx, ady;
  407.     int32_t dx, dy;
  408.     cairo_int64_t L, R;
  409.  
  410.     if (x < a->edge.line.p1.x && x < a->edge.line.p2.x)
  411.         return 1;
  412.     if (x > a->edge.line.p1.x && x > a->edge.line.p2.x)
  413.         return -1;
  414.  
  415.     adx = a->edge.line.p2.x - a->edge.line.p1.x;
  416.     dx = x - a->edge.line.p1.x;
  417.  
  418.     if (adx == 0)
  419.         return -dx;
  420.     if (dx == 0 || (adx ^ dx) < 0)
  421.         return adx;
  422.  
  423.     dy = y - a->edge.line.p1.y;
  424.     ady = a->edge.line.p2.y - a->edge.line.p1.y;
  425.  
  426.     L = _cairo_int32x32_64_mul (dy, adx);
  427.     R = _cairo_int32x32_64_mul (dx, ady);
  428.  
  429.     return _cairo_int64_cmp (L, R);
  430. }
  431.  
  432. static int
  433. edges_compare_x_for_y (const cairo_bo_edge_t *a,
  434.                        const cairo_bo_edge_t *b,
  435.                        int32_t y)
  436. {
  437.     /* If the sweep-line is currently on an end-point of a line,
  438.      * then we know its precise x value (and considering that we often need to
  439.      * compare events at end-points, this happens frequently enough to warrant
  440.      * special casing).
  441.      */
  442.     enum {
  443.        HAVE_NEITHER = 0x0,
  444.        HAVE_AX      = 0x1,
  445.        HAVE_BX      = 0x2,
  446.        HAVE_BOTH    = HAVE_AX | HAVE_BX
  447.     } have_ax_bx = HAVE_BOTH;
  448.     int32_t ax, bx;
  449.  
  450.     if (y == a->edge.line.p1.y)
  451.         ax = a->edge.line.p1.x;
  452.     else if (y == a->edge.line.p2.y)
  453.         ax = a->edge.line.p2.x;
  454.     else
  455.         have_ax_bx &= ~HAVE_AX;
  456.  
  457.     if (y == b->edge.line.p1.y)
  458.         bx = b->edge.line.p1.x;
  459.     else if (y == b->edge.line.p2.y)
  460.         bx = b->edge.line.p2.x;
  461.     else
  462.         have_ax_bx &= ~HAVE_BX;
  463.  
  464.     switch (have_ax_bx) {
  465.     default:
  466.     case HAVE_NEITHER:
  467.         return edges_compare_x_for_y_general (a, b, y);
  468.     case HAVE_AX:
  469.         return -edge_compare_for_y_against_x (b, y, ax);
  470.     case HAVE_BX:
  471.         return edge_compare_for_y_against_x (a, y, bx);
  472.     case HAVE_BOTH:
  473.         return ax - bx;
  474.     }
  475. }
  476.  
  477. static inline int
  478. _line_equal (const cairo_line_t *a, const cairo_line_t *b)
  479. {
  480.     return (a->p1.x == b->p1.x && a->p1.y == b->p1.y &&
  481.             a->p2.x == b->p2.x && a->p2.y == b->p2.y);
  482. }
  483.  
  484. static int
  485. _cairo_bo_sweep_line_compare_edges (cairo_bo_sweep_line_t       *sweep_line,
  486.                                     const cairo_bo_edge_t       *a,
  487.                                     const cairo_bo_edge_t       *b)
  488. {
  489.     int cmp;
  490.  
  491.     /* compare the edges if not identical */
  492.     if (! _line_equal (&a->edge.line, &b->edge.line)) {
  493.         cmp = edges_compare_x_for_y (a, b, sweep_line->current_y);
  494.         if (cmp)
  495.             return cmp;
  496.  
  497.         /* The two edges intersect exactly at y, so fall back on slope
  498.          * comparison. We know that this compare_edges function will be
  499.          * called only when starting a new edge, (not when stopping an
  500.          * edge), so we don't have to worry about conditionally inverting
  501.          * the sense of _slope_compare. */
  502.         cmp = _slope_compare (a, b);
  503.         if (cmp)
  504.             return cmp;
  505.     }
  506.  
  507.     /* We've got two collinear edges now. */
  508.     return b->edge.bottom - a->edge.bottom;
  509. }
  510.  
  511. static inline cairo_int64_t
  512. det32_64 (int32_t a, int32_t b,
  513.           int32_t c, int32_t d)
  514. {
  515.     /* det = a * d - b * c */
  516.     return _cairo_int64_sub (_cairo_int32x32_64_mul (a, d),
  517.                              _cairo_int32x32_64_mul (b, c));
  518. }
  519.  
  520. static inline cairo_int128_t
  521. det64x32_128 (cairo_int64_t a, int32_t       b,
  522.               cairo_int64_t c, int32_t       d)
  523. {
  524.     /* det = a * d - b * c */
  525.     return _cairo_int128_sub (_cairo_int64x32_128_mul (a, d),
  526.                               _cairo_int64x32_128_mul (c, b));
  527. }
  528.  
  529. /* Compute the intersection of two lines as defined by two edges. The
  530.  * result is provided as a coordinate pair of 128-bit integers.
  531.  *
  532.  * Returns %CAIRO_BO_STATUS_INTERSECTION if there is an intersection or
  533.  * %CAIRO_BO_STATUS_PARALLEL if the two lines are exactly parallel.
  534.  */
  535. static cairo_bool_t
  536. intersect_lines (cairo_bo_edge_t                *a,
  537.                  cairo_bo_edge_t                *b,
  538.                  cairo_bo_intersect_point_t     *intersection)
  539. {
  540.     cairo_int64_t a_det, b_det;
  541.  
  542.     /* XXX: We're assuming here that dx and dy will still fit in 32
  543.      * bits. That's not true in general as there could be overflow. We
  544.      * should prevent that before the tessellation algorithm begins.
  545.      * What we're doing to mitigate this is to perform clamping in
  546.      * cairo_bo_tessellate_polygon().
  547.      */
  548.     int32_t dx1 = a->edge.line.p1.x - a->edge.line.p2.x;
  549.     int32_t dy1 = a->edge.line.p1.y - a->edge.line.p2.y;
  550.  
  551.     int32_t dx2 = b->edge.line.p1.x - b->edge.line.p2.x;
  552.     int32_t dy2 = b->edge.line.p1.y - b->edge.line.p2.y;
  553.  
  554.     cairo_int64_t den_det;
  555.     cairo_int64_t R;
  556.     cairo_quorem64_t qr;
  557.  
  558.     den_det = det32_64 (dx1, dy1, dx2, dy2);
  559.  
  560.      /* Q: Can we determine that the lines do not intersect (within range)
  561.       * much more cheaply than computing the intersection point i.e. by
  562.       * avoiding the division?
  563.       *
  564.       *   X = ax + t * adx = bx + s * bdx;
  565.       *   Y = ay + t * ady = by + s * bdy;
  566.       *   ∴ t * (ady*bdx - bdy*adx) = bdx * (by - ay) + bdy * (ax - bx)
  567.       *   => t * L = R
  568.       *
  569.       * Therefore we can reject any intersection (under the criteria for
  570.       * valid intersection events) if:
  571.       *   L^R < 0 => t < 0, or
  572.       *   L<R => t > 1
  573.       *
  574.       * (where top/bottom must at least extend to the line endpoints).
  575.       *
  576.       * A similar substitution can be performed for s, yielding:
  577.       *   s * (ady*bdx - bdy*adx) = ady * (ax - bx) - adx * (ay - by)
  578.       */
  579.     R = det32_64 (dx2, dy2,
  580.                   b->edge.line.p1.x - a->edge.line.p1.x,
  581.                   b->edge.line.p1.y - a->edge.line.p1.y);
  582.     if (_cairo_int64_negative (den_det)) {
  583.         if (_cairo_int64_ge (den_det, R))
  584.             return FALSE;
  585.     } else {
  586.         if (_cairo_int64_le (den_det, R))
  587.             return FALSE;
  588.     }
  589.  
  590.     R = det32_64 (dy1, dx1,
  591.                   a->edge.line.p1.y - b->edge.line.p1.y,
  592.                   a->edge.line.p1.x - b->edge.line.p1.x);
  593.     if (_cairo_int64_negative (den_det)) {
  594.         if (_cairo_int64_ge (den_det, R))
  595.             return FALSE;
  596.     } else {
  597.         if (_cairo_int64_le (den_det, R))
  598.             return FALSE;
  599.     }
  600.  
  601.     /* We now know that the two lines should intersect within range. */
  602.  
  603.     a_det = det32_64 (a->edge.line.p1.x, a->edge.line.p1.y,
  604.                       a->edge.line.p2.x, a->edge.line.p2.y);
  605.     b_det = det32_64 (b->edge.line.p1.x, b->edge.line.p1.y,
  606.                       b->edge.line.p2.x, b->edge.line.p2.y);
  607.  
  608.     /* x = det (a_det, dx1, b_det, dx2) / den_det */
  609.     qr = _cairo_int_96by64_32x64_divrem (det64x32_128 (a_det, dx1,
  610.                                                        b_det, dx2),
  611.                                          den_det);
  612.     if (_cairo_int64_eq (qr.rem, den_det))
  613.         return FALSE;
  614. #if 0
  615.     intersection->x.exactness = _cairo_int64_is_zero (qr.rem) ? EXACT : INEXACT;
  616. #else
  617.     intersection->x.exactness = EXACT;
  618.     if (! _cairo_int64_is_zero (qr.rem)) {
  619.         if (_cairo_int64_negative (den_det) ^ _cairo_int64_negative (qr.rem))
  620.             qr.rem = _cairo_int64_negate (qr.rem);
  621.         qr.rem = _cairo_int64_mul (qr.rem, _cairo_int32_to_int64 (2));
  622.         if (_cairo_int64_ge (qr.rem, den_det)) {
  623.             qr.quo = _cairo_int64_add (qr.quo,
  624.                                        _cairo_int32_to_int64 (_cairo_int64_negative (qr.quo) ? -1 : 1));
  625.         } else
  626.             intersection->x.exactness = INEXACT;
  627.     }
  628. #endif
  629.     intersection->x.ordinate = _cairo_int64_to_int32 (qr.quo);
  630.  
  631.     /* y = det (a_det, dy1, b_det, dy2) / den_det */
  632.     qr = _cairo_int_96by64_32x64_divrem (det64x32_128 (a_det, dy1,
  633.                                                        b_det, dy2),
  634.                                          den_det);
  635.     if (_cairo_int64_eq (qr.rem, den_det))
  636.         return FALSE;
  637. #if 0
  638.     intersection->y.exactness = _cairo_int64_is_zero (qr.rem) ? EXACT : INEXACT;
  639. #else
  640.     intersection->y.exactness = EXACT;
  641.     if (! _cairo_int64_is_zero (qr.rem)) {
  642.         if (_cairo_int64_negative (den_det) ^ _cairo_int64_negative (qr.rem))
  643.             qr.rem = _cairo_int64_negate (qr.rem);
  644.         qr.rem = _cairo_int64_mul (qr.rem, _cairo_int32_to_int64 (2));
  645.         if (_cairo_int64_ge (qr.rem, den_det)) {
  646.             qr.quo = _cairo_int64_add (qr.quo,
  647.                                        _cairo_int32_to_int64 (_cairo_int64_negative (qr.quo) ? -1 : 1));
  648.         } else
  649.             intersection->y.exactness = INEXACT;
  650.     }
  651. #endif
  652.     intersection->y.ordinate = _cairo_int64_to_int32 (qr.quo);
  653.  
  654.     return TRUE;
  655. }
  656.  
  657. static int
  658. _cairo_bo_intersect_ordinate_32_compare (cairo_bo_intersect_ordinate_t  a,
  659.                                          int32_t                        b)
  660. {
  661.     /* First compare the quotient */
  662.     if (a.ordinate > b)
  663.         return +1;
  664.     if (a.ordinate < b)
  665.         return -1;
  666.     /* With quotient identical, if remainder is 0 then compare equal */
  667.     /* Otherwise, the non-zero remainder makes a > b */
  668.     return INEXACT == a.exactness;
  669. }
  670.  
  671. /* Does the given edge contain the given point. The point must already
  672.  * be known to be contained within the line determined by the edge,
  673.  * (most likely the point results from an intersection of this edge
  674.  * with another).
  675.  *
  676.  * If we had exact arithmetic, then this function would simply be a
  677.  * matter of examining whether the y value of the point lies within
  678.  * the range of y values of the edge. But since intersection points
  679.  * are not exact due to being rounded to the nearest integer within
  680.  * the available precision, we must also examine the x value of the
  681.  * point.
  682.  *
  683.  * The definition of "contains" here is that the given intersection
  684.  * point will be seen by the sweep line after the start event for the
  685.  * given edge and before the stop event for the edge. See the comments
  686.  * in the implementation for more details.
  687.  */
  688. static cairo_bool_t
  689. _cairo_bo_edge_contains_intersect_point (cairo_bo_edge_t                *edge,
  690.                                          cairo_bo_intersect_point_t     *point)
  691. {
  692.     int cmp_top, cmp_bottom;
  693.  
  694.     /* XXX: When running the actual algorithm, we don't actually need to
  695.      * compare against edge->top at all here, since any intersection above
  696.      * top is eliminated early via a slope comparison. We're leaving these
  697.      * here for now only for the sake of the quadratic-time intersection
  698.      * finder which needs them.
  699.      */
  700.  
  701.     cmp_top = _cairo_bo_intersect_ordinate_32_compare (point->y,
  702.                                                        edge->edge.top);
  703.     cmp_bottom = _cairo_bo_intersect_ordinate_32_compare (point->y,
  704.                                                           edge->edge.bottom);
  705.  
  706.     if (cmp_top < 0 || cmp_bottom > 0)
  707.     {
  708.         return FALSE;
  709.     }
  710.  
  711.     if (cmp_top > 0 && cmp_bottom < 0)
  712.     {
  713.         return TRUE;
  714.     }
  715.  
  716.     /* At this stage, the point lies on the same y value as either
  717.      * edge->top or edge->bottom, so we have to examine the x value in
  718.      * order to properly determine containment. */
  719.  
  720.     /* If the y value of the point is the same as the y value of the
  721.      * top of the edge, then the x value of the point must be greater
  722.      * to be considered as inside the edge. Similarly, if the y value
  723.      * of the point is the same as the y value of the bottom of the
  724.      * edge, then the x value of the point must be less to be
  725.      * considered as inside. */
  726.  
  727.     if (cmp_top == 0) {
  728.         cairo_fixed_t top_x;
  729.  
  730.         top_x = _line_compute_intersection_x_for_y (&edge->edge.line,
  731.                                                     edge->edge.top);
  732.         return _cairo_bo_intersect_ordinate_32_compare (point->x, top_x) > 0;
  733.     } else { /* cmp_bottom == 0 */
  734.         cairo_fixed_t bot_x;
  735.  
  736.         bot_x = _line_compute_intersection_x_for_y (&edge->edge.line,
  737.                                                     edge->edge.bottom);
  738.         return _cairo_bo_intersect_ordinate_32_compare (point->x, bot_x) < 0;
  739.     }
  740. }
  741.  
  742. /* Compute the intersection of two edges. The result is provided as a
  743.  * coordinate pair of 128-bit integers.
  744.  *
  745.  * Returns %CAIRO_BO_STATUS_INTERSECTION if there is an intersection
  746.  * that is within both edges, %CAIRO_BO_STATUS_NO_INTERSECTION if the
  747.  * intersection of the lines defined by the edges occurs outside of
  748.  * one or both edges, and %CAIRO_BO_STATUS_PARALLEL if the two edges
  749.  * are exactly parallel.
  750.  *
  751.  * Note that when determining if a candidate intersection is "inside"
  752.  * an edge, we consider both the infinitesimal shortening and the
  753.  * infinitesimal tilt rules described by John Hobby. Specifically, if
  754.  * the intersection is exactly the same as an edge point, it is
  755.  * effectively outside (no intersection is returned). Also, if the
  756.  * intersection point has the same
  757.  */
  758. static cairo_bool_t
  759. _cairo_bo_edge_intersect (cairo_bo_edge_t       *a,
  760.                           cairo_bo_edge_t       *b,
  761.                           cairo_bo_point32_t    *intersection)
  762. {
  763.     cairo_bo_intersect_point_t quorem;
  764.  
  765.     if (! intersect_lines (a, b, &quorem))
  766.         return FALSE;
  767.  
  768.     if (! _cairo_bo_edge_contains_intersect_point (a, &quorem))
  769.         return FALSE;
  770.  
  771.     if (! _cairo_bo_edge_contains_intersect_point (b, &quorem))
  772.         return FALSE;
  773.  
  774.     /* Now that we've correctly compared the intersection point and
  775.      * determined that it lies within the edge, then we know that we
  776.      * no longer need any more bits of storage for the intersection
  777.      * than we do for our edge coordinates. We also no longer need the
  778.      * remainder from the division. */
  779.     intersection->x = quorem.x.ordinate;
  780.     intersection->y = quorem.y.ordinate;
  781.  
  782.     return TRUE;
  783. }
  784.  
  785. static inline int
  786. cairo_bo_event_compare (const cairo_bo_event_t *a,
  787.                         const cairo_bo_event_t *b)
  788. {
  789.     int cmp;
  790.  
  791.     cmp = _cairo_bo_point32_compare (&a->point, &b->point);
  792.     if (cmp)
  793.         return cmp;
  794.  
  795.     cmp = a->type - b->type;
  796.     if (cmp)
  797.         return cmp;
  798.  
  799.     return a - b;
  800. }
  801.  
  802. static inline void
  803. _pqueue_init (pqueue_t *pq)
  804. {
  805.     pq->max_size = ARRAY_LENGTH (pq->elements_embedded);
  806.     pq->size = 0;
  807.  
  808.     pq->elements = pq->elements_embedded;
  809. }
  810.  
  811. static inline void
  812. _pqueue_fini (pqueue_t *pq)
  813. {
  814.     if (pq->elements != pq->elements_embedded)
  815.         free (pq->elements);
  816. }
  817.  
  818. static cairo_status_t
  819. _pqueue_grow (pqueue_t *pq)
  820. {
  821.     cairo_bo_event_t **new_elements;
  822.     pq->max_size *= 2;
  823.  
  824.     if (pq->elements == pq->elements_embedded) {
  825.         new_elements = _cairo_malloc_ab (pq->max_size,
  826.                                          sizeof (cairo_bo_event_t *));
  827.         if (unlikely (new_elements == NULL))
  828.             return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  829.  
  830.         memcpy (new_elements, pq->elements_embedded,
  831.                 sizeof (pq->elements_embedded));
  832.     } else {
  833.         new_elements = _cairo_realloc_ab (pq->elements,
  834.                                           pq->max_size,
  835.                                           sizeof (cairo_bo_event_t *));
  836.         if (unlikely (new_elements == NULL))
  837.             return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  838.     }
  839.  
  840.     pq->elements = new_elements;
  841.     return CAIRO_STATUS_SUCCESS;
  842. }
  843.  
  844. static inline cairo_status_t
  845. _pqueue_push (pqueue_t *pq, cairo_bo_event_t *event)
  846. {
  847.     cairo_bo_event_t **elements;
  848.     int i, parent;
  849.  
  850.     if (unlikely (pq->size + 1 == pq->max_size)) {
  851.         cairo_status_t status;
  852.  
  853.         status = _pqueue_grow (pq);
  854.         if (unlikely (status))
  855.             return status;
  856.     }
  857.  
  858.     elements = pq->elements;
  859.  
  860.     for (i = ++pq->size;
  861.          i != PQ_FIRST_ENTRY &&
  862.          cairo_bo_event_compare (event,
  863.                                  elements[parent = PQ_PARENT_INDEX (i)]) < 0;
  864.          i = parent)
  865.     {
  866.         elements[i] = elements[parent];
  867.     }
  868.  
  869.     elements[i] = event;
  870.  
  871.     return CAIRO_STATUS_SUCCESS;
  872. }
  873.  
  874. static inline void
  875. _pqueue_pop (pqueue_t *pq)
  876. {
  877.     cairo_bo_event_t **elements = pq->elements;
  878.     cairo_bo_event_t *tail;
  879.     int child, i;
  880.  
  881.     tail = elements[pq->size--];
  882.     if (pq->size == 0) {
  883.         elements[PQ_FIRST_ENTRY] = NULL;
  884.         return;
  885.     }
  886.  
  887.     for (i = PQ_FIRST_ENTRY;
  888.          (child = PQ_LEFT_CHILD_INDEX (i)) <= pq->size;
  889.          i = child)
  890.     {
  891.         if (child != pq->size &&
  892.             cairo_bo_event_compare (elements[child+1],
  893.                                     elements[child]) < 0)
  894.         {
  895.             child++;
  896.         }
  897.  
  898.         if (cairo_bo_event_compare (elements[child], tail) >= 0)
  899.             break;
  900.  
  901.         elements[i] = elements[child];
  902.     }
  903.     elements[i] = tail;
  904. }
  905.  
  906. static inline cairo_status_t
  907. _cairo_bo_event_queue_insert (cairo_bo_event_queue_t    *queue,
  908.                               cairo_bo_event_type_t      type,
  909.                               cairo_bo_edge_t           *e1,
  910.                               cairo_bo_edge_t           *e2,
  911.                               const cairo_point_t        *point)
  912. {
  913.     cairo_bo_queue_event_t *event;
  914.  
  915.     event = _cairo_freepool_alloc (&queue->pool);
  916.     if (unlikely (event == NULL))
  917.         return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  918.  
  919.     event->type = type;
  920.     event->e1 = e1;
  921.     event->e2 = e2;
  922.     event->point = *point;
  923.  
  924.     return _pqueue_push (&queue->pqueue, (cairo_bo_event_t *) event);
  925. }
  926.  
  927. static void
  928. _cairo_bo_event_queue_delete (cairo_bo_event_queue_t *queue,
  929.                               cairo_bo_event_t       *event)
  930. {
  931.     _cairo_freepool_free (&queue->pool, event);
  932. }
  933.  
  934. static cairo_bo_event_t *
  935. _cairo_bo_event_dequeue (cairo_bo_event_queue_t *event_queue)
  936. {
  937.     cairo_bo_event_t *event, *cmp;
  938.  
  939.     event = event_queue->pqueue.elements[PQ_FIRST_ENTRY];
  940.     cmp = *event_queue->start_events;
  941.     if (event == NULL ||
  942.         (cmp != NULL && cairo_bo_event_compare (cmp, event) < 0))
  943.     {
  944.         event = cmp;
  945.         event_queue->start_events++;
  946.     }
  947.     else
  948.     {
  949.         _pqueue_pop (&event_queue->pqueue);
  950.     }
  951.  
  952.     return event;
  953. }
  954.  
  955. CAIRO_COMBSORT_DECLARE (_cairo_bo_event_queue_sort,
  956.                         cairo_bo_event_t *,
  957.                         cairo_bo_event_compare)
  958.  
  959. static void
  960. _cairo_bo_event_queue_init (cairo_bo_event_queue_t       *event_queue,
  961.                             cairo_bo_event_t            **start_events,
  962.                             int                           num_events)
  963. {
  964.     _cairo_bo_event_queue_sort (start_events, num_events);
  965.     start_events[num_events] = NULL;
  966.  
  967.     event_queue->start_events = start_events;
  968.  
  969.     _cairo_freepool_init (&event_queue->pool,
  970.                           sizeof (cairo_bo_queue_event_t));
  971.     _pqueue_init (&event_queue->pqueue);
  972.     event_queue->pqueue.elements[PQ_FIRST_ENTRY] = NULL;
  973. }
  974.  
  975. static cairo_status_t
  976. _cairo_bo_event_queue_insert_stop (cairo_bo_event_queue_t       *event_queue,
  977.                                    cairo_bo_edge_t              *edge)
  978. {
  979.     cairo_bo_point32_t point;
  980.  
  981.     point.y = edge->edge.bottom;
  982.     point.x = _line_compute_intersection_x_for_y (&edge->edge.line,
  983.                                                   point.y);
  984.     return _cairo_bo_event_queue_insert (event_queue,
  985.                                          CAIRO_BO_EVENT_TYPE_STOP,
  986.                                          edge, NULL,
  987.                                          &point);
  988. }
  989.  
  990. static void
  991. _cairo_bo_event_queue_fini (cairo_bo_event_queue_t *event_queue)
  992. {
  993.     _pqueue_fini (&event_queue->pqueue);
  994.     _cairo_freepool_fini (&event_queue->pool);
  995. }
  996.  
  997. static inline cairo_status_t
  998. _cairo_bo_event_queue_insert_if_intersect_below_current_y (cairo_bo_event_queue_t       *event_queue,
  999.                                                            cairo_bo_edge_t      *left,
  1000.                                                            cairo_bo_edge_t *right)
  1001. {
  1002.     cairo_bo_point32_t intersection;
  1003.  
  1004.     if (_line_equal (&left->edge.line, &right->edge.line))
  1005.         return CAIRO_STATUS_SUCCESS;
  1006.  
  1007.     /* The names "left" and "right" here are correct descriptions of
  1008.      * the order of the two edges within the active edge list. So if a
  1009.      * slope comparison also puts left less than right, then we know
  1010.      * that the intersection of these two segments has already
  1011.      * occurred before the current sweep line position. */
  1012.     if (_slope_compare (left, right) <= 0)
  1013.         return CAIRO_STATUS_SUCCESS;
  1014.  
  1015.     if (! _cairo_bo_edge_intersect (left, right, &intersection))
  1016.         return CAIRO_STATUS_SUCCESS;
  1017.  
  1018.     return _cairo_bo_event_queue_insert (event_queue,
  1019.                                          CAIRO_BO_EVENT_TYPE_INTERSECTION,
  1020.                                          left, right,
  1021.                                          &intersection);
  1022. }
  1023.  
  1024. static void
  1025. _cairo_bo_sweep_line_init (cairo_bo_sweep_line_t *sweep_line)
  1026. {
  1027.     sweep_line->head = NULL;
  1028.     sweep_line->current_y = INT32_MIN;
  1029.     sweep_line->current_edge = NULL;
  1030. }
  1031.  
  1032. static cairo_status_t
  1033. _cairo_bo_sweep_line_insert (cairo_bo_sweep_line_t      *sweep_line,
  1034.                              cairo_bo_edge_t            *edge)
  1035. {
  1036.     if (sweep_line->current_edge != NULL) {
  1037.         cairo_bo_edge_t *prev, *next;
  1038.         int cmp;
  1039.  
  1040.         cmp = _cairo_bo_sweep_line_compare_edges (sweep_line,
  1041.                                                   sweep_line->current_edge,
  1042.                                                   edge);
  1043.         if (cmp < 0) {
  1044.             prev = sweep_line->current_edge;
  1045.             next = prev->next;
  1046.             while (next != NULL &&
  1047.                    _cairo_bo_sweep_line_compare_edges (sweep_line,
  1048.                                                        next, edge) < 0)
  1049.             {
  1050.                 prev = next, next = prev->next;
  1051.             }
  1052.  
  1053.             prev->next = edge;
  1054.             edge->prev = prev;
  1055.             edge->next = next;
  1056.             if (next != NULL)
  1057.                 next->prev = edge;
  1058.         } else if (cmp > 0) {
  1059.             next = sweep_line->current_edge;
  1060.             prev = next->prev;
  1061.             while (prev != NULL &&
  1062.                    _cairo_bo_sweep_line_compare_edges (sweep_line,
  1063.                                                        prev, edge) > 0)
  1064.             {
  1065.                 next = prev, prev = next->prev;
  1066.             }
  1067.  
  1068.             next->prev = edge;
  1069.             edge->next = next;
  1070.             edge->prev = prev;
  1071.             if (prev != NULL)
  1072.                 prev->next = edge;
  1073.             else
  1074.                 sweep_line->head = edge;
  1075.         } else {
  1076.             prev = sweep_line->current_edge;
  1077.             edge->prev = prev;
  1078.             edge->next = prev->next;
  1079.             if (prev->next != NULL)
  1080.                 prev->next->prev = edge;
  1081.             prev->next = edge;
  1082.         }
  1083.     } else {
  1084.         sweep_line->head = edge;
  1085.     }
  1086.  
  1087.     sweep_line->current_edge = edge;
  1088.  
  1089.     return CAIRO_STATUS_SUCCESS;
  1090. }
  1091.  
  1092. static void
  1093. _cairo_bo_sweep_line_delete (cairo_bo_sweep_line_t      *sweep_line,
  1094.                              cairo_bo_edge_t    *edge)
  1095. {
  1096.     if (edge->prev != NULL)
  1097.         edge->prev->next = edge->next;
  1098.     else
  1099.         sweep_line->head = edge->next;
  1100.  
  1101.     if (edge->next != NULL)
  1102.         edge->next->prev = edge->prev;
  1103.  
  1104.     if (sweep_line->current_edge == edge)
  1105.         sweep_line->current_edge = edge->prev ? edge->prev : edge->next;
  1106. }
  1107.  
  1108. static void
  1109. _cairo_bo_sweep_line_swap (cairo_bo_sweep_line_t        *sweep_line,
  1110.                            cairo_bo_edge_t              *left,
  1111.                            cairo_bo_edge_t              *right)
  1112. {
  1113.     if (left->prev != NULL)
  1114.         left->prev->next = right;
  1115.     else
  1116.         sweep_line->head = right;
  1117.  
  1118.     if (right->next != NULL)
  1119.         right->next->prev = left;
  1120.  
  1121.     left->next = right->next;
  1122.     right->next = left;
  1123.  
  1124.     right->prev = left->prev;
  1125.     left->prev = right;
  1126. }
  1127.  
  1128. static inline cairo_bool_t
  1129. edges_colinear (const cairo_bo_edge_t *a, const cairo_bo_edge_t *b)
  1130. {
  1131.     if (_line_equal (&a->edge.line, &b->edge.line))
  1132.         return TRUE;
  1133.  
  1134.     if (_slope_compare (a, b))
  1135.         return FALSE;
  1136.  
  1137.     /* The choice of y is not truly arbitrary since we must guarantee that it
  1138.      * is greater than the start of either line.
  1139.      */
  1140.     if (a->edge.line.p1.y == b->edge.line.p1.y) {
  1141.         return a->edge.line.p1.x == b->edge.line.p1.x;
  1142.     } else if (a->edge.line.p2.y == b->edge.line.p2.y) {
  1143.         return a->edge.line.p2.x == b->edge.line.p2.x;
  1144.     } else if (a->edge.line.p1.y < b->edge.line.p1.y) {
  1145.         return edge_compare_for_y_against_x (b,
  1146.                                              a->edge.line.p1.y,
  1147.                                              a->edge.line.p1.x) == 0;
  1148.     } else {
  1149.         return edge_compare_for_y_against_x (a,
  1150.                                              b->edge.line.p1.y,
  1151.                                              b->edge.line.p1.x) == 0;
  1152.     }
  1153. }
  1154.  
  1155. static void
  1156. _cairo_bo_edge_end (cairo_bo_edge_t     *left,
  1157.                     int32_t              bot,
  1158.                     cairo_polygon_t     *polygon)
  1159. {
  1160.     cairo_bo_deferred_t *d = &left->deferred;
  1161.  
  1162.     if (likely (d->top < bot)) {
  1163.         _cairo_polygon_add_line (polygon,
  1164.                                  &left->edge.line,
  1165.                                  d->top, bot,
  1166.                                  1);
  1167.         _cairo_polygon_add_line (polygon,
  1168.                                  &d->right->edge.line,
  1169.                                  d->top, bot,
  1170.                                  -1);
  1171.     }
  1172.  
  1173.     d->right = NULL;
  1174. }
  1175.  
  1176.  
  1177. static inline void
  1178. _cairo_bo_edge_start_or_continue (cairo_bo_edge_t       *left,
  1179.                                   cairo_bo_edge_t       *right,
  1180.                                   int                    top,
  1181.                                   cairo_polygon_t       *polygon)
  1182. {
  1183.     if (left->deferred.right == right)
  1184.         return;
  1185.  
  1186.     if (left->deferred.right != NULL) {
  1187.         if (right != NULL && edges_colinear (left->deferred.right, right))
  1188.         {
  1189.             /* continuation on right, so just swap edges */
  1190.             left->deferred.right = right;
  1191.             return;
  1192.         }
  1193.  
  1194.         _cairo_bo_edge_end (left, top, polygon);
  1195.     }
  1196.  
  1197.     if (right != NULL && ! edges_colinear (left, right)) {
  1198.         left->deferred.top = top;
  1199.         left->deferred.right = right;
  1200.     }
  1201. }
  1202.  
  1203. static inline void
  1204. _active_edges_to_polygon (cairo_bo_edge_t               *left,
  1205.                           int32_t                        top,
  1206.                           cairo_fill_rule_t              fill_rule,
  1207.                           cairo_polygon_t               *polygon)
  1208. {
  1209.     cairo_bo_edge_t *right;
  1210.     unsigned int mask;
  1211.  
  1212.     if (fill_rule == CAIRO_FILL_RULE_WINDING)
  1213.         mask = ~0;
  1214.     else
  1215.         mask = 1;
  1216.  
  1217.     while (left != NULL) {
  1218.         int in_out = left->edge.dir;
  1219.  
  1220.         right = left->next;
  1221.         if (left->deferred.right == NULL) {
  1222.             while (right != NULL && right->deferred.right == NULL)
  1223.                 right = right->next;
  1224.  
  1225.             if (right != NULL && edges_colinear (left, right)) {
  1226.                 /* continuation on left */
  1227.                 left->deferred = right->deferred;
  1228.                 right->deferred.right = NULL;
  1229.             }
  1230.         }
  1231.  
  1232.         right = left->next;
  1233.         while (right != NULL) {
  1234.             if (right->deferred.right != NULL)
  1235.                 _cairo_bo_edge_end (right, top, polygon);
  1236.  
  1237.             in_out += right->edge.dir;
  1238.             if ((in_out & mask) == 0) {
  1239.                 /* skip co-linear edges */
  1240.                 if (right->next == NULL || !edges_colinear (right, right->next))
  1241.                     break;
  1242.             }
  1243.  
  1244.             right = right->next;
  1245.         }
  1246.  
  1247.         _cairo_bo_edge_start_or_continue (left, right, top, polygon);
  1248.  
  1249.         left = right;
  1250.         if (left != NULL)
  1251.             left = left->next;
  1252.     }
  1253. }
  1254.  
  1255.  
  1256. static cairo_status_t
  1257. _cairo_bentley_ottmann_tessellate_bo_edges (cairo_bo_event_t   **start_events,
  1258.                                             int                  num_events,
  1259.                                             cairo_fill_rule_t    fill_rule,
  1260.                                             cairo_polygon_t     *polygon)
  1261. {
  1262.     cairo_status_t status = CAIRO_STATUS_SUCCESS; /* silence compiler */
  1263.     cairo_bo_event_queue_t event_queue;
  1264.     cairo_bo_sweep_line_t sweep_line;
  1265.     cairo_bo_event_t *event;
  1266.     cairo_bo_edge_t *left, *right;
  1267.     cairo_bo_edge_t *e1, *e2;
  1268.  
  1269.     _cairo_bo_event_queue_init (&event_queue, start_events, num_events);
  1270.     _cairo_bo_sweep_line_init (&sweep_line);
  1271.  
  1272.     while ((event = _cairo_bo_event_dequeue (&event_queue))) {
  1273.         if (event->point.y != sweep_line.current_y) {
  1274.             _active_edges_to_polygon (sweep_line.head,
  1275.                                       sweep_line.current_y,
  1276.                                       fill_rule, polygon);
  1277.  
  1278.             sweep_line.current_y = event->point.y;
  1279.         }
  1280.  
  1281.         switch (event->type) {
  1282.         case CAIRO_BO_EVENT_TYPE_START:
  1283.             e1 = &((cairo_bo_start_event_t *) event)->edge;
  1284.  
  1285.             status = _cairo_bo_sweep_line_insert (&sweep_line, e1);
  1286.             if (unlikely (status))
  1287.                 goto unwind;
  1288.  
  1289.             status = _cairo_bo_event_queue_insert_stop (&event_queue, e1);
  1290.             if (unlikely (status))
  1291.                 goto unwind;
  1292.  
  1293.             left = e1->prev;
  1294.             right = e1->next;
  1295.  
  1296.             if (left != NULL) {
  1297.                 status = _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, left, e1);
  1298.                 if (unlikely (status))
  1299.                     goto unwind;
  1300.             }
  1301.  
  1302.             if (right != NULL) {
  1303.                 status = _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, e1, right);
  1304.                 if (unlikely (status))
  1305.                     goto unwind;
  1306.             }
  1307.  
  1308.             break;
  1309.  
  1310.         case CAIRO_BO_EVENT_TYPE_STOP:
  1311.             e1 = ((cairo_bo_queue_event_t *) event)->e1;
  1312.             _cairo_bo_event_queue_delete (&event_queue, event);
  1313.  
  1314.             left = e1->prev;
  1315.             right = e1->next;
  1316.  
  1317.             _cairo_bo_sweep_line_delete (&sweep_line, e1);
  1318.  
  1319.             if (e1->deferred.right != NULL)
  1320.                 _cairo_bo_edge_end (e1, e1->edge.bottom, polygon);
  1321.  
  1322.             if (left != NULL && right != NULL) {
  1323.                 status = _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, left, right);
  1324.                 if (unlikely (status))
  1325.                     goto unwind;
  1326.             }
  1327.  
  1328.             break;
  1329.  
  1330.         case CAIRO_BO_EVENT_TYPE_INTERSECTION:
  1331.             e1 = ((cairo_bo_queue_event_t *) event)->e1;
  1332.             e2 = ((cairo_bo_queue_event_t *) event)->e2;
  1333.             _cairo_bo_event_queue_delete (&event_queue, event);
  1334.  
  1335.             /* skip this intersection if its edges are not adjacent */
  1336.             if (e2 != e1->next)
  1337.                 break;
  1338.  
  1339.             left = e1->prev;
  1340.             right = e2->next;
  1341.  
  1342.             _cairo_bo_sweep_line_swap (&sweep_line, e1, e2);
  1343.  
  1344.             /* after the swap e2 is left of e1 */
  1345.  
  1346.             if (left != NULL) {
  1347.                 status = _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, left, e2);
  1348.                 if (unlikely (status))
  1349.                     goto unwind;
  1350.             }
  1351.  
  1352.             if (right != NULL) {
  1353.                 status = _cairo_bo_event_queue_insert_if_intersect_below_current_y (&event_queue, e1, right);
  1354.                 if (unlikely (status))
  1355.                     goto unwind;
  1356.             }
  1357.  
  1358.             break;
  1359.         }
  1360.     }
  1361.  
  1362.  unwind:
  1363.     _cairo_bo_event_queue_fini (&event_queue);
  1364.  
  1365.     return status;
  1366. }
  1367.  
  1368. cairo_status_t
  1369. _cairo_polygon_reduce (cairo_polygon_t *polygon,
  1370.                        cairo_fill_rule_t fill_rule)
  1371. {
  1372.     cairo_status_t status;
  1373.     cairo_bo_start_event_t stack_events[CAIRO_STACK_ARRAY_LENGTH (cairo_bo_start_event_t)];
  1374.     cairo_bo_start_event_t *events;
  1375.     cairo_bo_event_t *stack_event_ptrs[ARRAY_LENGTH (stack_events) + 1];
  1376.     cairo_bo_event_t **event_ptrs;
  1377.     int num_limits;
  1378.     int num_events;
  1379.     int i;
  1380.  
  1381.     num_events = polygon->num_edges;
  1382.     if (unlikely (0 == num_events))
  1383.         return CAIRO_STATUS_SUCCESS;
  1384.  
  1385.     if (DEBUG_POLYGON) {
  1386.         FILE *file = fopen ("reduce_in.txt", "w");
  1387.         _cairo_debug_print_polygon (file, polygon);
  1388.         fclose (file);
  1389.     }
  1390.  
  1391.     events = stack_events;
  1392.     event_ptrs = stack_event_ptrs;
  1393.     if (num_events > ARRAY_LENGTH (stack_events)) {
  1394.         events = _cairo_malloc_ab_plus_c (num_events,
  1395.                                           sizeof (cairo_bo_start_event_t) +
  1396.                                           sizeof (cairo_bo_event_t *),
  1397.                                           sizeof (cairo_bo_event_t *));
  1398.         if (unlikely (events == NULL))
  1399.             return _cairo_error (CAIRO_STATUS_NO_MEMORY);
  1400.  
  1401.         event_ptrs = (cairo_bo_event_t **) (events + num_events);
  1402.     }
  1403.  
  1404.     for (i = 0; i < num_events; i++) {
  1405.         event_ptrs[i] = (cairo_bo_event_t *) &events[i];
  1406.  
  1407.         events[i].type = CAIRO_BO_EVENT_TYPE_START;
  1408.         events[i].point.y = polygon->edges[i].top;
  1409.         events[i].point.x =
  1410.             _line_compute_intersection_x_for_y (&polygon->edges[i].line,
  1411.                                                 events[i].point.y);
  1412.  
  1413.         events[i].edge.edge = polygon->edges[i];
  1414.         events[i].edge.deferred.right = NULL;
  1415.         events[i].edge.prev = NULL;
  1416.         events[i].edge.next = NULL;
  1417.     }
  1418.  
  1419.     num_limits = polygon->num_limits; polygon->num_limits = 0;
  1420.     polygon->num_edges = 0;
  1421.  
  1422.     status = _cairo_bentley_ottmann_tessellate_bo_edges (event_ptrs,
  1423.                                                          num_events,
  1424.                                                          fill_rule,
  1425.                                                          polygon);
  1426.     polygon->num_limits = num_limits;
  1427.  
  1428.     if (events != stack_events)
  1429.         free (events);
  1430.  
  1431.     if (DEBUG_POLYGON) {
  1432.         FILE *file = fopen ("reduce_out.txt", "w");
  1433.         _cairo_debug_print_polygon (file, polygon);
  1434.         fclose (file);
  1435.     }
  1436.  
  1437.     return status;
  1438. }
  1439.