concinnity_render/

bvh.rs

//! Top-down median-split bounding volume hierarchy over a set of AABBs.
//!
//! The renderer builds one BVH at GraphicsSystem init time from every cullable
//! DrawObject (objects without a finite AABB go into a separate fallback list).
//! Each frame the main pass traverses the BVH with the camera's frustum and
//! optional distance cutoff, producing a list of DrawObject indices to render.
//!
//! The BVH is static after construction: it does not refit when leaf AABBs
//! change.  Props that move at runtime (held items, animated transforms) must
//! opt out of culling by setting a non-finite AABB (UNCULLED_BB in draw_list).
//!
//! Construction is O(N log N) (sort + recurse); query is O(log N + V) where V
//! is the number of visible leaves.  Single-item scenes degenerate to a leaf
//! at the root; an empty scene produces no nodes and trivially answers "no
//! visible objects".

use crate::render_types::DrawObject;
use alloc::vec::Vec;

use crate::frustum::{Frustum, aabb_distance_sq};

#[derive(Copy, Clone, Debug)]
struct Aabb {
    min: [f32; 3],
    max: [f32; 3],
}

impl Aabb {
    fn empty() -> Self {
        Self {
            min: [f32::INFINITY; 3],
            max: [f32::NEG_INFINITY; 3],
        }
    }

    fn union(self, other: Aabb) -> Aabb {
        Aabb {
            min: [
                self.min[0].min(other.min[0]),
                self.min[1].min(other.min[1]),
                self.min[2].min(other.min[2]),
            ],
            max: [
                self.max[0].max(other.max[0]),
                self.max[1].max(other.max[1]),
                self.max[2].max(other.max[2]),
            ],
        }
    }

    fn centroid(self) -> [f32; 3] {
        [
            0.5 * (self.min[0] + self.max[0]),
            0.5 * (self.min[1] + self.max[1]),
            0.5 * (self.min[2] + self.max[2]),
        ]
    }
}

#[derive(Debug)]
enum Node {
    Internal {
        bb: Aabb,
        left: u32,
        right: u32,
    },
    Leaf {
        bb: Aabb,
        // Optional per-leaf view-distance cutoff (0 = no cutoff). Stored on
        // the leaf so the traversal can prune without a second array lookup.
        cull_distance: f32,
        index: u32,
    },
}

#[derive(Debug, Default)]
/// A bounding-volume hierarchy over cullable draw records.
pub struct Bvh {
    nodes: Vec<Node>,
    root: Option<u32>,
}

/// One leaf input as supplied to [`Bvh::build`].
#[derive(Copy, Clone, Debug)]
pub(crate) struct BvhItem {
    /// Lower corner of the leaf's world AABB.
    pub bb_min: [f32; 3],
    /// Upper corner of the leaf's world AABB.
    pub bb_max: [f32; 3],
    /// View-distance cutoff for this leaf; 0 means no cutoff.
    pub cull_distance: f32,
    /// Caller-side index passed through unchanged to the traversal callback.
    pub index: u32,
}

impl Bvh {
    /// Build a hierarchy over `items`. An empty input yields an empty tree.
    pub(crate) fn build(items: &[BvhItem]) -> Self {
        let mut bvh = Bvh::default();
        if items.is_empty() {
            return bvh;
        }
        let mut working: Vec<BvhItem> = items.to_vec();
        let root = bvh.build_recursive(&mut working);
        bvh.root = Some(root);
        bvh
    }

