Raytracing object matrix transformations with bounding volume hierarchies

Question

I've run into an interesting issue in my ray tracer that I am developing. The objects in my scene are stored in a bounding volume hierarchy. Each individual object is encapsulated in a bounding box at a leaf node of the hierarchy and has a matrix transformation associated with it.

Now, the way I have been taught to do matrix transformations of objects in raytracing is to transform each ray by the inverse of the object's matrix and then see if there is an intersection. In pseudocode (and without a bvh tree) it would look like this:

float minimum_distance = FLOAT_MAX;
Intersection closestHit = null;

for(each object in scene)
{
    Matrix transform = object.transform();
    Matrix inverse = transform.inverse();
    Ray transRay = transformRay(eyeRay, inverse);
    Intersection hit = CollisionTest(transRay, object);
    if(intersectionFound)
    {
        if(hit.distance() < minimum_distance)
        {
            closestHit = hit;
        }
    }
}
Shade(closestHit);

Since there is no bounding structure to the scene objects, you can loop through each one and transform the ray by the matrix of each object to test. But now imagine the following scenario with a BVH tree:

                                 ROOT
                        Left Box       Right Box
                           |                |
                           V                V
                         object A          object B

Now lets say we have an eyeRay that intersections only the right box. The ray will only check for intersections objects that are in the right box and completely ignore any objects in the left box (which is the main advantage of putting your objects in a hierarchy like this...as to avoid unnecessary checking).

However, object A in the left box has a scaling transform associated with it that when applied would stretch object A such that it crosses over into right box territory. If the ray were allowed to check itself against every object in the scene, you would find that when the inverse of the transform of object A is applied to the ray, an intersection would be found. However, the ray will never be allowed to do that transformation check because the untransformed object A sits squarely in the left box. Thus, the intersection will be missed and the result would be a partially rendered object A.

So my question is how would I resolve this issue? I don't want to give up using a bounding volume hierarchy but I don't see how it is compatible with the above algorithm of inverting the ray. Any thoughts?

Answer 1

First note, there are a number of BVH Tree specializations. The more common ones exclude intersection of bounding volumes from neighbor nodes (i.e. Left Box cannot intersect Right Box).

Now the whole point of a bounding volume is that it bounds the underlying object. So if that object has a transform that scales it past the bounding volume, then that means the bounding volume is NOT a proper bounding volume (BV).

Two ways to fix this, if the bounding volume was computed on untrasformed geometry, then when checking ray-boundingVolume intersection, first transform the BV to the same coordinate system as the object.

Depending on what you're doing, a more efficient way may be to compute the BV directly on the transformed object (Scaled, translated, etc) object. This way you don't need to transform the box (or the ray) when doing initial ray-BV check.

Hope that helps.