[cairo] infinite loop when CAIRO_FIXED_FRAC_BITS is 8
Behdad Esfahbod
behdad at behdad.org
Thu Feb 14 15:27:20 PST 2008
On Thu, 2008-02-14 at 15:15 -0800, Carl Worth wrote:
> On Thu, 14 Feb 2008 16:29:02 -0500, Behdad Esfahbod wrote:
> > On Thu, 2008-02-14 at 12:34 -0800, Carl Worth wrote:
> > + /* 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.
>
> Quite likely. Thanks for the review.
>
> > This breaks the compare function in that it will
> > both return a<b and b<a for some input slopes a and b.
>
> Right. In my defense, I was aware that this was giving special
> attention to the order in which the arguments were presented to the
> function, and I did _some_ analysis that we were calling it
> consistently, (though my analysis was probably too shallow).
>
> And for what it's worth, we *don't* call qsort with this comparison
> function.
We do, by way of _cairo_hull_vertex_compare(). I checked ;).
> > 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;
>
> Thanks, I like that. And it does seem to guarantee a total order.
>
> Now, do you also have a good proposal for how to document the
> behavior? The best I've got so far is:
>
> To resolve ambiguous cases, (where the angular difference is
> exactly pi), imagine subtracting an infinitesimally small
> amount from the dy value of each slope, (or if the dx value
> for both is 0, then add an infinitesimally small value to the
> dx value of each). The function returns a correct comparison
> for those effective slopes.
>
> I *think* that's right, but it's quite awkward, (either subtracting or
> adding), and it's not all that intuitive to start with that and figure
> out what happens.
>
> Other ideas?
I'd go with something like: "To break ties when comparing slope vectors
with exactly pi angular difference, the vector with a positive dx (or
positive dy if dx's are zero) is considered ..."
> -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