Optimize stroker by hoisting some calculations out of loops

sqrt and a few other floating-point operations were being done
repeatedly within a loop; those are now precalculated and passed
down where needed.

1 files changed, 87 insertions, 55 deletions

diff --git a/src/cairo-path-stroke.c b/src/cairo-path-stroke.c
index 5705e0a44..305f43f75 100644
--- a/src/cairo-path-stroke.c
+++ b/src/cairo-path-stroke.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
@@ -43,6 +44,8 @@ typedef struct cairo_stroker {
     cairo_matrix_t *ctm;
     cairo_matrix_t *ctm_inverse;
     double tolerance;
+    double ctm_determinant;
+    cairo_bool_t ctm_det_positive;
 
     cairo_traps_t *traps;
 
@@ -163,6 +166,12 @@ _cairo_stroker_init (cairo_stroker_t		*stroker,
     stroker->tolerance = tolerance;
     stroker->traps = traps;
 
+    _cairo_matrix_compute_determinant (stroker->ctm, &stroker->ctm_determinant);
+    if (stroker->ctm_determinant >= 0.0)
+	stroker->ctm_det_positive = TRUE;
+    else
+	stroker->ctm_det_positive = FALSE;
+
     status = _cairo_pen_init (&stroker->pen,
 		              stroke_style->line_width / 2.0,
 			      tolerance, ctm);
@@ -553,8 +562,42 @@ _cairo_stroker_add_trailing_cap (cairo_stroker_t     *stroker,
     return _cairo_stroker_add_cap (stroker, face);
 }
 
+static inline cairo_bool_t
+_compute_normalized_device_slope (double *dx, double *dy, cairo_matrix_t *ctm_inverse, double *mag_out)
+{
+    double dx0 = *dx, dy0 = *dy;
+    double mag;
+
+    cairo_matrix_transform_distance (ctm_inverse, &dx0, &dy0);
+
+    if (dx0 == 0.0 && dy0 == 0.0) {
+	if (mag_out)
+	    *mag_out = 0.0;
+	return FALSE;
+    }
+
+    if (dx0 == 0.0) {
+	mag = dy0;
+	*dx = 0.0;
+	*dy = 1.0;
+    } else if (dy0 == 0.0) {
+	mag = dx0;
+	*dx = 1.0;
+	*dy = 0.0;
+    } else {
+	mag = sqrt (dx0 * dx0 + dy0 * dy0);
+	*dx = dx0 / mag;
+	*dy = dy0 / mag;
+    }
+
+    if (mag_out)
+	*mag_out = mag;
+
+    return TRUE;
+}
+
 static void
-_compute_face (cairo_point_t *point, cairo_slope_t *slope, cairo_stroker_t *stroker, cairo_stroke_face_t *face);
+_compute_face (cairo_point_t *point, 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)
@@ -567,12 +610,14 @@ _cairo_stroker_add_caps (cairo_stroker_t *stroker)
 	&& stroker->style->line_cap == CAIRO_LINE_JOIN_ROUND)
     {
 	/* pick an arbitrary slope to use */
-	cairo_slope_t slope = {1, 0};
+	double dx = 1.0, dy = 0.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, stroker, &face);
+	_compute_face (&stroker->first_point, dx, dy, stroker, &face);
 
 	status = _cairo_stroker_add_leading_cap (stroker, &face);
 	if (status)
@@ -598,33 +643,11 @@ _cairo_stroker_add_caps (cairo_stroker_t *stroker)
 }
 
 static void
