Help with AABB collision detection.

Does anyone know how to use axis aligned bouding boxes w/ collision detection? I want to know when a line segment intersects with a box. The best thing I could find was one Gameasutra but it doesn't have enough documentation for me to figure out how to use it with LSL.

http://www.gamasutra.com/features/19991018/Gomez_6.htm

const bool AABB_LineSegmentOverlap
(


const VECTOR& l, //line direction
const VECTOR& mid, //midpoint of the line 
// segment
const SCALAR hl, //segment half-length
const AABB& b //box

)

The part I'm totally stumped on is the AABB data type. I assume it's just two vectors really, one is the center of the box, the other are the x/y/z extents of the box. Just not having any luck with this though.

Hi,

I can't read the article on gamasutra because one has to register first.

AABB is an acronym for "axis aligned bounding box" and consists of the minimum and maximum point in 3d space (spanning a box).

C source in it's entirety. I've converted this to LSL the best I could but the source is @ home. I still have problems with the AABB type.

From this function, it looks like it's a mid-point plus vectors for the extent of each side of the box. I don't see how it could be min/max points...

#include "aabb.h"

const bool AABB_LineSegmentOverlap
(


const VECTOR& l, //line direction
const VECTOR& mid, //midpoint of the line 
// segment
const SCALAR hl, //segment half-length
const AABB& b //box

)

{


/* ALGORITHM: Use the separating axis 
theorem to see if the line segment 
and the box overlap. A line 
segment is a degenerate OBB. */

const VECTOR T = b.P - mid;
VECTOR v;
SCALAR r;

//do any of the principal axes
//form a separating axis?

if( fabs(T.x) > b.E.x + hl*fabs(l.x) )
return false;

if( fabs(T.y) > b.E.y + hl*fabs(l.y) )
return false;

if( fabs(T.z) > b.E.z + hl*fabs(l.z) )
return false;

/* NOTE: Since the separating axis is
perpendicular to the line in these
last four cases, the line does not
contribute to the projection. */

//l.cross(x-axis)?

r = b.E.y*fabs(l.z) + b.E.z*fabs(l.y);

if( fabs(T.y*l.z - T.z*l.y) > r )
return false;

//l.cross(y-axis)?

r = b.E.x*fabs(l.z) + b.E.z*fabs(l.x);

if( fabs(T.z*l.x - T.x*l.z) > r )
return false;

//l.cross(z-axis)?

r = b.E.x*fabs(l.y) + b.E.y*fabs(l.x);

if( fabs(T.x*l.y - T.y*l.x) > r )
return false;

return true;


}

It seems to me:

They are using three quantities to represent the line:
l, the line direction, this is probably a normalized vector, and just gives the direction of the line segment

mid, the midpoint of the line segment, this positions the line segement in space

h1, half the length of the line segement, so the line segment will continue for h1 units away from mid in either direction.

To put it another way, the two endpoints of the line segment are:
mid + (l * h1)
mid - (l * h1)

(for those just joining our program, a line is infinite in both directions, a line segment is a part of a line)

Just skimming the code, I think Jack's right, the AABB type is a point (P) and extent , two vectors, the point being a corner of the box, then the extent being how far the box goes along each axis from the point.

So, if I were converting this to LSL, I would just use two vectors, something like
vector vBBOrigin; // = b.P in gamasutra code
vector vBBExtents; // = b.E in gamasutra code

PS, no decent human being uses 'l' as a variable name, it looks too much like 1

Here's a function I found on www.GarageGames.com

It looks easier to work with than the other one, however I still don't understand the "box" parameter. This function only looks at the x values for min and max. Wouldn't it need to look at y & z as well? What points do Box.min and Box.max represent?

typedef float F32;
struct Point {    
  F32 x,y,z;
};

struct Box {    
  Point min,max;
};

bool intersect(const Point &start, const Point &end, const &box, F32 *time) {   
 F32 st,et,fst = 0,fet = 1;
 F32 const *bmin = &box.min.x;
 F32 const *bmax = &box.max.x;
 F32 const *si = &start.x;
 F32 const *ei = &end.x;  
 for (int i = 0; i < 3; i++) {     
   if (*si < *ei) {         
      if (*si > *bmax || *ei < *bmin) 
        return false;

      F32 di = *ei - *si;
      st = (*si < *bmin)? (*bmin - *si) / di: 0;
      et = (*ei > *bmax)? (*bmax - *si) / di: 1;
    } else {
      if (*ei > *bmax || *si < *bmin) 
        return false;         
      F32 di = *ei - *si;
      st = (*si > *bmax)? (*bmax - *si) / di: 0;
      et = (*ei < *bmin)? (*bmin - *si) / di: 1;
    }

    if (st > fst) fst = st;
    if (et < fet) fet = et;      
    if (fet < fst) return false;      
    bmin++; bmax++;      
    si++; ei++;  
}   

*time = fst;
return true;

}

