path: Compute coarse bounds upon construction.

Frequently we only need the coarse path bounds, so avoid walking over
the list of points once more as we can cheaply track the extents during
construction.

1 files changed, 76 insertions, 7 deletions

diff --git a/src/cairo-path-fixed.c b/src/cairo-path-fixed.c
index 958c85c09..be071d168 100644
--- a/src/cairo-path-fixed.c
+++ b/src/cairo-path-fixed.c
@@ -96,11 +96,15 @@ _cairo_path_fixed_init (cairo_path_fixed_t *path)
     path->current_point.x = 0;
     path->current_point.y = 0;
     path->last_move_point = path->current_point;
+    path->has_last_move_point = FALSE;
     path->has_current_point = FALSE;
     path->has_curve_to = FALSE;
     path->is_rectilinear = TRUE;
     path->maybe_fill_region = TRUE;
     path->is_empty_fill = TRUE;
+
+    path->extents.p1.x = path->extents.p1.y = INT_MAX;
+    path->extents.p2.x = path->extents.p2.y = INT_MIN;
 }
 
 cairo_status_t
@@ -119,12 +123,15 @@ _cairo_path_fixed_init_copy (cairo_path_fixed_t *path,
 
     path->current_point = other->current_point;
     path->last_move_point = other->last_move_point;
+    path->has_last_move_point = other->has_last_move_point;
     path->has_current_point = other->has_current_point;
     path->has_curve_to = other->has_curve_to;
     path->is_rectilinear = other->is_rectilinear;
     path->maybe_fill_region = other->maybe_fill_region;
     path->is_empty_fill = other->is_empty_fill;
 
+    path->extents = other->extents;
+
     path->buf.base.num_ops = other->buf.base.num_ops;
     path->buf.base.num_points = other->buf.base.num_points;
     path->buf.base.buf_size = other->buf.base.buf_size;
@@ -176,6 +183,8 @@ _cairo_path_fixed_hash (const cairo_path_fixed_t *path)
     const cairo_path_buf_t *buf;
     int num_points, num_ops;
 
+    hash = _cairo_hash_bytes (hash, &path->extents, sizeof (path->extents));
+
     num_ops = num_points = 0;
     cairo_path_foreach_buf_start (buf, path) {
 	hash = _cairo_hash_bytes (hash, buf->op,
@@ -231,6 +240,14 @@ _cairo_path_fixed_equal (const cairo_path_fixed_t *a,
 	return FALSE;
     }
 
+    if (a->extents.p1.x != b->extents.p1.x ||
+	a->extents.p1.y != b->extents.p1.y ||
+	a->extents.p2.x != b->extents.p2.x ||
+	a->extents.p2.y != b->extents.p2.y)
+    {
+	return FALSE;
+    }
+
     num_ops_a = num_points_a = 0;
     if (a != NULL) {
 	cairo_path_foreach_buf_start (buf_a, a) {
@@ -365,6 +382,21 @@ _cairo_path_last_op (cairo_path_fixed_t *path)
     return buf->op[buf->num_ops - 1];
 }
 
+static inline void
+_cairo_path_fixed_extents_add (cairo_path_fixed_t *path,
+			       const cairo_point_t *point)
+{
+    if (point->x < path->extents.p1.x)
+	path->extents.p1.x = point->x;
+    if (point->y < path->extents.p1.y)
+	path->extents.p1.y = point->y;
+
+    if (point->x > path->extents.p2.x)
+	path->extents.p2.x = point->x;
+    if (point->y > path->extents.p2.y)
+	path->extents.p2.y = point->y;
+}
+
 cairo_status_t
 _cairo_path_fixed_move_to (cairo_path_fixed_t  *path,
 			   cairo_fixed_t	x,
@@ -403,6 +435,7 @@ _cairo_path_fixed_move_to (cairo_path_fixed_t  *path,
 
     path->current_point = point;
     path->last_move_point = point;
+    path->has_last_move_point = TRUE;
     path->has_current_point = TRUE;
 
     return CAIRO_STATUS_SUCCESS;
@@ -511,6 +544,11 @@ _cairo_path_fixed_line_to (cairo_path_fixed_t *path,
     }
 
     path->current_point = point;
+    if (path->has_last_move_point) {
+	_cairo_path_fixed_extents_add (path, &path->last_move_point);
+	path->has_last_move_point = FALSE;
+    }
+    _cairo_path_fixed_extents_add (path, &point);
     return CAIRO_STATUS_SUCCESS;
 }
 
@@ -557,6 +595,15 @@ _cairo_path_fixed_curve_to (cairo_path_fixed_t	*path,
     path->is_rectilinear = FALSE;
     path->maybe_fill_region = FALSE;
 
+    /* coarse bounds */
+    if (path->has_last_move_point) {
+	_cairo_path_fixed_extents_add (path, &path->last_move_point);
+	path->has_last_move_point = FALSE;
+    }
+    _cairo_path_fixed_extents_add (path, &point[0]);
+    _cairo_path_fixed_extents_add (path, &point[1]);
+    _cairo_path_fixed_extents_add (path, &point[2]);
+
     return CAIRO_STATUS_SUCCESS;
 }
 
@@ -907,6 +954,12 @@ _cairo_path_fixed_offset_and_scale (cairo_path_fixed_t *path,
 	     buf->points[i].y += offy;
 	 }
     } cairo_path_foreach_buf_end (buf, path);
+
+    path->extents.p1.x = _cairo_fixed_mul (scalex, path->extents.p1.x) + offx;
+    path->extents.p2.x = _cairo_fixed_mul (scalex, path->extents.p2.x) + offx;
+
+    path->extents.p1.y = _cairo_fixed_mul (scaley, path->extents.p1.y) + offy;
+    path->extents.p2.y = _cairo_fixed_mul (scaley, path->extents.p2.y) + offy;
 }
 
 void
@@ -927,9 +980,9 @@ _cairo_path_fixed_translate (cairo_path_fixed_t *path,
     }
 
     path->last_move_point.x += offx;
-    path->last_move_point.y += offx;
+    path->last_move_point.y += offy;
     path->current_point.x += offx;
-    path->current_point.y += offx;
+    path->current_point.y += offy;
 
     cairo_path_foreach_buf_start (buf, path) {
 	 for (i = 0; i < buf->num_points; i++) {
@@ -937,6 +990,11 @@ _cairo_path_fixed_translate (cairo_path_fixed_t *path,
 	     buf->points[i].y += offy;
 	 }
     } cairo_path_foreach_buf_end (buf, path);
+
+    path->extents.p1.x += offx;
+    path->extents.p1.y += offy;
+    path->extents.p2.x += offx;
+    path->extents.p2.y += offy;
 }
 
 /**
@@ -960,14 +1018,22 @@ _cairo_path_fixed_transform (cairo_path_fixed_t	*path,
 
     if (matrix->yx == 0.0 && matrix->xy == 0.0) {
 	/* Fast path for the common case of scale+transform */
-	_cairo_path_fixed_offset_and_scale (path,
-					    _cairo_fixed_from_double (matrix->x0),
-					    _cairo_fixed_from_double (matrix->y0),
-					    _cairo_fixed_from_double (matrix->xx),
-					    _cairo_fixed_from_double (matrix->yy));
+	 if (matrix->xx == 1. && matrix->yy == 1.) {
+	     _cairo_path_fixed_translate (path,
+					  _cairo_fixed_from_double (matrix->x0),
+					  _cairo_fixed_from_double (matrix->y0));
+	 } else {
+	     _cairo_path_fixed_offset_and_scale (path,
+						 _cairo_fixed_from_double (matrix->x0),
+						 _cairo_fixed_from_double (matrix->y0),
+						 _cairo_fixed_from_double (matrix->xx),
+						 _cairo_fixed_from_double (matrix->yy));
+	 }
 	return;
     }
 
+    path->extents.p1.x = path->extents.p1.y = INT_MAX;
+    path->extents.p2.x = path->extents.p2.y = INT_MIN;
     path->maybe_fill_region = FALSE;
     cairo_path_foreach_buf_start (buf, path) {
 	 for (i = 0; i < buf->num_points; i++) {
@@ -978,6 +1044,9 @@ _cairo_path_fixed_transform (cairo_path_fixed_t	*path,
 
 	    buf->points[i].x = _cairo_fixed_from_double (dx);
 	    buf->points[i].y = _cairo_fixed_from_double (dy);
+
+	    /* XXX need to eliminate surplus move-to's? */
+	    _cairo_path_fixed_extents_add (path, &buf->points[i]);
 	 }
     } cairo_path_foreach_buf_end (buf, path);
 }