[cairo] Tessellator performance patch

[Behdad Esfahbod]

On Sun, 2006-12-03 at 23:13 -0500, M Joonas Pihlaja wrote:
> Hi Rafael,
> 
> On Mon, 4 Dec 2006, Rafael Villar Burke wrote:
> 
> > Subject: [PATCH] Additional fast path tests to avoid intersection computation
> [snip]
> > + cairo_bo_point32_t a = edge1->top;
> > + cairo_bo_point32_t b = edge1->bottom;
> > + cairo_bo_point32_t c = edge2->top;
> > + cairo_bo_point32_t d = edge2->bottom;
> > +
> > + int crossp_abc = (b.x - a.x)*(c.y - a.y) - (c.x - a.x)*(b.y - a.y);
> > + int crossp_abd = (b.x - a.x)*(d.y - a.y) - (d.x - a.x)*(b.y - a.y);
> > + int crossp_cda = (d.x - c.x)*(a.y - c.y) - (a.x - c.x)*(d.y - c.y);
> > + int crossp_cdb = (d.x - c.x)*(b.y - c.y) - (b.x - c.x)*(d.y - c.y);
> 
> These multiplications are liable to overflow 32 bits and throw 
> off the later sign checks.  Could you replace them with a 64 bit 
> version and rerun your tests?

I'm surprised that a check with so many multiplications still bits the
intersection code with such a huge improvement.  May be possible to live
with the 32-bit math and detect sign changes and do a conservative
heuristic on the result (like, if any overflows happen, return that an
intersection is possible).


> Cheers,
> 
> Joonas
> _______________________________________________
> cairo mailing list
> cairo at cairographics.org
> http://cairographics.org/cgi-bin/mailman/listinfo/cairo
-- 
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