Clustered top level

The top level normally has one leaf per instance, holding the instance's whole mesh box. When big meshes overlap (architecture, Sponza, Bistro: one instance per wall, floor and column), a ray enters many instances it never hits, and pays a transform and a descent into each. clusterTraceScene cuts each mesh's tree into subtrees ("clusters") of fewer than primitiveLimit triangles and gives each cluster its own top-level leaf, with the cluster's box moved to world space. The top level can then tell the parts of overlapping meshes apart.

This is three-mesh-bvh's ClusteredBVH, the top level its BVHComputeData always builds. The cut is the same: walk down the mesh's tree and stop at the first node with fewer triangles than the limit, or at a leaf.

import { buildMeshBvhWithTinyBvh, buildTraceScene, clusterTraceScene, createTinyBvhBuilder, uploadTraceScene, type MeshGeometry, type TraceSceneInstance } from '@pmndrs/bvh';

const tiny = await createTinyBvhBuilder();
const scene = await buildTraceScene(meshes, instances, { build: (geometry) => buildMeshBvhWithTinyBvh(geometry, tiny) });

// Cut every unshared mesh's tree into subtrees of fewer than 64 triangles, each its own top-level leaf.
const clustered = clusterTraceScene(scene, { primitiveLimit: 64 });
console.log(clustered.clusters.records, '->', clustered.clusters.clusterRecords, 'top-level records');

// The same walk, kernels and queries trace it.
const buffers = uploadTraceScene(device, clustered);

The result is an ordinary scene. Nothing in the walk changes, so traceModuleWgsl, the batch kernels, the CPU walk, the GPU queries and SdfGenerator trace it as they are, in every node and triangle format, merged groups included.

const clustered = clusterTraceScene(scene, {
    // Instanced meshes too, but not the mesh you refit (its cluster copies would not follow).
    split: (record) => record.meshIndex !== characterMesh,
});

meshClusters(scene, nodeOffset, primitiveLimit) returns one mesh's cut without building anything: each cluster's root, triangle count and object-space box.

Each cluster's record is the instance's own record (transform, instance index, mask, material, flags) pointing at the cluster's subtree, so a hit names the same instance and triangle, with the same side, material and normal, and t is the same to the bit. The one difference is which of two triangles at the same distance (or a few ulps apart, where faces meet) is reported, because the walk meets them in another order.

CPU walk, nodes visited per ray (both levels), not time. Sixteen meshes of 4,000 triangles whose boxes overlap, one instance each, quantized nodes, 20,000 random rays:

GPU timings are not measured yet.

For instances that never move, merging does more: one world-space tree over all of them, no top level to walk. Clustering keeps each mesh in its own space, so it also works where merging doesn't: instanced meshes (merging never copies a mesh used twice), instances you will move (cluster again after moving them), and a scene that mixes merged groups with other instances (a merged group is cut like any mesh). It costs no triangle copies.