svenstaro / bvh

A fast BVH using SAH in rust

bvh

A crate which exports rays, axis-aligned bounding boxes, and binary bounding volume hierarchies.

About

This crate can be used for applications which contain intersection computations of rays with primitives. For this purpose a binary tree BVH (Bounding Volume Hierarchy) is of great use if the scene which the ray traverses contains a huge number of primitives. With a BVH the intersection test complexity is reduced from O(n) to O(log2(n)) at the cost of building the BVH once in advance. This technique is especially useful in ray/path tracers. For use in a shader this module also exports a flattening procedure, which allows for iterative traversal of the BVH.

It uses rayon by default to parallelize building the BVH.

Example

use bvh::aabb::{Aabb, Bounded};
use bvh::bounding_hierarchy::{BHShape, BoundingHierarchy};
use bvh::bvh::Bvh;
use bvh::ray::Ray;
use nalgebra::{Point3, Vector3};

let origin = Point3::new(0.0,0.0,0.0);
let direction = Vector3::new(1.0,0.0,0.0);
let ray = Ray::new(origin, direction);

struct Sphere {
    position: Point3<f32>,
    radius: f32,
    node_index: usize,
}

impl Bounded<f32, 3> for Sphere {
    fn aabb(&self) -> Aabb<f32, 3> {
        let half_size = Vector3::new(self.radius, self.radius, self.radius);
        let min = self.position - half_size;
        let max = self.position + half_size;
        Aabb::with_bounds(min, max)
    }
}

impl BHShape<f32, 3> for Sphere {
    fn set_bh_node_index(&mut self, index: usize) {
        self.node_index = index;
    }
    fn bh_node_index(&self) -> usize {
        self.node_index
    }
}

let mut spheres = Vec::new();
for i in 0..1000u32 {
    let position = Point3::new(i as f32, i as f32, i as f32);
    let radius = (i % 10) as f32 + 1.0;
    spheres.push(Sphere {
        position: position,
        radius: radius,
        node_index: 0,
    });
}

let bvh = Bvh::build_par(&mut spheres);
let hit_sphere_aabbs = bvh.traverse(&ray, &spheres);

Explicit SIMD

This crate features some manually written SIMD instructions, currently only for the x86_64 architecture. While nalgebra provides us with generic SIMD optimization (and it does a great job for the most part) - some important functions, such as ray-aabb-intersection have been optimized by hand.

The currently optimized intersections for ray-aabb are: Type: f32, Dimension: 2,3,4 Type: f64, Dimension: 2,3,4

To enable these optimziations, you must build with the nightly toolchain and enable the simd flag.

Optimization

This crate provides BVH updating, which is also called optimization. With BVH optimization you can mutate the shapes on which the BVH is built and update the tree accordingly without rebuilding it completely. This method is very useful when there are only very few changes to a huge scene. When the major part of the scene is static, it is faster to update the tree, instead of rebuilding it from scratch.

Drawbacks

First of all, optimizing is not helpful if more than half of the scene is not static. This is due to how optimizing takes place: Given a set of indices of all shapes which have changed, the optimize procedure tries to rotate fixed constellations in search for a better surface area heuristic (SAH) value. This is done recursively from bottom to top while fixing the AABBs in the inner nodes of the BVH. Which is why it is inefficient to update the BVH in comparison to rebuilding, when a lot of shapes have moved.

Another problem with updated BVHs is, that the resulting BVH is not optimal. Assume that the scene is composed of two major groups separated by a large gap. When one shape moves from one group to another, the updating procedure will not be able to find a sequence of bottom-up rotations which inserts the shape deeply into the other branch.

The following benchmarks are run with two different datasets:

• A randomly generated scene with unit sized cubes containing a total of (1200, 12000, and 120000 triangles).
• Sponza, a popular scene for benchmarking graphics engines.

All benchmarks were taken on a Ryzen 3900x.

All benchmarks unless otherwise noted were captured with the simd feature off.

Intersection via traversal of the list of triangles

test testbase::bench_intersect_120k_triangles_list                            ... bench:     570,717 ns/iter (+/- 21,689)
test testbase::bench_intersect_sponza_list                                    ... bench:     510,683 ns/iter (+/- 9,525)

// simd enabled
test testbase::bench_intersect_120k_triangles_list                            ... bench:     566,916 ns/iter (+/- 22,024)
test testbase::bench_intersect_sponza_list                                    ... bench:     518,821 ns/iter (+/- 12,191)

This is the most naive approach to intersecting a scene with a ray. It defines the baseline.

Intersection via traversal of the list of triangles with AABB checks

