[PATCH] [tessellator] Compare fractional remainders wrt to their dividers.

[Chris Wilson]

When comparing the x-coordinate of two edges for a particular y,
we check the following equality:
  A_x + (A_rem / A_dy) == B_x + (B_rem / B_dy)

First we can do a trivial check to see whether A_x and B_x differ.
However, given their equality we need to compare:
  A_rem / A_dy == B_rem / B_dy;
which rearranging gives:
  A_rem * B_dy == B_rem * A_dy.

Note that the sign of A_rem and B_rem is unknown, but by construction
we know that the fraction represents the remainder of a pixel away from
the origin. So we can just use the absolute values and fix up the sign
of the equality by comparing A_x with 0.
---
 src/cairo-bentley-ottmann.c |   89 +++++++++++++++++++++++++++++++++++--------
 1 files changed, 73 insertions(+), 16 deletions(-)

diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c
index a78745d..99787f0 100644
--- a/src/cairo-bentley-ottmann.c
+++ b/src/cairo-bentley-ottmann.c
@@ -220,8 +220,9 @@ _slope_compare (cairo_bo_edge_t *a,
 }
 
 static cairo_quorem64_t
-edge_x_for_y (cairo_bo_edge_t *edge,
-	      int32_t y)
+edge_x_for_y (const cairo_bo_edge_t *edge,
+	      int32_t y,
+	      int32_t *div_out)
 {
     /* 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
@@ -233,6 +234,8 @@ edge_x_for_y (cairo_bo_edge_t *edge,
     int64_t numerator;
     cairo_quorem64_t quorem;
 
+    *div_out = dy;
+
     if (edge->middle.y == y) {
        quorem.quo = edge->middle.x;
        quorem.rem = 0;
@@ -257,13 +260,76 @@ edge_x_for_y (cairo_bo_edge_t *edge,
     return quorem;
 }
 
+/*
+ * When comparing the x-coordinate of two edges for a particular y,
+ * we check the following equality:
+ *   A_x + (A_rem / A_dy) == B_x + (B_rem / B_dy)
+ *
+ * First we can do a trivial check to see whether A_x and B_x differ.
+ * However, given their equality we need to compare:
+ *   A_rem / A_dy == B_rem / B_dy;
+ * which rearranging gives:
+ *   A_rem * B_dy == B_rem * A_dy.
+ *
+ * Note that the sign of A_rem and B_rem is unknown, but by construction
+ * we know that the fraction represents the remainder of a pixel away from
+ * the origin. So we can just use the absolute values and fix up the sign
+ * of the equality by comparing A_x with 0.
+ *
+ * See the similar discussion for _slope_compare().
+ */
+static int
+edges_compare_x_for_y (const cairo_bo_edge_t *a,
+		       const cairo_bo_edge_t *b,
+		       int32_t y)
+{
+    cairo_quorem64_t ax;
+    cairo_quorem64_t bx;
+    int32_t ady, bdy;
+    int32_t arem, brem;
+    cairo_int64_t ab, ba;
+
+    ax = edge_x_for_y (a, y, &ady);
+    bx = edge_x_for_y (b, y, &bdy);
+    if (ax.quo > bx.quo)
+	return 1;
+    else if (ax.quo < bx.quo)
+	return -1;
+
+    /* Quotients are identical, test remainder. */
+    arem = _cairo_int64_to_int32 (ax.rem);
+    brem = _cairo_int64_to_int32 (bx.rem);
+    if (arem == 0 && brem == 0)
+	return 0;
+
+    if (arem < 0)
+	arem = -arem;
+    if (brem < 0)
+	brem = -brem;
+
+    if (ady == bdy) {
+	if (arem > brem)
+	    return ax.quo < 0 ? 1 : -1;
+	else if (arem < brem)
+	    return ax.quo < 0 ? -1 : 1;
+	return 0;
+    }
+
+    ab = _cairo_int32x32_64_mul (arem, bdy);
+    ba = _cairo_int32x32_64_mul (brem, ady);
+    if (ab > ba)
+	return ax.quo < 0 ? 1 : -1;
+    else if (ab < ba)
+	return ax.quo < 0 ? -1 : 1;
+
+    return 0;
+}
+
 static int
 _cairo_bo_sweep_line_compare_edges (cairo_bo_sweep_line_t	*sweep_line,
 				    cairo_bo_edge_t		*a,
 				    cairo_bo_edge_t		*b)
 {
-    cairo_quorem64_t ax;
-    cairo_quorem64_t bx;
     int cmp;
 
     if (a == b)
@@ -292,18 +358,9 @@ _cairo_bo_sweep_line_compare_edges (cairo_bo_sweep_line_t	*sweep_line,
            if (amin > bmax) return +1;
     }
 
-    ax = edge_x_for_y (a, sweep_line->current_y);
-    bx = edge_x_for_y (b, sweep_line->current_y);
-    if (ax.quo > bx.quo)
-	return 1;
-    else if (ax.quo < bx.quo)
-	return -1;
-
-    /* Quotients are identical, test remainder. */
-    if (ax.rem > bx.rem)
-	return 1;
-    else if (ax.rem < bx.rem)
-	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
-- 
1.5.6.3


--=-KbkbY7XkUAOFDijAJQ9C--