isomesh-gpu 0.0.8

GPU isosurface extraction for isomesh: wgpu buffers and pipelines, no engine types.
Documentation
// Exclusive prefix sum over the per-cell triangle counts, on the GPU.
//
// This replaces the largest avoidable cost in the extraction path. M-149 broke
// a 129^3 run into upload 8.61 ms, CPU prefix sum 3.28, counts read-back 1.97,
// geometry read-back 1.04 -- and the middle two exist only because the scan was
// done on the CPU, which meant copying 4 bytes per cell (8 MB at 129^3) home to
// add them up. Scanning here leaves the CPU needing four bytes: the grand
// total, to size the output buffer.
//
// # The algorithm, and why this one
//
// A hierarchical scan: each workgroup scans its own block in workgroup memory
// and publishes the block's total; the block totals are themselves scanned, one
// level up, until a level fits in a single workgroup; then each level adds its
// parent's exclusive scan back down. The level loop lives on the CPU because
// the number of levels depends on the cell count -- three for 129^3.
//
// The in-block scan is Hillis-Steele. It does O(n log n) work where a Blelloch
// up-down sweep does O(n), and it is chosen anyway: n here is 256, the whole
// thing is in workgroup memory, and the correctness argument is one loop rather
// than two sweeps with a mid-point swap. The measured cost is what decides
// whether that was right -- see the acceptance in GPU-010a -- and a scan that
// is subtly wrong produces a mesh that looks entirely plausible, which is the
// failure this trades against.

// Elements scanned per workgroup. Must equal the `@workgroup_size` below and
// `PrefixScan::BLOCK` on the CPU side.
const BLOCK: u32 = 256u;

struct ScanParams {
    // Elements at this level. The last block is partial whenever this is not a
    // multiple of BLOCK, which is the usual case. `write_draw_args` reads it as
    // the draw's triangles-per-workgroup instead.
    n: u32,
    // `write_draw_args` only: triangles the geometry buffers were sized for.
    // The scan levels write zero here and never read it.
    budget: u32,
}

@group(0) @binding(0) var<uniform> params: ScanParams;
@group(0) @binding(1) var<storage, read> input: array<u32>;
@group(0) @binding(2) var<storage, read_write> output: array<u32>;
@group(0) @binding(3) var<storage, read_write> block_sums: array<u32>;

var<workgroup> temp: array<u32, BLOCK>;

// Scan one block, write its exclusive scan to `output`, its total to
// `block_sums[workgroup]`.
@compute @workgroup_size(256)
fn scan_blocks(
    @builtin(global_invocation_id) gid: vec3<u32>,
    @builtin(local_invocation_index) tid: u32,
    @builtin(workgroup_id) wg: vec3<u32>,
) {
    let i = gid.x;
    // Threads past the end contribute zero, which keeps the block total right
    // without a separate partial-block path.
    var value = 0u;
    if (i < params.n) {
        value = input[i];
    }
    temp[tid] = value;
    workgroupBarrier();

    // Hillis-Steele inclusive scan. The two barriers are not decoration: every
    // read of `temp[tid - offset]` must complete before any write of
    // `temp[tid]` in the same round, or a thread reads a value from the round
    // it is currently in. Both barriers sit in uniform control flow -- the loop
    // bound is uniform and the `if`s contain no barrier -- which WGSL requires.
    for (var offset = 1u; offset < BLOCK; offset = offset << 1u) {
        var addend = 0u;
        if (tid >= offset) {
            addend = temp[tid - offset];
        }
        workgroupBarrier();
        if (tid >= offset) {
            temp[tid] = temp[tid] + addend;
        }
        workgroupBarrier();
    }

    // Exclusive from inclusive: subtract this element's own contribution.
    if (i < params.n) {
        output[i] = temp[tid] - value;
    }
    // The last lane holds the inclusive total of the whole block, including the
    // zeros any out-of-range lanes contributed.
    if (tid == BLOCK - 1u) {
        block_sums[wg.x] = temp[tid];
    }
}

// Add the parent level's exclusive scan back into this level's blocks.
//
// `block_sums` here is the *scanned* totals, so block 0 adds zero and the rest
// add everything before them.
@compute @workgroup_size(256)
fn add_block_offsets(
    @builtin(global_invocation_id) gid: vec3<u32>,
    @builtin(workgroup_id) wg: vec3<u32>,
) {
    let i = gid.x;
    if (i >= params.n) {
        return;
    }
    output[i] = output[i] + block_sums[wg.x];
}

// Write a mesh-shader draw's arguments from the scanned total, so the CPU never
// has to learn it.
//
// `input[0]` is the grand total the deepest level published; `params.n` carries
// the mesh shader's triangles-per-workgroup. One invocation, because there are
// four numbers to write.
@compute @workgroup_size(1)
fn write_draw_args() {
    // The emit pass stopped writing at the buffers' capacity, so the draw must
    // stop there too: walking the full total over budget-sized buffers would
    // read past everything that was written. The un-clamped total stays where
    // it always was -- the scan's own buffer -- for the caller who asks
    // whether truncation happened.
    let drawn = min(input[0], params.budget);
    // [group_count_x, y, z] for `draw_mesh_tasks_indirect`.
    output[0] = (drawn + params.n - 1u) / params.n;
    output[1] = 1u;
    output[2] = 1u;
    // The draw's own uniform: how many triangles the last workgroup should stop
    // at. Written here rather than uploaded, which is the whole point.
    block_sums[0] = drawn;
}