[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.

11 files changed, 631 insertions, 116 deletions

diff --git a/src/Makefile.sources b/src/Makefile.sources
index b8404e3d..0e7b54b5 100644
--- a/src/Makefile.sources
+++ b/src/Makefile.sources
@@ -99,6 +99,7 @@ cairo_sources = \
 	cairo-atomic.c \
 	cairo-base85-stream.c \
 	cairo-bentley-ottmann.c \
+	cairo-bentley-ottmann-rectilinear.c \
 	cairo.c \
 	cairo-cache.c \
 	cairo-clip.c \
diff --git a/src/cairo-bentley-ottmann-rectilinear.c b/src/cairo-bentley-ottmann-rectilinear.c
new file mode 100644
index 00000000..c7e738b6
--- /dev/null
+++ b/src/cairo-bentley-ottmann-rectilinear.c
@@ -0,0 +1,582 @@
+/*
+ * Copyright © 2004 Carl Worth
+ * Copyright © 2006 Red Hat, Inc.
+ * Copyright © 2008 Chris Wilson
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it either under the terms of the GNU Lesser General Public
+ * License version 2.1 as published by the Free Software Foundation
+ * (the "LGPL") or, at your option, under the terms of the Mozilla
+ * Public License Version 1.1 (the "MPL"). If you do not alter this
+ * notice, a recipient may use your version of this file under either
+ * the MPL or the LGPL.
+ *
+ * You should have received a copy of the LGPL along with this library
+ * in the file COPYING-LGPL-2.1; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ * You should have received a copy of the MPL along with this library
+ * in the file COPYING-MPL-1.1
+ *
+ * The contents of this file are subject to the Mozilla Public License
+ * Version 1.1 (the "License"); you may not use this file except in
+ * compliance with the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
+ * OF ANY KIND, either express or implied. See the LGPL or the MPL for
+ * the specific language governing rights and limitations.
+ *
+ * The Original Code is the cairo graphics library.
+ *
+ * The Initial Developer of the Original Code is Carl Worth
+ *
+ * Contributor(s):
+ *	Carl D. Worth <cworth@cworth.org>
+ *	Chris Wilson <chris@chris-wilson.co.uk>
+ */
+
+/* Provide definitions for standalone compilation */
+#include "cairoint.h"
+
+#include "cairo-combsort-private.h"
+
+typedef struct _cairo_bo_edge cairo_bo_edge_t;
+typedef struct _cairo_bo_trap cairo_bo_trap_t;
+
+/* A deferred trapezoid of an edge */
+struct _cairo_bo_trap {
+    cairo_bo_edge_t *right;
+    int32_t top;
+};
+
+struct _cairo_bo_edge {
+    cairo_edge_t edge;
+    cairo_bo_edge_t *prev;
+    cairo_bo_edge_t *next;
+    cairo_bo_trap_t deferred_trap;
+};
+
+typedef enum {
+    CAIRO_BO_EVENT_TYPE_START,
+    CAIRO_BO_EVENT_TYPE_STOP
+} cairo_bo_event_type_t;
+
+typedef struct _cairo_bo_event {
+    cairo_bo_event_type_t type;
+    cairo_point_t point;
+    cairo_bo_edge_t *edge;
+} cairo_bo_event_t;
+
+typedef struct _cairo_bo_sweep_line {
+    cairo_bo_event_t **events;
+    cairo_bo_edge_t *head;
+    cairo_bo_edge_t *stopped;
+    int32_t current_y;
+    cairo_bo_edge_t *current_edge;
+} cairo_bo_sweep_line_t;
+
+static inline int
+_cairo_point_compare (const cairo_point_t *a,
+		      const cairo_point_t *b)
+{
+    int cmp;
+
+    cmp = a->y - b->y;
+    if (likely (cmp))
+	return cmp;
+
+    return a->x - b->x;
+}
+
+static inline int
+_cairo_bo_edge_compare (const cairo_bo_edge_t	*a,
+			const cairo_bo_edge_t	*b)
+{
+    int cmp;
+
+    cmp = a->edge.line.p1.x - b->edge.line.p1.x;
+    if (likely (cmp))
+	return cmp;
+
+    return b->edge.bottom - a->edge.bottom;
+}
+
+static inline int
+cairo_bo_event_compare (const cairo_bo_event_t *a,
+			const cairo_bo_event_t *b)
+{
+    int cmp;
+
+    cmp = _cairo_point_compare (&a->point, &b->point);
+    if (likely (cmp))
+	return cmp;
+
+    cmp = a->type - b->type;
+    if (cmp)
+	return cmp;
+
+    return a - b;
+}
+
+static inline cairo_bo_event_t *
+_cairo_bo_event_dequeue (cairo_bo_sweep_line_t *sweep_line)
+{
+    return *sweep_line->events++;
+}
+
+CAIRO_COMBSORT_DECLARE (_cairo_bo_event_queue_sort,
+			cairo_bo_event_t *,
+			cairo_bo_event_compare)
+
+static void
+_cairo_bo_sweep_line_init (cairo_bo_sweep_line_t *sweep_line,
+			   cairo_bo_event_t	**events,
+			   int			  num_events)
+{
+    _cairo_bo_event_queue_sort (events, num_events);
+    events[num_events] = NULL;
+    sweep_line->events = events;
+
+    sweep_line->head = NULL;
+    sweep_line->current_y = INT32_MIN;
+    sweep_line->current_edge = NULL;
+}
+
+static void
+_cairo_bo_sweep_line_insert (cairo_bo_sweep_line_t	*sweep_line,
+			     cairo_bo_edge_t		*edge)
+{
+    if (sweep_line->current_edge != NULL) {
+	cairo_bo_edge_t *prev, *next;
+	int cmp;
+
+	cmp = _cairo_bo_edge_compare (sweep_line->current_edge, edge);
+	if (cmp < 0) {
+	    prev = sweep_line->current_edge;
+	    next = prev->next;
+	    while (next != NULL && _cairo_bo_edge_compare (next, edge) < 0)
+		prev = next, next = prev->next;
+
+	    prev->next = edge;
+	    edge->prev = prev;
+	    edge->next = next;
+	    if (next != NULL)
+		next->prev = edge;
+	} else if (cmp > 0) {
+	    next = sweep_line->current_edge;
+	    prev = next->prev;
+	    while (prev != NULL && _cairo_bo_edge_compare (prev, edge) > 0)
+		next = prev, prev = next->prev;
+
+	    next->prev = edge;
+	    edge->next = next;
+	    edge->prev = prev;
+	    if (prev != NULL)
+		prev->next = edge;
+	    else
+		sweep_line->head = edge;
+	} else {
+	    prev = sweep_line->current_edge;
+	    edge->prev = prev;
+	    edge->next = prev->next;
+	    if (prev->next != NULL)
+		prev->next->prev = edge;
+	    prev->next = edge;
+	}
+    } else {
+	sweep_line->head = edge;
+    }
+
+    sweep_line->current_edge = edge;
+}
+
+static void
+_cairo_bo_sweep_line_delete (cairo_bo_sweep_line_t	*sweep_line,
+			     cairo_bo_edge_t	*edge)
+{
+    if (edge->prev != NULL)
+	edge->prev->next = edge->next;
+    else
+	sweep_line->head = edge->next;
+
+    if (edge->next != NULL)
+	edge->next->prev = edge->prev;
+
+    if (sweep_line->current_edge == edge)
+	sweep_line->current_edge = edge->prev ? edge->prev : edge->next;
+}
+
+static inline cairo_bool_t
+edges_collinear (const cairo_bo_edge_t *a, const cairo_bo_edge_t *b)
+{
+    return a->edge.line.p1.x == b->edge.line.p1.x;
+}
+
+static cairo_status_t
+_cairo_bo_edge_end_trap (cairo_bo_edge_t	*left,
+			 int32_t		 bot,
+			 cairo_traps_t	        *traps)
+{
+    cairo_bo_trap_t *trap = &left->deferred_trap;
+
+    /* Only emit (trivial) non-degenerate trapezoids with positive height. */
+    if (likely (trap->top < bot)) {
+	_cairo_traps_add_trap (traps,
+			       trap->top, bot,
+			       &left->edge.line, &trap->right->edge.line);
+    }
+
+    trap->right = NULL;
+
+    return _cairo_traps_status (traps);
+}
+
+/* Start a new trapezoid at the given top y coordinate, whose edges
+ * are `edge' and `edge->next'. If `edge' already has a trapezoid,
+ * then either add it to the traps in `traps', if the trapezoid's
+ * right edge differs from `edge->next', or do nothing if the new
+ * trapezoid would be a continuation of the existing one. */
+static inline cairo_status_t
+_cairo_bo_edge_start_or_continue_trap (cairo_bo_edge_t	*left,
+				       cairo_bo_edge_t  *right,
+				       int               top,
+				       cairo_traps_t	*traps)
+{
+    cairo_status_t status;
+
+    if (left->deferred_trap.right == right)
+	return CAIRO_STATUS_SUCCESS;
+
+    if (left->deferred_trap.right != NULL) {
+	if (right != NULL && edges_collinear (left->deferred_trap.right, right))
+	{
+	    /* continuation on right, so just swap edges */
+	    left->deferred_trap.right = right;
+	    return CAIRO_STATUS_SUCCESS;
+	}
+
+	status = _cairo_bo_edge_end_trap (left, top, traps);
+	if (unlikely (status))
+	    return status;
+    }
+
+    if (right != NULL && ! edges_collinear (left, right)) {
+	left->deferred_trap.top = top;
+	left->deferred_trap.right = right;
+    }
+
+    return CAIRO_STATUS_SUCCESS;
+}
+
+static inline cairo_status_t
+_active_edges_to_traps (cairo_bo_edge_t		*left,
+			int32_t			 top,
+			cairo_fill_rule_t	 fill_rule,
+			cairo_traps_t	        *traps)
+{
+    cairo_bo_edge_t *right;
+    cairo_status_t status;
+
+    if (fill_rule == CAIRO_FILL_RULE_WINDING) {
+	while (left != NULL) {
+	    int in_out;
+
+	    /* Greedily search for the closing edge, so that we generate the
+	     * maximal span width with the minimal number of trapezoids.
+	     */
+	    in_out = left->edge.dir;
+
+	    /* Check if there is a co-linear edge with an existing trap */
+	    right = left->next;
+	    if (left->deferred_trap.right == NULL) {
+		while (right != NULL && right->deferred_trap.right == NULL)
+		    right = right->next;
+
+		if (right != NULL && edges_collinear (left, right)) {
+		    /* continuation on left */
+		    left->deferred_trap = right->deferred_trap;
+		    right->deferred_trap.right = NULL;
+		}
+	    }
+
+	    /* End all subsumed traps */
+	    right = left->next;
+	    while (right != NULL) {
+		if (right->deferred_trap.right != NULL) {
+		    status = _cairo_bo_edge_end_trap (right, top, traps);
+		    if (unlikely (status))
+			return status;
+		}
+
+		in_out += right->edge.dir;
+		if (in_out == 0) {
+		    /* skip co-linear edges */
+		    if (right->next == NULL ||
+			! edges_collinear (right, right->next))
+		    {
+			break;
+		    }
+		}
+
+		right = right->next;
+	    }
+
+	    status = _cairo_bo_edge_start_or_continue_trap (left, right,
+							    top, traps);
+	    if (unlikely (status))
+		return status;
+
+	    left = right;
+	    if (left != NULL)
+		left = left->next;
+	}
+    } else {
+	while (left != NULL) {
+	    int in_out = 0;
+
+	    right = left->next;
+	    while (right != NULL) {
+		if (right->deferred_trap.right != NULL) {
+		    status = _cairo_bo_edge_end_trap (right, top, traps);
+		    if (unlikely (status))
+			return status;
+		}
+
+		if ((in_out++ & 1) == 0) {
+		    cairo_bo_edge_t *next;
+		    cairo_bool_t skip = FALSE;
+
+		    /* skip co-linear edges */
+		    next = right->next;
+		    if (next != NULL)
+			skip = edges_collinear (right, next);
+
+		    if (! skip)
+			break;
+		}
+
+		right = right->next;
+	    }
+
+	    status = _cairo_bo_edge_start_or_continue_trap (left, right,
+							    top, traps);
+	    if (unlikely (status))
+		return status;
+
+	    left = right;
+	    if (left != NULL)
+		left = left->next;
+	}
+    }
+
+    return CAIRO_STATUS_SUCCESS;
+}
+
+static cairo_status_t
+_cairo_bentley_ottmann_tessellate_rectilinear (cairo_bo_event_t   **start_events,
+					       int			 num_events,
+					       cairo_fill_rule_t	 fill_rule,
+					       cairo_traps_t	*traps)
+{
+    cairo_bo_sweep_line_t sweep_line;
+    cairo_bo_event_t *event;
+    cairo_status_t status;
+
+    _cairo_bo_sweep_line_init (&sweep_line, start_events, num_events);
+
+    while ((event = _cairo_bo_event_dequeue (&sweep_line))) {
+	if (event->point.y != sweep_line.current_y) {
+	    status = _active_edges_to_traps (sweep_line.head,
+					     sweep_line.current_y,
+					     fill_rule, traps);
+	    if (unlikely (status))
+		return status;
+
+	    sweep_line.current_y = event->point.y;
+	}
+
+	switch (event->type) {
+	case CAIRO_BO_EVENT_TYPE_START:
+	    _cairo_bo_sweep_line_insert (&sweep_line, event->edge);
+	    break;
+
+	case CAIRO_BO_EVENT_TYPE_STOP:
+	    _cairo_bo_sweep_line_delete (&sweep_line, event->edge);
+
+	    if (event->edge->deferred_trap.right != NULL) {
+		status = _cairo_bo_edge_end_trap (event->edge,
+						  sweep_line.current_y,
+						  traps);
+		if (unlikely (status))
+		    return status;
+	    }
+
+	    break;
+	}
+    }
+
+    return CAIRO_STATUS_SUCCESS;
+}
+
+cairo_status_t
+_cairo_bentley_ottmann_tessellate_rectilinear_polygon (cairo_traps_t	 *traps,
+						       const cairo_polygon_t *polygon,
+						       cairo_fill_rule_t	  fill_rule)
+{
+    cairo_status_t status;
+    cairo_bo_event_t stack_events[CAIRO_STACK_ARRAY_LENGTH (cairo_bo_event_t)];
+    cairo_bo_event_t *events;
+    cairo_bo_event_t *stack_event_ptrs[ARRAY_LENGTH (stack_events) + 1];
+    cairo_bo_event_t **event_ptrs;
+    cairo_bo_edge_t stack_edges[ARRAY_LENGTH (stack_events)];
+    cairo_bo_edge_t *edges;
+    int num_events;
+    int i, j;
+
+    if (unlikely (polygon->num_edges == 0))
+	return CAIRO_STATUS_SUCCESS;
+
+    num_events = 2 * polygon->num_edges;
+
+    events = stack_events;
+    event_ptrs = stack_event_ptrs;
+    edges = stack_edges;
+    if (num_events > ARRAY_LENGTH (stack_events)) {
+	events = _cairo_malloc_ab_plus_c (num_events,
+					  sizeof (cairo_bo_event_t) +
+					  sizeof (cairo_bo_edge_t) +
+					  sizeof (cairo_bo_event_t *),
+					  sizeof (cairo_bo_event_t *));
+	if (unlikely (events == NULL))
+	    return _cairo_error (CAIRO_STATUS_NO_MEMORY);
+
+	event_ptrs = (cairo_bo_event_t **) (events + num_events);
+	edges = (cairo_bo_edge_t *) (event_ptrs + num_events + 1);
+    }
+
+    for (i = j = 0; i < polygon->num_edges; i++) {
+	edges[i].edge = polygon->edges[i];
+	edges[i].deferred_trap.right = NULL;
+	edges[i].prev = NULL;
+	edges[i].next = NULL;
+
+	event_ptrs[j] = &events[j];
+	events[j].type = CAIRO_BO_EVENT_TYPE_START;
+	events[j].point.y = polygon->edges[i].top;
+	events[j].point.x = polygon->edges[i].line.p1.x;
+	events[j].edge = &edges[i];
+	j++;
+
+	event_ptrs[j] = &events[j];
+	events[j].type = CAIRO_BO_EVENT_TYPE_STOP;
+	events[j].point.y = polygon->edges[i].bottom;
+	events[j].point.x = polygon->edges[i].line.p1.x;
+	events[j].edge = &edges[i];
+	j++;
+    }
+
+    status = _cairo_bentley_ottmann_tessellate_rectilinear (event_ptrs, j,
+							    fill_rule, traps);
+    if (events != stack_events)
+	free (events);
+
+    traps->is_rectilinear = TRUE;
+
+    return status;
+}
+
+cairo_status_t
+_cairo_bentley_ottmann_tessellate_rectilinear_traps (cairo_traps_t *traps,
+						     cairo_fill_rule_t fill_rule)
+{
+    cairo_bo_event_t stack_events[CAIRO_STACK_ARRAY_LENGTH (cairo_bo_event_t)];
+    cairo_bo_event_t *events;
+    cairo_bo_event_t *stack_event_ptrs[ARRAY_LENGTH (stack_events) + 1];
+    cairo_bo_event_t **event_ptrs;
+    cairo_bo_edge_t stack_edges[ARRAY_LENGTH (stack_events)];
+    cairo_bo_edge_t *edges;
+    cairo_status_t status;
+    int i, j, k;
+
+    if (unlikely (traps->num_traps == 0))
+	return CAIRO_STATUS_SUCCESS;
+
+    assert (traps->is_rectilinear);
+
+    i = 4 * traps->num_traps;
+
+    events = stack_events;
+    event_ptrs = stack_event_ptrs;
+    edges = stack_edges;
+    if (i > ARRAY_LENGTH (stack_events)) {
+	events = _cairo_malloc_ab_plus_c (i,
+					  sizeof (cairo_bo_event_t) +
+					  sizeof (cairo_bo_edge_t) +
+					  sizeof (cairo_bo_event_t *),
+					  sizeof (cairo_bo_event_t *));
+	if (unlikely (events == NULL))
+	    return _cairo_error (CAIRO_STATUS_NO_MEMORY);
+
+	event_ptrs = (cairo_bo_event_t **) (events + i);
+	edges = (cairo_bo_edge_t *) (event_ptrs + i + 1);
+    }
+
+    for (i = j = k = 0; i < traps->num_traps; i++) {
+	edges[k].edge.top = traps->traps[i].top;
+	edges[k].edge.bottom = traps->traps[i].bottom;
+	edges[k].edge.line = traps->traps[i].left;
+	edges[k].edge.dir = 1;
+	edges[k].deferred_trap.right = NULL;
+	edges[k].prev = NULL;
+	edges[k].next = NULL;
+
+	event_ptrs[j] = &events[j];
+	events[j].type = CAIRO_BO_EVENT_TYPE_START;
+	events[j].point.y = traps->traps[i].top;
+	events[j].point.x = traps->traps[i].left.p1.x;
+	events[j].edge = &edges[k];
+	j++;
+
+	event_ptrs[j] = &events[j];
+	events[j].type = CAIRO_BO_EVENT_TYPE_STOP;
+	events[j].point.y = traps->traps[i].bottom;
+	events[j].point.x = traps->traps[i].left.p1.x;
+	events[j].edge = &edges[k];
+	j++;
+	k++;
+
+	edges[k].edge.top = traps->traps[i].top;
+	edges[k].edge.bottom = traps->traps[i].bottom;
+	edges[k].edge.line = traps->traps[i].right;
+	edges[k].edge.dir = -1;
+	edges[k].deferred_trap.right = NULL;
+	edges[k].prev = NULL;
+	edges[k].next = NULL;
+
+	event_ptrs[j] = &events[j];
+	events[j].type = CAIRO_BO_EVENT_TYPE_START;
+	events[j].point.y = traps->traps[i].top;
+	events[j].point.x = traps->traps[i].right.p1.x;
+	events[j].edge = &edges[k];
+	j++;
+
+	event_ptrs[j] = &events[j];
+	events[j].type = CAIRO_BO_EVENT_TYPE_STOP;
+	events[j].point.y = traps->traps[i].bottom;
+	events[j].point.x = traps->traps[i].right.p1.x;
+	events[j].edge = &edges[k];
+	j++;
+	k++;
+    }
+
+    _cairo_traps_clear (traps);
+    status = _cairo_bentley_ottmann_tessellate_rectilinear (event_ptrs, j,
+							    fill_rule,
+							    traps);
+    traps->is_rectilinear = TRUE;
+
+    if (events != stack_events)
+	free (events);
+
+    return status;
+}
diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c
index 3d3a3d60..99f4655d 100644
--- a/src/cairo-bentley-ottmann.c
+++ b/src/cairo-bentley-ottmann.c
@@ -2002,7 +2002,8 @@ _compute_clipped_trapezoid_edges (const cairo_traps_t *traps,
 }
 
 cairo_status_t
-_cairo_bentley_ottmann_tessellate_traps (cairo_traps_t *traps)
+_cairo_bentley_ottmann_tessellate_traps (cairo_traps_t *traps,
+					 cairo_fill_rule_t fill_rule)
 {
     int intersections;
     cairo_status_t status;
@@ -2054,7 +2055,7 @@ _cairo_bentley_ottmann_tessellate_traps (cairo_traps_t *traps)
     _cairo_traps_clear (traps);
     status = _cairo_bentley_ottmann_tessellate_bo_edges (event_ptrs,
 							 num_events,
-							 CAIRO_FILL_RULE_WINDING,
+							 fill_rule,
 							 traps,
 							 &intersections);
 
diff --git a/src/cairo-combsort-private.h b/src/cairo-combsort-private.h
index d2fbb72b..ce31257e 100644
--- a/src/cairo-combsort-private.h
+++ b/src/cairo-combsort-private.h
@@ -56,7 +56,7 @@ NAME (TYPE *base, unsigned int nmemb) \
   int swapped; \
   do { \
       gap = _cairo_combsort_newgap (gap); \
-      swapped = 0; \
+      swapped = gap > 1; \
       for (i = 0; i < nmemb-gap ; i++) { \
 	  j = i + gap; \
 	  if (CMP (base[i], base[j]) > 0 ) { \
@@ -67,5 +67,5 @@ NAME (TYPE *base, unsigned int nmemb) \
 	      swapped = 1; \
 	  } \
       } \
-  } while (gap > 1 || swapped); \
+  } while (swapped); \
 }
