[cairo-commit] 2 commits - src/cairo-bentley-ottmann.c
Chris Wilson
ickle at kemper.freedesktop.org
Thu Oct 30 11:26:56 PDT 2008
src/cairo-bentley-ottmann.c | 183 +++++++++++++++++++++++++++++++++++++-------
1 file changed, 156 insertions(+), 27 deletions(-)
New commits:
commit e3a7f522a6b96729b2a0122f8c430c24dc17fc5a
Author: Chris Wilson <chris at chris-wilson.co.uk>
Date: Tue Oct 7 23:33:32 2008 +0100
[tessellator] Perform cheap checks before computing intersect.
First check if we can reject the intersection without having to perform
the full divides, based on analysing:
t * (ady*bdx - bdy*adx) = bdy * (ax - bx) - bdx * (ay - by)
s * (ady*bdx - bdy*adx) = ady * (ax - bx) - adx * (ay - by)
and excluding the result if by inspection we know that
(s, t) <= 0 || (s, t) => 1.
Doing so virtually eliminates all division and speeds up the strokes (when
performing self-intersection elimination using the tessellator) perf cases
by about 5%.
diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c
index 93d0fbf..2d8e324 100644
--- a/src/cairo-bentley-ottmann.c
+++ b/src/cairo-bentley-ottmann.c
@@ -704,12 +704,61 @@ intersect_lines (cairo_bo_edge_t *a,
int32_t dx2 = b->top.x - b->bottom.x;
int32_t dy2 = b->top.y - b->bottom.y;
- cairo_int64_t den_det = det32_64 (dx1, dy1, dx2, dy2);
+ cairo_int64_t den_det;
+ cairo_int64_t R;
cairo_quorem64_t qr;
+ den_det = det32_64 (dx1, dy1, dx2, dy2);
if (_cairo_int64_is_zero (den_det))
return CAIRO_BO_STATUS_PARALLEL;
+ /* Q: Can we determine that the lines do not intersect (within range)
+ * much more cheaply than computing the intersection point i.e. by
+ * avoiding the division?
+ *
+ * X = ax + t * adx = bx + s * bdx;
+ * Y = ay + t * ady = by + s * bdy;
+ * => t * (ady*bdx - bdy*adx) = bdx * (by - ay) + bdy * (ax - bx)
+ * => t * L = R
+ *
+ * Therefore we can reject any intersection (under the criteria for
+ * valid intersection events) if:
+ * L^R < 0 => t < 0
+ * L<R => t > 1
+ *
+ * (where top/bottom must at least extend to the line endpoints).
+ *
+ * A similar substitution can be performed for s, yielding:
+ * s * (ady*bdx - bdy*adx) = ady * (ax - bx) - adx * (ay - by)
+ */
+ R = det32_64 (dx2, dy2, b->top.x - a->top.x, b->top.y - a->top.y);
+ if (_cairo_int64_is_zero (R))
+ return CAIRO_BO_STATUS_NO_INTERSECTION;
+ if (_cairo_int64_negative (den_det) ^ _cairo_int64_negative (R))
+ return CAIRO_BO_STATUS_NO_INTERSECTION;
+ if (_cairo_int64_negative (den_det)) {
+ if (_cairo_int64_ge (den_det, R))
+ return CAIRO_BO_STATUS_NO_INTERSECTION;
+ } else {
+ if (_cairo_int64_le (den_det, R))
+ return CAIRO_BO_STATUS_NO_INTERSECTION;
+ }
+
+ R = det32_64 (dy1, dx1, a->top.y - b->top.y, a->top.x - b->top.x);
+ if (_cairo_int64_is_zero (R))
+ return CAIRO_BO_STATUS_NO_INTERSECTION;
+ if (_cairo_int64_negative (den_det) ^ _cairo_int64_negative (R))
+ return CAIRO_BO_STATUS_NO_INTERSECTION;
+ if (_cairo_int64_negative (den_det)) {
+ if (_cairo_int64_ge (den_det, R))
+ return CAIRO_BO_STATUS_NO_INTERSECTION;
+ } else {
+ if (_cairo_int64_le (den_det, R))
+ return CAIRO_BO_STATUS_NO_INTERSECTION;
+ }
+
+ /* We now know that the two lines should intersect within range. */
+
a_det = det32_64 (a->top.x, a->top.y,
a->bottom.x, a->bottom.y);
b_det = det32_64 (b->top.x, b->top.y,
commit 553fde4bb3e913de7e26bf416166d69bae4d02e1
Author: Chris Wilson <chris at chris-wilson.co.uk>
Date: Sat Oct 4 13:15:08 2008 +0100
[tessellator] Simplify special cases of edges to compare.
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%.
diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c
index c657dd9..93d0fbf 100644
--- a/src/cairo-bentley-ottmann.c
+++ b/src/cairo-bentley-ottmann.c
@@ -197,11 +197,21 @@ _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. */
+ if (adx == 0)
+ return -bdx;
+ if (bdx == 0)
+ return adx;
+
+ /* Then where the two edges point in different directions wrt x. */
+ if ((adx ^ bdx) < 0)
+ return adx;
+
+ /* 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;
cairo_int64_t adx_bdy = _cairo_int32x32_64_mul (adx, bdy);
@@ -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 adx, ady;
int32_t bdx, bdy;
- cairo_int128_t L, R;
+ 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;
- adx = a->bottom.x - a->top.x;
ady = a->bottom.y - a->top.y;
+ adx = a->bottom.x - a->top.x;
+ if (adx == 0)
+ have_dx_adx_bdx &= ~HAVE_ADX;
- bdx = b->bottom.x - b->top.x;
bdy = b->bottom.y - b->top.y;
+ bdx = b->bottom.x - b->top.x;
+ if (bdx == 0)
+ have_dx_adx_bdx &= ~HAVE_BDX;
- 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)
+ have_dx_adx_bdx &= ~HAVE_DX;
- R = _cairo_int128_sub (_cairo_int64x32_128_mul (_cairo_int32x32_64_mul (bdx,
- ady),
- y - b->top.y),
- _cairo_int64x32_128_mul (_cairo_int32x32_64_mul (adx,
- 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)
+ 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->top.y == b->top.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;
- /* return _cairo_int128_cmp (L, R); */
- if (_cairo_int128_lt (L, R))
- return -1;
- if (_cairo_int128_gt (L, R))
- return 1;
- return 0;
+ ady_dx = _cairo_int32x32_64_mul (ady, dx);
+ dy_adx = _cairo_int32x32_64_mul (a->top.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->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;
adx = a->bottom.x - a->top.x;
- ady = a->bottom.y - a->top.y;
+ dx = x - a->top.x;
+
+ if (adx == 0)
+ return -dx;
+ if ((adx ^ dx) < 0)
+ return adx;
dy = y - a->top.y;
- dx = x - a->top.x;
+ ady = a->bottom.y - a->top.y;
L = _cairo_int32x32_64_mul (dy, adx);
R = _cairo_int32x32_64_mul (dx, ady);
@@ -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:
More information about the cairo-commit
mailing list