[cairo] intersect_lines in Bentley Ottman implementation

[M Joonas Pihlaja]

On Sun, 1 Jun 2008, Antoine Azar wrote:

> 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. The 64/128 bit functions inside are costly. I was
> wondering why we didn't use floats inside that function?

The old tessellator in cairo <= 1.2 used floats extensively and
was pretty fast on x86 and such.  Apparently on fpuless devices
it sucked pretty hard though, and one of the reasons for
developing the current tessellator was to make cairo less float
heavy.

I think what your findings are showing is that
[...]_insert_if_intersect_below_current_y() and callees need to
be able to chose a code path depending on the hardware and the
input polygon's coordinate range.

Choosing between using the fpu or not is one such choice, but
even on all-integer devices, the current internal 24.8 fixed
point format for coordinates would now allow for a 32/64 bit
integer version to be used more often than before with the
previous 16.16 format.

Cheers,

Joonas