Implicit tiling - request tiles from child subtree files

[bertt]

Hi, I’m doing some experiments with implicit tiling and child subtree files.
Background of this work is issue Black screen on loading larger tileset with implicit tiling where we had 1 large subtree file on level 0 (without child subtrees) that resulted in long loading times.

As a workaround I’m trying to split the subtree file in 4 parts on level 1, but the problem is in that case no tiles are requested from the Cesium Viewer (the child subtree files are requested though).

For a reduced example see: https://bertt.github.io/cesium_3dtiles_samples/samples/1.1/subtrees/level1/

tileset.json - subtreeLevels = 1

0.0.0.subtree:

• Tile availability: 1

• Content availability: -

• Subtree availability: 1000

Result: 1.0.0.subtree is requested

1.0.0 subtree:

• Tile availability: 11000

• Content availability: 01000

• Subtree availability: -

Result: box_2__0_0.glb is NOT requested Also no error is shown.

I think it has got something to do with a rule in the specs (3d-tiles/specification/ImplicitTiling at draft-1.1 · CesiumGS/3d-tiles · GitHub), where with subtreeLevels=1 only 1 level can be requested (so box_1__0_0.glb)? If so this design seems to be very limited.

So the question is how can we split a large 3D Tileset in 4 child subtrees on level 1 and get it working in Cesium? cc @ptrgags

[Marco13]

tl;dr: I think that the core of the issue is that subtreeLevels=1 does not make much sense. Note that this is the number of levels. The “root node” of the subtree is indeed “one level” (see the image at 3d-tiles/README.adoc at draft-1.1 · CesiumGS/3d-tiles · GitHub for example).

(In fact, I even wonder whether subtreeLevels=1 should be disallowed by the spec - but there might be corner cases where this makes sense…)

---

Details - this may not be immediately relevant, but I’ll drop this here anyhow: Applying the validator to the given tileset (without a BOM - see notes at the bottom of this comment) reports this:

Validation result:
{
  "date": "2023-01-24T16:45:00.854Z",
  "numErrors": 2,
  "numWarnings": 0,
  "numInfos": 0,
    {
      "type": "SUBTREE_AVAILABILITY_INCONSISTENT",
      "path": "subtrees/1.0.0.subtree/tileAvailability",
      "message": "The tile availability declares an 'availableCount' of 2 but the number of available elements is 1",
      "severity": "ERROR"
    },
    {
      "type": "SUBTREE_AVAILABILITY_INCONSISTENT",
      "path": "subtrees/1.0.0.subtree/contentAvailability/0",
      "message": "The content availability 0 declares an 'availableCount' of 1 but the number of available elements is 0",
      "severity": "ERROR"
    }
  ]
}

The validator is still in an early preview version. There’s always the possibility that this may a false flag. And it might be that a message is misleading. But … the message seems to be “right”: It computes the number of nodes that appear in one subtree. And for subtreeLevels=1, there is only one node in a subtree (namely its root node). So the availableCount=2 can not be correct.

But … I have to admit that despite the error message, I had to dig into the files, and run it in a debugger, to finally notice what’s probably the reason here (and what might have been obvious in hindsight) - namely, that the tileset says subtreeLevels=1.

I wonder how that case could be detected and pointed out more sensibly. Iff subtreeLevels=1 should not be an ‘error’, then I’d consider to at least mark it as a ‘warning’ or ‘info’ - it’s a corner case, for sure.

---

Note about the BOM in the given tileset:

The tileset.json at cesium_3dtiles_samples/tileset.json at 2fab7cb01daa892f63432226221b256d33fa2cd9 · bertt/cesium_3dtiles_samples · GitHub contains a Unicode BOM (i.e. it starts with the bytes EF BB BF). CesiumJS will probably not complain about that, but the specification explicitly requires no BOM to be present.

The 3d-tiles-validator actually did not handle this until now, and reported an unhelpful parsing error. In the current state (i.e. the next release) it will explicitly say

"path": "C:/cesium_3dtiles_samples/samples/1.1/subtrees/level1/tileset.json",
"message": "Unexpected BOM in JSON buffer: UTF-8 (EF BB BF)",

