svenstaro / bvh

A fast BVH using SAH in rust

Hi there, random stranger! 👋

Stay awhile and listen

• I make handy CLI tools. 🔧
• I quite like Rust. 🦀
• I do graphics and high-performance stuff. 🏎️
• I like automation and when things just maintain themselves. Sadly though, they rarely do in practice. 🤖
• I am a developer and devops in Arch Linux where I also maintain a ton of packages! 🐧

Also check out svenstaro.org.

If you like my work, please consider supporting me!

bvh's Issues

Support for Distance Queries

This is sort of a feature request, but I would also be happy to work on implementing it!

I am experimenting with porting some of our C++ code to rust. I would love to use a community supported BVH implementation this time around. However, besides ray intersections, we also make extensive use of distance queries, i.e. what is the closest object/s in the BVH to arbitrary points.

Is this functionality y'all would be open to having in this crate?

I have some ideas on how that would look which I'd be happy to discuss, and there are some other queries I'd be willing to port over too like a Fast Winding Number, but I don't want to get ahead of myself or be overwhelming.

Consider restructuring the bvh/ directory

Currently some functions are defined in some files where it is unobvious that they are implemented there.

`Bvh::traverse{_iterator}` panics on an empty BVH

Thanks for making this crate! I noticed a panic when iterating an empty BVH. Here is a reproducible example:

[package]
name = "bvh_test"
version = "0.1.0"
edition = "2021"

[dependencies]
bvh = "0.9.0"
nalgebra = "0.32.5"

use bvh::{aabb::{Aabb, Bounded}, bounding_hierarchy::BHShape, bvh::Bvh, ray::Ray};
use nalgebra::{OPoint, Vector};

fn main() {
    struct Shape;
    const DIM : usize = 3;
    impl Bounded<f32, DIM> for Shape {
        fn aabb(&self) -> Aabb<f32, DIM> {
            unreachable!();
        }
    }
    impl BHShape<f32, DIM> for Shape {
        fn bh_node_index(&self) -> usize {
            unreachable!();
        }
        fn set_bh_node_index(&mut self, _: usize) {
            unreachable!();
        }
    }
    let mut shapes = [];
    let bvh = Bvh::<f32, 3>::build::<Shape>(&mut shapes);
    bvh.traverse_iterator(&Ray::new(OPoint::origin(), Vector::x()), &shapes).next();
}

thread 'main' panicked at /home/finnb/.cargo/registry/src/index.crates.io-6f17d22bba15001f/bvh-0.9.0/src/bvh/iter.rs:68:29:
index out of bounds: the len is 0 but the index is 0
stack backtrace:
   0: rust_begin_unwind
             at /rustc/f067fd6084d750f3797f54b71771c5dbc149726f/library/std/src/panicking.rs:647:5
   1: core::panicking::panic_fmt
             at /rustc/f067fd6084d750f3797f54b71771c5dbc149726f/library/core/src/panicking.rs:72:14
   2: core::panicking::panic_bounds_check
             at /rustc/f067fd6084d750f3797f54b71771c5dbc149726f/library/core/src/panicking.rs:208:5
   3: <usize as core::slice::index::SliceIndex<[T]>>::index
             at /rustc/f067fd6084d750f3797f54b71771c5dbc149726f/library/core/src/slice/index.rs:255:10
   4: core::slice::index::<impl core::ops::index::Index<I> for [T]>::index
             at /rustc/f067fd6084d750f3797f54b71771c5dbc149726f/library/core/src/slice/index.rs:18:9
   5: <alloc::vec::Vec<T,A> as core::ops::index::Index<I>>::index
             at /rustc/f067fd6084d750f3797f54b71771c5dbc149726f/library/alloc/src/vec/mod.rs:2771:9
   6: bvh::bvh::iter::BvhTraverseIterator<T,_,Shape>::move_left
             at /home/finnb/.cargo/registry/src/index.crates.io-6f17d22bba15001f/bvh-0.9.0/src/bvh/iter.rs:68:29
   7: <bvh::bvh::iter::BvhTraverseIterator<T,_,Shape> as core::iter::traits::iterator::Iterator>::next
             at /home/finnb/.cargo/registry/src/index.crates.io-6f17d22bba15001f/bvh-0.9.0/src/bvh/iter.rs:124:17
   8: bvh_test::main
             at ./src/main.rs:22:5
   9: core::ops::function::FnOnce::call_once
             at /rustc/f067fd6084d750f3797f54b71771c5dbc149726f/library/core/src/ops/function.rs:250:5