    /// Walk the BVH and call `visit` with every leaf index whose AABB is not
    /// fully outside the frustum and whose distance to `cam_pos` is within
    /// the leaf's `cull_distance` (0 = always inside).
    pub fn query<F: FnMut(u32)>(&self, frustum: &Frustum, cam_pos: [f32; 3], mut visit: F) {
        let root = match self.root {
            Some(r) => r,
            None => return,
        };
        // Recursive-style traversal using an explicit stack avoids blowing
        // the program stack on degenerate inputs and keeps the hot path
        // amenable to inlining.
        let mut stack: [u32; 64] = [0; 64];
        let mut sp: usize = 0;
        stack[sp] = root;
        sp += 1;

        while sp > 0 {
            sp -= 1;
            let idx = stack[sp];
            match &self.nodes[idx as usize] {
                Node::Internal { bb, left, right } => {
                    if !frustum.intersects_aabb(bb.min, bb.max) {
                        continue;
                    }
                    // Push both children. Order doesn't matter for correctness;
                    // pushing right first means left is visited first (cache
                    // locality if leaves were arranged by build order).
                    if sp + 2 > stack.len() {
                        // Tree depth exceeded the inline stack; fall back to
                        // a heap stack for the rest of this subtree. In
                        // practice 64 entries handles ~2^64 leaves.
                        self.query_heap(idx, frustum, cam_pos, &mut visit);
                        continue;
                    }
                    stack[sp] = *right;
                    sp += 1;
                    stack[sp] = *left;
                    sp += 1;
                }
                Node::Leaf {
                    bb,
                    cull_distance,
                    index,
                } => {
                    if !frustum.intersects_aabb(bb.min, bb.max) {
                        continue;
                    }
                    if *cull_distance > 0.0 {
                        let dsq = aabb_distance_sq(cam_pos, bb.min, bb.max);
                        if dsq > (*cull_distance) * (*cull_distance) {
                            continue;
                        }
                    }
                    visit(*index);
                }
            }
        }
    }

    fn query_heap<F: FnMut(u32)>(
        &self,
        start: u32,
        frustum: &Frustum,
        cam_pos: [f32; 3],
        visit: &mut F,
    ) {
        let mut stack: Vec<u32> = Vec::with_capacity(32);
        stack.push(start);
        while let Some(idx) = stack.pop() {
            match &self.nodes[idx as usize] {
                Node::Internal { bb, left, right } => {
                    if !frustum.intersects_aabb(bb.min, bb.max) {
                        continue;
                    }
                    stack.push(*right);
                    stack.push(*left);
                }
                Node::Leaf {
                    bb,
                    cull_distance,
                    index,
                } => {
                    if !frustum.intersects_aabb(bb.min, bb.max) {
                        continue;
                    }
                    if *cull_distance > 0.0 {
                        let dsq = aabb_distance_sq(cam_pos, bb.min, bb.max);
                        if dsq > (*cull_distance) * (*cull_distance) {
                            continue;
                        }
                    }
                    visit(*index);
                }
            }
        }
    }

    fn build_recursive(&mut self, items: &mut [BvhItem]) -> u32 {
        let bb = items
            .iter()
            .fold(Aabb::empty(), |acc, it| acc.union(item_aabb(it)));

        if items.len() == 1 {
            let it = items[0];
            let node_idx = self.nodes.len() as u32;
            self.nodes.push(Node::Leaf {
                bb,
                cull_distance: it.cull_distance,
                index: it.index,
            });
            return node_idx;
        }

        let extent = [
            bb.max[0] - bb.min[0],
            bb.max[1] - bb.min[1],
            bb.max[2] - bb.min[2],
        ];
        let axis = if extent[0] >= extent[1] && extent[0] >= extent[2] {
            0
        } else if extent[1] >= extent[2] {
            1
        } else {
            2
        };

        items.sort_by(|a, b| {
            let ca = item_aabb(a).centroid()[axis];
            let cb = item_aabb(b).centroid()[axis];
            ca.partial_cmp(&cb).unwrap_or(core::cmp::Ordering::Equal)
        });

        let mid = items.len() / 2;
        // Reserve this internal slot first so the indices reflect a stable
        // pre-order layout (root, left subtree, right subtree).
        let self_idx = self.nodes.len() as u32;
        self.nodes.push(Node::Internal {
            bb,
            left: u32::MAX,
            right: u32::MAX,
        });

        let (left_items, right_items) = items.split_at_mut(mid);
        let left = self.build_recursive(left_items);
        let right = self.build_recursive(right_items);

        match &mut self.nodes[self_idx as usize] {
            Node::Internal {
                left: l, right: r, ..
            } => {
                *l = left;
                *r = right;
            }
            Node::Leaf { .. } => unreachable!("self_idx must point at an Internal node"),
        }
        self_idx
    }
}