Removing the BOM allows the validator to run on the tileset, printing the report that I posted above.

[bertt]

Ok thanks, appreciate your help I fixed the BOM error. I could also reproduce the validator errors.

About the subtreeLevels: If I use subtreeLevels = 2, then the following error appears in the Cesium browser after retrieving the root 0.0.0.subtree: ‘Error: Availability bitstream must be exactly 2 bytes long to store 16 bits. Actual bitstream was 1 bytes long.’. This is about the subtree availability string. 2 bytes is needed to retrieve subtree file 2.0.0, but I want to get subtree file 1.0.0. I used ‘1000’ to define the availability of 1.0.0.subtree (on level 1 where there are 4 cells - 1 byte). It looks like there is no problem with using subtreeLevels =1 (according to the browser and validator), but there is an issue with child 1.0.0.subtree.

About the validator messages in child subtree file 1.0.0.subtree:

• Tile availability: ‘The tile availability declares an ‘availableCount’ of 2 but the number of available elements is 1’. I used for tile availability ‘11000’ in file 1.0.0.subtree. The first bit is for the current cell on level 1 (1,0,0), the second bit is for the lower left cell on level 2 (2,0,0). That’s 2 bits available so I don’t understand the message ‘but the number of available elements is 1’.

• Content availability: ‘The content availability 0 declares an ‘availableCount’ of 1 but the number of available elements is 0’. I used ‘01000’ in file 0.0.1.subtree for content availability. So the first 0 bit is for the current cell (1,0,0), the first one bit is to retrieve content from cell 2,0,0. There is only 1 bit set so I don’t understand the message ‘but the number of available elements is 0’.

Looks to me the validator (and Cesium) only reads the first bit of the availability bitstream in the child subtree file (because subtreeLevels=1)? Is this intentional? If so it’s quite limiting.

Workaround would be create a subtree file for every tile on every level (when subtreeLevels=1) or every two levels (when subtreeLevel = 2)?

[bertt]

Maybe it helps: a drawing of what I’m trying to achieve for this test (green arrow works, red arrow does not work):

[Marco13]

It might be the case that I haven’t correctly understood some technical details of the question, or the actual goals. But I’ll try to address it as far as I think that I understood it - even though this is in a different order than you brought up these points:

About the validator messages in child subtree file 1.0.0.subtree:
…

• Tile availability: ‘The tile availability declares an ‘availableCount’ of 2 but the number of available elements is 1’.
  …
  I used for tile availability ‘11000’ in file 1.0.0.subtree. The first bit is for the current cell on level 1 (1,0,0), the second bit is for the lower left cell on level 2 (2,0,0). That’s 2 bits available so I don’t understand the message ‘but the number of available elements is 1’.

When subtreeLevels=1, then the tileAvailability and contentAvailability will always have a length of 1. The tiles/content in the subtree then only refer to the root node. (The root tile is always present. The root content may not be present. But there’s hardly any use in the tree if there is no content. That’s one aspect of why having subtreeLevels=1 hardly makes sense…)

So indeed, your conclusion is correct:

Looks to me the validator (and Cesium) only reads the first bit of the availability bitstream in the child subtree file (because subtreeLevels=1)? Is this intentional? If so it’s quite limiting.

Yes, it is only considering the first bit - because there is only one tile. (In fact, you don’t need a bitstream then - it can just be a constant availability).

My guess is now that some confusion (and maybe the core of the question) is related to the childSubtreeAvailability. It may be worth pointing out that the structure of the tile- and content availability is different to that of the childSubtreeAvailability. When you have a subtree with a certain number of subtreeLevels, then the tile/content availability refers to all the nodes of this subtree. The childSubtreeAvailability refers to the next layer of subtrees.

For example:

When subtreeLevels = 2:

• The length of the tile/content availability is 5: One for the root node, and 4 for the child nodes
• The length of the childSubtreeAvailability availability is 16: One for each child node of the leaf nodes of the actual subtree

When subtreeLevels = 1:

• The length of the tile/content availability is 1 - only containing the root node.
• The length of the childSubtreeAvailability availability is 4 One for each child node of the root node (which also is a leaf node then…)

