[cairo] Solving the self-intersecting stroke

[Chris Wilson]

Hi guys,
	I've pushed to git+ssh://annarchy.freedesktop.org/~ickle/cairo a
self-intersecting branch which contains a method to remove overlapping
trapezoids from cairo_traps_t. This solves the self-intersecting problem
at a cost of re-running the general Bentley-Ottmann tessellator over the
entire input.

>From a totally unbiased perspective ;-), cairo's output looks a look
better with far fewer bright pixels around curves and joints. See the
dash-curve images for an example.

One major unresolved issue is what appears to be a loss of precision
when computing the vertices of the trapezoids for constructing the edge
list for the second pass of the tessellator. For a good example look at
the single pixel discrepancy inside the round end-cap around the middle
of the dash-caps-join image. I'm still deciding the cause of the
differences in the antialiasing, particularly if it is indeed correctly
removing overlap of small trapezoid around the edge.

Initial estimates for the performance impact are:

    Speedups
    ========
    image-rgb      paint_similar_rgb_over-256    0.16 0.55% ->   0.12
1.28%:
    1.36x speedup
    ▍
    image-rgb    paint_similar_rgb_source-256    0.16 2.20% ->   0.12
0.88%:
    1.34x speedup
    ▍
    image-rgba  paint_similar_rgba_source-256    0.15 1.25% ->   0.12
1.84%:
    1.31x speedup
    ▎
    image-rgba              subimage_copy-128    0.00 0.37% ->   0.00
0.00%:
    1.14x speedup
    ▏
    image-rgba              subimage_copy-64     0.00 0.35% ->   0.00
0.00%:
    1.14x speedup
    ▏
    image-rgba              subimage_copy-512    0.00 0.12% ->   0.00
0.15%:
    1.14x speedup
    ▏
...

   Slowdowns
    =========
    image-rgb                   world_map-800  154.42 0.11% -> 898.37
0.25%:
    5.81x slowdown
    ████▉
    image-rgba                  world_map-800  154.65 0.09% -> 899.50
0.40%:
    5.80x slowdown
    ████▊
    image-rgb         zrusin_another_fill-415    5.57 1.79% ->  15.40
1.07%:
    2.79x slowdown
    █▊
    image-rgba        zrusin_another_fill-415    5.57 1.54% ->  15.13
0.99%:
    2.78x slowdown
    █▊
    image-rgb       stroke_solid_rgb_over-64     0.39 1.24% ->   0.77
0.25%:
    2.05x slowdown
    █
    image-rgba      stroke_solid_rgb_over-64     0.38 1.32% ->   0.77
0.26%:
    2.05x slowdown
    █
... lots more


So... Joonas, how's your polygon rasteriser?
-- 
Chris Wilson
-------------- next part --------------
A non-text attachment was scrubbed...
Name: dash-caps-joins-image-argb32-out.png
Type: image/png
Size: 5120 bytes
Desc: not available
Url : http://lists.cairographics.org/archives/cairo/attachments/20081001/fcdb35a9/attachment-0004.png 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: dash-curve-image-argb32-diff.png
Type: image/png
Size: 9086 bytes
Desc: not available
Url : http://lists.cairographics.org/archives/cairo/attachments/20081001/fcdb35a9/attachment-0005.png 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: dash-curve-image-argb32-out.png
Type: image/png
Size: 9010 bytes
Desc: not available
Url : http://lists.cairographics.org/archives/cairo/attachments/20081001/fcdb35a9/attachment-0006.png 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: dash-curve-ref.png
Type: image/png
Size: 8835 bytes
Desc: not available
Url : http://lists.cairographics.org/archives/cairo/attachments/20081001/fcdb35a9/attachment-0007.png