# [PATCH] [tessellator] Simplify special cases of edges to compare.

Chris Wilson chris at chris-wilson.co.uk
Sat Oct 4 05:15:08 PDT 2008

```Use our prior knowledge of the inputs and trivial conditions to simplify
the edge equations and in many common conditions, such as vertical edges
and common points, reduce the operations down to a just returning the
non-degenerate 32 bit value.  This adds an overhead of a few conditionals,
but on the fast paths we actually generate fewer branches and many fewer
arithmetic operations such that it improves performance of the fill
performance tests by around 10%.
---
src/cairo-bentley-ottmann.c |  140 +++++++++++++++++++++++++++++++++---------
1 files changed, 110 insertions(+), 30 deletions(-)

diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c
index 47ee833..6d1c78c 100644
--- a/src/cairo-bentley-ottmann.c
+++ b/src/cairo-bentley-ottmann.c
@@ -197,15 +197,25 @@ _slope_compare (cairo_bo_edge_t *a,
int32_t bdx = b->bottom.x - b->top.x;

/* Since the dy's are all positive by construction we can fast
-     * path the case where the two edges point in different directions
-     * with respect to x. */
-    if ((adx ^ bdx) < 0) {
-	return adx < 0 ? -1 : +1;
-    } else {
+     * path several common cases.
+     */
+
+    /* First check for vertical lines. */
+	return -bdx;
+    if (bdx == 0)
+
+    /* Then where the two edges point in different directions wrt x. */
+    if ((adx ^ bdx) < 0)
+
+    /* Finally we actually need to do the general comparison. */
+    {
int32_t ady = a->bottom.y - a->top.y;
int32_t bdy = b->bottom.y - b->top.y;

}
@@ -228,7 +238,9 @@ _slope_compare (cairo_bo_edge_t *a,
*                                 - (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.
+ * 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.)
@@ -245,32 +257,95 @@ edges_compare_x_for_y_general (const cairo_bo_edge_t *a,
* should prevent that before the tessellation algorithm
* begins.
*/
+    int32_t dx;
int32_t bdx, bdy;
-    cairo_int128_t L, R;
+    enum {
+       HAVE_NONE    = 0x0,
+       HAVE_DX      = 0x1,
+       HAVE_BDX     = 0x4,
+       HAVE_DX_BDX  = HAVE_DX | HAVE_BDX,
+       HAVE_ALL     = HAVE_DX | HAVE_ADX | HAVE_BDX

-    adx = a->bottom.x - a->top.x;
+    adx = a->bottom.x - a->top.x;

-    bdx = b->bottom.x - b->top.x;
bdy = b->bottom.y - b->top.y;
+    bdx = b->bottom.x - b->top.x;
+    if (bdx == 0)

-    L = _cairo_int64x32_128_mul (_cairo_int32x32_64_mul (ady, bdy),
-				 a->top.x - b->top.x);
+    dx = a->top.x - b->top.x;
+    if (dx == 0)

-    R = _cairo_int128_sub (_cairo_int64x32_128_mul (_cairo_int32x32_64_mul (bdx,
-						    y - b->top.y),
-									    bdy),
-						    y - a->top.y));
+#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->top.y)
+#define B _cairo_int64x32_128_mul (_cairo_int32x32_64_mul (bdx, ady), y - b->top.y)
+    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 */
+	/* 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 */
+	/*  0 -?- (Y - B_y) * B_dx * A_dy - (Y - A_y) * A_dx * B_dy */
+	if ((adx ^ bdx) < 0) {
+	} else if (a->top.y == b->top.y) { /* common origin */
+
+	    /* => A_dx * B_dy -?- B_dx * A_dy */
+
+
+	} else
+	    return _cairo_int128_cmp (A, B);
+	/* A_dy * (A_x - B_x) -?- - (Y - A_y) * A_dx */
+	if ((-adx ^ dx) < 0) {
+	    return dx;
+	} else {

-    /* return _cairo_int128_cmp (L, R); */
-    if (_cairo_int128_lt (L, R))
-	return -1;
-    if (_cairo_int128_gt (L, R))
-	return 1;
-    return 0;
+
+	}
+    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->top.y, bdx);
+
+	    return _cairo_int64_cmp (bdy_dx, dy_bdx);
+	}
+    case HAVE_ALL:
+	return _cairo_int128_cmp (L, _cairo_int128_sub (B, A));
+    }
+#undef B
+#undef A
+#undef L
}

/*
@@ -304,10 +379,15 @@ edge_compare_for_y_against_x (const cairo_bo_edge_t *a,
cairo_int64_t L, R;

-    ady = a->bottom.y - a->top.y;
+    dx = x - a->top.x;
+
+	return -dx;
+    if ((adx ^ dx) < 0)

dy = y - a->top.y;
-    dx = x - a->top.x;
+    ady = a->bottom.y - a->top.y;

@@ -352,7 +432,7 @@ edges_compare_x_for_y (const cairo_bo_edge_t *a,
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);
+	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:
--
1.5.6.3

--=-s8o5xVksy5kwgG7ZmUbu--

```