Skip to main content
Game Development

Return to Answer

added 118 characters in body
Source Link
bobobobo
bobobobo
  • 17.2k
  • 10
  • 67
  • 99
bool AABB::intersects( const Ray& ray )
{      
  // This culls theEZ backcases: facesif first,the andray givesstarts youinside the answer with thebox, largestor validends tinside
  for( int i = 0 ;// ithe <box, 3then ;it i++definitely )
hits the {box.
   // intI'm o1using =this (code ifor +ray 1tracing )with %an 3octree,
 ; // i=0: o1=1, o2=2,so i=1:I o1=2,o2=0needed etc.
rays that start and intend o2within =an
 ( i// +octree 2node )to %COUNT 3as ;
hits.
    // min.x (NX) isYou possible,could PXmodify won'tthis betest hit.to (unlessray you'restarts inside theand box.ends outside)
    if( ray.direction.e[i] > 0 ) // CULLto BACKqualify FACE
as a hit if {
you wanted to NOT count totally realinternal trays
 = if( min.e[i] -containsIn( ray.startPos.e[i] ) /|| containsIn( ray.direction.e[i] ;

 getEndPoint() ) )
   // 1.return CHECKtrue VALID; T
     
  if(// BetweenIn(the t,algorithm 0says, ray.lengthfind )3 )t's,
    Vector t {;
       
  // 2.LARGEST CHECKt INis BOX
the only one we need to test if Vectorit's pton =the rayface.at( t ) ;
        if( BetweenInfor( pt.e[o1],int min.e[o1],i max.e[o1]= )0 &&; BetweenIn(i pt.e[o2],< min.e[o2],3 max.e[o2]; )i++ )
     {
    if( returnray.direction.e[i] true> ;0 ) // it's valid inCULL theBACK boxFACE
      }
    }
 t.e[i] = ( elsemin.e[i] if(- ray.directionstartPos.e[i] < 0 ) // maxray.x (PX) isdirection.e[i] possible;
    {else
      real t.e[i] = ( max.e[i] - ray.startPos.e[i] ) / ray.direction.e[i] ;
  }

  int mi = t.maxIndex() ;
  if( BetweenIn( t.e[mi], 0, ray.length ) ) // valid t
      {
        Vector pt = ray.at( t.e[mi] ) ; 

    // check it's in if(the BetweenInbox in other 2 dimensions
    int o1 = ( pt.e[o1],mi min.e[o1],+ max.e[o1]1 ) &&% BetweenIn(3 pt.e[o2]; // i=0: o1=1, min.e[o2]o2=2, max.e[o2]i=1: )o1=2,o2=0 )etc.
    int o2 = ( mi + return2 true) % 3 ; 

  // it's validreturn inBetweenIn( thept.e[o1], boxmin.e[o1], max.e[o1] ) &&
      }
    } BetweenIn( pt.e[o2], min.e[o2], max.e[o2] ) ;
  }

  return false ; // nothe ray did not hit the box.
}

bool AABB::intersects( const Ray& ray )
{      
  // This culls the back faces first, and gives you the answer with the largest valid t
  for( int i = 0 ; i < 3 ; i++ )
  {
    int o1 = ( i + 1 ) % 3 ; // i=0: o1=1, o2=2, i=1: o1=2,o2=0 etc.
    int o2 = ( i + 2 ) % 3 ;

    // min.x (NX) is possible, PX won't be hit. (unless you're inside the box.)
    if( ray.direction.e[i] > 0 ) // CULL BACK FACE
    {
      real t = ( min.e[i] - ray.startPos.e[i] ) / ray.direction.e[i] ;

      // 1. CHECK VALID T
      if( BetweenIn( t, 0, ray.length ) )
      {
        // 2. CHECK IN BOX
        Vector pt = ray.at( t ) ;
        if( BetweenIn( pt.e[o1], min.e[o1], max.e[o1] ) && BetweenIn( pt.e[o2], min.e[o2], max.e[o2] ) )
          return true ;  // it's valid in the box
      }
    }
    else if( ray.direction.e[i] < 0 ) // max.x (PX) is possible
    {
      real t = ( max.e[i] - ray.startPos.e[i] ) / ray.direction.e[i] ;
      if( BetweenIn( t, 0, ray.length ) ) // valid t
      {
        Vector pt = ray.at( t ) ;
        if( BetweenIn( pt.e[o1], min.e[o1], max.e[o1] ) && BetweenIn( pt.e[o2], min.e[o2], max.e[o2] ) )
          return true ;  // it's valid in the box
      }
    }
  }

  return false ; // no hit.
}

bool AABB::intersects( const Ray& ray )
{
  // EZ cases: if the ray starts inside the box, or ends inside
  // the box, then it definitely hits the box.
  // I'm using this code for ray tracing with an octree,
  // so I needed rays that start and end within an
  // octree node to COUNT as hits.
  // You could modify this test to (ray starts inside and ends outside)
  // to qualify as a hit if you wanted to NOT count totally internal rays
  if( containsIn( ray.startPos ) || containsIn( ray.getEndPoint() ) )
    return true ; 
 
  // the algorithm says, find 3 t's,
  Vector t ;
 
  // LARGEST t is the only one we need to test if it's on the face.
  for( int i = 0 ; i < 3 ; i++ )
  {
    if( ray.direction.e[i] > 0 ) // CULL BACK FACE
      t.e[i] = ( min.e[i] - ray.startPos.e[i] ) / ray.direction.e[i] ;
    else
      t.e[i] = ( max.e[i] - ray.startPos.e[i] ) / ray.direction.e[i] ;
  }

  int mi = t.maxIndex() ;
  if( BetweenIn( t.e[mi], 0, ray.length ) )
  {
    Vector pt = ray.at( t.e[mi] ) ; 

    // check it's in the box in other 2 dimensions
    int o1 = ( mi + 1 ) % 3 ; // i=0: o1=1, o2=2, i=1: o1=2,o2=0 etc.
    int o2 = ( mi + 2 ) % 3 ; 

    return BetweenIn( pt.e[o1], min.e[o1], max.e[o1] ) &&
           BetweenIn( pt.e[o2], min.e[o2], max.e[o2] ) ;
  }

  return false ; // the ray did not hit the box.
}
added 1431 characters in body
Source Link
bobobobo
bobobobo
  • 17.2k
  • 10
  • 67
  • 99

My implementation:

bool AABB::intersects( const Ray& ray )
{      
  // This culls the back faces first, and gives you the answer with the largest valid t
  for( int i = 0 ; i < 3 ; i++ )
  {
    int o1 = ( i + 1 ) % 3 ; // i=0: o1=1, o2=2, i=1: o1=2,o2=0 etc.
    int o2 = ( i + 2 ) % 3 ;

    // min.x (NX) is possible, PX won't be hit. (unless you're inside the box.)
    if( ray.direction.e[i] > 0 ) // CULL BACK FACE
    {
      real t = ( min.e[i] - ray.startPos.e[i] ) / ray.direction.e[i] ;

      // 1. CHECK VALID T
      if( BetweenIn( t, 0, ray.length ) )
      {
        // 2. CHECK IN BOX
        Vector pt = ray.at( t ) ;
        if( BetweenIn( pt.e[o1], min.e[o1], max.e[o1] ) && BetweenIn( pt.e[o2], min.e[o2], max.e[o2] ) )
          return true ;  // it's valid in the box
      }
    }
    else if( ray.direction.e[i] < 0 ) // max.x (PX) is possible
    {
      real t = ( max.e[i] - ray.startPos.e[i] ) / ray.direction.e[i] ;
      if( BetweenIn( t, 0, ray.length ) ) // valid t
      {
        Vector pt = ray.at( t ) ;
        if( BetweenIn( pt.e[o1], min.e[o1], max.e[o1] ) && BetweenIn( pt.e[o2], min.e[o2], max.e[o2] ) )
          return true ;  // it's valid in the box
      }
    }
  }

  return false ; // no hit.
}

My implementation:

bool AABB::intersects( const Ray& ray )
{      
  // This culls the back faces first, and gives you the answer with the largest valid t
  for( int i = 0 ; i < 3 ; i++ )
  {
    int o1 = ( i + 1 ) % 3 ; // i=0: o1=1, o2=2, i=1: o1=2,o2=0 etc.
    int o2 = ( i + 2 ) % 3 ;

    // min.x (NX) is possible, PX won't be hit. (unless you're inside the box.)
    if( ray.direction.e[i] > 0 ) // CULL BACK FACE
    {
      real t = ( min.e[i] - ray.startPos.e[i] ) / ray.direction.e[i] ;

      // 1. CHECK VALID T
      if( BetweenIn( t, 0, ray.length ) )
      {
        // 2. CHECK IN BOX
        Vector pt = ray.at( t ) ;
        if( BetweenIn( pt.e[o1], min.e[o1], max.e[o1] ) && BetweenIn( pt.e[o2], min.e[o2], max.e[o2] ) )
          return true ;  // it's valid in the box
      }
    }
    else if( ray.direction.e[i] < 0 ) // max.x (PX) is possible
    {
      real t = ( max.e[i] - ray.startPos.e[i] ) / ray.direction.e[i] ;
      if( BetweenIn( t, 0, ray.length ) ) // valid t
      {
        Vector pt = ray.at( t ) ;
        if( BetweenIn( pt.e[o1], min.e[o1], max.e[o1] ) && BetweenIn( pt.e[o2], min.e[o2], max.e[o2] ) )
          return true ;  // it's valid in the box
      }
    }
  }

  return false ; // no hit.
}
Source Link
bobobobo
bobobobo
  • 17.2k
  • 10
  • 67
  • 99

Nobody described the algorithm here, but the Graphics Gems algorithm is simply:

  1. Using your ray's direction vector, determine which 3 of the 6 candidate planes would be hit first. If your (unnormalized) ray direction vector is (-1, 1, -1), then the 3 planes that are possible to be hit are +x, -y, and +z.

  2. Of the 3 candidate planes, do find the t-value for the intersection for each. Accept the plane that gets the largest t value as being the plane that got hit, and check that the hit is within the box. The diagram in the text makes this clear:

enter image description here