Attachment 8174 Details for Bug 9276 – Patch to fix pen, miter join, and stroke face computation.

[patch] Patch to fix pen, miter join, and stroke face computation.

fix-9276.patch (text/plain), 9.23 KB, created by M Joonas Pihlaja on 2006-12-19 23:51:59 UTC

(hide)

Description:

Filename:

MIME Type:

Creator: M Joonas Pihlaja

Created: 2006-12-19 23:51:59 UTC

Size: 9.23 KB

patch

obsolete

>diff --git a/src/cairo-path-stroke.c b/src/cairo-path-stroke.c
>index 792fbfa..b7e0742 100644
>--- a/src/cairo-path-stroke.c
>+++ b/src/cairo-path-stroke.c
>@@ -36,6 +36,9 @@
> 
> #include "cairoint.h"
> 
>+/* device space maximum representable double. */
>+#define RANGE_MAX (32767.0 + 65535.0/65536.0)
>+
> typedef struct cairo_stroker {
>     cairo_stroke_style_t	*style;
> 
>@@ -108,6 +111,11 @@ _cairo_stroker_face_clockwise (cairo_str
> 
> static cairo_status_t
> _cairo_stroker_join (cairo_stroker_t *stroker, cairo_stroke_face_t *in, cairo_stroke_face_t *out);
>+static double
>+_cairo_stroker_hypot (double x, double y);
>+
>+static double
>+_cairo_stroker_normalise_vector (double *x, double *y);
> 
> static void
> _cairo_stroker_start_dash (cairo_stroker_t *stroker)
>@@ -260,8 +268,8 @@ _cairo_stroker_join (cairo_stroker_t *st
>     case CAIRO_LINE_JOIN_MITER:
>     default: {
> 	/* dot product of incoming slope vector with outgoing slope vector */
>-	double	in_dot_out = ((-in->usr_vector.x * out->usr_vector.x)+
>-			      (-in->usr_vector.y * out->usr_vector.y));
>+	double	in_dot_out = ((in->usr_vector.x * out->usr_vector.x)+
>+			      (in->usr_vector.y * out->usr_vector.y));
> 	double	ml = stroker->style->miter_limit;
> 
> 	/*
>@@ -275,13 +283,11 @@ _cairo_stroker_join (cairo_stroker_t *st
> 	 *
> 	 * where psi is the angle between in and out
> 	 *
>-	 *				secant(psi/2) = 1/sin(psi/2)
>-	 *	1/sin(psi/2) <= ml
>-	 *	1 <= ml sin(psi/2)
>-	 *	1 <= mlÂ² sinÂ²(psi/2)
>-	 *	2 <= mlÂ² 2 sinÂ²(psi/2)
>-	 *				2Â·sinÂ²(psi/2) = 1-cos(psi)
>-	 *	2 <= mlÂ² (1-cos(psi))
>+	 *				secant(psi/2) = 1/cos(psi/2)
>+	 *	1/cos(psi/2) <= ml
>+	 *	1 <= ml cos(psi/2)
>+	 *	1 <= mlÂ² cos(psi/2)Â²
>+	 *      2 <= mlÂ² (1 + cos(psi))
> 	 *
> 	 *				in Â· out = |in| |out| cos (psi)
> 	 *
>@@ -289,10 +295,10 @@ _cairo_stroker_join (cairo_stroker_t *st
> 	 *
> 	 *				in Â· out = cos (psi)
> 	 *
>-	 *	2 <= mlÂ² (1 - in Â· out)
>+	 *	2 <= mlÂ² (1 + in Â· out)
> 	 *
> 	 */
>-	if (2 <= ml * ml * (1 - in_dot_out)) {
>+	if (2 <= ml * ml * (1 + in_dot_out)) {
> 	    double		x1, y1, x2, y2;
> 	    double		mx, my;
> 	    double		dx1, dx2, dy1, dy2;
>@@ -310,6 +316,8 @@ _cairo_stroker_join (cairo_stroker_t *st
> 	    y1 = _cairo_fixed_to_double (inpt->y);
> 	    dx1 = in->usr_vector.x;
> 	    dy1 = in->usr_vector.y;
>+	    if (0.0 == dx1 &&  0.0 == dy1)
>+		goto FALL_BACK_TO_BEVEL;
> 	    cairo_matrix_transform_distance (stroker->ctm, &dx1, &dy1);
> 
> 	    /* outer point of outgoing line face */
>@@ -317,6 +325,8 @@ _cairo_stroker_join (cairo_stroker_t *st
> 	    y2 = _cairo_fixed_to_double (outpt->y);
> 	    dx2 = out->usr_vector.x;
> 	    dy2 = out->usr_vector.y;
>+	    if (0.0 == dx2 && 0.0 == dy2)
>+		goto FALL_BACK_TO_BEVEL;
> 	    cairo_matrix_transform_distance (stroker->ctm, &dx2, &dy2);
> 
> 	    /*
>@@ -333,6 +343,8 @@ _cairo_stroker_join (cairo_stroker_t *st
> 		mx = (my - y1) * dx1 / dy1 + x1;
> 	    else
> 		mx = (my - y2) * dx2 / dy2 + x2;
>+	    if ( ! (fabs (mx) <= RANGE_MAX && fabs (my) <= RANGE_MAX) )
>+		goto FALL_BACK_TO_BEVEL;
> 
> 	    /*
> 	     * Draw the quadrilateral
>@@ -354,7 +366,8 @@ _cairo_stroker_join (cairo_stroker_t *st
> 	}
> 	/* fall through ... */
>     }
>-    case CAIRO_LINE_JOIN_BEVEL: {
>+    case CAIRO_LINE_JOIN_BEVEL:
>+    FALL_BACK_TO_BEVEL: {
> 	cairo_point_t tri[3];
> 	tri[0] = in->point;
> 	tri[1] = *inpt;
>@@ -499,10 +512,47 @@ _cairo_stroker_add_caps (cairo_stroker_t
>     return CAIRO_STATUS_SUCCESS;
> }
> 
>+/* Compute sqrt(x^2 + y^2) with less chance of underflow.  Returns
>+ * zero for NaNs.  May return positive infinity. */
>+static double
>+_cairo_stroker_hypot (double x, double y)
>+{
>+    x = fabs (x);  y = fabs (y);
>+    if (x==0 && y==0) { return 0.0; }
>+    if (x <= y) {
>+	double q = x/y;
>+	return y*sqrt(q*q + 1);
>+    }
>+    else if (x > y) {
>+	double q = y/x;
>+	return x*sqrt(q*q + 1);
>+    }
>+    return 0.0;
>+}
>+
>+/* Normalises a vector to unit length and returns the magnitude of the
>+ * vector before normalisation.  If the vector has NaN components, or
>+ * the computation of its norm overflowed, sets the components to zero
>+ * and returns zero. */
>+static double
>+_cairo_stroker_normalise_vector (double *x, double *y)
>+{
>+    double norm = _cairo_stroker_hypot (*x, *y);
>+    if (0.0 != norm) {
>+	*x /= norm;
>+	*y /= norm;
>+	if (norm <= HUGE_VAL)
>+	    return norm;
>+    }
>+    *x = 0.0;
>+    *y = 0.0;
>+    return 0.0;
>+}
>+
> static void
> _compute_face (cairo_point_t *point, cairo_slope_t *slope, cairo_stroker_t *stroker, cairo_stroke_face_t *face)
> {
>-    double mag, det;
>+    double det;
>     double line_dx, line_dy;
>     double face_dx, face_dy;
>     cairo_point_double_t usr_vector;
>@@ -514,16 +564,8 @@ _compute_face (cairo_point_t *point, cai
>     /* 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;
>-
>+    /* normalize to unit length or the zero vector. */
>+    _cairo_stroker_normalise_vector (&line_dx, &line_dy);
>     usr_vector.x = line_dx;
>     usr_vector.y = line_dy;
> 
>@@ -711,7 +753,7 @@ _cairo_stroker_line_to_dashed (void *clo
> 
>     cairo_matrix_transform_distance (stroker->ctm_inverse, &dx, &dy);
> 
>-    mag = sqrt (dx *dx + dy * dy);
>+    mag = _cairo_stroker_hypot (dx, dy);
>     remain = mag;
>     fd1 = *p1;
>     while (remain) {
>diff --git a/src/cairo-pen.c b/src/cairo-pen.c
>index 87de9a4..5769b4a 100644
>--- a/src/cairo-pen.c
>+++ b/src/cairo-pen.c
>@@ -36,6 +36,14 @@
> 
> #include "cairoint.h"
> 
>+/* Maximum number of pen vertices we can fit in 2G of memory, less
>+ * four to allow for the spline stroker to add them. */
>+#define MAX_PEN_VERTICES (2*(0x3FFFFFFF / sizeof(cairo_pen_vertex_t)) - 4)
>+
>+/* limits on the device space. */
>+#define RANGE_MAX (32767.0 + 65535.0/65536.0)
>+#define RANGE_MIN (-32768.0)
>+
> static int
> _cairo_pen_vertices_needed (double tolerance, double radius, cairo_matrix_t *matrix);
> 
>@@ -45,6 +53,9 @@ _cairo_pen_compute_slopes (cairo_pen_t *
> static cairo_status_t
> _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_clamp_double_to_device_space (double *x);
>+
> cairo_status_t
> _cairo_pen_init_empty (cairo_pen_t *pen)
> {
>@@ -56,6 +67,23 @@ _cairo_pen_init_empty (cairo_pen_t *pen)
>     return CAIRO_STATUS_SUCCESS;
> }
> 
>+static int
>+_cairo_pen_clamp_double_to_device_space (double *x)
>+{
>+    if (RANGE_MIN <= *x && *x <= RANGE_MAX) {
>+	return 1;
>+    }
>+    else if (*x >= RANGE_MAX) {
>+	*x = RANGE_MAX;
>+	return 1;
>+    }
>+    else if (*x < RANGE_MIN) {
>+	*x = RANGE_MIN;
>+	return 1;
>+    }
>+    return 0;
>+}
>+
> cairo_status_t
> _cairo_pen_init (cairo_pen_t	*pen,
> 		 double		 radius,
>@@ -80,7 +108,7 @@ _cairo_pen_init (cairo_pen_t	*pen,
> 						    radius,
> 						    ctm);
> 
>-    pen->vertices = malloc (pen->num_vertices * sizeof (cairo_pen_vertex_t));
>+    pen->vertices = calloc (pen->num_vertices, sizeof (cairo_pen_vertex_t));
>     if (pen->vertices == NULL) {
> 	return CAIRO_STATUS_NO_MEMORY;
>     }
>@@ -97,6 +125,12 @@ _cairo_pen_init (cairo_pen_t	*pen,
> 	double dy = radius * sin (reflect ? -theta : theta);
> 	cairo_pen_vertex_t *v = &pen->vertices[i];
> 	cairo_matrix_transform_distance (ctm, &dx, &dy);
>+
>+	if (! _cairo_pen_clamp_double_to_device_space (&dx))
>+	    continue;
>+	if (! _cairo_pen_clamp_double_to_device_space (&dy))
>+	    continue;
>+
> 	v->point.x = _cairo_fixed_from_double (dx);
> 	v->point.y = _cairo_fixed_from_double (dy);
>     }
>@@ -259,19 +293,29 @@ _cairo_pen_vertices_needed (double	    t
>      * compute number of vertices needed
>      */
>     int	    num_vertices;
>+    double  step = 1 - tolerance / major_axis;
> 
>     /* Where tolerance / M is > 1, we use 4 points */
>-    if (tolerance >= major_axis) {
>-	num_vertices = 4;
>-    } else {
>-	double delta = acos (1 - tolerance / major_axis);
>-	num_vertices = ceil (M_PI / delta);
>-
>-	/* number of vertices must be even */
>-	if (num_vertices % 2)
>-	    num_vertices++;
>+    if (step > 0 && step < 1) {
>+	double delta = acos (step);
>+	double num_vertices_double = ceil (M_PI / delta);
>+
>+	if (num_vertices_double >= 4) {
>+	    if (num_vertices_double < MAX_PEN_VERTICES) {
>+		int num_vertices = num_vertices_double;
>+
>+		/* number of vertices must be even */
>+		if (num_vertices % 2)
>+		    num_vertices++;
>+		return num_vertices;
>+	    }
>+	    /* Infinity or just too big. */
>+	    return MAX_PEN_VERTICES;
>+	}
>     }
>-    return num_vertices;
>+    /* At this point we've either got NaNs somewhere or too few
>+     * vertices. */
>+    return 4;
> }
> 
> static void
>@@ -315,6 +359,8 @@ _cairo_pen_find_active_cw_vertex_index (
> 	    break;
>     }
> 
>+    if (i >= pen->num_vertices)
>+	i = pen->num_vertices/2;
>     *active = i;
> 
>     return CAIRO_STATUS_SUCCESS;
>@@ -343,6 +389,8 @@ _cairo_pen_find_active_ccw_vertex_index 
> 	    break;
>     }
> 
>+    if (i < 0)
>+	i = 0;
>     *active = i;
> 
>     return CAIRO_STATUS_SUCCESS;
>@@ -423,7 +471,7 @@ _cairo_pen_stroke_spline (cairo_pen_t		*
> 
>     /* 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 (pen->num_vertices <= 1 || ! (tolerance > 0))
> 	return CAIRO_STATUS_SUCCESS;
> 
>     _cairo_polygon_init (&polygon);

Actions: View | Splinter Review

Attachments on bug 9276: 8016 | 8093 | 8162 | 8163 | 8164 | 8165 | 8174 | 19489

Use of freedesktop.org services, including Bugzilla, is subject to our Code of Conduct. How we collect and use information is described in our Privacy Policy.