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.
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.
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).
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.
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.
In Page::hasPixmap() we check if the page has a TilesManager. Then we call TilesManager::hasPixmap() to know whether the given region is updated.
The tiles manager needs to know the page's size, and when it changes all pixmaps are marked as dirty (outdated).
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.
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.
This function returns the smallest tiles intersecting a given normalized rect.
In other words: it will get all childless tiles intersecting a given region.
The split function gets an arbitrary value and checks whether the tile's size is above it. If so, the splitting operation occurs.
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.
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.
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:
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
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.
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.
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).
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.
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.
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.
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.
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 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).
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.
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.