// 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;
}
}
}