fn item_aabb(it: &BvhItem) -> Aabb {
    Aabb {
        min: it.bb_min,
        max: it.bb_max,
    }
}

/// Partition the draw list into cullable leaves (suitable for BVH insertion)
/// and an always-drawn fallback list. Objects that opt out of culling (skybox,
/// rooms, held props) keep their original draw order via the returned index
/// list; the BVH owns everything else.
pub fn partition_draw_objects(draw_objects: &[DrawObject]) -> (Bvh, Vec<u32>) {
    let mut items: Vec<BvhItem> = Vec::new();
    let mut always_draw: Vec<u32> = Vec::new();
    for (i, obj) in draw_objects.iter().enumerate() {
        if obj.cullable() {
            items.push(BvhItem {
                bb_min: obj.bb_min,
                bb_max: obj.bb_max,
                cull_distance: obj.cull_distance,
                index: i as u32,
            });
        } else {
            always_draw.push(i as u32);
        }
    }
    (Bvh::build(&items), always_draw)
}

#[cfg(test)]
mod tests {
    use super::*;

    use alloc::vec;
    fn ident_vp() -> [[f32; 4]; 4] {
        [
            [1.0, 0.0, 0.0, 0.0],
            [0.0, 1.0, 0.0, 0.0],
            [0.0, 0.0, 1.0, 0.0],
            [0.0, 0.0, 0.0, 1.0],
        ]
    }

    fn item(idx: u32, min: [f32; 3], max: [f32; 3]) -> BvhItem {
        BvhItem {
            bb_min: min,
            bb_max: max,
            cull_distance: 0.0,
            index: idx,
        }
    }

    fn collect(bvh: &Bvh, frustum: &Frustum) -> Vec<u32> {
        let mut out = Vec::new();
        bvh.query(frustum, [0.0, 0.0, 0.0], |i| out.push(i));
        out.sort();
        out
    }

    #[test]
    fn empty_input_yields_empty_bvh() {
        let bvh = Bvh::build(&[]);
        assert!(bvh.root.is_none());
        assert_eq!(bvh.nodes.len(), 0);
        let f = Frustum::from_view_projection(ident_vp());
        let mut hits = 0;
        bvh.query(&f, [0.0, 0.0, 0.0], |_| hits += 1);
        assert_eq!(hits, 0);
    }

    #[test]
    fn single_item_creates_one_leaf() {
        let bvh = Bvh::build(&[item(7, [-0.1, -0.1, -0.1], [0.1, 0.1, 0.1])]);
        assert!(bvh.root.is_some());
        assert_eq!(bvh.nodes.len(), 1);
        let f = Frustum::from_view_projection(ident_vp());
        assert_eq!(collect(&bvh, &f), vec![7]);
    }

    #[test]
    fn visible_and_invisible_items_separate() {
        let bvh = Bvh::build(&[
            item(0, [-0.5, -0.5, -0.5], [0.5, 0.5, 0.5]),
            item(1, [5.0, -0.5, -0.5], [6.0, 0.5, 0.5]),
            item(2, [-0.5, -0.5, -0.5], [0.5, 0.5, 0.5]),
        ]);
        let f = Frustum::from_view_projection(ident_vp());
        assert_eq!(collect(&bvh, &f), vec![0, 2]);
    }

    #[test]
    fn distance_cutoff_prunes_far_leaf() {
        let mut a = item(0, [-0.5, -0.5, -0.5], [0.5, 0.5, 0.5]);
        a.cull_distance = 1.0;
        let mut b = item(1, [-0.5, -0.5, -0.5], [0.5, 0.5, 0.5]);
        b.cull_distance = 0.0;
        let bvh = Bvh::build(&[a, b]);
        let f = Frustum::from_view_projection(ident_vp());
        let mut out = Vec::new();
        // Camera 10 units away: `a` should drop, `b` stays.
        bvh.query(&f, [10.0, 0.0, 0.0], |i| out.push(i));
        out.sort();
        assert_eq!(out, vec![1]);
    }

