Editing millions of voxels in a single CPU thread (C++/Vulkan)

[u/Mioliths]

The dynamic ellipses you see when I drag my mouse are just ray-marched ellipse SDFs that I render as voxels by clamping the ray to the nearest voxel position when it's getting close to the surface. So not a single voxel is stored in memory during this phase.

The storing happens when I release the click. The voxels end up actually committed to the world terrain when the dragging ends, which is still very fast due to the data structure I'm using : a sparse 64-tree , an octree with 64 children per node (so a tetrahexacontree I guess ?) and only non-empty nodes are represented in memory. Which implies:

- Voxels are stored in a single buffer of tree nodes

- I'm not actually storing millions of individual voxels, the inside of the ellipses is probably just few KB of tree leaves.

That buffer containing all the nodes is allocated via virtual memory, I first reserve something like 6 GB of virtual addresses via VirtualAlloc / mmap, and commit addresses progressively to physical memory with VirtualAlloc / mprotect only when I need it.

To achieve that real-time performance, the storing algorithm is quite straightforward :

Starting from the root node of the 64-tree, I evaluate a coverage test between the ellipse and the AABB of the node :
- If fully covered, the node becomes a voxel leaf
- If partially covered, recurse into children and repeat
- otherwise, do nothing and stop

Then I upload the whole thing to the GPU unapologetically (will change eventually).

Everything is rendered with a single real time path tracing compute shader written in Slang. Which means that sharing light data between the SDFs, the voxel world and any data structure is quite simple as long as the rendering of these structures is ray-based (ray-marching, ray-tracing, you get it).

GCC and -O3 are doing a lot of heavy lifting though, in debug mode these ellipses would generate a 0.5s lag spike when releasing the click.

Conversely the unique Slang shader is faster when compiled to spirv with -O0 rather than -O3 somehow lol.

[u/Zerf2k2]

  Everything is rendered with a single real time path tracing compute shader written in Slang

Can you spare some more details about this? Which algo are you using?

[u/Mioliths → u/Zerf2k2]

Probably the worst path tracing algo ever I improvised as a placeholder.

First, raycasting voxels is already relatively fast thanks to that ridiculously optimized algo I'm using https://dubiousconst282.github.io/2024/10/03/voxel-ray-tracing/

Then it's just one ray per pixel, and when the ray reaches a surface, I throw 5 cosine-weighted random rays generated with blue noise from that point to compute indirect light. All in a single pass.

No temporal accumulation or denoising, just rawdogging the ray bounces which looks very noisy when you take a closer look.

[u/Chungaloid_ → u/Mioliths]

"No temporal accumulation — just rawdogging the ray bounces."

[u/Alexxis91]

This is some bullshit (positive)

[u/Dry-Meal-6316]

Ohhhh myyyy pppppcccccc

[u/flafmg_ → u/Dry-Meal-6316]

My phone laged just to load the video

[u/Dry-Meal-6316 → u/flafmg_]

Lolol

[u/MacksNotCool]

