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(¶ms, 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(¶ms, 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;