[cairo] intersect_lines in Bentley Ottman implementation

[Peter Clifton]

On Sun, 2008-06-01 at 00:56 -0400, Antoine Azar wrote:
> I've profiled a couple of performance tests, and the stroking
> benchmarks reveal the intersect_lines function (part of the Bentley
> Ottman algo) takes up quite some time. The 64/128 bit functions inside
> are costly. I was wondering why we didn't use floats inside
> that function? I tried re-writing it with floats, and the function
> runs 8x faster and the tests still seem to pass. The range of floats
> should be quite enough to handle overflow cases. We might lose a tiny
> bit in the precision of the computation but it's all rounded to the
> nearest integer anyways.
>  
> Comments welcome, if there's no potential problem with that approach
> I'll clean up the code and send a patch.

I'd be interested to see that (no need to clean it up), but in my
profiles, it is mostly:

(below) pixman_rasterize_trapezoid :
pixman_rasterize_edges
pixman_edge_init (and below)

which are hot.

I notice those are using 64 bit fixed point internally. 

I'm not sure the sysprof output is as helpful / detailed as it could be,
but oprofile makes my head hurt.

Regards,
> 
-- 
Peter Clifton

Electrical Engineering Division,
Engineering Department,
University of Cambridge,
9, JJ Thomson Avenue,
Cambridge
CB3 0FA

Tel: +44 (0)7729 980173 - (No signal in the lab!)