Clarify upsampling requirements in 3DTILES_implicit_tiling

[kring]

In Cesium World Terrain, it doesn't really make any sense for just 1, 2, or 3 child tiles to be available for rendering. Either the tile is a leaf and has 0 children available, or, if we refine this tile, we're going to need to be able to render all 4 of its children. If we refine a parent tile but only have three children, there would be a hole where the fourth child is meant to be.

However, it's actually fairly common in Cesium World Terrain to have a tile with only 1, 2, or 3 tiles marked as available. When this happens, the client is expected to subdivide the parent tile to create the missing children, a process that is called "upsampling" in CesiumJS and cesium-native. This is a small optimization, reducing the number of pre-generated tiles that need to be stored and transmitted.

In the more general case of 3DTILES_implicit_tiling, though, a missing child tile might be common and normal and not indicate any need for upsampling. For example, if the tileset is buildings, there may simply not be any buildings in the area of a child tile.

So, some questions:

1. Should we enshrine "no need to upsample" in the 3DTILES_implicit_tiling spec? This will make client implementation easier and more performant.
2. Should there be a way to indicate that upsampling should happen? This would make it easier to convert Cesium World Terrain and similiar to 3DTILES_implicit_tiling (and may help out other tilers in a similar boat), but at the cost of client complexity.

[ptrgags]

I wonder if the distinction should depend on the type of refinement? e.g. REPLACE refinement would require all four children to be present (e.g. terrain) while ADD refinement doesn't have this restriction (e.g. for buildings)

[kring]

I don't think so @ptrgags, because buildings could be REPLACE as well. It will never hurt to do the upsampling, though, it's just (potentially unnecessary) complexity.

As an aside, I kind of think we should deprecate ADD refinement. It has problems:

1. Precision. Additive refinement means geometry from large tiles is sometimes viewed up close, which is a recipe for poor precision.
2. Even worse precision when the position attribute is quantized or otherwise compressed.
3. It's very difficult to sensibly drape raster overlays on additive-refined tileset.

Of course, we could turn an ADD tileset into a REPLACE one at runtime, and very well may end up doing that in Cesium for Unreal, but I'm not sure the value of ADD refinement actually outweighs the costs.

[javagl]

When this happens, the client is expected to subdivide the parent tile to create the missing children,

Is this already "enshrined" at some point?
(Or is it just an internal practice to handle the fact that CWT sometimes contains this sort of data?)

In the more general case of 3DTILES_implicit_tiling, though, a missing child tile might be common and normal and not indicate any need for upsampling.

I think this could be the case for buildings and terrain, and for ADD as well as REPLACE.

Beyond that: There may be an implicit assumption below that, namely that terrain geometry is always... "complete" (as in ~"homeomorphic to the 3-sphere"). If somebody only has terrain for a certain area (e.g. a certain country), I wonder how this case should be handled:

Specifically: Clients should be able to trust the availability info, and know that the upper right child is not available, because ... there is nothing.

I'm not so deeply involved in how the tilers actually generate that data, but ... if the client had to figure out the difference between available and reallyAvailableBecauseThereIsGeometry, then this would confront the client with a task of which I think that it should be handled by the tiler - even though this would mean that the client requests child data which it already implicitly had (because it's only a part of the parent tile data).

(Other questions might become relevant then. For example: How often does this happen in practice?)

[kring]

Clients should be able to trust the availability info, and know that the upper right child is not available, because ... there is nothing.

Yes, I think I agree. Clients should never be required to upsample, and the spec should say so. Or perhaps no one outside of Cesium would even think of doing that anyway, so it doesn't really need to be mentioned. That will make it slightly more work to convert Cesium World Terrain to 3D Tiles with 3DTILES_implicit_tiling, but that's ok.

[lilleyse]

@kring how often does the client needs to upsample for CWT? I kind of agree with @javagl that that upsampling should happen at tiling time so that availability isn't ambiguous, but also don't want to balloon the number of network requests with small redundant data.

If we don't give any hints in the spec, will Cesium Native just continue to treat CWT as "complete" and upsample as needed?

[kring]

@lilleyse I don't know offhand how often it happens. It would only be on edges where multiple data sources that went into CWT meet. It's uncommon enough, though, that we nearly got to release before we noticed we weren't doing the upsampling:
CesiumGS/cesium-unreal#233

I don't think it'll balloon the number of tiles or network requests much, so I'd definitely support dealing with it at tiling time.

Either way, cesium-native will need to do upsampling in some situations. Backward compatibility for quantized-mesh for one. And high-res imagery draped on lower res terrain, for another.

[javagl]

One could argue about whether the behavior in this case is so much an aspect of "a certain runtime behavior" that it does not have to be specified. But not saying anything about the case of "one quadtree node with 3 children" will raise the question about how this should be handled. (It already did, in slack, and it will in the future, in GitHub issues).

So the crucial question is: How will this affect the spec?