Support glam instead of or in addition to nalgebra?

glam (https://github.com/bitshifter/glam-rs) is a much slimmer, faster-to-build and neater vector math library than nalgebra, which is so complex that it often triggers Rust compiler bugs (a discussion to be had elsewhere).

It might be possible to support both through feature flags and some type redefinitions.

why won't my rays intersect?

So I have a problem, obvious ray intersections just arn't happening, like, at all, I can't get any rays (from the origin, but anywere else as well) to hit my custom mesh. this is part of a small personal project so it's only a couple hundred lines and I have already tested everything else and the problem seems to stem from this code here:

fn closest_hit(&self, ray: &Ray<f32, 3>) -> Option<(f32, usize)> {
       let mut closest_dist = f32::INFINITY;
       let mut closest_idx = 0;

    for tri in self.bvh.traverse_iterator(&ray, &self.tris) {
        let p1 = Point3::from(self.verts[tri.indices[0]]);
        let p2 = Point3::from(self.verts[tri.indices[1]]);
        let p3 = Point3::from(self.verts[tri.indices[2]]);
        
        let res = ray.intersects_triangle(&p1, &p2, &p3);
        
        if res.distance < closest_dist {
            closest_dist = res.distance;
            closest_idx = tri.index;
        }
    }

    if closest_dist == f32::INFINITY {
        None
    } else {
        Some((closest_dist, closest_idx))
    }
}

this code always return None no matter where the ray is, it's durection or the normals of the triangles being tested. The iterator always returns no items. And like I said I already validated everything else and it's driving me insane. Does anyone know what could possibley be causing this issue? Here is some debug info on the bvh:

child_l Min bound: {-2.050189, -2.050189, -2.050189}; Max bound: {-2.050189, 2.050189, 2.050189}
child_l Min bound: {-2.050189, -2.050189, -2.050189}; Max bound: {-2.050189, -0.990136, 2.050189}
child_l Min bound: {-2.050189, -2.050189, -2.050189}; Max bound: {-2.050189, -0.990136, 2.050189}
shape 14
child_r Min bound: {-2.050189, -2.050189, -0.990136}; Max bound: {-2.050189, -0.990136, 2.050189}
shape 5
child_r Min bound: {-2.050189, -2.050189, -2.050189}; Max bound: {-2.050189, 2.050189, 2.050189}
child_l Min bound: {-2.050189, -2.050189, -2.050189}; Max bound: {-2.050189, 2.050189, -0.990136}
child_l Min bound: {-2.050189, -2.050189, -2.050189}; Max bound: {-2.050189, 0.990136, -0.990136}
shape 7
child_r Min bound: {-2.050189, -2.050189, -2.050189}; Max bound: {-2.050189, 2.050189, -0.990136}
shape 16
child_r Min bound: {-2.050189, -2.050189, -2.050189}; Max bound: {-2.050189, 2.050189, 2.050189}
child_l Min bound: {-2.050189, 0.990136, -2.050189}; Max bound: {-2.050189, 2.050189, 2.050189}
child_l Min bound: {-2.050189, 0.990136, -2.050189}; Max bound: {-2.050189, 2.050189, 0.990136}
shape 8
child_r Min bound: {-2.050189, 0.990136, -2.050189}; Max bound: {-2.050189, 2.050189, 2.050189}
shape 17
child_r Min bound: {-2.050189, -2.050189, 0.990136}; Max bound: {-2.050189, 2.050189, 2.050189}
child_l Min bound: {-2.050189, -2.050189, 0.990136}; Max bound: {-2.050189, 2.050189, 2.050189}
shape 15
child_r Min bound: {-2.050189, -0.990136, 0.990136}; Max bound: {-2.050189, 2.050189, 2.050189}
shape 6
child_r Min bound: {-2.050189, -2.050189, -2.050189}; Max bound: {2.050189, 2.050189, 2.050189}
child_l Min bound: {-2.050189, -2.050189, -2.050189}; Max bound: {2.050189, -2.050189, 2.050189}
child_l Min bound: {-2.050189, -2.050189, -2.050189}; Max bound: {2.050189, -2.050189, 2.050189}
shape 2
child_r Min bound: {-2.050189, -2.050189, -2.050189}; Max bound: {2.050189, -2.050189, 2.050189}
shape 11
child_r Min bound: {-2.050189, -2.050189, -2.050189}; Max bound: {2.050189, 2.050189, 2.050189}
child_l Min bound: {-2.050189, -2.050189, -2.050189}; Max bound: {2.050189, 2.050189, -2.050189}
child_l Min bound: {-2.050189, -2.050189, -2.050189}; Max bound: {2.050189, 2.050189, -2.050189}
shape 4
child_r Min bound: {-2.050189, -2.050189, -2.050189}; Max bound: {2.050189, 2.050189, -2.050189}
shape 13
child_r Min bound: {-2.050189, -2.050189, -2.050189}; Max bound: {2.050189, 2.050189, 2.050189}
child_l Min bound: {-2.050189, -2.050189, -2.050189}; Max bound: {2.050189, 2.050189, 2.050189}
child_l Min bound: {-2.050189, -2.050189, 2.050189}; Max bound: {2.050189, 2.050189, 2.050189}
child_l Min bound: {-2.050189, -2.050189, 2.050189}; Max bound: {2.050189, 2.050189, 2.050189}
shape 1
child_r Min bound: {-2.050189, -2.050189, 2.050189}; Max bound: {2.050189, 2.050189, 2.050189}
shape 10
child_r Min bound: {-2.050189, 2.050189, -2.050189}; Max bound: {2.050189, 2.050189, 2.050189}
child_l Min bound: {-2.050189, 2.050189, -2.050189}; Max bound: {2.050189, 2.050189, 2.050189}
shape 0
child_r Min bound: {-2.050189, 2.050189, -2.050189}; Max bound: {2.050189, 2.050189, 2.050189}
shape 9
child_r Min bound: {2.050189, -2.050189, -2.050189}; Max bound: {2.050189, 2.050189, 2.050189}
child_l Min bound: {2.050189, -2.050189, -2.050189}; Max bound: {2.050189, 2.050189, 2.050189}
shape 3
child_r Min bound: {2.050189, -2.050189, -2.050189}; Max bound: {2.050189, 2.050189, 2.050189}
shape 12

Prepare 0.2.0 release

• Write more/better performance benchmarks
• Tag 0.2.0
• Release on crates.io
• Make a thread on reddit and ask for feedback

Null ray intersect with a flat AABB

Hello,

thank you for this useful crate :) It works great for my application, except for the following case. When intersecting a ray and a flat AABB, false is returned. For instance,

    let origin = Point3::<f64>::new(0.0, 0.0, 0.0);
    let direction = Vector3::<f64>::new(0.0, 0.0, 1.0);
    let ray = Ray::new(origin, direction);
    let min = Point3::<f64>::new(-1.0, -1.0, 1.0);
    let max = Point3::<f64>::new(1.0, 1.0, 1.0);
    let aabb = Aabb::with_bounds(min, max);
    assert!(ray.intersects_aabb(&aabb));

