Validate that geometry is fully contained in bounding volumes

[javagl]

One aspect of the validation of content data should be to check that geometry is fully contained in the relevant bounding volumes. This refers to content.boundingVolume and each tile.boundingVolume on the path from the tile that contains the geometry, up to the root.

[javagl]

A small update here: When this issue was opened, it would have been a lot of effort to actually implement this, because there was no functionality for computing the bounding volume of the tile content in the first place. In the meantime, there are some functionalities in the 3d-tiles-tools, surrounding the https://github.com/CesiumGS/3d-tiles-tools/blob/ac192defb95fde7c93a06897bf68228bd3ad87ce/src/tools/tilesetProcessing/ContentBoundingVolumes.ts#L25 class, which may allow implementing this check with reasonable effort.

It would likely be computationally expensive, so should probably be disabled by default via a validation config flag. And it could be difficult to make this check "perfect" - for example, some really clever and expensive implementation could compute a bounding volume for an I3DM that is tighter than the one that is computed with the 3D Tiles Tools. But it could at least be implemented as a preview feature, maybe even with some "threshold" so that small deviations would only be a WARNING. In any case, the building blocks are now there.

[javagl]

Minor updates here from investigations about how this could be implemented:

The validator currently checks whether a content bounding volume is contained in the tile bounding volume. This is part of the legacy consistency check. But I think that this is not something that should be validated. It is not required by the specification. The specification always refers to the geometry being contained in bounding volumes, but never to bounding volumes being contained in bounding volumes

Related that that: The previous comment pointed to the functions in the 3d-tiles-tools that allow computing the bounding volumes of content. But these are not useful for validation or consistency checks, for the reason mentioned above: One could compute some bounding box from the content, and determine that this bounding box is not fully contained in the bounding volume that was declared in the tileset JSON, but still, both bounding volumes may fully contain the actual geometry

Now... the only approach that I see for doing a sensible check here:

The functions for computing the bounding volumes in the 3D Tiles Tools already follow the pattern of

1. extracting the vertex positions from the content
2. computing the bounding box from the vertex positions

(with some special cases, e.g. for I3DM, but in principle, it's that).

The positions are stored as some positions : number[][3], but this is hardly required: It could/should just be some Iterable<number[3]>.

The validation function could therefore be implemented as a simple

  private static validate(
    boundingVolume: BoundingVolume,
    positions: Iterable<number[3]>
  ): boolean {
    for (const p of positions) {
      if (!contained(boundingVolume, p)) {
        return false;
      }
    }
    return true;
  }

(with contained or the function itself differentiating or specializing for box/sphere/region).

Now the unfortunate part:

So it will be necessary to iterate over all vertex positions, for each content, for each tile bounding volume 😬 And the image is oversimplified. For a real hierarchy, it will be necessary to iterate over all vertices of all contents to check whether the root tile bounding volume is valid. With a "straightforward" approach, it would be necessary to iterate over the vertices of each content n times, with n being the number of tiles on the path from the content and the root.

But with a dedicated traversal, this may be more reasonable: When traversing down to the content, one could keep some sort of "stack" of bounding volumes that any content has to be validated against. I'll probably try that out...

[javagl]

An aside: A seemingly straightforward optimization of that last approach would be to check whether the geometry is contained in the leaf bounding volume, and then first only check whether the leaf bounding volume is fully contained in its parent (up to the root). If this is the case, then it will imply that the geometry is also fully contained in each of the parent bounding volumes. But 1. when this is not the case, the low-level, really geometry-based check has to be done, and 2. one has to think about how to carry that information up the hierarchy.