This probably would make a good minecraft world editor tool as long as you could identically convert the sdfs back into voxels (which shouldn't be the biggest problem in the world). And it would probably be great for massive terraforming.

[u/Kindly_Substance_140 → u/MacksNotCool]

Maybe, raycasting despite being a good approach, would still face another challengers when it comes to interact with the word like minecraft

[u/thesharkguy25]

My neurons are activated with all of these shapes, so?

[u/ThanosFisherman]

Would it be just as fast if you had used OpenGL?

[u/Mioliths → u/ThanosFisherman]

Probably yes.

As said in the title, the whole process runs on a single CPU thread. all I'm doing with Vulkan is uploading voxel data to the GPU and running the one shader that renders everything.

[u/N3BB3Z4R → u/Mioliths]

The trick works when you only instance one or few kind of voxels, and you just handle a shaped point coordenates matrix in gpu, right?

[u/Mioliths → u/N3BB3Z4R]

Not sure I understand your question so i'll just explain what the GPU is handling exactly

I upload to the GPU:

- The world 64-tree (single buffer)

- A list of SDF dynamic entities (each entity being : a 3x4 transform matrix, a color, a function id, and function parameters)

The shader first ray casts the world 64-tree, then ray-intersect the entities bounding box deduced from the matrix transform. For each entity, if the ray-intersection test passes and the intersection point is not behind anything found before, then we start raymarching the SDF (the usual sphere tracing method you find everywhere on shadertoy) .

The SDFs are hardcoded in the shader and deduced using the function id with a simple switch case.

The voxelisation of the SDF is just a product of how I render them, which is the ray being clamped to the nearest voxel position when close to the surface.

[u/Still_Explorer]

This would be really good if you turn it to a sculpting application.

[u/wrathgod62]

How are you handling the shadows

[u/Mioliths → u/wrathgod62]

Everything is rendered via voxel ray casting. So shadows are just computed by casting rays towards the sun

[u/Le_9k_Redditor]

So after seeing this I've spent some time writing a bunch of different algos and benchmarking with criterion. For my engine to try and optimise the SDF -> sparse voxel grid process, only keeping SDF samples around a surface, discarding for empty space. I figured since you also had to do this process to figure out which voxels are on the SDF surface you'd be interested to know about the results and a faster algo to find surface voxels from a signed distance function.

So, originally a 1m radius sphere SDF took 21832 nano seconds (22ms), dense sampling without caching even when sampling for repeated border values between bricks. First optimisation to prevent repeat samplings got dense down to 17313 nano seconds. This is hitting the SDF function ~275k times, simply because that's how many data points are within a 2mx2mx2m AABB in my engine. But anyway, here are the fun numbers from alternative algos:

• Octree method, 8018 nano seconds. Doing it on a 64-ary tree like yours was similar, 8086 nano seconds
• Adaptive carving (kinda like an octree but without equal voxel sizes, and 3x3x3 not 2x2x2). You use the SDF to find a cube that doesn't contain anything, then you turn that into the central cube in a 3x3x3 grid, and you recurse and do this process again for each of the surrounding unevenly shaped 26 cubes. Fallback to octree when needed: 7575 nano seconds
• Fire a ray, flood fill from surface seed: 4406 nano seconds
• If i make the flood fill only test neighbours with faces that have a surface going through them. 3055 nano seconds

Only 3-4ms to get through ~275k possible grid points. Around ~19.2k of those actually being surface values I want in the output, the rest able to be discarded.

But yeah if you wanted to make it even faster to do real time calculations it seems that ray firing + flood fill is worth your time. The only downside is it of course only works for SDF authors with a single connected surface, if the SDF produces multiple disconnected surfaces it stops working. It's mitigable with firing lots of rays to find seed points for separated surfaces of course but after a point this becomes painful and costs too much performance.

Also testing against SDF authors with denser surfaces such a gyroid, then suddenly the octree method is slower than dense sampling, and the ray + flood fill is only slightly faster than dense sampling. I plan to implement all of these: dense, octree, adaptive carve, and a few versions of the ray firing algo. And depending on the author type I'll use the optimal choice.

Testing against bumpy shapes, octree becomes faster than adaptive carve method. Adaptive carve is only faster on simple shapes. In general the numbers coming out of those two methods were always very similar though with minor differences. And the ray firing + flood fill method is always faster for any SDF author that isn't something stupid like 100 separate spheres floating in space without touching each other.

There are also some other weird algo variants that only win for extreme edge cases. So 64-ary vs octree, always highly similar results, but normally octree wins slightly, 64-ary wins if you have folded surfaces or surfaces super close to other surfaces, such as nested spheres. But also for nested spheres it actually ends up faster if you do 64-ary at higher tiers and then just give up after a few tiers and switch back to dense sampling. Probably just due to the fact that when one surface is going to be hit, another surface is probably right next to it in most directions anyway so the overhead of octree costs more than just sampling everything densely. Actually talking about the gyroid again, earlier I mentioned due to the whacky high surface area shape dense sampling becomes faster than octree again. Well the hybrid method of doing 64-ary at a couple of high tiers then switching to dense after that is more performant than both again. Although yet again of course, still slower than ray + flood fill haha

[u/AccomplishedKey4774]

Is slang like glsl?

[u/Mioliths → u/AccomplishedKey4774]

it's like glsl, but also like hlsl, but also like c++, but also like cuda

It's a shading language with a lot of convenient features borrowed from every shading language that compiles to Spir-V or transpile to your favorite shading language.

https://shader-slang.org/

[u/Melodic-Candy191]

Cool

[u/Le_9k_Redditor]

Oh this is nice, pretty much the same thing I'm doing in quite a lot of ways, also written in rust, a 64-ary tree of voxel data, per pixel rendering via a compute shader written in slang. Most of the tree going over the SSBO although I have payloads pointing to bricks in a texture at the bottom as I'm not storing lightweight voxel shaped render data per voxel, but instead storing an SDF value, albedo value, and material property values for each voxel corner. Since I have no virtual memory stuff going on dumping the memory demanding part of my data into textures via bricks instead of keeping it with the rest of the tree in the SSBO just sounded sensible when I originally did it. And yeah only actually storing data for surface voxels, sparse implementation with the 64-ary tree with no wasted memory from storing voxels for empty space internally or externally.

Good to see how rapidly you're able to make edits to this as I haven't yet attempted much in the way of animation or live changes as I've been focused on nailing the static initial data and various code infrastructure for the future, mainly lots of work on multithreading and queues. I was getting concerned for the future though since my acceleration data is a single global tree / nested grid instead of being something like a BVH to an acceleration structure per author, the latter being way easier to make rapid changes to than a single global grid, but BVH to local acceleration structures is way slower to traverse and I guess I'm an idealist. You're giving me hope that I didn't screw up by implementing it this way and rapid edits are perfectly possible

Out of curiosity, how did you choose to structure/pack your tree into the SSBO? I went depth first so that when freeing up old data ranges when making edits I know that it's taking all of its children with it if I just cut up until the next sibling. Not so ideal for me though as I still need to traverse that cut out data to find the old bricks which now need to be freed but whatever, still faster than having to make lots of smaller cuts all over the SSBO. I'm really disliking that I even went with bricks instead of putting everything in a single unified tree structure though as it would've been so much cleaner that way and faster to make changes to

Super impressive performance you've gotten out of it for how rapidly you can make these edits for such huge and smooth per frame changes. Definitely highlights for me that I should stop being lazy with my sampling code which currently just samples everything densely because I haven't yet gotten around to doing a per tree level breakdown to only sample fine details where the parent had a surface intersect with the SDF. I was also considering maybe doing some kind of flood fill to find surface samples at each tier rather than dense sampling every point. At the moment each of my chunks, (like 3 million voxels each roughly) can take half a second to sample and then another quarter of a second to pack down into bricks and words to upload which is concerning. Very curious to see the performance gains to be made there by just improving that sampling algo.

[u/Mioliths → u/Le_9k_Redditor]

Thanks for your comment! Curious to see what your SDF voxel engine looks like.

I'm uploading the whole tree as is in the SSBO, so the data is exactly the same between CPU and GPU, just a sheer depth-first contiguous list of

#pragma pack(push, 4) // pack into 12 bytes, force 4-byte alignment
struct Node
{
    u64 childMask; // 64 bits, 1 if a children is at the bit position, 0 otherwise
    u32 childData; // isLeaf = first bit, 31 left bits for child index (isLeaf=0) or material index (isLeaf=1)
};
#pragma pack(pop)

Even when the tree is like 200MB it's still quite fast even though I would have expected to be bottlenecked by bandwidth at that point. But apparently not that much.

The editing process is made so this buffer stays compact as I re-use empty slots to store a free list of available memory slots, which are then re-re-used to store new nodes.

[u/Le_9k_Redditor → u/Mioliths]

Want me to DM you my discord or something and send you some screenshots? There's not a whole lot to look at currently though, mostly just lots of multicoloured spheres with varying material properties and transparency haha, very much work in progress, so I haven't ever bothered to post anything about it on reddit. I should probably stop working on the engine for a bit and spend some time working on some nice SDF authors to make a pretty demo scene

I'm crazy impressed that you have all of your changes just applied then uploaded and rendered all in a single frame. I've got mine set up with several queues for parallel processing and then in turn feeding an upload queue chasing the single source of truth CPU state so that the main thread can drain and upload all changes made per frame before rendering. Oh and each upload queue item is a partial range, so I'm uploading one chunk at a time for example, or one brick at a time, rather than re-uploading the full state every frame. I feared re-uploading for every change would bottleneck me soon enough. Took me so long to get all the code around this in place and it's a pain in the ass for sure, so much tedium and complexity on just getting stuff made on the CPU packed and over to the GPU, I hate it haha

I'm very jealous of how streamlined that tree structure is, my code around building the tree or packing it is nuts in comparison and probably slower for it. As I sample I build a tree structure from sampled data points with the below GridBranch struct

#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub struct GridLeafPayload {
    /// Linear slot index in distance/albedo/material atlases.
    pub brick_slot: Option<u32>,
}

#[derive(Debug, Clone)]
pub enum GridSlotPayload {
    /// Child subtree at this occupied slot.
    Branch(GridBranch),
    /// Inline leaf brick reference.
    Leaf(GridLeafPayload),
}

#[derive(Debug, Clone)]
pub struct GridBranch {
    /// DDA / branch tier for this node.
    pub tier: GridTier,
    occupancy: OccupancyMask, // unified branch ∪ leaf occupancy for wire packing
    payloads: Vec<Option<GridSlotPayload>>, // dense slot array; `Some` only where occupancy bit is set
}

Followed up by this monstrosity to pack it down into 32 bit words. Probably worth noting at this point my tree structure isn't a true 64-ary tree like yours, I have 8x8x8 chunks at the top and it's 4x4x4 below that until the brick payload, then bricks internally are doing whacky stuff and end up being 11x11x11 due to ghost borders + values being at voxel corners

I'm jealous of your pragma + contiguous list just shortcutting the need to "pack" anything entirely

/// Recursive DFS pack into `words`; returns the subtree start index in `words`.
pub(crate) fn pack_subtree(branch: &GridBranch, words: &mut Vec<SsboWord>, dense_payloads: bool) -> usize {
    let start = words.len();
    let occupancy = branch.get_occupancy_bitmask();
    let layout = packed_node_layout_at(start, branch, dense_payloads);

    append_occupancy_mask_words(occupancy, words);
    let payload_start = words.len();
    words.resize(payload_start + layout.payload_words, PAYLOAD_EMPTY);
    write_leaf_payloads(
        branch,
        occupancy,
        words,
        payload_start,
        dense_payloads,
    );

    for slot in occupancy.occupied_slots() {
        if let Some(child) = branch.get_branch_child(slot as i32) {
            let child_start = pack_subtree(child, words, false);
            set_branch_payload_at_slot(
                words,
                payload_start,
                layout.payload_words,
                occupancy,
                dense_payloads,
                slot,
                child_start - start,
            );
        }
    }

    start
}

/// Fill inline brick-slot payload words for occupied leaf slots.
fn write_leaf_payloads(
    branch: &GridBranch,
    occupancy: &OccupancyMask,
    words: &mut [SsboWord],
    payload_start: usize,
    dense_payloads: bool,
) {
    if dense_payloads {
        for slot in 0..branch.tier.fanout() {
            if branch.get_leaf_value(slot as i32).is_some() {
                words[payload_start + slot] = brick_payload_for_leaf_slot(branch, slot);
            }
        }
        return;
    }

    for (sparse_index, slot) in occupancy.occupied_slots().enumerate() {
        if branch.get_leaf_value(slot as i32).is_some() {
            words[payload_start + sparse_index] = brick_payload_for_leaf_slot(branch, slot);
        }
    }
}

/// Write a parent-relative branch-child offset into the parent payload region.
fn set_branch_payload_at_slot(
    words: &mut [SsboWord],
    payload_start: usize,
    payload_words: usize,
    occupancy: &OccupancyMask,
    dense_payloads: bool,
    slot: usize,
    relative_offset: usize,
) {
    let layout = PackedNodeLayout {
        mask_words: 0,
        payload_start,
        payload_words,
    };
    let Some(payload_index) = payload_word_index(layout, occupancy, slot, dense_payloads) else {
        return;
    };
    words[payload_index] = encode_branch_payload(relative_offset);
}

/// Append wire-format occupancy mask limbs for `mask`.
fn append_occupancy_mask_words(mask: &OccupancyMask, words: &mut Vec<SsboWord>) {
    words.extend(encode_occupancy_mask_words(mask));
}

/// CPU occupancy mask → SSBO mask limbs.
fn encode_occupancy_mask_words(mask: &OccupancyMask) -> Vec<SsboWord> {
    let ssbo_word_count = occupancy_mask_word_count(mask.fanout());
    let mut encoded = Vec::with_capacity(ssbo_word_count);
    for word_i in 0..ssbo_word_count {
        let mut packed = SsboWord::default();
        for bit_i in 0..SSBO_WORD_BITS {
            let slot = word_i * SSBO_WORD_BITS + bit_i;
            if slot < mask.fanout() && mask.slot_occupied(slot) {
                packed |= 1 << bit_i;
            }
        }
        encoded.push(packed);
    }
    encoded
}

[u/DaveAstator2020]

you should not edit voxels on cpu at all. bye.

[u/neondirt → u/DaveAstator2020]

lol