The last assertion fails, where I would have expected true (e.g. when bounding an axis-aligned triangular facet).

My apologies if this is the intended behaviour?

I am running on x86_64 Linux with version 0.9.0 (and default features, i.e. simd disabled).

Investigate using Bounding Interval Hierarchies

BIHs are similar to BVHs, but have interesting properties in terms of speed.

https://en.wikipedia.org/wiki/Bounding_interval_hierarchy

improvements

Thanks for maintaining this crate, I've been integrating it into a game I'm working on in Unity and in doing so I've added/am adding a bunch of things that I needed and was wondering how much of it you might be interested me trying to separate out for a PR.
The performance is amazing!

I've been implementing some new query shapes

• Sphere
• Capsule
• AABB
• OBB (almost)
• Segment (tbd)

In addition to those I've also been adding some new methods

• Add (add a new node to the bvh without a rebuild)
• Remove (remove a node without a rebuild)
• Rebuild (rebuild bvh but reuse the vector to reduce allocations)

I've also defined a C FFI so that it could be used outside of Rust code

My version is also 64bit because I needed the precision

If any of this stuff sounds like something you might be interested in a PR for let me know.

Migrate to GitHub Actions

BVH optimize panics when only one shape contained in it

I am getting this error when attempting to optimize with only one shape in the bvh:

