isomesh-gpu 0.0.6

GPU isosurface extraction for isomesh: wgpu buffers and pipelines, no engine types.
Documentation
// Marching Cubes, one thread per cell, in two passes.
//
// The case table is NOT transcribed here. It is uploaded from isomesh's own
// `marching_cubes::table::CASES`, which is itself derived by a const fn rather
// than copied from a paper. So the GPU runs the same 256 cases the CPU does,
// and CLAUDE.md rule 5 -- never guess a case table -- is satisfied by having no
// second copy to disagree with the first.
//
// Two passes because the output has to be dense and deterministic:
//
//   1. `count_cells`  -- classify every cell, write its triangle count.
//   2. (CPU prefix-sums the counts into offsets, and sizes the output.)
//   3. `emit_cells`   -- classify again, write triangles at this cell's offset.
//
// Classifying twice is cheaper than the alternative. An atomic bump allocator
// would need one pass, but the output order would then depend on which
// workgroup got there first, and a mesh whose vertex order changes run to run
// cannot be compared against anything -- including itself. Cell order is the
// CPU's order, so the two are lined up by construction.

#include <grid>

// Layout of the uploaded case table, mirroring `table::McCase`.
//
// 13 u32 per case: a header, then one word per triangle.
//   header    = count | (centroids << 8)
//   triangle  = a | (b << 8) | (c << 16)   -- corner codes
//
// A corner code below CENTROID_BASE is a cube edge; at or above it, code minus
// CENTROID_BASE is a cell-local cycle centroid.
const CASE_STRIDE: u32 = 13u;
const MAX_TRIANGLES: u32 = 12u;
const MAX_CENTROIDS: u32 = 3u;
const CENTROID_BASE: u32 = 12u;

@group(0) @binding(0) var<uniform> params: GridParams;
@group(0) @binding(1) var<storage, read> field: array<f32>;
@group(0) @binding(2) var<storage, read> cases: array<u32>;
@group(0) @binding(3) var<storage, read_write> counts: array<u32>;
@group(0) @binding(4) var<storage, read_write> positions: array<f32>;
@group(0) @binding(5) var<storage, read_write> normals: array<f32>;

// The two corners of each cube edge, lower first. Mirrors cube::EDGE_CORNERS,
// which is generated by walking axes x, y, z and, within each, the four corners
// whose bit for that axis is zero.
const EDGE_CORNERS = array<vec2<u32>, 12>(
    vec2<u32>(0u, 1u), vec2<u32>(2u, 3u), vec2<u32>(4u, 5u), vec2<u32>(6u, 7u),
    vec2<u32>(0u, 2u), vec2<u32>(1u, 3u), vec2<u32>(4u, 6u), vec2<u32>(5u, 7u),
    vec2<u32>(0u, 4u), vec2<u32>(1u, 5u), vec2<u32>(2u, 6u), vec2<u32>(3u, 7u),
);

// Corner c sits at (c&1, (c>>1)&1, (c>>2)&1) grid steps from the cell's base.
fn corner_offset(c: u32) -> vec3<u32> {
    return vec3<u32>(c & 1u, (c >> 1u) & 1u, (c >> 2u) & 1u);
}

fn sample_at(at: vec3<u32>) -> f32 {
    return field[grid_index(params, at)];
}

// A sample of exactly zero is OUTSIDE.
//
// Lengyel (2010 dissertation, ยง3.1.1): the choice must be made once and applied
// everywhere. Strict `< 0` also makes the interpolation below safe without an
// epsilon -- on a cut edge one endpoint is strictly negative and the other is
// >= 0, so a - b is strictly negative and can never be zero.
fn is_inside(v: f32) -> bool {
    return v < 0.0;
}

// Cells per axis, and the base sample index of a cell.
fn cell_count(g: GridParams) -> u32 {
    let c = grid_cells(g);
    return c.x * c.y * c.z;
}

