[cairo] Tessellator performance patch

Sun Dec 3 19:41:06 PST 2006

I've been trying to find some ways to avoid intersection computation in 
the tessellator code to improve performance.

This patch creates a new function _cairo_may_intersect that takes to 
edges and informs about the feasibility of an intersection between them. 
It can report false positives when TRUE, but it's really useful to 
discard cases where no intersection is possible to avoid expensive 
intersection code.

The function fully detects proper intersection and checks for the 
possibility of improper intersection, through the detection of collinear 
points.

This is how the code works:

1) Proper intersection check
When two segments segment1 and segment2, defined by its endpoints a,b 
and c,d, intersect properly, then edge segment1 has one of the segment2 
endpoints to its left AND the other one to its right side, and vice versa.

It's possible to check whether a point c is to the left of a segment 
(a->b) using the cross product of a->b and a->c : 
(bx-ax).(cy-ay)-(by-ay)(cx-ax)

The cross product is:
* greater than zero when both vectors form a counter-clockwise system, 
so c is to the left.
* equal to zero when the three points are colinear
* less than zero when the point is to the left

we can now check for proper intersection using:
!(crossp_abc>0) ^ !(crossp_abd>0)) && (!(crossp_cda>0) ^ !(crossp_cdb>0)
to return TRUE iff proper intersection happens

2)Improper intersection: Colinearity
Improper intersection means that one endpoint of a segment is on the 
other segment. We can discard improper intersection cases checking for 
colinearity of the endpoints in each segment:
crossp_abc==0 || crossp_abd==0 || crossp_cda==0 || crossp_cdb==0

We use this checks to return before doing actual intersection 
calculation in _cairo_bo_event_queue_insert_if_intersect_below_current_y 
and there's little performance difference when doing this check before 
the slope test or after it.

I've tried to get a fast slope comparison test into this function but I 
can't see why I can't get it working.
As we are checking for _slope_compare(left, right)<0 we could benefit 
from a short path check, and avoid the calculation of the other cases.

Also, there's room to improve the tests, as we're not using the fact 
that the intersections we're looking for are under the current sweep 
line, and that we know the segments ordering.

The performance impact for ./cairo-perf-diff origin HEAD -- world-map 
zrusin tessellate
is this:

Speedups
========
image-rgba tessellate-256-100 62.67 0.92% -> 2.77 3.31%: 22.64x speedup
â–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–‹
xlib-rgba tessellate-256-100 63.05 0.80% -> 2.79 3.21%: 22.58x speedup
â–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–‹
image-rgb tessellate-256-100 63.02 0.72% -> 2.82 2.61%: 22.38x speedup
â–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–
xlib-rgb tessellate-256-100 63.28 0.92% -> 2.88 1.88%: 21.96x speedup
â–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆâ–ˆ
image-rgba tessellate-64-100 2.33 2.65% -> 0.40 3.53%: 5.90x speedup
â–ˆâ–ˆâ–ˆâ–ˆâ–‰
image-rgb tessellate-64-100 2.36 2.75% -> 0.40 3.14%: 5.83x speedup
â–ˆâ–ˆâ–ˆâ–ˆâ–‰
xlib-rgb tessellate-64-100 2.46 1.67% -> 0.49 2.67%: 5.05x speedup
â–ˆâ–ˆâ–ˆâ–ˆ
xlib-rgba tessellate-64-100 2.43 2.34% -> 0.49 1.43%: 5.00x speedup
â–ˆâ–ˆâ–ˆâ–ˆ
image-rgba tessellate-16-100 0.13 1.39% -> 0.06 3.59%: 2.11x speedup
â–ˆâ–
image-rgb tessellate-16-100 0.13 1.65% -> 0.06 2.26%: 2.04x speedup
â–ˆ
xlib-rgba zrusin_another_tessellate-415 15.35 1.81% -> 8.92 1.57%: 1.72x 
speedup
â–Š
image-rgb zrusin_another_tessellate-415 15.06 2.28% -> 8.83 2.98%: 1.71x 
speedup
â–Š
image-rgba zrusin_another_tessellate-415 14.99 1.77% -> 8.80 1.73%: 
1.70x speedup
â–Š
xlib-rgb zrusin_another_tessellate-415 15.36 1.48% -> 9.05 2.08%: 1.70x 
speedup
â–Š
xlib-rgba tessellate-16-100 0.21 1.11% -> 0.14 1.91%: 1.53x speedup
â–Œ
xlib-rgb tessellate-16-100 0.22 1.15% -> 0.15 0.80%: 1.45x speedup
â–Œ
image-rgb zrusin_another_fill-415 22.78 1.34% -> 15.78 1.28%: 1.44x speedup
â–Œ
image-rgba zrusin_another_fill-415 22.69 1.26% -> 15.73 1.50%: 1.44x speedup
â–Œ
xlib-rgba zrusin_another_fill-415 30.73 0.99% -> 23.10 0.82%: 1.33x speedup
â–
xlib-rgb zrusin_another_fill-415 31.03 0.90% -> 23.48 1.02%: 1.32x speedup
â–


I hope the patch is correct and we can benefit from those speed gains...

Regards,

--
Rafael Villar Burke
www.rvburke.com

 From ea04d05739a46e219a25b6f76978cf1337051e84 Mon Sep 17 00:00:00 2001
From: Rafael Villar Burke <pachi at rvburke.com>
Date: Mon, 4 Dec 2006 04:20:00 +0100
Subject: [PATCH] Additional fast path tests to avoid intersection 
computation

