Simple Oriented Bounding Box OBB collision detection explaining

Question

I can implement the AABB method to detect collisions it is easy and cheap but I want to implement OBB for more accuracy so I create the bounding box with the model initialization it is consists of 8 bounding vertices and center, each frame I transform all the vertices with the transformation matrix to fit the Oriented Bounding Box but I can't understand the method for detecting the collision between two OBBs and I can't find a simplified and clear tutorial which explain the algorithm with the code view point not the math because I am not a mathematician.

if I have

struct Box {
    glm::vec3 vertices[8];
    Box() {
        for (int i = 0; i < 8; i++) {
            vertices[i] = glm::vec3(0);
        }
    }
    glm::vec3 max;
    glm::vec3 min;
    glm::vec3 origin;

    void reCompute() {
        max = vertices[0];
        min = vertices[0];
        for (int i = 1; i < 8; i++) {
            max.x = max.x > vertices[i].x ? max.x : vertices[i].x;
            max.y = max.y > vertices[i].y ? max.y : vertices[i].y;
            max.z = max.z > vertices[i].z ? max.z : vertices[i].z;

            min.x = min.x < vertices[i].x ? min.x : vertices[i].x;
            min.y = min.y < vertices[i].y ? min.y : vertices[i].y;
            min.z = min.z < vertices[i].z ? min.z : vertices[i].z;
        }
        origin = glm::vec3((max.x + min.x) / 2.0f, (max.y + min.y) / 2.0f, (max.z + min.z) / 2.0f);
    }
//AABB intersection
    bool intersects(const Box &b) const {
        return (min.x < b.max.x) && (max.x > b.min.x) && (min.y < b.max.y) && (max.y > b.min.y) && (min.z < b.max.z) && (max.z > b.min.z) && *this != b;
    }

    bool operator==(const Box& b) const {
        return (max.x == b.max.x && max.y == b.max.y && max.z == b.max.z && min.x == b.min.x && min.y == b.min.y && min.z == b.min.z);
    }
    bool operator!=(const Box& b) const {
        return (max.x != b.max.x) || (max.y != b.max.y) || (max.z != b.max.z) || (min.x != b.min.x) || (min.y != b.min.y) || (min.z != b.min.z);
    }
};

on model initialization I create the box

    box.vertices[0] = glm::vec3(meshMinX, meshMinY, meshMinZ);
    box.vertices[1] = glm::vec3(meshMaxX, meshMinY, meshMinZ);
    box.vertices[2] = glm::vec3(meshMinX, meshMaxY, meshMinZ);
    box.vertices[3] = glm::vec3(meshMaxX, meshMaxY, meshMinZ);
    box.vertices[4] = glm::vec3(meshMinX, meshMinY, meshMaxZ);
    box.vertices[5] = glm::vec3(meshMaxX, meshMinY, meshMaxZ);
    box.vertices[6] = glm::vec3(meshMinX, meshMaxY, meshMaxZ);
    box.vertices[7] = glm::vec3(meshMaxX, meshMaxY, meshMaxZ);

and each frame I recompute the box with the transformation matrix of the model

for (int n = 0; n < 8; n++) {
        boxs[j].vertices[n] = glm::vec3(matrix * glm::vec4(box.vertices[n], 1));
    }
boxs[j].reCompute();

Deflation

This research paper here explains it in quite detail. See "5." researchgate.net/publication/… – Ripon

it has very much math details so I found it complex for understanding – Deflation

Answer 1

A C++ code implementation of the separating axis theorem for simple collision detection between two 3D OBB would be this:

#include <iostream>

// define the operations to be used in our 3D vertices
struct vec3
{
    float x, y, z;
    vec3 operator- (const vec3 & rhs) const { return{ x - rhs.x, y - rhs.y, z - rhs.z }; }
    float operator* (const vec3 & rhs) const { return{ x * rhs.x + y * rhs.y + z * rhs.z }; } // DOT PRODUCT
    vec3 operator^ (const vec3 & rhs) const { return{ y * rhs.z - z * rhs.y, z * rhs.x - x * rhs.z, x * rhs.y - y * rhs.x }; } // CROSS PRODUCT
    vec3 operator* (const float& rhs)const { return vec3{ x * rhs, y * rhs, z * rhs }; }
};

// set the relevant elements of our oriented bounding box
struct OBB
{
    vec3 Pos, AxisX, AxisY, AxisZ, Half_size;
};

