Limiting the number of files in a directory for implicit tiling

[javagl]

The 3DTILES_implicit_tiling specification allows defining quadtree- or octree tilesets that only exist implicitly. Each of these implicit tiles may have associated tile.content. This tile content is stored in a file that is referred to with a template URI. This template URI includes variables for the tile coordinates (level, x, y, (z)).

For example, an implicit quadtree tileset may refer to b3dm content that is stored under the template URI "content/{level}/{x}/{y}.b3dm".

The number of content files that may end up in one directory may be large. This is true even when they are distributed into mutliple directory levels, by creating subdirectories for each level and each coordinate, as shown in the example above. The size along one dimension, for a given level, is 2^level. This means that for an implicit tileset with 16 levels, there may be content files

content/0/0/0.b3dm
....
content/0/0/65535.b3dm

Having so many files in one directory may not be possible at all for certain file systems, or cause severe performance penalties on others (see https://stackoverflow.com/q/466521 for some details).

There should be an alternative for addressing the content files of large implicit tilesets, beyond the template URIs that are currently allowed.

[donmccurdy]

Loosely related suggestion in #553 (comment), loading multiple tile contents from a single file like uri: lod0.glb#15.

It is a bit regrettable to complicate the specification in order to support the specific combination of (1) an old filesystem, and (2) a server with no distinction between URLs and paths on disk. Cloud object storage (Amazon S3, Google Cloud Storage) is a great way to host large tilesets and has no such limitations. Other complexities exist in URL resolution (e.g. authentication, temporary tokens) which are left out of scope for good reason.

[jerstlouis]

I agree that a distinction between paths on disk vs. URL paths should be made.

Regarding storing on disk, one file per tile might easily be too much overhead See the CDB 2 proposal to handle arbitrarily large datasets by grouping multiple tiles within GeoPackages as tile pyramids based on LOD, but still splitting over multiple GeoPackages for repository use cases.

We also prototyped there the use of glTF as the tile payload for batched 3D models which hopefully could coincide with the 3D Tiles next specification in terms of that glTF content.

The front-end API can remain simple with {lod}/{x}/{y} even if this is the back-end.
Also to consider is requests for multiple tiles at once, something we also plan to support in OGC API - Tiles and OGC API - DGGS.

[lilleyse]

{subtreeLevel}, {subtreeX}, {subtreeY}, {subtreeZ} could be added as new parameters in the template URI.

"{subtreeLevel}/{subtreeX}/{subtreeY}/{level}/{x}/{y}.glb"

For a quadtree with subtreeLevels: 7 this pattern would yield at most 64 glb's per folder.

"{subtreeLevel}_{subtreeX}_{subtreeY}/{level}_{x}_{y}.glb"

While this one would yield at most 5461 glb's per folder (equals the number of tiles in a subtree)

EDIT: this idea may create too many subdirectories. In the example below, within level 21 there will be 2,097,152 subdirectories.

const levels = 28;
const subtreeLevels = 7;

const subtreeLayers = Math.ceil(levels / subtreeLevels);

const subtreeLevel = subtreeLayers;
const subtreeX = Math.pow(2, subtreeLevels * (subtreeLayers - 1));
const subtreeY = Math.pow(2, subtreeLevels * (subtreeLayers - 1));
const level = subtreeLevels;
const x = Math.pow(2, subtreeLevels - 1);
const y = Math.pow(2, subtreeLevels - 1);

console.log(subtreeLevel);
console.log(subtreeX);
console.log(subtreeY);
console.log(level);
console.log(x);
console.log(y);

4
2097152
2097152
7
64
64

[lilleyse]

Another idea is to create subdirectories based on morton index.

[morton id in level 0]/[morton id in level 1]/.../[morton id in level 31].glb

This will limit the number of files or folders in each directory to four for quadtree and eight for octree. They should probably be local morton indexes since global indexes can get very large fast.

One variation on this is to stop subdividing the directories early and store more contents in the terminal folders. In this example there would be at most 21845 glbs in each terminal folder - (4^N - 1)/3 where N=8

[morton id in level 0]/[morton id in level 1]/.../[morton id in level 23]/[morton id in level 24-31].glb

Or apply that concept to the whole tree:

[morton index in level 0-7]/[morton index in level 8-15]/.../[morton index in level 24-31].glb

This system is not really compatible with template uris as they are today. 3D Tiles would need to define a mapping from x,y,z to local morton indexes at each level and the result would be joined into a string based on a user defined separator that could then be inserted into the template uri.

content/{...insert morton path here...}.glb

Also we should keep in mind that there are other filesystem limits besides number of files/folders per directory. ext4 has a theoretical limit of 4,294,967,296 files total which is enough to store a complete quadtree only up to 16 levels.

[erikdahlstrom]

Another idea: add a property that let's one define one or more custom variables for use with the template URI syntax. The variable values could be defined e.g as tile metadata, to be shipped inside the subtree.json binary data section. It would need to have a way to avoid having to write a value for every single tile though (unless actually needed).