Thread by @SebAaltonen

Let's discuss why I think 4x4x4 tree is better than 2x2x2 (oct) tree for voxel storage.

It all boils down to link overhead and memory access patterns. L1$ hit rate is the most important thing for GPU performance nowadays.

Thread...

2x2x2 = uint8. That's one byte. Link = uint32 = 4 bytes. Total = 5 bytes.

4x4x4 = uint64. That's 8 bytes. Total (with link) = 12 bytes.

4x4x4 tree is half as deep as 2x2x2 tree. You get up/down twice as fast.

Voxel mask (in non-leaf nodes) tells us which children are present. You can do a popcnt (full rate instruction on GPU) to count the children. Children are allocated next to each other. Children sub-address can be calculated with binary prefix sum (= AND prev bits + popcnt).

In a 4x4x4 tree, our uint64 gives the ray at least 4 steps (DDA) worth of data using a single memory load. In best case 12 steps. These extra steps allow the ray to get further from a surface faster. When you exit the 4x4x4 brick, you are further away...

In a 2x2x2 tree, you go two steps and then go one level up, and then another step or two and another level up. 4x4x4 tree doesn't need the middle step at all. Middle step = different memory location = potential cache miss. We want to avoid this.

In Claybook we had 8-bit SDF mip chain. World gen generated every mip, but my ray-tracing algo only used every other mip as that was faster. The reason was better cache utilization. Every mip level is stored separately. Extra mips = bigger working set.

gdcvault.com/play/1025030/A…

This is the same reason why 4x4x4 tracing ends up being faster. It's touches less different cache lines, and transitions faster to near/far trace (fast empty space skip <-> near surface root finding).

2nd reason why 4x4x4 tree is better is the amount of metadata compared to payload. For each 64 bits of voxels, we have 32 bits of link (offset). That's 66% payload / 33% link. 2x2x2 tree has 20% payload / 80% link. In data structure design, you always want to minimize metadata.

3rd reason is cache line utilization. 5 byte node is just 3.9% of a 128 byte cache line. 12 byte node = 9.3%. Since children are allocated next to each other (shared link), a full set of children = 40 bytes in octtree and 768 bytes in 4x4x4 tree. 40 bytes = 31% of a cache line.

Thus even if we have all 8 children present, the octree still doesn't utilize the cache lines fully. Partially used cache lines will be evicted from the tiny L1$, and you pay for data you didn't use. In realistic case we have less than 8 children, so this issue is even worse.

For the 4x4x4 tree, the children often span multiple cache lines (up to 6), since they are continuously allocated. This is great for cache access pattern, especially in cases of nearby voxels representing a continuous surface, which is a common pattern for real content.

Why not 8x8x8 or 16x16x16 trees? If you already allocate children next to each other 4x4x4 is good enough as it puts children in the same cache line implicitly. 4x4x4 fits nicely in a single uint64, so it's efficient to load and process in a single register. 8x8x8 = 512 bits.

Since voxel octrees often encode just the surface, a more narrow region is more storage efficient. Bigger nodes increase the ratio of payload:metadata, but the ratio is already pretty good in 4x4x4 tree. Most nodes are leaf nodes and leaf nodes don't need the link.

The last reason to avoid 2x2x2 tree is that GPUs are not optimized for 1-byte memory loads. Leaf nodes without metadata are just 1-byte. 64-bit loads are much more optimal. You basically get 64-bits for the same price as 8-bits.

Of course we have to ask: Why not a single cache line aligned nodes. That's iffy because, A) are storing sparse data (surface near band is not a tile), B) GPU SIMD branch/loop coherency issues (homogenerous tiles are important). Allocating children contiguously is almost as good.

And most important last: Do not mix material/texture data in your ray-tracing data structure. Keep it minimal. Find the ray hits first. Then do material/texture stuff. You don't want to load material/texture data to L1$ for voxels that you miss.

If you don't want to store extra links for material/texture data, then you can just do 1:1 mapping (two base pointers) or AoSoA-style alternating arrays with cache line aware strides. There's lots of ways to achieve material/texture data separation efficiently.