[spline] Eliminate intermediate allocations during spline decomposition.

The spline decomposition code allocates and stores points in a temporary
buffer which is immediately consumed by the caller. If the caller supplies
a callback that handles each point computed along the spline, then we can
use the point immediately and avoid the allocation.

1 files changed, 166 insertions, 88 deletions

diff --git a/src/cairo-pen.c b/src/cairo-pen.c
index 425b3b965..43d344a19 100644
--- a/src/cairo-pen.c
+++ b/src/cairo-pen.c
@@ -1,6 +1,7 @@
 /* cairo - a vector graphics library with display and print output
  *
  * Copyright © 2002 University of Southern California
+ * Copyright © 2008 Chris Wilson
  *
  * This library is free software; you can redistribute it and/or
  * modify it either under the terms of the GNU Lesser General Public
@@ -32,6 +33,7 @@
  *
  * Contributor(s):
  *	Carl D. Worth <cworth@cworth.org>
+ *	Chris Wilson <chris@chris-wilson.co.uk>
  */
 
 #include "cairoint.h"
@@ -42,9 +44,6 @@ _cairo_pen_vertices_needed (double tolerance, double radius, cairo_matrix_t *mat
 static void
 _cairo_pen_compute_slopes (cairo_pen_t *pen);
 
-static void
-_cairo_pen_stroke_spline_half (cairo_pen_t *pen, cairo_spline_t *spline, cairo_direction_t dir, cairo_polygon_t *polygon);
-
 cairo_status_t
 _cairo_pen_init (cairo_pen_t	*pen,
 		 double		 radius,
@@ -104,7 +103,7 @@ _cairo_pen_fini (cairo_pen_t *pen)
 }
 
 cairo_status_t
-_cairo_pen_init_copy (cairo_pen_t *pen, cairo_pen_t *other)
+_cairo_pen_init_copy (cairo_pen_t *pen, const cairo_pen_t *other)
 {
     *pen = *other;
 
@@ -323,10 +322,9 @@ _cairo_pen_compute_slopes (cairo_pen_t *pen)
  * pen's "extra points" from the spline's initial and final slopes are
  * properly found when beginning the spline stroking.]
  */
-void
-_cairo_pen_find_active_cw_vertex_index (cairo_pen_t *pen,
-					cairo_slope_t *slope,
-					int *active)
+int
+_cairo_pen_find_active_cw_vertex_index (const cairo_pen_t *pen,
+					const cairo_slope_t *slope)
 {
     int i;
 
@@ -344,7 +342,7 @@ _cairo_pen_find_active_cw_vertex_index (cairo_pen_t *pen,
     if (i == pen->num_vertices)
 	i = 0;
 
-    *active = i;
+    return i;
 }
 
 /* Find active pen vertex for counterclockwise edge of stroke at the given slope.
@@ -352,13 +350,12 @@ _cairo_pen_find_active_cw_vertex_index (cairo_pen_t *pen,
  * Note: See the comments for _cairo_pen_find_active_cw_vertex_index
  * for some details about the strictness of the inequalities here.
  */
-void
-_cairo_pen_find_active_ccw_vertex_index (cairo_pen_t *pen,
-					 cairo_slope_t *slope,
-					 int *active)
+int
+_cairo_pen_find_active_ccw_vertex_index (const cairo_pen_t *pen,
+					 const cairo_slope_t *slope)
 {
-    int i;
     cairo_slope_t slope_reverse;
+    int i;
 
     slope_reverse = *slope;
     slope_reverse.dx = -slope_reverse.dx;
@@ -378,56 +375,26 @@ _cairo_pen_find_active_ccw_vertex_index (cairo_pen_t *pen,
     if (i < 0)
 	i = pen->num_vertices - 1;
 
-    *active = i;
+    return i;
 }
 
-static void
-_cairo_pen_stroke_spline_half (cairo_pen_t *pen,
-			       cairo_spline_t *spline,
-			       cairo_direction_t dir,
-			       cairo_polygon_t *polygon)
+static int
+_cairo_pen_stroke_spline_add_convolved_point (cairo_pen_stroke_spline_t	*stroker,
+					      const cairo_point_t *last_point,
+					      const cairo_slope_t *slope,
+					      cairo_point_t *last_hull_point,
+					      int active,
+					      int step)
 {
-    int i;
-    int start, stop, step;
-    int active = 0;
-    cairo_point_t hull_point;
-    cairo_slope_t slope, initial_slope, final_slope;
-    cairo_point_t *point = spline->points;
-    int num_points = spline->num_points;
-
-    if (dir == CAIRO_DIRECTION_FORWARD) {
-	start = 0;
-	stop = num_points;
-	step = 1;
-	initial_slope = spline->initial_slope;
-	final_slope = spline->final_slope;
-    } else {
-	start = num_points - 1;
-	stop = -1;
-	step = -1;
-	initial_slope = spline->final_slope;
-	initial_slope.dx = -initial_slope.dx;
-	initial_slope.dy = -initial_slope.dy;
-	final_slope = spline->initial_slope;
-	final_slope.dx = -final_slope.dx;
-	final_slope.dy = -final_slope.dy;
-    }
-
-    _cairo_pen_find_active_cw_vertex_index (pen,
-	                                    &initial_slope,
-					    &active);
+    do {
+	cairo_point_t hull_point;
 
-    i = start;
-    while (i != stop) {
-	hull_point.x = point[i].x + pen->vertices[active].point.x;
-	hull_point.y = point[i].y + pen->vertices[active].point.y;
-
-	_cairo_polygon_line_to (polygon, &hull_point);
-
-	if (i + step == stop)
-	    slope = final_slope;
-	else
-	    _cairo_slope_init (&slope, &point[i], &point[i+step]);
+	hull_point.x = last_point->x + stroker->pen.vertices[active].point.x;
+	hull_point.y = last_point->y + stroker->pen.vertices[active].point.y;
+	_cairo_polygon_add_edge (&stroker->polygon,
+				 last_hull_point, &hull_point,
+				 step);
+	*last_hull_point = hull_point;
 
 	/* The strict inequalities here ensure that if a spline slope
 	 * compares identically with either of the slopes of the
@@ -439,53 +406,164 @@ _cairo_pen_stroke_spline_half (cairo_pen_t *pen,
 	 * consider it unequal and reject. This is due to the inherent
 	 * ambiguity when comparing slopes that differ by exactly
 	 * pi. */
-	if (_cairo_slope_compare (&slope, &pen->vertices[active].slope_ccw) > 0) {
-	    if (++active == pen->num_vertices)
+	if (_cairo_slope_compare (slope,
+				  &stroker->pen.vertices[active].slope_ccw) > 0)
+	{
+	    if (++active == stroker->pen.num_vertices)
 		active = 0;
-	} else if (_cairo_slope_compare (&slope, &pen->vertices[active].slope_cw) < 0) {
+	}
+	else if (_cairo_slope_compare (slope,
+				       &stroker->pen.vertices[active].slope_cw) < 0)
+	{
 	    if (--active == -1)
-		active = pen->num_vertices - 1;
-	} else {
-	    i += step;
+		active = stroker->pen.num_vertices - 1;
 	}
-    }
+	else
+	{
+	    return active;
+	}
+    } while (TRUE);
 }
 
+
 /* Compute outline of a given spline using the pen.
-   The trapezoids needed to fill that outline will be added to traps
-*/
+ * The trapezoids needed to fill that outline will be added to traps
+ */
 cairo_status_t
-_cairo_pen_stroke_spline (cairo_pen_t		*pen,
-			  cairo_spline_t	*spline,
-			  double		tolerance,
-			  cairo_traps_t		*traps)
+_cairo_pen_stroke_spline (cairo_pen_stroke_spline_t	*stroker,
+			  double			 tolerance,
+			  cairo_traps_t			*traps)
 {
     cairo_status_t status;
-    cairo_polygon_t polygon;
+    cairo_slope_t slope;
 
     /* If the line width is so small that the pen is reduced to a
        single point, then we have nothing to do. */
-    if (pen->num_vertices <= 1)
+    if (stroker->pen.num_vertices <= 1)
 	return CAIRO_STATUS_SUCCESS;
 
-    _cairo_polygon_init (&polygon);
-
-    status = _cairo_spline_decompose (spline, tolerance);
+    /* open the polygon */
+    slope = stroker->spline.initial_slope;
+    stroker->forward_vertex =
+	_cairo_pen_find_active_cw_vertex_index (&stroker->pen, &slope);
+    stroker->forward_hull_point.x = stroker->last_point.x +
+	stroker->pen.vertices[stroker->forward_vertex].point.x;
+    stroker->forward_hull_point.y = stroker->last_point.y +
+	stroker->pen.vertices[stroker->forward_vertex].point.y;
+
+    slope.dx = -slope.dx;
+    slope.dy = -slope.dy;
+    stroker->backward_vertex =
+	_cairo_pen_find_active_cw_vertex_index (&stroker->pen, &slope);
+    stroker->backward_hull_point.x = stroker->last_point.x +
+	stroker->pen.vertices[stroker->backward_vertex].point.x;
+    stroker->backward_hull_point.y = stroker->last_point.y +
+	stroker->pen.vertices[stroker->backward_vertex].point.y;
+
+    _cairo_polygon_add_edge (&stroker->polygon,
+			     &stroker->backward_hull_point,
+			     &stroker->forward_hull_point,
+			     1);
+
+    _cairo_spline_decompose (&stroker->spline, tolerance);
+
+    /* close the polygon */
+    slope = stroker->spline.final_slope;
+    _cairo_pen_stroke_spline_add_convolved_point (stroker,
+						  &stroker->last_point,
+						  &slope,
+						  &stroker->forward_hull_point,
+						  stroker->forward_vertex,
+						  1);
+
+    slope.dx = -slope.dx;
+    slope.dy = -slope.dy;
+    _cairo_pen_stroke_spline_add_convolved_point (stroker,
+						  &stroker->last_point,
+						  &slope,
+						  &stroker->backward_hull_point,
+						  stroker->backward_vertex,
+						  -1);
+
+    _cairo_polygon_add_edge (&stroker->polygon,
+			     &stroker->forward_hull_point,
+			     &stroker->backward_hull_point,
+			     1);
+
+    status = _cairo_polygon_status (&stroker->polygon);
     if (status)
 	goto BAIL;
 
-    _cairo_pen_stroke_spline_half (pen, spline, CAIRO_DIRECTION_FORWARD, &polygon);
+    status = _cairo_bentley_ottmann_tessellate_polygon (traps,
+							&stroker->polygon,
+							CAIRO_FILL_RULE_WINDING);
+BAIL:
 
-    _cairo_pen_stroke_spline_half (pen, spline, CAIRO_DIRECTION_REVERSE, &polygon);
+    return status;
+}
 
-    _cairo_polygon_close (&polygon);
-    status = _cairo_polygon_status (&polygon);
-    if (status)
-	goto BAIL;
+static void
+_cairo_pen_stroke_spline_add_point (cairo_pen_stroke_spline_t	*stroker,
+				    const cairo_point_t		*point)
+{
+    cairo_slope_t slope;
+
+    _cairo_slope_init (&slope, &stroker->last_point, point);
+    stroker->forward_vertex =
+	_cairo_pen_stroke_spline_add_convolved_point (stroker,
+						      &stroker->last_point,
+						      &slope,
+						      &stroker->forward_hull_point,
+						      stroker->forward_vertex,
+						      1);
+
+    slope.dx = -slope.dx;
+    slope.dy = -slope.dy;
+    stroker->backward_vertex =
+	_cairo_pen_stroke_spline_add_convolved_point (stroker,
+						      &stroker->last_point,
+						      &slope,
+						      &stroker->backward_hull_point,
+						      stroker->backward_vertex,
+						      -1);
+    stroker->last_point = *point;
+}
 
-    status = _cairo_bentley_ottmann_tessellate_polygon (traps, &polygon, CAIRO_FILL_RULE_WINDING);
-BAIL:
-    _cairo_polygon_fini (&polygon);
+cairo_int_status_t
+_cairo_pen_stroke_spline_init (cairo_pen_stroke_spline_t *stroker,
+			       const cairo_pen_t *pen,
+			       const cairo_point_t *a,
+			       const cairo_point_t *b,
+			       const cairo_point_t *c,
+			       const cairo_point_t *d)
+{
+    cairo_int_status_t status;
 
-    return status;
+    if (! _cairo_spline_init (&stroker->spline,
+			      (cairo_add_point_func_t) _cairo_pen_stroke_spline_add_point,
+			      stroker,
+			      a, b, c, d))
+    {
+	return CAIRO_INT_STATUS_DEGENERATE;
+    }
+
+    status = _cairo_pen_init_copy (&stroker->pen, pen);
+    if (status) {
+	_cairo_spline_fini (&stroker->spline);
+	return status;
+    }
+
+    _cairo_polygon_init (&stroker->polygon);
+
+    stroker->last_point = *a;
+
+    return CAIRO_STATUS_SUCCESS;
+}
+
+void
+_cairo_pen_stroke_spline_fini (cairo_pen_stroke_spline_t *stroker)
+{
+    _cairo_polygon_fini (&stroker->polygon);
+    _cairo_spline_fini (&stroker->spline);
+    _cairo_pen_fini (&stroker->pen);
 }