[cairo] Correcting the 'wild miter' test for bug 7245
Keith Packard
keithp at keithp.com
Thu Jan 3 18:37:53 PST 2008
Bug 7245 identified a case where cairo drew a dramatically incorrect
miter join. The root cause of these 'wild miters' was two
nearly-parallel segments -- slight imperfections in the positioning of
the ends of the two faces caused the miter position to move far from the
correct position.
Carl's original fix had a minor flaw -- it was using the user-space line
width as if it were measured in device-space units. When the transform
was far from the identity, his miter length computation would be
inaccurate enough to accidentally draw bevel joins on many simple lines.
Attempting to fix this uncovered a more subtle flaw -- the underlying
algorithm assumed a square transformation where the line widths of the
two faces were exactly the same. Under a strongly rectangular transform,
when those line widths varied greatly, the computation wouldn't work at
all.
Here's a proposed patch that replaces the high-level test with a simple
sanity check for the resulting miter point. If the computed miter point
does not lie between the two faces, the miter is replaced with a bevel.
I've just pushed a test which checks this case; this, in combination
with the existing path extents check should suffice to test both
negative and positive versions of the miter test.
commit a86fd00e0e10fa0ad564579a4ebd020375735b72
Author: Keith Packard <keithp at keithp.com>
Date: Thu Jan 3 18:22:16 2008 -0800
Directly check the miter corner to detect wild miters.
The original test for wild miters would only work with a square transform
(and, in fact, the original code required an identity transform). Instead of
fixing that, I replaced it with a more obvious test which makes sure the
miter corner lies between the two faces and not out in space somewhere.
diff --git a/src/cairo-path-stroke.c b/src/cairo-path-stroke.c
index fb12f15..773e9fd 100644
--- a/src/cairo-path-stroke.c
+++ b/src/cairo-path-stroke.c
@@ -205,6 +205,22 @@ _cairo_stroker_face_clockwise (cairo_stroke_face_t *in, cairo_stroke_face_t *out
return _cairo_slope_clockwise (&in_slope, &out_slope);
}
+/**
+ * _cairo_slope_compare_sgn
+ *
+ * Return -1, 0 or 1 depending on the relative slopes of
+ * two lines.
+ */
+static int
+_cairo_slope_compare_sgn (double dx1, double dy1, double dx2, double dy2)
+{
+ double c = (dx1 * dy2 - dx2 * dy1);
+
+ if (c > 0) return 1;
+ if (c < 0) return -1;
+ return 0;
+}
+
static cairo_status_t
_cairo_stroker_join (cairo_stroker_t *stroker, cairo_stroke_face_t *in, cairo_stroke_face_t *out)
{
@@ -272,9 +288,6 @@ _cairo_stroker_join (cairo_stroker_t *stroker, cairo_stroke_face_t *in, cairo_st
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;
- double tolerance_squared = stroker->tolerance * stroker->tolerance;
- double line_width_squared = (stroker->style->line_width *
- stroker->style->line_width);
/* Check the miter limit -- lines meeting at an acute angle
* can generate long miters, the limit converts them to bevel
@@ -332,84 +345,17 @@ _cairo_stroker_join (cairo_stroker_t *stroker, cairo_stroke_face_t *in, cairo_st
*
* 2 <= ml² (1 - in · out)
*
- *
- * That gives us the condition to avoid generating miters that
- * are too large from angles that are too large. But we also
- * need to avoid generating miters when the angle is very small.
- *
- * The miter formed from a tiny angle is also tiny, so the
- * miter limit is not a concern. But with a tiny angle we will
- * be computing the intersection of two lines that are very
- * near parallel. Also, the limits of the fixed-point grid on
- * the input face coordinates mean that the resulting
- * intersection could be wildly wrong. (See the
- * get-path-extents test case for a call to cairo_arc that
- * results in two problematic faces.)
- *
- * Fortunately we can also derive an expression for when using
- * a bevel join instead of a miter will introduce an error no
- * larger than the tolerance. Consider the same join from
- * before but with the miter now chopped off and replaced with
- * a bevel join. The drawing is zoomed in a bit again, the
- * point marked as '*' is the center of the stroke---the point
- * where the two line segments of interest intersect:
- *
- * ----- .
- * ^ ..
- * | . .
- * | . .
- * 1/2 . .
- * miter . . |
- * length . . |
- * | .______. ___v___
- * | | . \ 1/2 bevel
- * v | . \ width
- * ---- * \ -------
- * | \ ^
- *
- *
- * The length of interest here is the vertical length of the
- * miter that is eliminated. It's length can be obtained by
- * starting with 1/2 the miter length and the subtracting off
- * the vertical length that is included by the bevel join,
- * (here termed 1/2 bevel width). To determine this new bevel
- * width, we have a small right triangle shown, the hypotenuse
- * of which has a length of 1/2 the line width, and the small
- * angle at the upper right of the figure is psi/2.
- *
- * So we have:
- *
- * sin (psi/2) = (bevel_width / 2) / (line_width / 2)
- *
- * And we can determine when the miter is required by
- * calculating when the eliminated portion of the miter is
- * greater than the tolerance:
- *
- * (miter_length / 2) - (bevel_width / 2) > tolerance
- *
- * Substituting in the above expressions for miter_length and
- * bevel_width:
- *
- * (line_width/2) / sin (psi/2) - (line_width/2) * sin (psi/2) > tolerance
- * 1 / sin(psi/2) - sin (psi/2) > 2 * tolerance / line_width
- * 1 / sin²(psi/2) -2 + sin²(psi/2) > 4 * (tolerance/line_width)²
- *
- * Use identity: sin²(psi/2) = (1-cos(psi))/2
-
- * 2/(1 - cos(psi)) - 2 + (1-cos(psi))/2 > 4 * (tolerance/line_width)²
- * 4/(1 - cos(psi)) - 4 + (1-cos(psi)) > 8 * (tolerance/line_width)²
- * 4/(1 - cos(psi)) + (1-cos(psi)) > 8 * ((tolerance/line_width)² + 0.5)
*/
- if ((2 <= ml * ml * (1 - in_dot_out)) &&
- ((8 * (tolerance_squared / line_width_squared + 0.5)) <
- 4 / (1 - in_dot_out) + (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;
cairo_point_t outer;
cairo_point_t quad[4];
+ double ix, iy;
+ double fdx1, fdy1, fdx2, fdy2;
+ double mdx, mdy;
/*
* we've got the points already transformed to device
@@ -447,17 +393,46 @@ _cairo_stroker_join (cairo_stroker_t *stroker, cairo_stroke_face_t *in, cairo_st
mx = (my - y2) * dx2 / dy2 + x2;
/*
- * Draw the quadrilateral
+ * When the two outer edges are nearly parallel, slight
+ * perturbations in the position of the outer points of the lines
+ * caused by representing them in fixed point form can cause the
+ * intersection point of the miter to move a large amount. If
+ * that moves the miter intersection from between the two faces,
+ * then draw a bevel instead.
*/
- outer.x = _cairo_fixed_from_double (mx);
- outer.y = _cairo_fixed_from_double (my);
- quad[0] = in->point;
- quad[1] = *inpt;
- quad[2] = outer;
- quad[3] = *outpt;
+ ix = _cairo_fixed_to_double (in->point.x);
+ iy = _cairo_fixed_to_double (in->point.y);
- return _cairo_traps_tessellate_convex_quad (stroker->traps, quad);
+ /* slope of one face */
+ fdx1 = x1 - ix; fdy1 = y1 - iy;
+
+ /* slope of the other face */
+ fdx2 = x2 - ix; fdy2 = y2 - iy;
+
+ /* slope from the intersection to the miter point */
+ mdx = mx - ix; mdy = my - iy;
+
+ /*
+ * Make sure the miter point line lies between the two
+ * faces by comparing the slopes
+ */
+ if (_cairo_slope_compare_sgn (fdx1, fdy1, mdx, mdy) !=
+ _cairo_slope_compare_sgn (fdx2, fdy2, mdx, mdy))
+ {
+ /*
+ * Draw the quadrilateral
+ */
+ outer.x = _cairo_fixed_from_double (mx);
+ outer.y = _cairo_fixed_from_double (my);
+
+ quad[0] = in->point;
+ quad[1] = *inpt;
+ quad[2] = outer;
+ quad[3] = *outpt;
+
+ return _cairo_traps_tessellate_convex_quad (stroker->traps, quad);
+ }
}
/* fall through ... */
}
--
keith.packard at intel.com
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: This is a digitally signed message part
Url : http://lists.cairographics.org/archives/cairo/attachments/20080103/f9cd9d4c/attachment-0001.pgp
More information about the cairo
mailing list