attempt to subtract with overflow
thread 'sphere_intersector::tests::test_ray_intersect' panicked at 'attempt to subtract with overflow', /Users/tlaukkan/.cargo/registry/src/github.com-1ecc6299db9ec823/bvh-0.3.2/src/bvh/optimization.rs:144:43
stack backtrace:
0: backtrace::backtrace::libunwind::trace
at /Users/runner/.cargo/registry/src/github.com-1ecc6299db9ec823/backtrace-0.3.44/src/backtrace/libunwind.rs:86
1: backtrace::backtrace::trace_unsynchronized
at /Users/runner/.cargo/registry/src/github.com-1ecc6299db9ec823/backtrace-0.3.44/src/backtrace/mod.rs:66
2: std::sys_common::backtrace::_print_fmt
at src/libstd/sys_common/backtrace.rs:78
3: <std::sys_common::backtrace::_print::DisplayBacktrace as core::fmt::Display>::fmt
at src/libstd/sys_common/backtrace.rs:59
4: core::fmt::write
at src/libcore/fmt/mod.rs:1063
5: std::io::Write::write_fmt
at /rustc/4fb7144ed159f94491249e86d5bbd033b5d60550/src/libstd/io/mod.rs:1426
6: std::io::impls::<impl std::io::Write for alloc::boxed::Box>::write_fmt
at src/libstd/io/impls.rs:156
7: std::sys_common::backtrace::_print
at src/libstd/sys_common/backtrace.rs:62
8: std::sys_common::backtrace::print
at src/libstd/sys_common/backtrace.rs:49
9: std::panicking::default_hook::{{closure}}
at src/libstd/panicking.rs:204
10: std::panicking::default_hook
at src/libstd/panicking.rs:221
11: std::panicking::rust_panic_with_hook
at src/libstd/panicking.rs:470
12: rust_begin_unwind
at src/libstd/panicking.rs:378
13: std::panicking::begin_panic
14: std::panicking::begin_panic
15: bvh::bvh::optimization::::optimize
at /Users/tlaukkan/.cargo/registry/src/github.com-1ecc6299db9ec823/bvh-0.3.2/src/bvh/optimization.rs:144
16: intersect::sphere_intersector::SphereIntersector::optimize
at src/sphere_intersector.rs:111
17: intersect::sphere_intersector::tests::test_ray_intersect
at src/sphere_intersector.rs:192
18: intersect::sphere_intersector::tests::test_ray_intersect::{{closure}}
at src/sphere_intersector.rs:151
19: core::ops::function::FnOnce::call_once
at /rustc/4fb7144ed159f94491249e86d5bbd033b5d60550/src/libcore/ops/function.rs:232
20: <alloc::boxed::Box as core::ops::function::FnOnce>::call_once
at /rustc/4fb7144ed159f94491249e86d5bbd033b5d60550/src/liballoc/boxed.rs:1017
21: __rust_maybe_catch_panic
at src/libpanic_unwind/lib.rs:86
22: std::panicking::try
at /rustc/4fb7144ed159f94491249e86d5bbd033b5d60550/src/libstd/panicking.rs:281
23: std::panic::catch_unwind
at /rustc/4fb7144ed159f94491249e86d5bbd033b5d60550/src/libstd/panic.rs:394
24: test::run_test_in_process
at src/libtest/lib.rs:542
25: test::run_test::run_test_inner::{{closure}}
at src/libtest/lib.rs:451
note: Some details are omitted, run with RUST_BACKTRACE=full for a verbose backtrace.

