[cairo] intersect_lines in Bentley Ottman implementation
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
> floating point support to the line intersection code in the Bentley
> algorithm. The line intersection was taking up quite some time on my
> 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