[cairo] Survey of polygon rasterization techniques
M Joonas Pihlaja
jpihlaja at cc.helsinki.fi
Wed Aug 27 19:00:28 PDT 2008
Hi,
I've reimplemented the ftgrays_tor10.h rasteriser from David
Turner's rasteriser shootout for use in cairo. You can find the
stand alone version here:
http://www.discontinuity.info/~rowan/glitter-paths-20080828.tar.gz
and the same code incorporated into the ftgrays framework here:
http://www.discontinuity.info/~rowan/raster-comparison-20080828.tar.gz
The 20080828 tarball is based off David's 20070813 one and
additionally includes some random bug fixes as well as the latest
version of Kiia Kallio's scan converter that was posted to this
list. (It rocks btw.)
My version differs from tor_10.h in two main ways:
1. It will use analytical coverage computation to fill in the
coverage lists for an entire scan line at a time if it can
determine that no intersections or new edges are introduced in
that scan line.
2. The subsampling x-resolution is increased to 256 from 17 since
this is what cairo uses internally and it doesn't actually hurt
any to increase it.
As to performance, this puts the rasteriser in the range
1.1x-1.9x as fast as the analytical version (used as the
reference point in the rasteriser-shootout). Compared to
tor15x17, speed ranges from slightly faster to almost twice as
fast.
I have a version of this incorporated into cairo itself, but as
I've just spent all day cleaning it up for this post I think I'll
use the cleaner one instead.
Cheers,
Joonas
8<--------8<-----------8<-----------
Benchmark results compiled with -O2 -g -DUNIX. The
ftgrays_gli<n>_1 ones are the new rasterisers, with <n> being the
y-subsampling resolution. As the size parameter -s grows, more
opportunities for doing full pixel row steps are available, so
the speed approaches the analytical one.
The most relevant comparison points are analytical, tor15x17_10,
and kiia32_9. Note how kiia16_9 is faster than the analytical
one even and really is just all round awesome.
./ftrasters -r 50 -s 25 DejaVu-Sans-Bold-Oblique.ttf
loading 4101 glyphs = 0.043000 s
rasterizer time throughput global relative
================================================================================
with dummy : 0.588 s ( 348724 glyphs/s)
with analytical : 3.713 s ( 55224 glyphs/s) x 1.00 x 1.00
with mono1 : 1.562 s ( 131274 glyphs/s) x 0.42 x 0.31
with tor15x17_9 : 8.426 s ( 24335 glyphs/s) x 2.27 x 2.51
with tor15x17_10 : 7.558 s ( 27130 glyphs/s) x 2.04 x 2.23
with tor16x16_9 : 8.105 s ( 25299 glyphs/s) x 2.18 x 2.41
with tor16x16_10 : 7.420 s ( 27634 glyphs/s) x 2.00 x 2.19
with tor8x8_9 : 5.416 s ( 37860 glyphs/s) x 1.46 x 1.54
with tor8x8_10 : 5.008 s ( 40944 glyphs/s) x 1.35 x 1.41
with kiia32_7 : 5.929 s ( 34584 glyphs/s) x 1.60 x 1.71
with kiia32_8 : 5.053 s ( 40579 glyphs/s) x 1.36 x 1.43
with kiia32_9 : 4.017 s ( 51045 glyphs/s) x 1.08 x 1.10
with kiia16_7 : 4.172 s ( 49149 glyphs/s) x 1.12 x 1.15
with kiia16_8 : 3.672 s ( 55841 glyphs/s) x 0.99 x 0.99
with kiia16_9 : 3.035 s ( 67561 glyphs/s) x 0.82 x 0.78
with kiia8_7 : 3.195 s ( 64178 glyphs/s) x 0.86 x 0.83
with kiia8_8 : 2.951 s ( 69484 glyphs/s) x 0.79 x 0.76
with kiia8_9 : 2.592 s ( 79108 glyphs/s) x 0.70 x 0.64
with gli15_1 : 6.809 s ( 30114 glyphs/s) x 1.83 x 1.99
with gli16_1 : 6.949 s ( 29507 glyphs/s) x 1.87 x 2.04
with gli8_1 : 4.902 s ( 41829 glyphs/s) x 1.32 x 1.38
./ftrasters -r 50 -s 100 DejaVu-Sans-Bold-Oblique.ttf
loading 4101 glyphs = 0.037000 s
rasterizer time throughput global relative
================================================================================
with dummy : 0.713 s ( 287587 glyphs/s)
with analytical : 11.833 s ( 17328 glyphs/s) x 1.00 x 1.00
with mono1 : 3.924 s ( 52255 glyphs/s) x 0.33 x 0.29
with tor15x17_9 : 29.125 s ( 7040 glyphs/s) x 2.46 x 2.56
with tor15x17_10 : 24.903 s ( 8233 glyphs/s) x 2.10 x 2.18
with tor16x16_9 : 27.857 s ( 7360 glyphs/s) x 2.35 x 2.44
with tor16x16_10 : 24.322 s ( 8430 glyphs/s) x 2.06 x 2.12
with tor8x8_9 : 17.415 s ( 11774 glyphs/s) x 1.47 x 1.50
with tor8x8_10 : 14.946 s ( 13719 glyphs/s) x 1.26 x 1.28
with kiia32_7 : 17.555 s ( 11680 glyphs/s) x 1.48 x 1.51
with kiia32_8 : 14.720 s ( 13930 glyphs/s) x 1.24 x 1.26
with kiia32_9 : 11.228 s ( 18262 glyphs/s) x 0.95 x 0.95
with kiia16_7 : 12.098 s ( 16949 glyphs/s) x 1.02 x 1.02
with kiia16_8 : 10.559 s ( 19419 glyphs/s) x 0.89 x 0.89
with kiia16_9 : 7.940 s ( 25824 glyphs/s) x 0.67 x 0.65
with kiia8_7 : 9.127 s ( 22466 glyphs/s) x 0.77 x 0.76
with kiia8_8 : 8.449 s ( 24269 glyphs/s) x 0.71 x 0.70
with kiia8_9 : 6.601 s ( 31063 glyphs/s) x 0.56 x 0.53
with gli15_1 : 18.494 s ( 11087 glyphs/s) x 1.56 x 1.60
with gli16_1 : 19.064 s ( 10755 glyphs/s) x 1.61 x 1.65
with gli8_1 : 13.087 s ( 15668 glyphs/s) x 1.11 x 1.11
./ftrasters -r 50 -s 400 DejaVu-Sans-Bold-Oblique.ttf
loading 4101 glyphs = 0.037000 s
rasterizer time throughput global relative
================================================================================
with dummy : 3.408 s ( 60167 glyphs/s)
with analytical : 50.795 s ( 4036 glyphs/s) x 1.00 x 1.00
with mono1 : 15.855 s ( 12932 glyphs/s) x 0.31 x 0.26
with tor15x17_9 : 115.468 s ( 1775 glyphs/s) x 2.27 x 2.36
with tor15x17_10 : 95.926 s ( 2137 glyphs/s) x 1.89 x 1.95
with tor16x16_9 : 110.543 s ( 1854 glyphs/s) x 2.18 x 2.26
with tor16x16_10 : 94.038 s ( 2180 glyphs/s) x 1.85 x 1.91
with tor8x8_9 : 68.363 s ( 2999 glyphs/s) x 1.35 x 1.37
with tor8x8_10 : 56.595 s ( 3623 glyphs/s) x 1.11 x 1.12
with kiia32_7 : 79.076 s ( 2593 glyphs/s) x 1.56 x 1.60
with kiia32_8 : 73.019 s ( 2808 glyphs/s) x 1.44 x 1.47
with kiia32_9 : 54.623 s ( 3753 glyphs/s) x 1.08 x 1.08
with kiia16_7 : 60.393 s ( 3395 glyphs/s) x 1.19 x 1.20
with kiia16_8 : 56.768 s ( 3612 glyphs/s) x 1.12 x 1.13
with kiia16_9 : 40.590 s ( 5051 glyphs/s) x 0.80 x 0.78
with kiia8_7 : 49.901 s ( 4109 glyphs/s) x 0.98 x 0.98
with kiia8_8 : 48.582 s ( 4220 glyphs/s) x 0.96 x 0.95
with kiia8_9 : 36.093 s ( 5681 glyphs/s) x 0.71 x 0.69
with gli15_1 : 55.919 s ( 3666 glyphs/s) x 1.10 x 1.11
with gli16_1 : 57.361 s ( 3574 glyphs/s) x 1.13 x 1.14
with gli8_1 : 42.652 s ( 4807 glyphs/s) x 0.84 x 0.83
More information about the cairo
mailing list