Expose JS API lod tree walker

[jo-chemla]

Hi there,

Context is I'm trying to get a POC for converting the RAD tiled-splat format (generated offline from build-lod bhatt-lod) into an OGC 3D-tiles dataset, with glb leaf nodes relying on the KHR_gaussian_splatting + spz extensions. I've got one question that could facilitate implementing that converter and would probably make it more future-proof.

Once the tree is walked, for each splat tile, extracting the raw typed array data (for a specific LoD node's splats, positions, scales, rotations, SH etc) can be done via ExtSplats/PackedSplats encoding utilities, utils.encodeExtSplat/utils.unpackSplat. This way, the splat geometry can be repacked into a glTF buffer via something like gltf-transform and written as a KHR_gaussian_splatting GLB.

What's missing at the moment would be a lod tree walker. It could be useful to have a js API-way to traverse the RAD hlod splat hierarchy node by node, similar to how 3d-tiles-tools exposes a TilesetTraversal.traverseExplicit() pipeline. This pipeline relies on a callback being executed on each tile/node being visited, with access to its metadata (child indices, bounding volume, geometric error) - see this thread CesiumGS/3d-tiles-tools#177 and folded code block for function signature.

Result from a quick chat with claude sonnet: It would help reconstruct the tree topology in JS without parsing internal wasm memory or the raw binary format. The LodTree (center, featureSize, childCount, childStart per node) is precomputed in wasm memory for the lodWorker but has no JS-side equivalent of forEachSplat. A lodSplats.forEachNode((index, childStart, childCount, bounds, featureSize) => {}) callback, mirroring the existing forEachSplat pattern — would make it possible to reconstruct the tree topology in JS without parsing Wasm memory or the raw binary.

3d-tiles-tools tilesetTraverser.traverse example

  // Traverse the tileset
  const tilesetTraverser = new TilesetTraverser(directory, resourceResolver, {
    depthFirst: false,
    traverseExternalTilesets: true,
  });
  await tilesetTraverser.traverse(
    tileset,
    async (traversedTile: TraversedTile) => {
      if (traversedTile.isImplicitTilesetRoot()) {
        return true;
      }
      // For each content: Compute the convex hull, and add it
      // as a "Feature" to the feature collection
      const contentUris = traversedTile.getFinalContents().map((c) => c.uri);
      for (const contentUri of contentUris) {
        const cartesianPoints = await extractCartesianPoints(
          resourceResolver,
          contentUri
        );
        const contentHull = await computeConvexHull(cartesianPoints);
        if (contentHull) {
          featureCollection.features.push(contentHull);
        }
      }
      return true;
    }
  );```

</p>
</details> 

[mrxz]

With the RAD format the LoD-tree itself isn't spatial and isn't "tiled" either. For streaming the tree is spatially partitioned into chunks, but not into tiles. In fact the bounds of these chunks aren't persisted and only used during construction.

Exposing a JS API for traversing the LodTree is likely going to be hard to use and not the right solution. As mentioned above there won't be a bounds parameter on the callback. And depending on whether the RAD file is paged or not, the splat data might not even be present while walking the tree. So there'd have to be a way to trigger chunk fetches separate from the main lod driver for paged splat support.

Based on your description an offline process is likely going to be a better fit. Especially for a POC I'd opt for adjusting the build-lod command to directly output the desired "tile" data in separate files. You can directly work with the internal representation and directly output SPZ files, avoiding intermediate conversions for both performance and accuracy. The biggest challenge is likely going to be determining which LodTree nodes to use/keep and in which tiles they need to end up.

[jo-chemla]

Thank you for coming back with all these details, and stating why that tree-walker is not yet doable, and potentially not a good idea. The Spark 2.0 blog post, especially section Spatially partitioning LoD tree and lod-chunking example led me into thinking the tree was indeed spatially organized. Quick excerpt below:

There are many strategies possible here, but Spark's method aims to have splat data spatially co-located by subdividing space into recursively smaller regions. Chunks of 64K are filled with splats within these spatial regions from largest to smallest, resolving as much detail as possible within the chunk.

The first chunk has no spatial bounds and starts with the root splat at index 0, then its children, then their children in order of decreasing size until we have reached 64K splats. We then subdivide space into AABB regions and recurse on each region, adding splats within the regions until they fill a 64K chunk. These regions are further subdivided and the process continues until all splats have been output to a chunk.

With this strategy, the first 64K chunk of splats loaded are the largest 64K splats in the tree, allowing a coarse version of the splats to be rendered almost immediately. Each additional chunk of 64K splats delivers as much detail as possible within spatially subdivided regions. This way, we can fetch chunks corresponding to regions near the viewer and resolve details quickly.

Depending on how you subdivide space into AABB regions and recurse on each region, [...] further subdivided until all splats have been output to a chunk, sound similar to building up an octree, BVH or similar resulting spatially-consistent hierarchy.

I'm pretty close to having a great shot at rad-to-3dtiles, since it can use explicit tiling (not only octree or equivalent), which is what is using for arbitrary child-to-parent mappings. Given the chunks bounds are not persisted, I'm rebuilding them offline, parsing both the tree hierarchy as well as the tiles geometry to encode to glb nodes with KHR_gaussian_splatting extension / spz compression.
Still wrong Geometric Error computation and tiles streamed, but allows me to render rad tiled splat scenes converted to 3dtiles via 3DTilesRendererJS (so also R3F) / CesiumJS

Just for reference, the rad-to-3dtiles toolbox I implemented evolved into any tiled-format to 3dtiles). Right now I'm doing various 3dtiled-to-3dtiles, <fmt>-to-3dtiles with input format being either

• pointcloud: COPC, POTREE
• tiled-splats: streamed-SOG, XGrids LCC, sparkjs/worldviewlabs RAD,
• tiled-mesh/ptc: ESRI I3S.

I'm also testing live middleware handling requests to a proxy 3dtiles endpoint, and fetching the hierarchy / translating the node tiles content geometry on-the-fly - so can use any 3dtiles compatible viewer or lib, like unreal-engine, qgis etc, to read these 3dtiled formats.

[mrxz]

Depending on how you subdivide space into AABB regions and recurse on each region, [...] further subdivided until all splats have been output to a chunk, sound similar to building up an octree, BVH or similar resulting spatially-consistent hierarchy.

That is the current strategy used for chunking the splats of the LoD tree for the RAD chunks and it does effectively build an octree. But this spatial information isn't retained in the resulting RAD chunks. The LoD system operates on the LoD tree and the chunks are for streaming/progressive loading. The chunks could also be "arbitrarily" filled with splats and everything would still work, though it'll likely have to fetch a lot more chunks to get all desired splats for a given view as they can be scattered about.

In fact, you can find several alternative/experimental chunking strategies in chunk_tree.rs. Not all of these prioritize (or incorporate) spatial information. Of course, due to the nature of how the LoD tree is built, parent splats are bound to be spatially close to their children, so that will play a part one way or another.

I'm pretty close to having a great shot at rad-to-3dtiles, since it can use explicit tiling (not only octree or equivalent), which is what is using for arbitrary child-to-parent mappings. Given the chunks bounds are not persisted, I'm rebuilding them offline, parsing both the tree hierarchy as well as the tiles geometry to encode to glb nodes with KHR_gaussian_splatting extension / spz compression.

Based on the screenshot I believe you might be conflating the RAD chunks and LoD tree nodes. By recomputing the bounds of the splats in a chunk you might be able to reconstruct the octree used during chunking, but that isn't the LoD tree. A chunk can have splats from multiple "levels" of the LoD tree and these shouldn't be rendered together.

If you do intend to stick with "chunks" -> tiles conversion, you should extract the "leaf-most" splats based on the LoD tree from each chunk, as I'm fairly certain the direct children are never split across chunks.

In any case, that is why I suggested making this an offline process and possibly writing it directly in/against spark-lib. That way you can guarantee that the spatial partitioning is applied and have all the relevant data you'll need. Though I'm not convinced the chunking logic is the best basis for tiles.