isomesh-gpu 0.0.6

GPU isosurface extraction for isomesh: wgpu buffers and pipelines, no engine types.
Documentation
//! Jump flooding: a distance field in `O(log n)` passes, on the GPU.
//!
//! Ticket: S-005. Rong & Tan, *Jump flooding in GPU with applications to Voronoi
//! diagram and distance transform*, I3D 2006 (`10.1145/1111411.1111431`).
//!
//! # What it is, and what "approximate" costs here
//!
//! Every sample carries the nearest surface point it has heard about. The seed
//! pass puts a crossing on each sample adjacent to a sign change; then
//! `⌈log₂ n⌉` passes let each sample look at 26 neighbours a halving stride
//! away and adopt the better seed. `n/2, n/4, … 1` — so a 65³ grid is six
//! dispatches rather than the 65 a naive propagation would need.
//!
//! **It is not exact, and the word is a measurement here rather than an
//! adjective.** A sample only ever sees seeds sitting at one of 27 fixed offsets
//! at each stride, so a Voronoi region whose owner never lands on that lattice
//! is missed.
//!
//! # What the measurement actually found (M-257)
//!
//! The approximate GPU method is **more accurate than both exact CPU
//! constructors**, on every one of the twelve rows — four exact reference fields
//! at 17³, 33³ and 65³. Worst error against the analytic field:
//!
//! | field | n | jump flood | swept (S-002) | exact transform (S-001) |
//! |---|---|---|---|---|
//! | `sphere` | 65 | **0.02048** | 0.09271 | 0.06250 |
//! | `torus` | 65 | **0.02370** | 0.10527 | 0.06233 |
//! | `box_exact` | 65 | **0.08839** | 0.15861 | 0.10825 |
//! | `thin_plate` | 65 | **0.06250** | 0.19221 | 0.08927 |
//!
//! Full table: `docs/measurements/jump_flood.csv`, regenerated by
//! `cargo test -p isomesh-gpu jump_flood -- --nocapture`.
//!
//! That is not a paradox. "Exact" in S-001 means exact to the nearest *sample*,
//! which quantises every distance to the grid; the sweep is exact in the limit
//! but its Godunov update is first-order. The flood is seeded sub-cell and then
//! measures a true Euclidean distance to that seed, so on these fields the
//! seeding buys more than the lattice restriction costs.
//!
//! **This makes "error against S-001" the wrong assertion**, and it was written
//! twice before that was clear. Asserting the flood agrees with a CPU
//! constructor asserts it reproduce that constructor's error: `thin_plate` at
//! 17³ misses a half-cell agreement bound at 0.523 cells while being the most
//! accurate of the three. The gate is against the analytic field.
//!
//! # Seeded from the crossing, not from the sample
//!
//! The textbook seeds each boundary sample with **its own position**, which
//! quantises every distance to the grid and floors the error at half a cell.
//! That would make any comparison against S-001 a comparison of seedings. This
//! seeds the linearly interpolated crossing on each cut edge — the same sub-cell
//! information the CPU's swept and marched constructors use — so what the
//! comparison isolates is the flood's own approximation.
//!
//! ```no_run
//! use isomesh::fields::Sphere;
//! use isomesh_gpu::{FieldBuffer, GridParams, JumpFlood, headless};
//!
//! # fn main() -> Result<(), Box<dyn std::error::Error>> {
//! let gpu = headless::Gpu::new()?;
//! let grid = GridParams::new([65; 3], [-2.0; 3], 0.0625)?;
//! let field = FieldBuffer::sampled(gpu.device(), gpu.queue(), grid, &Sphere::<f32>::canonical())?;
//!
//! let flood = JumpFlood::new(gpu.device())?;
//! let distance = flood.build(gpu.device(), gpu.queue(), &field)?;
//! # let _ = distance;
//! # Ok(())
//! # }
//! ```

#[cfg(test)]
mod tests;

use crate::{Composer, Error, FieldBuffer, GridParams, Result, read_buffer};

/// Threads per workgroup. Must match `WORKGROUP` in `jump_flood.wgsl`.
const WORKGROUP: u32 = 64;

/// Bytes per seed entry: `vec4<f32>`.
const SEED_STRIDE: u64 = 16;