    #[test]
    fn many_items_all_visible_inside_frustum() {
        let mut items = Vec::new();
        for i in 0..64 {
            let x = (i as f32) * 0.001 - 0.5;
            items.push(item(i, [x, -0.5, -0.5], [x + 0.05, 0.5, 0.5]));
        }
        let bvh = Bvh::build(&items);
        let f = Frustum::from_view_projection(ident_vp());
        let got = collect(&bvh, &f);
        assert_eq!(got.len(), 64);
    }

    #[test]
    fn frustum_rejecting_root_emits_nothing() {
        let bvh = Bvh::build(&[
            item(0, [10.0, -0.5, -0.5], [11.0, 0.5, 0.5]),
            item(1, [10.0, -0.5, -0.5], [11.0, 0.5, 0.5]),
        ]);
        let f = Frustum::from_view_projection(ident_vp());
        assert!(collect(&bvh, &f).is_empty());
    }

    // A minimal DrawObject carrying only the fields partition_draw_objects
    // reads: the bounding box (which decides `cullable`) and the cull distance.
    fn draw_object(bb_min: [f32; 3], bb_max: [f32; 3]) -> DrawObject {
        DrawObject {
            vertex_offset: 0,
            vertex_count: 0,
            index_offset: 0,
            index_count: 0,
            base_vertex: 0,
            geometry_generation: 0,
            shader_bucket: 0,
            model: ident_vp(),
            texture_slot: 0,
            normal_map_slot: 0,
            material: crate::render_types::MaterialUniforms::DEFAULT,
            visible: true,
            resident: true,
            bb_min,
            bb_max,
            cull_distance: 0.0,
            lod_alternates: Vec::new(),
        }
    }

    #[test]
    fn partition_splits_cullable_from_always_draw() {
        // A NaN box opts out of culling, so it lands in the always-draw list;
        // the two finite boxes become BVH leaves under one internal root.
        let objs = vec![
            draw_object([-0.5, -0.5, -0.5], [0.5, 0.5, 0.5]), // idx 0, cullable
            draw_object([f32::NAN, 0.0, 0.0], [1.0, 1.0, 1.0]), // idx 1, opts out
            draw_object([-0.3, -0.3, -0.3], [0.3, 0.3, 0.3]), // idx 2, cullable
        ];
        let (bvh, always_draw) = partition_draw_objects(&objs);
        assert_eq!(always_draw, vec![1]);
        assert!(bvh.root.is_some());
        // Two leaves plus their internal root.
        assert_eq!(bvh.nodes.len(), 3);
        // The BVH carries the original draw indices through to the traversal.
        let f = Frustum::from_view_projection(ident_vp());
        assert_eq!(collect(&bvh, &f), vec![0, 2]);
    }

    #[test]
    fn partition_with_no_cullable_objects_yields_empty_bvh() {
        let objs = vec![
            draw_object([f32::NAN, 0.0, 0.0], [1.0, 1.0, 1.0]),
            draw_object([0.0, f32::NAN, 0.0], [1.0, 1.0, 1.0]),
        ];
        let (bvh, always_draw) = partition_draw_objects(&objs);
        assert_eq!(always_draw, vec![0, 1]);
        assert!(bvh.root.is_none());
        assert_eq!(bvh.nodes.len(), 0);
    }

    #[test]
    fn build_splits_on_the_y_axis() {
        // Leaves spread along y with tiny x/z extent force the y-axis split
        // branch (extent[1] is the largest).
        let items: Vec<BvhItem> = (0..4)
            .map(|i| {
                let y = i as f32 * 0.2 - 0.3;
                item(i, [-0.05, y, -0.05], [0.05, y + 0.05, 0.05])
            })
            .collect();
        let bvh = Bvh::build(&items);
        // Four leaves + three internal nodes in the balanced median split.
        assert_eq!(bvh.nodes.len(), 7);
        let f = Frustum::from_view_projection(ident_vp());
        assert_eq!(collect(&bvh, &f), vec![0, 1, 2, 3]);
    }