// check if there's a separating plane in between the selected axes
bool getSeparatingPlane(const vec3& RPos, const vec3& Plane, const OBB& box1, const OBB&box2)
{
    return (fabs(RPos*Plane) > 
        (fabs((box1.AxisX*box1.Half_size.x)*Plane) +
        fabs((box1.AxisY*box1.Half_size.y)*Plane) +
        fabs((box1.AxisZ*box1.Half_size.z)*Plane) +
        fabs((box2.AxisX*box2.Half_size.x)*Plane) + 
        fabs((box2.AxisY*box2.Half_size.y)*Plane) +
        fabs((box2.AxisZ*box2.Half_size.z)*Plane)));
}

// test for separating planes in all 15 axes
bool getCollision(const OBB& box1, const OBB&box2)
{
    static vec3 RPos;
    RPos = box2.Pos - box1.Pos;

    return !(getSeparatingPlane(RPos, box1.AxisX, box1, box2) ||
        getSeparatingPlane(RPos, box1.AxisY, box1, box2) ||
        getSeparatingPlane(RPos, box1.AxisZ, box1, box2) ||
        getSeparatingPlane(RPos, box2.AxisX, box1, box2) ||
        getSeparatingPlane(RPos, box2.AxisY, box1, box2) ||
        getSeparatingPlane(RPos, box2.AxisZ, box1, box2) ||
        getSeparatingPlane(RPos, box1.AxisX^box2.AxisX, box1, box2) ||
        getSeparatingPlane(RPos, box1.AxisX^box2.AxisY, box1, box2) ||
        getSeparatingPlane(RPos, box1.AxisX^box2.AxisZ, box1, box2) ||
        getSeparatingPlane(RPos, box1.AxisY^box2.AxisX, box1, box2) ||
        getSeparatingPlane(RPos, box1.AxisY^box2.AxisY, box1, box2) ||
        getSeparatingPlane(RPos, box1.AxisY^box2.AxisZ, box1, box2) ||
        getSeparatingPlane(RPos, box1.AxisZ^box2.AxisX, box1, box2) ||
        getSeparatingPlane(RPos, box1.AxisZ^box2.AxisY, box1, box2) ||
        getSeparatingPlane(RPos, box1.AxisZ^box2.AxisZ, box1, box2));
}

// a quick test to see the code working
int _tmain(int argc, _TCHAR* argv[])
{
    // create two obbs
    OBB A, B;

    // set the first obb's properties
    A.Pos = { 0.f, 0.f, 0.f }; // set its center position

    // set the half size
    A.Half_size.x = 10.f; 
    A.Half_size.y = 1.f; 
    A.Half_size.z = 1.f;

    // set the axes orientation
    A.AxisX = { 1.f, 0.f, 0.f };
    A.AxisY = { 0.f, 1.f, 0.f };
    A.AxisZ = { 0.f, 0.f, 1.f };

    // set the second obb's properties
    B.Pos = { 20.f, 0.f, 0.f }; // set its center position

    // set the half size
    B.Half_size.x = 10.f;
    B.Half_size.y = 1.f;
    B.Half_size.z = 1.f;

    // set the axes orientation
    B.AxisX = { 1.f, 0.f, 0.f };
    B.AxisY = { 0.f, 1.f, 0.f };
    B.AxisZ = { 0.f, 0.f, 1.f };

    // run the code and get the result as a message
    if (getCollision(A, B)) std::cout << "Collision!!!" << std::endl;
    else std::cout << "No collision." << std::endl;

    // pause and quit
    std::cout << std::endl;
    system("pause");
    return 0;
}

Kroon

excuse me It's a bit late, but I am implementing SAT for a 3D engine. I am strugling to get the info of the collision. What I need is the collision point of one of the cube, the normal of the collision and depth. Do you have any idea how to implement that in your implementation ? – Cristobalcristobalite

Answer 2

To know if two OBB collide you use SAT(separating axis theorem): you have to project all the points of the two shapes on every normal of the two shapes. Then you see if the projection of the two shapes overlap on each normals there is a collision. If there is at least one normal where there is no overlap then they do not collide. And that's all, to do that you will need a method to do orthogonal projection of a vector on another vector which returns a scalar, and a method to see if two intervals overlap.

I have some code in Java :

Orthagonal projection of U on V :

/**
 * Vec u is projected on Vec v
 * @param u 2d point
 * @param v 2d axe
 * @return the orthogonal projection
 */
public static float orthagonalProjectionOf(Vector2f u, Vector2f v){
    float norme_u = u.lenght();
    float norme_v = v.lenght();
    float dot_u_v = dot(u, v);
    float buffer = (dot_u_v/(norme_u*norme_v))*norme_u;
    if(Float.isNaN(buffer))return 0;//If the vector u is null, then is orthogonal projection is 0, not a NaN
    else return buffer;
}

