Indexing of Vector Tiles (Clipping Justification)

vector-tile-pr.md

Indexing of Vector Tiles (Clipping Justification)

This pull-request provides the ability to display vector tile trees containing leaves at different levels of detail (LOD) based on data density. This requires clipping tiles when zoomed in beyond a physically present leaf and using an index to determine tile presence.

Purpose

The goal is to efficiently cook tiles and still maintain a high level of data precision in vector tiles. We can achieve this by limiting the cooking of tiles to a satisfactory LOD in less geometrically dense areas. On the consumer side, clipping can be used to clip larger tiles to fit a more precise LOD as needed. This methodology also provides over-zooming of tiles beyond the LOD limit of the current Vector Tile specification.

In the example above, tiles that contain fewer geometries, such as large areas of the ocean, can be cooked at a lower LOD and clipped as needed for any requested LOD.

Index Model

• Avoid cooking an unnecessarily large number of small tiles
• Stop cooking when the tile complexity threshold is reached
• Provide an index file of available tiles (this avoids round trips to the server)
• Contains fewer vertices which equals smaller GPU load

Index File

The index file provides a quad tree of tiles.

NW	NE
SW	SE

The number of children per node is determined by the complexity of data in the associated tile. This is based on the number of features, attributes, and vertices within the tile. The threshold is determined by the tools used to generate the tiles.

The JSON encoding of the index looks like the following:

{
   "index":[
      [        // -- NW tile
         1,    // -- NW - NW tile
         [     // -- NW - NE tile
            1, // -- NW - NE - NW tile
            0, // -- NW - NE - NE tile
            1, // -- NW - NE - SW tile
            0  // -- NW - NE - SE tile
         ],
         1,    // -- NW - NE tile
         [     // -- NW - SW tile
            1, // -- NW - SW - NW tile
            1, // -- NW - SW - NE tile
            1, // -- NW - SW - SW tile
            0  // -- NW - SW - SE tile
         ]
      ],
      1,       // -- NE tile
      1,       // -- SW tile
      [        // -- SE tile
         1,    // -- SE - NW tile
         1,    // -- SE - NE tile
         0,    // -- SE - SW tile
         1     // -- SE - SE tile
      ]
   ]
}

The size in bytes of the JSON encoded format of the index file is roughly equal to twice the number of tiles.

Possible values per node:

• 0 - No tile
• 1 - Tile with no children (leaf tile)
• 2 - Sub-tree defined in different index file

Tiles are identified by lod/h/v, where the h and v values are indices on a 2^lod by 2^lod grid.

A leaf tile is a single tile with no children. Leaf tiles have higher geometry precision and leverage the extent property from the Vector Tile spec. They are slightly larger due to encoding, but can be clipped and over-zoomed, which is a nice advantage.

Clipping

The clipping improvements allow the client to take advantage of the indexed vector tiles. When a tile with no children is viewed and you want to over-zoom this tile, the clipping logic will determine the bounds to clip geometries from this tile into a new child tile in the client.

These clipping capabilities also work on non-indexed vector tiles.

Benefits

This pull request has the following benefits:

• More efficient cooking of tiles
• Allows over-zooming on tiles via clipping

Because there are fewer tiles to download there is less latency in the client.

The current LOD limit of the spec is LOD 18. However, LOD 15 is probably more reasonable for the world. The index and clipping capabilities allow tiles to be resampled and displayed beyond these limits. By definition these tiles are not as complex, but clipping one simple tile is more advantageous than generating additional tiles during the cooking process. Clipping provides the ability to resample current tiles in the cache and still respect the current spec.

This methodology also benefits developers creating offline-mapping applications. Since there are fewer tiles generated in areas with low detail, these tiles may be stored and displayed more efficiently and over-zoomed (clipped).

Benchmarks

Test Description

The test consists of two steps:

• Process the leaf tile for one LOD higher than its native LOD. So if the tile is cooked down to level 10, the tile is rendered at level 11. It is processed four times, once for each tile coordinate that the leaf tile covers at level 11. Each time the tile is processed for a tile coordinate the geometries needed by the tile are run through the clipping process.
• Process the 4 child tiles that were cooked specifically for the zoom level that was tested in step 1.

The tile coordinates run through the tests were:

Tile coordinate 1:

• Leaf tile: 10, 177,399
• Full tiles:
  • 11, 354, 798
  • 11, 354, 799
  • 11, 355, 798
  • 11, 355, 799

Tile coordinate 2:

• Leaf tile: 10, 177, 401:
• Full tiles:
  • 11, 354, 802
  • 11, 354, 803
  • 11, 355, 802
  • 11, 355, 803

Results

Description	Over-Zoomed	Samples	Time per run	Avg Time	Results
Leaf Tile 1 level 11	true	37	~161.514	~0.054	18.64 ops/sec ±6.92%
Full Tile 1 level 11	false	44	~126.091	~0.031	31.78 ops/sec ±4.76%
Leaf Tile 2 level 11	true	44	~130.134	~0.045	22.45 ops/sec ±5.86%
Full Tile 2 level 11	false	50	112.62	~0.028	35.76 ops/sec ±3.36%

vtiles.png

Do you have code that implements this clipping? Maybe something using OpenLayers api?