Optimize dashed strokes, part 2

Pass down the bounding box to the stroker, and avoid doing expensive
calculations for dash segments that are outside the box.

4 files changed, 195 insertions, 39 deletions

diff --git a/src/cairo-path-stroke.c b/src/cairo-path-stroke.c
index 305f43f75..71510b1f9 100644
--- a/src/cairo-path-stroke.c
+++ b/src/cairo-path-stroke.c
@@ -67,6 +67,9 @@ typedef struct cairo_stroker {
     cairo_bool_t dash_on;
     cairo_bool_t dash_starts_on;
     double dash_remain;
+
+    cairo_bool_t has_bounds;
+    cairo_box_t bounds;
 } cairo_stroker_t;
 
 /* private functions */
@@ -187,6 +190,34 @@ _cairo_stroker_init (cairo_stroker_t		*stroker,
     else
 	stroker->dashed = FALSE;
 
+    stroker->has_bounds = _cairo_traps_get_limit (traps, &stroker->bounds);
+    if (stroker->has_bounds) {
+	/* Extend the bounds by the line width in each direction so that we correctly
+	 * capture segment endcaps and other similar renderings that would extend beyond
+	 * the segment itself.
+	 */
+	double width_x = stroker->style->line_width;
+	double width_y = stroker->style->line_width;
+
+	cairo_fixed_t fixed_x, fixed_y;
+
+	if (stroke_style->line_join == CAIRO_LINE_JOIN_MITER) {
+	    width_x *= stroker->style->miter_limit;
+	    width_y *= stroker->style->miter_limit;
+	}
+
+	cairo_matrix_transform_distance (stroker->ctm, &width_x, &width_y);
+
+	fixed_x = _cairo_fixed_from_double (width_x);
+	fixed_y = _cairo_fixed_from_double (width_y);
+
+	stroker->bounds.p1.x -= fixed_x;
+	stroker->bounds.p2.x += fixed_x;
+
+	stroker->bounds.p1.y -= fixed_y;
+	stroker->bounds.p2.y += fixed_y;
+    }
+
     return CAIRO_STATUS_SUCCESS;
 }
 
@@ -797,16 +828,24 @@ _cairo_stroker_line_to_dashed (void *closure, cairo_point_t *point)
     double mag, remain, step_length = 0;
     double slope_dx, slope_dy;
     double dx2, dy2;
-    cairo_point_t fd1, fd2;
     cairo_stroke_face_t sub_start, sub_end;
     cairo_point_t *p1 = &stroker->current_point;
     cairo_point_t *p2 = point;
+    cairo_bool_t fully_in_bounds = TRUE;
+    cairo_line_t segment;
 
     stroker->has_initial_sub_path = stroker->dash_starts_on;
 
     if (p1->x == p2->x && p1->y == p2->y)
 	return CAIRO_STATUS_SUCCESS;
 
+    if (stroker->has_bounds &&
+	(!_cairo_box_contains_point (&stroker->bounds, p1) ||
+	 !_cairo_box_contains_point (&stroker->bounds, p2)))
+    {
+	fully_in_bounds = FALSE;
+    }
+
     slope_dx = _cairo_fixed_to_double (p2->x - p1->x);
     slope_dy = _cairo_fixed_to_double (p2->y - p1->y);
 
@@ -814,58 +853,63 @@ _cairo_stroker_line_to_dashed (void *closure, cairo_point_t *point)
 	return CAIRO_STATUS_SUCCESS;
 
     remain = mag;
