[cairo] [PATCH 1/2] stroke: Fix large line widths for fallback stroke shaper

[Martin Robinson]

On 03/13/2013 04:57 AM, Chris Wilson wrote:
> Hmm, can you do this as a separate patch. Preferably with another to try
> and fix the current code before replacing it. As you should be able to
> avoid the division to check the intersection against [0,1] so I want a
> closer look at what you consider the bug to be.

Sure, I think that the attached patch fixes the intersection code.
If that's correct we can keep both the slow version (floating point)
and the fast version (fixed point) around.


commit c3042c097e1a508fc56c87781cb72096ee735833
Author: Martin Robinson <mrobinson at igalia.com>
Date:   Wed Mar 13 17:08:23 2013 -0700

    path: Fix a bug in line intersection
    
    Before the intersection code was not taking into account that both
    quotients are required to be in the range (0,1) for the segments to
    intersect or handling the case of negative numerators and denominators.

diff --git a/src/cairo-path-fixed.c b/src/cairo-path-fixed.c
index 10a6515..59db071 100644
--- a/src/cairo-path-fixed.c
+++ b/src/cairo-path-fixed.c
@@ -1308,6 +1308,7 @@ _lines_intersect_or_are_coincident (cairo_point_t a,
 				    cairo_point_t d)
 {
     cairo_int64_t numerator_a, numerator_b, denominator;
+    cairo_bool_t denominator_negative;
 
     denominator = _cairo_int64_sub (_cairo_int32x32_64_mul (d.y - c.y, b.x - a.x),
 				    _cairo_int32x32_64_mul (d.x - c.x, b.y - a.y));
@@ -1327,20 +1328,34 @@ _lines_intersect_or_are_coincident (cairo_point_t a,
 	return FALSE;
     }
 
-    /* If either division would produce a number between 0 and 1, i.e.
-     * the numerator is smaller than the denominator and their signs are
-     * the same, then the lines intersect. */
-    if (_cairo_int64_lt (numerator_a, denominator) &&
-	! (_cairo_int64_negative (numerator_a) ^ _cairo_int64_negative(denominator))) {
-	return TRUE;
-    }
+    /* The lines intersect if both quotients are between 0 and 1 (exclusive). */
 
-    if (_cairo_int64_lt (numerator_b, denominator) &&
-	! (_cairo_int64_negative (numerator_b) ^ _cairo_int64_negative(denominator))) {
-	return TRUE;
+     /* We first test whether either quotient is a negative number. */
+    denominator_negative = _cairo_int64_negative (denominator);
+    if (_cairo_int64_negative (numerator_a) ^ denominator_negative)
+	return FALSE;
+    if (_cairo_int64_negative (numerator_b) ^ denominator_negative)
+	return FALSE;
+
+    /* A zero quotient indicates an "intersection" at an endpoint, which
+     * we aren't considering a true intersection. */
+    if (_cairo_int64_is_zero (numerator_a) || _cairo_int64_is_zero (numerator_b))
+	return FALSE;
+
+    /* If the absolute value of the numerator is larger than or equal to the
+     * denominator the result of the division would be greater than or equal
+     * to one. */
+    if (! denominator_negative) {
+        if (! _cairo_int64_lt (numerator_a, denominator) ||
+	    ! _cairo_int64_lt (numerator_b, denominator))
+	    return FALSE;
+    } else {
+        if (! _cairo_int64_lt (denominator, numerator_a) ||
+	    ! _cairo_int64_lt (denominator, numerator_b))
+	    return FALSE;
     }
 
-    return FALSE;
+    return TRUE;
 }
 
 cairo_bool_t