diff --git a/src/cairo-path-fill.c b/src/cairo-path-fill.c
index 46148cf5..5b82a400 100644
--- a/src/cairo-path-fill.c
+++ b/src/cairo-path-fill.c
@@ -155,14 +155,6 @@ _cairo_path_fixed_fill_to_traps (const cairo_path_fixed_t *path,
     cairo_polygon_t polygon;
     cairo_status_t status;
 
-    if (path->is_rectilinear) {
-	status = _cairo_path_fixed_fill_rectilinear_to_traps (path,
-							      fill_rule,
-							      traps);
-	if (status != CAIRO_INT_STATUS_UNSUPPORTED)
-	    return status;
-    }
-
     _cairo_polygon_init (&polygon);
     status = _cairo_path_fixed_fill_to_polygon (path,
 						tolerance,
@@ -170,15 +162,21 @@ _cairo_path_fixed_fill_to_traps (const cairo_path_fixed_t *path,
     if (unlikely (status))
 	goto CLEANUP;
 
-    status = _cairo_bentley_ottmann_tessellate_polygon (traps, &polygon,
-							fill_rule);
+    if (path->is_rectilinear) {
+	status = _cairo_bentley_ottmann_tessellate_rectilinear_polygon (traps,
+									&polygon,
+									fill_rule);
+    } else {
+	status = _cairo_bentley_ottmann_tessellate_polygon (traps,
+							    &polygon,
+							    fill_rule);
+    }
 
   CLEANUP:
     _cairo_polygon_fini (&polygon);
     return status;
 }
 
-
 /* This special-case filler supports only a path that describes a
  * device-axis aligned rectangle. It exists to avoid the overhead of
  * the general tessellator when drawing very common rectangles.
@@ -186,86 +184,6 @@ _cairo_path_fixed_fill_to_traps (const cairo_path_fixed_t *path,
  * If the path described anything but a device-axis aligned rectangle,
  * this function will return %CAIRO_INT_STATUS_UNSUPPORTED.
  */
-cairo_int_status_t
-_cairo_path_fixed_fill_rectilinear_to_traps (const cairo_path_fixed_t	*path,
-					     cairo_fill_rule_t	 fill_rule,
-					     cairo_traps_t		*traps)
-{
-    cairo_box_t box;
-
-    assert (path->is_rectilinear);
-
-    if (_cairo_path_fixed_is_box (path, &box)) {
-	if (box.p1.x > box.p2.x) {
-	    cairo_fixed_t t;
-
-	    t = box.p1.x;
-	    box.p1.x = box.p2.x;
-	    box.p2.x = t;
-	}
-
-	if (box.p1.y > box.p2.y) {
-	    cairo_fixed_t t;
-
-	    t = box.p1.y;
-	    box.p1.y = box.p2.y;
-	    box.p2.y = t;
-	}
-
-	return _cairo_traps_tessellate_rectangle (traps, &box.p1, &box.p2);
-    } else if (fill_rule == CAIRO_FILL_RULE_WINDING) {
-	cairo_path_fixed_iter_t iter;
-	int last_cw = -1;
-
-	/* Support a series of rectangles as can be expected to describe a
-	 * GdkRegion clip region during exposes.
-	 */
-	_cairo_path_fixed_iter_init (&iter, path);
-	while (_cairo_path_fixed_iter_is_fill_box (&iter, &box)) {
-	    cairo_status_t status;
-	    int cw = 0;
-
-	    if (box.p1.x > box.p2.x) {
-		cairo_fixed_t t;
-
-		t = box.p1.x;
-		box.p1.x = box.p2.x;
-		box.p2.x = t;
-
-		cw = ! cw;
-	    }
-
-	    if (box.p1.y > box.p2.y) {
-		cairo_fixed_t t;
-
-		t = box.p1.y;
-		box.p1.y = box.p2.y;
-		box.p2.y = t;
-
-		cw = ! cw;
-	    }
-
-	    if (last_cw < 0) {
-		last_cw = cw;
-	    } else if (last_cw != cw) {
-		_cairo_traps_clear (traps);
-		return CAIRO_INT_STATUS_UNSUPPORTED;
-	    }
-
-	    status = _cairo_traps_tessellate_rectangle (traps,
-							&box.p1, &box.p2);
-	    if (unlikely (status))
-		return status;
-	}
-	if (_cairo_path_fixed_iter_at_end (&iter))
-	    return CAIRO_STATUS_SUCCESS;
-
-	_cairo_traps_clear (traps);
-    }
-
-    return CAIRO_INT_STATUS_UNSUPPORTED;
-}
-
 cairo_region_t *
 _cairo_path_fixed_fill_rectilinear_to_region (const cairo_path_fixed_t	*path,
 					      cairo_fill_rule_t	 fill_rule,
diff --git a/src/cairo-path-stroke.c b/src/cairo-path-stroke.c
index 208e3903..d37c597b 100644
--- a/src/cairo-path-stroke.c
+++ b/src/cairo-path-stroke.c
@@ -2027,6 +2027,7 @@ _cairo_path_fixed_stroke_rectilinear_to_traps (const cairo_path_fixed_t	*path,
     else
 	status = _cairo_rectilinear_stroker_emit_segments (&rectilinear_stroker);
 
+    traps->is_rectilinear = 1;
 BAIL:
     _cairo_rectilinear_stroker_fini (&rectilinear_stroker);
 
diff --git a/src/cairo-surface-fallback.c b/src/cairo-surface-fallback.c
index 8f13bfbb..b97eb193 100644
--- a/src/cairo-surface-fallback.c
+++ b/src/cairo-surface-fallback.c
@@ -727,7 +727,12 @@ _clip_and_composite_trapezoids (const cairo_pattern_t *src,
 
     /* No fast path, exclude self-intersections and clip trapezoids. */
     if (traps->has_intersections) {
-	status = _cairo_bentley_ottmann_tessellate_traps (traps);
+	if (traps->is_rectilinear)
+	    status = _cairo_bentley_ottmann_tessellate_rectilinear_traps (traps,
+									  CAIRO_FILL_RULE_WINDING);
+	else
+	    status = _cairo_bentley_ottmann_tessellate_traps (traps,
+							      CAIRO_FILL_RULE_WINDING);
 	if (unlikely (status))
 	    return status;
     }
@@ -1152,20 +1157,7 @@ _cairo_surface_fallback_fill (cairo_surface_t		*surface,
     _cairo_polygon_init (&polygon);
     _cairo_polygon_limit (&polygon, &box);
 
-    if (path->is_rectilinear) {
-	status = _cairo_path_fixed_fill_rectilinear_to_traps (path,
-							      fill_rule,
-							      &traps);
-	if (likely (status == CAIRO_STATUS_SUCCESS))
-	    goto DO_TRAPS;
-
-	if (unlikely (_cairo_status_is_error (status)))
-	    goto CLEANUP;
-    }
-
-    status = _cairo_path_fixed_fill_to_polygon (path,
-						tolerance,
-						&polygon);
+    status = _cairo_path_fixed_fill_to_polygon (path, tolerance, &polygon);
     if (unlikely (status))
 	goto CLEANUP;
 
@@ -1177,6 +1169,18 @@ _cairo_surface_fallback_fill (cairo_surface_t		*surface,
 	    goto CLEANUP;
     }
 
+    if (path->is_rectilinear) {
+	status = _cairo_bentley_ottmann_tessellate_rectilinear_polygon (&traps,
+									&polygon,
+									fill_rule);
+	if (likely (status == CAIRO_STATUS_SUCCESS))
+	    goto DO_TRAPS;
+
+	if (unlikely (_cairo_status_is_error (status)))
+	    goto CLEANUP;
+    }
+
+
     if (antialias != CAIRO_ANTIALIAS_NONE &&
 	_cairo_surface_check_span_renderer (op, source, surface,
 					    antialias, NULL))
diff --git a/src/cairo-traps.c b/src/cairo-traps.c
index 5f04ce16..a5974cc2 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;
diff --git a/src/cairoint.h b/src/cairoint.h
index 439acfb8..7312f7e1 100644
--- a/src/cairoint.h
+++ b/src/cairoint.h
@@ -956,6 +956,7 @@ typedef struct _cairo_traps {
     unsigned int maybe_region : 1; /* hint: 0 implies that it cannot be */
     unsigned int has_limits : 1;
     unsigned int has_intersections : 1;
+    unsigned int is_rectilinear : 1;
 
     int num_traps;
     int traps_size;
@@ -1616,11 +1617,6 @@ _cairo_path_fixed_fill_rectilinear_to_region (const cairo_path_fixed_t	*path,
 					      cairo_fill_rule_t	 fill_rule,
 					      const cairo_rectangle_int_t *extents);
 
-cairo_private cairo_int_status_t
-_cairo_path_fixed_fill_rectilinear_to_traps (const cairo_path_fixed_t *path,
-					     cairo_fill_rule_t fill_rule,
-					     cairo_traps_t    *traps);
-
 cairo_private cairo_status_t
 _cairo_path_fixed_fill_to_traps (const cairo_path_fixed_t   *path,
 				 cairo_fill_rule_t	     fill_rule,
@@ -2377,12 +2373,22 @@ _cairo_traps_add_trap (cairo_traps_t *traps,
 		       cairo_line_t *left, cairo_line_t *right);
 
 cairo_private cairo_status_t
+_cairo_bentley_ottmann_tessellate_rectilinear_polygon (cairo_traps_t	 *traps,
+						       const cairo_polygon_t *polygon,
+						       cairo_fill_rule_t	  fill_rule);
+
+cairo_private cairo_status_t
 _cairo_bentley_ottmann_tessellate_polygon (cairo_traps_t         *traps,
 					   const cairo_polygon_t *polygon,
 					   cairo_fill_rule_t      fill_rule);
 
 cairo_private cairo_status_t
-_cairo_bentley_ottmann_tessellate_traps (cairo_traps_t *traps);
+_cairo_bentley_ottmann_tessellate_traps (cairo_traps_t *traps,
+					 cairo_fill_rule_t fill_rule);
+
+cairo_private cairo_status_t
+_cairo_bentley_ottmann_tessellate_rectilinear_traps (cairo_traps_t *traps,
+						     cairo_fill_rule_t fill_rule);
 
 cairo_private int
 _cairo_traps_contain (const cairo_traps_t *traps,
diff --git a/test/ft-text-vertical-layout-type1.ref.png b/test/ft-text-vertical-layout-type1.ref.png
index 6f0df7b3..f1c12a9f 100644
--- a/test/ft-text-vertical-layout-type1.ref.png
+++ b/test/ft-text-vertical-layout-type1.ref.png
diff --git a/test/ft-text-vertical-layout-type3.ref.png b/test/ft-text-vertical-layout-type3.ref.png
index 94048f1c..1bda421c 100644
--- a/test/ft-text-vertical-layout-type3.ref.png
+++ b/test/ft-text-vertical-layout-type3.ref.png