Eliminate self-intersecting strokes.

We refactor the surface fallbacks to convert full strokes and fills to the
intermediate polygon representation (as opposed to before where we
returned the trapezoidal representation). This allow greater flexibility
to choose how then to rasterize the polygon. Where possible we use the
local spans rasteriser for its increased performance, but still have the
option to use the tessellator instead (for example, with the current
Render protocol which does not yet have a polygon image).

In order to accommodate this, the spans interface is tweaked to accept
whole polygons instead of a path and the tessellator is tweaked for speed.

Performance Impact
==================

...
Still measuring, expecting some severe regressions.
...

1 files changed, 625 insertions, 400 deletions

diff --git a/src/cairo-path-stroke.c b/src/cairo-path-stroke.c
index 4fa4ce5ac..208e39030 100644
--- a/src/cairo-path-stroke.c
+++ b/src/cairo-path-stroke.c
@@ -33,6 +33,7 @@
  *
  * Contributor(s):
  *	Carl D. Worth <cworth@cworth.org>
+ *	Chris Wilson <chris@chris-wilson.co.uk>
  */
 
 #define _BSD_SOURCE /* for hypot() */
@@ -60,7 +61,18 @@ typedef struct cairo_stroker {
     double ctm_determinant;
     cairo_bool_t ctm_det_positive;
 
-    cairo_traps_t *traps;
+    void *closure;
+    cairo_status_t (*add_external_edge) (void *closure,
+					 const cairo_point_t *p1,
+					 const cairo_point_t *p2);
+    cairo_status_t (*add_triangle) (void *closure,
+				    const cairo_point_t triangle[3]);
+    cairo_status_t (*add_triangle_fan) (void *closure,
+					const cairo_point_t *midpt,
+					const cairo_point_t *points,
+					int npoints);
+    cairo_status_t (*add_convex_quad) (void *closure,
+				       const cairo_point_t quad[4]);
 
     cairo_pen_t	  pen;
 
@@ -141,8 +153,7 @@ _cairo_stroker_init (cairo_stroker_t		*stroker,
 		     cairo_stroke_style_t	*stroke_style,
 		     const cairo_matrix_t	*ctm,
 		     const cairo_matrix_t	*ctm_inverse,
-		     double			 tolerance,
-		     cairo_traps_t		*traps)
+		     double			 tolerance)
 {
     cairo_status_t status;
 
@@ -150,7 +161,6 @@ _cairo_stroker_init (cairo_stroker_t		*stroker,
     stroker->ctm = ctm;
     stroker->ctm_inverse = ctm_inverse;
     stroker->tolerance = tolerance;
-    stroker->traps = traps;
 
     stroker->ctm_determinant = _cairo_matrix_compute_determinant (stroker->ctm);
     stroker->ctm_det_positive = stroker->ctm_determinant >= 0.0;
@@ -161,35 +171,45 @@ _cairo_stroker_init (cairo_stroker_t		*stroker,
     if (unlikely (status))
 	return status;
 
+    stroker->has_bounds = FALSE;
+
     stroker->has_current_face = FALSE;
     stroker->has_first_face = FALSE;
     stroker->has_initial_sub_path = FALSE;
 
     _cairo_stroker_dash_init (&stroker->dash, stroke_style);
 
-    stroker->has_bounds = _cairo_traps_get_limit (traps, &stroker->bounds);
-    if (stroker->has_bounds) {
-	/* Extend the bounds in each direction to account for the maximum area
-	 * we might generate trapezoids, to capture line segments that are outside
-	 * of the bounds but which might generate rendering that's within bounds.
-	 */
-	double dx, dy;
-	cairo_fixed_t fdx, fdy;
+    stroker->add_external_edge = NULL;
 
-	_cairo_stroke_style_max_distance_from_path (stroker->style,
-						    stroker->ctm,
-						    &dx, &dy);
+    return CAIRO_STATUS_SUCCESS;
+}
 
-	fdx = _cairo_fixed_from_double (dx);
-	stroker->bounds.p1.x -= fdx;
-	stroker->bounds.p2.x += fdx;
+static void
+_cairo_stroker_limit (cairo_stroker_t *stroker,
+		      const cairo_box_t *box)
+{
+    double dx, dy;
+    cairo_fixed_t fdx, fdy;
 
-	fdy = _cairo_fixed_from_double (dy);
-	stroker->bounds.p1.y -= fdy;
-	stroker->bounds.p2.y += fdy;
-    }
+    stroker->has_bounds = TRUE;
+    stroker->bounds = *box;
 
-    return CAIRO_STATUS_SUCCESS;
+    /* Extend the bounds in each direction to account for the maximum area
+     * we might generate trapezoids, to capture line segments that are outside
+     * of the bounds but which might generate rendering that's within bounds.
+     */
+
+    _cairo_stroke_style_max_distance_from_path (stroker->style, stroker->ctm,
+						&dx, &dy);
+
+    fdx = _cairo_fixed_from_double (dx);
+    fdy = _cairo_fixed_from_double (dy);
+
+    stroker->bounds.p1.x -= fdx;
+    stroker->bounds.p2.x += fdx;
+
+    stroker->bounds.p1.y -= fdy;
+    stroker->bounds.p2.y += fdy;
 }
 
 static void
@@ -199,14 +219,15 @@ _cairo_stroker_fini (cairo_stroker_t *stroker)
 }
 
 static void
-_translate_point (cairo_point_t *point, cairo_point_t *offset)
+_translate_point (cairo_point_t *point, const cairo_point_t *offset)
 {
     point->x += offset->x;
     point->y += offset->y;
 }
 
 static int
-_cairo_stroker_face_clockwise (cairo_stroke_face_t *in, cairo_stroke_face_t *out)
+_cairo_stroker_join_is_clockwise (const cairo_stroke_face_t *in,
+				  const cairo_stroke_face_t *out)
 {
     cairo_slope_t in_slope, out_slope;
 
@@ -232,76 +253,209 @@ _cairo_slope_compare_sgn (double dx1, double dy1, double dx2, double dy2)
     return 0;
 }
 
+static inline int
+_range_step (int i, int step, int max)
+{
+    i += step;
+    if (i < 0)
+	i = max - 1;
+    if (i >= max)
+	i = 0;
+    return i;
+}
+
+/*
+ * Construct a fan around the midpoint using the vertices from pen between
+ * inpt and outpt.
+ */
 static cairo_status_t
-_cairo_stroker_join (cairo_stroker_t *stroker, cairo_stroke_face_t *in, cairo_stroke_face_t *out)
+_tessellate_fan (cairo_stroker_t *stroker,
+		 const cairo_slope_t *in_vector,
+		 const cairo_slope_t *out_vector,
+		 const cairo_point_t *midpt,
+		 const cairo_point_t *inpt,
+		 const cairo_point_t *outpt,
+		 cairo_bool_t clockwise)
 {
-    int			clockwise = _cairo_stroker_face_clockwise (out, in);
-    cairo_point_t	*inpt, *outpt;
+    cairo_point_t stack_points[64], *points = stack_points;
+    int start, stop, step, i, npoints;
     cairo_status_t status;
 
-    if (in->cw.x == out->cw.x
-	&& in->cw.y == out->cw.y
-	&& in->ccw.x == out->ccw.x
-	&& in->ccw.y == out->ccw.y)
+    if (clockwise) {
+	step  = -1;
+
+	start = _cairo_pen_find_active_ccw_vertex_index (&stroker->pen,
+							 in_vector);
+	if (_cairo_slope_compare (&stroker->pen.vertices[start].slope_ccw,
+				  in_vector) < 0)
+	    start = _range_step (start, -1, stroker->pen.num_vertices);
+
+	stop  = _cairo_pen_find_active_ccw_vertex_index (&stroker->pen,
+							 out_vector);
+	if (_cairo_slope_compare (&stroker->pen.vertices[stop].slope_cw,
+				  out_vector) > 0)
+	{
+	    stop = _range_step (stop, 1, stroker->pen.num_vertices);
+	    if (_cairo_slope_compare (&stroker->pen.vertices[stop].slope_ccw,
+				      in_vector) < 0)
+	    {
+		goto BEVEL;
+	    }
+	}
+
+	npoints = start - stop;
+    } else {
+	step  = 1;
+
+	start = _cairo_pen_find_active_cw_vertex_index (&stroker->pen,
+							in_vector);
+	if (_cairo_slope_compare (&stroker->pen.vertices[start].slope_cw,
+				  in_vector) < 0)
+	    start = _range_step (start, 1, stroker->pen.num_vertices);
+
+	stop  = _cairo_pen_find_active_cw_vertex_index (&stroker->pen,
+							out_vector);
+	if (_cairo_slope_compare (&stroker->pen.vertices[stop].slope_ccw,
+				  out_vector) > 0)
+	{
+	    stop = _range_step (stop, -1, stroker->pen.num_vertices);
+	    if (_cairo_slope_compare (&stroker->pen.vertices[stop].slope_cw,
+				      in_vector) < 0)
+	    {
+		goto BEVEL;
+	    }
+	}
+
+	npoints = stop - start;
+    }
+    stop = _range_step (stop, step, stroker->pen.num_vertices);
+
+    if (npoints < 0)
+	npoints += stroker->pen.num_vertices;
+    npoints += 2;
+
+    if (npoints <= 1)
+	goto BEVEL;
+
+    if (npoints > ARRAY_LENGTH (stack_points)) {
+	points = _cairo_malloc_ab (npoints, sizeof (cairo_point_t));
+	if (unlikely (points == NULL))
+	    return _cairo_error (CAIRO_STATUS_NO_MEMORY);
+    }
+
+
+    /* Construct the fan. */
+    npoints = 0;
+    points[npoints++] = *inpt;
+    for (i = start;
+	 i != stop;
+	i = _range_step (i, step, stroker->pen.num_vertices))
+    {
+	points[npoints] = *midpt;
+	_translate_point (&points[npoints], &stroker->pen.vertices[i].point);
+	npoints++;
+    }
+    points[npoints++] = *outpt;
+
+    if (stroker->add_external_edge != NULL) {
+	for (i = 0; i < npoints - 1; i++) {
+	    if (clockwise) {
+		status = stroker->add_external_edge (stroker->closure,
+						     &points[i], &points[i+1]);
+	    } else {
+		status = stroker->add_external_edge (stroker->closure,
+						     &points[i+1], &points[i]);
+	    }
+	    if (unlikely (status))
+		break;
+	}
+    } else {
+	status = stroker->add_triangle_fan (stroker->closure,
+					    midpt, points, npoints);
+    }
+
+    if (points != stack_points)
+	free (points);
+
+    return status;
+
+BEVEL:
+    /* Ensure a leak free connection... */
+    if (stroker->add_external_edge != NULL) {
+	if (clockwise)
+	    return stroker->add_external_edge (stroker->closure, inpt, outpt);
+	else
+	    return stroker->add_external_edge (stroker->closure, outpt, inpt);
+    } else {
+	stack_points[0] = *midpt;
+	stack_points[1] = *inpt;
+	stack_points[2] = *outpt;
+	return stroker->add_triangle (stroker->closure, stack_points);
+    }
+}
+
+static cairo_status_t
+_cairo_stroker_join (cairo_stroker_t *stroker,
+		     const cairo_stroke_face_t *in,
+		     const cairo_stroke_face_t *out)
+{
+    int	 clockwise = _cairo_stroker_join_is_clockwise (out, in);
+    const cairo_point_t	*inpt, *outpt;
+    cairo_point_t points[4];
+    cairo_status_t status;
+
+    if (in->cw.x  == out->cw.x  && in->cw.y  == out->cw.y &&
+	in->ccw.x == out->ccw.x && in->ccw.y == out->ccw.y)
     {
 	return CAIRO_STATUS_SUCCESS;
     }
 
     if (clockwise) {
+	if (stroker->add_external_edge != NULL) {
+	    status = stroker->add_external_edge (stroker->closure,
+						 &out->cw, &in->point);
+	    if (unlikely (status))
+		return status;
+
+	    status = stroker->add_external_edge (stroker->closure,
+						 &in->point, &in->cw);
+	    if (unlikely (status))
+		return status;
+	}
+
 	inpt = &in->ccw;
 	outpt = &out->ccw;
     } else {
-	inpt = &in->cw;
-	outpt = &out->cw;
-    }
-
-    switch (stroker->style->line_join) {
-    case CAIRO_LINE_JOIN_ROUND: {
-	int i;
-	int start, step, stop;
-	cairo_point_t tri[3];
-	cairo_pen_t *pen = &stroker->pen;
-
-	tri[0] = in->point;
-	if (clockwise) {
-	    start =
-		_cairo_pen_find_active_ccw_vertex_index (pen, &in->dev_vector);
-	    stop =
-		_cairo_pen_find_active_ccw_vertex_index (pen, &out->dev_vector);
-	    step = -1;
-	} else {
-	    start =
-		_cairo_pen_find_active_cw_vertex_index (pen, &in->dev_vector);
-	    stop =
-		_cairo_pen_find_active_cw_vertex_index (pen, &out->dev_vector);
-	    step = +1;
-	}
+	if (stroker->add_external_edge != NULL) {
+	    status = stroker->add_external_edge (stroker->closure,
+						 &in->ccw, &in->point);
+	    if (unlikely (status))
+		return status;
 
-	i = start;
-	tri[1] = *inpt;
-	while (i != stop) {
-	    tri[2] = in->point;
-	    _translate_point (&tri[2], &pen->vertices[i].point);
-	    status = _cairo_traps_tessellate_triangle (stroker->traps, tri);
+	    status = stroker->add_external_edge (stroker->closure,
+						 &in->point, &out->ccw);
 	    if (unlikely (status))
 		return status;
-	    tri[1] = tri[2];
-	    i += step;
-	    if (i < 0)
-		i = pen->num_vertices - 1;
-	    if (i >= pen->num_vertices)
-		i = 0;
 	}
 
-	tri[2] = *outpt;
-
-	return _cairo_traps_tessellate_triangle (stroker->traps, tri);
+	inpt = &in->cw;
+	outpt = &out->cw;
     }
+
+    switch (stroker->style->line_join) {
+    case CAIRO_LINE_JOIN_ROUND:
+	/* construct a fan around the common midpoint */
+	return _tessellate_fan (stroker,
+				&in->dev_vector,
+				&out->dev_vector,
+				&in->point, inpt, outpt,
+				clockwise);
+
     case CAIRO_LINE_JOIN_MITER:
     default: {
 	/* dot product of incoming slope vector with outgoing slope vector */
-	double	in_dot_out = ((-in->usr_vector.x * out->usr_vector.x)+
-			      (-in->usr_vector.y * out->usr_vector.y));
+	double	in_dot_out = -in->usr_vector.x * out->usr_vector.x +
+			     -in->usr_vector.y * out->usr_vector.y;
 	double	ml = stroker->style->miter_limit;
 
 	/* Check the miter limit -- lines meeting at an acute angle
@@ -361,13 +515,10 @@ _cairo_stroker_join (cairo_stroker_t *stroker, cairo_stroke_face_t *in, cairo_st
 	 *	2 <= ml² (1 - in · out)
 	 *
 	 */
-	if (2 <= ml * ml * (1 - in_dot_out))
-	{
+	if (2 <= ml * ml * (1 - in_dot_out)) {
 	    double		x1, y1, x2, y2;
 	    double		mx, my;
 	    double		dx1, dx2, dy1, dy2;
-	    cairo_point_t	outer;
-	    cairo_point_t	quad[4];
 	    double		ix, iy;
 	    double		fdx1, fdy1, fdx2, fdy2;
 	    double		mdx, mdy;
@@ -435,74 +586,90 @@ _cairo_stroker_join (cairo_stroker_t *stroker, cairo_stroke_face_t *in, cairo_st
 	    if (_cairo_slope_compare_sgn (fdx1, fdy1, mdx, mdy) !=
 		_cairo_slope_compare_sgn (fdx2, fdy2, mdx, mdy))
 	    {
-		/*
-		 * Draw the quadrilateral
-		 */
-		outer.x = _cairo_fixed_from_double (mx);
-		outer.y = _cairo_fixed_from_double (my);
-
-		quad[0] = in->point;
-		quad[1] = *inpt;
-		quad[2] = outer;
-		quad[3] = *outpt;
-
-		return _cairo_traps_tessellate_convex_quad (stroker->traps, quad);
+		if (stroker->add_external_edge != NULL) {
+		    points[0].x = _cairo_fixed_from_double (mx);
+		    points[0].y = _cairo_fixed_from_double (my);
+
+		    if (clockwise) {
+			status = stroker->add_external_edge (stroker->closure,
+							     inpt, &points[0]);
+			if (unlikely (status))
+			    return status;
+
+			status = stroker->add_external_edge (stroker->closure,
+							     &points[0], outpt);
+			if (unlikely (status))
+			    return status;
+		    } else {
+			status = stroker->add_external_edge (stroker->closure,
+							     outpt, &points[0]);
+			if (unlikely (status))
+			    return status;
+
+			status = stroker->add_external_edge (stroker->closure,
+							     &points[0], inpt);
+			if (unlikely (status))
+			    return status;
+		    }
+
+		    return CAIRO_STATUS_SUCCESS;
+		} else {
+		    points[0] = in->point;
+		    points[1] = *inpt;
+		    points[2].x = _cairo_fixed_from_double (mx);
+		    points[2].y = _cairo_fixed_from_double (my);
+		    points[3] = *outpt;
+
+		    return stroker->add_convex_quad (stroker->closure, points);
+		}
 	    }
 	}
-	/* fall through ... */
     }
-    case CAIRO_LINE_JOIN_BEVEL: {
-	cairo_point_t tri[3];
-	tri[0] = in->point;
-	tri[1] = *inpt;
-	tri[2] = *outpt;
 
-	return _cairo_traps_tessellate_triangle (stroker->traps, tri);
-    }
+    /* fall through ... */
+
+    case CAIRO_LINE_JOIN_BEVEL:
+	if (stroker->add_external_edge != NULL) {
+	    if (clockwise) {
+		return stroker->add_external_edge (stroker->closure,
+						   inpt, outpt);
+	    } else {
+		return stroker->add_external_edge (stroker->closure,
+						   outpt, inpt);
+	    }
+	} else {
+	    points[0] = in->point;
+	    points[1] = *inpt;
+	    points[2] = *outpt;
+
+	    return stroker->add_triangle (stroker->closure, points);
+	}
     }
 }
 
 static cairo_status_t
-_cairo_stroker_add_cap (cairo_stroker_t *stroker, cairo_stroke_face_t *f)
+_cairo_stroker_add_cap (cairo_stroker_t *stroker,
+			const cairo_stroke_face_t *f)
 {
-    cairo_status_t	    status;
-
-    if (stroker->style->line_cap == CAIRO_LINE_CAP_BUTT)
-	return CAIRO_STATUS_SUCCESS;
-
     switch (stroker->style->line_cap) {
     case CAIRO_LINE_CAP_ROUND: {
-	int i;
-	int start, stop;
 	cairo_slope_t slope;
-	cairo_point_t tri[3];
-	cairo_pen_t *pen = &stroker->pen;
-
-	slope = f->dev_vector;
-	start = _cairo_pen_find_active_cw_vertex_index (pen, &slope);
-	slope.dx = -slope.dx;
-	slope.dy = -slope.dy;
-	stop = _cairo_pen_find_active_cw_vertex_index (pen, &slope);
-
-	tri[0] = f->point;
-	tri[1] = f->cw;
-	for (i=start; i != stop; i = (i+1) % pen->num_vertices) {
-	    tri[2] = f->point;
-	    _translate_point (&tri[2], &pen->vertices[i].point);
-	    status = _cairo_traps_tessellate_triangle (stroker->traps, tri);
-	    if (unlikely (status))
-		return status;
-	    tri[1] = tri[2];
-	}
-	tri[2] = f->ccw;
 
-	return _cairo_traps_tessellate_triangle (stroker->traps, tri);
+	slope.dx = -f->dev_vector.dx;
+	slope.dy = -f->dev_vector.dy;
+
+	return _tessellate_fan (stroker,
+				&f->dev_vector,
+				&slope,
+				&f->point, &f->cw, &f->ccw,
+				FALSE);
+
     }
+
     case CAIRO_LINE_CAP_SQUARE: {
 	double dx, dy;
 	cairo_slope_t	fvector;
-	cairo_point_t	occw, ocw;
-	cairo_polygon_t	polygon;
+	cairo_point_t	quad[4];
 
 	dx = f->usr_vector.x;
 	dy = f->usr_vector.y;
@@ -511,38 +678,52 @@ _cairo_stroker_add_cap (cairo_stroker_t *stroker, cairo_stroke_face_t *f)
 	cairo_matrix_transform_distance (stroker->ctm, &dx, &dy);
 	fvector.dx = _cairo_fixed_from_double (dx);
 	fvector.dy = _cairo_fixed_from_double (dy);
-	occw.x = f->ccw.x + fvector.dx;
-	occw.y = f->ccw.y + fvector.dy;
-	ocw.x = f->cw.x + fvector.dx;
-	ocw.y = f->cw.y + fvector.dy;
-
-	_cairo_polygon_init (&polygon);
-	_cairo_polygon_move_to (&polygon, &f->cw);
-	_cairo_polygon_line_to (&polygon, &ocw);
-	_cairo_polygon_line_to (&polygon, &occw);
-	_cairo_polygon_line_to (&polygon, &f->ccw);
-	_cairo_polygon_close (&polygon);
-	status = _cairo_polygon_status (&polygon);
-
-	if (status == CAIRO_STATUS_SUCCESS) {
-	    status = _cairo_bentley_ottmann_tessellate_polygon (stroker->traps,
-								&polygon,
-								CAIRO_FILL_RULE_WINDING);
-	}
 
-	_cairo_polygon_fini (&polygon);
+	quad[0] = f->ccw;
+	quad[1].x = f->ccw.x + fvector.dx;
+	quad[1].y = f->ccw.y + fvector.dy;
+	quad[2].x = f->cw.x + fvector.dx;
+	quad[2].y = f->cw.y + fvector.dy;
+	quad[3] = f->cw;
 
-	return status;
+	if (stroker->add_external_edge != NULL) {
+	    cairo_status_t status;
+
+	    status = stroker->add_external_edge (stroker->closure,
+						 &quad[0], &quad[1]);
+	    if (unlikely (status))
+		return status;
+
+	    status = stroker->add_external_edge (stroker->closure,
+						 &quad[1], &quad[2]);
+	    if (unlikely (status))
+		return status;
+
+	    status = stroker->add_external_edge (stroker->closure,
+						 &quad[2], &quad[3]);
+	    if (unlikely (status))
+		return status;
+
+	    return CAIRO_STATUS_SUCCESS;
+	} else {
+	    return stroker->add_convex_quad (stroker->closure, quad);
+	}
     }
+
     case CAIRO_LINE_CAP_BUTT:
     default:
-	return CAIRO_STATUS_SUCCESS;
+	if (stroker->add_external_edge != NULL) {
+	    return stroker->add_external_edge (stroker->closure,
+					       &f->ccw, &f->cw);
+	} else {
+	    return CAIRO_STATUS_SUCCESS;
+	}
     }
 }
 
 static cairo_status_t
 _cairo_stroker_add_leading_cap (cairo_stroker_t     *stroker,
-				cairo_stroke_face_t *face)
+				const cairo_stroke_face_t *face)
 {
     cairo_stroke_face_t reversed;
     cairo_point_t t;
@@ -563,7 +744,7 @@ _cairo_stroker_add_leading_cap (cairo_stroker_t     *stroker,
 
 static cairo_status_t
 _cairo_stroker_add_trailing_cap (cairo_stroker_t     *stroker,
-				 cairo_stroke_face_t *face)
+				 const cairo_stroke_face_t *face)
 {
     return _cairo_stroker_add_cap (stroker, face);
 }
@@ -617,55 +798,6 @@ _compute_normalized_device_slope (double *dx, double *dy,
 static void
 _compute_face (const cairo_point_t *point, cairo_slope_t *dev_slope,
 	       double slope_dx, double slope_dy,
-	       cairo_stroker_t *stroker, cairo_stroke_face_t *face);
-
-static cairo_status_t
-_cairo_stroker_add_caps (cairo_stroker_t *stroker)
-{
-    cairo_status_t status;
-    /* check for a degenerative sub_path */
-    if (stroker->has_initial_sub_path
-	&& !stroker->has_first_face
-	&& !stroker->has_current_face
-	&& stroker->style->line_cap == CAIRO_LINE_JOIN_ROUND)
-    {
-	/* pick an arbitrary slope to use */
-	double dx = 1.0, dy = 0.0;
-	cairo_slope_t slope = { CAIRO_FIXED_ONE, 0 };
-	cairo_stroke_face_t face;
-
-	_compute_normalized_device_slope (&dx, &dy, stroker->ctm_inverse, NULL);
-
-	/* arbitrarily choose first_point
-	 * first_point and current_point should be the same */
-	_compute_face (&stroker->first_point, &slope, dx, dy, stroker, &face);
-
-	status = _cairo_stroker_add_leading_cap (stroker, &face);
-	if (unlikely (status))
-	    return status;
-	status = _cairo_stroker_add_trailing_cap (stroker, &face);
-	if (unlikely (status))
-	    return status;
-    }
-
-    if (stroker->has_first_face) {
-	status = _cairo_stroker_add_leading_cap (stroker, &stroker->first_face);
-	if (unlikely (status))
-	    return status;
-    }
-
-    if (stroker->has_current_face) {
-	status = _cairo_stroker_add_trailing_cap (stroker, &stroker->current_face);
-	if (unlikely (status))
-	    return status;
-    }
-
-    return CAIRO_STATUS_SUCCESS;
-}
-
-static void
-_compute_face (const cairo_point_t *point, cairo_slope_t *dev_slope,
-	       double slope_dx, double slope_dy,
 	       cairo_stroker_t *stroker, cairo_stroke_face_t *face)
 {
     double face_dx, face_dy;
@@ -712,6 +844,55 @@ _compute_face (const cairo_point_t *point, cairo_slope_t *dev_slope,
 }
 
 static cairo_status_t
+_cairo_stroker_add_caps (cairo_stroker_t *stroker)
+{
+    cairo_status_t status;
+
+    /* check for a degenerative sub_path */
+    if (stroker->has_initial_sub_path
+	&& ! stroker->has_first_face
+	&& ! stroker->has_current_face
+	&& stroker->style->line_cap == CAIRO_LINE_JOIN_ROUND)
+    {
+	/* pick an arbitrary slope to use */
+	double dx = 1.0, dy = 0.0;
+	cairo_slope_t slope = { CAIRO_FIXED_ONE, 0 };
+	cairo_stroke_face_t face;
+
+	_compute_normalized_device_slope (&dx, &dy,
+					  stroker->ctm_inverse, NULL);
+
+	/* arbitrarily choose first_point
+	 * first_point and current_point should be the same */
+	_compute_face (&stroker->first_point, &slope, dx, dy, stroker, &face);
+
+	status = _cairo_stroker_add_leading_cap (stroker, &face);
+	if (unlikely (status))
+	    return status;
+
+	status = _cairo_stroker_add_trailing_cap (stroker, &face);
+	if (unlikely (status))
+	    return status;
+    }
+
+    if (stroker->has_first_face) {
+	status = _cairo_stroker_add_leading_cap (stroker,
+						 &stroker->first_face);
+	if (unlikely (status))
+	    return status;
+    }
+
+    if (stroker->has_current_face) {
+	status = _cairo_stroker_add_trailing_cap (stroker,
+						  &stroker->current_face);
+	if (unlikely (status))
+	    return status;
+    }
+
+    return CAIRO_STATUS_SUCCESS;
+}
+
+static cairo_status_t
 _cairo_stroker_add_sub_edge (cairo_stroker_t *stroker,
 			     const cairo_point_t *p1,
 			     const cairo_point_t *p2,
@@ -720,24 +901,42 @@ _cairo_stroker_add_sub_edge (cairo_stroker_t *stroker,
 			     cairo_stroke_face_t *start,
 			     cairo_stroke_face_t *end)
 {
-    cairo_point_t rectangle[4];
-
     _compute_face (p1, dev_slope, slope_dx, slope_dy, stroker, start);
-
-    /* XXX: This could be optimized slightly by not calling
-       _compute_face again but rather  translating the relevant
-       fields from start. */
-    _compute_face (p2, dev_slope, slope_dx, slope_dy, stroker, end);
+    *end = *start;
 
     if (p1->x == p2->x && p1->y == p2->y)
 	return CAIRO_STATUS_SUCCESS;
 
-    rectangle[0] = start->cw;
-    rectangle[1] = start->ccw;
-    rectangle[2] = end->ccw;
-    rectangle[3] = end->cw;
+    end->point = *p2;
+    end->ccw.x += p2->x - p1->x;
+    end->ccw.y += p2->y - p1->y;
+    end->cw.x += p2->x - p1->x;
+    end->cw.y += p2->y - p1->y;
+
+    if (stroker->add_external_edge != NULL) {
+	cairo_status_t status;
 
-    return _cairo_traps_tessellate_convex_quad (stroker->traps, rectangle);
+	status = stroker->add_external_edge (stroker->closure,
+					     &end->cw, &start->cw);
+	if (unlikely (status))
+	    return status;
+
+	status = stroker->add_external_edge (stroker->closure,
+					     &start->ccw, &end->ccw);
+	if (unlikely (status))
+	    return status;
+
+	return CAIRO_STATUS_SUCCESS;
+    } else {
+	cairo_point_t quad[4];
+
+	quad[0] = start->cw;
+	quad[1] = end->cw;
+	quad[2] = end->ccw;
+	quad[3] = start->ccw;
+
+	return stroker->add_convex_quad (stroker->closure, quad);
+    }
 }
 
 static cairo_status_t
@@ -747,6 +946,9 @@ _cairo_stroker_move_to (void *closure,
     cairo_stroker_t *stroker = closure;
     cairo_status_t status;
 
+    /* reset the dash pattern for new sub paths */
+    _cairo_stroker_dash_start (&stroker->dash);
+
     /* Cap the start and end of the previous sub path as needed */
     status = _cairo_stroker_add_caps (stroker);
     if (unlikely (status))
@@ -763,40 +965,29 @@ _cairo_stroker_move_to (void *closure,
 }
 
 static cairo_status_t
-_cairo_stroker_move_to_dashed (void *closure,
-			       const cairo_point_t *point)
-{
-    cairo_stroker_t *stroker = closure;
-
-    /* reset the dash pattern for new sub paths */
-    _cairo_stroker_dash_start (&stroker->dash);
-
-    return _cairo_stroker_move_to (closure, point);
-}
-
-static cairo_status_t
 _cairo_stroker_line_to (void *closure,
-			const cairo_point_t *p2)
+			const cairo_point_t *point)
 {
-    cairo_status_t status;
     cairo_stroker_t *stroker = closure;
     cairo_stroke_face_t start, end;
     cairo_point_t *p1 = &stroker->current_point;
     cairo_slope_t dev_slope;
     double slope_dx, slope_dy;
+    cairo_status_t status;
 
     stroker->has_initial_sub_path = TRUE;
 
-    if (p1->x == p2->x && p1->y == p2->y)
+    if (p1->x == point->x && p1->y == point->y)
 	return CAIRO_STATUS_SUCCESS;
 
-    _cairo_slope_init (&dev_slope, p1, p2);
-    slope_dx = _cairo_fixed_to_double (p2->x - p1->x);
-    slope_dy = _cairo_fixed_to_double (p2->y - p1->y);
-    _compute_normalized_device_slope (&slope_dx, &slope_dy, stroker->ctm_inverse, NULL);
+    _cairo_slope_init (&dev_slope, p1, point);
+    slope_dx = _cairo_fixed_to_double (point->x - p1->x);
+    slope_dy = _cairo_fixed_to_double (point->y - p1->y);
+    _compute_normalized_device_slope (&slope_dx, &slope_dy,
+				      stroker->ctm_inverse, NULL);
 
     status = _cairo_stroker_add_sub_edge (stroker,
-					  p1, p2,
+					  p1, point,
 					  &dev_slope,
 					  slope_dx, slope_dy,
 					  &start, &end);
@@ -805,10 +996,12 @@ _cairo_stroker_line_to (void *closure,
 
     if (stroker->has_current_face) {
 	/* Join with final face from previous segment */
-	status = _cairo_stroker_join (stroker, &stroker->current_face, &start);
+	status = _cairo_stroker_join (stroker,
+				      &stroker->current_face,
+				      &start);
 	if (unlikely (status))
 	    return status;
-    } else if (!stroker->has_first_face) {
+    } else if (! stroker->has_first_face) {
 	/* Save sub path's first face in case needed for closing join */
 	stroker->first_face = start;
 	stroker->has_first_face = TRUE;
@@ -816,7 +1009,7 @@ _cairo_stroker_line_to (void *closure,
     stroker->current_face = end;
     stroker->has_current_face = TRUE;
 
-    stroker->current_point = *p2;
+    stroker->current_point = *point;
 
     return CAIRO_STATUS_SUCCESS;
 }
@@ -858,7 +1051,7 @@ _cairo_stroker_line_to_dashed (void *closure,
     slope_dy = _cairo_fixed_to_double (p2->y - p1->y);
 
     if (! _compute_normalized_device_slope (&slope_dx, &slope_dy,
-					   stroker->ctm_inverse, &mag))
+					    stroker->ctm_inverse, &mag))
     {
 	return CAIRO_STATUS_SUCCESS;
     }
@@ -973,121 +1166,22 @@ _cairo_stroker_curve_to (void *closure,
 			 const cairo_point_t *d)
 {
     cairo_stroker_t *stroker = closure;
-    cairo_pen_stroke_spline_t spline_pen;
-    cairo_stroke_face_t start, end;
-    cairo_point_t extra_points[4];
-    cairo_point_t *a = &stroker->current_point;
-    double initial_slope_dx, initial_slope_dy;
-    double final_slope_dx, final_slope_dy;
-    cairo_status_t status;
-
-    status = _cairo_pen_stroke_spline_init (&spline_pen,
-					    &stroker->pen,
-					    a, b, c, d);
-    if (status == CAIRO_INT_STATUS_DEGENERATE)
-	return _cairo_stroker_line_to (closure, d);
-    else if (unlikely (status))
-	return status;
-
-    initial_slope_dx = _cairo_fixed_to_double (spline_pen.spline.initial_slope.dx);
-    initial_slope_dy = _cairo_fixed_to_double (spline_pen.spline.initial_slope.dy);
-    final_slope_dx = _cairo_fixed_to_double (spline_pen.spline.final_slope.dx);
-    final_slope_dy = _cairo_fixed_to_double (spline_pen.spline.final_slope.dy);
-
-    if (_compute_normalized_device_slope (&initial_slope_dx, &initial_slope_dy,
-					  stroker->ctm_inverse, NULL))
-    {
-	_compute_face (a,
-		       &spline_pen.spline.initial_slope,
-		       initial_slope_dx, initial_slope_dy,
-		       stroker, &start);
-    }
-
-    if (_compute_normalized_device_slope (&final_slope_dx, &final_slope_dy,
-					  stroker->ctm_inverse, NULL))
-    {
-	_compute_face (d,
-		       &spline_pen.spline.final_slope,
-		       final_slope_dx, final_slope_dy,
-		       stroker, &end);
-    }
-
-    if (stroker->has_current_face) {
-	status = _cairo_stroker_join (stroker, &stroker->current_face, &start);
-	if (unlikely (status))
-	    goto CLEANUP_PEN;
-    } else if (! stroker->has_first_face) {
-	stroker->first_face = start;
-	stroker->has_first_face = TRUE;
-    }
-    stroker->current_face = end;
-    stroker->has_current_face = TRUE;
-
-    extra_points[0] = start.cw;
-    extra_points[0].x -= start.point.x;
-    extra_points[0].y -= start.point.y;
-    extra_points[1] = start.ccw;
-    extra_points[1].x -= start.point.x;
-    extra_points[1].y -= start.point.y;
-    extra_points[2] = end.cw;
-    extra_points[2].x -= end.point.x;
-    extra_points[2].y -= end.point.y;
-    extra_points[3] = end.ccw;
-    extra_points[3].x -= end.point.x;
-    extra_points[3].y -= end.point.y;
-
-    status = _cairo_pen_add_points (&spline_pen.pen, extra_points, 4);
-    if (unlikely (status))
-	goto CLEANUP_PEN;
-
-    status = _cairo_pen_stroke_spline (&spline_pen,
-				       stroker->tolerance,
-				       stroker->traps);
-
-  CLEANUP_PEN:
-    _cairo_pen_stroke_spline_fini (&spline_pen);
-
-    stroker->current_point = *d;
-
-    return status;
-}
-
-/* We're using two different algorithms here for dashed and un-dashed
- * splines. The dashed algorithm uses the existing line dashing
- * code. It's linear in path length, but gets subtly wrong results for
- * self-intersecting paths (an outstanding but for self-intersecting
- * non-curved paths as well). The non-dashed algorithm tessellates a
- * single polygon for the whole curve. It handles the
- * self-intersecting problem, but it's (unsurprisingly) not O(n) and
- * more significantly, it doesn't yet handle dashes.
- *
- * The only reason we're doing split algorithms here is to
- * minimize the impact of fixing the splines-aren't-dashed bug for
- * 1.0.2. Long-term the right answer is to rewrite the whole pile
- * of stroking code so that the entire result is computed as a
- * single polygon that is tessellated, (that is, stroking can be
- * built on top of filling). That will solve the self-intersecting
- * problem. It will also increase the importance of implementing
- * an efficient and more robust tessellator.
- */
-static cairo_status_t
-_cairo_stroker_curve_to_dashed (void *closure,
-				const cairo_point_t *b,
-				const cairo_point_t *c,
-				const cairo_point_t *d)
-{
-    cairo_stroker_t *stroker = closure;
     cairo_spline_t spline;
-    cairo_point_t *a = &stroker->current_point;
     cairo_line_join_t line_join_save;
-    cairo_status_t status;
+    cairo_stroke_face_t face;
+    double slope_dx, slope_dy;
+    cairo_path_fixed_line_to_func_t *line_to;
+    cairo_status_t status = CAIRO_STATUS_SUCCESS;
+
+    line_to = stroker->dash.dashed ?
+	_cairo_stroker_line_to_dashed :
+	_cairo_stroker_line_to;
 
     if (! _cairo_spline_init (&spline,
-			      _cairo_stroker_line_to_dashed,
-			      stroker,
-			      a, b, c, d))
+			      line_to, stroker,
+			      &stroker->current_point, b, c, d))
     {
-	return _cairo_stroker_line_to_dashed (closure, d);
+	return line_to (closure, d);
     }
 
     /* If the line width is so small that the pen is reduced to a
@@ -1095,23 +1189,71 @@ _cairo_stroker_curve_to_dashed (void *closure,
     if (stroker->pen.num_vertices <= 1)
 	return CAIRO_STATUS_SUCCESS;
 
+    /* Compute the initial face */
+    if (! stroker->dash.dashed || stroker->dash.dash_on) {
+	slope_dx = _cairo_fixed_to_double (spline.initial_slope.dx);
+	slope_dy = _cairo_fixed_to_double (spline.initial_slope.dy);
+	if (_compute_normalized_device_slope (&slope_dx, &slope_dy,
+					      stroker->ctm_inverse, NULL))
+	{
+	    _compute_face (&stroker->current_point,
+			   &spline.initial_slope,
+			   slope_dx, slope_dy,
+			   stroker, &face);
+	}
+	if (stroker->has_current_face) {
+	    status = _cairo_stroker_join (stroker,
+					  &stroker->current_face, &face);
+	    if (unlikely (status))
+		return status;
+	} else if (! stroker->has_first_face) {
+	    stroker->first_face = face;
+	    stroker->has_first_face = TRUE;
+	}
+
+	stroker->current_face = face;
+	stroker->has_current_face = TRUE;
+    }
+
     /* Temporarily modify the stroker to use round joins to guarantee
      * smooth stroked curves. */
     line_join_save = stroker->style->line_join;
     stroker->style->line_join = CAIRO_LINE_JOIN_ROUND;
 
     status = _cairo_spline_decompose (&spline, stroker->tolerance);
+    if (unlikely (status))
+	return status;
+
+    /* And join the final face */
+    if (! stroker->dash.dashed || stroker->dash.dash_on) {
+	slope_dx = _cairo_fixed_to_double (spline.final_slope.dx);
+	slope_dy = _cairo_fixed_to_double (spline.final_slope.dy);
+	if (_compute_normalized_device_slope (&slope_dx, &slope_dy,
+					      stroker->ctm_inverse, NULL))
+	{
+	    _compute_face (&stroker->current_point,
+			   &spline.final_slope,
+			   slope_dx, slope_dy,
+			   stroker, &face);
+	}
+
+	status = _cairo_stroker_join (stroker, &stroker->current_face, &face);
+	if (unlikely (status))
+	    return status;
+
+	stroker->current_face = face;
+    }
 
     stroker->style->line_join = line_join_save;
 
-    return status;
+    return CAIRO_STATUS_SUCCESS;
 }
 
 static cairo_status_t
 _cairo_stroker_close_path (void *closure)
 {
-    cairo_status_t status;
     cairo_stroker_t *stroker = closure;
+    cairo_status_t status;
 
     if (stroker->dash.dashed)
 	status = _cairo_stroker_line_to_dashed (stroker, &stroker->first_point);
@@ -1122,7 +1264,9 @@ _cairo_stroker_close_path (void *closure)
 
     if (stroker->has_first_face && stroker->has_current_face) {
 	/* Join first and final faces of sub path */
-	status = _cairo_stroker_join (stroker, &stroker->current_face, &stroker->first_face);
+	status = _cairo_stroker_join (stroker,
+				      &stroker->current_face,
+				      &stroker->first_face);
 	if (unlikely (status))
 	    return status;
     } else {
@@ -1139,11 +1283,100 @@ _cairo_stroker_close_path (void *closure)
     return CAIRO_STATUS_SUCCESS;
 }
 
-static cairo_int_status_t
-_cairo_path_fixed_stroke_rectilinear (const cairo_path_fixed_t	*path,
-				      cairo_stroke_style_t	*stroke_style,
-				      const cairo_matrix_t	*ctm,
-				      cairo_traps_t		*traps);
+cairo_status_t
+_cairo_path_fixed_stroke_to_shaper (cairo_path_fixed_t	*path,
+				    cairo_stroke_style_t	*stroke_style,
+				    cairo_matrix_t	*ctm,
+				    cairo_matrix_t	*ctm_inverse,
+				    double		 tolerance,
+				    cairo_status_t (*add_triangle) (void *closure,
+								    const cairo_point_t triangle[3]),
+				    cairo_status_t (*add_triangle_fan) (void *closure,
+									const cairo_point_t *midpt,
+									const cairo_point_t *points,
+									int npoints),
+				    cairo_status_t (*add_convex_quad) (void *closure,
+								       const cairo_point_t quad[4]),
+				    void *closure)
+{
+    cairo_stroker_t stroker;
+    cairo_status_t status;
+
+    status = _cairo_stroker_init (&stroker, stroke_style,
+			          ctm, ctm_inverse, tolerance);
+    if (unlikely (status))
+	return status;
+
+    stroker.add_triangle = add_triangle;
+    stroker.add_triangle_fan = add_triangle_fan;
+    stroker.add_convex_quad = add_convex_quad;
+    stroker.closure = closure;
+
+    status = _cairo_path_fixed_interpret (path,
+					  CAIRO_DIRECTION_FORWARD,
+					  _cairo_stroker_move_to,
+					  stroker.dash.dashed ?
+					  _cairo_stroker_line_to_dashed :
+					  _cairo_stroker_line_to,
+					  _cairo_stroker_curve_to,
+					  _cairo_stroker_close_path,
+					  &stroker);
+
+    if (unlikely (status))
+	goto BAIL;
+
+    /* Cap the start and end of the final sub path as needed */
+    status = _cairo_stroker_add_caps (&stroker);
+
+BAIL:
+    _cairo_stroker_fini (&stroker);
+
+    return status;
+}
+
+cairo_status_t
+_cairo_path_fixed_stroke_to_polygon (const cairo_path_fixed_t	*path,
+				     cairo_stroke_style_t	*stroke_style,
+				     const cairo_matrix_t	*ctm,
+				     const cairo_matrix_t	*ctm_inverse,
+				     double		 tolerance,
+				     cairo_polygon_t *polygon)
+{
+    cairo_stroker_t stroker;
+    cairo_status_t status;
+
+    status = _cairo_stroker_init (&stroker, stroke_style,
+			          ctm, ctm_inverse, tolerance);
+    if (unlikely (status))
+	return status;
+
+    stroker.add_external_edge = _cairo_polygon_add_external_edge,
+    stroker.closure = polygon;
+
+    if (polygon->has_limits)
+	_cairo_stroker_limit (&stroker, &polygon->limits);
+
+    status = _cairo_path_fixed_interpret (path,
+					  CAIRO_DIRECTION_FORWARD,
+					  _cairo_stroker_move_to,
+					  stroker.dash.dashed ?
+					  _cairo_stroker_line_to_dashed :
+					  _cairo_stroker_line_to,
+					  _cairo_stroker_curve_to,
+					  _cairo_stroker_close_path,
+					  &stroker);
+
+    if (unlikely (status))
+	goto BAIL;
+
+    /* Cap the start and end of the final sub path as needed */
+    status = _cairo_stroker_add_caps (&stroker);
+
+BAIL:
+    _cairo_stroker_fini (&stroker);
+
+    return status;
+}
 
 cairo_status_t
 _cairo_path_fixed_stroke_to_traps (const cairo_path_fixed_t	*path,
@@ -1154,50 +1387,44 @@ _cairo_path_fixed_stroke_to_traps (const cairo_path_fixed_t	*path,
 				   cairo_traps_t	*traps)
 {
     cairo_status_t status;
-    cairo_stroker_t stroker;
+    cairo_polygon_t polygon;
 
     /* Before we do anything else, we attempt the rectilinear
      * stroker. It's careful to generate trapezoids that align to
      * device-pixel boundaries when possible. Many backends can render
      * those much faster than non-aligned trapezoids, (by using clip
      * regions, etc.) */
-    status = _cairo_path_fixed_stroke_rectilinear (path,
-						   stroke_style,
-						   ctm,
-						   traps);
-    if (status != CAIRO_INT_STATUS_UNSUPPORTED)
-	return status;
+    if (path->is_rectilinear) {
+	status = _cairo_path_fixed_stroke_rectilinear_to_traps (path,
+								stroke_style,
+								ctm,
+								traps);
+	if (status != CAIRO_INT_STATUS_UNSUPPORTED)
+	    return status;
+    }
 
-    status = _cairo_stroker_init (&stroker, stroke_style,
-			          ctm, ctm_inverse, tolerance,
-				  traps);
+    _cairo_polygon_init (&polygon);
+    if (traps->has_limits)
+	_cairo_polygon_limit (&polygon, &traps->limits);
+
+    status = _cairo_path_fixed_stroke_to_polygon (path,
+						 stroke_style,
+						 ctm,
+						 ctm_inverse,
+						 tolerance,
+						 &polygon);
     if (unlikely (status))
-	return status;
+	goto BAIL;
 
-    if (stroker.style->dash)
-	status = _cairo_path_fixed_interpret (path,
-					      CAIRO_DIRECTION_FORWARD,
-					      _cairo_stroker_move_to_dashed,
-					      _cairo_stroker_line_to_dashed,
-					      _cairo_stroker_curve_to_dashed,
-					      _cairo_stroker_close_path,
-					      &stroker);
-    else
-	status = _cairo_path_fixed_interpret (path,
-					      CAIRO_DIRECTION_FORWARD,
-					      _cairo_stroker_move_to,
-					      _cairo_stroker_line_to,
-					      _cairo_stroker_curve_to,
-					      _cairo_stroker_close_path,
-					      &stroker);
+    status = _cairo_polygon_status (&polygon);
     if (unlikely (status))
 	goto BAIL;
 
-    /* Cap the start and end of the final sub path as needed */
-    status = _cairo_stroker_add_caps (&stroker);
+    status = _cairo_bentley_ottmann_tessellate_polygon (traps, &polygon,
+							CAIRO_FILL_RULE_WINDING);
 
 BAIL:
-    _cairo_stroker_fini (&stroker);
+    _cairo_polygon_fini (&polygon);
 
     return status;
 }
@@ -1263,6 +1490,9 @@ _cairo_rectilinear_stroker_init (cairo_rectilinear_stroker_t	*stroker,
     _cairo_stroker_dash_init (&stroker->dash, stroke_style);
 
     stroker->has_bounds = FALSE;
+
+    /* As we incrementally tessellate, we do not eliminate self-intersections */
+    stroker->traps->has_intersections = TRUE;
 }
 
 static void
@@ -1583,8 +1813,7 @@ _cairo_rectilinear_stroker_line_to (void		*closure,
     cairo_status_t status;
 
     /* We only support horizontal or vertical elements. */
-    if (! (a->x == b->x || a->y == b->y))
-	return CAIRO_INT_STATUS_UNSUPPORTED;
+    assert (a->x == b->x || a->y == b->y);
 
     /* We don't draw anything for degenerate paths. */
     if (a->x == b->x && a->y == b->y)
@@ -1620,8 +1849,7 @@ _cairo_rectilinear_stroker_line_to_dashed (void		*closure,
 	return CAIRO_STATUS_SUCCESS;
 
     /* We only support horizontal or vertical elements. */
-    if (! (a->x == b->x || a->y == b->y))
-	return CAIRO_INT_STATUS_UNSUPPORTED;
+    assert (a->x == b->x || a->y == b->y);
 
     fully_in_bounds = TRUE;
     if (stroker->has_bounds &&
@@ -1736,11 +1964,11 @@ _cairo_rectilinear_stroker_close_path (void *closure)
     return CAIRO_STATUS_SUCCESS;
 }
 
-static cairo_int_status_t
-_cairo_path_fixed_stroke_rectilinear (const cairo_path_fixed_t	*path,
-				      cairo_stroke_style_t	*stroke_style,
-				      const cairo_matrix_t	*ctm,
-				      cairo_traps_t		*traps)
+cairo_int_status_t
+_cairo_path_fixed_stroke_rectilinear_to_traps (const cairo_path_fixed_t	*path,
+					       cairo_stroke_style_t	*stroke_style,
+					       const cairo_matrix_t	*ctm,
+					       cairo_traps_t		*traps)
 {
     cairo_rectilinear_stroker_t rectilinear_stroker;
     cairo_int_status_t status;
@@ -1755,8 +1983,8 @@ _cairo_path_fixed_stroke_rectilinear (const cairo_path_fixed_t	*path,
      * UNSUPPORTED from _cairo_rectilinear_stroker_line_to if any
      * non-rectilinear line_to is encountered.
      */
-    if (! path->is_rectilinear)
-	return CAIRO_INT_STATUS_UNSUPPORTED;
+    assert (path->is_rectilinear);
+
     if (stroke_style->line_join	!= CAIRO_LINE_JOIN_MITER)
 	return CAIRO_INT_STATUS_UNSUPPORTED;
     /* If the miter limit turns right angles into bevels, then we
@@ -1770,11 +1998,8 @@ _cairo_path_fixed_stroke_rectilinear (const cairo_path_fixed_t	*path,
     {
 	return CAIRO_INT_STATUS_UNSUPPORTED;
     }
-    if (! (_cairo_matrix_is_identity (ctm) ||
-	   _cairo_matrix_is_translation (ctm)))
-    {
+    if (! _cairo_matrix_has_unity_scale (ctm))
 	return CAIRO_INT_STATUS_UNSUPPORTED;
-    }
 
     _cairo_rectilinear_stroker_init (&rectilinear_stroker,
 				     stroke_style,