[cairo] intersect_lines in Bentley Ottman implementation

Antoine Azar cairo at antoineazar.com
Mon Aug 4 00:14:13 PDT 2008

Hi Carl, 

> We didn't write those in fixed-point for performance reasons, 
> (and especially not to cater to machines without hardware 
> floating-point).

Ah, that was my impression from previous discussion on the list about this

> So a switch to floating-point here really needs to be accompanied by
careful analysis of the input data and the 
> precision provided by the floating-point operations. Otherwise it's just
not interesting.

Two questions:
-Do we have tests for polygon intersection that demonstrate issues in
floating-point precision (either float or double) and the need for
-Would optimizations in this code benefit in a significant way many
applications? I see the Bentley-Ottman tesselation is not only used by the
stroker, but also by many clipping and filling functions.

I'm basically trying to determine if it's worth it to put much effort into
this optimization, or just to stick to Soren's idea of checking the path's
bounding box (included in my patch). The bounding box optim alone gives an
average speed boost of 7% on all the stroking tests:

The floating point optim gave an average of 11%. This is of course dependant
on how many edge intersections are present in the test (about none in the
performance suite). We would see a much larger performance gain if there
were more edge intersections to compute, but as Soeren pointed out, those
are probably rare cases.


More information about the cairo mailing list