Monday, March 02, 2009

Tiling An Image With FractalFill

Last summer Adam and I looked into how to speed up tiling an image. In particular we were using QImage (Not a QPixmap so X11 isn't involved in this) and tiling an image on it. This is a pretty common operation, especially on the web where many web pages have repeating backgrounds on items. We came up with a few different ways to do this in Qt.*
  • Naive
    loop over the height 
    loop over the width
    fillRect(tile)

  • QPainter::eraseRect
    Set a background brush to be the tiling image.
    call painter.eraseRect(QRect(0, 0, image.width(), image.height());

  • QPainter::fillRect
    call painter.fillRect(QRect(0, 0, image.width(), image.height(), brush(tile));

  • FractalFill
    painter.drawImage(0, 0, tile)
    while we haven't reached the width and height
    copy everything we have done so far to the next location

Benchmarking this we discovered that eraseRect was pretty horrible, but much more surprising was that our FractalFill algorithm that we tossed together was faster then all of Qt's method. (If any graphics ninja's want to suggest a even better algorithm we are all ears) Adam blogged about this some of the Trolls responded saying that Qt's painting had improved in a private branch which would be part of Qt 4.5. Now that Qt 4.5 is almost out I thought I would revisit to see how the painting performance numbers shaped up to be.

Along with the four algorithms there are two more that are added to the benchmark (Colored yellow in the graphs).

  1. A base line, something that we shouldn't be able to be faster then: just calling painter.fillRect(QRect(0, 0, width, height), color);

  2. Using the FractalFill to paint the whole image with a color.

First up is RGB16 with: 1000x5000





Qt 4.5 really has improved upon Qt 4.4. The problems in eraseRect are gone and everything is faster across the board moving to 4.5 and even better when using the raster engine. But more surprising is that FractalFill is still faster then the two QPainter functions.

Same format (RGB16), but in a larger size: 5000x5000





Again it is clear that eraseRect has been fixed and overall painting has been improved slightly.

Moving on to ARGB32: 1000x5000




And in 5000x5000





On this last one with the larger image sizes I started getting larger differences in the tests results. On ARGB32 the performance seemed to be about the same or slightly better.

Overall performance is much better in Qt 4.5 then 4.4. A big congrats to the Trolls for all their hard work. Painting speed has improved across the board decreasing the runtime of all of the functions. FractalFill is still faster then using QPainter's fillRect or eraseRect so for the time being if you looking for something faster then Qt's fill functions for tiling this might be useful for you.

Notes:
I have uploaded the source for the test application to a GitHub repository. I ran the application multiple times on my computer to generate the numbers using the release version of Qt, building from qt-snapshot with 4.3.2 on ubuntu and qt3compat turned off. Now that Qt 4.5 is out it would probably be worth converting to the new benchmark tool. I used Google's graph service to generate the graphs.

* Analyzing each algorithm to determining their Big-O notation is left as an exercise to the reader. ;)

1 comment:

Steve said...

This is pretty cool, I'd be interested to see if filling horizontally first then vertically was even faster, as it might be friendlier to your CPU cache.

Popular Posts