[PATCH] Limit miters for small angles
Carl Worth
cworth at cworth.org
Mon Oct 29 17:55:28 PDT 2007
This fixes the current failure get-path-extents, which is a
demonstration of the following bug:
cairo_stroke_extents() gives wrong result for arcs in some cases
https://bugs.freedesktop.org/show_bug.cgi?id=7245
---
src/cairo-path-stroke.c | 76 ++++++++++++++++++++++++++++++++++++++++++++++-
1 files changed, 75 insertions(+), 1 deletions(-)
diff --git a/src/cairo-path-stroke.c b/src/cairo-path-stroke.c
index 5555a6c..ad2db9b 100644
--- a/src/cairo-path-stroke.c
+++ b/src/cairo-path-stroke.c
@@ -272,6 +272,9 @@ _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
@@ -329,8 +332,79 @@ _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)) - 8 + (1-cos(psi)) > 8 * (tolerance/line_width)Â²
+ * 4/(1 - cos(psi)) + (1-cos(psi)) > 8 * ((tolerance/line_width)Â² + 1)
*/
- if (2 <= ml * ml * (1 - in_dot_out)) {
+ if ((2 <= ml * ml * (1 - in_dot_out)) &&
+ ((8 * (tolerance_squared / line_width_squared + 1)) <
+ 4 / (1 - in_dot_out) + (1 - in_dot_out))
+ )
+ {
double x1, y1, x2, y2;
double mx, my;
double dx1, dx2, dy1, dy2;
--
1.5.3.4
--Multipart_Mon_Oct_29_18:00:46_2007-1--
--pgp-sign-Multipart_Mon_Oct_29_18:00:46_2007-1
Content-Type: application/pgp-signature
Content-Transfer-Encoding: 7bit
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
iD8DBQBHJoJF6JDdNq8qSWgRAr9XAJ92k7ETemJIXkXTKNqbMFoxupnlCQCeOo5r
T+xdkB/45IrMq4Rh75lVPK8=
=zJoj
-----END PGP SIGNATURE-----
--pgp-sign-Multipart_Mon_Oct_29_18:00:46_2007-1--
More information about the cairo
mailing list