I already have the 8 corner points of two 3d boxes that are stationary. What is a good technique to tell if the boxes intersect each other? Thank you.
For each point in box1, check if it is inside box2. That means you're doing a simple point-in-box test.
To do a point in box test, for each dimension (3D = x,y,z and 2D = x,y) you check the coordinate of the point, and see if its between the matching 2 edges on that surface.
Thats a horrible explanation, sorry :P Draw a little diagram in 2D, and it should be clear. Then its trivial to expand that to 3D.
To do a point in box test, for each dimension (3D = x,y,z and 2D = x,y) you check the coordinate of the point, and see if its between the matching 2 edges on that surface.
Thats a horrible explanation, sorry :P Draw a little diagram in 2D, and it should be clear. Then its trivial to expand that to 3D.
But what if the corner points of one box are not inside the other, how will this test work if a point on a line between two corner points is inside the box?
Separating Axis Theorem :)
In short:
Check whether the boxes projection on 15 specific axes overlap, if one of them don't, they can't overlap.
The 15 axes are:
The 3 basis vectors of box A
The 3 basis vectors of box B
The 9 (3*3) axes that are the result of the crossproduct of the basis vectors, A.axis[0].cross(B.axis[0]), A.axis[0].cross(B.axis[1]) etc...
In short:
Check whether the boxes projection on 15 specific axes overlap, if one of them don't, they can't overlap.
The 15 axes are:
The 3 basis vectors of box A
The 3 basis vectors of box B
The 9 (3*3) axes that are the result of the crossproduct of the basis vectors, A.axis[0].cross(B.axis[0]), A.axis[0].cross(B.axis[1]) etc...
Does anyone know where source code for such an algorithm is available? I've googling for a while now.
I tried to mplement the following. Would something like this work? Thanks.
bool doBoundingBoxesCollide(Point3d & pointMinBox_1, Point3d & pointMaxBox_1, Point3d & pointMinBox_2, Point3d & pointMaxBox_2){ // RETURNS true IF THERE IS A COLLISION, false FOR NO COLLISION if (((pointMinBox_2.x > pointMinBox_1.x) && (pointMinBox_2.x < pointMaxBox_1.x)) || ((pointMaxBox_2.x > pointMinBox_1.x) && (pointMaxBox_2.x < pointMaxBox_1.x))) { if (((pointMinBox_2.y > pointMinBox_1.y) && (pointMinBox_2.y < pointMaxBox_1.y)) || ((pointMaxBox_2.y > pointMinBox_1.y) && (pointMaxBox_2.y < pointMaxBox_1.y))) { if (((pointMinBox_2.z > pointMinBox_1.z) && (pointMinBox_2.z < pointMaxBox_1.z)) || ((pointMaxBox_2.z > pointMinBox_1.z) && (pointMaxBox_2.z < pointMaxBox_1.z))) { // WE GOT A COLLISION return true; } } } // NO COLLISION return false;}
Quote:Original post by kelaklub
I tried to mplement the following. Would something like this work? Thanks.
*** Source Snippet Removed ***
That will work only with "non rotated boxes", where each face is perpendicular to one of the main axis (x, y, z).
(I know that "non rotated" isn't a proper way of defining how are the boxes, but I'm pretty sure that helps you get the point).
Hi,
Depends on wether you boxes are axis aligned or not. If they are axis aligned (AABB) then its simple to determine if they overlap. If they are not, in other words they are rotated boxes (OBB) then you'll need the full seperating axis theorem.
For AABB I use the following, which simply checks if the max extent of one AABB axis is less then the min extent of the other (for each axis in turn) (and vice versa). If true the boxes cannot overlap, the good thing being an early out if any axis test fails.
You may also find this article useful
http://www.gamasutra.com/features/19991018/Gomez_3.htm
Cheers
Depends on wether you boxes are axis aligned or not. If they are axis aligned (AABB) then its simple to determine if they overlap. If they are not, in other words they are rotated boxes (OBB) then you'll need the full seperating axis theorem.
For AABB I use the following, which simply checks if the max extent of one AABB axis is less then the min extent of the other (for each axis in turn) (and vice versa). If true the boxes cannot overlap, the good thing being an early out if any axis test fails.
-- Function: Do the two AABB overlapAABB_OVERLAP MinA, MaxA, MinB, MaxB { if MaxA.x < MinB.x or MinA.x > MaxB.x then return (0) if MaxA.y < MinB.y or MinA.y > MaxB.y then return (0) if MaxA.z < MinB.z or MinA.z > MaxB.z then return (0) return (1)}
You may also find this article useful
http://www.gamasutra.com/features/19991018/Gomez_3.htm
Cheers
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement