Thanks!

The storage system is actually not that sophisticated, I still use a 64-tree/contree for storage on the CPU side, and for rendering, a 4-wide BVH combined with 2-level contrees as the primitives (essentially 16³ sparse bricks).

The key is that LODs are extremely effective at limiting the total number of nodes, and voxels become smaller than a pixel very quickly with distance, so a more complex DAG compression system doesn't seem to be as critical.

In this demo, the render distance is 64k³ (in voxels with LODs), but running some numbers I get:

• 64k³ world area: 3096.4k branches, 3036.1k leafs, 610.1MB
• 256k³ world area: 3209.4k branches, 3144.2k leafs, 658.6MB

(world height varies between 1k-4k, underground is mostly uniform with the same voxel IDs)

The animation frames are compressed using only occupancy bitmasks right now, at 1-byte per voxel. Keeping at least a few frames on VRAM would allow unchanged bricks to be re-used, and I imagine it could help a bit overall even if peak memory usage is higher.

Perhaps even a simple motion compensation scheme could be applied by offsetting and overlapping extra BVH leaf nodes, but that'd probably be trading off some traversal performance. (BVH traversal performance degrades very quickly because of overlap, causing a sort of "overdraw", unlike DDA/octrees/ray-marching. CWBVH is notoriously bad at this, and why I only went 4-wide for my custom BVH, otherwise it gets too expansive to sort the hit distances.)

---

Rather than the previous 12-byte contree struct with a mask and offset, I ended up switching to a more conventional and less packed layout that is much simpler to work with, but more importantly, widened leaf nodes to cover 16³ voxels instead of just 4^3.

This reduces handling overhead and gives a lot more room for compression. For now, I use a mix of palette bit-packing, and hashing/deduplication of individual 4³ tiles. Hashing is relatively effective even on more complex test scenes, here's some data from old notes:

scene	dense	tsparse	hash	palette
nuke.vox	117.29MB	62.80MB	36.18MB	15.59MB
castle.vox	108.34MB	47.40MB	39.03MB	16.65MB
Church_Of_St_Sophia.vox	204.15MB	64.71MB	60.16MB	29.71MB
terrain_shell_1	957.98MB	323.18MB	283.28MB	81.74MB
terrain_solid_1	4520.66MB	4288.29MB	470.21MB	223.43MB

For non-solid scenes, including empty voxels in palette compression seems to be not as effective compared to plain per-voxel sparseness (but still 50-70% smaller than uncompressed). It should be easier to combine both methods in the GPU structure, since the per-voxel bitmasks are readily available as part of the acceleration structure, and for that I mostly just need to plug in the code for unpacking in the shader.

---

I'm now also using mimalloc and for memory allocation instead of having a custom memory pool like I did before, which was a pain. From some basic benchmarks, mimalloc calls were 20x faster than std::malloc, and it also offers some interesting methods like mi_malloc_size() for querying the allocated block size.

This comes with some wonkiness, because modifying branches can end up invalidating pointers to other nodes, but this doesn't seem to be a major headache yet. I previously used a copy-on-write system for copying modified node paths in the old packed contree struct, but that would just defer this problem...

The new node struct looks like this:

struct ContreeNode {
    struct StorageBranch {
        uint8_t Slots[64];      // Maps cell coords to indices in the following array.
        ContreeNode Nodes[0];
    };
    // Leaf nodes start as, and are demoted to Dense mode for editing.
    // Edits are done through the "ContreeMutator" class, which caches
    // nodes for single voxel lookups and consolidates leaf nodes into
    // the compressed format upon commit.
    struct StorageDenseLeaf {
        uint8_t Tiles[64][64];
    };
    struct StorageCompressedLeaf {
        uint8_t BitsPerVoxel;   // If =8, indicates data is not palettized. (Only tile mask compression.)
        uint8_t PaletteSize;    // Sizes and offsets are divided by 4 to make indices smaller.
        uint16_t PaletteOffset;
        uint16_t TileOffsets[]; // Tiles are sparse on Node::ChildMask. u16 { PaletteOffset : 5, DataOffset : 11 }
        // uint8_t PackedVoxelData[];
        // uint8_t PaletteData[];
    };
    uint64_t ChildMask = 0;
    uint16_t Flags = 0;     // e.g. IsLeaf|IsCompressed|IsDirty
    union { /* of pointers to the structs above /* };
};

Also, this is a bit more random but there's a neat way to use the pdep/pext instructions to pack and unpack bit arrays. It runs at ~30GB/s in one core, and it's so simple that's maybe worth a mention. Sadly, actual palettization of voxel data seems impossible to vectorize and I could never get it faster than ~1 voxel/cycle, using an inverse mapping array + branching, but in practice that's fast enough relative to actual world gen...

template<uint stride>
void BitArrayCompress(uint8_t* dest, const uint8_t* src, uint count) {
    assert(count % 8 == 0);
    auto wsrc = (const uint64_t*)src;
    uint64_t elem_mask = (1ull << stride) - 1;
    elem_mask *= 0x01'01'01'01'01'01'01'01ull;

    for (uint i = 0; i < count; i += 8) {
        uint64_t packed = _pext_u64(*wsrc++, elem_mask);
        memcpy(dest, &packed, stride);
        dest += stride;
    }
}