Implicit tileset refinement fails to skip LODs

[nithinp7]

During tileset refinement, it is often useful to skip LODs and jump to the target SSE. There are natural stopping points that you cannot skip past like the end of an external tileset or implicit subtree, in these cases more tile metadata must be loaded to know which descendants are available. In the implicit tiling case however, we currently needlessly wait for an implicit tile to be in ContentLoaded, before we create its implicit children, even if the tile availability of its children is already known. This causes each tile to load first before refining as you traverse to the target SSE. Fixing this might require separating out how implicit children are created vs quantized mesh children are created. I think quantized mesh needs to wait until the tile is loaded to create children (or at least it needs to wait until content loaded to know for certain it doesn't have children).

The culprit code (written by me of course!): https://github.com/CesiumGS/cesium-native/blob/3cd085eefbe03c408d32a7b53a6467fa991a6ee1/Cesium3DTilesSelection/src/Tileset.cpp#L532-L537

[kring]

@baothientran asked me to write up how this might be done for quantized-mesh / layer.json in the context of the refactored content loading (#508, #510, #511, #512).

To create child tiles in updateTileContent, we need to be able to determine whether child tiles are available. So we need a function something like this:

enum TileAvailability { Available, NotAvailable, Unknown };

TileAvailability isTileAvailable(const Tile& tile) {
   // ...
}

We'll call this function on all four possible children. If all four children are available, we'll create them. If any are unknown, we'll try again later. If some are available and some are not, we'll create all four (upsampling the missing ones).

To implement this function, we need to walk through the layers from top to bottom. If the tile is available in a layer, then the tile is available overall. If it's unknown if the tile is available in a layer, then it's unknown overall. If the tile is not available in a layer, we check the next layer. Maybe clearer in pseudo-code:

TileAvailability isTileAvailable(const Tile& tile) {
  for (const auto& layer : layers) {
    TileAvailability layerAvailability = isTileAvailableInLayer(tile, layer);
    if (layerAvailability == TileAvailability::Available || layerAvailability == TileAvailability::Unknown) {
      return layerAvailability;
    }
  }

  return TileAvailability::NotAvailable;
}

In #510, each layer has a QuadtreeRectangleAvailability that tracks which tiles are known to be available. But this isn't enough information to implement the isTileAvailableInLayer function used above because we can't distinguish NotAvailable from Unknown.

There are many ways to solve this, but an elegant one that @baothientran and I talked about on our call today is to use QuadtreeRectangleAvailability to track the availability of availability information, too. So in addition to CesiumGeometry::QuadtreeRectangleAvailability availability, LayerJsonTerrainLoader::Layer would have another field like this:

CesiumGeometry::QuadtreeRectangleAvailability loadedAvailability;

Each time we load a tile and acquire new availability information, we also update loadedAvailability with the total possible availability in that subtree. For example, when we load tile L0X0Y0, we put the actual availability in availability (as we're already doing), and then also add these rectangular ranges to loadedAvailability:

QuadtreeTileRectangularRange{0, 0, 0, 0, 0},
QuadtreeTileRectangularRange{1, 0, 0, 1, 1},
QuadtreeTileRectangularRange{2, 0, 0, 3, 3},
QuadtreeTileRectangularRange{3, 0, 0, 7, 7},
// and so on through level 10

With that in place, we can implement isTileAvailableInLayer something like this:

TileAvailability isTileAvailableInLayer(const Tile& tile, const Layer& layer) {
  if (layer.availability.isTileAvailable(tile.getID())) {
    return TileAvailability::Available;
  } else if (layer.loadedAvailability.isTileAvailable(tile.getID())) {
    return TileAvailability::NotAvailable;
  } else {
    return TileAvailability::Unknown;
  }
}

[nithinp7]

I think this issue is resolved now, please reopen if I'm wrong @kring!