Movement and Collision with AABB
- by Jeremy Giberson
I'm having a little difficulty figuring out the following scenarios.
http://i.stack.imgur.com/8lM6i.png
In scenario A, the moving entity has fallen to (and slightly into the floor). The current position represents the projected position that will occur if I apply the acceleration & velocity as usual without worrying about collision. The Next position, represents the corrected projection position after collision check. The resulting end position is the falling entity now rests ON the floor--that is, in a consistent state of collision by sharing it's bottom X axis with the floor's top X axis.
My current update loop looks like the following:
// figure out forces & accelerations and project an objects next position
// check collision occurrence from current position -> projected position
// if a collision occurs, adjust projection position
Which seems to be working for the scenario of my object falling to the floor. However, the situation becomes sticky when trying to figure out scenario's B & C.
In scenario B, I'm attempt to move along the floor on the X axis (player is pressing right direction button) additionally, gravity is pulling the object into the floor. The problem is, when the object attempts to move the collision detection code is going to recognize that the object is already colliding with the floor to begin with, and auto correct any movement back to where it was before.
In scenario C, I'm attempting to jump off the floor. Again, because the object is already in a constant collision with the floor, when the collision routine checks to make sure moving from current position to projected position doesn't result in a collision, it will fail because at the beginning of the motion, the object is already colliding.
How do you allow movement along the edge of an object? How do you allow movement away from an object you are already colliding with.
Extra Info
My collision routine is based on AABB sweeping test from an old gamasutra article, http://www.gamasutra.com/view/feature/3383/simple_intersection_tests_for_games.php?page=3
My bounding box implementation is based on top left/bottom right instead of midpoint/extents, so my min/max functions are adjusted. Otherwise, here is my bounding box class with collision routines:
public class BoundingBox {
public XYZ topLeft;
public XYZ bottomRight;
public BoundingBox(float x, float y, float z, float w, float h, float d)
{
topLeft = new XYZ();
bottomRight = new XYZ();
topLeft.x = x;
topLeft.y = y;
topLeft.z = z;
bottomRight.x = x+w;
bottomRight.y = y+h;
bottomRight.z = z+d;
}
public BoundingBox(XYZ position, XYZ dimensions, boolean centered)
{
topLeft = new XYZ();
bottomRight = new XYZ();
topLeft.x = position.x;
topLeft.y = position.y;
topLeft.z = position.z;
bottomRight.x = position.x + (centered ? dimensions.x/2 : dimensions.x);
bottomRight.y = position.y + (centered ? dimensions.y/2 : dimensions.y);
bottomRight.z = position.z + (centered ? dimensions.z/2 : dimensions.z);
}
/**
* Check if a point lies inside a bounding box
* @param box
* @param point
* @return
*/
public static boolean isPointInside(BoundingBox box, XYZ point)
{
if(box.topLeft.x <= point.x && point.x <= box.bottomRight.x
&& box.topLeft.y <= point.y && point.y <= box.bottomRight.y
&& box.topLeft.z <= point.z && point.z <= box.bottomRight.z)
return true;
return false;
}
/**
* Check for overlap between two bounding boxes using separating axis theorem
* if two boxes are separated on any axis, they cannot be overlapping
* @param a
* @param b
* @return
*/
public static boolean isOverlapping(BoundingBox a, BoundingBox b)
{
XYZ dxyz = new XYZ(b.topLeft.x - a.topLeft.x, b.topLeft.y - a.topLeft.y, b.topLeft.z - a.topLeft.z);
// if b - a is positive, a is first on the axis and we should use its extent
// if b -a is negative, b is first on the axis and we should use its extent
// check for x axis separation
if ((dxyz.x >= 0 && a.bottomRight.x-a.topLeft.x < dxyz.x)
// negative scale, reverse extent sum, flip equality
||(dxyz.x < 0 && b.topLeft.x-b.bottomRight.x > dxyz.x))
return false;
// check for y axis separation
if ((dxyz.y >= 0 && a.bottomRight.y-a.topLeft.y < dxyz.y)
// negative scale, reverse extent sum, flip equality
||(dxyz.y < 0 && b.topLeft.y-b.bottomRight.y > dxyz.y))
return false;
// check for z axis separation
if ((dxyz.z >= 0 && a.bottomRight.z-a.topLeft.z < dxyz.z)
// negative scale, reverse extent sum, flip equality
||(dxyz.z < 0 && b.topLeft.z-b.bottomRight.z > dxyz.z))
return false;
// not separated on any axis, overlapping
return true;
}
public static boolean isContactEdge(int xyzAxis, BoundingBox a, BoundingBox b)
{
switch(xyzAxis) {
case XYZ.XCOORD:
if(a.topLeft.x == b.bottomRight.x || a.bottomRight.x == b.topLeft.x)
return true;
return false;
case XYZ.YCOORD:
if(a.topLeft.y == b.bottomRight.y || a.bottomRight.y == b.topLeft.y)
return true;
return false;
case XYZ.ZCOORD:
if(a.topLeft.z == b.bottomRight.z || a.bottomRight.z == b.topLeft.z)
return true;
return false;
}
return false;
}
/**
* Sweep test min extent value
* @param box
* @param xyzCoord
* @return
*/
public static float min(BoundingBox box, int xyzCoord)
{
switch(xyzCoord) {
case XYZ.XCOORD:
return box.topLeft.x;
case XYZ.YCOORD:
return box.topLeft.y;
case XYZ.ZCOORD:
return box.topLeft.z;
default: return 0f;
}
}
/**
* Sweep test max extent value
* @param box
* @param xyzCoord
* @return
*/
public static float max(BoundingBox box, int xyzCoord)
{
switch(xyzCoord) {
case XYZ.XCOORD:
return box.bottomRight.x;
case XYZ.YCOORD:
return box.bottomRight.y;
case XYZ.ZCOORD:
return box.bottomRight.z;
default: return 0f;
}
}
/**
* Test if bounding box A will overlap bounding box B at any point
* when box A moves from position 0 to position 1 and box B moves from position 0 to position 1
* Note, sweep test assumes bounding boxes A and B's dimensions do not change
*
* @param a0 box a starting position
* @param a1 box a ending position
* @param b0 box b starting position
* @param b1 box b ending position
* @param aCollisionOut xyz of box a's position when/if a collision occurs
* @param bCollisionOut xyz of box b's position when/if a collision occurs
* @return
*/
public static boolean sweepTest(BoundingBox a0, BoundingBox a1, BoundingBox b0, BoundingBox b1, XYZ aCollisionOut, XYZ bCollisionOut)
{
// solve in reference to A
XYZ va = new XYZ(a1.topLeft.x-a0.topLeft.x, a1.topLeft.y-a0.topLeft.y, a1.topLeft.z-a0.topLeft.z);
XYZ vb = new XYZ(b1.topLeft.x-b0.topLeft.x, b1.topLeft.y-b0.topLeft.y, b1.topLeft.z-b0.topLeft.z);
XYZ v = new XYZ(vb.x-va.x, vb.y-va.y, vb.z-va.z);
// check for initial overlap
if(BoundingBox.isOverlapping(a0, b0))
{
// java pass by ref/value gotcha, have to modify value can't reassign it
aCollisionOut.x = a0.topLeft.x;
aCollisionOut.y = a0.topLeft.y;
aCollisionOut.z = a0.topLeft.z;
bCollisionOut.x = b0.topLeft.x;
bCollisionOut.y = b0.topLeft.y;
bCollisionOut.z = b0.topLeft.z;
return true;
}
// overlap min/maxs
XYZ u0 = new XYZ();
XYZ u1 = new XYZ(1,1,1);
float t0, t1;
// iterate axis and find overlaps times (x=0, y=1, z=2)
for(int i = 0; i < 3; i++)
{
float aMax = max(a0, i);
float aMin = min(a0, i);
float bMax = max(b0, i);
float bMin = min(b0, i);
float vi = XYZ.getCoord(v, i);
if(aMax < bMax && vi < 0)
XYZ.setCoord(u0, i, (aMax-bMin)/vi);
else if(bMax < aMin && vi > 0)
XYZ.setCoord(u0, i, (aMin-bMax)/vi);
if(bMax > aMin && vi < 0)
XYZ.setCoord(u1, i, (aMin-bMax)/vi);
else if(aMax > bMin && vi > 0)
XYZ.setCoord(u1, i, (aMax-bMin)/vi);
}
// get times of collision
t0 = Math.max(u0.x, Math.max(u0.y, u0.z));
t1 = Math.min(u1.x, Math.min(u1.y, u1.z));
// collision only occurs if t0 < t1
if(t0 <= t1 && t0 != 0) // not t0 because we already tested it!
{
// t0 is the normalized time of the collision
// then the position of the bounding boxes would
// be their original position + velocity*time
aCollisionOut.x = a0.topLeft.x + va.x*t0;
aCollisionOut.y = a0.topLeft.y + va.y*t0;
aCollisionOut.z = a0.topLeft.z + va.z*t0;
bCollisionOut.x = b0.topLeft.x + vb.x*t0;
bCollisionOut.y = b0.topLeft.y + vb.y*t0;
bCollisionOut.z = b0.topLeft.z + vb.z*t0;
return true;
}
else
return false;
}
}
