[cairo] Tessellator performance patch

[Rafael Villar Burke]

Behdad Esfahbod wrote:
> 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).
The sign changes are enough for this situation and I've read that it can
be safely done using the trick that's explained later. I was aware of
the overflow problem but don't know well the semanthics of the provided
functions and can't evaluate whether any solution I could write is
correct, so I decided to avoid code I wasn't sure what it does and
expect than maybe some of you, with a better understanding of the
overflow problem, could improve the code.

I've read that the following trick could do too...

int crossp(point x, point y, point z)
{
int crossp_xyz = (y.x - x.x)*(double)(z.y - x.y) - (z.x -
x.x)*(double)(y.y - x.y);

if (crossp > 0.5) return 1;
else if (crossp < -0.5) return -1
else return 0;
}

Regards, and excuse my poor C coding, I'm more a python guy,

Rafael Villar Burke