fn cell_at(g: GridParams, flat: u32) -> vec3<u32> {
    let c = grid_cells(g);
    return vec3<u32>(flat % c.x, (flat / c.x) % c.y, flat / (c.x * c.y));
}

// The eight corner values of a cell, and its case index.
struct Cell {
    value: array<f32, 8>,
    case_index: u32,
}

fn read_cell(base: vec3<u32>) -> Cell {
    var cell: Cell;
    cell.case_index = 0u;
    for (var c = 0u; c < 8u; c = c + 1u) {
        let v = sample_at(base + corner_offset(c));
        cell.value[c] = v;
        if (is_inside(v)) {
            cell.case_index = cell.case_index | (1u << c);
        }
    }
    return cell;
}

fn case_header(case_index: u32) -> u32 {
    return cases[case_index * CASE_STRIDE];
}

fn case_triangle(case_index: u32, t: u32) -> vec3<u32> {
    let word = cases[case_index * CASE_STRIDE + 1u + t];
    return vec3<u32>(word & 0xffu, (word >> 8u) & 0xffu, (word >> 16u) & 0xffu);
}

// Where the surface crosses an edge: t = a / (a - b), the same expression
// cube::edge_crossing uses. Positions are the grid origin plus a multiple of the
// cell size, never an accumulated cursor -- see grid_position.
fn edge_position(cell: Cell, base: vec3<u32>, edge: u32) -> vec3<f32> {
    let ends = EDGE_CORNERS[edge];
    let a = cell.value[ends.x];
    let b = cell.value[ends.y];
    let t = a / (a - b);
    let pa = grid_position(params, base + corner_offset(ends.x));
    let pb = grid_position(params, base + corner_offset(ends.y));
    return pa + (pb - pa) * t;
}

// Trilinear read of the sample grid at a world position.
//
// Index clamped at the border. That is a boundary condition rather than a
// fallback: the gradient stencil below reaches one cell outside the grid at the
// outermost samples, and clamping is the defined answer there. The alternative,
// one-sided differences at the border, would be a second code path computing a
// different quantity for the same input.
fn sample_world(p: vec3<f32>) -> f32 {
    let last = grid_samples(params) - vec3<u32>(1u, 1u, 1u);
    let local = (p - params.placement.xyz) / params.placement.w;
    let clamped = clamp(local, vec3<f32>(0.0), vec3<f32>(last));
    let i0 = vec3<u32>(floor(clamped));
    let i1 = min(i0 + vec3<u32>(1u), last);
    let f = clamped - vec3<f32>(i0);

    let c000 = field[grid_index(params, vec3<u32>(i0.x, i0.y, i0.z))];
    let c100 = field[grid_index(params, vec3<u32>(i1.x, i0.y, i0.z))];
    let c010 = field[grid_index(params, vec3<u32>(i0.x, i1.y, i0.z))];
    let c110 = field[grid_index(params, vec3<u32>(i1.x, i1.y, i0.z))];
    let c001 = field[grid_index(params, vec3<u32>(i0.x, i0.y, i1.z))];
    let c101 = field[grid_index(params, vec3<u32>(i1.x, i0.y, i1.z))];
    let c011 = field[grid_index(params, vec3<u32>(i0.x, i1.y, i1.z))];
    let c111 = field[grid_index(params, vec3<u32>(i1.x, i1.y, i1.z))];

    let c00 = mix(c000, c100, f.x);
    let c10 = mix(c010, c110, f.x);
    let c01 = mix(c001, c101, f.x);
    let c11 = mix(c011, c111, f.x);
    return mix(mix(c00, c10, f.y), mix(c01, c11, f.y), f.z);
}

