Introduction

In this article I'll give a detailed explanation on how the tiled rendering in Okular works. The text is mostly focused on Okular developers.

Tiles manager

The use of tiles is made through a tiles manager which has functions to store, retrieve and ask for necessary tiles. Each page needs an instance of TilesManager for each observer.

Throughout this text I'll explain more about TilesManager and how it works.

new TilesManager();

As pointed out before, each page has it's own tiles manager. If the page doesn't have an instance of it, the pixmap handling acts like before.

A tiles manager will only exist when the use of tiles is necessary. That's when the page is bigger than an arbitrary value (currently page.width * page.height > 8000000).

Tile

Initially the tiles manager divides the page in 16 equal sized tiles. The width of each is 1/4 of the page width and its height is 1/4 of the page height. Note that the page's size is passed right in the constructor.

The initial tiles are stored in an array of Tile objects.

Take a look at Tile definition.

Apart from that a Tile can also have children. That's when 1/16 of the page is still a big size to handle, so the tile is split in 4. Knowing that we can tell that the tiles manager is a collection of 16 trees.

Note: the split happens only to the region intersecting the current viewport. We don't need to split every tile in the tiles manager for that.

Workflow

In this section I'll explain how the tiles are requested, rendered and painted to the page.

When a page change occurs in the UI (the user scrolled the page, for example) a call to PageView::slotRequestVisiblePixmaps() is made. If the page is not using tiles, it only checks if the current page is in cache and make a new request if not.

The tiled approach is obviously different. The page may exist but only part of it. The job of this function is to check if the visible region already has all pixmaps (tiles) to paint the scene. If not, it creates a new request for the region not yet in cache.

The method Page::hasPixmap() checks if the region (or page) is in cache. There's an additional parameter for tiled rendering which is the current viewport.

Actually is a little bit more than the viewport. We pretend that the visible region is a little bit bigger so we can request nearby tiles in advance.

Going deeper

In Page::hasPixmap() we check if the page has a TilesManager. Then we call TilesManager::hasPixmap() to know whether the given region is updated.

setWidth, setHeight?

The tiles manager needs to know the page's size, and when it changes all pixmaps are marked as dirty (outdated).

TilesManager::hasPixmap()

This function is meant to check if all tiles of a given region are updated. Returning true means that all tiles intersecting a given region have a pixmap and are not marked as dirty. If at least one of them does not match this rule, the function will return false and no further checks are necessary.

  1. We don't need to worry about non-intersecting tiles
  2. Node tiles may not have a pixmap, however its dirty flag indicates that one of their descendants is dirty. If such tile has the dirty flag set to false, all tiles below it are updated.

We were talking about the workflow of a tile request and how it gets painted on the page. We stopped to explain in details the hasPixmap check in Page::slotRequestVisiblePixmaps.

Let's say we don't have the entire visible region in cache.

Inside that if block we create a new PixmapRequest containing all necessary information so the generator can handle it. Such informations are (among others) the requesting observer, the page number, and the page size. In addition to that we now have a normalized rect and a boolean which says whether this is a request for a tile or not.

We already know the viewport needs an update but we don't know where. The following code gets all tiles for a given region and checks which one of them is outdated.

tilesManager->tilesAt( visibleRect )

This function returns the smallest tiles intersecting a given normalized rect.

In other words: it will get all childless tiles intersecting a given region.

  1. Ignore the allowEmpty parameter for now. The default value is true.
  2. The tile doesn't intersect the visible region, so its miss counter is incremented.
  3. Remember when I said that a tile may split in 4 more tiles? That's where it happens. (I'll come back later on this)
  4. The tile is inside the visible region. Decrement its miss counter.
  5. Append tile to the list

Understanding split()

The split function gets an arbitrary value and checks whether the tile's size is above it. If so, the splitting operation occurs.

  1. Split only tiles without children. Don't worry about the children of this tile, tilesAt() will handle them later.
  2. Don't worry about non-visible tiles
  3. Keep trying to split the children tiles. This is for the case the zoom level changes abruptly and the newly created children tiles are still big.

