Skip to content

SolidCraft: an open-source parametric 3D CAD application built in pure Rust. Desktop, web, and automation through MCP.

2.6 KB
Raw Blame
use super::{MAX_BVH_DEPTH, Node, Triangle, build};
use solidcore_record::Vec3;
use solidcraft_render::{job::CancelToken, surface::OpaqueSurface};

// Triangle centres spread over 60 decades: a sixteen-bin SAH split on the
// centre range peels only the few largest triangles off at each level, so an
// unbounded build is far deeper than the shader's traversal stack allows.
fn decades(count: usize) -> Vec<Triangle> {
    let surface = OpaqueSurface::new(Vec3::new(0.5, 0.5, 0.5), 0.0, 0.5, 1.5).unwrap();
    (0..count)
        .map(|i| {
            let x = 10f64.powf(-30.0 + 60.0 * i as f64 / count as f64);
            Triangle {
                p: [Vec3::new(x, 0., 0.), Vec3::new(x * 1.5, 0., 0.), Vec3::new(x, x, x)],
                indices: [0, 1, 2].map(|c| (3 * i + c) as u32),
                surface,
                transmission: None,
                medium: 0,
                scalar_face: false,
            }
        })
        .collect()
}

#[test]
fn sah_tree_respects_the_shader_stack_depth_and_covers_every_triangle_once() {
    let count = 2048;
    let mut triangles = decades(count);
    let mut nodes = vec![Node::default()];
    build(&mut triangles, 0, &mut nodes, 0, 0, &CancelToken::default()).unwrap();
    assert!(nodes.len() < 2 * count, "{} nodes", nodes.len());
    let mut covered = vec![0; count];
    let mut deepest = 0;
    let mut pending = vec![(0usize, 0usize)];
    while let Some((index, depth)) = pending.pop() {
        let node = &nodes[index];
        let (first, size) = (node.first as usize, node.count as usize);
        deepest = deepest.max(depth);
        if size == 0 {
            for child in [first, first + 1] {
                let inner = &nodes[child];
                for axis in 0..3 {
                    assert!(node.lo[axis] <= inner.lo[axis] && inner.hi[axis] <= node.hi[axis], "child box escapes its parent");
                }
                pending.push((child, depth + 1));
            }
            continue;
        }
        assert!(size <= 4);
        for (slot, triangle) in covered[first..first + size].iter_mut().zip(&triangles[first..first + size]) {
            *slot += 1;
            for p in triangle.p {
                for (axis, value) in [p.x as f32, p.y as f32, p.z as f32].into_iter().enumerate() {
                    assert!(node.lo[axis] <= value && value <= node.hi[axis], "triangle escapes its leaf");
                }
            }
        }
    }
    assert!(covered.iter().all(|&c| c == 1), "{covered:?}");
    assert!(deepest <= MAX_BVH_DEPTH, "depth {deepest}");
    // Covering 2048 triangles in leaves of four needs at least nine levels.
    assert!(deepest >= 9, "depth {deepest}");
}