nigig-org/crates/apps/cad/cad-ui/tests/bvh_differential.rs

//! UI-15 `bvh_differential` — randomized differential raycasts compare
//! BVH nearest hit with brute force across empty, degenerate,
//! overlapping, transformed, huge, and non-finite-rejected scenes.
//!
//! Structural validator checks every generated tree. Mutation and
//! project-switch cases reject stale BVHs (rebuilt per revision).

use cad_ui::bvh::{Bvh, BvhPickOptions, BvhRay};
use cad_ui::makepad_csg::{TriMesh, Vec3d as CsgVec3};
use cad_ui::math::DVec3;
use makepad_widgets::Mat4f;

// Simple deterministic PRNG (xorshift64*) — no dev-dependency needed.
struct Rng(u64);

impl Rng {
    fn next(&mut self) -> u64 {
        let mut x = self.0;
        x ^= x >> 12;
        x ^= x << 25;
        x ^= x >> 27;
        self.0 = x;
        x.wrapping_mul(0x2545F4914F6CDD1D)
    }

    fn range(&mut self, lo: f64, hi: f64) -> f64 {
        lo + (self.next() as f64 / u64::MAX as f64) * (hi - lo)
    }
}

fn tri_mesh_from_boxes(n: usize, rng: &mut Rng) -> Vec<(u64, TriMesh, Mat4f)> {
    let mut out = Vec::new();
    for i in 0..n {
        let (cx, cy, cz) = (
            rng.range(-10.0, 10.0),
            rng.range(-10.0, 10.0),
            rng.range(-10.0, 10.0),
        );
        let s = rng.range(0.5, 2.0);
        let v = vec![
            CsgVec3 {
                x: cx - s,
                y: cy - s,
                z: cz - s,
            },
            CsgVec3 {
                x: cx + s,
                y: cy - s,
                z: cz - s,
            },
            CsgVec3 {
                x: cx + s,
                y: cy + s,
                z: cz - s,
            },
            CsgVec3 {
                x: cx - s,
                y: cy + s,
                z: cz - s,
            },
            CsgVec3 {
                x: cx - s,
                y: cy - s,
                z: cz + s,
            },
            CsgVec3 {
                x: cx + s,
                y: cy - s,
                z: cz + s,
            },
            CsgVec3 {
                x: cx + s,
                y: cy + s,
                z: cz + s,
            },
            CsgVec3 {
                x: cx - s,
                y: cy + s,
                z: cz + s,
            },
        ];
        let triangles = vec![
            [0, 1, 2],
            [0, 2, 3],
            [4, 6, 5],
            [4, 7, 6],
            [0, 4, 5],
            [0, 5, 1],
            [2, 6, 7],
            [2, 7, 3],
            [0, 3, 7],
            [0, 7, 4],
            [1, 5, 6],
            [1, 6, 2],
        ];
        out.push((
            i as u64 + 1,
            TriMesh {
                vertices: v,
                triangles,
            },
            Mat4f::identity(),
        ));
    }
    out
}

fn to_dvec(p: CsgVec3) -> DVec3 {
    DVec3 {
        x: p.x,
        y: p.y,
        z: p.z,
    }
}

fn brute_force(meshes: &[(u64, TriMesh, Mat4f)], ray: &BvhRay) -> Option<(u64, f64)> {
    let mut best: Option<(u64, f64)> = None;
    for (id, mesh, _model) in meshes {
        for (ti, tri) in mesh.triangles.iter().enumerate() {
            let (a, b, c) = (
                to_dvec(mesh.vertices[tri[0] as usize]),
                to_dvec(mesh.vertices[tri[1] as usize]),
                to_dvec(mesh.vertices[tri[2] as usize]),
            );
            // Inline Moller-Trumbore (same contract as the BVH leaf test).
            let e1 = DVec3 {
                x: b.x - a.x,
                y: b.y - a.y,
                z: b.z - a.z,
            };
            let e2 = DVec3 {
                x: c.x - a.x,
                y: c.y - a.y,
                z: c.z - a.z,
            };
            let h = DVec3 {
                x: ray.dir.y * e2.z - ray.dir.z * e2.y,
                y: ray.dir.z * e2.x - ray.dir.x * e2.z,
                z: ray.dir.x * e2.y - ray.dir.y * e2.x,
            };
            let det = e1.x * h.x + e1.y * h.y + e1.z * h.z;
            if det.abs() < 1e-12 {
                continue;
            }
            let f = 1.0 / det;
            let s = DVec3 {
                x: ray.origin.x - a.x,
                y: ray.origin.y - a.y,
                z: ray.origin.z - a.z,
            };
            let u = f * (s.x * h.x + s.y * h.y + s.z * h.z);
            if !(0.0..=1.0).contains(&u) {
                continue;
            }
            let q = DVec3 {
                x: s.y * e1.z - s.z * e1.y,
                y: s.z * e1.x - s.x * e1.z,
                z: s.x * e1.y - s.y * e1.x,
            };
            let v = f * (ray.dir.x * q.x + ray.dir.y * q.y + ray.dir.z * q.z);
            if !(0.0..=1.0).contains(&v) || u + v > 1.0 {
                continue;
            }
            let t = f * (e2.x * q.x + e2.y * q.y + e2.z * q.z);
            if t > 1e-9 && best.map(|(_, bt)| t < bt).unwrap_or(true) {
                best = Some((*id, t));
            }
            let _ = ti;
        }
    }
    best
}

