[tessellator] Special case rectilinear tessellation

For the frequent cases where we know in advance that we are dealing with a
rectilinear path, but can not use the simple region code, implement a
variant of the Bentley-Ottmann tessellator. The advantages here are that
edge comparison is very simple (we only have vertical edges) and there are
no intersection, though possible overlaps. The idea is the same, maintain
a y-x sorted queue of start/stop events that demarcate traps and sweep
through the active edges at each event, looking for completed traps.

The motivation for this was noticing a performance regression in
box-fill-outline with the self-intersection work:

  1.9.2 to HEAD^: 3.66x slowdown
  HEAD^ to HEAD:  5.38x speedup
  1.9.2 to HEAD:  1.57x speedup

The cause of which was choosing to use spans instead of the region handling
code, as the complex polygon was no longer being tessellated.

1 files changed, 2 insertions, 0 deletions

diff --git a/src/cairo-traps.c b/src/cairo-traps.c
index 5f04ce160..a5974cc23 100644
--- a/src/cairo-traps.c
+++ b/src/cairo-traps.c
@@ -51,6 +51,7 @@ _cairo_traps_init (cairo_traps_t *traps)
     traps->status = CAIRO_STATUS_SUCCESS;
 
     traps->maybe_region = 1;
+    traps->is_rectilinear = 0;
 
     traps->num_traps = 0;
 
@@ -76,6 +77,7 @@ _cairo_traps_clear (cairo_traps_t *traps)
     traps->status = CAIRO_STATUS_SUCCESS;
 
     traps->maybe_region = 1;
+    traps->is_rectilinear = 0;
 
     traps->num_traps = 0;
     traps->has_intersections = FALSE;