[clip] Use geometric clipping for unaligned clips

For the simple cases where the clip is an unaligned box (or boxes), apply
the clip directly to the geometry and avoid having to use an intermediate
clip-mask.

12 files changed, 830 insertions, 662 deletions

diff --git a/src/cairo-bentley-ottmann.c b/src/cairo-bentley-ottmann.c
index 99f4655d..cb508f51 100644
--- a/src/cairo-bentley-ottmann.c
+++ b/src/cairo-bentley-ottmann.c
@@ -216,28 +216,6 @@ _line_compute_intersection_x_for_y (const cairo_line_t *line,
     return x;
 }
 
-static cairo_fixed_t
-_line_compute_intersection_y_for_x (const cairo_line_t *line,
-				    cairo_fixed_t x)
-{
-    cairo_fixed_t y, dx;
-
-    if (x == line->p1.x)
-	return line->p1.y;
-    if (x == line->p2.x)
-	return line->p2.y;
-
-    y = line->p1.y;
-    dx = line->p2.x - line->p1.x;
-    if (dx != 0) {
-	y += _cairo_fixed_mul_div_floor (x - line->p1.x,
-					 line->p2.y - line->p1.y,
-					 dx);
-    }
-
-    return y;
-}
-
 static inline int
 _cairo_bo_point32_compare (cairo_bo_point32_t const *a,
 			   cairo_bo_point32_t const *b)
@@ -1801,217 +1779,12 @@ _cairo_bentley_ottmann_tessellate_polygon (cairo_traps_t	 *traps,
     return status;
 }
 
