Skip to main content

isomesh_gpu/
scan.rs

1//! Exclusive prefix sum on the GPU, so the counts never come home.
2//!
3//! # What this replaces, and what it is worth
4//!
5//! Before this, extraction did: count pass → **read every per-cell count back**
6//! → prefix-sum on the CPU → upload the offsets → emit pass. M-149 measured the
7//! two CPU-side stages at **3.28 ms and 1.97 ms of a 15.03 ms** run at 129³ —
8//! 35% of the whole GPU path — and the read-back alone moves **4 bytes per
9//! cell**, which is 8 MB at that size, purely to add the numbers up.
10//!
11//! With the scan here the CPU needs **four bytes**: the grand total, to size the
12//! output buffer. That last read-back disappears too once the emit pass is
13//! dispatched indirectly and the geometry buffer is sized without it, which is
14//! GPU-010b.
15//!
16//! **Measured (M-150):** the two stages it replaces were `5.24 ms` at 129³ and
17//! the scan is `0.37 ms` — **14× faster** — taking the whole GPU path from
18//! `15.01` to `9.65 ms` and from `1.27×` to `1.95×` ahead of a single-threaded
19//! CPU. It is a small *loss* below about 25³, where two extra dispatches cost
20//! more than adding four thousand numbers up on the CPU.
21//!
22//! # The shape of it
23//!
24//! Hierarchical, with the level loop on the CPU because the depth depends on the
25//! cell count — three levels at 129³, one below 256 cells:
26//!
27//! 1. Each workgroup scans its own block of [`PrefixScan::BLOCK`] elements and
28//!    publishes the
29//!    block's total.
30//! 2. The block totals are themselves scanned, one level up, until a level fits
31//!    in a single workgroup.
32//! 3. Each level then adds its parent's exclusive scan back down.
33//!
34//! The grand total falls out for free: the deepest level has exactly one block,
35//! so its single published total is the sum of everything below it.
36
37use crate::{Composer, Error, Result, read_buffer_u32};
38
39/// Elements one workgroup scans. Must match `BLOCK` and `@workgroup_size` in
40/// `scan.wgsl`.
41const BLOCK: u32 = 256;
42
43/// One level of the hierarchy: the elements it scans and where it puts them.
44#[derive(Debug)]
45struct Level {
46    /// Workgroups, i.e. blocks, i.e. how many totals this level publishes.
47    ///
48    /// The element count it came from lives only in [`Level::params`], because
49    /// that is the copy the shader reads — keeping a second one in Rust would
50    /// be two numbers that must agree and one place for them to stop agreeing.
51    blocks: u32,
52    /// This level's exclusive scan, `n` elements.
53    out: wgpu::Buffer,
54    /// Per-block totals, `blocks` elements. Scanned by the level above.
55    sums: wgpu::Buffer,
56    /// `n`, as the shader's uniform.
57    params: wgpu::Buffer,
58}
59
60/// A scan whose total is still on the GPU.
61///
62/// The zero-synchronisation form: nothing is read back, so the CPU never waits
63/// for the dispatches to finish and the caller can keep recording. The price is
64/// that the caller does not know how many triangles there will be, which is what
65/// [`MarchingCubesGpu::extract_indirect`](crate::MarchingCubesGpu::extract_indirect)
66/// solves with a budget.
67#[derive(Debug)]
68pub struct DeferredScan {
69    /// The exclusive prefix sum, one `u32` per input element.
70    pub offsets: wgpu::Buffer,
71    /// A one-element buffer holding the sum of every input element.
72    pub total: wgpu::Buffer,
73    /// Levels the hierarchy needed. Zero when there was nothing to scan.
74    pub levels: usize,
75}
76
77/// What a scan produced.
78#[derive(Debug)]
79pub struct ScanOutput {
80    /// The exclusive prefix sum, one `u32` per input element.
81    pub offsets: wgpu::Buffer,
82    /// The sum of every input element.
83    pub total: u32,
84    /// Levels the hierarchy needed. One below [`PrefixScan::BLOCK`] elements,
85    /// three at 129³, zero when there was nothing to scan.
86    ///
87    /// Exposed because a test that does not know the depth cannot tell a
88    /// single-level scan from a multi-level one, and the multi-level path is
89    /// the one with a cross-block bug to have.
90    pub levels: usize,
91}
92
93/// The compiled scan pipelines.
94#[derive(Debug)]
95pub struct PrefixScan {
96    scan: wgpu::ComputePipeline,
97    add: wgpu::ComputePipeline,
98    draw_args: wgpu::ComputePipeline,
99    layout: wgpu::BindGroupLayout,
100}
101
102impl PrefixScan {
103    /// Elements one workgroup scans.
104    pub const BLOCK: u32 = BLOCK;
105
106    /// Compile both entry points.
107    ///
108    /// # Errors
109    ///
110    /// Propagates composition failure, which would mean this crate's own
111    /// shaders are inconsistent.
112    pub fn new(device: &wgpu::Device) -> Result<Self> {
113        let source = Composer::with_builtins().compose("scan", &[])?;
114        let module = device.create_shader_module(wgpu::ShaderModuleDescriptor {
115            label: Some("isomesh prefix scan"),
116            source: wgpu::ShaderSource::Wgsl(source.into()),
117        });
118
119        let entry = |binding: u32, ty: wgpu::BufferBindingType| wgpu::BindGroupLayoutEntry {
120            binding,
121            visibility: wgpu::ShaderStages::COMPUTE,
122            ty: wgpu::BindingType::Buffer {
123                ty,
124                has_dynamic_offset: false,
125                min_binding_size: None,
126            },
127            count: None,
128        };
129        let read = wgpu::BufferBindingType::Storage { read_only: true };
130        let write = wgpu::BufferBindingType::Storage { read_only: false };
131        let layout = device.create_bind_group_layout(&wgpu::BindGroupLayoutDescriptor {
132            label: Some("isomesh prefix scan bindings"),
133            entries: &[
134                entry(0, wgpu::BufferBindingType::Uniform),
135                entry(1, read),
136                entry(2, write),
137                entry(3, write),
138            ],
139        });
140        let pipeline_layout = device.create_pipeline_layout(&wgpu::PipelineLayoutDescriptor {
141            label: Some("isomesh prefix scan layout"),
142            bind_group_layouts: &[Some(&layout)],
143            immediate_size: 0,
144        });
145        let compile = |entry_point: &str| {
146            device.create_compute_pipeline(&wgpu::ComputePipelineDescriptor {
147                label: Some(entry_point),
148                layout: Some(&pipeline_layout),
149                module: &module,
150                entry_point: Some(entry_point),
151                compilation_options: wgpu::PipelineCompilationOptions::default(),
152                cache: None,
153            })
154        };
155
156        Ok(Self {
157            scan: compile("scan_blocks"),
158            add: compile("add_block_offsets"),
159            draw_args: compile("write_draw_args"),
160            layout,
161        })
162    }
163
164    /// Exclusive prefix sum of the first `n` `u32`s in `counts`.
165    ///
166    /// `counts` needs `STORAGE`. The returned `offsets` buffer carries
167    /// `STORAGE | COPY_SRC`, so it can be bound to the emit pass or read back
168    /// for comparison.
169    ///
170    /// Blocks once, for four bytes: the grand total, which the caller needs to
171    /// size whatever the scan is feeding.
172    ///
173    /// # Errors
174    ///
175    /// Anything the four-byte read-back can report, and
176    /// [`Error::ScanTooLong`] from the dispatch bound `scan_deferred` checks.
177    pub fn scan(
178        &self,
179        device: &wgpu::Device,
180        queue: &wgpu::Queue,
181        counts: &wgpu::Buffer,
182        n: u32,
183    ) -> Result<ScanOutput> {
184        let deferred = self.scan_deferred(device, queue, counts, n)?;
185        // The four bytes. Measured at 0.033 ms on their own, and the `poll(Wait)`
186        // around them also waits for every dispatch queued before -- 0.375 ms at
187        // 129³ (M-159). `scan_deferred` is the form that skips both.
188        //
189        // Four bytes in means one word out; a short read would be a failed
190        // read-back, not a zero total.
191        let total = read_buffer_u32(device, queue, &deferred.total, 4)?
192            .first()
193            .copied()
194            .ok_or(Error::MapFailed)?;
195        Ok(ScanOutput {
196            offsets: deferred.offsets,
197            total,
198            levels: deferred.levels,
199        })
200    }
201
202    /// The same scan, leaving the total in GPU memory.
203    ///
204    /// Nothing is read back and nothing is waited on, so the caller can carry on
205    /// recording work. Pair it with
206    /// [`write_draw_args`](Self::write_draw_args) to turn the total into a draw
207    /// the GPU issues to itself.
208    ///
209    /// `n = 0` is the empty scan: `total` holds zero, `offsets` is a 4-byte
210    /// placeholder nothing will read, and no dispatch is recorded.
211    ///
212    /// # Errors
213    ///
214    /// [`Error::ScanTooLong`] if level 0 needs more workgroups than the device
215    /// dispatches per dimension. Checked here rather than trusted, because the
216    /// symptom of not checking is a wgpu validation panic instead of a named
217    /// error.
218    pub fn scan_deferred(
219        &self,
220        device: &wgpu::Device,
221        queue: &wgpu::Queue,
222        counts: &wgpu::Buffer,
223        n: u32,
224    ) -> Result<DeferredScan> {
225        if n == 0 {
226            // Zero elements have a zero total and no offsets -- the answer
227            // `cpu_prefix_sum(&[])` gives. Written rather than dispatched,
228            // because a dispatch would read `counts[0]`, an element the caller
229            // said does not exist, and report whatever stale word it holds.
230            let placeholder = |label: &str| {
231                device.create_buffer(&wgpu::BufferDescriptor {
232                    label: Some(label),
233                    size: 4,
234                    usage: wgpu::BufferUsages::STORAGE
235                        | wgpu::BufferUsages::COPY_SRC
236                        | wgpu::BufferUsages::COPY_DST,
237                    mapped_at_creation: false,
238                })
239            };
240            let offsets = placeholder("isomesh scan output (empty)");
241            let total = placeholder("isomesh scan total (empty)");
242            queue.write_buffer(&total, 0, &[0u8; 4]);
243            return Ok(DeferredScan {
244                offsets,
245                total,
246                levels: 0,
247            });
248        }
249
250        // Level 0 is the widest dispatch: every level above scans the previous
251        // level's block totals, so block counts only shrink and bounding `n`
252        // bounds them all.
253        let limit = device.limits().max_compute_workgroups_per_dimension;
254        if n.div_ceil(BLOCK) > limit {
255            return Err(Error::ScanTooLong {
256                elements: n,
257                max: limit.saturating_mul(BLOCK),
258            });
259        }
260
261        // Sizes first, buffers second, dispatches third. Working out the whole
262        // hierarchy before allocating any of it keeps the borrow of the level
263        // below out of the loop that builds the level above.
264        let mut sizes = Vec::new();
265        let mut at = n;
266        loop {
267            let blocks = at.div_ceil(BLOCK);
268            sizes.push((at, blocks));
269            if blocks <= 1 {
270                break;
271            }
272            at = blocks;
273        }
274
275        let levels: Vec<Level> = sizes
276            .iter()
277            .map(|&(n, blocks)| {
278                let storage = |label: &str, elements: u32| {
279                    device.create_buffer(&wgpu::BufferDescriptor {
280                        label: Some(label),
281                        size: u64::from(elements.max(1)) * 4,
282                        usage: wgpu::BufferUsages::STORAGE
283                            | wgpu::BufferUsages::COPY_SRC
284                            | wgpu::BufferUsages::COPY_DST,
285                        mapped_at_creation: false,
286                    })
287                };
288                let params = device.create_buffer(&wgpu::BufferDescriptor {
289                    label: Some("isomesh scan params"),
290                    size: 16,
291                    usage: wgpu::BufferUsages::UNIFORM | wgpu::BufferUsages::COPY_DST,
292                    mapped_at_creation: false,
293                });
294                // One `u32`, padded to a 16-byte uniform binding.
295                let mut bytes = [0u8; 16];
296                bytes[..4].copy_from_slice(&n.to_le_bytes());
297                queue.write_buffer(&params, 0, &bytes);
298                Level {
299                    blocks,
300                    out: storage("isomesh scan output", n),
301                    sums: storage("isomesh scan block sums", blocks),
302                    params,
303                }
304            })
305            .collect();
306
307        // Up: scan each level, publishing block totals to the level above.
308        for (index, level) in levels.iter().enumerate() {
309            let input = if index == 0 {
310                counts
311            } else {
312                &levels[index - 1].sums
313            };
314            self.dispatch(
315                device,
316                queue,
317                &self.scan,
318                level,
319                input,
320                &level.out,
321                &level.sums,
322            );
323        }
324
325        // Down: add each parent's exclusive scan into its children's blocks.
326        // Skipped entirely when there is one level, because a single block's
327        // exclusive scan is already the answer.
328        for index in (0..levels.len().saturating_sub(1)).rev() {
329            let level = &levels[index];
330            self.dispatch(
331                device,
332                queue,
333                &self.add,
334                level,
335                &level.sums,
336                &level.out,
337                &levels[index + 1].out,
338            );
339        }
340
341        // The deepest level has exactly one block, so the single total it
342        // published is the sum of everything.
343        let mut levels = levels;
344        let deepest = levels.pop().expect("the loop pushes at least one level");
345        let total = deepest.sums;
346        // With one level the buffer just popped is also the first, so its own
347        // `out` is the answer. `Level` implements no `Drop`, so taking two
348        // fields out of it separately is a partial move rather than a clone.
349        let offsets = match levels.into_iter().next() {
350            Some(first) => first.out,
351            None => deepest.out,
352        };
353        Ok(DeferredScan {
354            offsets,
355            total,
356            levels: sizes.len(),
357        })
358    }
359
360    /// Turn a scanned total into a mesh-shader draw the GPU issues to itself.
361    ///
362    /// Writes `[ceil(drawn / batch), 1, 1]` into `indirect` for
363    /// `draw_mesh_tasks_indirect`, and `drawn` into `draw_params` for the
364    /// shader's own bound — where `drawn = min(total, budget)`, so the draw
365    /// stops where the emit pass stopped writing. Neither number is ever known
366    /// to the CPU; the un-clamped total stays in the scan's own buffer for the
367    /// caller who asks whether truncation happened.
368    ///
369    /// `indirect` needs `INDIRECT | STORAGE`; `draw_params` needs
370    /// `UNIFORM | STORAGE`.
371    #[allow(clippy::too_many_arguments)]
372    pub fn write_draw_args(
373        &self,
374        device: &wgpu::Device,
375        queue: &wgpu::Queue,
376        total: &wgpu::Buffer,
377        indirect: &wgpu::Buffer,
378        draw_params: &wgpu::Buffer,
379        batch: u32,
380        budget: u32,
381    ) {
382        // `params.n` carries the batch size for this entry point rather than an
383        // element count -- one uniform, two meanings, documented at both ends --
384        // and `params.budget` the triangle capacity of the geometry buffers.
385        let params = device.create_buffer(&wgpu::BufferDescriptor {
386            label: Some("isomesh draw args params"),
387            size: 16,
388            usage: wgpu::BufferUsages::UNIFORM | wgpu::BufferUsages::COPY_DST,
389            mapped_at_creation: false,
390        });
391        let mut bytes = [0u8; 16];
392        bytes[..4].copy_from_slice(&batch.to_le_bytes());
393        bytes[4..8].copy_from_slice(&budget.to_le_bytes());
394        queue.write_buffer(&params, 0, &bytes);
395
396        let level = Level {
397            blocks: 1,
398            out: indirect.clone(),
399            sums: draw_params.clone(),
400            params,
401        };
402        self.dispatch(
403            device,
404            queue,
405            &self.draw_args,
406            &level,
407            total,
408            indirect,
409            draw_params,
410        );
411    }
412
413    #[allow(clippy::too_many_arguments)]
414    fn dispatch(
415        &self,
416        device: &wgpu::Device,
417        queue: &wgpu::Queue,
418        pipeline: &wgpu::ComputePipeline,
419        level: &Level,
420        input: &wgpu::Buffer,
421        output: &wgpu::Buffer,
422        block_sums: &wgpu::Buffer,
423    ) {
424        fn entry(binding: u32, buffer: &wgpu::Buffer) -> wgpu::BindGroupEntry<'_> {
425            wgpu::BindGroupEntry {
426                binding,
427                resource: buffer.as_entire_binding(),
428            }
429        }
430        let bind_group = device.create_bind_group(&wgpu::BindGroupDescriptor {
431            label: Some("isomesh prefix scan"),
432            layout: &self.layout,
433            entries: &[
434                entry(0, &level.params),
435                entry(1, input),
436                entry(2, output),
437                entry(3, block_sums),
438            ],
439        });
440        let mut encoder = device.create_command_encoder(&wgpu::CommandEncoderDescriptor {
441            label: Some("isomesh prefix scan"),
442        });
443        {
444            let mut pass = encoder.begin_compute_pass(&wgpu::ComputePassDescriptor {
445                label: Some("isomesh prefix scan"),
446                timestamp_writes: None,
447            });
448            pass.set_pipeline(pipeline);
449            pass.set_bind_group(0, &bind_group, &[]);
450            pass.dispatch_workgroups(level.blocks, 1, 1);
451        }
452        queue.submit(Some(encoder.finish()));
453    }
454}
455
456/// The exclusive prefix sum, on the CPU.
457///
458/// The reference the GPU scan is asserted against, and the implementation the
459/// extraction used before GPU-010a. Kept because a parallel scan that is subtly
460/// wrong produces a mesh that looks entirely plausible, so the comparison has to
461/// be against something obviously right rather than against a second clever
462/// implementation.
463#[must_use]
464pub fn cpu_prefix_sum(counts: &[u32]) -> (Vec<u32>, u32) {
465    let mut running = 0u32;
466    let mut offsets = Vec::with_capacity(counts.len());
467    for n in counts {
468        offsets.push(running);
469        running = running.wrapping_add(*n);
470    }
471    (offsets, running)
472}
473
474#[cfg(test)]
475mod tests;