Even if it only was a (non-normative) "Implementation note", I wonder what it could look like.

Consider this pseudocode:

void renderImplicitTiles(ImplicitQuadtreeNode node) {
    vector<ImplicitQuadtreeNode> children= node.getChildren();

    // No children? Render current content
    if (children.size() == 0) {
        render(node.content);
        return;
    }

    // Four children? Render each content
    if (children.size() == 4) {
        for (ImplicitQuadtreeNode child : children) {
            render(child.content);
        }
        return;
    }
    
    // TODO What is the pseudocode for this part?
    ....
}

If the answer to the TODO is "Whatever is done in the 1000 undocumented lines of code in upsampleGltfForRasterOverlays, then I have to say: "Nope. This cannot go into the spec". (And if somebody disagrees: What is supposed to be done here or here?)

---

One could mention it, but leave it vague and open, as in

Implementation note: When a client encounters an N-ary implicit node with 1...[N-1] children that are available and have content, then the behavior in terms of the rendered result is not specified. Depending on the nature of the underlying data, clients may chose to only render the available child content, or combine the content of the node with the available child content in a sensible manner.

I don't recommend this, of course. It would be a form of surrendering in view of the accidental complexity that we're facing here. And of course, it would make it impossible to achieve a cleanly defined state in the future without breaking ""backward compatibility"" for existing combinations of implementations and data sets (and we're already seeing that).

---

A more abstract aside: When it comes to implementations, I'm usually repeating the mantra "When in doubt, leave it out". It's always possible to add something later. But it is never possible to remove something later. When it comes to specifications, the mantra could be "When in doubt, don't allow it". It's always possible to relax a requirement later. But it's never possible to make a requirement stricter.

---

Maybe the spec can still be made stricter, and then refer to future data sets and implementations that will be created, and the existing tiler+CWT+CesiumJS/cesium-native behavior can be seen as an inofficial, internal backward compatibility mechanism. That will cause trouble (*cough* gltfUpAxis *cough*), but maybe less trouble than the fragmentation that could be caused by leaving this case unspecified.

[lilleyse]

I say we close this for now - if 3DTILES_implicit_tiling marks content as unavailable then that volume of space should be considered empty. It's the tiler's responsibility to fill that space with upsampled content if needed.

cesium-native will just need backwards compatibility for quantized-mesh.

[IanLilleyT]

It would be useful to make content availability even stricter:

• child content must be all available or all unavailable (see above comments)
• child content cannot have unavailable parent content

This means:

• No more runtime upsampling to fill in empty gaps (see above comments)
• Geometry cannot disappear (or reappear) as the camera zooms. If missing geometry is actually desired it should be handled at the tiler level by writing zero triangles / points / etc for the content. (Is this allowed in glTF?)
• Leaf tiles must have content
• Easier to determine if something is a leaf tile. Right now you have to check descendent content availability which could mean fetching entire subtrees in pathological cases. This could be avoided by introducing a child subtree content availability that has a recursive definition, but that feels too complicated.

I probably have several blindspots. Is anything made worse or impossible with these rules?

[javagl]

I probably have several blindspots.

Me too. But a few short comments:

child content cannot have unavailable parent content
[...]
If missing geometry is actually desired it should be handled at the tiler level by writing zero triangles / points / etc for the content. (Is this allowed in glTF?)

This is allowed. { asset { version: 2.0 } } is a complete, valid glTF 2.0 asset. But ... something might have to be done to prevent the client from sending out hundreds or thousands of requests for ... essentially empty files.

Leaf tiles must have content

This sounds sensible for me (I always wondered what could be the purpose of leaf tiles without content, but they considered that they might carry some other data).

But ... when all leaf tiles must have content, and this implies that their parents must have content, then ... I think that some of the data structures ... "collapse": Right now, they store availability information for tiles and content, for each node in a tree. With these additional constraints, they'd basically just describe ~"the set of available leaves", and then there might be an easier and more compact representation of that. (I think you once mentioned the option of having something like a deepestAvailableLevel and depthUpToWhichTheTreeIsComplete or so...?)

(I'll probably have to re-read this and think more thoroughly about the implications on the spec - and even then, I could hardly foresee the implications for the implementation, so I'm curious what others think...)

[IanLilleyT]

I might need to change the second rule from

child content cannot have unavailable parent content

to

child content cannot have unavailable parent content unless all ancestor content is unavailable

(there's got to be a shorter way to say that...)

This would mean content availability is still needed after all - to handle cases like content decimation being unacceptable and only leaf tiles being allowed to render. Maybe useful for CAD models. You still get the benefit of occluding tiles that are offscreen but you'd have to crank down your geometric error to 0.

I was going to say a double headed quadtree that has a root tile with no content, but usually that's implemented as two different implicit tiles...

[javagl]

A related issue, about the role of "empty tiles" that are used for culling (but not refinement): #609