gemath 0.1.0

#![cfg(feature = "spatial")]

use criterion::{black_box, criterion_group, criterion_main, Criterion};
use gemath::{Aabb2, Aabb3, Bvh3, Quadtree2, UniformGrid2, Vec2, Vec3};

#[derive(Clone, Copy)]
struct XorShift32 {
    state: u32,
}

impl XorShift32 {
    fn new(seed: u32) -> Self {
        Self { state: seed.max(1) }
    }

    fn next_u32(&mut self) -> u32 {
        let mut x = self.state;
        x ^= x << 13;
        x ^= x >> 17;
        x ^= x << 5;
        self.state = x;
        x
    }

    fn next_f32(&mut self) -> f32 {
        // [0,1)
        let v = self.next_u32();
        (v as f32) / (u32::MAX as f32)
    }
}

fn make_aabb2s(n: usize, seed: u32) -> Vec<Aabb2<(), ()>> {
    let mut rng = XorShift32::new(seed);
    let mut out = Vec::with_capacity(n);
    for _ in 0..n {
        let cx = rng.next_f32() * 1024.0;
        let cy = rng.next_f32() * 1024.0;
        let hx = 1.0 + rng.next_f32() * 8.0;
        let hy = 1.0 + rng.next_f32() * 8.0;
        let min = Vec2::new(cx - hx, cy - hy);
        let max = Vec2::new(cx + hx, cy + hy);
        out.push(Aabb2::from_min_max(min, max));
    }
    out
}

fn make_aabb3s(n: usize, seed: u32) -> Vec<Aabb3<(), ()>> {
    let mut rng = XorShift32::new(seed);
    let mut out = Vec::with_capacity(n);
    for _ in 0..n {
        let cx = rng.next_f32() * 1024.0;
        let cy = rng.next_f32() * 1024.0;
        let cz = rng.next_f32() * 1024.0;
        let hx = 1.0 + rng.next_f32() * 8.0;
        let hy = 1.0 + rng.next_f32() * 8.0;
        let hz = 1.0 + rng.next_f32() * 8.0;
        let min = Vec3::new(cx - hx, cy - hy, cz - hz);
        let max = Vec3::new(cx + hx, cy + hy, cz + hz);
        out.push(Aabb3::from_min_max(min, max));
    }
    out
}

pub fn spatial_benchmarks(c: &mut Criterion) {
    // Keep sizes moderate so benches finish quickly.
    let n2 = 10_000usize;
    let q2 = 2_000usize;

    let aabbs2 = make_aabb2s(n2, 0xC0FFEEu32);
    let queries2 = make_aabb2s(q2, 0xBADC0DEu32);

    c.bench_function("spatial2d/bruteforce_query_count", |b| {
        b.iter(|| {
            let mut hits = 0usize;
            for q in &queries2 {
                for a in &aabbs2 {
                    if a.intersection(q).is_some() {
                        hits += 1;
                    }
                }
            }
            black_box(hits)
        })
    });

    c.bench_function("spatial2d/uniform_grid_build", |b| {
        b.iter(|| {
            let min = Vec2::new(0.0, 0.0);
            let max = Vec2::new(1024.0, 1024.0);
            let mut grid: UniformGrid2<(), ()> = UniformGrid2::new(min, max, 16.0);
            grid.rebuild_from_aabbs(&aabbs2);
            black_box(grid.dims())
        })
    });

    c.bench_function("spatial2d/uniform_grid_query_candidates", |b| {
        let min = Vec2::new(0.0, 0.0);
        let max = Vec2::new(1024.0, 1024.0);
        let mut grid: UniformGrid2<(), ()> = UniformGrid2::new(min, max, 16.0);
        grid.rebuild_from_aabbs(&aabbs2);
        let mut out = Vec::<usize>::new();
        b.iter(|| {
            let mut total = 0usize;
            for q in &queries2 {
                grid.query_aabb(q, &mut out);
                total += out.len();
            }
            black_box(total)
        })
    });

    c.bench_function("spatial2d/quadtree_build", |b| {
        b.iter(|| {
            let root: Aabb2<(), ()> = Aabb2::from_min_max(Vec2::new(0.0, 0.0), Vec2::new(1024.0, 1024.0));
            let mut qt: Quadtree2<(), ()> = Quadtree2::new(root, 10, 8);
            qt.rebuild_from_aabbs(&aabbs2);
            black_box(())
        })
    });

    c.bench_function("spatial2d/quadtree_query_candidates", |b| {
        let root: Aabb2<(), ()> = Aabb2::from_min_max(Vec2::new(0.0, 0.0), Vec2::new(1024.0, 1024.0));
        let mut qt: Quadtree2<(), ()> = Quadtree2::new(root, 10, 8);
        qt.rebuild_from_aabbs(&aabbs2);
        let mut out = Vec::<usize>::new();
        b.iter(|| {
            let mut total = 0usize;
            for q in &queries2 {
                qt.query_aabb(q, &mut out);
                total += out.len();
            }
            black_box(total)
        })
    });

    // 3D BVH
    let n3 = 20_000usize;
    let q3 = 2_000usize;
    let aabbs3 = make_aabb3s(n3, 0x1234ABCDu32);
    let queries3 = make_aabb3s(q3, 0xCAFEBABEu32);

    c.bench_function("spatial3d/bvh_build", |b| {
        b.iter(|| {
            let bvh: Bvh3<(), ()> = Bvh3::build(&aabbs3);
            black_box(bvh)
        })
    });

    c.bench_function("spatial3d/bvh_query_candidates", |b| {
        let bvh: Bvh3<(), ()> = Bvh3::build(&aabbs3);
        let mut out = Vec::<usize>::new();
        b.iter(|| {
            let mut total = 0usize;
            for q in &queries3 {
                bvh.query_aabb(q, &mut out);
                total += out.len();
            }
            black_box(total)
        })
    });
}

criterion_group!(benches, spatial_benchmarks);
criterion_main!(benches);