[cairo] Derivation of the mitre limit

[Chris Wilson]

Chris Wilson (chris at chris-wilson.co.uk) said: 
> Chris Wilson (chris at chris-wilson.co.uk) said: 
> > I was reviewing https://bugs.freedesktop.org/show_bug.cgi?id=7245,
> > cairo_stroke_extents() gives wrong result for arcs in some cases, when I
> > left scratching my head over the detailed comment that derives the
> > condition for the mitre limit (cairo-path-stroke.c, line 276).
> 
> Well I pulled out the old trusty pen and paper to derive the miter
> condition and agree with 1/sin(psi/2) <= ml - it's clear as soon as you
> draw a diagram, so I'll try to remember to add one to the docs.
> 
> However, there is still a problem in there somewhere so I wrote a
> little test case to explore a few line joints. The issue appears to be
> an incorrect sign in the dot product between the intersection of two
> rotated curves.

Progress, of sorts. Both the original bug and my test case suffer from
numerical instability. In my test case, the mitre limit is very close to
90° and breaks due to rounding errors as the vectors are rotated,
converted to fixed point, converted back and unrotated before being used
to generate the faces for the mitre limit.

The original bug is a little more worrisome as the cairo_arc() generates
a pair of curves whose endpoints are nearly parallel but very slightly
displaced. As the lines are nearly parallel, they pass the mitre limit
check when in fact they generate an ugly mitre - which although added to
the traps is not drawn, but still affects the extents.

My current band-aid looks like:
diff --git a/src/cairo-path-stroke.c b/src/cairo-path-stroke.c
index d8d989b..88f9f41 100644
--- a/src/cairo-path-stroke.c
+++ b/src/cairo-path-stroke.c
@@ -205,17 +210,28 @@ _cairo_stroker_face_clockwise (cairo_stroke_face_t *in, cairo_stroke_face_t *out
     return _cairo_slope_clockwise (&in_slope, &out_slope);
 }
 
+static double
+_PointDistanceSquaredToPoint (const cairo_point_t *a, const cairo_point_t *b)
+{
+    double dx = _cairo_fixed_to_double (b->x - a->x);
+    double dy = _cairo_fixed_to_double (b->y - a->y);
+
+    return dx*dx + dy*dy;
+}
 static cairo_status_t
 _cairo_stroker_join (cairo_stroker_t *stroker, cairo_stroke_face_t *in, cairo_stroke_face_t *out)
 {
     int			clockwise = _cairo_stroker_face_clockwise (out, in);
     cairo_point_t	*inpt, *outpt;
     cairo_status_t status;
+    double tolerance_sqr = stroker->tolerance * stroker->tolerance;
 
-    if (in->cw.x == out->cw.x
+    if ((in->cw.x == out->cw.x
 	&& in->cw.y == out->cw.y
 	&& in->ccw.x == out->ccw.x
 	&& in->ccw.y == out->ccw.y)
+	|| (_PointDistanceSquaredToPoint (&in->cw, &out->cw) < tolerance_sqr &&
+	    _PointDistanceSquaredToPoint (&in->ccw, &out->ccw) < tolerance_sqr))
     {
 	return CAIRO_STATUS_SUCCESS;
     }
--
Chris Wilson