    #[test]
    fn build_splits_on_the_z_axis() {
        // Leaves spread along z with tiny x/y extent force the z-axis (else)
        // split branch.
        let items: Vec<BvhItem> = (0..4)
            .map(|i| {
                let z = i as f32 * 0.2 - 0.3;
                item(i, [-0.05, -0.05, z], [0.05, 0.05, z + 0.05])
            })
            .collect();
        let bvh = Bvh::build(&items);
        assert_eq!(bvh.nodes.len(), 7);
        let f = Frustum::from_view_projection(ident_vp());
        assert_eq!(collect(&bvh, &f), vec![0, 1, 2, 3]);
    }
}

// Build and query cost over a scene the size a stress world reaches. In-crate
// rather than under a bench target because `Bvh::build` and `BvhItem` have no
// consumer outside this crate -- a backend receives a built `Bvh` from
// `partition_draw_objects` and only queries it.
//
//     cargo test -p concinnity-render --release -- --ignored --nocapture \
//         --test-threads=1 bench_bvh
#[cfg(test)]
mod bench {
    use super::{Bvh, BvhItem};
    use crate::frustum::Frustum;
    use alloc::vec::Vec;
    use std::println;
    use std::time::Instant;

    const OBJECTS: usize = 10_000;
    const TARGET_NS: u128 = 200_000_000;
    const MAX_ITERS: u64 = 1 << 20;

    fn bench<R>(name: &str, items: u64, mut body: impl FnMut() -> R) {
        let mut iters: u64 = 1;
        loop {
            let start = Instant::now();
            for _ in 0..iters {
                core::hint::black_box(body());
            }
            if start.elapsed().as_nanos() >= TARGET_NS || iters >= MAX_ITERS {
                break;
            }
            iters = iters.saturating_mul(4).min(MAX_ITERS);
        }

        let start = Instant::now();
        for _ in 0..iters {
            core::hint::black_box(body());
        }
        let per_item_ns = start.elapsed().as_secs_f64() * 1e9 / (iters * items.max(1)) as f64;
        println!("  {name:<40} {per_item_ns:>10.2} ns/item");
    }

    // Unit boxes on a 100x100 ground grid straddling the camera plane, so the
    // frustum query sees a real mix of accepted, rejected, and straddling
    // nodes.
    fn scene_items() -> Vec<BvhItem> {
        (0..OBJECTS)
            .map(|i| {
                let x = (i % 100) as f32 * 3.0 - 150.0;
                let z = (i / 100) as f32 * 6.0 - 300.0;
                BvhItem {
                    bb_min: [x - 0.5, 0.0, z - 0.5],
                    bb_max: [x + 0.5, 1.0, z + 0.5],
                    cull_distance: 0.0,
                    index: i as u32,
                }
            })
            .collect()
    }

    // Perspective view-projection (70 degree fov, 16:9, camera at the origin
    // looking down -Z), column-major as the renderer's ViewUniforms lay it out.
    fn camera_frustum() -> Frustum {
        let f = 1.0 / 35.0f32.to_radians().tan();
        let aspect = 16.0 / 9.0;
        let (near, far) = (0.1, 400.0);
        let mut vp = [[0.0f32; 4]; 4];
        vp[0][0] = f / aspect;
        vp[1][1] = f;
        vp[2][2] = (far + near) / (near - far);
        vp[2][3] = -1.0;
        vp[3][2] = 2.0 * far * near / (near - far);
        Frustum::from_view_projection(vp)
    }

    #[test]
    #[ignore = "benchmark; run with --ignored --test-threads=1"]
    fn bench_bvh() {
        let items = scene_items();
        let frustum = camera_frustum();

        bench("render/bvh_build/10k", OBJECTS as u64, || {
            Bvh::build(&items)
        });

        let bvh = Bvh::build(&items);
        let mut visible = 0u32;
        bvh.query(&frustum, [0.0; 3], |_| visible += 1);
        assert!(
            visible > 0 && (visible as usize) < OBJECTS,
            "the query fixture must accept some objects and reject others, saw {visible}"
        );
        bench("render/bvh_query/10k", OBJECTS as u64, || {
            let mut seen = 0u32;
            bvh.query(&frustum, [0.0; 3], |_| seen += 1);
            seen
        });
    }
}