test testbase::bench_intersect_120k_triangles_list_aabb                       ... bench:     687,660 ns/iter (+/- 6,850)
test testbase::bench_intersect_sponza_list_aabb                               ... bench:     381,037 ns/iter (+/- 1,416)

// simd enabled
test testbase::bench_intersect_120k_triangles_list_aabb                       ... bench:     295,810 ns/iter (+/- 3,309)
test testbase::bench_intersect_sponza_list_aabb                               ... bench:     163,738 ns/iter (+/- 1,822)

AABB checks are cheap, compared to triangle-intersection algorithms. Therefore, preceeding AABB checks increase intersection speed by filtering negative results a lot faster.

Build of a BVH from scratch

test flat_bvh::bench::bench_build_1200_triangles_flat_bvh                     ... bench:     242,357 ns/iter (+/- 1,882)
test flat_bvh::bench::bench_build_12k_triangles_flat_bvh                      ... bench:   3,681,965 ns/iter (+/- 223,716)
test flat_bvh::bench::bench_build_120k_triangles_flat_bvh                     ... bench:  46,415,590 ns/iter (+/- 3,226,404)
test bvh::bvh_impl::bench::bench_build_1200_triangles_bvh                     ... bench:     239,473 ns/iter (+/- 2,456)
test bvh::bvh_impl::bench::bench_build_1200_triangles_bvh_rayon               ... bench:     123,387 ns/iter (+/- 9,427)
test bvh::bvh_impl::bench::bench_build_12k_triangles_bvh                      ... bench:   2,903,150 ns/iter (+/- 54,318)
test bvh::bvh_impl::bench::bench_build_12k_triangles_bvh_rayon                ... bench:   1,073,300 ns/iter (+/- 89,530)
test bvh::bvh_impl::bench::bench_build_120k_triangles_bvh                     ... bench:  37,390,480 ns/iter (+/- 2,789,280)
test bvh::bvh_impl::bench::bench_build_120k_triangles_bvh_rayon               ... bench:   8,935,320 ns/iter (+/- 1,780,231)
test bvh::bvh_impl::bench::bench_build_sponza_bvh                             ... bench:  23,828,070 ns/iter (+/- 1,307,461)
test bvh::bvh_impl::bench::bench_build_sponza_bvh_rayon                       ... bench:   4,764,530 ns/iter (+/- 950,640)

Flatten a BVH

test flat_bvh::bench::bench_flatten_120k_triangles_bvh                        ... bench:   9,806,060 ns/iter (+/- 1,771,861)

As you can see, building a BVH takes a long time. Building a BVH is only useful if the number of intersections performed on the scene exceeds the build duration. This is the case in applications such as ray and path tracing, where the minimum number of intersections is 1280 * 720 for an HD image.

Intersection via BVH traversal

test flat_bvh::bench::bench_intersect_1200_triangles_flat_bvh                 ... bench:         144 ns/iter (+/- 1)
test flat_bvh::bench::bench_intersect_12k_triangles_flat_bvh                  ... bench:         370 ns/iter (+/- 4)
test flat_bvh::bench::bench_intersect_120k_triangles_flat_bvh                 ... bench:         866 ns/iter (+/- 16)
test bvh::bvh_impl::bench::bench_intersect_1200_triangles_bvh                 ... bench:         146 ns/iter (+/- 2)
test bvh::bvh_impl::bench::bench_intersect_12k_triangles_bvh                  ... bench:         367 ns/iter (+/- 5)
test bvh::bvh_impl::bench::bench_intersect_120k_triangles_bvh                 ... bench:         853 ns/iter (+/- 12)
test bvh::bvh_impl::bench::bench_intersect_sponza_bvh                         ... bench:       1,381 ns/iter (+/- 20)
test ray::ray_impl::bench::bench_intersects_aabb                              ... bench:       4,404 ns/iter (+/- 17)

// simd enabled
test bvh::bvh_impl::bench::bench_intersect_1200_triangles_bvh                 ... bench:         121 ns/iter (+/- 2)
test bvh::bvh_impl::bench::bench_intersect_12k_triangles_bvh                  ... bench:         309 ns/iter (+/- 3)
test bvh::bvh_impl::bench::bench_intersect_120k_triangles_bvh                 ... bench:         749 ns/iter (+/- 15)
test bvh::bvh_impl::bench::bench_intersect_sponza_bvh                         ... bench:       1,216 ns/iter (+/- 16)
test ray::ray_impl::bench::bench_intersects_aabb                              ... bench:       2,447 ns/iter (+/- 18)

