[cairo] [PATCH] Performance patch for bo intersections

[Baz]

Ok, here's a tidied up patch. Unfortunately theres no way to add this
as an attachment without gmail mangling it, nor can I add in the raw
results of perf-diff without it switching modes; here's the top figures:

xlib-rgba    paint_solid_rgba_source-256    0.48 5.60% ->   0.22
5.30%:  2.20x speedup
xlib-rgba      paint_solid_rgba_over-256   13.75 5.36% ->   7.97
1.04%:  1.72x speedup
xlib-rgba       paint_solid_rgb_over-256    0.38 8.73% ->   0.22
17.42%:  1.71x speedup
...
image-rgba  zrusin_another_tessellate-415   17.11 0.71% ->  14.87
0.55%:  1.15x speedup
image-rgba                  world_map-800  567.51 0.19% -> 519.48
0.17%:  1.09x speedup
...
 xlib-rgb       text_similar_rgb_over-256   21.07 8.27% ->  25.58
3.88%:  1.21x slowdown
 xlib-rgb      text_solid_rgba_source-64     8.73 6.14% ->   9.90
0.88%:  1.13x slowdown
(etc)

I can't explain those regressions - they don't seem to hit the changed
code? Running text_similar_rgb_over with 10x more iterations seems to
show less of a slowdown.

And the patch:
====
Prevent full intersection checks being done when the bounding boxes
of line segments do not overlap; also prevent the intersection check
when the intersection would be at a segment endpoint.

---
commit c47a09fe2b00e2e61a10ce1f2107863708b3b82a
tree 42c9be88f3685957725886e491e1f908bf4363bc
parent 41e01d95edd7eb573a8b79acd0ab2b9de8cdab40
author Brian Ewins <Brian.Ewins at gmail.com> Tue, 12 Dec 2006 16:28:03 +0000
committer Brian Ewins <Brian.Ewins at gmail.com> Tue, 12 Dec 2006 16:28:03 +0000

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

diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c
index 4a72a8d..d64fbe4 100644
--- a/src/cairo-bentley-ottmann.c
+++ b/src/cairo-bentley-ottmann.c
@@ -804,9 +804,54 @@ _cairo_bo_event_queue_insert_if_intersec
     cairo_bo_status_t status;
     cairo_bo_point32_t intersection;
     cairo_bo_event_t event;
+    cairo_bo_point32_t* l1;
+    cairo_bo_point32_t* r1;
+    cairo_bo_point32_t* l2;
+    cairo_bo_point32_t* r2;

     if (left == NULL || right == NULL)
        return;
+
+    /* Edges whose bounding boxes don't overlap can't intersect.
+     * Test for vertical overlap.
+     */
+    if (left->bottom.y < right->top.y || right->bottom.y < left->top.y)
+      return;
+
+    /* Sort the points left-to-right. This simplifies the
+     * horizontal overlap and coincident endpoint tests.
+     */
+    if (left->top.x < left->bottom.x) {
+      l1 = &(left->top);
+      r1 = &(left->bottom);
+    } else {
+      l1 = &(left->bottom);
+      r1 = &(left->top);
+    }
+
+    if (right->top.x < right->bottom.x) {
+      l2 = &(right->top);
+      r2 = &(right->bottom);
+    } else {
+      l2 = &(right->bottom);
+      r2 = &(right->top);
+    }
+
+    /* Test for horizontal overlap */
+    if (r1->x < l2->x || r2->x < l1->x) {
+      return;
+    }
+
+    /* End points cannot be intersections. However, coincident
+     * endpoints are common in polygonal drawings.
+     */
+    if (r1->x == l2->x
+       && ((r1->y == l2->y)
+           || (l1->x == l2->x && l1->y == l2->y)
+           || (r1->x == r2->x && r1->y == r2->y)
+           || (l1->x == r2->x &&  l1->y == r2->y))) {
+      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