I’ve been working on a new rasterizer to replace the Freetype rasterizer for aliased painting in the raster paint engine, which is used on Windows and when rendering to a QImage. The new rasterizer is scheduled to be part of Qt 4.4, and is already available in the snapshots.
The performance of rasterizing various paths with QRasterizer compared to the Freetype rasterizer can bee seen in the following figure:
And the same results in table form:
| Freetype | QRasterizer | Improvement | |
| A - Plain rectangle | 25773.2 | 37174.72 | 1.44 |
| B - Rotated rectangle 1 | 23201.86 | 27247.96 | 1.17 |
| C - Rotated rectangle 2 | 23041.47 | 28735.63 | 1.25 |
| D - Rect dash stroke | 276.24 | 1754.39 | 6.35 |
| E - Rect dot stroke | 87.95 | 826.45 | 9.4 |
| F - Ellipse | 3558.72 | 6944.44 | 1.95 |
| G - Ellipse dash stroke | 141.64 | 1282.05 | 9.05 |
| H - Ellipse dot stroke | 83.54 | 800 | 9.58 |
| I - Short text path | 14285.71 | 17241.38 | 1.21 |
| J - Long text path | 1683.5 | 1930.5 | 1.15 |
| K - Random path size 5 | 24523.81 | 30294.12 | 1.24 |
| L - Random path size 50 | 778.15 | 1098.13 | 1.41 |
| M - Random rects (5) | 25750 | 39615.38 | 1.54 |
| N - Random rects (50) | 324.81 | 753.21 | 2.32 |
Note: the numbers are for generating spans only, not filling. The benchmark used to measure these results can be downloaded from here: rasterizerbench.tar.gz
These numbers are already quite impressive, but where the new rasterizer really shines is for rasterizing complex paths with a lot of elements and potentially many self intersections. I’ve created an example which generates a path representing the Dragon Curve fractal. A screenshot from the application is shown below:
At the highest detail setting the path (which is a round-cap/round-join stroke of the dragon curve) contains 507913 path elements. In this specific case the frame rate is approximately 36 times higher with the new rasterizer (filling included) 
The example is available for download from here: dragoncurve.tar.gz
Note: the new rasterizer only affects primitive rendering (polygons, paths, ellipses, strokes, etc), and does not replace the Freetype rasterizer for plain font rendering.
7 Responses to “Rasterizing dragons”
First… COOL!
Now, why will this only be available under Windows/QImage or when rendering some path? If this is so much faster, then why not enable it for X11/Qtopia/plain font rendering?
Also, how does your rasterizer perform when the QPainter has a large (or small) scale transform set? ie, when drawing large or small text does this rasterizer perform well? We’ve noticed signifcant performance problems when painting text with a QPainter scale transform set…
manyoso, In regards to why the rasterizer is only used for primitives and not fonts: “The Black Raster”, as we called it, is a fork of the ftraster.c file provided in FreeType, as described here: http://doc.trolltech.com/4.3/3rdparty.html#freetype-2. There are quite some differences as to how to rasterize a glyph, like the letter X, compared to how to rasterize a primitive, like the dragon path above. Both the old “black raster” and the new QRaster that Samuel wrote follow a different set of rasterization rules than used for fonts, so in short… They are not compatible 
How about improving existing Freetype rasterizer instead of writing new one?
Thanks to Gunnar for clearing things up
I see I forgot to mention that the raster paint engine is the default on Qtopia as well, sorry about that…
manyoso: To use this on X11 we would have to render the path to a temporary image which would then have to be transfered to the X server, so that would probably kill any performance advantage. For very complex paths it might be a win, but it’s not worth it in general.
x: As Gunnar said, the Freetype rasterizer is specialized and optimized for rendering glyphs, whereas this one is meant for vector graphics.
Oh wait, I see. This rasterizer doesn’t touch font rendering at all. No matter if it is rendered on a path or not.
When you talk about FreeType and rasterizers I immediately think this is font related.
Would it be possible to use this new rasterizer on OSX to speed up drawing primitives there as well? Any painting speedups are very much appreciated (I’m doing a lot of complicated painting in some of my custom widgets) although the biggest slowdown I see is lots of calls to drawText. If only drawText, especially on OSX, was not so expensive. 
Will,
Drawing text is expensive, we are using ATSUI and Core Graphics, so we are already about as fast as we can get with the currently available OS X technology. Perhaps things will get better in the next OS X release, but we that’s something we’ll have to examine in time. We are always looking in new ways of speeding up text rendering, but it’s a difficult process. In the meantime, one of the things that makes a big difference is to ensure that you only update the text that must actually be updated and not do more work than is necessary in computing your text layout.