Implicit tiling schemes

[pjcozzi]

The general spatial data structure in tileset.json does not allow for random access, e.g., "give me tile x,y at level z" because the tiling scheme is not fixed; instead the data structure needs to be searched top-down.

If random access is needed, we could allow a tileset to advertise itself as using a particular typing scheme, e.g.,

"tilingScheme" : "quadtree"

[pjcozzi]

Could also be useful for #90.

[pjcozzi]

The tileset.json would have to specify the tile format - or each tile could say the formats of its children - and each tiling scheme may have some specific data like a bounding volume if it isn't global, e.g.,

{
  "asset": { /* ... */ },
  "tilingScheme": "quadtree",
  "format": "b3dm",
  "boundingVolume" : {
    "region": [ /* ... */ ]  // could default to global
  }
}

• Geometric error would either be implicit or part of a new section of the tile's payload
• The tile may also need a new section for children information like child contents' bounding volumes

[pjcozzi]

This might have to get pushed post 1.0, but I would at least like to prototype beforehand since this is an important feature for global-scale datasets.

@austinEng perhaps you can help with this once you are ramped up.

[pjcozzi]

This should probably be called implicit tiling scheme, not explicit tiling scheme. Renamed.

[pjcozzi]

For point clouds, also see https://github.com/connormanning/ept

[pjcozzi]

A few potential use cases / interoperability to consider

• quadtree for global or local terrain or vector data. Dual-quadtree for Cesium's current quantized-mesh terrain. How valuable is the dual tree given it is atypical?
  • Also for 3D buildings from OSM and trees from OTM
• octree for interior CAD/BIM, exterior CAD/BIM, point clouds, photogrammetry, 3D buildings, etc. Local with Cartesian AABB/OBBs and global with geographic regions
• interop well with Mapbox Vector Tiles, https://github.com/mapbox/vector-tile-spec
• Interop well with GeoPackage, https://github.com/AnalyticalGraphicsInc/3d-tiles/issues/89#issuecomment-465330742
• Interop well with CDB, https://www.opengeospatial.org/standards/cdb
• Interop well with Uber H3 Hexagon index? https://eng.uber.com/h3/

Implementation notes

• See https://github.com/AnalyticalGraphicsInc/3d-tiles/issues/92#issuecomment-234416818
• How much better can this make skip LODs, prefetch, etc?
• How to efficiently handle sparse trees and avoid needless client requests for empty tiles. What can we learn from https://github.com/AnalyticalGraphicsInc/cesium/blob/master/Source/Core/CesiumTerrainProvider.js#L57?
• Does this interop well with tilesets of tilesets?
• What client-side projections to support other than geographic to Cartesian? Also for use beyond rendering use cases?
• What metadata to store about tiles, e.g., tile format(s), used point cloud attributes, used vertex attributes, (including range for both?), etc. Note this is likely a useful object property for 3D Tiles even separate from implicit tiling.

[OmarShehata]

Requested on the forum for figuring out which buildings are in a given area.

[loshjawrence]

Some of the potential schema ideas coming out of the implicit tiling brainstorm/prototyping: https://github.com/AnalyticalGraphicsInc/3d-tiles/tree/implicit-tiling/extensions/3DTILES_implicit_tiling_scheme

layerNames string array that supplies prefixes (or postfixes) to the base uri for fetching those layers of data. One set of traversal calculations and one availability for a bunch of different layers of data that pertain to the same context. Use this mechanism to encode a bunch of layers of metadata(ex: per point) as basis textures (ktx2 payloads). Mip down to 1x1 for ave, min, max Use this mechanism for time-dynamic (layer name is timestamp) or is something more explicit needed?

[pjcozzi]

Draft spec: https://github.com/AnalyticalGraphicsInc/3d-tiles/pull/386

[kring]

An idea I really like:

Implicit tiling in 3D Tiles should: 1) allow new implicit tiling schemes to be defined, and 2) not require that clients actually understand the implicit tiling scheme in order to work.

This might sound impossible, but it's surprisingly easy to achieve with a small tweak. Rather than expressing implicit tiling as a special section in the tileset.json with a bunch of parameters that clients need to understand, instead allow the BVH to be loaded from an arbitrary external URI referenced in the tileset.json. Then, provide some standard external URLs can be used to express standard tiling schemes.

So, a tileset.json might look like this:

{
    "asset": {
        "version": "1.0"
    },
    "geometricError": 563.8721715009725,
    "root": {
        "uri": "https://cesium.com/3dtiles/tilingschemes/quadtree?bbox=-180,-90,180,90&root=2,1&levels=12"
    }
}

So now a client that understands the quadtree implicit tiling scheme just notes the URI and knows what do; no need to actually request it. While a client that doesn't understand that particular implicit tiling scheme simply has to request the full 3D Tiles BVH available at that URI. By requesting and caching unfamiliar tiling schemes, clients can "learn" new implicit tiling schemes.

Obviously lots of details to work out, particularly around the standard URIs. But I think this provides a really nice progressive enhancement approach. There's almost zero new mandatory spec for clients to deal with, but it still enables optimization - in an extensible way - by sophisticated clients.

[lilleyse]

Implicit tiling is now an extension: https://github.com/CesiumGS/3d-tiles/tree/main/extensions/3DTILES_implicit_tiling.

Will open a new issue for https://github.com/CesiumGS/3d-tiles/issues/92#issuecomment-586098550