That's what I was thought.. I made a pretty large box, 4mx4mx4m but could never get it to detect intersection in a predictable way. Sometime it was working, but other times it would register an intersect when there was none. Maybe I messed up my line segment direction...

I'm going to try the other function I found but I think it uses a different format to define the box. min and max points, but I don't know if it's min/max in a corner of the box, middle of the box.. no idea.

Too bad this isn't built into LSL.

I am shipping the people at Garage Games a big box of source code comments, sice they clearly have run out.

Note:
F32 const *bmin = &box.min.x;
F32 const *bmax = &box.max.x;

These are pointers to the values in the box stucture then at the bottom of the loop:
bmin++; bmax++;
The loop (for i = 0 to 2) iterates over the x, y and z fields of the box.min and box.max structures.

So they are doing some highly questionable C pointer math. I wrote something about this on the Wiki.

Ahh! Damn pointer math. That makes sense now. Thx Wed's!

He describes the function a bit but I didnt see anything about pointer math in his description:

http://www.garagegames.com/index.php?sec=mg&mod=resource&page=view&qid=309

Here is the working line-segment vs aabb function in LSL for anyone who wants it. Got it working finally.

// start - line segment start point
// end - line segment end point
// boxmin - lower corner aabb
// boxmin - upper corner aabb
// returns true if line segment intersects with aabb
integer intersect(vector start, vector end, vector boxmin, vector boxmax) {   
    float st;
    float et;
    float fst;
    float fet = 1;
    float si;
    float ei;
    float bmin;
    float bmax;
    float time;
    
    bmin = boxmin.x;
    bmax = boxmax.x;
     
    si = start.x;
    ei = end.x;
    
    if (si < ei) {         
      if ((si > bmax) || (ei < bmin))  {
        return FALSE;
      }

      float di = ei - si;
      if (si < bmin) {
          st = (bmin - si) / di;
      } else {
          st = 0;
      }
      
      if (ei > bmax) {
          et = (bmax - si) / di;
      } else {
          et = 1;
      }      
      
    } else {
      if ((ei > bmax) || (si < bmin)) {
        return FALSE;         
      }
      
      float di = ei - si;
      if (si > bmax) {
          st = (bmax - si) / di;
      } else {
          st = 0;
      }
      
      if (ei < bmin) {
          et = (bmin - si) / di;
      } else {
          et = 1;
      }      
    }

    if (st > fst) {
        fst = st;
    }
    if (et < fet) {
        fet = et;      
    }
    if (fet < fst) {
        return FALSE;      
    }
    
    bmin = boxmin.y;
    bmax = boxmax.y;
     
    si = start.y;
    ei = end.y;
    
    if (si < ei) {         
      if ((si > bmax) || (ei < bmin))  {
        return FALSE;
      }

      float di = ei - si;
      if (si < bmin) {
          st = (bmin - si) / di;
      } else {
          st = 0;
      }
      
      if (ei > bmax) {
          et = (bmax - si) / di;
      } else {
          et = 1;
      }      
      
    } else {
      if ((ei > bmax) || (si < bmin)) {
        return FALSE;         
      }
      
      float di = ei - si;
      if (si > bmax) {
          st = (bmax - si) / di;
      } else {
          st = 0;
      }
      
      if (ei < bmin) {
          et = (bmin - si) / di;
      } else {
          et = 1;
      }      
    }

    if (st > fst) {
        fst = st;
    }
    if (et < fet) {
        fet = et;      
    }
    if (fet < fst) {
        return FALSE;      
    }
    
    bmin = boxmin.z;
    bmax = boxmax.z;
     
    si = start.z;
    ei = end.z;
    
    if (si < ei) {         
      if ((si > bmax) || (ei < bmin))  {
        return FALSE;
      }

      float di = ei - si;
      if (si < bmin) {
          st = (bmin - si) / di;
      } else {
          st = 0;
      }
      
      if (ei > bmax) {
          et = (bmax - si) / di;
      } else {
          et = 1;
      }      
      
    } else {
      if ((ei > bmax) || (si < bmin)) {
        return FALSE;         
      }
      
      float di = ei - si;
      if (si > bmax) {
          st = (bmax - si) / di;
      } else {
          st = 0;
      }
      
      if (ei < bmin) {
          et = (bmin - si) / di;
      } else {
          et = 1;
      }      
    }

    if (st > fst) {
        fst = st;
    }
    if (et < fet) {
        fet = et;      
    }
    if (fet < fst) {
        return FALSE;      
    }
    

    time = fst;

    return TRUE;
}

the time variable at the end isn't returned but it lets you calculate the intersection point. the intersection point is :

start + (end - start) * time


eg axis aligned bb :

p = llDetectedPos(0);
vector minB = <p.x - 2,  p.y - 2, p.z - 2>;
vector maxB = <p.x + 2, p.y + 2, p.z + 4>;