[cairo] cairo_in_fill optimisation

[M Joonas Pihlaja]

Hi,

We don't need to tessellate the entire path if we're only doing
hit testing at a point.  The attached patch ignores edges that
are strictly above or below the point under test.  Depending on
the polygon this can speed things up a lot.  The perf-suite
reports huge speedups in tessellation, but that's because it uses
cairo_in_fill() to trigger a complete tessellation.

That's great for just this one patch, but in general I think it
would be misleading to leave them like this.  On #cairo a new
cairo_debug_force_tessellation() function was suggested as a
means of making sure we'll get the full love of the tessellator
in perf-tests instead of relying on in_fill to do it.  If that
sounds OK to all, I'll add that too.

Joonas

Speedups
========
image-rgba  zrusin_another_tessellate-415   14.62 0.68% ->   0.39 0.26%: 37.50x speedup
image-rgba              tessellate-16-100    0.09 1.35% ->   0.02 2.77%:  4.45x speedup
image-rgba   mosaic_tessellate_curves-800  100.87 0.16% ->  38.75 0.05%:  2.60x speedup
image-rgba              tessellate-64-100    2.03 0.68% ->   0.91 0.43%:  2.22x speedup
image-rgba             tessellate-256-100   62.54 2.51% ->  29.33 0.08%:  2.08x speedup
image-rgba    mosaic_tessellate_lines-800   19.41 0.03% ->  10.91 0.32%:  1.79x speedup
-------------- next part --------------
From c9941f30cd7a68037b25e2a379d89f0071fd38b1 Mon Sep 17 00:00:00 2001
From: M Joonas Pihlaja <jpihlaja at cc.helsinki.fi>
Date: Fri, 12 Sep 2008 01:19:13 +0300
Subject: [PATCH] Speed up cairo_in_fill() by avoiding some edges while tessellating.

We don't need to tessellate edges strictly above or below the
hit-test point.
---
 src/cairo-bentley-ottmann.c |    9 +++++++++
 src/cairo-gstate.c          |    7 +++++++
 2 files changed, 16 insertions(+), 0 deletions(-)

diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c
index 8e97f1f..eec748a 100644
--- a/src/cairo-bentley-ottmann.c
+++ b/src/cairo-bentley-ottmann.c
@@ -1427,6 +1427,8 @@ _cairo_bentley_ottmann_tessellate_polygon (cairo_traps_t	 *traps,
     cairo_fixed_t ymin = 0x7FFFFFFF;
     cairo_fixed_t xmax = -0x80000000;
     cairo_fixed_t ymax = -0x80000000;
+    cairo_box_t limit;
+    cairo_bool_t has_limits = _cairo_traps_get_limit(traps, &limit);
     int num_bo_edges;
     int i;
 
@@ -1471,6 +1473,13 @@ _cairo_bentley_ottmann_tessellate_polygon (cairo_traps_t	 *traps,
 	cairo_point_t top = polygon->edges[i].edge.p1;
 	cairo_point_t bot = polygon->edges[i].edge.p2;
 
+        /* Discard the edge if traps doesn't care. */
+        if (has_limits) {
+                /* Strictly above or below the limits? */
+                if (bot.y <= limit.p1.y || top.y >= limit.p2.y)
+                        continue;
+        }
+
 	/* Offset coordinates into the non-negative range. */
 	top.x -= xmin;
 	top.y -= ymin;
diff --git a/src/cairo-gstate.c b/src/cairo-gstate.c
index 2980770..0c51371 100644
--- a/src/cairo-gstate.c
+++ b/src/cairo-gstate.c
@@ -1012,10 +1012,17 @@ _cairo_gstate_in_fill (cairo_gstate_t	  *gstate,
 {
     cairo_status_t status;
     cairo_traps_t traps;
+    cairo_box_t limit;
 
     _cairo_gstate_user_to_backend (gstate, &x, &y);
 
+    limit.p1.x = _cairo_fixed_from_double (x) - 1;
+    limit.p1.y = _cairo_fixed_from_double (y) - 1;
+    limit.p2.x = limit.p1.x + 2;
+    limit.p2.y = limit.p1.y + 2;
+
     _cairo_traps_init (&traps);
+    _cairo_traps_limit (&traps, &limit);
 
     status = _cairo_path_fixed_fill_to_traps (path,
 					      gstate->fill_rule,
-- 
1.4.4.4