Detecting Collisions of Two Cubes

Sage
Posts: 1,066
Joined: 2004.07
Post: #1
I'm trying to figure out how to detect collisions between two cubes in OpenGL. This is my code so far which doesn't work at all:
Code:
void CCharacter::CheckCollision(CActiveObject *object)
{
    
    int w = 0;
    
    if ( ( ( GetX() + GetW() ) > ( object->GetX() - object->GetW() ) ) &&
         ( ( GetX() - GetW() ) < ( object->GetX() + object->GetW() ) ) &&
         ( ( GetY() + GetH() ) > ( object->GetY() - object->GetH() ) ) &&
         ( ( GetY() - GetH() ) < ( object->GetY() + object->GetH() ) ) &&
         ( ( GetZ() + GetD() ) > ( object->GetZ() - object->GetD() ) ) &&
         ( ( GetZ() - GetD() ) < ( object->GetZ() + object->GetD() ) ) )
    {    
        if ( GetX() < object->GetX() ) { w += LEFT; }
        if ( GetX() > object->GetX() ) { w += RIGHT; }
        if ( GetY() < object->GetY() ) { w += BOTTOM; }
        if ( GetY() > object->GetY() ) { w += TOP; }
        if ( GetZ() < object->GetZ() ) { w += BACK; }
        if ( GetZ() > object->GetZ() ) { w += FRONT; }
    }
    
    if ( object->GetType() == BUILDING_TYPE ) { CollideBuilding(object,w); }
    if ( object->GetType() == LADDER_TYPE ) { CollideLadder(object,w); }
    if ( object->GetType() != LADDER_TYPE ) { mOnLadder = false; }

}

All the code should be fairly self explanatory. GetX, GetY, and GetZ return the coordinates of the CENTER of the cube. GetW, GetH, and GetD return the dimensions as the distance from the center to a side, not from one side to the opposite. LEFT, RIGHT, BOTTOM, etc are all enumerated constants. GetType() returns a defined constant telling this code which more specific code to run.

If you can help me out, I would appreciate it.
Quote this message in a reply
Member
Posts: 157
Joined: 2002.12
Post: #2
not an easy answer for this one.
if the cubes do not rotate all you have to do is check that cubes extend overlap in (x,y,z).
if they do rotate it becomes really tricky involves a lot of math.
Did you try google for "box collision detection"?
Quote this message in a reply
Member
Posts: 177
Joined: 2002.08
Post: #3
There should be 3 separate tests:

-do they overlap in X?
-do they overlap in Y?
-do they overlap in Z?

If all of them are true, then they hit.

Also, each test is going to have to consist of 2 separate checks, since you have to check each cube against the other.
Quote this message in a reply
Member
Posts: 157
Joined: 2002.12
Post: #4
if you will have lots of boxes to check.you could do a pre-process to find box pairs to do the collision test.
If you have 3 boxes [A,B,C] you would end up with an array of pairs that would look like this.

pairs [ [A,B], [A,C], [B,C] ]
Quote this message in a reply
Member
Posts: 509
Joined: 2002.05
Post: #5
Mark Levin Wrote:There should be 3 separate tests:

-do they overlap in X?
-do they overlap in Y?
-do they overlap in Z?

If all of them are true, then they hit.

Also, each test is going to have to consist of 2 separate checks, since you have to check each cube against the other.

Not always...

Code:
/\
/    \
\   /
   \/ /\
     /   \
     \   /
       \/

Overlapping but not colliding
Quote this message in a reply
Moderator
Posts: 916
Joined: 2002.10
Post: #6
Jake Wrote:Not always...

Code:
/\
/    \
\   /
   \/ /\
     /   \
     \   /
       \/

Overlapping but not colliding

I thought he was using axis aligned bounding boxes
Quote this message in a reply
Moderator
Posts: 1,560
Joined: 2003.10
Post: #7
Keeping everything axis-aligned will make your life much easier. As Mark said, if the X, Y, and Z all overlap, there's a collision. However, if you have very small collision boxes and/or very fast-moving objects, this system will fail from time to time if one object moves far enough in one framestep to go all the way past something it was supposed to collide with.

I account for this in Water Tower 3D by incorporating 3 bounding boxes into my collision tests: The player's current bounding box, the player's new intended bounding box (with velocity added), and the bounding box of the object to collide with. For each edge on the collision object {left, right, bottom, top, back, front}, I check to see if the opposing edge on the player's current bounding box {right, left, top, bottom, front, back} is on one side of the edge, and the opposing edge on the new intended bounding box is on the other side of that edge. If both of those are true, I know a collision has occurred. For subsequent collision tests in the same frame, the new intended bounding box gets adjusted.

This system isn't perfect, but it seems to do that job pretty well in my case. There are a few gotchas I should tell you about if you decide to go this route. Let me know if you want me to elaborate; I'm at work at the moment, but I can post a more detailed message after I get home.

Alex Diener
Quote this message in a reply
Member
Posts: 469
Joined: 2002.10
Post: #8
cubes are easy. rectangular prisms are not.

D = the distance between the box centers.
W = (widthA+widthB)/2.
if (D < W) then collide.
else if (D > sqrt(3)*W) then not collided.
else if (any point in boxA is inside boxB or any point of boxB is inside boxA) then collide.

done.

---Kelvin--
15.4" MacBook Pro revA
1.83GHz/2GB/250GB
Quote this message in a reply
Sage
Posts: 1,066
Joined: 2004.07
Post: #9
Kelvin, can you explain why W = (widthA+widthB)/2 and why if (D > sqrt(3)*W) there is no collision? I also assume this will not work will rectangular objects. Am I correct?
Quote this message in a reply
Member
Posts: 469
Joined: 2002.10
Post: #10
SimReality/Nick Wrote:Kelvin, can you explain why W = (widthA+widthB)/2 and why if (D > sqrt(3)*W) there is no collision? I also assume this will not work will rectangular objects. Am I correct?
W is just precalculation on my part. It just happens that the distance formula simplifies down and that's one of the terms. sqrt(3)*W = the distance from the center of cubeA to a corner + the distance from the center of cubeB to a corner. So, basically this tests if the distance is greater than the nearest distance required for two corners to touch.

Rectangles can be done in a similar fashion, but the math doesn't simplify down nearly as cleanly, and there are a lot of edge cases that you need to account for after the last check for the cubes. If you want to do irregular shaped objects, I'd suggest using Capsules, Cylinders, and Spheres for collision checking as it will probably be the easiest to represent and implement.

---Kelvin--
15.4" MacBook Pro revA
1.83GHz/2GB/250GB
Quote this message in a reply
Sage
Posts: 1,066
Joined: 2004.07
Post: #11
Thanks for that tip. I'll see if I can fit it in to my code and get it to work. Unfortunately most of my objects come out as rectangles so I won't be able to use this too much.
Quote this message in a reply
Member
Posts: 469
Joined: 2002.10
Post: #12
to do the corner check for rectangles, it's 0.5*(sqrt(wA^2+hA^2+dA^2)+sqrt(wB^2+hB^2+dB^2)). Which takes quite a bit longer since you now have 2 square roots and several multiplies where as you only have a multiply by a constant sqrt(3) for cubes which can be calculated ahead of time.

---Kelvin--
15.4" MacBook Pro revA
1.83GHz/2GB/250GB
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Frustrations, Collisions, et al. blobbo 6 4,023 Feb 9, 2005 11:37 AM
Last Post: phydeaux
  Detecting a RagePro, and related poll inio 5 4,945 Jul 2, 2002 05:00 PM
Last Post: Carlos Camacho