[cairo] intersect_lines in Bentley Ottman implementation

[Carl Worth]

On Mon, 2008-08-04 at 03:14 -0400, Antoine Azar wrote:
> > 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
> fixed-point?

No.

When I wrote that code I went through the various multiplications and
divisions carefully to ensure there was sufficient range in the
fixed-point arithmetic to accurately capture results. But I did not
generate any test cases to exercise these issues.

I'd like to see similar analysis provided for any floating-point
implementation, (and if backed up by some test cases, that would be
great too). But the analyis is the thing that matters more to me.

> -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.

Tessellation is primarily used by the filler, and not the stroker. And
yes, I think the mozilla folks could tell you that tessellation
performance does impact overall performance quite a bit.

Note also that we have Joonas currently doing a Summer-of-Code project
that will do rasterization directly from polygons, which will allow
paths to be filled *without* tessellation at all. So that's something
else to keep in mind.

-Carl