How do I calculate collision with rotation in 3D space?

Question

In my program I need to calculate collision between a rotated box and a sphere as well as collision between 2 rotated boxes. I can't seem to find any information on it and trying to figure the math out in my own is boggling my mind.

I have collision working for 2 boxes and a sphere and a box, but now I need to factor in angles. This is my code so far:

class Box
{
public:
    Box();

private:
    float m_CenterX, m_CenterY, m_CenterZ, m_Width, m_Height, m_Depth;
    float m_XRotation, m_YRotation, m_ZRotation;
};

class Sphere
{
public:
   Sphere();

private:
   float m_CenterX, m_CenterY, m_CenterZ, radius;
   unsigned char m_Colour[3];
};

bool BoxBoxCollision(BoxA, BoxB)
{
    //The sides of the Cubes 
    float leftA, leftB; 
    float rightA, rightB;
    float topA, topB; 
    float bottomA, bottomB;
    float nearA, nearB;
    float farA, farB;

    //center pivot is at the center of the object
    leftA = A.GetCenterX() - A.GetWidth(); 
    rightA = A.GetCenterX() + A.GetWidth(); 
    topA = A.GetCenterY() - A.GetHeight(); 
    bottomA = A.GetCenterY() + A.GetHeight();
    farA = A.GetCenterZ() - A.GetDepth(); 
    nearA = A.GetCenterZ() + A.GetDepth();

    leftB = B.GetCenterX() - B.GetWidth(); 
    rightB = B.GetCenterX() + B.GetWidth(); 
    topB = B.GetCenterY() - B.GetHeight(); 
    bottomB = B.GetCenterY() + B.GetHeight();
    farB = B.GetCenterZ() - B.GetDepth(); 
    nearB = B.GetCenterZ() + B.GetDepth();

    //If any of the sides from A are outside of B 
    if( bottomA <= topB ) { return false; }
    if( topA >= bottomB ) { return false; }
    if( rightA <= leftB ) { return false; }
    if( leftA >= rightB ) { return false; }
    if( nearA <= farB ) { return false; }
    if( farA >= nearB ) { return false; }

     //If none of the sides from A are outside B 
    return true;
}

bool SphereBoxCollision( Sphere& sphere, Box& box) 
{ 
    float sphereXDistance = abs(sphere.getCenterX() - box.GetCenterX());
    float sphereYDistance = abs(sphere.getCenterY() - box.GetCenterY());
    float sphereZDistance = abs(sphere.getCenterZ() - box.GetCenterZ());

    if (sphereXDistance >= (box.GetWidth() + sphere.getRadius())) { return false; }
    if (sphereYDistance >= (box.GetHeight() + sphere.getRadius())) { return false; }
    if (sphereZDistance >= (box.GetDepth() + sphere.getRadius())) { return false; }

    if (sphereXDistance < (box.GetWidth())) { return true; } 
    if (sphereYDistance < (box.GetHeight())) { return true; }
    if (sphereZDistance < (box.GetDepth())) { return true; }

   float cornerDistance_sq = ((sphereXDistance - box.GetWidth()) * (sphereXDistance - box.GetWidth())) +
                         ((sphereYDistance - box.GetHeight()) * (sphereYDistance - box.GetHeight()) +
                         ((sphereYDistance - box.GetDepth()) * (sphereYDistance - box.GetDepth())));

    return (cornerDistance_sq < (sphere.getRadius()*sphere.getRadius()));
}

How do I factor in rotation? Any suggestions would be great.

Answer 1

First of all, your objects are boxes, not rectangles. The term rectangle is strictly reserved for the 2D figure.

When you are dealing with rotations, you should generally view them as a special form of an affine transform. An affine transform can be a rotation, a translation, a scaling operation, a shearing operation, or any combination of these, and it can be represented by a simple 4x4 matrix that is multiplied to the vectors that give the vertices of your boxes. That is, you can describe any rotated, scaled, sheared box as the unit box (the box between the vectors <0,0,0> to <1,1,1>) to which an affine transform has been applied.

The matrix of most affine transforms (except those that scale by a factor of zero) can be inverted, so that you can both transform any point into the coordinate system of the box and then compare it against <0,0,0> and <1,1,1> to check whether its inside the box, and transform any point in the coordinates of the box back into your world coordinate system (for instance you can find the center of your box by transforming the vector <0.5, 0.5, 0.5>). Since any straight line remains a straight line when an affine transform is applied to it, all you ever need to transform is the vertices of your boxes.

Now, you can just take the vertices of one box (<0,0,0>, <0,0,1>, ...), transform them into your world coordinate system, then transform them back into the coordinate system of another box. After that, the question whether the two boxes overlap becomes the question whether the box described by the transformed eight vertices overlaps the unit box. Now you can easily decide whether there is a vertex above the base plane of the unit box (y > 0), below the top plane (y < 1), and so on. Unfortunately there is a lot of cases to cover for a box/box intersection, it is much easier to intersect spheres, rays, planes, etc. than such complex objects like boxes. However, having one box nailed to the unit box should help a lot.

---

Sidenote:

For rotations in 3D, it pays to know how to use quaternions for that. Euler angles and similar systems all have the issue of gimbal lock, quaternions do not have this restriction.

Basically, every unit quaternion describes a rotation around a single, free axis. When you multiply two unit quaternions, you get a third one that gives you the rotation that results from applying the two quaternions one after the other. And, since it is trivial to compute the multiplicative inverse of a quaternion, you can also divide one quaternion by another to answer the question what one-axis rotation you would need to apply to get from one rotation state to another. That last part is simply impossible to do in terms of Euler angles. Quaternions are really one of the sweetest parts of mathematics.

I simply cannot cover all the details in this answer, the topic is quite a broad and interesting one. That is why I linked the four wikipedia articles. Read them if you need further details.

Answer 2

For Box-Box collision transform the coordinates in such a way that the first box is centered at the origin and is aligned with the axis. Then checking if the second box collides with it is easier even tho is not quite trivial. For most cases (physics engine at small dt*v where you can assume movement is continuous) it suffices to check if any of the vertices fall inside the first box.

For Box-Sphere is simpler. Like before, transform the coordinates in such a way that the box is centered at the origin and is aligned with the axis. Now you only need to check that the distance between the center of the box and each of the canonical planes (generated by the axes) is less than the radius of the sphere plus half of the span of the box in the normal direction.