[cairo] intersect_lines in Bentley Ottman implementation

Carl Worth cworth at cworth.org
Wed Jul 30 14:12:08 PDT 2008

On Wed, 2008-07-30 at 05:22 -0400, Antoine Azar wrote:
> I neglected this patch in the last few weeks but here it is: I've
> added
> floating point support to the line intersection code in the Bentley
> Ottman
> algorithm. The line intersection was taking up quite some time on my
> Wintel
> machine, mostly due to costly 64 bit and 128 bit operations.

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

The idea behind that fixed-point arithmetic is to guarantee correctness,
(intersection calculations have a tendency to create some nice numeric
explosions as lines become near parallel, etc.).

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.


More information about the cairo mailing list