Trouble Figuring out BVT & RayIntersectionCostFn

ncollide
1

If anyone is willing to pull down this commit and help me out, that would be greatly appreciated. https://github.com/dannyfritz/ray-tracing-in-one-weekend-rs/tree/ceaa816efd85b9b1b87aa2751ca936da79873670

I’ve been working on a ray tracer. After doing some profiling, I noticed my ray collision detection was very slow. I decided it would be a good idea to use ncollide3d’s BVT struct. It seems I can create the BVT and pass it around, but when I invoke RayIntersectionCostFn with bestFirstSearch, it produces an error:

C:\Users\danny\Dev\ray-tracing-in-one-weekend-rs (ncollide)
λ cargo +nightly check
    Checking ray-tracing-in-one-weekend-rs v0.1.0 (file:///C:/Users/danny/Dev/ray-tracing-in-one-weekend-rs)
error[E0277]: the trait bound `std::rc::Rc<dyn material::Material>: ncollide3d::query::RayCast<f32>` is not satisfied
  --> src\main.rs:55:17
   |
55 |     match world.best_first_search(&mut visitor) {
   |                 ^^^^^^^^^^^^^^^^^ the trait `ncollide3d::query::RayCast<f32>` is not implemented for `std::rc::Rc<dyn material::Material>`
   |
   = note: required because of the requirements on the impl of `ncollide3d::partitioning::BVTCostFn<f32, std::rc::Rc<dyn material::Material>, ncollide3d::bounding_volume::BoundingSphere<f32>>` for `ncollide3d::query::RayIntersectionCostFn<'_, f32>`

error: aborting due to previous error

For more information about this error, try `rustc --explain E0277`.
error: Could not compile `ray-tracing-in-one-weekend-rs`.

To learn more, run the command again with --verbose.

C:\Users\danny\Dev\ray-tracing-in-one-weekend-rs (ncollide)
2

As stated by the compilation error, the issue here is that the RayCast trait (from ncollide3d) is not implemented for your Rc<dyn Material> type. So you will have to add this implementation to fix the error.

RayCast is necessary so that the best-first-search knows how to cast rays on your objects. More specifically, this requirement comes from the BVTCostFn implementation of RayIntersectionCostFn (see there) needed by best_first_search.

1 Like
3

Oh I see. So in BVT<B, BV>:

  • B is the shape
  • BV is the bounding volume

Thanks for the info, I can take it from here. :+1: I think I was really just confused by what B and BV meant.

Ray casting with BV I’m assuming is a cheaper calculation and ray casting with B is more expensive.

In this example I was expecting to see something like impl RayCast for SceneNode.

4

Ray casting with BV I’m assuming is a cheaper calculation and ray casting with B is more expensive.

Yes, the BVT traversal casts rays on the bounding volumes first to avoid as much cast on shapes as possible.

In this example I was expecting to see something like impl RayCast for SceneNode.

The linked example actually uses another alternative. Instead of implementing the RayCast trait, which is required by the RayIntersectionCostFn, we call .best_first_search with a custom cost function (or visitor as you call it) dedicated to SceneNode. Such a custom cost function implements the BVTCostFn trait. See this for the case of nrays.

Using a custom cost function can be more flexible in some situations as this can return a custom result type (specified by the BVTCostFn::UserData associated type) instead of just the ray/shape intersection point.

5

I did get BVT working and it gave me a 100x speed bump over my naive implementation. :+1:

6

Is this line a bug in nrays? Seems the BoundingVolume gets misaligned from the Shape if you rotate a translated Shape.

Specifically the &Isometry::identity() part of the line.

UPDATE:
I figured it out, you’re using BoundingSphere so rotation didn’t matter. I’m using AABB so it did.

7

I am actually using AABBs. All the bounding volumes on a BVT should be expressed in the same coordinate system. That’s why in nrays shapes transforms are already taken into account when creating the AABBs there to compute them in world-space.

The construction of a BVT requires merging some bounding volumes so they have to be expressed in the same coordinate system.