-_compute_face (cairo_point_t *point, cairo_slope_t *slope, cairo_stroker_t *stroker, cairo_stroke_face_t *face)
+_compute_face (cairo_point_t *point, double slope_dx, double slope_dy, cairo_stroker_t *stroker, cairo_stroke_face_t *face)
 {
-    double mag, det;
-    double line_dx, line_dy;
     double face_dx, face_dy;
-    cairo_point_double_t usr_vector;
     cairo_point_t offset_ccw, offset_cw;
 
-    line_dx = _cairo_fixed_to_double (slope->dx);
-    line_dy = _cairo_fixed_to_double (slope->dy);
-
-    /* faces are normal in user space, not device space */
-    cairo_matrix_transform_distance (stroker->ctm_inverse, &line_dx, &line_dy);
-
-    mag = sqrt (line_dx * line_dx + line_dy * line_dy);
-    if (mag == 0) {
-	/* XXX: Can't compute other face points. Do we want a tag in the face for this case? */
-	return;
-    }
-
-    /* normalize to unit length */
-    line_dx /= mag;
-    line_dy /= mag;
-
-    usr_vector.x = line_dx;
-    usr_vector.y = line_dy;
-
     /*
      * rotate to get a line_width/2 vector along the face, note that
      * the vector must be rotated the right direction in device space,
@@ -632,16 +655,15 @@ _compute_face (cairo_point_t *point, cairo_slope_t *slope, cairo_stroker_t *stro
      * whether the ctm reflects or not, and that can be determined
      * by looking at the determinant of the matrix.
      */
-    _cairo_matrix_compute_determinant (stroker->ctm, &det);
-    if (det >= 0)
+    if (stroker->ctm_det_positive)
     {
-	face_dx = - line_dy * (stroker->style->line_width / 2.0);
-	face_dy = line_dx * (stroker->style->line_width / 2.0);
+	face_dx = - slope_dy * (stroker->style->line_width / 2.0);
+	face_dy = slope_dx * (stroker->style->line_width / 2.0);
     }
     else
     {
-	face_dx = line_dy * (stroker->style->line_width / 2.0);
-	face_dy = - line_dx * (stroker->style->line_width / 2.0);
+	face_dx = slope_dy * (stroker->style->line_width / 2.0);
+	face_dy = - slope_dx * (stroker->style->line_width / 2.0);
     }
 
     /* back to device space */
@@ -660,25 +682,26 @@ _compute_face (cairo_point_t *point, cairo_slope_t *slope, cairo_stroker_t *stro
     face->cw = *point;
     _translate_point (&face->cw, &offset_cw);
 
-    face->usr_vector.x = usr_vector.x;
-    face->usr_vector.y = usr_vector.y;
+    face->usr_vector.x = slope_dx;
+    face->usr_vector.y = slope_dy;
 
-    face->dev_vector = *slope;
+    face->dev_vector.dx = _cairo_fixed_from_double (slope_dx);
+    face->dev_vector.dy = _cairo_fixed_from_double (slope_dy);
 }
 
 static cairo_status_t
 _cairo_stroker_add_sub_edge (cairo_stroker_t *stroker, cairo_point_t *p1, cairo_point_t *p2,
-			     cairo_slope_t *slope, cairo_stroke_face_t *start,
+			     double slope_dx, double slope_dy, cairo_stroke_face_t *start,
 			     cairo_stroke_face_t *end)
 {
     cairo_point_t rectangle[4];
 
-    _compute_face (p1, slope, stroker, start);
+    _compute_face (p1, 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, slope, stroker, end);
+    _compute_face (p2, slope_dx, slope_dy, stroker, end);
 
     if (p1->x == p2->x && p1->y == p2->y)
 	return CAIRO_STATUS_SUCCESS;
@@ -730,16 +753,18 @@ _cairo_stroker_line_to (void *closure, cairo_point_t *point)
     cairo_stroke_face_t start, end;
     cairo_point_t *p1 = &stroker->current_point;
     cairo_point_t *p2 = point;
-    cairo_slope_t slope;
+    double slope_dx, slope_dy;
 
     stroker->has_initial_sub_path = TRUE;
 
     if (p1->x == p2->x && p1->y == p2->y)
 	return CAIRO_STATUS_SUCCESS;
 
-    _cairo_slope_init (&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);
 
-    status = _cairo_stroker_add_sub_edge (stroker, p1, p2, &slope, &start, &end);
+    status = _cairo_stroker_add_sub_edge (stroker, p1, p2, slope_dx, slope_dy, &start, &end);
     if (status)
 	return status;
 
@@ -770,40 +795,37 @@ _cairo_stroker_line_to_dashed (void *closure, cairo_point_t *point)
     cairo_status_t status = CAIRO_STATUS_SUCCESS;
     cairo_stroker_t *stroker = closure;
     double mag, remain, step_length = 0;
-    double dx, dy;
+    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_slope_t slope;
 
     stroker->has_initial_sub_path = stroker->dash_starts_on;
 
     if (p1->x == p2->x && p1->y == p2->y)
 	return CAIRO_STATUS_SUCCESS;
 
-    _cairo_slope_init (&slope, p1, p2);
-
-    dx = _cairo_fixed_to_double (p2->x - p1->x);
-    dy = _cairo_fixed_to_double (p2->y - p1->y);
+    slope_dx = _cairo_fixed_to_double (p2->x - p1->x);
+    slope_dy = _cairo_fixed_to_double (p2->y - p1->y);
 
-    cairo_matrix_transform_distance (stroker->ctm_inverse, &dx, &dy);
+    if (!_compute_normalized_device_slope (&slope_dx, &slope_dy, stroker->ctm_inverse, &mag))
+	return CAIRO_STATUS_SUCCESS;
 
-    mag = sqrt (dx * dx + dy * dy);
     remain = mag;
     fd1 = *p1;
     while (remain) {
 	step_length = MIN (stroker->dash_remain, remain);
 	remain -= step_length;
-	dx2 = dx * (mag - remain)/mag;
-	dy2 = dy * (mag - remain)/mag;
+	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;
 
 	if (stroker->dash_on) {
-	    status = _cairo_stroker_add_sub_edge (stroker, &fd1, &fd2, &slope, &sub_start, &sub_end);
+	    status = _cairo_stroker_add_sub_edge (stroker, &fd1, &fd2, slope_dx, slope_dy, &sub_start, &sub_end);
 	    if (status)
 		return status;
 
@@ -854,7 +876,7 @@ _cairo_stroker_line_to_dashed (void *closure, cairo_point_t *point)
 	 * in the path. Whether this behaviour is desirable or not is debatable.
 	 * On one side these degnerate caps can not be reproduced with regular path stroking.
 	 * On the other side Acroread 7 also produces the degenerate caps. */
-	_compute_face (point, &slope, stroker, &stroker->current_face);
+	_compute_face (point, slope_dx, slope_dy, stroker, &stroker->current_face);
 	stroker->has_current_face = TRUE;
 	status = _cairo_stroker_add_leading_cap (stroker, &stroker->current_face);
 	if (status)
@@ -879,6 +901,8 @@ _cairo_stroker_curve_to (void *closure,
     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;
 
     status = _cairo_spline_init (&spline, a, b, c, d);
     if (status == CAIRO_INT_STATUS_DEGENERATE)
@@ -888,8 +912,16 @@ _cairo_stroker_curve_to (void *closure,
     if (status)
 	goto CLEANUP_SPLINE;
 
-    _compute_face (a, &spline.initial_slope, stroker, &start);
-    _compute_face (d, &spline.final_slope, stroker, &end);
+    initial_slope_dx = _cairo_fixed_to_double (spline.initial_slope.dx);
+    initial_slope_dy = _cairo_fixed_to_double (spline.initial_slope.dy);
+    final_slope_dx = _cairo_fixed_to_double (spline.final_slope.dx);
+    final_slope_dy = _cairo_fixed_to_double (spline.final_slope.dy);
+
+    if (_compute_normalized_device_slope (&initial_slope_dx, &initial_slope_dy, stroker->ctm_inverse, NULL))
+	_compute_face (a, 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, final_slope_dx, final_slope_dy, stroker, &end);
 
     if (stroker->has_current_face) {
 	status = _cairo_stroker_join (stroker, &stroker->current_face, &start);