/// The three kernels and the layout they share.
#[derive(Debug)]
pub struct JumpFlood {
    seed: wgpu::ComputePipeline,
    flood: wgpu::ComputePipeline,
    resolve: wgpu::ComputePipeline,
    layout: wgpu::BindGroupLayout,
}

impl JumpFlood {
    /// Compile the kernels.
    ///
    /// # Errors
    ///
    /// [`Error::ShaderModuleMissing`] or [`Error::ShaderDirective`] if the
    /// composition fails, which means this crate's own shaders are broken rather
    /// than anything the caller did.
    pub fn new(device: &wgpu::Device) -> Result<Self> {
        let source = Composer::with_builtins().compose("jump_flood", &[])?;
        let module = device.create_shader_module(wgpu::ShaderModuleDescriptor {
            label: Some("isomesh jump flood"),
            source: wgpu::ShaderSource::Wgsl(source.into()),
        });

        let entry = |binding: u32, ty: wgpu::BufferBindingType| wgpu::BindGroupLayoutEntry {
            binding,
            visibility: wgpu::ShaderStages::COMPUTE,
            ty: wgpu::BindingType::Buffer {
                ty,
                has_dynamic_offset: false,
                min_binding_size: None,
            },
            count: None,
        };
        let read = wgpu::BufferBindingType::Storage { read_only: true };
        let write = wgpu::BufferBindingType::Storage { read_only: false };
        let layout = device.create_bind_group_layout(&wgpu::BindGroupLayoutDescriptor {
            label: Some("isomesh jump flood bindings"),
            entries: &[
                entry(0, wgpu::BufferBindingType::Uniform),
                entry(1, wgpu::BufferBindingType::Uniform),
                entry(2, read),
                entry(3, write),
                entry(4, write),
                entry(5, write),
            ],
        });
        let pipeline_layout = device.create_pipeline_layout(&wgpu::PipelineLayoutDescriptor {
            label: Some("isomesh jump flood layout"),
            bind_group_layouts: &[Some(&layout)],
            immediate_size: 0,
        });
        let compile = |entry_point: &str| {
            device.create_compute_pipeline(&wgpu::ComputePipelineDescriptor {
                label: Some(entry_point),
                layout: Some(&pipeline_layout),
                module: &module,
                entry_point: Some(entry_point),
                compilation_options: wgpu::PipelineCompilationOptions::default(),
                cache: None,
            })
        };

        Ok(Self {
            seed: compile("seed"),
            flood: compile("flood"),
            resolve: compile("resolve"),
            layout,
        })
    }

    /// The strides a grid of this size needs, largest first.
    ///
    /// `n/2, n/4, … 1` where `n` is the longest axis. Rong & Tan's ordering; the
    /// reverse ("1+JFA") trades a pass for accuracy and is not what this is.
    #[must_use]
    pub fn strides(params: GridParams) -> Vec<u32> {
        let s = params.samples();
        let longest = s[0].max(s[1]).max(s[2]);
        let mut out = Vec::new();
        let mut k = longest / 2;
        while k >= 1 {
            out.push(k);
            k /= 2;
        }
        out
    }

