[cairo] infinite loop when CAIRO_FIXED_FRAC_BITS is 8
Behdad Esfahbod
behdad at behdad.org
Thu Feb 14 13:29:02 PST 2008
On Thu, 2008-02-14 at 12:34 -0800, Carl Worth wrote:
> On Wed, 13 Feb 2008 20:20:50 -0800, Carl Worth wrote:
> > Anyway, I think I'll have a fix soon.
>
> Here's what I've got. This fixes the infinite loop, adds a spline to
> the degenerate-pen test case, (which was triggering the infinite loop
> before the fix here), and then switches from 16.16 to 24.8 fixed-point
> format.
>
> I'd appreciate any review of the change I made to
> _cairo_slope_compare. This is a fairly core part of cairo's
> computational geometric machinery so it's important to get the details
> right.
Sure thing.
@@ -78,6 +80,22 @@ _cairo_slope_compare (cairo_slope_t *a, cairo_slope_t *b)
if (b->dx == 0 && b->dy ==0)
return -1;
+ /* Finally, we're looking at two vectors that are either equal or
+ * that differ by exactly pi. We can identify the "differ by pi"
+ * case by looking for a change in sign in either dx or dy between
+ * a and b.
+ *
+ * And in these cases, we eliminate the ambiguity by reducing the angle
+ * of b by an infinitesimally small amount, (that is, 'a' will
+ * always be considered less than 'b').
+ */
+ if (((a->dx > 0) != (b->dx > 0)) ||
+ ((a->dy > 0) != (b->dy > 0)))
+ {
+ return -1;
+ }
+
+ /* Finally, for identical slopes, we obviously return 0. */
return 0;
}
I think this is wrong. This breaks the compare function in that it will
both return a<b and b<a for some input slopes a and b. That is, it
doesn't represent a total order anymore, and depending on qsort()'s
implementation, this may cause an infinite look in itself.
I suggest instead of "return -1", you do something like:
if (a->dx > 0 || (a->dx == 0 && a->dy > 0))
return +1;
else
return -1;
> -Carl
--
behdad
http://behdad.org/
"Those who would give up Essential Liberty to purchase a little
Temporary Safety, deserve neither Liberty nor Safety."
-- Benjamin Franklin, 1759
More information about the cairo
mailing list