[cairo] infinite loop when CAIRO_FIXED_FRAC_BITS is 8

[Behdad Esfahbod]

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