Tracing Boxes

This is my last post on ray tracing, and it’s on tracing boxes. Spheres alone are not all that fun and the infinite planes have the drawback of being...well infinite. Therefore, I decided to put boxes to my ray tracer. It is of course possible to use 12 triangles. This is a general solution but it is not exactly cost effective and moreover, it does not scale well to collision detection, where boxes are often used (I am working on some physics code too). I started my journey by searching the web and of course, Real-Time Collision Detection by Christer Ericson, which is probably the best book in its field. What I got was plenty of fast algorithms that only tell if the there is an intersection or not, some of which give the intersection position too. Also few algorithms that give the normal vector as well, but most of them did checking against all 6 planes and went through lots of boundary conditions. As a normal vector is needed in ray tracing for light calculation, I decided to make the best of the both worlds.
The idea is very simple. Use the fast algorithm to get the intersection position and then use that information to get the normal. Say we have an axis aligned unit cube centered at the origin, a point on it and a vector to that point. The surface normal at that point is in the direction in which the vector extends the most. In case it’s not immediately obvious, let’s take one side of the cube, say the one laying on the x=1 plane. The side can be defined as an intersection of the x=1 plane and the cone made of half-spaces defined by x>|y| and x>|z|, which is exactly the same as the original statement. So now we have three steps of the algorithm.

• First, calculate the position of the center of the box and calculate the vector from it to the point on the surface.
• Next, scale the vector into a unit cube, to cancel the scaling of the box along the axes.
  
• Finally, zero out the coordinates with smaller absolute value, and then normalize the resulting vector.

The first part of the algorithm, used to calculate the position of intersection, is taken straight from a text book on graphics. The relevant code from the Box class is below.

public class Box extends Traceable {

protected Vec3;
protected Vec3 max;

// Component-wise min
public static Vec3 min(Vec3 a, Vec3 b) {
return new Vec3( min(a.x, b.x),
               min(a.y, b.y),
               min(a.z, b.z));
}

// Component-wise max
public static Vec3 max(Vec3 a, Vec3 b) {
return new Vec3( max(a.x, b.x),
               max(a.y, b.y),
               max(a.z, b.z));
}

@Override
public IntersectionInfo intersect(Ray r) {
// Interval based test
Vec3 direction = new Vec3(r.direction);
direction.normalize();
//
Vec3 oneoverdir = new Vec3(1.0f / direction.x, 1.0f / direction.y, 1.0f / direction.z);
Vec3 tmin = min.minus(r.origin).times(oneoverdir);
Vec3 tmax = max.minus(r.origin).times(oneoverdir);
//
Vec3 realmin = min(tmax, tmin);
Vec3 realmax = max(tmax, tmin);
//
float minmax = min(min( realmax.x, realmax.y), realmax.z);
float maxmin = max(max( realmin.x, realmin.y), realmin.z);

if(minmax >= maxmin && maxmin > 0.0f) { // Have intersection
 // Get position
 float t = maxmin;
 Vec3 position = r.origin.add(direction.times(t));

 // Get normal
 // 1. Get vector to relative position
 Vec3 center = max.add( min ).times(0.5f);
Vec3 normal = position.minus(center);

 // 2. Scale to matching unit box
 normal.x /= max.x - min.x;
 normal.y /= max.y - min.y;
 normal.z /= max.z - min.z;

 // 3. Keep the largest axis
 if(Math.abs(normal.x) > Math.abs(normal.y)) {
    normal.y = 0.0f;
    if(Math.abs(normal.x) > Math.abs(normal.z))
       normal.z = 0;
    else
       normal.x = 0;
 } else {
    normal.x = 0;
    if(Math.abs(normal.y) > Math.abs(normal.z))
       normal.z = 0;
    else
       normal.y = 0;
 }
 // 4. Normalize to unit
 normal.normalize();
 return new IntersectionInfo(position, normal, t, this);
}
//
return new IntersectionInfo(false);
}
} // end class

This might not be the fastest algorithm, but it beats most that I have come across on the internet. Here is one very ugly image showing ray tracing of a box in room and some normal mapping. Also the scene from the post on ambient occlusion was modeled with some boxes and a sphere.

The algorithm assumes that the box is axis aligned. This is not really an issue, as you can always do the intersection in the local space of the box. Transform the ray to the local space of the box with the inverse of rotation matrix of the box, find the intersection and normal and transform them back to world space with the rotation matrix of the box. Just have in mind that if you have scaling and translation applied to the box, the direction of the ray and the normal of the surface need special care.