need help understanding ray AABB intersection

[broli86]

I have written some code based on a pseudocode I saw on internet but I just couldn't understand the algorithm well. Can anyone please explain it to me ? I specifically do not understadn the purpose of tnear and tfar. Here's my code btw :


bool ray_aabb_intersection(ray r , vector maxB, vector minB, double *tnear, double *tfar)
{
double t1, t2;
*tnear = -DBL_MAX;
*tfar = DBL_MAX;

if(r.origin.x == 0)
{
if(r.origin.x < minB.x || r.origin.x > maxB.x)
return FALSE;
}
else
{
t1 = (minB.x - r.origin.x)/ r.d.x;
t2 = (maxB.x - r.origin.x)/ r.d.x;
if(t1 > t2)
swap(&t1, &t2);
if(t1 >* tnear)
*tnear = t1;
if(t2 < *tfar)
*tfar = t2;
if(*tnear > *tfar)
return FALSE;
if(*tfar < 0)
return FALSE;
}

if(r.origin.y == 0)
{
if(r.origin.y < minB.y || r.origin.y > maxB.y)
return FALSE;
}
else
{
t1 = (minB.y - r.origin.y)/ r.d.y;
t2 = (maxB.y - r.origin.y)/ r.d.y;
if(t1 > t2)
swap(&t1, &t2);
if(t1 > *tnear)
*tnear = t1;
if(t2 < *tfar)
*tfar = t2;
if(*tnear > *tfar)
return FALSE;
if(*tfar < 0)
return FALSE;
}

if(r.origin.z == 0)
{
if(r.origin.z < minB.z || r.origin.z > maxB.z)
return FALSE;
}
else
{
t1 = (minB.z - r.origin.z)/ r.d.z;
t2 = (maxB.z - r.origin.z)/ r.d.z;
if(t1 > t2)
swap(&t1, &t2);
if(t1 > *tnear)
*tnear = t1;
if(t2 < *tfar)
*tfar = t2;
if(*tnear > *tfar)
return FALSE;
if(*tfar < 0)
return FALSE;
}

return TRUE;
}

[hovermonkey]

Imagine your ray being a point travelling through space such that at time 0 it is at position r.origin, and every 1 unit of time it moves the vector r.d.
so pos = r.origin + (r.d * time), ie pos.x = r.origin.x + (r.d.x * time) etc.

Your bounding box is the intersection of six halfspaces
(when a plane splits space into two, the volume each side of the plane is called a halfspace) - these are represented by these equations
x > minB.x, x < maxB.x, y > minB.y, y < maxB.y, z > minB.z, z < maxB.z

What this code does is calculate the "time" when x is between minB.x and maxB.x, then calculate the time when y is between minB.y and minB.y and ditto for z. These are calculated as the interval t1 to t2.
Then tnear and tfar are updated as the 1D intersection of these intervals.

The if (r.origin.x == 0) bit is wrong I think, I believe it should be
if (r.d.x == 0) and so on.

This checks if the ray is not moving in the x direction, and if so it is either always inside the x halfspaces, or never. If never, we return FALSE as the test cannot be true.

I tend to remove the divide from the test and keep separate numerators and denominators for tNear and tFar until the end as it avoids math errors when elements of r.d are very close to zero.

[anubis]

here is an implementation that is a little more compact


bool aabb::clip_ray_segment(const ray& ray, float& tmin, float& tmax)
{
float tmpa, tmpb;
point3 ext = position + size;

for(unsigned int i=0; i<3; ++i){

float ood = 1.0f / ray.direction.v[i];
if(ood >= 0.0f){

tmpa = (position.v[i] - ray.origin.v[i]) * ood;
tmpb = (ext.v[i] - ray.origin.v[i]) * ood;
}
else {

tmpa = (ext.v[i] - ray.origin.v[i]) * ood;
tmpb = (position.v[i] - ray.origin.v[i]) * ood;
}

if(tmin > tmax){

return false;
}
if(tmpa > tmin){ tmin = tmpa; }
if(tmpb < tmax){ tmax = tmpb; }
}

return true;
}