At first the split operation happened at the setPixmap function (that's where a rendered pixmap arrives at the tiles manager) but this happened to be a terrible idea.

Page::slotRequestVisiblePixmaps() use tiles returned by TilesManager::tilesAt() to make the request's normalized rect. If we don't split the tiles right in tilesAt, there's a chance that the visible region intersects a big tile. Furthermore, a big request would be made and most of it would probably be useless.

We were talking about how we get to know what region needs update.

After that, the outdated tiles are used to create a single normalized rect which will be set to the request. This request is then added to a list of requests.

Sending the request to the generator

The method DocumentPrivate::sendGeneratorRequest() iterates over the list of requests, performs some checks and operations and then call the generator to render the page (or tiles).

Some of those checks are:

  1. The previous code checks if the soon to be requested pixmap is already in cache.
  1. Checks whether the current request is already being processed by the generator.

Do not make the same request multiple times

Sometimes the generator takes too long to render while the user may keep moving around the page. Therefore the same region will be requested again (since it's not yet in cache). To avoid that we keep track of the current processing request and drop any repeated ones.

We always keep track of current request rect, page width and page height. Those informations are set right before handling the request to the generator.

For a better understanding, check out this patch

Avoid making unnecessary requests

The following code show how a tiles manager is created. That happens when a request is bigger than a threshold.

Also, if the tile is too small, the tiles manager is dismissed.

After that the generator receives a valid request and proceed to render the appropriate image. When the image is ready it calls the page's setPixmap method which also call TilesManager::setPixmap( QPixmap*, NormalizedRect ).

Usually the incoming pixmap represents more than one tile. If you head back to the explanation of Page::slotRequestVisiblePixmaps you'll notice that single requests to multiple tiles are preferred.

  1. Check if the upcoming pixmap was expected. This avoids processing late requests.
  2. Find in which tiles the pixmap will be set. Call to a private setPixmap.

The private setPixmap function is big so I'll explain it in parts.

Check if the current tile is the one to set a pixmap.

  1. Conversion from NormalizedRect to QRect. This is going to be used in the code below
  2. Checks if the current tile is one of the tiles in which the incoming pixmap will be used.
  3. True if part of the tile won't be painted using the incoming pixmap. A tile is only used if the pixmap can paint it completely. Otherwise its children will be used.
  1. Pixmaps are painted to childless tiles.
  2. New pixmap arrived. Unmark dirty state.
  3. Remove previous pixmap
  4. totalPixels indicates the total memory used by the tiles manager.
  5. Slice and set pixmap to tile.
  6. Although tiles are split inside tilesAt there are some situations where pixmap is set without calling that function (like when a tiles manager is constructed)

If the current tile has children two things can happen:

We can pass the pixmap to its children.

Or we notice that the tile is too small to have children. So the four children tiles are merged into one tile (the children are removed and the parent is used instead).

When the page view use tiles

I've made small modification to PageView::drawDocumentOnPainter. The crop parameter passed to PagePainter::paintCroppedPageOnPainter now represents the visible region.

A lot of changes were made to PagePainter::paintCroppedPageOnPainter. That's the function that gets the page's pixmap (or tiles) and draw it in a QPainter.

  1. Get tiles with pixmaps
  2. We don't check if the tile is dirty. That's because even dirty tiles can be rescaled and painted. If we put a limit on that, there won't be a smooth transition between zoom levels
  3. Just paint it :)

tilesAt (again)

Note that second parameter in tilesAt. That's allowEmpty and here indicates that only tiles with pixmap will be returned.

With allowEmpty set to true (default), tilesAt will return the smallest tiles intersecting a given rect. It doesn't matter whether it has pixmaps or not. This is very useful when those tiles are used to request new pixmaps.

On the other hand, page painting requires tiles with pixmaps. Even though pixmaps are always set to leaf nodes of the tree, some may have pixmap whereas their children won't.

Rotation

Add rotation support to tiles manager

Evict unused tiles

Usually pages are removed from cache if the application is using too much memory. However some pages may have a lot of tiles in cache and still be in the viewport (specially visible pages). We can't wait until the page is ready to be removed. Instead we should evict unused tiles from the page.

At first pages that are far from viewport are removed completely. The next approach is to remove tiles from pages that were not removed. This step doesn't require the page to be out of the viewport (but tiles intersecting it are kept).

The procedure is simple. We cleanup memoryToFree bytes from the tiles manager and then update m_allocatedPixmapsTotalMemory which is used to keep track of the memory usage.

tilesManager->cleanupPixmapMemory(memoryToFree)

This function removes memoryToFree bytes worth of tiles in decreasing order of importance.

The first value to check is whether the tile is dirty. Dirty tiles are there only to have something to show while the current tile is being requested.

After that the miss counter is taken into account. The higher this value, the least important the tile is.

The miss counter

This counter is updated inside TilesManager::tilesAt()

A call to tilesAt means that tiles are going to be used. Those that intersects the viewport have their miss counter decreased.

On the other hand, an increment is made for tiles not intersecting the viewport.

Note that we don't go further and increment the counter for the children tiles. Although the counter only makes sense for tiles with pixmap (and most of them don't have children), it would take a lot of resources if the entire tree were traversed only to increment the miss counter. When we increment a tile's miss counter, if it has children, we're indirectly incrementing the counter of its children.

cleanupPixmapMemory has two steps. First the tiles are ranked according to what was explained before.

rankTiles

rankTiles get all tiles with a pixmap and add to a list that will be sorted and used to know which tiles should be evicted first.

It also adds to the children tile the miss counter of their parents.

After ranking and sorting, tiles are removed one by one until memoryToFree bytes are removed (or there isn't any other hidden tiles).

  1. Do not remove visible tiles
  2. Update totalMemory()
  3. Mark parent tiles as dirty (recursively)

Modifying PDF generator to the use of tiles

To work properly with tiles only a few changes had to be made to the PDF generator.

Return true on supportsTiles (it defaults to false).

Modifying PDFGenerator::image() to request only part of the page if the request is a tiled request.

PageView::scrollTo()

Finally this last thing I did is not directly related to the tiles manager but it was essential to make it more robust.

PageView is an QAbstractScrollArea and whenever a value of one of its scrollbars changes, the method slotRequestVisiblePixmaps() is called. Also the scrollbar values are used to determine the current viewport (which is vastly used by the tiles manager).

The problem is: zoom actions changes both vertical and horizontal scrollbars, one after the other, and when slotRequestVisiblePixmaps is called first, it has the new value for one scrollbar but the old value for the other. This will obviously lead to a wrong viewport and tiles may be requested to a region that is not visible at all.

To fix that I introduced a new function to PageView called scrollTo which calls slotRequestVisiblePixmaps only once, after both scrollbars are updated.

Always have the correct viewport when zooming