Threaded Image Tiling

For quite some time now I’ve wanted to do a program that demonstrates Image Tiling using threads. Everyone should be familiar with the results of this technique, it’s used in Google Maps, Google Earth, NASA Worldwind, KDE’s Marble, and the like.

So, to begin I started off looking for example of how this is accomplished in the real world. I found a series of posts about Marble’s Secrets (Part I: Behind the Scenes, Part II: Walking in the shoes of Slartibartfast, Part III: The Earth in a Download). While these didn’t tell me what happens in the gory detail, it gave me enough of an idea that I’m not too terribly lost when wandering around the source code.

The first thing I noticed is that Marble doesn’t use the QGraphics framework, and they opted to do all their own painting (I assume they went to the trouble so that they would be able to do Spherical distortion on their quadtiles). So, I’m not able to get away with easily stealing stuff from Marble.

Track 2: Since I’ve already done one project that would breakup an image into tiles; The real core of the problem becomes threading the loading and unloading of these tiles. So I turned to Trolltech’s Mandelbrot example.

Before we begin, we should remember something about QThreads. Namely, that a QThread instance has affinity for the thread that created it, not to itself. I had to discover this the hard way; but the issue is discussed in slide 42 of Bradly Huges’ talk at Trolltech’s DevDays, 2007. The point of this is that, if you make a subclass of QThread called MyThread, then objects created in MyThread’s constructor actually reside in the thread that instantiated MyThread. I initially expected them to reside in their own thread, to which the MyThread class would provide an interface. So, from a software engineering perspective, the thing to do is create a QThread and instantiate your worker objects, then move those objects to the QThread.

Now, grab a big image to play with, a map of the London underground, which is crisp and has detail that you won’t be able to decipher when zoomed out. (It’s also not geographically correct, hence the need for ‘walklines’)

From an engineering point of view it’s really convenient to be able to map from image coordinates and zoom level to a designated and unique TileId. This allows us to have very fast lookups for images that will be kept in hashtables and caches. To accomplish this we shamelessly swipe the TileId class from Marble/src/lib. A quick check of it’s internals reveals that it will be suitable to our needs.

TileId::TileId( int zoomLevel, int tileX, int tileY )
  : m_zoomLevel( zoomLevel ), m_tileX( tileX ), m_tileY( tileY )
{
}
 
TileId::TileId()
  : m_zoomLevel( 0 ), m_tileX( 0 ), m_tileY( 0 )
{
}
 
bool operator==( TileId const& lhs, TileId const& rhs )
{
    return lhs.m_zoomLevel == rhs.m_zoomLevel
        && lhs.m_tileX == rhs.m_tileX
        && lhs.m_tileY == rhs.m_tileY;
}
 
uint qHash( TileId const& tid )
{
    quint64 tmp = ((quint64)(tid.m_zoomLevel) << 36)
        + ((quint64)(tid.m_tileX) << 18)
        + (quint64)(tid.m_tileY);
    return qHash( tmp );
}

We also want to add some convenience functions for the translation of TileId‘s to actual image sizes. To do this we first add tileSizeX and tileSizeY parameters to the TileId header, and prototypes for the conversion functions.

class TileId
{
    public:
        ...
        QRect rect() const;
        QSize size() const;
        ...
    private:
        ...
        static int tileSizeX;
        static int tileSizeY;
};

And the requisite definitions:

TileId::tileSizeX = 25;
TileId::tileSizeY = 25;
 
QRect TileId::rect() const
{
    return QRect( m_tileX, m_tileY,
                  m_zoomLevel * TileId::tileSizeX + 1,
                  m_zoomLevel * TileId::tileSizeY + 1 );
}
 
QSize TileId::size() const
{
    return QSize( TileId::tileSizeX+1, TileId::tileSizeY+1 );
}

The reason for the +1‘s is that we wish to have one pixel of overlap on all our tiles, at all zoom levels. This slightly improves image rendering within the QGraphics framework. We’ll be treating the rect() as the clipped tile out of the source image, and the size() as the actual size that the tile will be once on screen. Given these formulae, a level 1 tile will mean native resolution, while a level 10 tile will be zoomed way out.

Initially I’d decided that we would load and unload the tiles dynamically onto/from a subclass of QGraphicsScene. After writing some code, and browsing around I realized that this may not be the best plan. The QGraphicsScene is really supposed to be a model for attached QGraphicsView‘s, it’s setup so that you can have more than one view attached to a single model. I browsed around the internal code of QGraphicsView to see where it asks for rendered updates of the QGraphicsScene but wasn’t really able to find it. Anyway, it’s not clear to me that dynamic loading and unloading of QGraphicsPixmapItem is really the right way to go about this, especially so if I don’t have easy access to a list of regions (and zoomlevels) being viewed.

Looking back at the Marble project. They solved this problem by creating their own MarbleMap class that interacts with a custom MarbleModel. The MarbleMap gets Tiles (images), Vectors (political borders, coastlines), and Placemarks from the MarbleModel. It then uses this info to render a picture of the Globe with appropriate image projections by composition of layers. (Actually, MarbleMap::paint() calls MarbleModel::paintGlobe() and then paints the layers on top of that. Naturally they both use the custom GeoPainter class).

Right now I’m somewhat lost on where to head next, so I’ll be punting this topic until next weekend. So far my options seem to be:

1. Make custom rendering widget and associated model, ala Marble
2. Go ahead with the Graphics Framework, but with the caveat that users might not be able to use more than one QGraphicsView on the customized scene.
• custom QGraphicsPixmapItem that knows how to fetch and delete it’s image data in it’s own QThread. The drawback being the spawing of as many threads as there are tiles.
• potentially might have to create custom QGraphicsView that explicitly hand viewing parameters to a custom QGraphicsScene
• the custom QGraphicsScene could manage a set of worker threads, and store the pixmaps in a cache, then the QGraphicsScene is responsible for all the memory management of all items in the scene. At the moment this seem the most attractive path.