1 files changed, 8 insertions, 226 deletions

diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c
index 7259add0c..3f6f02422 100755..100644
--- a/src/cairo-bentley-ottmann.c
+++ b/src/cairo-bentley-ottmann.c
@@ -38,9 +38,10 @@
 /* Provide definitions for standalone compilation */
 #include "cairoint.h"
 
+#include "cairo-combsort-inline.h"
 #include "cairo-error-private.h"
 #include "cairo-freelist-private.h"
-#include "cairo-combsort-inline.h"
+#include "cairo-line-inline.h"
 #include "cairo-traps-private.h"
 
 #define DEBUG_PRINT_STATE 0
@@ -307,156 +308,6 @@ _slope_compare (const cairo_bo_edge_t *a,
     }
 }
 
-/*
- * We need to compare the x-coordinates of a pair of lines for a particular y,
- * without loss of precision.
- *
- * The x-coordinate along an edge for a given y is:
- *   X = A_x + (Y - A_y) * A_dx / A_dy
- *
- * So the inequality we wish to test is:
- *   A_x + (Y - A_y) * A_dx / A_dy ∘ B_x + (Y - B_y) * B_dx / B_dy,
- * where ∘ is our inequality operator.
- *
- * By construction, we know that A_dy and B_dy (and (Y - A_y), (Y - B_y)) are
- * all positive, so we can rearrange it thus without causing a sign change:
- *   A_dy * B_dy * (A_x - B_x) ∘ (Y - B_y) * B_dx * A_dy
- *                                 - (Y - A_y) * A_dx * B_dy
- *
- * Given the assumption that all the deltas fit within 32 bits, we can compute
- * this comparison directly using 128 bit arithmetic. For certain, but common,
- * input we can reduce this down to a single 32 bit compare by inspecting the
- * deltas.
- *
- * (And put the burden of the work on developing fast 128 bit ops, which are
- * required throughout the tessellator.)
- *
- * See the similar discussion for _slope_compare().
- */
-static int
-edges_compare_x_for_y_general (const cairo_bo_edge_t *a,
-			       const cairo_bo_edge_t *b,
-			       int32_t y)
-{
-    /* XXX: We're assuming here that dx and dy will still fit in 32
-     * bits. That's not true in general as there could be overflow. We
-     * should prevent that before the tessellation algorithm
-     * begins.
-     */
-    int32_t dx;
-    int32_t adx, ady;
-    int32_t bdx, bdy;
-    enum {
-       HAVE_NONE    = 0x0,
-       HAVE_DX      = 0x1,
-       HAVE_ADX     = 0x2,
-       HAVE_DX_ADX  = HAVE_DX | HAVE_ADX,
-       HAVE_BDX     = 0x4,
-       HAVE_DX_BDX  = HAVE_DX | HAVE_BDX,
-       HAVE_ADX_BDX = HAVE_ADX | HAVE_BDX,
-       HAVE_ALL     = HAVE_DX | HAVE_ADX | HAVE_BDX
-    } have_dx_adx_bdx = HAVE_ALL;
-
-    /* don't bother solving for abscissa if the edges' bounding boxes
-     * can be used to order them. */
-    {
-           int32_t amin, amax;
-           int32_t bmin, bmax;
-           if (a->edge.line.p1.x < a->edge.line.p2.x) {
-                   amin = a->edge.line.p1.x;
-                   amax = a->edge.line.p2.x;
-           } else {
-                   amin = a->edge.line.p2.x;
-                   amax = a->edge.line.p1.x;
-           }
-           if (b->edge.line.p1.x < b->edge.line.p2.x) {
-                   bmin = b->edge.line.p1.x;
-                   bmax = b->edge.line.p2.x;
-           } else {
-                   bmin = b->edge.line.p2.x;
-                   bmax = b->edge.line.p1.x;
-           }
-           if (amax < bmin) return -1;
-           if (amin > bmax) return +1;
-    }
-
-    ady = a->edge.line.p2.y - a->edge.line.p1.y;
-    adx = a->edge.line.p2.x - a->edge.line.p1.x;
-    if (adx == 0)
-	have_dx_adx_bdx &= ~HAVE_ADX;
-
-    bdy = b->edge.line.p2.y - b->edge.line.p1.y;
-    bdx = b->edge.line.p2.x - b->edge.line.p1.x;
-    if (bdx == 0)
-	have_dx_adx_bdx &= ~HAVE_BDX;
-
-    dx = a->edge.line.p1.x - b->edge.line.p1.x;
-    if (dx == 0)
-	have_dx_adx_bdx &= ~HAVE_DX;
-
-#define L _cairo_int64x32_128_mul (_cairo_int32x32_64_mul (ady, bdy), dx)
-#define A _cairo_int64x32_128_mul (_cairo_int32x32_64_mul (adx, bdy), y - a->edge.line.p1.y)
-#define B _cairo_int64x32_128_mul (_cairo_int32x32_64_mul (bdx, ady), y - b->edge.line.p1.y)
-    switch (have_dx_adx_bdx) {
-    default:
-    case HAVE_NONE:
-	return 0;
-    case HAVE_DX:
-	/* A_dy * B_dy * (A_x - B_x) ∘ 0 */
-	return dx; /* ady * bdy is positive definite */
-    case HAVE_ADX:
-	/* 0 ∘  - (Y - A_y) * A_dx * B_dy */
-	return adx; /* bdy * (y - a->top.y) is positive definite */
-    case HAVE_BDX:
-	/* 0 ∘ (Y - B_y) * B_dx * A_dy */
-	return -bdx; /* ady * (y - b->top.y) is positive definite */
-    case HAVE_ADX_BDX:
-	/*  0 ∘ (Y - B_y) * B_dx * A_dy - (Y - A_y) * A_dx * B_dy */
-	if ((adx ^ bdx) < 0) {
-	    return adx;
-	} else if (a->edge.line.p1.y == b->edge.line.p1.y) { /* common origin */
-	    cairo_int64_t adx_bdy, bdx_ady;
-
-	    /* ∴ A_dx * B_dy ∘ B_dx * A_dy */
-
-	    adx_bdy = _cairo_int32x32_64_mul (adx, bdy);
-	    bdx_ady = _cairo_int32x32_64_mul (bdx, ady);
-
-	    return _cairo_int64_cmp (adx_bdy, bdx_ady);
-	} else
-	    return _cairo_int128_cmp (A, B);
-    case HAVE_DX_ADX:
-	/* A_dy * (A_x - B_x) ∘ - (Y - A_y) * A_dx */
-	if ((-adx ^ dx) < 0) {
-	    return dx;
-	} else {
-	    cairo_int64_t ady_dx, dy_adx;
-
-	    ady_dx = _cairo_int32x32_64_mul (ady, dx);
-	    dy_adx = _cairo_int32x32_64_mul (a->edge.line.p1.y - y, adx);
-
-	    return _cairo_int64_cmp (ady_dx, dy_adx);
-	}
-    case HAVE_DX_BDX:
-	/* B_dy * (A_x - B_x) ∘ (Y - B_y) * B_dx */
-	if ((bdx ^ dx) < 0) {
-	    return dx;
-	} else {
-	    cairo_int64_t bdy_dx, dy_bdx;
-
-	    bdy_dx = _cairo_int32x32_64_mul (bdy, dx);
-	    dy_bdx = _cairo_int32x32_64_mul (y - b->edge.line.p1.y, bdx);
-
-	    return _cairo_int64_cmp (bdy_dx, dy_bdx);
-	}
-    case HAVE_ALL:
-	/* XXX try comparing (a->edge.line.p2.x - b->edge.line.p2.x) et al */
-	return _cairo_int128_cmp (L, _cairo_int128_sub (B, A));
-    }
-#undef B
-#undef A
-#undef L
-}
 
 /*
  * We need to compare the x-coordinate of a line for a particular y wrt to a
@@ -510,58 +361,6 @@ edge_compare_for_y_against_x (const cairo_bo_edge_t *a,
     return _cairo_int64_cmp (L, R);
 }
 
-static int
-edges_compare_x_for_y (const cairo_bo_edge_t *a,
-		       const cairo_bo_edge_t *b,
-		       int32_t y)
-{
-    /* If the sweep-line is currently on an end-point of a line,
-     * then we know its precise x value (and considering that we often need to
-     * compare events at end-points, this happens frequently enough to warrant
-     * special casing).
-     */
-    enum {
-       HAVE_NEITHER = 0x0,
-       HAVE_AX      = 0x1,
-       HAVE_BX      = 0x2,
-       HAVE_BOTH    = HAVE_AX | HAVE_BX
-    } have_ax_bx = HAVE_BOTH;
-    int32_t ax, bx;
-
-    if (y == a->edge.line.p1.y)
-	ax = a->edge.line.p1.x;
-    else if (y == a->edge.line.p2.y)
-	ax = a->edge.line.p2.x;
-    else
-	have_ax_bx &= ~HAVE_AX;
-
-    if (y == b->edge.line.p1.y)
-	bx = b->edge.line.p1.x;
-    else if (y == b->edge.line.p2.y)
-	bx = b->edge.line.p2.x;
-    else
-	have_ax_bx &= ~HAVE_BX;
-
-    switch (have_ax_bx) {
-    default:
-    case HAVE_NEITHER:
-	return edges_compare_x_for_y_general (a, b, y);
-    case HAVE_AX:
-	return -edge_compare_for_y_against_x (b, y, ax);
-    case HAVE_BX:
-	return edge_compare_for_y_against_x (a, y, bx);
-    case HAVE_BOTH:
-	return ax - bx;
-    }
-}
-
-static inline int
-_line_equal (const cairo_line_t *a, const cairo_line_t *b)
-{
-    return a->p1.x == b->p1.x && a->p1.y == b->p1.y &&
-           a->p2.x == b->p2.x && a->p2.y == b->p2.y;
-}
-
 static inline int
 _cairo_bo_sweep_line_compare_edges (const cairo_bo_sweep_line_t	*sweep_line,
 				    const cairo_bo_edge_t	*a,
@@ -569,28 +368,11 @@ _cairo_bo_sweep_line_compare_edges (const cairo_bo_sweep_line_t	*sweep_line,
 {
     int cmp;
 
-    /* compare the edges if not identical */
-    if (! _line_equal (&a->edge.line, &b->edge.line)) {
-	if (MAX (a->edge.line.p1.x, a->edge.line.p2.x) <
-	    MIN (b->edge.line.p1.x, b->edge.line.p2.x))
-	    return -1;
-	else if (MIN (a->edge.line.p1.x, a->edge.line.p2.x) >
-		 MAX (b->edge.line.p1.x, b->edge.line.p2.x))
-	    return 1;
-
-	cmp = edges_compare_x_for_y (a, b, sweep_line->current_y);
-	if (cmp)
-	    return cmp;
-
-	/* The two edges intersect exactly at y, so fall back on slope
-	 * comparison. We know that this compare_edges function will be
-	 * called only when starting a new edge, (not when stopping an
-	 * edge), so we don't have to worry about conditionally inverting
-	 * the sense of _slope_compare. */
-	cmp = _slope_compare (a, b);
-	if (cmp)
+    cmp = cairo_lines_compare_at_y (&a->edge.line,
+				    &b->edge.line,
+				    sweep_line->current_y);
+    if (cmp)
 	    return cmp;
-    }
 
     /* We've got two collinear edges now. */
     return b->edge.bottom - a->edge.bottom;
@@ -1090,7 +872,7 @@ _cairo_bo_event_queue_insert_if_intersect_below_current_y (cairo_bo_event_queue_
 	MIN (right->edge.line.p1.x, right->edge.line.p2.x))
 	return CAIRO_STATUS_SUCCESS;
 
-    if (_line_equal (&left->edge.line, &right->edge.line))
+    if (cairo_lines_equal (&left->edge.line, &right->edge.line))
 	return CAIRO_STATUS_SUCCESS;
 
     /* The names "left" and "right" here are correct descriptions of
@@ -1691,7 +1473,7 @@ _cairo_bentley_ottmann_tessellate_polygon (cairo_traps_t	 *traps,
     cairo_bo_event_t **event_ptrs;
     cairo_bo_start_event_t *stack_event_y[64];
     cairo_bo_start_event_t **event_y = NULL;
-    int i, num_events, y, ymin = 0, ymax = 0;
+    int i, num_events, y, ymin, ymax;
     cairo_status_t status;
 
     num_events = polygon->num_edges;