need help understanding ray AABB intersection

D1189cc75544eea31979c55b45fa72ef
0
broli86 101 Apr 15, 2008 at 07:28

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;
}

2 Replies

Please log in or register to post a reply.

64212d89ffc7e91ed54b96ebbe99bd05
0
hovermonkey 101 Apr 15, 2008 at 15:57

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.

F7a4a748ecf664f189bb704a660b3573
0
anubis 101 Apr 17, 2008 at 17:44

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;
}