Iterator with tmin/tmax and ray shortening

[mdesmedt]

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.

[svenstaro]

Is this a dup of #56?

[mdesmedt]

Is this a dup of #56?

I don't believe so. #56 asks for "what is the closest object/s in the BVH to arbitrary points".

This request is mostly for adding ray shortening to the traversal. It could look something like:

let iter = bvh.traverse_iterator(ray)
for shape in iter {
    let hitinfo = do_full_intersection(ray, shape);
    if hitinfo.hit {
        iter.shorten_ray(hitinfo.t);
    }
}

[mdesmedt]

I gave this some thought. I think the only way to safely do this is to pass an Rc<RefCell<Ray>> to the iterator, which adds a lot of overhead during traversal. And computing t per box is also extra cycles. So unless we add unsafe code (not a fan) or can think of another approach this is probably not worth it. Some form of SIMD is probably still the best option for perf gain.

[tavianator]

And computing t per box is also extra cycles

That's not really true, the slab method computes t anyway.

[finnbear]

As of #128, users can almost do something like this:

struct ShorteningRay {
    inner: Ray<f32, _>,
    max_t: Cell<f32>,
}

impl IntersectsAabb for ShorteningRay {
    fn intersects_aabb(&self, aabb: &Aabb<f32, _>) -> bool {
       let (nearest_t, _) = self.inner.intersection_slice_for_aabb(aabb);
       if nearest_t == -1.0 || nearest_t > self.max_t.get() {
            return false;
       }
       self.max_t.set(self.max_t.get().min(nearest_t));
       true
   }
}

bvh.traverse(&ShorteningRay{...}, ...);

This could easily be adapted to filter by an immutable tmax threshold.

The only problem is that intersects_aabb doesn't know whether it is intersecting an internal node AABB or a leaf node shape AABB, leading self.max_t to be reduced prematurely.