[cairo] self-intersecting: slow but beautiful

[Chris Wilson]

Guys,
	I've a conundrum that needs to be discussed...

A long standing bug in Cairo is the treatment of self-intersecting
strokes, whereby the accumulation of overlapping edges causes incorrect
anti-aliasing, for example test/self-intersecting and the twin waterfall
demo.

The method I've looked at in order to remove these artefacts is to run
the trapezoids generated by the stroker through the general
Bentley-Ottmann tessellator so that we remove all overlapping
trapezoids. This has the desired effect (the output is even more
beautiful ;-), but at tremendous cost - as we are feeding in
intersecting edges into the tessellator.

On the flip side, the rework of the tessellator allows it to preserve
the original line equations which enables it to not only clip the edges
to the desired limits, but also to easily identify co-linear edges and
perform greedy trapezoidation. This improves the performance of both
large geometries and overlapping geometries (such as the strokes).

The self-intersecting branch is available for inspection from
annarchy:~ickle/cairo
[http://gitweb.freedesktop.org/?p=users/ickle/cairo;a=shortlog;h=self-intersecting]

The highlight is commit dc32ad71b0d82d61bd956a4d3eb88539d310bfc3, and in
particular:

Speedups
========

image-rgb   paint_similar_rgba_source-256    0.13 0.85% ->   0.11 0.63%:
1.21x speedup
▎

image-rgb     paint_image_rgba_source-256    0.13 0.82% ->   0.11 0.49%:
1.20x speedup
▎

image-rgb               subimage_copy-512    0.00 0.63% ->   0.00 0.07%:
1.11x speedup
▏

...


Slowdowns
=========

image-rgba                  world_map-800  147.71 0.09% -> 986.54 0.23%:
6.68x slowdown
█████▋

image-rgb                   world_map-800  152.23 0.07% -> 992.26 0.25%:
6.51x slowdown
█████▌

image-rgba      stroke_solid_rgb_over-64     0.34 0.29% ->   0.46 0.33%:
1.34x slowdown
▍

image-rgb       stroke_solid_rgb_over-64     0.35 0.48% ->   0.46 0.39%:
1.34x slowdown
▍

image-rgb      stroke_solid_rgba_over-64     0.35 0.35% ->   0.47 0.39%:
1.33x slowdown
▍

image-rgba     stroke_solid_rgba_over-64     0.35 0.37% ->   0.47 0.30%:
1.33x slowdown
▍

image-rgba      stroke_solid_rgb_over-256    0.87 0.38% ->   1.16 0.63%:
1.32x slowdown
▍

image-rgba    stroke_similar_rgb_over-64     0.37 0.20% ->   0.49 0.31%:
1.32x slowdown
▍

image-rgba   stroke_similar_rgba_over-64     0.37 0.18% ->   0.48 0.36%:
1.31x slowdown
▍

image-rgba      stroke_image_rgb_over-64     0.37 0.39% ->   0.48 0.24%:
1.31x slowdown
▍

image-rgba     stroke_image_rgba_over-64     0.37 0.16% ->   0.48 0.31%:
1.31x slowdown
▎

image-rgb    stroke_similar_rgba_over-64     0.37 0.22% ->   0.48 0.28%:
1.31x slowdown
▎

image-rgb       stroke_solid_rgb_over-256    0.89 0.46% ->   1.16 0.48%:
1.31x slowdown
▎

image-rgba    stroke_solid_rgb_source-64     0.38 0.23% ->   0.50 0.37%:
1.31x slowdown
▎

image-rgb       stroke_image_rgb_over-64     0.37 0.31% ->   0.48 0.30%:
1.31x slowdown
▎

image-rgba stroke_similar_rgba_source-64     0.38 0.25% ->   0.50 0.30%:
1.31x slowdown
▎

...many more...

Now if only we had a method for direct rasterisation of strokes...
-- 
Chris