---
src/cairo-bentley-ottmann.c | 26 ++++++++++++++++++++++++++
1 files changed, 26 insertions(+), 0 deletions(-)

diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c
index 2c0f98c..9f5291f 100644
--- a/src/cairo-bentley-ottmann.c
+++ b/src/cairo-bentley-ottmann.c
@@ -783,6 +783,29 @@ _cairo_bo_event_queue_fini (cairo_bo_event_queue_t 
*event_queue)
free (event_queue->sorted_startstop_event_ptrs);
}

+static cairo_bool_t
+_cairo_may_intersect (cairo_bo_edge_t const *edge1,
+ cairo_bo_edge_t const *edge2)
+{
+ cairo_bo_point32_t a = edge1->top;
+ cairo_bo_point32_t b = edge1->bottom;
+ cairo_bo_point32_t c = edge2->top;
+ cairo_bo_point32_t d = edge2->bottom;
+
+ int crossp_abc = (b.x - a.x)*(c.y - a.y) - (c.x - a.x)*(b.y - a.y);
+ int crossp_abd = (b.x - a.x)*(d.y - a.y) - (d.x - a.x)*(b.y - a.y);
+ int crossp_cda = (d.x - c.x)*(a.y - c.y) - (a.x - c.x)*(d.y - c.y);
+ int crossp_cdb = (d.x - c.x)*(b.y - c.y) - (b.x - c.x)*(d.y - c.y);
+
+ /* colinearity check: if colinear, return True */
+ if (crossp_abc==0 || crossp_abd==0 || crossp_cda==0 || crossp_cdb==0)
+ return TRUE;
+ /* left -> area(a,b,c)>0
+ * proper intersection check: if proper intersection return true
+ * xor(x, y) <-> !x ^!y */
+ return (!(crossp_abc>0) ^ !(crossp_abd>0)) && (!(crossp_cda>0) ^ 
!(crossp_cdb>0));
+}
+
static void
_cairo_bo_event_queue_insert_if_intersect_below_current_y 
(cairo_bo_event_queue_t *event_queue,
cairo_bo_edge_t *left,
@@ -795,6 +818,9 @@ 
_cairo_bo_event_queue_insert_if_intersect_below_current_y 
(cairo_bo_event_queue_
if (left == NULL || right == NULL)
return;

+ if (!_cairo_may_intersect (left, right))
+ return;
+
/* The names "left" and "right" here are correct descriptions of
* the order of the two edges within the active edge list. So if a
* slope comparison also puts left less than right, then we know
--
1.4.4.1
-------------- next part --------------
From ea04d05739a46e219a25b6f76978cf1337051e84 Mon Sep 17 00:00:00 2001
From: Rafael Villar Burke <pachi at rvburke.com>
Date: Mon, 4 Dec 2006 04:20:00 +0100
Subject: [PATCH] Additional fast path tests to avoid intersection computation

---
 src/cairo-bentley-ottmann.c |   26 ++++++++++++++++++++++++++
 1 files changed, 26 insertions(+), 0 deletions(-)

diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c
index 2c0f98c..9f5291f 100644
--- a/src/cairo-bentley-ottmann.c
+++ b/src/cairo-bentley-ottmann.c
@@ -783,6 +783,29 @@ _cairo_bo_event_queue_fini (cairo_bo_event_queue_t *event_queue)
 	free (event_queue->sorted_startstop_event_ptrs);
 }
 
+static cairo_bool_t
+_cairo_may_intersect (cairo_bo_edge_t const *edge1,
+        cairo_bo_edge_t const *edge2)
+{
+    cairo_bo_point32_t a = edge1->top;
+    cairo_bo_point32_t b = edge1->bottom;
+    cairo_bo_point32_t c = edge2->top;
+    cairo_bo_point32_t d = edge2->bottom;
+
+    int crossp_abc = (b.x - a.x)*(c.y - a.y) - (c.x - a.x)*(b.y - a.y);
+    int crossp_abd = (b.x - a.x)*(d.y - a.y) - (d.x - a.x)*(b.y - a.y);
+    int crossp_cda = (d.x - c.x)*(a.y - c.y) - (a.x - c.x)*(d.y - c.y);
+    int crossp_cdb = (d.x - c.x)*(b.y - c.y) - (b.x - c.x)*(d.y - c.y);
+
+    /* colinearity check: if colinear, return True */
+    if (crossp_abc==0 || crossp_abd==0 || crossp_cda==0 || crossp_cdb==0)
+        return TRUE;
+    /* left -> area(a,b,c)>0
+     * proper intersection check: if proper intersection return true
+     * xor(x, y) <-> !x ^!y */
+    return (!(crossp_abc>0) ^ !(crossp_abd>0)) && (!(crossp_cda>0) ^ !(crossp_cdb>0));
+}
+
 static void
 _cairo_bo_event_queue_insert_if_intersect_below_current_y (cairo_bo_event_queue_t	*event_queue,
 							   cairo_bo_edge_t	*left,
@@ -795,6 +818,9 @@ _cairo_bo_event_queue_insert_if_intersect_below_current_y (cairo_bo_event_queue_
     if (left == NULL || right == NULL)
 	return;
 
+    if (!_cairo_may_intersect (left, right))
+    return;
+
     /* The names "left" and "right" here are correct descriptions of
      * the order of the two edges within the active edge list. So if a
      * slope comparison also puts left less than right, then we know
-- 
1.4.4.1

