svenstaro / bvh Goto Github PK

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

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.

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?

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.

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.

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.

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

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?

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.

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

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

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

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

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

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!

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

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?

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

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.

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).