BVHNode is Debug, but BVH itself is not

Hi, I'm curious - why isn't the Debug trait derived for the BVH struct? It contains only one member - a vector of BVHNode's which are Debug themselves, so could we make BVH Debug, too, or there is some reasoning against doing that? :) Thanks!

Next release

There are a lot of changes in the repository, but the last release is from 8 months ago. Can the current state be released as 0.7.3?

Refactor and split the `build()` function

Write a proper README.md with a nice full example on how to use this

Other intersection structures (plane, sphere)

Hey.

Thank you very much for making this. We have been creating a wrapper for this project for Babylonjs, and the results are just fantastic.

https://github.com/tlaukkan/rust-ray-intersect-js

I am wondering if you would like a bit of help with the BVH repo. I noticed that you set up a great structure for adding more intersection objects. If I write a plane, and sphere intercept structure, would you be open to merging them into the project?

Parallelize building

It should be possible to make the building parallel. Look into rayon (http://smallcultfollowing.com/babysteps/blog/2015/12/18/rayon-data-parallelism-in-rust/#rayons-core-primitive-join).

Refactor and split the `optimize()` function

Change benchmarks to either criterion or divan

The current benchmarks need nightly and they are kind of primitive. Using criterion or divan would be much better.

FlatNode's fields should be public.

Due to private fields and no access methods FlatNode cannot be used on GPU.

More general queries

Would it be possible to add queries that are not tied to ray intersection tests? Something like can I provide a sphere and get a list of potential collisions to test for?

Find a way of DRYing `UnitBox`

panicked at assertion failed: !child_l_aabb.is_empty()

Hi

I am building BVH consisting of triangles for ray casting. I am using the triangle code from testbase.rs. The crate versions are:

nalgebra = "0.20"
bvh = "0.3.2"

The code works with a simple box test case but when I try to load larger mesh with something like this I get the following error:

triangle #0 (0,0,0) (0,0,0) (0,0,0) 
triangle #1 (0,0,0) (0,0,0) (0,0,1) 

panicked at 'assertion failed: !child_l_aabb.is_empty()', <::std::macros::panic macros>:2:4

The problem seems to appear when there is triangle with all vertexes in same coordinates and another with one vertex translated only in one dimension.

It could be good idea to fail fast when dot (0 dimensional) or line (1 dimensional) shapes are added.

Kind regards,
Tommi

Iterator with tmin/tmax and ray shortening

Currently traverse() and traverse_iterator() visit every node along an infinite ray. The application however has information which could reduce traversal steps:

• Provide a tmin/tmax with the ray and test ray/AABB distance against this range.
• When the app is looking for the smallest t along the ray (common) it can shorten the ray during traversal tmax=min(tmax,t)

Implementing an iterator which supports tmin/tmax as well as making these mutable to shorten the ray during traversal would help performance in many apps.

Benchmark against other implementations

We should benchmark this against a few other implementations to figure out where we are:

• https://github.com/brandonpelfrey/Fast-BVH
• https://embree.github.io/
• https://github.com/rkruppe/beevage.rs
• https://github.com/ruuda/convector
• https://github.com/kvark/collision-rs/tree/master/src/dbvt
• https://github.com/lohedges/aabbcc
• https://github.com/sebcrozet/ncollide/tree/master/ncollide_geometry/partitioning

Outsource benches and tests to proper subdirs

See the official cargo layout. Keep in mind that only integrations tests should go to tests/ and not the unit tests.

Expose ray.inv_direction

ray.inv_direction is often used for intersection calculations after a bvh has trimmed the number of primitives to check. By exposing inv_direction it allows users to reuse the cached inv_direction within Ray for other purposes.