    /// Build a signed distance field from `field`'s signs, reading it back.
    ///
    /// # Errors
    ///
    /// [`Error::MapFailed`] or [`Error::DeviceLost`] if the read-back fails.
    pub fn build(
        &self,
        device: &wgpu::Device,
        queue: &wgpu::Queue,
        field: &FieldBuffer,
    ) -> Result<Vec<f32>> {
        let params = field.params();
        let count = params.sample_count();
        if count == 0 {
            return Err(Error::DegenerateGrid {
                samples: params.samples(),
            });
        }

        let grid_uniform = device.create_buffer(&wgpu::BufferDescriptor {
            label: Some("isomesh jump flood grid"),
            size: GridParams::UNIFORM_SIZE,
            usage: wgpu::BufferUsages::UNIFORM | wgpu::BufferUsages::COPY_DST,
            mapped_at_creation: false,
        });
        queue.write_buffer(&grid_uniform, 0, &params.to_std140());

        // **One uniform per step, not one rewritten between dispatches.** A
        // `write_buffer` is ordered against the queue, not against dispatches
        // already recorded in an encoder, so reusing a single buffer would give
        // every pass whichever stride was written last.
        let strides = Self::strides(params);
        let mut step_uniforms = Vec::with_capacity(strides.len() + 1);
        for &k in core::iter::once(&0u32).chain(strides.iter()) {
            let buf = device.create_buffer(&wgpu::BufferDescriptor {
                label: Some("isomesh jump flood step"),
                size: 16,
                usage: wgpu::BufferUsages::UNIFORM | wgpu::BufferUsages::COPY_DST,
                mapped_at_creation: false,
            });
            let mut bytes = [0u8; 16];
            bytes[..4].copy_from_slice(&k.to_le_bytes());
            queue.write_buffer(&buf, 0, &bytes);
            step_uniforms.push(buf);
        }

        let seeds = |label: &str| {
            device.create_buffer(&wgpu::BufferDescriptor {
                label: Some(label),
                size: count * SEED_STRIDE,
                usage: wgpu::BufferUsages::STORAGE,
                mapped_at_creation: false,
            })
        };
        let ping = seeds("isomesh jump flood seeds A");
        let pong = seeds("isomesh jump flood seeds B");
        let out = device.create_buffer(&wgpu::BufferDescriptor {
            label: Some("isomesh jump flood distance"),
            size: count * 4,
            usage: wgpu::BufferUsages::STORAGE | wgpu::BufferUsages::COPY_SRC,
            mapped_at_creation: false,
        });

        let bind = |step: &wgpu::Buffer, src: &wgpu::Buffer, dst: &wgpu::Buffer| {
            device.create_bind_group(&wgpu::BindGroupDescriptor {
                label: Some("isomesh jump flood bindings"),
                layout: &self.layout,
                entries: &[
                    wgpu::BindGroupEntry {
                        binding: 0,
                        resource: grid_uniform.as_entire_binding(),
                    },
                    wgpu::BindGroupEntry {
                        binding: 1,
                        resource: step.as_entire_binding(),
                    },
                    wgpu::BindGroupEntry {
                        binding: 2,
                        resource: field.buffer().as_entire_binding(),
                    },
                    wgpu::BindGroupEntry {
                        binding: 3,
                        resource: src.as_entire_binding(),
                    },
                    wgpu::BindGroupEntry {
                        binding: 4,
                        resource: dst.as_entire_binding(),
                    },
                    wgpu::BindGroupEntry {
                        binding: 5,
                        resource: out.as_entire_binding(),
                    },
                ],
            })
        };

        let groups = count.div_ceil(u64::from(WORKGROUP)) as u32;
        let mut encoder =
            device.create_command_encoder(&wgpu::CommandEncoderDescriptor { label: None });

        // Seeding writes into `dst`, so after it the live buffer is `pong`.
        let mut live_is_pong = true;
        {
            let group = bind(&step_uniforms[0], &ping, &pong);
            let mut pass = encoder.begin_compute_pass(&wgpu::ComputePassDescriptor {
                label: Some("isomesh jump flood seed"),
                timestamp_writes: None,
            });
            pass.set_pipeline(&self.seed);
            pass.set_bind_group(0, &group, &[]);
            pass.dispatch_workgroups(groups, 1, 1);
        }

        for (i, _) in strides.iter().enumerate() {
            let (src, dst) = if live_is_pong {
                (&pong, &ping)
            } else {
                (&ping, &pong)
            };
            let group = bind(&step_uniforms[i + 1], src, dst);
            let mut pass = encoder.begin_compute_pass(&wgpu::ComputePassDescriptor {
                label: Some("isomesh jump flood"),
                timestamp_writes: None,
            });
            pass.set_pipeline(&self.flood);
            pass.set_bind_group(0, &group, &[]);
            pass.dispatch_workgroups(groups, 1, 1);
            live_is_pong = !live_is_pong;
        }

        {
            let live = if live_is_pong { &pong } else { &ping };
            let other = if live_is_pong { &ping } else { &pong };
            let group = bind(&step_uniforms[0], live, other);
            let mut pass = encoder.begin_compute_pass(&wgpu::ComputePassDescriptor {
                label: Some("isomesh jump flood resolve"),
                timestamp_writes: None,
            });
            pass.set_pipeline(&self.resolve);
            pass.set_bind_group(0, &group, &[]);
            pass.dispatch_workgroups(groups, 1, 1);
        }

        queue.submit(Some(encoder.finish()));
        read_buffer(device, queue, &out, count * 4)
    }
}