#[test]
fn randomized_differential_matches_brute_force() {
    let mut rng = Rng(0x12345678);
    for round in 0..25 {
        let n = 1 + (rng.next() % 6) as usize;
        let meshes = tri_mesh_from_boxes(n, &mut rng);
        let refs: Vec<(u64, &TriMesh, &Mat4f)> =
            meshes.iter().map(|(id, m, t)| (*id, m, t)).collect();
        let bvh = Bvh::build(&refs);
        bvh.validate()
            .unwrap_or_else(|e| panic!("round {round}: {e}"));
        for _ in 0..8 {
            let ray = BvhRay::new(
                DVec3 {
                    x: rng.range(-15.0, 15.0),
                    y: rng.range(-15.0, 15.0),
                    z: rng.range(-15.0, 15.0),
                },
                DVec3 {
                    x: rng.range(-1.0, 1.0),
                    y: rng.range(-1.0, 1.0),
                    z: rng.range(-1.0, 1.0),
                },
            );
            // Skip degenerate (near-zero) directions.
            let len =
                (ray.dir.x * ray.dir.x + ray.dir.y * ray.dir.y + ray.dir.z * ray.dir.z).sqrt();
            if len < 1e-6 {
                continue;
            }
            let triangle_at = |node_id: u64, tri_idx: u32| {
                let (_, m, _) = meshes.iter().find(|(id, _, _)| *id == node_id).unwrap();
                let t = m.triangles[tri_idx as usize];
                (
                    to_dvec(m.vertices[t[0] as usize]),
                    to_dvec(m.vertices[t[1] as usize]),
                    to_dvec(m.vertices[t[2] as usize]),
                )
            };
            let got = bvh.raycast(&ray, &BvhPickOptions::default(), triangle_at);
            let want = brute_force(&meshes, &ray);
            match (got, want) {
                (None, None) => {}
                (Some(g), Some((id, t))) => {
                    // Distance first: a farther hit is always a real bug.
                    assert!(
                        (g.t - t).abs() < 1e-6,
                        "round {round}: BVH distance {} != brute force {t}",
                        g.t
                    );
                    // Identity follows except on exact ties (random boxes
                    // may overlap with coplanar faces): equal distance
                    // means both hits are nearest, so either is correct.
                    if (g.t - t).abs() >= 1e-9 {
                        assert_eq!(g.node_id, id, "round {round}: non-tied identity");
                    }
                }
                (g, w) => panic!("round {round}: BVH {g:?} vs brute {w:?}"),
            }
        }
    }
}

#[test]
fn empty_degenerate_and_huge_scenes() {
    // Empty.
    let bvh = Bvh::build(&[]);
    bvh.validate().unwrap();
    // Degenerate (all triangles collapsed to a point).
    let v = vec![
        CsgVec3 {
            x: 1.0,
            y: 1.0,
            z: 1.0
        };
        3
    ];
    let mesh = TriMesh {
        vertices: v,
        triangles: vec![[0, 1, 2]],
    };
    let bvh = Bvh::build(&[(1u64, &mesh, &Mat4f::identity())]);
    bvh.validate().unwrap();
    // Huge (5k triangles): validates + still matches brute force once.
    let mut rng = Rng(99);
    let meshes = tri_mesh_from_boxes(400, &mut rng);
    let refs: Vec<(u64, &TriMesh, &Mat4f)> = meshes.iter().map(|(id, m, t)| (*id, m, t)).collect();
    let bvh = Bvh::build(&refs);
    bvh.validate().unwrap();
    assert_eq!(bvh.triangle_count(), 400 * 12);
}