About the subtreeLevels: If I use subtreeLevels = 2, then the following error appears in the Cesium browser after retrieving the root 0.0.0.subtree …

To emphasize that: If you only changed the subtreeLevels in the tileset JSON, then the subtree files that you used previously will no longer work. The subtree files have to “match” the structure that is defined in the tileset JSON, so to speak.

---

An attempt to capture what I think your goal is (and correct me where I’m wrong):

The intended structure is this: 3 levels, where the green cells (marked with 1) have available tiles, and the cell marked with 1+ also has content:

And this should be written into an implicit tileset, with subtreeLevels=1.

I’ll emphasize this again: This will hardly make sense. I know that having “large” subtree files can lead to issues with CesiumJS, related to the issue about subtree loading that was sparked by one of your other threads. But the case of subtreeLevels=1 is extreme, and likely very wasteful. The question of “How to make subtree division easier to do correctly?” certainly has some … engineering aspects, but setting subtreeLevels=1 is certainly not the answer, except for some sort of “compliance tests” or experiments.

If this is the goal, then an example tileset with this structure is attached here:

Cesium Implicit Tileset Forum 22048.zip (2.5 KB)

It contains the tileset.json, the subtree files, some dummy content, and (maybe most importantly) a subtreeInfo.md file that shows the JSON for each subtree, as well as the buffer data (i.e. the bits and bytes of the availability bitstreams. Since there is only one node in each subtree, only the childSubtreeAvailability is relevant here, as mentioned above)

The tileset passes validation, and can be rendered with CesiumJS, basically using the sandcastle code from one of the 3d-tiles-samples:

[bertt]

yeah this work is related to Improve lazy loading of implicit subtrees · Issue #10939 · CesiumGS/cesium · GitHub, there we had only the root 0.0.0.subtree. This works for small datasets but for large datasets (with a lot of content tiles from level 5 to 10) it resulted in bad performance on startup. So I thought let’s split the root subtree file in 4 parts at level 1 (with subtreeLevels =1) and performance should be something better.

But now it looks I have to use subtreeLevels > 1 and create a lot more subtree files (on various levels). It get’s complicated quickly

What I don’t understand whats the purpose of this subtreeLevels parameter? To retrieve the next level subtree file(s) it can be derived from the length of the childSubtreeAvailability (if its 4 → 1 level, if its 16 → 2 levels). When childSubtreeAvailability is empty in a subtree file I expected I could use any level for tile/content availability (so not depending on subtreeLevels parameter) but apparently that’s not the case.

[Marco13]

There are some aspects of implciit tiling that are a bit hard to grasp. There are some degrees of freedom for implementations, and depending on the implementation, the purpose of certain parts may not be perfectly clear (we talked about CesiumJS apparently not using the availableLevels, in Implicit tiling: availableLevels and IIRC a later thread).

---

A somewhat anecdotal example: I created an implementation for reading, traversing, creating and converting implicit tilesets. And at some point, I noticed: “Whoops. I didn’t use childSubtreeAvailability anywhere in my code!”. Sure, I always ran this on the file system, and basically did an if (exists(subtreeFile)) where necessary. The childSubtreeAvailability serves - very roughly speaking - the purpose of not having to do this kind of check. One has to keep in mind that when operating on the network, this would imply sending out thousands of requests that would be answered with 404s…

---

Regarding the subtreeLevels:

One could see the information in the implicitTiling JSON structure as two separate things.

1. The subdivisionScheme and availableLevels define the overall structure. Together with the content.uri (i.e. the template URI), they define the overall structure of the tileset, in a very abstract sense. They just say “This is an octree with 10 levels, and the content is in stored in files called level_x_y_z.glb”.

2. The subtreeLevels and subtrees.uri are information about how this abstract data structure is stored. It’s not possible or sensible to store the availability information for 10 million tiles and content in a single file. So the overall information is subdivided into subtrees. These subtrees are regular, and always have the same height (namely subtreeLevels). One can imagine the overall data structure to be divided into “layers” of subtrees.

There often are different ways how certain structures can be defined, or how certain information can be encoded. This may be related to your point:

