use super::RayMesh;
use glam::Vec3;
#[repr(C)]
#[derive(Clone, Copy, bytemuck::Pod, bytemuck::Zeroable)]
struct Node {
min: [f32; 3],
escape: u32,
max: [f32; 3],
count: u32,
first: u32,
padding: [u32; 3],
}
const NODE_WORDS: usize = std::mem::size_of::<Node>() / 4;
pub(super) const LEAF_PRIMITIVES: usize = 4;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(super) enum Split {
SurfaceArea,
EqualCounts,
}
const SAH_BINS: usize = 16;
const MOST_SAH_DEPTH: usize = 64;
fn median(count: usize) -> Option<usize> {
(count > LEAF_PRIMITIVES).then_some(count / 2)
}
pub(super) fn words<T>(primitives: usize) -> usize {
fn nodes(primitives: usize) -> usize {
match median(primitives) {
Some(middle) => 1 + nodes(middle) + nodes(primitives - middle),
None => 1,
}
}
if primitives == 0 {
return 0;
}
nodes(primitives) * NODE_WORDS + primitives * std::mem::size_of::<T>() / 4
}
fn half_area(min: Vec3, max: Vec3) -> f32 {
let extent = (max - min).max(Vec3::ZERO);
extent.x * extent.y + extent.y * extent.z + extent.z * extent.x
}
#[derive(Clone, Copy)]
struct Bounds {
min: Vec3,
max: Vec3,
centroid_min: Vec3,
centroid_max: Vec3,
}
impl Bounds {
const EMPTY: Self = Self {
min: Vec3::INFINITY,
max: Vec3::NEG_INFINITY,
centroid_min: Vec3::INFINITY,
centroid_max: Vec3::NEG_INFINITY,
};
fn add<T>(&mut self, p: &Primitive<T>) {
self.min = self.min.min(p.min);
self.max = self.max.max(p.max);
self.centroid_min = self.centroid_min.min(p.centroid);
self.centroid_max = self.centroid_max.max(p.centroid);
}
fn of<T>(primitives: &[Primitive<T>]) -> Self {
let mut bounds = Self::EMPTY;
for p in primitives {
bounds.add(p);
}
bounds
}
}
type Halves = (usize, Bounds, Bounds);
fn split_median<T>(primitives: &mut [Primitive<T>], bounds: &Bounds) -> Option<Halves> {
let middle = median(primitives.len())?;
let axis = (bounds.max - bounds.min).max_position();
primitives.select_nth_unstable_by(middle, |a, b| a.centroid[axis].total_cmp(&b.centroid[axis]));
let (left, right) = primitives.split_at(middle);
Some((middle, Bounds::of(left), Bounds::of(right)))
}
fn split_surface_area<T>(primitives: &mut [Primitive<T>], bounds: &Bounds) -> Option<Halves> {
let count = primitives.len();
if count <= LEAF_PRIMITIVES {
return None;
}
let low = bounds.centroid_min;
let extent = bounds.centroid_max - low;
let scale = Vec3::select(
extent.cmpgt(Vec3::ZERO),
SAH_BINS as f32 / extent,
Vec3::ZERO,
);
let bin = |p: &Primitive<T>, axis: usize| {
(((p.centroid[axis] - low[axis]) * scale[axis]) as usize).min(SAH_BINS - 1)
};
let empty = (0, Vec3::INFINITY, Vec3::NEG_INFINITY);
let mut bins = [[empty; SAH_BINS]; 3];
for p in primitives.iter() {
for (axis, bins) in bins.iter_mut().enumerate() {
if scale[axis] > 0. {
let b = &mut bins[bin(p, axis)];
*b = (b.0 + 1, b.1.min(p.min), b.2.max(p.max));
}
}
}
let mut best: Option<(f32, usize, usize)> = None;
for axis in (0..3).filter(|&axis| scale[axis] > 0.) {
let bins = &bins[axis];
let mut left = [(0, 0.); SAH_BINS];
let mut sweep = empty;
for (at, b) in bins.iter().enumerate().take(SAH_BINS - 1) {
sweep = (sweep.0 + b.0, sweep.1.min(b.1), sweep.2.max(b.2));
left[at + 1] = (sweep.0, half_area(sweep.1, sweep.2));
}
let mut sweep = empty;
for at in (1..SAH_BINS).rev() {
let b = bins[at];
sweep = (sweep.0 + b.0, sweep.1.min(b.1), sweep.2.max(b.2));
let (left_count, left_area) = left[at];
if left_count == 0 || sweep.0 == 0 {
continue;
}
let cost = left_area * left_count as f32 + half_area(sweep.1, sweep.2) * sweep.0 as f32;
if best.is_none_or(|(least, ..)| cost < least) {
best = Some((cost, axis, at));
}
}
}
let Some((_, axis, first_right)) = best else {
return split_median(primitives, bounds);
};
let (mut left, mut right) = (Bounds::EMPTY, Bounds::EMPTY);
let mut middle = 0;
for at in 0..count {
let p = &primitives[at];
if bin(p, axis) < first_right {
left.add(p);
primitives.swap(middle, at);
middle += 1;
} else {
right.add(p);
}
}
Some((middle, left, right))
}
pub(super) fn rebase(words: &mut [u32], by: u32) {
let leaf_words = std::mem::size_of::<LeafPrimitive>() / 4;
let mut at = 0;
while at < words.len() {
let node: &mut Node =
bytemuck::from_bytes_mut(bytemuck::cast_slice_mut(&mut words[at..at + NODE_WORDS]));
node.escape += by;
let count = node.count as usize;
if count > 0 {
node.first += by;
}
at += NODE_WORDS + count * leaf_words;
}
}
#[repr(C)]
#[derive(Clone, Copy, bytemuck::Pod, bytemuck::Zeroable)]
struct LeafPrimitive {
mesh: u32,
triangle: u32,
}
pub(crate) struct Primitive<T> {
min: Vec3,
max: Vec3,
centroid: Vec3,
leaf: T,
}
impl<T> Primitive<T> {
pub fn new(min: Vec3, max: Vec3, leaf: T) -> Self {
Self {
min,
max,
centroid: min * 0.5 + max * 0.5,
leaf,
}
}
}
pub(super) fn append(meshes: &[RayMesh<'_>], words: &mut Vec<u32>, base: u32) -> u32 {
let mut primitives = Vec::new();
for (mesh_id, mesh) in meshes.iter().enumerate() {
for (triangle, indices) in mesh.indices.chunks_exact(3).enumerate() {
let p =
[0, 1, 2].map(|i| Vec3::from_array(mesh.vertices[indices[i] as usize].position));
primitives.push(Primitive::new(
p[0].min(p[1]).min(p[2]),
p[0].max(p[1]).max(p[2]),
LeafPrimitive {
mesh: mesh_id as u32,
triangle: triangle as u32,
},
));
}
}
append_primitives(&mut primitives, Split::SurfaceArea, words, base)
}
pub(super) fn append_primitives<T: bytemuck::Pod>(
primitives: &mut [Primitive<T>],
split: Split,
words: &mut Vec<u32>,
base: u32,
) -> u32 {
if primitives.is_empty() {
return 0;
}
let root = base + words.len() as u32;
build(primitives, &Bounds::of(primitives), split, 0, words, base);
root
}
fn build<T: bytemuck::Pod>(
primitives: &mut [Primitive<T>],
bounds: &Bounds,
split: Split,
depth: usize,
words: &mut Vec<u32>,
base: u32,
) {
let at = words.len();
words.resize(at + NODE_WORDS, 0);
let halves = match split {
Split::SurfaceArea if depth < MOST_SAH_DEPTH => split_surface_area(primitives, bounds),
_ => split_median(primitives, bounds),
};
let (count, first) = if let Some((middle, left_bounds, right_bounds)) = halves {
let (left, right) = primitives.split_at_mut(middle);
build(left, &left_bounds, split, depth + 1, words, base);
build(right, &right_bounds, split, depth + 1, words, base);
(0, 0)
} else {
let first = base + words.len() as u32;
for p in primitives.iter() {
words.extend_from_slice(bytemuck::cast_slice(&[p.leaf]));
}
(primitives.len() as u32, first)
};
let node = Node {
min: bounds.min.to_array().map(|v| v.next_down().max(f32::MIN)),
max: bounds.max.to_array().map(|v| v.next_up().min(f32::MAX)),
escape: base + words.len() as u32,
count,
first,
padding: [0; 3],
};
words[at..at + NODE_WORDS].copy_from_slice(bytemuck::cast_slice(&[node]));
}
#[cfg(test)]
pub(super) fn layout() -> [(&'static str, usize); 9] {
use std::mem::{offset_of, size_of};
[
("SCENE_BVH_NODE_WORDS", size_of::<Node>()),
("SCENE_BVH_NODE_MIN", offset_of!(Node, min)),
("SCENE_BVH_NODE_ESCAPE", offset_of!(Node, escape)),
("SCENE_BVH_NODE_MAX", offset_of!(Node, max)),
("SCENE_BVH_NODE_COUNT", offset_of!(Node, count)),
("SCENE_BVH_NODE_FIRST", offset_of!(Node, first)),
("SCENE_BVH_PRIMITIVE_WORDS", size_of::<LeafPrimitive>()),
("SCENE_BVH_PRIMITIVE_MESH", offset_of!(LeafPrimitive, mesh)),
(
"SCENE_BVH_PRIMITIVE_TRIANGLE",
offset_of!(LeafPrimitive, triangle),
),
]
}
#[cfg(test)]
mod tests {
use super::{
LEAF_PRIMITIVES, NODE_WORDS, Node, Primitive, RayMesh, Split, append, append_primitives,
rebase,
};
use crate::asset::Vertex;
use crate::scene::mesh_ranges::MeshRanges;
use glam::Vec3;
use wasm_bindgen_test::wasm_bindgen_test;
fn check_subtree(
words: &[u32],
at: usize,
bounds: [Vec3; 2],
primitives: &[[Vec3; 2]],
seen: &mut [u32],
) -> usize {
let node: Node = *bytemuck::from_bytes(bytemuck::cast_slice(&words[at..at + NODE_WORDS]));
let [min, max] = [Vec3::from(node.min), Vec3::from(node.max)];
assert!(
min.cmpge(bounds[0]).all() && max.cmple(bounds[1]).all(),
"node at {at} lies within its parent"
);
let escape = node.escape as usize;
assert!(escape > at, "node at {at} escapes forward");
if node.count == 0 {
let right = check_subtree(words, at + NODE_WORDS, [min, max], primitives, seen);
let end = check_subtree(words, right, [min, max], primitives, seen);
assert_eq!(end, escape, "node at {at} escapes past its children");
return escape;
}
let count = node.count as usize;
assert!(count <= LEAF_PRIMITIVES, "leaf at {at} holds {count}");
for &index in &words[node.first as usize..node.first as usize + count] {
let [p_min, p_max] = primitives[index as usize];
assert!(
p_min.cmpge(min).all() && p_max.cmple(max).all(),
"leaf at {at} bounds primitive {index}"
);
seen[index as usize] += 1;
}
assert_eq!(
escape,
at + NODE_WORDS + count,
"leaf at {at} escapes past its records"
);
escape
}
#[wasm_bindgen_test(unsupported = test)]
fn a_bvh_names_each_primitive_once_within_its_bounds() {
let mut seed = 0x2468_ace1_u32;
let mut random = move || {
seed = seed.wrapping_mul(1_664_525).wrapping_add(1_013_904_223);
(seed >> 8) as f32 / (1 << 24) as f32
};
for (split, count) in [Split::SurfaceArea, Split::EqualCounts]
.into_iter()
.flat_map(|split| {
[1, 2, 3, 4, 5, 6, 7, 8, 9, 17, 64, 1000, 5000].map(|count| (split, count))
})
{
let bounds: Vec<[Vec3; 2]> = (0..count)
.map(|index| {
let at = Vec3::new(random(), random(), random()) * 200. - 100.;
let size = match index % 4 {
0 => Vec3::new(60. * random(), 0.01, 0.4),
1 => Vec3::new(0.2, 8. * random(), 30. * random()),
2 => Vec3::splat(0.05),
_ => {
let half = random();
return [Vec3::splat(3. - half), Vec3::splat(3. + half)];
}
};
[at, at + size]
})
.collect();
let mut primitives: Vec<Primitive<u32>> = bounds
.iter()
.enumerate()
.map(|(index, &[min, max])| Primitive::new(min, max, index as u32))
.collect();
let mut words = Vec::new();
let root = append_primitives(&mut primitives, split, &mut words, 0);
assert_eq!(root, 0);
if split == Split::EqualCounts {
assert_eq!(words.len(), super::words::<u32>(count), "{count}");
}
let mut seen = vec![0; count];
let everything = [Vec3::splat(f32::MIN), Vec3::splat(f32::MAX)];
let end = check_subtree(&words, 0, everything, &bounds, &mut seen);
assert_eq!(
end,
words.len(),
"{split:?} {count}: the root's subtree is the BVH"
);
assert!(seen.iter().all(|&n| n == 1), "{split:?} {count}: {seen:?}");
}
}
#[wasm_bindgen_test(unsupported = test)]
fn rebased_words_match_words_built_in_place() {
let mut seed = 0x1357_9bdf_u32;
let mut random = move || {
seed = seed.wrapping_mul(1_664_525).wrapping_add(1_013_904_223);
(seed >> 8) as f32 / (1 << 24) as f32
};
let meshes: Vec<(Vec<Vertex>, Vec<u32>)> = [1usize, 3, 7, 61, 200]
.into_iter()
.map(|triangles| {
let vertices = (0..triangles * 3)
.map(|_| Vertex {
position: [random() * 16., random() * 16., random() * 16.],
..bytemuck::Zeroable::zeroed()
})
.collect();
(vertices, (0..triangles as u32 * 3).collect())
})
.collect();
let ranges: Vec<_> = meshes
.iter()
.map(|(vertices, indices)| MeshRanges::new(vertices, indices))
.collect();
let rays: Vec<_> = meshes
.iter()
.zip(&ranges)
.map(|((vertices, indices), ranges)| RayMesh {
vertices,
indices,
ranges,
shader_data: &[],
})
.collect();
for base in [1, 4096, 0x00ab_cdef] {
let mut in_place = Vec::new();
let root = append(&rays, &mut in_place, base);
let mut rebased = Vec::new();
let from_zero = append(&rays, &mut rebased, 0);
rebase(&mut rebased, base);
assert_eq!(from_zero + base, root);
assert_eq!(rebased, in_place, "base {base}");
}
}
}