[cairo] intersect_lines in Bentley Ottman implementation

Antoine Azar cairo at antoineazar.com
Sat May 31 21:56:30 PDT 2008


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.
 
Cheers,
Antoine
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.cairographics.org/archives/cairo/attachments/20080601/e2ea5e22/attachment.htm 


More information about the cairo mailing list