Marble/VectorTilingProposal

From KDE Community Wiki
Revision as of 16:40, 28 May 2012 by Tackat (talk | contribs)

Vector Tiles for Marble

Here are a few requirements that need to be met for technical, common-sense or organizational reasons. Of course they don't have to be met immediately but should at least serve as a goal.

Server Requirements

  • For reasons of performance tile data files should be available statically (so it shouldn't be necessary to have a script create the tiles on demand).
  • It should be easy to set up any server based solution on the KDE server.
  • Tile update needs to be possibly regularly (e.g. once a week).
  • The tiling access scheme should be similar to the current bitmap tiles: i.e. the access urls should be similar to e.g. a.tile.openstreetmap.org/3/4/2.png

Tiling Requirements

  • It needs to be possible to render single tiles alone.
  • It should be possible to show tiles from different tile levels at once.
  • It needs to be possible to identify features across tiles and across tile levels. E.g. it should be possible to identify several sections of the same river belonging together or resembling the same river. This could be done through an id that serves as a unique identifier for the same geometrical feature across tiles. This is also necessary to display the "same" feature only once in the model (despite having versions for multiple zoom levels in memory)
  • It should be possible to fill or select a certain polygon (e.g. a country) inspite of the fact that it might be distributed across different tiles that possibly belong to different tile levels.
  • The data that is stored inside a tile should stay relatively small (in the kB range).
  • The tiles rendered should adhere to cartographic standards.

Discussion of a possible Vector Tiling approach

The idea is to create tiles similar to the standard OpenStreetMap vector tiles. So the data inside the tile needs to get prefiltered: The polygons provided for display need to be carefully chosen (depending on importance) and need to be simplified in advance (Node reduction). So a simplified level 0 tile could look like this:

This would be the lowest zoom level possible. Now further tiles could get created for higher zoom level using the Quadtile scheme. This is a level 2 tile that shows parts of Europe (the actual one would probably already display country boundaries, but we leave that out in this discussion for purposes of simplicity and illustration):

As you can see the file just contains the clipped polygon data. It does not contain the whole polygon data e.g. for the whole Eurasian-African coastline for this zoom level since that would add lots of data and would defeat the idea of the tiles (imagine having to download the whole Eurasian coastline at zoom level 16 just to display a small part of Portugal ....).

Now what would happen if the user started Marble and would zoom so that tile level 2 gets activated? It would download tile by tile. What we'd like to avoid at all cost is that tiles appear and are surrounded just by a plain white area like this:

Instead it should "reuse" data from lower-level tiles that show those parts which haven't been downloaded yet: With the most simple approach this would require that a tile is fully opaque (i.e. no parts of the whole square are transparent) and really gets rendered on top of the "parent" tile. Here we see our tile from tile level 2 "inserted" into the tile 0:


Now this approach would work to some degree and might be the first mile-stone to implement. However it has some backdraws:

  • It requires to completely "overpaint" the tile of the tile level below. So it would still be required to render the area below the level 2 tile.
  • the same geometric feature that is covered in both tile levels is distributed across different polygons. This might make "filling" (e.g. with a plain color or a texture) harder. Same applies for selection of such a polygon.

Also note that if tiles weren't fully opaque with this approach we'd run into artefacts like visible on this picture (land shines through where there should be sea, e.g. Red Sea). To better recognize the issue the land of the level 2 tile has been marked with a darker gray tint:

Hook nodes

So ideally one would merge polygons from lower zoom levels with those polygon section from higher zoom levels into a single polygon.

Of course one would need to specify points where the polygon sections of higher zoom levels could dynamically "hook in". For the lack of a better term we just call these specially tagged nodes "hook nodes" in this document. So a level 0 tile would just contain hook nodes (here red squares) along the QuadTile borders for the level 1 tile borders (black lines):

Now if we just provided hook nodes for the next level then we'd have to download the full range of level 0 to level 8 parent tiles just to properly embed a single level 9 tile. So it would be useful if the hook nodes would span a wider range of zoom levels: E.g. a level 0 tile could provide hook nodes for zoom levels 1 and 2 - or even for 3. This approach would then reduce the amount of parent tiles to be downloaded for higher zoom levels dramatically. Here you can see the hook nodes on a level 0 tile for level 1 (red) and level 2 (green) as an example:

Now of course the "child" tile would have to define hook nodes as well so that its polygons can hook into the polygon of the parent tile. In this picture the hook nodes that are meant to be connected to the parent tiles are colored yellow:

And here is a picture that shows the "hook nodes" of both, the level 0 and the level 2 tile:

Also note the purple "helper node" at the top-right of the child tile. This node requires a special form of tagging so that it can be distinguished from the other "hook nodes". The purpose of the helper nodes is this: if a polygon is downloaded without any parents to hook in then the polygon area needs to get properly closed. The helper nodes define nodes that close the polygons properly even if there are no parent tiles that the polygon can hook into.

The nice thing about this concept of "hook nodes" is that a map browser client doesn't necessarily need to provide support for them: Since they are just specially flagged nodes they can just be considered normal nodes by the client and the client would still render the whole tile properly. Advanced map browser clients could still make use of them.

The same also applies if the child tile defines some "hook nodes" (e.g. a cut off lake like the Caspian Sea on Tile 2 above) that are meant to be used by a parent tile and the available parents don't have fitting interfaces (because the lake isn't covered in those parent tiles). Then the two end-points of the half-cut lake would get connected right away until more data is available.