-static cairo_bool_t
-_points_outside (const cairo_fixed_t *x, const cairo_box_t *limits)
-{
-    if (x[0] < limits->p1.x || x[0] > limits->p2.x)
-	return TRUE;
-    if (x[1] < limits->p1.x || x[1] > limits->p2.x)
-	return TRUE;
-    if (x[2] < limits->p1.x || x[2] > limits->p2.x)
-	return TRUE;
-    if (x[3] < limits->p1.x || x[3] > limits->p2.x)
-	return TRUE;
-
-    return FALSE;
-}
-
-static int
-_add_event (const cairo_line_t *line,
-	   int32_t top, int32_t bottom,
-	   int dir,
-	   cairo_bo_start_event_t *event)
-{
-    if (top == bottom)
-	return 0;
-
-    event->type = CAIRO_BO_EVENT_TYPE_START;
-    event->point.y = top;
-    event->point.x = _line_compute_intersection_x_for_y (line, top);
-
-    event->edge.edge.line = *line;
-    event->edge.edge.top = top;
-    event->edge.edge.bottom = bottom;
-    event->edge.edge.dir = dir;
-
-    event->edge.deferred_trap.right = NULL;
-    event->edge.prev = NULL;
-    event->edge.next = NULL;
-
-    return 1;
-}
-
-static int
-_compute_clipped_trapezoid_edges (const cairo_traps_t *traps,
-				  const cairo_trapezoid_t *t,
-				  cairo_bo_start_event_t *events)
-{
-    cairo_fixed_t x[4];
-    int num_events = 0;
-    int top, bot;
-
-    /* compute points in clockwise orientation */
-    top = t->top;
-    bot = t->bottom;
-
-    x[0] = _line_compute_intersection_x_for_y (&t->left, top);
-    x[1] = _line_compute_intersection_x_for_y (&t->right, top);
-    x[2] = _line_compute_intersection_x_for_y (&t->right, bot);
-    x[3] = _line_compute_intersection_x_for_y (&t->left, bot);
-
-    if (traps->has_limits && _points_outside (x, &traps->limits)) {
-	cairo_line_t limits[2];
-	cairo_fixed_t ly[2], ry[2];
-	cairo_fixed_t ymin, ymax;
-
-	limits[0].p1.x = traps->limits.p1.x;
-	limits[0].p1.y = traps->limits.p1.y;
-	limits[0].p2.x = traps->limits.p1.x;
-	limits[0].p2.y = traps->limits.p2.y;
-
-	limits[1].p1.x = traps->limits.p2.x;
-	limits[1].p1.y = traps->limits.p1.y;
-	limits[1].p2.x = traps->limits.p2.x;
-	limits[1].p2.y = traps->limits.p2.y;
-
-	ly[0] = _line_compute_intersection_y_for_x (&t->left,
-						    traps->limits.p1.x);
-	ymin = ymax = ly[0];
-
-	ly[1] = _line_compute_intersection_y_for_x (&t->left,
-						    traps->limits.p2.x);
-	if (ly[1] < ymin)
-	    ymin = ly[1];
-	if (ly[1] > ymax)
-	    ymax = ly[1];
-
-	ry[0] = _line_compute_intersection_y_for_x (&t->right,
-						    traps->limits.p1.x);
-	if (ry[0] < ymin)
-	    ymin = ry[0];
-	if (ry[0] > ymax)
-	    ymax = ry[0];
-
-	ry[1] = _line_compute_intersection_y_for_x (&t->right,
-						    traps->limits.p2.x);
-	if (ry[1] < ymin)
-	    ymin = ry[1];
-	if (ry[1] > ymax)
-	    ymax = ry[1];
-
-	if (ymin > top)
-	    top = ymin;
-	if (ymax < bot)
-	    bot = ymax;
-	if (top >= bot)
-	    return 0;
-
-	/* left hand side intersects */
-
-	if (x[0] <= traps->limits.p1.x && x[3] <= traps->limits.p1.x)
-	{
-	    num_events += _add_event (&limits[0], top, bot, 1,
-				      events + num_events);
-	}
-	else if (x[0] >= traps->limits.p1.x && x[3] >= traps->limits.p1.x &&
-		 x[0] <= traps->limits.p2.x && x[3] <= traps->limits.p2.x)
-	{
-	    num_events += _add_event (&t->left, top, bot, 1,
-				      events + num_events);
-	}
-	else
-	{
-	    if (ly[0] < ly[1]) {
-		if (ly[1] >= top) {
-		    if (ly[0] < top)
-			ly[0] = top;
-		    if (ly[1] > bot)
-			ly[1] = bot;
-		    num_events += _add_event (&limits[0], top, ly[0], 1,
-					    events + num_events);
-		    num_events += _add_event (&t->left, ly[0], ly[1], 1,
-					    events + num_events);
-		    num_events += _add_event (&limits[1], ly[1], bot, 1,
-					    events + num_events);
-		}
-	    } else {
-		if (ly[1] <= bot) {
-		    if (ly[1] < top)
-			ly[1] = top;
-		    if (ly[0] > bot)
-			ly[0] = bot;
-		    num_events += _add_event (&limits[1], top, ly[1], 1,
-					    events + num_events);
-		    num_events += _add_event (&t->left, ly[1], ly[0], 1,
-					    events + num_events);
-		    num_events += _add_event (&limits[0], ly[0], bot, 1,
-					    events + num_events);
-		}
-	    }
-	}
-
-	/* right hand side intersects */
-
-	if (x[1] >= traps->limits.p2.x && x[2] >= traps->limits.p2.x)
-	{
-	    num_events += _add_event (&limits[1], top, bot, -1,
-				      events + num_events);
-	}
-	else if (x[1] <= traps->limits.p2.x && x[2] <= traps->limits.p2.x &&
-		 x[1] >= traps->limits.p1.x && x[2] >= traps->limits.p1.x)
-	{
-	    num_events += _add_event (&t->right, top, bot, -1,
-				      events + num_events);
-	}
-	else
-	{
-	    if (ry[0] < ry[1]) {
-		if (ry[0] <= bot) {
-		    if (ry[0] < top)
-			ry[0] = top;
-		    if (ry[1] > bot)
-			ry[1] = bot;
-		    num_events += _add_event (&limits[0], top, ry[0], -1,
-					    events + num_events);
-		    num_events += _add_event (&t->right, ry[0], ry[1], -1,
-					    events + num_events);
-		    num_events += _add_event (&limits[1], ry[1], bot, -1,
-					    events + num_events);
-		}
-	    } else {
-		if (ry[0] >= top) {
-		    if (ry[0] > bot)
-			ry[0] = bot;
-		    if (ry[1] < top)
-			ry[1] = top;
-		    num_events += _add_event (&limits[1], top, ry[1], -1,
-					    events + num_events);
-		    num_events += _add_event (&t->right, ry[1], ry[0], -1,
-					    events + num_events);
-		    num_events += _add_event (&limits[0], ry[0], bot, -1,
-					    events + num_events);
-		}
-	    }
-	}
-    } else {
-	num_events += _add_event (&t->left, top, bot, 1, events + num_events);
-	num_events += _add_event (&t->right, top, bot, -1, events + num_events);
-    }
-
-    return num_events;
-}
-
 cairo_status_t
 _cairo_bentley_ottmann_tessellate_traps (cairo_traps_t *traps,
 					 cairo_fill_rule_t fill_rule)
 {
-    int intersections;
     cairo_status_t status;
-    cairo_bo_start_event_t stack_events[CAIRO_STACK_ARRAY_LENGTH (cairo_bo_start_event_t)];
-    cairo_bo_start_event_t *events;
-    cairo_bo_event_t *stack_event_ptrs[ARRAY_LENGTH (stack_events) + 1];
-    cairo_bo_event_t **event_ptrs;
-    int num_events;
+    cairo_polygon_t polygon;
     int i;
 
     if (unlikely (0 == traps->num_traps))
@@ -2021,50 +1794,38 @@ _cairo_bentley_ottmann_tessellate_traps (cairo_traps_t *traps,
     dump_traps (traps, "bo-traps-in.txt");
 #endif
 
-    /* we need at most 6 vertical edges to describe each clipped trapezoid */
-    i = 6 * traps->num_traps;
+    _cairo_polygon_init (&polygon);
+    _cairo_polygon_limit (&polygon, traps->limits, traps->num_limits);
 
-    events = stack_events;
-    event_ptrs = stack_event_ptrs;
-    if (i > ARRAY_LENGTH (stack_events)) {
-	events = _cairo_malloc_ab_plus_c (i,
-					  sizeof (cairo_bo_start_event_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);
-    }
-
-    num_events = 0;
     for (i = 0; i < traps->num_traps; i++) {
-	num_events += _compute_clipped_trapezoid_edges (traps,
-							&traps->traps[i],
-							&events[num_events]);
-    }
-
-    for (i = 0; i < num_events; i++)
-	event_ptrs[i] = (cairo_bo_event_t *) &events[i];
-
+	status = _cairo_polygon_add_line (&polygon,
+					  &traps->traps[i].left,
+					  traps->traps[i].top,
+					  traps->traps[i].bottom,
+					  1);
+	if (unlikely (status))
+	    goto CLEANUP;
 
-#if DEBUG_TRAPS
-    dump_edges (events, num_events, "bo-traps-edges.txt");
-#endif
+	status = _cairo_polygon_add_line (&polygon,
+					  &traps->traps[i].right,
+					  traps->traps[i].top,
+					  traps->traps[i].bottom,
+					  -1);
+	if (unlikely (status))
+	    goto CLEANUP;
+    }
 
     _cairo_traps_clear (traps);
-    status = _cairo_bentley_ottmann_tessellate_bo_edges (event_ptrs,
-							 num_events,
-							 fill_rule,
-							 traps,
-							 &intersections);
+    status = _cairo_bentley_ottmann_tessellate_polygon (traps,
+							&polygon,
+							fill_rule);
 
 #if DEBUG_TRAPS
     dump_traps (traps, "bo-traps-out.txt");
 #endif
 
-    if (events != stack_events)
-	free (events);
+  CLEANUP:
+    _cairo_polygon_fini (&polygon);
 
     return status;
 }
diff --git a/src/cairo-clip-private.h b/src/cairo-clip-private.h
index d045d12e..6e404927 100644
--- a/src/cairo-clip-private.h
+++ b/src/cairo-clip-private.h
@@ -117,6 +117,11 @@ cairo_private cairo_int_status_t
 _cairo_clip_get_region (cairo_clip_t *clip,
 			cairo_region_t **region);
 
+cairo_private cairo_int_status_t
+_cairo_clip_get_boxes (cairo_clip_t *clip,
+		       cairo_box_t **boxes,
+		       int *count);
+
 cairo_private void
 _cairo_clip_translate (cairo_clip_t  *clip,
                        cairo_fixed_t  tx,
diff --git a/src/cairo-clip.c b/src/cairo-clip.c
index 32005118..09b26ade 100644
--- a/src/cairo-clip.c
+++ b/src/cairo-clip.c
@@ -600,7 +600,6 @@ _cairo_clip_apply_clip (cairo_clip_t *clip,
     return status;
 }
 
-#if 0
 static inline cairo_bool_t
 _clip_paths_are_rectilinear (cairo_clip_path_t *clip_path)
 {
@@ -613,7 +612,6 @@ _clip_paths_are_rectilinear (cairo_clip_path_t *clip_path)
 
     return TRUE;
 }
-#endif
 
 static cairo_int_status_t
 _cairo_clip_path_to_region_geometric (cairo_clip_path_t *clip_path)
@@ -634,7 +632,7 @@ _cairo_clip_path_to_region_geometric (cairo_clip_path_t *clip_path)
 
     _cairo_traps_init (&traps);
     _cairo_box_from_rectangle (&box, &clip_path->extents);
-    _cairo_traps_limit (&traps, &box);
+    _cairo_traps_limit (&traps, &box, 1);
 
     status = _cairo_path_fixed_fill_to_traps (&clip_path->prev->path,
 					      clip_path->prev->fill_rule,
@@ -712,6 +710,260 @@ _cairo_clip_path_to_region (cairo_clip_path_t *clip_path)
     return CAIRO_STATUS_SUCCESS;
 }
 
+static inline int
+pot (int v)
+{
+    v--;
+    v |= v >> 1;
+    v |= v >> 2;
+    v |= v >> 4;
+    v |= v >> 8;
+    v |= v >> 16;
+    v++;
+    return v;
+}
+
+/* XXX there is likely a faster method! ;-) */
+static cairo_status_t
+_region_clip_to_boxes (const cairo_region_t *region,
+		       cairo_box_t **boxes,
+		       int *num_boxes,
+		       int *size_boxes)
+{
+    cairo_traps_t traps;
+    cairo_status_t status;
+    int n, num_rects;
+
+    _cairo_traps_init (&traps);
+    _cairo_traps_limit (&traps, *boxes, *num_boxes);
+    traps.is_rectilinear = TRUE;
+
+    num_rects = cairo_region_num_rectangles (region);
+    for (n = 0; n < num_rects; n++) {
+	cairo_rectangle_int_t rect;
+	cairo_point_t p1, p2;
+
+	cairo_region_get_rectangle (region, n, &rect);
+
+	p1.x = _cairo_fixed_from_int (rect.x);
+	p1.y = _cairo_fixed_from_int (rect.y);
+	p2.x = _cairo_fixed_from_int (rect.x + rect.width);
+	p2.y = _cairo_fixed_from_int (rect.y + rect.height);
+
+	status = _cairo_traps_tessellate_rectangle (&traps, &p1, &p2);
+	if (unlikely (status))
+	    goto CLEANUP;
+    }
+
+    status = _cairo_bentley_ottmann_tessellate_rectilinear_traps (&traps, CAIRO_FILL_RULE_WINDING);
+    if (unlikely (status))
+	goto CLEANUP;
+
+    n = *size_boxes;
+    if (n < 0)
+	n = -n;
+
+    if (traps.num_traps > n) {
+	cairo_box_t *new_boxes;
+
+	new_boxes = _cairo_malloc_ab (traps.num_traps, sizeof (cairo_box_t));
+	if (unlikely (new_boxes == NULL)) {
+	    status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
+	    goto CLEANUP;
+	}
+
+	if (*size_boxes > 0)
+	    free (*boxes);
+
+	*boxes = new_boxes;
+	*size_boxes = traps.num_traps;
+    }
+
+    for (n = 0; n < traps.num_traps; n++) {
+	(*boxes)[n].p1.x = traps.traps[n].left.p1.x;
+	(*boxes)[n].p1.y = traps.traps[n].top;
+	(*boxes)[n].p2.x = traps.traps[n].right.p1.x;
+	(*boxes)[n].p2.y = traps.traps[n].bottom;
+    }
+    *num_boxes = n;
+
+  CLEANUP:
+    _cairo_traps_fini (&traps);
+
+    return status;
+}
+
+static cairo_status_t
+_rectilinear_clip_to_boxes (const cairo_path_fixed_t *path,
+			    cairo_fill_rule_t fill_rule,
+			    cairo_box_t **boxes,
+			    int *num_boxes,
+			    int *size_boxes)
+{
+    cairo_polygon_t polygon;
+    cairo_traps_t traps;
+    cairo_status_t status;
+
+    _cairo_polygon_init (&polygon);
+    _cairo_polygon_limit (&polygon, *boxes, *num_boxes);
+
+    /* tolerance will be ignored as the path is rectilinear */
+    status = _cairo_path_fixed_fill_to_polygon (path, 0., &polygon);
+    if (unlikely (status))
+	goto CLEANUP_POLYGON;
+
+    if (polygon.num_edges == 0) {
+	*num_boxes = 0;
+    } else {
+	_cairo_traps_init (&traps);
+
+	status = _cairo_bentley_ottmann_tessellate_rectilinear_polygon (&traps,
+									&polygon,
+									fill_rule);
+	if (likely (status == CAIRO_STATUS_SUCCESS)) {
+	    int i;
+
+	    i = *size_boxes;
+	    if (i < 0)
+		i = -i;
+
+	    if (traps.num_traps > i) {
+		cairo_box_t *new_boxes;
+		int new_size;
+
+		new_size = pot (traps.num_traps);
+		new_boxes = _cairo_malloc_ab (new_size, sizeof (cairo_box_t));
+		if (unlikely (new_boxes == NULL)) {
+		    status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
+		    goto CLEANUP_TRAPS;
+		}
+
+		if (*size_boxes > 0)
+		    free (*boxes);
+
+		*boxes = new_boxes;
+		*size_boxes = new_size;
+	    }
+
+	    for (i = 0; i < traps.num_traps; i++) {
+		(*boxes)[i].p1.x = traps.traps[i].left.p1.x;
+		(*boxes)[i].p1.y = traps.traps[i].top;
+		(*boxes)[i].p2.x = traps.traps[i].right.p1.x;
+		(*boxes)[i].p2.y = traps.traps[i].bottom;
+	    }
+	    *num_boxes = i;
+	}
+
+      CLEANUP_TRAPS:
+	_cairo_traps_fini (&traps);
+    }
+
+  CLEANUP_POLYGON:
+    _cairo_polygon_fini (&polygon);
+
+    return status;
+}
+
+static cairo_int_status_t
+_cairo_clip_path_to_boxes (cairo_clip_path_t *clip_path,
+			   cairo_box_t **boxes,
+			   int *count)
+{
+    int size = -*count;
+    int num_boxes = 0;
+    cairo_status_t status;
+
+    if (clip_path->region != NULL) {
+	int num_rects, n;
+
+	num_rects = cairo_region_num_rectangles (clip_path->region);
+	if (num_rects > -size) {
+	    cairo_box_t *new_boxes;
+
+	    new_boxes = _cairo_malloc_ab (num_rects, sizeof (cairo_box_t));
+	    if (unlikely (new_boxes == NULL))
+		return _cairo_error (CAIRO_STATUS_NO_MEMORY);
+
+	    *boxes = new_boxes;
+	}
+
+	for (n = 0; n < num_rects; n++) {
+	    cairo_rectangle_int_t rect;
+
+	    cairo_region_get_rectangle (clip_path->region, n, &rect);
+	    (*boxes)[n].p1.x = _cairo_fixed_from_int (rect.x);
+	    (*boxes)[n].p1.y = _cairo_fixed_from_int (rect.y);
+	    (*boxes)[n].p2.x = _cairo_fixed_from_int (rect.x + rect.width);
+	    (*boxes)[n].p2.y = _cairo_fixed_from_int (rect.y + rect.height);
+	}
+
+	*count = num_rects;
+	return CAIRO_STATUS_SUCCESS;
+    }
+
+    /* keep it simple at first */
+    if (! _clip_paths_are_rectilinear (clip_path))
+	return CAIRO_INT_STATUS_UNSUPPORTED;
+
+    assert (-size >= 1);
+    if (_cairo_path_fixed_is_box (&clip_path->path, *boxes)) {
+	num_boxes = 1;
+    } else {
+	status = _rectilinear_clip_to_boxes (&clip_path->path,
+					     clip_path->fill_rule,
+					     boxes, &num_boxes, &size);
+	if (unlikely (status))
+	    return status;
+    }
+
+    while ((clip_path = clip_path->prev) != NULL) {
+	cairo_box_t box;
+
+	if (clip_path->region != NULL) {
+	    status = _region_clip_to_boxes (clip_path->region,
+					    boxes, &num_boxes, &size);
+	    if (unlikely (status))
+		return status;
+
+	    break;
+	} else if (_cairo_path_fixed_is_box (&clip_path->path, &box)) {
+	    int i, j;
+
+	    for (i = j = 0; i < num_boxes; i++) {
+		if (j != i)
+		    (*boxes)[j] = (*boxes)[i];
+
+		if (box.p1.x > (*boxes)[j].p1.x)
+		    (*boxes)[j].p1.x = box.p1.x;
+		if (box.p2.x < (*boxes)[j].p2.x)
+		    (*boxes)[j].p2.x = box.p2.x;
+
+		if (box.p1.y > (*boxes)[j].p1.y)
+		    (*boxes)[j].p1.y = box.p1.y;
+		if (box.p2.y < (*boxes)[j].p2.y)
+		    (*boxes)[j].p2.y = box.p2.y;
+
+		j += (*boxes)[j].p2.x > (*boxes)[j].p1.x &&
+		     (*boxes)[j].p2.y > (*boxes)[j].p1.y;
+	    }
+
+	    num_boxes = j;
+	} else {
+	    status = _rectilinear_clip_to_boxes (&clip_path->path,
+						 clip_path->fill_rule,
+						 boxes, &num_boxes, &size);
+	    if (unlikely (status))
+		return status;
+	}
+
+	if (num_boxes == 0)
+	    break;
+    }
+
+    *count = num_boxes;
+    return CAIRO_STATUS_SUCCESS;
+}
+
 cairo_surface_t *
 _cairo_clip_get_surface (cairo_clip_t *clip, cairo_surface_t *target)
 {
@@ -943,12 +1195,10 @@ _cairo_clip_get_region (cairo_clip_t *clip,
 {
     cairo_int_status_t status;
 
-    *region = NULL;
     if (clip->all_clipped)
-	return CAIRO_INT_STATUS_NOTHING_TO_DO;
+	goto CLIPPED;
 
-    if (clip->path == NULL)
-	return CAIRO_STATUS_SUCCESS;
+    assert (clip->path != NULL);
 
     status = _cairo_clip_path_to_region (clip->path);
     if (status)
@@ -956,10 +1206,40 @@ _cairo_clip_get_region (cairo_clip_t *clip,
 
     if (cairo_region_is_empty (clip->path->region)) {
 	_cairo_clip_set_all_clipped (clip);
+	goto CLIPPED;
+    }
+
+    if (region)
+	*region = clip->path->region;
+    return CAIRO_STATUS_SUCCESS;
+
+  CLIPPED:
+    if (region)
+	*region = NULL;
+    return CAIRO_INT_STATUS_NOTHING_TO_DO;
+}
+
+cairo_int_status_t
+_cairo_clip_get_boxes (cairo_clip_t *clip,
+		       cairo_box_t **boxes,
+		       int *count)
+{
+    cairo_int_status_t status;
+
+    if (clip->all_clipped)
+	return CAIRO_INT_STATUS_NOTHING_TO_DO;
+
+    assert (clip->path != NULL);
+
+    status = _cairo_clip_path_to_boxes (clip->path, boxes, count);
+    if (status)
+	return status;
+
+    if (*count == 0) {
+	_cairo_clip_set_all_clipped (clip);
 	return CAIRO_INT_STATUS_NOTHING_TO_DO;
     }
 
-    *region = clip->path->region;
     return CAIRO_STATUS_SUCCESS;
 }
 
diff --git a/src/cairo-gstate.c b/src/cairo-gstate.c
index 8cb52ab0..902de85b 100644
--- a/src/cairo-gstate.c
+++ b/src/cairo-gstate.c
@@ -869,27 +869,28 @@ static cairo_bool_t
 _clipped (cairo_gstate_t *gstate)
 {
     cairo_rectangle_int_t extents;
-    cairo_region_t *clip_region;
 
     if (gstate->clip.all_clipped)
 	return TRUE;
 
+    /* XXX consider applying a surface clip? */
+
+    if (gstate->clip.path == NULL)
+	return FALSE;
+
     if (_cairo_surface_get_extents (gstate->target, &extents)) {
 	if (extents.width == 0 || extents.height == 0)
 	    return TRUE;
 
-	if (gstate->clip.path != NULL &&
-	    ! _cairo_rectangle_intersect (&extents,
+	if (! _cairo_rectangle_intersect (&extents,
 					  &gstate->clip.path->extents))
 	{
 	    return TRUE;
 	}
-
-	/* XXX consider applying a surface clip? */
     }
 
     /* perform a simple query to exclude trivial all-clipped cases */
-    return _cairo_clip_get_region (&gstate->clip, &clip_region) == CAIRO_INT_STATUS_NOTHING_TO_DO;
+    return _cairo_clip_get_region (&gstate->clip, NULL) == CAIRO_INT_STATUS_NOTHING_TO_DO;
 }
 
 cairo_status_t
@@ -1018,7 +1019,7 @@ _cairo_gstate_in_stroke (cairo_gstate_t	    *gstate,
     limit.p2.y = limit.p1.y + 2;
 
     _cairo_traps_init (&traps);
-    _cairo_traps_limit (&traps, &limit);
+    _cairo_traps_limit (&traps, &limit, 1);
 
     status = _cairo_path_fixed_stroke_to_traps (path,
 						&gstate->stroke_style,
diff --git a/src/cairo-path-fill.c b/src/cairo-path-fill.c
index 0cad156c..d46917d5 100644
--- a/src/cairo-path-fill.c
+++ b/src/cairo-path-fill.c
@@ -160,8 +160,7 @@ _cairo_path_fixed_fill_to_traps (const cairo_path_fixed_t *path,
 	return CAIRO_STATUS_SUCCESS;
 
     _cairo_polygon_init (&polygon);
-    if (traps->has_limits)
-	_cairo_polygon_limit (&polygon, &traps->limits);
+    _cairo_polygon_limit (&polygon, traps->limits, traps->num_limits);
 
     status = _cairo_path_fixed_fill_to_polygon (path,
 						tolerance,
@@ -189,6 +188,7 @@ _cairo_path_fixed_fill_rectilinear_tessellate_to_region (const cairo_path_fixed_
 							 cairo_fill_rule_t	 fill_rule,
 							 const cairo_rectangle_int_t *extents)
 {
+    cairo_box_t box;
     cairo_polygon_t polygon;
     cairo_traps_t traps;
     cairo_status_t status;
@@ -196,10 +196,8 @@ _cairo_path_fixed_fill_rectilinear_tessellate_to_region (const cairo_path_fixed_
 
     _cairo_polygon_init (&polygon);
     if (extents != NULL) {
-	cairo_box_t box;
-
 	_cairo_box_from_rectangle (&box, extents);
-	_cairo_polygon_limit (&polygon, &box);
+	_cairo_polygon_limit (&polygon, &box, 1);
     }
 
     /* tolerance will be ignored as the path is rectilinear */
diff --git a/src/cairo-path-stroke.c b/src/cairo-path-stroke.c
index d37c597b..33fed4fc 100644
--- a/src/cairo-path-stroke.c
+++ b/src/cairo-path-stroke.c
@@ -186,13 +186,14 @@ _cairo_stroker_init (cairo_stroker_t		*stroker,
 
 static void
 _cairo_stroker_limit (cairo_stroker_t *stroker,
-		      const cairo_box_t *box)
+		      const cairo_box_t *boxes,
+		      int num_boxes)
 {
     double dx, dy;
     cairo_fixed_t fdx, fdy;
 
     stroker->has_bounds = TRUE;
-    stroker->bounds = *box;
+    _cairo_boxes_get_extents (boxes, num_boxes, &stroker->bounds);
 
     /* Extend the bounds in each direction to account for the maximum area
      * we might generate trapezoids, to capture line segments that are outside
@@ -1353,8 +1354,8 @@ _cairo_path_fixed_stroke_to_polygon (const cairo_path_fixed_t	*path,
     stroker.add_external_edge = _cairo_polygon_add_external_edge,
     stroker.closure = polygon;
 
-    if (polygon->has_limits)
-	_cairo_stroker_limit (&stroker, &polygon->limits);
+    if (polygon->num_limits)
+	_cairo_stroker_limit (&stroker, polygon->limits, polygon->num_limits);
 
     status = _cairo_path_fixed_interpret (path,
 					  CAIRO_DIRECTION_FORWARD,
@@ -1404,8 +1405,7 @@ _cairo_path_fixed_stroke_to_traps (const cairo_path_fixed_t	*path,
     }
 
     _cairo_polygon_init (&polygon);
-    if (traps->has_limits)
-	_cairo_polygon_limit (&polygon, &traps->limits);
+    _cairo_polygon_limit (&polygon, traps->limits, traps->num_limits);
 
     status = _cairo_path_fixed_stroke_to_polygon (path,
 						 stroke_style,
@@ -1458,10 +1458,11 @@ typedef struct _cairo_rectilinear_stroker {
 
 static void
 _cairo_rectilinear_stroker_limit (cairo_rectilinear_stroker_t *stroker,
-				  const cairo_box_t *box)
+				  const cairo_box_t *boxes,
+				  int num_boxes)
 {
     stroker->has_bounds = TRUE;
-    stroker->bounds = *box;
+    _cairo_boxes_get_extents (boxes, num_boxes, &stroker->bounds);
 
     stroker->bounds.p1.x -= stroker->half_line_width;
     stroker->bounds.p2.x += stroker->half_line_width;
@@ -2005,9 +2006,10 @@ _cairo_path_fixed_stroke_rectilinear_to_traps (const cairo_path_fixed_t	*path,
 				     stroke_style,
 				     ctm,
 				     traps);
-    if (traps->has_limits) {
+    if (traps->num_limits) {
 	_cairo_rectilinear_stroker_limit (&rectilinear_stroker,
-					  &traps->limits);
+					  traps->limits,
+					  traps->num_limits);
     }
 
     status = _cairo_path_fixed_interpret (path,
diff --git a/src/cairo-polygon.c b/src/cairo-polygon.c
index a8addff2..fdc5c92d 100644
--- a/src/cairo-polygon.c
+++ b/src/cairo-polygon.c
@@ -50,7 +50,7 @@ _cairo_polygon_init (cairo_polygon_t *polygon)
 
     polygon->has_current_point = FALSE;
     polygon->has_current_edge = FALSE;
-    polygon->has_limits = FALSE;
+    polygon->num_limits = 0;
 
     polygon->extents.p1.x = polygon->extents.p1.y = INT32_MAX;
     polygon->extents.p2.x = polygon->extents.p2.y = INT32_MIN;
@@ -58,10 +58,11 @@ _cairo_polygon_init (cairo_polygon_t *polygon)
 
 void
 _cairo_polygon_limit (cairo_polygon_t	*polygon,
-		      const cairo_box_t *limits)
+		      const cairo_box_t *limits,
+		      int num_limits)
 {
-    polygon->has_limits = TRUE;
-    polygon->limits = *limits;
+    polygon->limits = limits;
+    polygon->num_limits = num_limits;
 }
 
 void
@@ -159,156 +160,163 @@ static void
 _add_clipped_edge (cairo_polygon_t *polygon,
 		   const cairo_point_t *p1,
 		   const cairo_point_t *p2,
-		   int dir)
+		   const int top, const int bottom,
+		   const int dir)
 {
     cairo_point_t p[2];
     int top_y, bot_y;
+    int n;
 
-    if (p1->x <= polygon->limits.p1.x && p2->x <= polygon->limits.p1.x)
-    {
-	p[0].x = polygon->limits.p1.x;
-	p[0].y = polygon->limits.p1.y;
-	top_y = p1->y;
-	if (top_y < p[0].y)
-	    top_y = p[0].y;
-
-	p[1].x = polygon->limits.p1.x;
-	p[1].y = polygon->limits.p2.y;
-	bot_y = p2->y;
-	if (bot_y > p[1].y)
-	    bot_y = p[1].y;
-
-	_add_edge (polygon, &p[0], &p[1], top_y, bot_y, dir);
-    }
-    else if (p1->x >= polygon->limits.p2.x && p2->x >= polygon->limits.p2.x)
-    {
-	p[0].x = polygon->limits.p2.x;
-	p[0].y = polygon->limits.p1.y;
-	top_y = p1->y;
-	if (top_y < p[0].y)
-	    top_y = p[0].y;
-
-	p[1].x = polygon->limits.p2.x;
-	p[1].y = polygon->limits.p2.y;
-	bot_y = p2->y;
-	if (bot_y > p[1].y)
-	    bot_y = p[1].y;
-
-	_add_edge (polygon, &p[0], &p[1], top_y, bot_y, dir);
-    }
-    else if (p1->x >= polygon->limits.p1.x && p2->x >= polygon->limits.p1.x &&
-	     p1->x <= polygon->limits.p2.x && p2->x <= polygon->limits.p2.x)
-    {
-	top_y = p1->y;
-	if (top_y < polygon->limits.p1.y)
-	    top_y = polygon->limits.p1.y;
-
-	bot_y = p2->y;
-	if (bot_y > polygon->limits.p2.y)
-	    bot_y = polygon->limits.p2.y;
-
-	_add_edge (polygon, p1, p2, top_y, bot_y, dir);
-    }
-    else
-    {
-	int left_y, right_y;
-	int p1_y, p2_y;
+    for (n = 0; n < polygon->num_limits; n++) {
+	const cairo_box_t *limits = &polygon->limits[n];
 
-	left_y = _cairo_edge_compute_intersection_y_for_x (p1, p2,
-						     polygon->limits.p1.x);
-	right_y = _cairo_edge_compute_intersection_y_for_x (p1, p2,
-						      polygon->limits.p2.x);
+	if (top >= limits->p2.y)
+	    continue;
+	if (bottom <= limits->p1.y)
+	    continue;
 
-	if (left_y == right_y) /* horizontal within bounds */
-	    return;
+	if (p1->x <= limits->p1.x && p2->x <= limits->p1.x)
+	{
+	    p[0].x = limits->p1.x;
+	    p[0].y = limits->p1.y;
+	    top_y = top;
+	    if (top_y < p[0].y)
+		top_y = p[0].y;
+
+	    p[1].x = limits->p1.x;
+	    p[1].y = limits->p2.y;
+	    bot_y = bottom;
+	    if (bot_y > p[1].y)
+		bot_y = p[1].y;
+
+	    _add_edge (polygon, &p[0], &p[1], top_y, bot_y, dir);
+	}
+	else if (p1->x >= limits->p2.x && p2->x >= limits->p2.x)
+	{
+	    p[0].x = limits->p2.x;
+	    p[0].y = limits->p1.y;
+	    top_y = top;
+	    if (top_y < p[0].y)
+		top_y = p[0].y;
+
+	    p[1].x = limits->p2.x;
+	    p[1].y = limits->p2.y;
+	    bot_y = bottom;
+	    if (bot_y > p[1].y)
+		bot_y = p[1].y;
+
+	    _add_edge (polygon, &p[0], &p[1], top_y, bot_y, dir);
+	}
+	else if (p1->x >= limits->p1.x && p2->x >= limits->p1.x &&
+		 p1->x <= limits->p2.x && p2->x <= limits->p2.x)
+	{
+	    top_y = top;
+	    if (top_y < limits->p1.y)
+		top_y = limits->p1.y;
 
-	p1_y = p1->y;
-	p2_y = p2->y;
-
-	if (left_y < right_y) {
-	    if (p1->x < polygon->limits.p1.x && left_y > polygon->limits.p1.y)
-	    {
-		p[0].x = polygon->limits.p1.x;
-		p[0].y = polygon->limits.p1.y;
-		top_y = p1_y;
-		if (top_y < p[0].y)
-		    top_y = p[0].y;
-
-		p[1].x = polygon->limits.p1.x;
-		p[1].y = polygon->limits.p2.y;
-		bot_y = left_y;
-		if (bot_y > p[1].y)
-		    bot_y = p[1].y;
-
-		if (bot_y > top_y)
-		    _add_edge (polygon, &p[0], &p[1], top_y, bot_y, dir);
-		p1_y = bot_y;
-	    }
+	    bot_y = bottom;
+	    if (bot_y > limits->p2.y)
+		bot_y = limits->p2.y;
 
-	    if (p2->x > polygon->limits.p2.x && right_y < polygon->limits.p2.y)
-	    {
-		p[0].x = polygon->limits.p2.x;
-		p[0].y = polygon->limits.p1.y;
-		top_y = right_y;
-		if (top_y < p[0].y)
-		    top_y = p[0].y;
-
-		p[1].x = polygon->limits.p2.x;
-		p[1].y = polygon->limits.p2.y;
-		bot_y = p2_y;
-		if (bot_y > p[1].y)
-		    bot_y = p[1].y;
-
-		if (bot_y > top_y)
-		    _add_edge (polygon, &p[0], &p[1], top_y, bot_y, dir);
-		p2_y = top_y;
-	    }
-	} else {
-	    if (p1->x > polygon->limits.p2.x && right_y > polygon->limits.p1.y)
-	    {
-		p[0].x = polygon->limits.p2.x;
-		p[0].y = polygon->limits.p1.y;
-		top_y = p1_y;
-		if (top_y < p[0].y)
-		    top_y = p[0].y;
-
-		p[1].x = polygon->limits.p2.x;
-		p[1].y = polygon->limits.p2.y;
-		bot_y = right_y;
-		if (bot_y > p[1].y)
-		    bot_y = p[1].y;
-
-		if (bot_y > top_y)
-		    _add_edge (polygon, &p[0], &p[1], top_y, bot_y, dir);
-		p1_y = bot_y;
-	    }
+	    _add_edge (polygon, p1, p2, top_y, bot_y, dir);
+	}
+	else
+	{
+	    int left_y, right_y;
+	    int p1_y, p2_y;
 
-	    if (p2->x < polygon->limits.p1.x && left_y < polygon->limits.p2.y)
-	    {
-		p[0].x = polygon->limits.p1.x;
-		p[0].y = polygon->limits.p1.y;
-		top_y = left_y;
-		if (top_y < p[0].y)
-		    top_y = p[0].y;
-
-		p[1].x = polygon->limits.p1.x;
-		p[1].y = polygon->limits.p2.y;
-		bot_y = p2_y;
-		if (bot_y > p[1].y)
-		    bot_y = p[1].y;
-
-		if (bot_y > top_y)
-		    _add_edge (polygon, &p[0], &p[1], top_y, bot_y, dir);
-		p2_y = top_y;
+	    left_y = _cairo_edge_compute_intersection_y_for_x (p1, p2,
+							       limits->p1.x);
+	    right_y = _cairo_edge_compute_intersection_y_for_x (p1, p2,
+								limits->p2.x);
+
+	    if (left_y == right_y) /* horizontal within bounds */
+		return;
+
+	    p1_y = top;
+	    p2_y = bottom;
+
+	    if (left_y < right_y) {
+		if (p1->x < limits->p1.x && left_y > limits->p1.y) {
+		    p[0].x = limits->p1.x;
+		    p[0].y = limits->p1.y;
+		    top_y = p1_y;
+		    if (top_y < p[0].y)
+			top_y = p[0].y;
+
+		    p[1].x = limits->p1.x;
+		    p[1].y = limits->p2.y;
+		    bot_y = left_y;
+		    if (bot_y > p[1].y)
+			bot_y = p[1].y;
+
+		    if (bot_y > top_y)
+			_add_edge (polygon, &p[0], &p[1], top_y, bot_y, dir);
+		    p1_y = bot_y;
+		}
+
+		if (p2->x > limits->p2.x && right_y < limits->p2.y) {
+		    p[0].x = limits->p2.x;
+		    p[0].y = limits->p1.y;
+		    top_y = right_y;
+		    if (top_y < p[0].y)
+			top_y = p[0].y;
+
+		    p[1].x = limits->p2.x;
+		    p[1].y = limits->p2.y;
+		    bot_y = p2_y;
+		    if (bot_y > p[1].y)
+			bot_y = p[1].y;
+
+		    if (bot_y > top_y)
+			_add_edge (polygon, &p[0], &p[1], top_y, bot_y, dir);
+		    p2_y = top_y;
+		}
+	    } else {
+		if (p1->x > limits->p2.x && right_y > limits->p1.y) {
+		    p[0].x = limits->p2.x;
+		    p[0].y = limits->p1.y;
+		    top_y = p1_y;
+		    if (top_y < p[0].y)
+			top_y = p[0].y;
+
+		    p[1].x = limits->p2.x;
+		    p[1].y = limits->p2.y;
+		    bot_y = right_y;
+		    if (bot_y > p[1].y)
+			bot_y = p[1].y;
+
+		    if (bot_y > top_y)
+			_add_edge (polygon, &p[0], &p[1], top_y, bot_y, dir);
+		    p1_y = bot_y;
+		}
+
+		if (p2->x < limits->p1.x && left_y < limits->p2.y) {
+		    p[0].x = limits->p1.x;
+		    p[0].y = limits->p1.y;
+		    top_y = left_y;
+		    if (top_y < p[0].y)
+			top_y = p[0].y;
+
+		    p[1].x = limits->p1.x;
+		    p[1].y = limits->p2.y;
+		    bot_y = p2_y;
+		    if (bot_y > p[1].y)
+			bot_y = p[1].y;
+
+		    if (bot_y > top_y)
+			_add_edge (polygon, &p[0], &p[1], top_y, bot_y, dir);
+		    p2_y = top_y;
+		}
 	    }
-	}
 
-	if (p1_y < polygon->limits.p1.y)
-	    p1_y = polygon->limits.p1.y;
-	if (p2_y > polygon->limits.p2.y)
-	    p2_y = polygon->limits.p2.y;
-	if (p2_y > p1_y)
-	    _add_edge (polygon, p1, p2, p1_y, p2_y, dir);
+	    if (p1_y < limits->p1.y)
+		p1_y = limits->p1.y;
+	    if (p2_y > limits->p2.y)
+		p2_y = limits->p2.y;
+	    if (p2_y > p1_y)
+		_add_edge (polygon, p1, p2, p1_y, p2_y, dir);
+	}
     }
 }
 
@@ -331,14 +339,14 @@ _cairo_polygon_add_edge (cairo_polygon_t *polygon,
 	dir = -1;
     }
 
-    if (polygon->has_limits) {
-	if (p2->y <= polygon->limits.p1.y)
+    if (polygon->num_limits) {
+	if (p2->y <= polygon->limits[0].p1.y)
 	    return;
 
-	if (p1->y >= polygon->limits.p2.y)
+	if (p1->y >= polygon->limits[polygon->num_limits-1].p2.y)
 	    return;
 
-	_add_clipped_edge (polygon, p1, p2, dir);
+	_add_clipped_edge (polygon, p1, p2, p1->y, p2->y, dir);
     } else
 	_add_edge (polygon, p1, p2, p1->y, p2->y, dir);
 }
@@ -352,6 +360,33 @@ _cairo_polygon_add_external_edge (void *polygon,
     return _cairo_polygon_status (polygon);
 }
 
+cairo_status_t
+_cairo_polygon_add_line (cairo_polygon_t *polygon,
+			 const cairo_line_t *line,
+			 int top, int bottom,
+			 int dir)
+{
+    /* drop horizontal edges */
+    if (line->p1.y == line->p2.y)
+	return CAIRO_STATUS_SUCCESS;
+
+    if (bottom <= top)
+	return CAIRO_STATUS_SUCCESS;
+
+    if (polygon->num_limits) {
+	if (line->p2.y <= polygon->limits[0].p1.y)
+	    return CAIRO_STATUS_SUCCESS;
+
+	if (line->p1.y >= polygon->limits[polygon->num_limits-1].p2.y)
+	    return CAIRO_STATUS_SUCCESS;
+
+	_add_clipped_edge (polygon, &line->p1, &line->p2, top, bottom, dir);
+    } else
+	_add_edge (polygon, &line->p1, &line->p2, top, bottom, dir);
+
+    return _cairo_polygon_status (polygon);
+}
+
 /* flattened path operations */
 
 void
diff --git a/src/cairo-rectangle.c b/src/cairo-rectangle.c
index b1396248..e887c751 100644
--- a/src/cairo-rectangle.c
+++ b/src/cairo-rectangle.c
@@ -71,6 +71,29 @@ _cairo_box_from_rectangle (cairo_box_t                 *box,
     box->p2.y = _cairo_fixed_from_int (rect->y + rect->height);
 }
 
+void
+_cairo_boxes_get_extents (const cairo_box_t *boxes,
+			  int num_boxes,
+			  cairo_box_t *extents)
+{
+    int n;
+
+    assert (num_boxes > 0);
+    *extents = *boxes;
+
+    for (n = 1; n < num_boxes; n++) {
+	if (boxes[n].p1.x < extents->p1.x)
+	    extents->p1.x = boxes[n].p1.x;
+	if (boxes[n].p2.x > extents->p2.x)
+	    extents->p2.x = boxes[n].p2.x;
+
+	if (boxes[n].p1.y < extents->p1.y)
+	    extents->p1.y = boxes[n].p1.y;
+	if (boxes[n].p2.y > extents->p2.y)
+	    extents->p2.y = boxes[n].p2.y;
+    }
+}
+
 /* XXX We currently have a confusing mix of boxes and rectangles as
  * exemplified by this function.  A #cairo_box_t is a rectangular area
  * represented by the coordinates of the upper left and lower right
diff --git a/src/cairo-surface-fallback.c b/src/cairo-surface-fallback.c
index cca63846..14d94fd7 100644
--- a/src/cairo-surface-fallback.c
+++ b/src/cairo-surface-fallback.c
@@ -810,6 +810,80 @@ _rectangle_intersect_clip (cairo_rectangle_int_t *extents, cairo_clip_t *clip)
     return CAIRO_STATUS_SUCCESS;
 }
 
+static cairo_bool_t
+_clip_contains_rectangle (cairo_clip_t *clip,
+			  const cairo_rectangle_int_t *rect)
+{
+    cairo_clip_path_t *clip_path;
+
+    clip_path = clip->path;
+
+    if (clip_path->extents.x > rect->x ||
+	clip_path->extents.y > rect->y ||
+	clip_path->extents.x + clip_path->extents.width < rect->x + rect->width ||
+	clip_path->extents.y + clip_path->extents.height < rect->y + rect->height)
+    {
+	return FALSE;
+    }
+
+    do {
+	cairo_box_t box;
+
+	if (! _cairo_path_fixed_is_box (&clip_path->path, &box))
+	    return FALSE;
+
+	if (box.p1.x > _cairo_fixed_from_int (rect->x) ||
+	    box.p1.y > _cairo_fixed_from_int (rect->y) ||
+	    box.p2.x < _cairo_fixed_from_int (rect->x + rect->width) ||
+	    box.p2.y < _cairo_fixed_from_int (rect->y + rect->height))
+	{
+	    return FALSE;
+	}
+    } while ((clip_path = clip_path->prev) != NULL);
+
+    return TRUE;
+}
+
+static cairo_status_t
+_clip_to_boxes (cairo_clip_t **clip,
+		const cairo_rectangle_int_t *extents,
+		cairo_box_t **boxes,
+		int *num_boxes)
+{
+    cairo_status_t status;
+
+    if (*clip == NULL) {
+	status = CAIRO_STATUS_SUCCESS;
+	goto OUT;
+    }
+
+    /* In some cases it may be preferable to always use boxes instead
+     * of a region, in particular where we can cull lots of geometry.
+     * For the time being, continue to use the old path until we can
+     * find a compelling use-case for geometry clipping.
+     */
+    status = _cairo_clip_get_region (*clip, NULL);
+    if (status != CAIRO_INT_STATUS_UNSUPPORTED)
+	goto OUT;
+
+    status = _cairo_clip_get_boxes (*clip, boxes, num_boxes);
+    switch ((int) status) {
+    case CAIRO_STATUS_SUCCESS:
+	*clip = NULL;
+	goto DONE;
+
+    case  CAIRO_INT_STATUS_UNSUPPORTED:
+	status = CAIRO_STATUS_SUCCESS;
+	goto OUT;
+    }
+
+  OUT:
+    _cairo_box_from_rectangle (&(*boxes)[0], extents);
+    *num_boxes = 1;
+  DONE:
+    return status;
+}
+
 cairo_status_t
 _cairo_surface_fallback_paint (cairo_surface_t		*surface,
 			       cairo_operator_t		 op,
@@ -819,9 +893,8 @@ _cairo_surface_fallback_paint (cairo_surface_t		*surface,
     cairo_status_t status;
     cairo_rectangle_int_t extents;
     cairo_bool_t is_bounded;
-    cairo_region_t *clip_region = NULL;
-    cairo_bool_t clip_surface = FALSE;
-    cairo_box_t box;
+    cairo_box_t boxes_stack[32], *boxes = boxes_stack;
+    int num_boxes = ARRAY_LENGTH (boxes_stack);
     cairo_traps_t traps;
 
     is_bounded = _cairo_surface_get_extents (surface, &extents);
@@ -835,71 +908,36 @@ _cairo_surface_fallback_paint (cairo_surface_t		*surface,
 	    return CAIRO_STATUS_SUCCESS;
     }
 
+    if (clip != NULL && _clip_contains_rectangle (clip, &extents))
+	clip = NULL;
+
     status = _rectangle_intersect_clip (&extents, clip);
-    if (status) {
+    if (unlikely (status)) {
 	if (status == CAIRO_INT_STATUS_NOTHING_TO_DO)
 	    status = CAIRO_STATUS_SUCCESS;
 	return status;
     }
 
-    /* avoid the palaver of constructing traps for a simple region */
-    if (clip != NULL) {
-	status = _cairo_clip_get_region (clip, &clip_region);
-	if (unlikely (_cairo_status_is_error (status)))
-	    return status;
-	if (unlikely (status == CAIRO_INT_STATUS_NOTHING_TO_DO))
-	    return CAIRO_STATUS_SUCCESS;
-
-	clip_surface = status == CAIRO_INT_STATUS_UNSUPPORTED;
-    }
-
-    if (! clip_surface ||
-       (_cairo_operator_bounded_by_mask (op) && op != CAIRO_OPERATOR_SOURCE))
-    {
-	cairo_region_t region, *trap_region;
-
-	/* avoid unnecessarily allocating a region */
-	if (clip_region != NULL &&
-	    cairo_region_num_rectangles (clip_region) > 1)
-	{
-	    trap_region = cairo_region_copy (clip_region);
-	    status = cairo_region_intersect_rectangle (trap_region, &extents);
-	    if (unlikely (status)) {
-		cairo_region_destroy (trap_region);
-		return status;
-	    }
-	}
-	else
-	{
-	    _cairo_region_init_rectangle (&region, &extents);
-	    trap_region = &region;
-	}
-
-	if (cairo_region_is_empty (trap_region)) {
+    status = _clip_to_boxes (&clip, &extents, &boxes, &num_boxes);
+    if (unlikely (status)) {
+	if (status == CAIRO_INT_STATUS_NOTHING_TO_DO)
 	    status = CAIRO_STATUS_SUCCESS;
-	} else {
-	    status = _clip_and_composite_region (source, op, surface,
-						 trap_region,
-						 clip_surface ? clip : NULL,
-						 &extents);
-	}
-	if (trap_region == &region)
-	    _cairo_region_fini (trap_region);
-	else
-	    cairo_region_destroy (trap_region);
-
-	if (status != CAIRO_INT_STATUS_UNSUPPORTED)
-	    return status;
+	return status;
     }
 
-    /* otherwise, use the trapezoid fallbacks */
-    _cairo_box_from_rectangle (&box, &extents);
-    _cairo_traps_init_box (&traps, &box);
+    status = _cairo_traps_init_boxes (&traps, boxes, num_boxes);
+    if (unlikely (status))
+	goto CLEANUP_BOXES;
+
     status = _clip_and_composite_trapezoids (source, op, surface,
-					     &traps, CAIRO_ANTIALIAS_NONE,
+					     &traps, CAIRO_ANTIALIAS_DEFAULT,
 					     clip, &extents);
     _cairo_traps_fini (&traps);
 
+CLEANUP_BOXES:
+    if (boxes != boxes_stack)
+	free (boxes);
+
     return status;
 }
 
@@ -934,7 +972,6 @@ _cairo_surface_mask_draw_func (void                          *closure,
     }
 }
 
-
 cairo_status_t
 _cairo_surface_fallback_mask (cairo_surface_t		*surface,
 			      cairo_operator_t		 op,
@@ -965,6 +1002,9 @@ _cairo_surface_fallback_mask (cairo_surface_t		*surface,
 	    return CAIRO_STATUS_SUCCESS;
     }
 
+    if (clip != NULL && _clip_contains_rectangle (clip, &extents))
+	clip = NULL;
+
     status = _rectangle_intersect_clip (&extents, clip);
     if (status) {
 	if (status == CAIRO_INT_STATUS_NOTHING_TO_DO)
@@ -992,7 +1032,8 @@ _cairo_surface_fallback_stroke (cairo_surface_t		*surface,
 {
     cairo_polygon_t polygon;
     cairo_traps_t traps;
-    cairo_box_t box;
+    cairo_box_t boxes_stack[32], *boxes = boxes_stack;
+    int num_boxes = ARRAY_LENGTH (boxes_stack);
     cairo_rectangle_int_t extents;
     cairo_bool_t is_bounded;
     cairo_status_t status;
@@ -1018,20 +1059,28 @@ _cairo_surface_fallback_stroke (cairo_surface_t		*surface,
 	    return CAIRO_STATUS_SUCCESS;
     }
 
+    if (clip != NULL && _clip_contains_rectangle (clip, &extents))
+	clip = NULL;
+
     status = _rectangle_intersect_clip (&extents, clip);
-    if (status) {
+    if (unlikely (status)) {
 	if (status == CAIRO_INT_STATUS_NOTHING_TO_DO)
 	    status = CAIRO_STATUS_SUCCESS;
 	return status;
     }
 
-    _cairo_box_from_rectangle (&box, &extents);
+    status = _clip_to_boxes (&clip, &extents, &boxes, &num_boxes);
+    if (unlikely (status)) {
+	if (status == CAIRO_INT_STATUS_NOTHING_TO_DO)
+	    status = CAIRO_STATUS_SUCCESS;
+	return status;
+    }
 
     _cairo_polygon_init (&polygon);
-    _cairo_polygon_limit (&polygon, &box);
+    _cairo_polygon_limit (&polygon, boxes, num_boxes);
 
     _cairo_traps_init (&traps);
-    _cairo_traps_limit (&traps, &box);
+    _cairo_traps_limit (&traps, boxes, num_boxes);
 
     if (path->is_rectilinear) {
 	status = _cairo_path_fixed_stroke_rectilinear_to_traps (path,
@@ -1094,6 +1143,8 @@ _cairo_surface_fallback_stroke (cairo_surface_t		*surface,
   CLEANUP:
     _cairo_traps_fini (&traps);
     _cairo_polygon_fini (&polygon);
+    if (boxes != boxes_stack)
+	free (boxes);
 
     return status;
 }
@@ -1110,7 +1161,8 @@ _cairo_surface_fallback_fill (cairo_surface_t		*surface,
 {
     cairo_polygon_t polygon;
     cairo_traps_t traps;
-    cairo_box_t box;
+    cairo_box_t boxes_stack[32], *boxes = boxes_stack;
+    int num_boxes = ARRAY_LENGTH (boxes_stack);
     cairo_rectangle_int_t extents;
     cairo_bool_t is_bounded;
     cairo_status_t status;
@@ -1134,78 +1186,34 @@ _cairo_surface_fallback_fill (cairo_surface_t		*surface,
 	    return CAIRO_STATUS_SUCCESS;
     }
 
+    if (clip != NULL && _clip_contains_rectangle (clip, &extents))
+	clip = NULL;
+
+    if (clip != NULL && clip->path->prev == NULL &&
+	_cairo_path_fixed_equal (&clip->path->path, path))
+    {
+	clip = NULL;
+    }
+
     status = _rectangle_intersect_clip (&extents, clip);
-    if (status) {
+    if (unlikely (status)) {
 	if (status == CAIRO_INT_STATUS_NOTHING_TO_DO)
 	    status = CAIRO_STATUS_SUCCESS;
 	return status;
     }
 
-    /* avoid the palaver of constructing traps for a simple region */
-    if (path->maybe_fill_region) {
-	cairo_region_t *clip_region = NULL;
-	cairo_bool_t clip_surface = FALSE;
-
-	if (clip != NULL) {
-	    status = _cairo_clip_get_region (clip, &clip_region);
-	    if (unlikely (_cairo_status_is_error (status)))
-		return status;
-	    if (unlikely (status == CAIRO_INT_STATUS_NOTHING_TO_DO))
-		return CAIRO_STATUS_SUCCESS;
-
-	    clip_surface = status == CAIRO_INT_STATUS_UNSUPPORTED;
-	}
-
-	if (! clip_surface ||
-	    (_cairo_operator_bounded_by_mask (op) &&
-	     op != CAIRO_OPERATOR_SOURCE))
-	{
-	    cairo_region_t *trap_region;
-
-	    trap_region = _cairo_path_fixed_fill_rectilinear_to_region (path,
-									fill_rule,
-									&extents);
-	    if (trap_region != NULL) {
-		status = trap_region->status;
-		if (unlikely (status))
-		    return status;
-
-		if (clip_region != NULL &&
-		    cairo_region_num_rectangles (clip_region) > 1)
-		{
-		    status = cairo_region_intersect (trap_region, clip_region);
-		    if (unlikely (status)) {
-			cairo_region_destroy (trap_region);
-			return status;
-		    }
-		}
-
-		if (_cairo_operator_bounded_by_mask (op)) {
-		    cairo_region_get_extents (trap_region, &extents);
-		    if (extents.width == 0 || extents.height == 0)
-			goto CLEANUP_TRAP;
-		}
-
-		status = _clip_and_composite_region (source, op, surface,
-						     trap_region,
-						     clip_surface ? clip : NULL,
-						     &extents);
-             CLEANUP_TRAP:
-		cairo_region_destroy (trap_region);
-
-		if (status != CAIRO_INT_STATUS_UNSUPPORTED)
-		    return status;
-	    }
-	}
+    status = _clip_to_boxes (&clip, &extents, &boxes, &num_boxes);
+    if (unlikely (status)) {
+	if (status == CAIRO_INT_STATUS_NOTHING_TO_DO)
+	    status = CAIRO_STATUS_SUCCESS;
+	return status;
     }
 
-    _cairo_box_from_rectangle (&box, &extents);
-
     _cairo_traps_init (&traps);
-    _cairo_traps_limit (&traps, &box);
+    _cairo_traps_limit (&traps, boxes, num_boxes);
 
     _cairo_polygon_init (&polygon);
-    _cairo_polygon_limit (&polygon, &box);
+    _cairo_polygon_limit (&polygon, boxes, num_boxes);
 
     status = _cairo_path_fixed_fill_to_polygon (path, tolerance, &polygon);
     if (unlikely (status))
@@ -1264,6 +1272,8 @@ _cairo_surface_fallback_fill (cairo_surface_t		*surface,
   CLEANUP:
     _cairo_traps_fini (&traps);
     _cairo_polygon_fini (&polygon);
+    if (boxes != boxes_stack)
+	free (boxes);
 
     return status;
 }
@@ -1342,6 +1352,14 @@ _cairo_surface_fallback_show_glyphs (cairo_surface_t		*surface,
     is_bounded = _cairo_surface_get_extents (surface, &extents);
     assert (is_bounded || clip);
 
+    if (_cairo_operator_bounded_by_source (op)) {
+	cairo_rectangle_int_t source_extents;
+
+	_cairo_pattern_get_extents (source, &source_extents);
+	if (! _cairo_rectangle_intersect (&extents, &source_extents))
+	    return CAIRO_STATUS_SUCCESS;
+    }
+
     if (_cairo_operator_bounded_by_mask (op)) {
         cairo_rectangle_int_t glyph_extents;
 
@@ -1357,6 +1375,9 @@ _cairo_surface_fallback_show_glyphs (cairo_surface_t		*surface,
 	    return CAIRO_STATUS_SUCCESS;
     }
 
+    if (clip != NULL && _clip_contains_rectangle (clip, &extents))
+	clip = NULL;
+
     status = _rectangle_intersect_clip (&extents, clip);
     if (status) {
 	if (status == CAIRO_INT_STATUS_NOTHING_TO_DO)
diff --git a/src/cairo-traps.c b/src/cairo-traps.c
index a5974cc2..c6709de3 100644
--- a/src/cairo-traps.c
+++ b/src/cairo-traps.c
@@ -58,17 +58,17 @@ _cairo_traps_init (cairo_traps_t *traps)
     traps->traps_size = ARRAY_LENGTH (traps->traps_embedded);
     traps->traps = traps->traps_embedded;
 
-    traps->has_limits = FALSE;
+    traps->num_limits = 0;
     traps->has_intersections = FALSE;
 }
 
 void
 _cairo_traps_limit (cairo_traps_t	*traps,
-		    cairo_box_t		*limits)
+		    const cairo_box_t	*limits,
+		    int			 num_limits)
 {
-    traps->has_limits = TRUE;
-
-    traps->limits = *limits;
+    traps->limits = limits;
+    traps->num_limits = num_limits;
 }
 
 void
@@ -92,35 +92,6 @@ _cairo_traps_fini (cairo_traps_t *traps)
     VG (VALGRIND_MAKE_MEM_NOACCESS (traps, sizeof (cairo_traps_t)));
 }
 
-/**
- * _cairo_traps_init_box:
- * @traps: a #cairo_traps_t
- * @box: a box that will be converted to a single trapezoid
- *       to store in @traps.
- *
- * Initializes a #cairo_traps_t to contain a single rectangular
- * trapezoid.
- **/
-void
-_cairo_traps_init_box (cairo_traps_t *traps,
-		       const cairo_box_t   *box)
-{
-    _cairo_traps_init (traps);
-
-    assert (traps->traps_size >= 1);
-
-    traps->num_traps = 1;
-
-    traps->traps[0].top = box->p1.y;
-    traps->traps[0].bottom = box->p2.y;
-    traps->traps[0].left.p1 = box->p1;
-    traps->traps[0].left.p2.x = box->p1.x;
-    traps->traps[0].left.p2.y = box->p2.y;
-    traps->traps[0].right.p1.x = box->p2.x;
-    traps->traps[0].right.p1.y = box->p1.y;
-    traps->traps[0].right.p2 = box->p2;
-}
-
 /* make room for at least one more trap */
 static cairo_bool_t
 _cairo_traps_grow (cairo_traps_t *traps)
@@ -171,6 +142,60 @@ _cairo_traps_add_trap (cairo_traps_t *traps,
     trap->right = *right;
 }
 
+/**
+ * _cairo_traps_init_box:
+ * @traps: a #cairo_traps_t
+ * @box: an array box that will each be converted to a single trapezoid
+ *       to store in @traps.
+ *
+ * Initializes a #cairo_traps_t to contain an array of rectangular
+ * trapezoids.
+ **/
+cairo_status_t
+_cairo_traps_init_boxes (cairo_traps_t	    *traps,
+		         const cairo_box_t  *boxes,
+			 int		     num_boxes)
+{
+    cairo_trapezoid_t *trap;
+
+    _cairo_traps_init (traps);
+
+    while (traps->traps_size < num_boxes) {
+	if (unlikely (! _cairo_traps_grow (traps))) {
+	    _cairo_traps_fini (traps);
+	    return _cairo_error (CAIRO_STATUS_NO_MEMORY);
+	}
+    }
+
+    traps->num_traps = num_boxes;
+    traps->is_rectilinear = TRUE;
+
+    trap = &traps->traps[0];
+    while (num_boxes--) {
+	trap->top    = boxes->p1.y;
+	trap->bottom = boxes->p2.y;
+
+	trap->left.p1   = boxes->p1;
+	trap->left.p2.x = boxes->p1.x;
+	trap->left.p2.y = boxes->p2.y;
+
+	trap->right.p1.x = boxes->p2.x;
+	trap->right.p1.y = boxes->p1.y;
+	trap->right.p2   = boxes->p2;
+
+	if (traps->maybe_region) {
+	    traps->maybe_region  = _cairo_fixed_is_integer (boxes->p1.x) &&
+		                   _cairo_fixed_is_integer (boxes->p1.y) &&
+		                   _cairo_fixed_is_integer (boxes->p2.x) &&
+		                   _cairo_fixed_is_integer (boxes->p2.y);
+	}
+
+	trap++, boxes++;
+    }
+
+    return CAIRO_STATUS_SUCCESS;
+}
+
 cairo_status_t
 _cairo_traps_tessellate_rectangle (cairo_traps_t *traps,
 				   const cairo_point_t *top_left,
@@ -188,63 +213,72 @@ _cairo_traps_tessellate_rectangle (cairo_traps_t *traps,
      top = top_left->y;
      bottom = bottom_right->y;
 
-    if (traps->has_limits) {
-	/* Trivially reject if trapezoid is entirely to the right or
-	 * to the left of the limits. */
-	if (left.p1.x >= traps->limits.p2.x &&
-	    left.p2.x >= traps->limits.p2.x)
-	{
-	    return CAIRO_STATUS_SUCCESS;
-	}
-
-	if (right.p1.x <= traps->limits.p1.x &&
-	    right.p2.x <= traps->limits.p1.x)
-	{
-	    return CAIRO_STATUS_SUCCESS;
-	}
-
-	/* And reject if the trapezoid is entirely above or below */
-	if (top > traps->limits.p2.y || bottom < traps->limits.p1.y)
-	    return CAIRO_STATUS_SUCCESS;
-
-	/* Otherwise, clip the trapezoid to the limits. We only clip
-	 * where an edge is entirely outside the limits. If we wanted
-	 * to be more clever, we could handle cases where a trapezoid
-	 * edge intersects the edge of the limits, but that would
-	 * require slicing this trapezoid into multiple trapezoids,
-	 * and I'm not sure the effort would be worth it. */
-	if (top < traps->limits.p1.y)
-	    top = traps->limits.p1.y;
-
-	if (bottom > traps->limits.p2.y)
-	    bottom = traps->limits.p2.y;
-
-	if (left.p1.x <= traps->limits.p1.x &&
-	    left.p2.x <= traps->limits.p1.x)
-	{
-	    left.p1.x = traps->limits.p1.x;
-	    left.p1.y = traps->limits.p1.y;
-	    left.p2.x = traps->limits.p1.x;
-	    left.p2.y = traps->limits.p2.y;
-	}
-
-	if (right.p1.x >= traps->limits.p2.x &&
-	    right.p2.x >= traps->limits.p2.x)
-	{
-	    right.p1.x = traps->limits.p2.x;
-	    right.p1.y = traps->limits.p1.y;
-	    right.p2.x = traps->limits.p2.x;
-	    right.p2.y = traps->limits.p2.y;
-	}
-    }
-
     if (top == bottom)
 	return CAIRO_STATUS_SUCCESS;
 
     if (left.p1.x == right.p1.x)
 	return CAIRO_STATUS_SUCCESS;
 
-    _cairo_traps_add_trap (traps, top, bottom, &left, &right);
+    if (traps->num_limits) {
+	int n;
+
+	for (n = 0; n < traps->num_limits; n++) {
+	    const cairo_box_t *limits = &traps->limits[n];
+	    cairo_line_t _left, _right;
+	    cairo_fixed_t _top, _bottom;
+
+	    if (top >= limits->p2.y)
+		continue;
+	    if (bottom <= limits->p1.y)
+		continue;
+
+	    /* Trivially reject if trapezoid is entirely to the right or
+	     * to the left of the limits. */
+	    if (left.p1.x >= limits->p2.x)
+		continue;
+	    if (right.p1.x <= limits->p1.x)
+		continue;
+
+	    /* Otherwise, clip the trapezoid to the limits. */
+	    _top = top;
+	    if (_top < limits->p1.y)
+		_top = limits->p1.y;
+
+	    _bottom = bottom;
+	    if (_bottom > limits->p2.y)
+		_bottom = limits->p2.y;
+
+	    if (_bottom <= _top)
+		continue;
+
+	    _left = left;
+	    if (_left.p1.x <= limits->p1.x &&
+		_left.p2.x <= limits->p1.x)
+	    {
+		_left.p1.x = limits->p1.x;
+		_left.p1.y = limits->p1.y;
+		_left.p2.x = limits->p1.x;
+		_left.p2.y = limits->p2.y;
+	    }
+
+	    _right = right;
+	    if (_right.p1.x >= limits->p2.x &&
+		_right.p2.x >= limits->p2.x)
+	    {
+		_right.p1.x = limits->p2.x;
+		_right.p1.y = limits->p1.y;
+		_right.p2.x = limits->p2.x;
+		_right.p2.y = limits->p2.y;
+	    }
+
+	    if (left.p1.x >= right.p1.x)
+		continue;
+
+	    _cairo_traps_add_trap (traps, _top, _bottom, &_left, &_right);
+	}
+    } else {
+	_cairo_traps_add_trap (traps, top, bottom, &left, &right);
+    }
 
     return traps->status;
 }
@@ -493,12 +527,6 @@ _cairo_traps_extract_region (cairo_traps_t   *traps,
 	int x2 = _cairo_fixed_integer_part (traps->traps[i].right.p1.x);
 	int y2 = _cairo_fixed_integer_part (traps->traps[i].bottom);
 
-	/* XXX: Sometimes we get degenerate trapezoids from the tesellator;
-	 * skip these.
-	 */
-	assert (x1 != x2);
-	assert (y1 != y2);
-
 	rects[rect_count].x = x1;
 	rects[rect_count].y = y1;
 	rects[rect_count].width = x2 - x1;
diff --git a/src/cairo-types-private.h b/src/cairo-types-private.h
index 1e1f823d..54bd2a74 100644
--- a/src/cairo-types-private.h
+++ b/src/cairo-types-private.h
@@ -254,8 +254,8 @@ typedef struct _cairo_polygon {
     cairo_bool_t has_current_edge;
 
     cairo_box_t extents;
-    cairo_box_t limits;
-    cairo_bool_t has_limits;
+    const cairo_box_t *limits;
+    int num_limits;
 
     int num_edges;
     int edges_size;
diff --git a/src/cairoint.h b/src/cairoint.h
index 7312f7e1..bbeb8e09 100644
--- a/src/cairoint.h
+++ b/src/cairoint.h
@@ -252,6 +252,11 @@ cairo_private void
 _cairo_box_round_to_rectangle (const cairo_box_t     *box,
 			       cairo_rectangle_int_t *rectangle);
 
+cairo_private void
+_cairo_boxes_get_extents (const cairo_box_t *boxes,
+			  int num_boxes,
+			  cairo_box_t *extents);
+
 static inline void
 _cairo_unbounded_rectangle_init (cairo_rectangle_int_t *rect)
 {
@@ -951,10 +956,10 @@ typedef struct _cairo_surface_attributes {
 typedef struct _cairo_traps {
     cairo_status_t status;
 
-    cairo_box_t limits;
+    const cairo_box_t *limits;
+    int num_limits;
 
     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;
 
@@ -2245,12 +2250,19 @@ _cairo_polygon_init (cairo_polygon_t *polygon);
 
 cairo_private void
 _cairo_polygon_limit (cairo_polygon_t	*polygon,
-		      const cairo_box_t *limits);
+		      const cairo_box_t *boxes,
+		      int		 num_boxes);
 
 cairo_private void
 _cairo_polygon_fini (cairo_polygon_t *polygon);
 
 cairo_private cairo_status_t
+_cairo_polygon_add_line (cairo_polygon_t *polygon,
+			 const cairo_line_t *line,
+			 int top, int bottom,
+			 int dir);
+
+cairo_private cairo_status_t
 _cairo_polygon_add_external_edge (void *polygon,
 				  const cairo_point_t *p1,
 				  const cairo_point_t *p2);
@@ -2345,11 +2357,13 @@ _cairo_traps_init (cairo_traps_t *traps);
 
 cairo_private void
 _cairo_traps_limit (cairo_traps_t	*traps,
-		    cairo_box_t		*limits);
+		    const cairo_box_t	*boxes,
+		    int			 num_boxes);
 
-cairo_private void
-_cairo_traps_init_box (cairo_traps_t *traps,
-		       const cairo_box_t   *box);
+cairo_private cairo_status_t
+_cairo_traps_init_boxes (cairo_traps_t	    *traps,
+			 const cairo_box_t    *boxes,
+			 int		     num_boxes);
 
 cairo_private void
 _cairo_traps_clear (cairo_traps_t *traps);