These performance measurements show that traversing a BVH is much faster than traversing a list.

Optimization

The benchmarks for how long it takes to update the scene also contain a randomization process which takes some time.

test bvh::optimization::bench::bench_update_shapes_bvh_120k_00p               ... bench:   1,057,965 ns/iter (+/- 76,098)
test bvh::optimization::bench::bench_update_shapes_bvh_120k_01p               ... bench:   2,535,682 ns/iter (+/- 80,231)
test bvh::optimization::bench::bench_update_shapes_bvh_120k_10p               ... bench:  18,840,970 ns/iter (+/- 3,432,867)
test bvh::optimization::bench::bench_update_shapes_bvh_120k_50p               ... bench:  76,025,200 ns/iter (+/- 3,899,770)
test bvh::optimization::bench::bench_randomize_120k_50p                       ... bench:   5,361,645 ns/iter (+/- 436,340)

This is the place where you have to differentiate between rebuilding the tree from scratch or trying to optimize the old one. These tests show the impact of moving around a particular percentage of shapes (10p => 10%). It is important to note that the randomization process here moves triangles around indiscriminately. This will also lead to cases where the BVH would have to be restructured completely.

Intersection after the optimization

These intersection tests are grouped by dataset and by the BVH generation method.

• _after_optimize uses a BVH which was kept up to date with calls to optimize, while
• _with_rebuild uses the same triangle data as _after_optimize, but constructs a BVH from scratch.

120K Triangles

test bvh::optimization::bench::bench_intersect_120k_after_update_shapes_00p   ... bench:         855 ns/iter (+/- 15)
test bvh::optimization::bench::bench_intersect_120k_after_update_shapes_01p   ... bench:         921 ns/iter (+/- 13)
test bvh::optimization::bench::bench_intersect_120k_after_update_shapes_10p   ... bench:       2,677 ns/iter (+/- 191)
test bvh::optimization::bench::bench_intersect_120k_after_update_shapes_50p   ... bench:       2,992 ns/iter (+/- 103)

test bvh::optimization::bench::bench_intersect_120k_with_rebuild_00p          ... bench:         852 ns/iter (+/- 13)
test bvh::optimization::bench::bench_intersect_120k_with_rebuild_01p          ... bench:         918 ns/iter (+/- 13)
test bvh::optimization::bench::bench_intersect_120k_with_rebuild_10p          ... bench:       1,920 ns/iter (+/- 266)
test bvh::optimization::bench::bench_intersect_120k_with_rebuild_50p          ... bench:       2,075 ns/iter (+/- 318)

Sponza

test bvh::optimization::bench::bench_intersect_sponza_after_update_shapes_00p ... bench:       2,023 ns/iter (+/- 52)
test bvh::optimization::bench::bench_intersect_sponza_after_update_shapes_01p ... bench:       3,444 ns/iter (+/- 120)
test bvh::optimization::bench::bench_intersect_sponza_after_update_shapes_10p ... bench:      16,873 ns/iter (+/- 2,123)
test bvh::optimization::bench::bench_intersect_sponza_after_update_shapes_50p ... bench:       9,075 ns/iter (+/- 486)

test bvh::optimization::bench::bench_intersect_sponza_with_rebuild_00p        ... bench:       1,388 ns/iter (+/- 46)
test bvh::optimization::bench::bench_intersect_sponza_with_rebuild_01p        ... bench:       1,529 ns/iter (+/- 102)
test bvh::optimization::bench::bench_intersect_sponza_with_rebuild_10p        ... bench:       1,920 ns/iter (+/- 120)
test bvh::optimization::bench::bench_intersect_sponza_with_rebuild_50p        ... bench:       2,505 ns/iter (+/- 88)

This set of tests shows the impact of randomly moving triangles around and producing degenerated trees. The 120K Triangles dataset has been updated randomly. The Sponza scene was updated using a method which has a maximum offset distance for shapes. This simulates a more realistic scenario.

We also see that the Sponza scene by itself contains some structures which can be tightly wrapped in a BVH. By mowing those structures around we destroy the locality of the triangle groups which leads to more branches in the BVH requiring a check, thus leading to a higher intersection duration.

Running the benchmark suite

The benchmark suite uses features from the test crate and therefore cannot be run on stable rust. Using a nightly toolchain, run cargo bench --features bench.

bvh's Issues

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.

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

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!

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

Migrate to GitHub Actions

Refactor and split the `build()` function

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?

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?

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.

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.

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

Find a way of DRYing `UnitBox`

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

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

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?

FlatNode's fields should be public.

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

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.

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.

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.

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.

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.