// The unit normal at a vertex, by central differences at the cell size.
//
// The CPU extractor calls Sdf::gradient, which the reference fields override
// analytically. A shader has only the uploaded samples, so this is the same
// quantity isomesh's `CentralDifference { step: h }` computes, and M-65 already
// measured the difference between the two: 0.460 deg worst and 0.299 deg mean
// at 17^3, converging at h^2. That is a documented divergence, not a defect.
//
// A zero-length gradient is returned as zero rather than normalised, because
// normalising it would divide by zero and inventing a direction there would be
// worse than reporting that there is none.
fn vertex_normal(p: vec3<f32>) -> vec3<f32> {
    let h = params.placement.w;
    let g = vec3<f32>(
        sample_world(p + vec3<f32>(h, 0.0, 0.0)) - sample_world(p - vec3<f32>(h, 0.0, 0.0)),
        sample_world(p + vec3<f32>(0.0, h, 0.0)) - sample_world(p - vec3<f32>(0.0, h, 0.0)),
        sample_world(p + vec3<f32>(0.0, 0.0, h)) - sample_world(p - vec3<f32>(0.0, 0.0, h)),
    );
    let len = length(g);
    if (len > 0.0) {
        return g / len;
    }
    return vec3<f32>(0.0, 0.0, 0.0);
}

@compute @workgroup_size(64)
fn count_cells(@builtin(global_invocation_id) id: vec3<u32>) {
    let flat = id.x;
    if (flat >= cell_count(params)) {
        return;
    }
    let cell = read_cell(cell_at(params, flat));
    counts[flat] = case_header(cell.case_index) & 0xffu;
}

@compute @workgroup_size(64)
fn emit_cells(@builtin(global_invocation_id) id: vec3<u32>) {
    let flat = id.x;
    if (flat >= cell_count(params)) {
        return;
    }
    let base = cell_at(params, flat);
    let cell = read_cell(base);
    let header = case_header(cell.case_index);
    let count = header & 0xffu;
    if (count == 0u) {
        return;
    }

    // Cycle centroids first: a triangle naming one needs every edge vertex of
    // that cycle averaged before it can be emitted. A cycle's edges are exactly
    // the `tri[1]` corners of the triangles naming it -- the same rule the CPU
    // extractor uses, so the two average the same points in the same order.
    let centroids = (header >> 8u) & 0xffu;
    var centroid: array<vec3<f32>, 3>;
    for (var c = 0u; c < centroids; c = c + 1u) {
        let code = CENTROID_BASE + c;
        var sum = vec3<f32>(0.0);
        var n = 0u;
        for (var t = 0u; t < count; t = t + 1u) {
            let tri = case_triangle(cell.case_index, t);
            if (tri.x == code) {
                sum = sum + edge_position(cell, base, tri.y);
                n = n + 1u;
            }
        }
        centroid[c] = sum / f32(n);
    }

    // `counts` holds exclusive prefix sums by now, so this cell's triangles go
    // at a slot nothing else writes and the output is dense with no atomics.
    //
    // The bound comes from `arrayLength` rather than a uniform: when the caller
    // sized the buffers from the scanned total there is nothing to clamp, and
    // when they sized them from a budget (the zero-read-back path) this is what
    // stops a write running off the end. A surface that exceeds the budget is
    // truncated, and the caller detects that by comparing the total against
    // their capacity -- explicitly, when they choose, rather than by this
    // shader deciding for them.
    let capacity = arrayLength(&positions) / 3u;
    var slot = counts[flat] * 3u;
    for (var t = 0u; t < count; t = t + 1u) {
        let tri = case_triangle(cell.case_index, t);
        let code = array<u32, 3>(tri.x, tri.y, tri.z);
        for (var k = 0u; k < 3u; k = k + 1u) {
            if (slot >= capacity) {
                return;
            }
            var p: vec3<f32>;
            if (code[k] >= CENTROID_BASE) {
                p = centroid[code[k] - CENTROID_BASE];
            } else {
                p = edge_position(cell, base, code[k]);
            }
            let n = vertex_normal(p);
            positions[slot * 3u + 0u] = p.x;
            positions[slot * 3u + 1u] = p.y;
            positions[slot * 3u + 2u] = p.z;
            normals[slot * 3u + 0u] = n.x;
            normals[slot * 3u + 1u] = n.y;
            normals[slot * 3u + 2u] = n.z;
            slot = slot + 1u;
        }
    }
}