[cairo] intersect_lines in Bentley Ottman implementation

[Antoine Azar]

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.
I've added an ifdef that checks for the OPTIMIZE_FOR_FPU flag. You can
specify it in the makefile to take advantage of the floating point code. Let
me know if that's fine for everyone or if we should use the floating point
code by default and rather have a OPTIMIZE_FOR_NO_FPU flag.

I've added Soeren's suggestion to check the bounding box of the edges before
going into the line intersection code. I also tried checking for shared
points, but the added comparisons required actually slowed down the code a
bit instead of speeding it up. This might be test-case dependant, I've
relied entirely on the stroke benchmark.

The stroke performance benchmark shows an average gain of 11%, with some
benches shaving up to 20% off the median time. The stroking tests still
pass.
You can view the bench result here:
http://www.2xmlabs.com/clients/mozilla/strokingBench.htm

Comments welcome.
Thanks,
Antoine


> -----Original Message-----
> From: sandmann at daimi.au.dk [mailto:sandmann at daimi.au.dk] 
> Sent: Monday, June 02, 2008 5:46 PM
> To: Antoine Azar
> Cc: cairo at cairographics.org
> Subject: Re: [cairo] intersect_lines in Bentley Ottman implementation
> 
> "Antoine Azar" <cairo at antoineazar.com> writes:
> 
> > 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.
> 
> I noticed that as well, but there is actually a pretty simple 
> patch that gave decent speedups for my test case.
> 
> The idea is simply to bail immediately if the bounding boxes 
> of the two line segments don't intersect. This is very 
> commonly the case because self-intersecting polygons are so rare.
> 
> The intersect_lines() function computes whether the two line 
> segments are 'parallel', 'intersect', or 'don't intersect', 
> but nothing seems to make use of the difference between 
> 'parallel' and 'don't intersect', so we can simply return 
> 'don't intersect' when the bounding boxes are disjoing. If 
> this patch is accepted, it may be worthwhile replacing 
> CAIRO_BO_STATUS_PARALLEL with CAIRO_BO_STATUS_NO_INTERSECTION 
> altogether.
> 
> I wrote the patch a while back, then promptly forgot about 
> it, but here it is (also attached):
> 
>     http://www.daimi.au.dk/~sandmann/fast-path-no-intersection.patch
> 
> I remember measuring some good speedups for my test case, but 
> I don't have the data anymore. I also seem to remember that 
> essentially all the remaining intersections were cases where 
> the two lines had a point in common, so that's another 
> straightforward fast path that could be done.
> 
> 
> Soren
> 
> 
> 
> 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0006-Added-support-for-float-operations-along-int64-128.patch
Type: application/octet-stream
Size: 0 bytes
Desc: not available
Url : http://lists.cairographics.org/archives/cairo/attachments/20080730/a4de47e6/attachment.obj