3D Tiles 1.1 - Implicit tiling

Recently the 1.1 version of 3D Tiles was released. One of the new features is 'implicit tiling'. When using this feature the spatial data is divided in a regular pattern (quadtree for 2D or octree for 3D). The advantage of this method is that we no longer have to specify the location and bounds of each tile (in large/multiple tileset.json files).

One of the more complex aspects of Implicit Tiling are the 'availability bitstreams'. These bitstreams are used to indicate where content can be found (using bit '1') or where nothing can be found (using bit '0').

A simple availability bitstream could look like '01100' for 2 levels in a quadtree. The first bit (value '0') means there is no content on level 0, so the client should not request anything for tile (0,0,0). The following 4 bits ('1100') means there is content on level 1 for tile (1,0,0) and (1,1,0) but not for (1, 0, 1) and (1,1,1).

To transform from a 2D or 3D matrix to a 1 dimensional array the Z-order curve/Morton code is used (see https://en.wikipedia.org/wiki/Z-order_curve).

In this notebook we compute the availability bitstream in a real world data scenario. As input data we use a SpatiaLite database with US building footprints (https://wiki.openstreetmap.org/wiki/Microsoft_Building_Footprint_Data), specific the Dover dataset (https://1drv.ms/u/s!AqWv0F0N63JkgQqO6E9e2kI28R16).

Javascript library Leaflet is used to visualise the results.

For more information about Implicit Tiling see https://github.com/CesiumGS/3d-tiles/tree/draft-1.1/specification/ImplicitTiling

Database

As test database a SpatiaLite database is used, this is an SQLite database with spatial functions. It's created using GDAL command line tool 'ogr2ogr' from the download shapefile:

$ ogr2ogr -f sqlite -dsco spatialite=yes delaware.sqlite bldg_footprints.shp

spatialite_db = "https://bertt.github.io/spatialite_sample/delaware.sqlite"

Data inspection

First inspect the data, there is a table ('bldg_footprints') with 22532 building footprints and height attribute.

Create quadtree

Now we create a quadtree. An important parameter is the maxFeaturesPerTile (default value = 1000). If there are more than maxFeaturesPerTile buildings in an area, the area is divided by 4 equal areas on a lower level. We use a recursive function for this.

When changing maxFeaturesPerTile to a higher value, less levels will be created.

Here we call the recursive function, results are visualized in LeafLet. Each cell has less buildings than the maxFeaturesPerTile parameter.

Get Morton indices

To calculate the availability bitstream, we loop through all levels and determine the Morton index per level.

maxZ = 4
width = 16

Summarized per level in a table the Morton index looks like:

To get the availability bitstream for all levels we concatenate:

mortonAllLevels = "00000001001010001000001011100000010101011000011110000101100111111000001100000000000000000000000000000000000001111111100000000000000000000111100001111000000000000000000000000000000000000000000000000000000000000000000001111000000001111111100000000000000000000000000000000000000001111000000000000000000000000000000000000000000000000000000000000"

Conclusion

With some computation we can get the availability bitstreams using real word data. The availability bitstream is used in the Implicit Tiling 'subtree' file so a client knows where to find content and where nothing is available.