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.

1 files changed, 94 insertions, 0 deletions

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;
+}