use crate::{Composer, Error, Result, read_buffer_u32};
const BLOCK: u32 = 256;
#[derive(Debug)]
struct Level {
blocks: u32,
out: wgpu::Buffer,
sums: wgpu::Buffer,
params: wgpu::Buffer,
}
#[derive(Debug)]
pub struct DeferredScan {
pub offsets: wgpu::Buffer,
pub total: wgpu::Buffer,
pub levels: usize,
}
#[derive(Debug)]
pub struct ScanOutput {
pub offsets: wgpu::Buffer,
pub total: u32,
pub levels: usize,
}
#[derive(Debug)]
pub struct PrefixScan {
scan: wgpu::ComputePipeline,
add: wgpu::ComputePipeline,
draw_args: wgpu::ComputePipeline,
layout: wgpu::BindGroupLayout,
}
impl PrefixScan {
pub const BLOCK: u32 = BLOCK;
pub fn new(device: &wgpu::Device) -> Result<Self> {
let source = Composer::with_builtins().compose("scan", &[])?;
let module = device.create_shader_module(wgpu::ShaderModuleDescriptor {
label: Some("isomesh prefix scan"),
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 prefix scan bindings"),
entries: &[
entry(0, wgpu::BufferBindingType::Uniform),
entry(1, read),
entry(2, write),
entry(3, write),
],
});
let pipeline_layout = device.create_pipeline_layout(&wgpu::PipelineLayoutDescriptor {
label: Some("isomesh prefix scan 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 {
scan: compile("scan_blocks"),
add: compile("add_block_offsets"),
draw_args: compile("write_draw_args"),
layout,
})
}
pub fn scan(
&self,
device: &wgpu::Device,
queue: &wgpu::Queue,
counts: &wgpu::Buffer,
n: u32,
) -> Result<ScanOutput> {
let deferred = self.scan_deferred(device, queue, counts, n)?;
let total = read_buffer_u32(device, queue, &deferred.total, 4)?
.first()
.copied()
.ok_or(Error::MapFailed)?;
Ok(ScanOutput {
offsets: deferred.offsets,
total,
levels: deferred.levels,
})
}
pub fn scan_deferred(
&self,
device: &wgpu::Device,
queue: &wgpu::Queue,
counts: &wgpu::Buffer,
n: u32,
) -> Result<DeferredScan> {
if n == 0 {
let placeholder = |label: &str| {
device.create_buffer(&wgpu::BufferDescriptor {
label: Some(label),
size: 4,
usage: wgpu::BufferUsages::STORAGE
| wgpu::BufferUsages::COPY_SRC
| wgpu::BufferUsages::COPY_DST,
mapped_at_creation: false,
})
};
let offsets = placeholder("isomesh scan output (empty)");
let total = placeholder("isomesh scan total (empty)");
queue.write_buffer(&total, 0, &[0u8; 4]);
return Ok(DeferredScan {
offsets,
total,
levels: 0,
});
}
let limit = device.limits().max_compute_workgroups_per_dimension;
if n.div_ceil(BLOCK) > limit {
return Err(Error::ScanTooLong {
elements: n,
max: limit.saturating_mul(BLOCK),
});
}
let mut sizes = Vec::new();
let mut at = n;
loop {
let blocks = at.div_ceil(BLOCK);
sizes.push((at, blocks));
if blocks <= 1 {
break;
}
at = blocks;
}
let levels: Vec<Level> = sizes
.iter()
.map(|&(n, blocks)| {
let storage = |label: &str, elements: u32| {
device.create_buffer(&wgpu::BufferDescriptor {
label: Some(label),
size: u64::from(elements.max(1)) * 4,
usage: wgpu::BufferUsages::STORAGE
| wgpu::BufferUsages::COPY_SRC
| wgpu::BufferUsages::COPY_DST,
mapped_at_creation: false,
})
};
let params = device.create_buffer(&wgpu::BufferDescriptor {
label: Some("isomesh scan params"),
size: 16,
usage: wgpu::BufferUsages::UNIFORM | wgpu::BufferUsages::COPY_DST,
mapped_at_creation: false,
});
let mut bytes = [0u8; 16];
bytes[..4].copy_from_slice(&n.to_le_bytes());
queue.write_buffer(¶ms, 0, &bytes);
Level {
blocks,
out: storage("isomesh scan output", n),
sums: storage("isomesh scan block sums", blocks),
params,
}
})
.collect();
for (index, level) in levels.iter().enumerate() {
let input = if index == 0 {
counts
} else {
&levels[index - 1].sums
};
self.dispatch(
device,
queue,
&self.scan,
level,
input,
&level.out,
&level.sums,
);
}
for index in (0..levels.len().saturating_sub(1)).rev() {
let level = &levels[index];
self.dispatch(
device,
queue,
&self.add,
level,
&level.sums,
&level.out,
&levels[index + 1].out,
);
}
let mut levels = levels;
let deepest = levels.pop().expect("the loop pushes at least one level");
let total = deepest.sums;
let offsets = match levels.into_iter().next() {
Some(first) => first.out,
None => deepest.out,
};
Ok(DeferredScan {
offsets,
total,
levels: sizes.len(),
})
}
#[allow(clippy::too_many_arguments)]
pub fn write_draw_args(
&self,
device: &wgpu::Device,
queue: &wgpu::Queue,
total: &wgpu::Buffer,
indirect: &wgpu::Buffer,
draw_params: &wgpu::Buffer,
batch: u32,
budget: u32,
) {
let params = device.create_buffer(&wgpu::BufferDescriptor {
label: Some("isomesh draw args params"),
size: 16,
usage: wgpu::BufferUsages::UNIFORM | wgpu::BufferUsages::COPY_DST,
mapped_at_creation: false,
});
let mut bytes = [0u8; 16];
bytes[..4].copy_from_slice(&batch.to_le_bytes());
bytes[4..8].copy_from_slice(&budget.to_le_bytes());
queue.write_buffer(¶ms, 0, &bytes);
let level = Level {
blocks: 1,
out: indirect.clone(),
sums: draw_params.clone(),
params,
};
self.dispatch(
device,
queue,
&self.draw_args,
&level,
total,
indirect,
draw_params,
);
}
#[allow(clippy::too_many_arguments)]
fn dispatch(
&self,
device: &wgpu::Device,
queue: &wgpu::Queue,
pipeline: &wgpu::ComputePipeline,
level: &Level,
input: &wgpu::Buffer,
output: &wgpu::Buffer,
block_sums: &wgpu::Buffer,
) {
fn entry(binding: u32, buffer: &wgpu::Buffer) -> wgpu::BindGroupEntry<'_> {
wgpu::BindGroupEntry {
binding,
resource: buffer.as_entire_binding(),
}
}
let bind_group = device.create_bind_group(&wgpu::BindGroupDescriptor {
label: Some("isomesh prefix scan"),
layout: &self.layout,
entries: &[
entry(0, &level.params),
entry(1, input),
entry(2, output),
entry(3, block_sums),
],
});
let mut encoder = device.create_command_encoder(&wgpu::CommandEncoderDescriptor {
label: Some("isomesh prefix scan"),
});
{
let mut pass = encoder.begin_compute_pass(&wgpu::ComputePassDescriptor {
label: Some("isomesh prefix scan"),
timestamp_writes: None,
});
pass.set_pipeline(pipeline);
pass.set_bind_group(0, &bind_group, &[]);
pass.dispatch_workgroups(level.blocks, 1, 1);
}
queue.submit(Some(encoder.finish()));
}
}
#[must_use]
pub fn cpu_prefix_sum(counts: &[u32]) -> (Vec<u32>, u32) {
let mut running = 0u32;
let mut offsets = Vec::with_capacity(counts.len());
for n in counts {
offsets.push(running);
running = running.wrapping_add(*n);
}
(offsets, running)
}
#[cfg(test)]
mod tests;