-    fd1 = *p1;
+    segment.p1 = *p1;
     while (remain) {
 	step_length = MIN (stroker->dash_remain, remain);
 	remain -= step_length;
 	dx2 = slope_dx * (mag - remain);
 	dy2 = slope_dy * (mag - remain);
 	cairo_matrix_transform_distance (stroker->ctm, &dx2, &dy2);
-	fd2.x = _cairo_fixed_from_double (dx2) + p1->x;
-	fd2.y = _cairo_fixed_from_double (dy2) + p1->y;
+	segment.p2.x = _cairo_fixed_from_double (dx2) + p1->x;
+	segment.p2.y = _cairo_fixed_from_double (dy2) + p1->y;
 
-	if (stroker->dash_on) {
-	    status = _cairo_stroker_add_sub_edge (stroker, &fd1, &fd2, slope_dx, slope_dy, &sub_start, &sub_end);
-	    if (status)
-		return status;
-
-	    if (stroker->has_current_face) {
-		/* Join with final face from previous segment */
-		status = _cairo_stroker_join (stroker, &stroker->current_face, &sub_start);
-		stroker->has_current_face = FALSE;
-		if (status)
-		    return status;
-	    } else if (!stroker->has_first_face && stroker->dash_starts_on) {
-		/* Save sub path's first face in case needed for closing join */
-		stroker->first_face = sub_start;
-		stroker->has_first_face = TRUE;
-	    } else {
-		/* Cap dash start if not connecting to a previous segment */
-		status = _cairo_stroker_add_leading_cap (stroker, &sub_start);
+	if (fully_in_bounds ||
+	    _cairo_box_intersects_line (&stroker->bounds, &segment))
+	{
+	    if (stroker->dash_on) {
+		status = _cairo_stroker_add_sub_edge (stroker, &segment.p1, &segment.p2, slope_dx, slope_dy, &sub_start, &sub_end);
 		if (status)
 		    return status;
-	    }
 
-	    if (remain) {
-		/* Cap dash end if not at end of segment */
-		status = _cairo_stroker_add_trailing_cap (stroker, &sub_end);
-		if (status)
-		    return status;
+		if (stroker->has_current_face) {
+		    /* Join with final face from previous segment */
+		    status = _cairo_stroker_join (stroker, &stroker->current_face, &sub_start);
+		    stroker->has_current_face = FALSE;
+		    if (status)
+			return status;
+		} else if (!stroker->has_first_face && stroker->dash_starts_on) {
+		    /* Save sub path's first face in case needed for closing join */
+		    stroker->first_face = sub_start;
+		    stroker->has_first_face = TRUE;
+		} else {
+		    /* Cap dash start if not connecting to a previous segment */
+		    status = _cairo_stroker_add_leading_cap (stroker, &sub_start);
+		    if (status)
+			return status;
+		}
+
+		if (remain) {
+		    /* Cap dash end if not at end of segment */
+		    status = _cairo_stroker_add_trailing_cap (stroker, &sub_end);
+		    if (status)
+			return status;
+		} else {
+		    stroker->current_face = sub_end;
+		    stroker->has_current_face = TRUE;
+		}
 	    } else {
-		stroker->current_face = sub_end;
-		stroker->has_current_face = TRUE;
-	    }
-	} else {
-	    if (stroker->has_current_face) {
-		/* Cap final face from previous segment */
-		status = _cairo_stroker_add_trailing_cap (stroker, &stroker->current_face);
-		if (status)
-		    return status;
-		stroker->has_current_face = FALSE;
+		if (stroker->has_current_face) {
+		    /* Cap final face from previous segment */
+		    status = _cairo_stroker_add_trailing_cap (stroker, &stroker->current_face);
+		    if (status)
+			return status;
+		    stroker->has_current_face = FALSE;
+		}
 	    }
 	}
+
 	_cairo_stroker_step_dash (stroker, step_length);
-	fd1 = fd2;
+	segment.p1 = segment.p2;
     }
 
     if (stroker->dash_on && !stroker->has_current_face) {
diff --git a/src/cairo-rectangle.c b/src/cairo-rectangle.c
index 5c686838e..58426f3ef 100644
--- a/src/cairo-rectangle.c
+++ b/src/cairo-rectangle.c
@@ -1,3 +1,4 @@
+/* -*- Mode: c; tab-width: 8; c-basic-offset: 4; indent-tabs-mode: t; -*- */
 /* cairo - a vector graphics library with display and print output
  *
  * Copyright © 2002 University of Southern California
@@ -83,3 +84,96 @@ _cairo_rectangle_intersect (cairo_rectangle_int_t *dest, cairo_rectangle_int_t *
 	dest->height = y2 - y1;
     }
 }
+
+
+#define P1x (line->p1.x)
+#define P1y (line->p1.y)
+#define P2x (line->p2.x)
+#define P2y (line->p2.y)
+#define B1x (box->p1.x)
+#define B1y (box->p1.y)
+#define B2x (box->p2.x)
+#define B2y (box->p2.y)
+
+/*
+ * Check whether any part of line intersects box.  This function essentially
+ * computes whether the ray starting at line->p1 in the direction of line->p2
+ * intersects the box before it reaches p2.  Normally, this is done
+ * by dividing by the lengths of the line projected onto each axis.  Because
+ * we're in fixed point, this function does a bit more work to avoid having to
+ * do the division -- we don't care about the actual intersection point, so
+ * it's of no interest to us.
+ */
+
+cairo_bool_t
+_cairo_box_intersects_line (cairo_box_t *box, cairo_line_t *line)
+{
+    cairo_fixed_t t1, t2, t3, t4;
+    cairo_int64_t t1y, t2y, t3x, t4x;
+
+    cairo_fixed_t xlen = P2x - P1x;
+    cairo_fixed_t ylen = P2y - P1y;
+
+    if (xlen) {
+	if (xlen > 0) {
+	    t1 = B1x - P1x;
+	    t2 = B2x - P1x;
+	} else {
+	    t1 = P1x - B2x;
+	    t2 = P1x - B1x;
+	    xlen = - xlen;
+	}
+
+	if ((t1 < 0 || t1 > xlen) &&
+	    (t2 < 0 || t2 > xlen))
+	    return FALSE;
+    } else {
+	/* Fully vertical line -- check that X is in bounds */
+	if (P1x < B1x || P1x > B2x)
+	    return FALSE;
+    }
+
+    if (ylen) {
+	if (ylen > 0) {
+	    t3 = B1y - P1y;
+	    t4 = B2y - P1y;
+	} else {
+	    t3 = P1y - B2y;
+	    t4 = P1y - B1y;
+	    ylen = - ylen;
+	}
+
+	if ((t3 < 0 || t3 > ylen) &&
+	    (t4 < 0 || t4 > ylen))
+	    return FALSE;
+    } else {
+	/* Fully horizontal line -- check Y */
+	if (P1y < B1y || P1y > B2y)
+	    return FALSE;
+    }
+
+    /* If we had a horizontal or vertical line, then it's already been checked */
+    if (P1x == P2x || P1y == P2y)
+	return TRUE;
+
+    /* Check overlap.  Note that t1 < t2 and t3 < t4 here. */
+    t1y = _cairo_int32x32_64_mul (t1, ylen);
+    t2y = _cairo_int32x32_64_mul (t2, ylen);
+    t3x = _cairo_int32x32_64_mul (t3, xlen);
+    t4x = _cairo_int32x32_64_mul (t4, xlen);
+
+    if (_cairo_int64_lt(t1y, t4x) &&
+	_cairo_int64_lt(t3x, t2y))
+	return TRUE;
+
+    return FALSE;
+}
+
+cairo_bool_t
+_cairo_box_contains_point (cairo_box_t *box, cairo_point_t *point)
+{
+    if (point->x < box->p1.x || point->x > box->p2.x ||
+	point->y < box->p1.y || point->y > box->p2.y)
+	return FALSE;
+    return TRUE;
+}
diff --git a/src/cairo-traps.c b/src/cairo-traps.c
index 8b009b1c9..8d7160730 100644
--- a/src/cairo-traps.c
+++ b/src/cairo-traps.c
@@ -75,6 +75,14 @@ _cairo_traps_limit (cairo_traps_t	*traps,
     traps->limits = *limits;
 }
 
+cairo_bool_t
+_cairo_traps_get_limit (cairo_traps_t *traps,
+			cairo_box_t   *limits)
+{
+    *limits = traps->limits;
+    return traps->has_limits;
+}
+
 void
 _cairo_traps_fini (cairo_traps_t *traps)
 {
diff --git a/src/cairoint.h b/src/cairoint.h
index 13f21fb74..2a1df7bba 100644
--- a/src/cairoint.h
+++ b/src/cairoint.h
@@ -179,6 +179,12 @@ _cairo_box_round_to_rectangle (cairo_box_t *box, cairo_rectangle_int_t *rectangl
 cairo_private void
 _cairo_rectangle_intersect (cairo_rectangle_int_t *dest, cairo_rectangle_int_t *src);
 
+cairo_private cairo_bool_t
+_cairo_box_intersects_line (cairo_box_t *box, cairo_line_t *line);
+
+cairo_private cairo_bool_t
+_cairo_box_contains_point (cairo_box_t *box, cairo_point_t *point);
+
 /* cairo_array.c structures and functions */
 
 cairo_private void
@@ -1996,6 +2002,10 @@ cairo_private void
 _cairo_traps_limit (cairo_traps_t	*traps,
 		    cairo_box_t		*limits);
 
+cairo_private cairo_bool_t
+_cairo_traps_get_limit (cairo_traps_t *traps,
+                        cairo_box_t   *limits);
+
 cairo_private cairo_status_t
 _cairo_traps_init_box (cairo_traps_t *traps,
 		       cairo_box_t   *box);