To retrieve the next level subtree file(s) it can be derived from the length of the childSubtreeAvailability (if its 4 → 1 level, if its 16 → 2 levels). When childSubtreeAvailability is empty in a subtree file I expected I could use any level for tile/content availability

If I understood this correctly, then this eventually leads to a structure where the heights of the “subtree layers” is not fixed. And that’s a valid (and interesting) point.

Until now, I think that you only intended to leave the number of levels for the “leaf subtrees” open. As a generalization (just brainstorming now: ) one could consider having an implicit tiling scheme where the first subtree has a height of 3, and its children have a height of 5, and its grandchildren have a height of 7. This could even be very generic, as in subtreeLevelsProgression=CONSTANT/LINEAR/EXPONENTIAL - or somehow defined explicitly for each “layer” (as in something like subtreeHeights: [3, 5, 7, INFINITE]).

But one would have to think deeply about the implications for this on the spec- and implementation (!) level - and.whether it could be expected to have benefits that are worthwhile. Having some regularity in the subtree structure may as well be beneficial here.

(An aside: It is also true that some information can sometimes be derived from other information. For example, the subtreeHeight could be derived from the childSubtreeAvailability. But as you said, this only works when the latter is present, so defining this clearly and unambiguously in the spec would be hard…)

---

Going up a few levels: I think the overarching question here is How to make subtree division… that I linked to earlier.

When you have a tileset with 10 levels, you could choose subtreeLevels=10,9,8...,2,1, and the resulting layout out the data itself (for the same abstract data structure!) would be vastly different. Many of them will be very wasteful - like 9 and 1. The engineering questions here start with fairly trivial ones, e.g. whether availableLevels is divisible by subtreeLevels. But they quickly touch topics where there is no “one true answer” - for example: Which content is actually available? This determines whether you can structure the data in a way that nicely exploits the cases where you can use constant:0/1 for the availability. On top of that are questions like “What are sensible file sizes for subtree files, to be transferred via network without large delays?”, or “Does the client/viewer use a smart approach to deal with this data?” (which leads to the CesiumJS issue that you linked to).

For now, I think that setting subtreeLevels=ceil(availableLevels/2) should be a good first shot. But this is just a gut feeling for now: Every potential insight of such trial and err… engineering has to be justified with experiments - i.e. with performance tests. And… designing these in a sensible form is a huge topic on its own…

[bertt]

Using your formula ‘subtreeLevels=ceil(availableLevels/2)’ I was able to create a working tileset (in this case using subtreeLevels=3) demo see https://bertt.github.io/cesium_3dtiles_samples/samples/1.1/subtrees/level3/ .
As extra step I had to fill the availabilities in the child subtree files with additional zero’s (to match the length of the availabilities in the root subtree file).

Thanks!

[Marco13]

Thanks for the update. Yes, with "availableLevels": 5 and "subtreeLevels": 3, there will be some unused bits. How hard one should try to make sure that availableLevels divisible by subtreeLevels is one of the open questions. Getting a better idea of the trade-offs here, e.g. between file sizes and load times, could be part of a more thorough peformance evaluation.

An aside: Your samples are already linked at 3d-tiles/RESOURCES.md at main · CesiumGS/3d-tiles · GitHub , but I actually considered to put a more prominent link to them into the 3d-tiles-samples repo. They nicely cover the area between “artificial examples” and “(small, and therefore more easily manageable) real-world data”, and use some of the features that are not yet used in the 3d-tiles-samples (e.g. subtree metadata).

I also had a short look at the underlying repo (i.e. the subtree repo), but would need more time to dive deeper into that. I could imagine that some of that could be used to generate test data in various configurations, exactly for these kinds of performance tests. I also have some infrastructure for that (unrelated to Cesium, just a private repo), where I tried to add a few abstractions for implicit tiling (that may turn out to be useless eventually), but I haven’t been using it for real data (beyond the artifical samples) yet.

[bertt]

For the samples I used a small set from Microsoft Building footprints (Microsoft Building Footprint Data - OpenStreetMap Wiki), some real world data to avoid falling in very tiny demo data trap

A while ago I wrote a fun Observable notebook about the implicit tiling 3D Tiles 1.1 - Implicit tiling / Geodan research | Observable , I’m considering to add the child subtrees to it.