[cairo] Greedy trapezoidation

[Chris Wilson]

Looking at the output of the tessellator, I was surprised by the number
of [interior] trapezoids it was producing. Having played about with the
code and started to understand the implementation better, I saw that it
would be quite easy to extend it in order to emit a single trapezoid
covering the entire span, rather than a series of trapezoids between
each edge inside the span. The attached patch is a rough cut (it
unfortunately contains an unrelated change as I'm trying to track down
an unfortunate rounding error when computing the trapezoid edges.)

Performance highlights of the change:
Speedups
========
image-rgba      stroke_solid_rgb_over-64     1.00 0.31% ->   0.48 0.39%:
2.07x speedup
█▏
image-rgba     stroke_solid_rgba_over-64     1.00 0.20% ->   0.49 0.19%:
2.05x speedup
█
image-rgb      stroke_solid_rgba_over-64     1.01 0.20% ->   0.52 3.19%:
2.04x speedup
█
image-rgb    stroke_similar_rgba_over-64     1.02 0.14% ->   0.50 0.21%:
2.02x speedup
█
image-rgb       stroke_image_rgb_over-64     1.02 0.29% ->   0.51 0.25%:
2.02x speedup
█
image-rgba      stroke_image_rgb_over-64     1.02 0.32% ->   0.50 0.15%:
2.01x speedup
█
image-rgb      stroke_image_rgba_over-64     1.02 0.23% ->   0.51 0.42%:
2.01x speedup
█
image-rgba     stroke_image_rgba_over-64     1.02 0.17% ->   0.51 0.11%:
2.01x speedup
█
image-rgba    stroke_similar_rgb_over-64     1.02 0.30% ->   0.51 0.41%:
2.00x speedup
█
image-rgb       stroke_solid_rgb_over-128    1.20 0.18% ->   0.60 0.29%:
2.00x speedup
█
image-rgb     stroke_similar_rgb_over-64     1.02 0.30% ->   0.51 0.32%:
1.99x speedup
█
image-rgba    stroke_solid_rgb_source-64     1.03 0.24% ->   0.52 0.34%:
1.99x speedup
█
...
image-rgba                  world_map-800  875.85 0.59% -> 712.22 0.57%:
1.23x speedup
▎
image-rgb                   world_map-800  879.35 0.62% -> 711.86 0.32%:
1.22x speedup
▎
...

Slowdowns
=========
image-rgb   paint_similar_rgba_source-256    0.13 0.89% ->   0.20 0.25%:
1.52x slowdown
▌
image-rgb      paint_image_rgb_source-256    0.14 0.69% ->   0.20 1.22%:
1.49x slowdown
▌
image-rgb        paint_image_rgb_over-256    0.14 6.41% ->   0.20 2.72%:
1.48x slowdown
▌
image-rgba  paint_similar_rgba_source-256    0.12 0.86% ->   0.15 0.88%:
1.29x slowdown
▎
image-rgb              tessellate-256-100    4.53 0.59% ->   5.40 0.43%:
1.20x slowdown
▎
image-rgba             tessellate-256-100    4.52 0.40% ->   5.44 0.59%:
1.19x slowdown
▎
...not many more...

Which basically says that the extra compares in the tessellator slow it
down by ~20%, but we see about a factor speed increase from pixman for
generating fewer trapezoids covering fewer pixels.

(/me wonders why paint is affected at all - when does it use the
tessellator?)
-- 
Chris Wilson
-------------- next part --------------
A non-text attachment was scrubbed...
Name: greedy-trapezoidation.png
Type: image/png
Size: 29415 bytes
Desc: not available
Url : http://lists.cairographics.org/archives/cairo/attachments/20081003/327ab9a0/attachment-0001.png 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0012-Greedy-trapezoidation.patch
Type: text/x-patch
Size: 0 bytes
Desc: not available
Url : http://lists.cairographics.org/archives/cairo/attachments/20081003/327ab9a0/attachment-0001.bin