Overlapping of two interval :

/**
 * Get the overlapping of two interval on an axis.
 * @param minA
 * @param maxA
 * @param minB
 * @param maxB
 * @return true overlapping. false if there is no overlapping
 */
public static boolean isOverlapping(float minA, float maxA, float minB, float maxB) {

    float minOverlap = Float.NaN;
    float maxOverlap = Float.NaN;


    //If B contain in A
    if(minA <= minB && minB <= maxA) {
        if(Float.isNaN(minOverlap) || minB < minOverlap)minOverlap = minB;
    }
    if(minA <= maxB && maxB <= maxA) {
        if(Float.isNaN(maxOverlap) || maxB > minOverlap)maxOverlap = maxB;
    }

    //If A contain in B
    if(minB <= minA && minA <= maxB) {
        if(Float.isNaN(minOverlap) || minA < minOverlap)minOverlap = minA;
    }
    if(minB <= maxA && maxA <= maxB) {
        if(Float.isNaN(maxOverlap) || maxA > minOverlap)maxOverlap = maxA;
    }

    if(Float.isNaN(minOverlap) || Float.isNaN(maxOverlap))return false; //Pas d'intersection
    else return true;//Intersection

}

With that your are able to do a method to test collision between two OBB :

public boolean OBBwOBB(RigidBody bodyA, RigidBody bodyB) {
    Shape shapeA = bodyA.getObb().getShape();
    Shape shapeB = bodyB.getObb().getShape();

    short overlapCompt = 0;

    //We test for each normal the projection of the two shape
        //Shape A :
    for(int i = 0; i < shapeA.getNbrOfNormals(); i++) {
        Vector2f normal = shapeA.getNormal(i, bodyA.getAngle());
        boolean overlap = overlapOnThisNormal(bodyA, bodyB, normal);
        if(overlap) {
            overlapCompt++;
        }
    }
        //Shape B :
    for(int i = 0; i < shapeB.getNbrOfNormals(); i++) {
        Vector2f normal = shapeB.getNormal(i, bodyB.getAngle());
        boolean overlap = overlapOnThisNormal(bodyA, bodyB, normal);
        if(overlap){
            overlapCompt++;
        }
    }

    //Now we see if there is a collision
    short howManyNormals = (short) (shapeA.getNbrOfNormals() + shapeB.getNbrOfNormals());
    if(overlapCompt == howManyNormals){//If the number of overlap equal the number of normal in both shape :
        return true;
    }
    else return false;

}

And you will need that to get the min and max of the projection of the two shape projected on a vector:

/**
 * Test if the orthogonal projection of two shape on a vector overlap.
 * @param bodyA
 * @param bodyB
 * @param normal
 * @return null if no overlap, else Vector2f(minOverlaping, maxOverlaping).
 */
public static boolean overlapOnThisNormal(RigidBody bodyA, RigidBody bodyB, Vector2f normal) {
    Shape shapeA = bodyA.getObb().getShape();
    Shape shapeB = bodyB.getObb().getShape();

    //We test each vertex of A
    float minA = Float.NaN;
    float maxA = Float.NaN;
    for(short j = 0; j < shapeA.getNbrOfPoint(); j++){
        Vector2f vertex = shapeA.getVertex(j, bodyA.getScale().x, bodyA.getScale().y, bodyA.getPosition().x, bodyA.getPosition().y, bodyA.getAngle());
        float bufferA = Vector2f.orthagonalProjectionOf(vertex, normal);
        if(Float.isNaN(minA) || bufferA < minA)minA = bufferA;//Set min interval
        if(Float.isNaN(maxA) || bufferA > maxA)maxA = bufferA;//Set max interval
    }

    //We test each vertex of B
    float minB = Float.NaN;
    float maxB = Float.NaN;
    for(short j = 0; j < shapeB.getNbrOfPoint(); j++){
        Vector2f vertex = shapeB.getVertex(j, bodyB.getScale().x, bodyB.getScale().y, bodyB.getPosition().x, bodyB.getPosition().y, bodyB.getAngle());
        float bufferB = Vector2f.orthagonalProjectionOf(vertex, normal);
        if(Float.isNaN(minB) || bufferB < minB)minB = bufferB;//Set min interval
        if(Float.isNaN(maxB) || bufferB > maxB)maxB = bufferB;//Set max interval
    }

    //We test if there overlap
    boolean overlap = isOverlapping(minA, maxA, minB, maxB);
    return overlap;
}

I hope this helps you ;)

Anselm

This is the 2D solution. The question is asking about 3D collision detection. The extension of SAT into the third dimension is not a trivial matter. – Artilleryman