10

我可以实现 AABB 方法来检测碰撞,它既简单又便宜,但我想实现 OBB 以获得更高的准确性,所以我使用模型初始化创建了边界框,它由 8 个边界顶点和中心组成,每一帧我都会转换所有顶点使用变换矩阵来适应定向边界框,但我无法理解检测两个 OBB 之间碰撞的方法,而且我找不到一个简化且清晰的教程,它用代码观点而不是数学来解释算法,因为我我不是数学家。

如果我有

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);
    }
};

在模型初始化时,我创建了盒子

    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);

并且每一帧我用模型的变换矩阵重新计算盒子

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

2 回答 2

12

用于两个 3D OBB 之间的简单碰撞检测的分离轴定理的 C++ 代码实现如下:

#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;
}
于 2018-08-24T19:07:46.820 回答
1

要知道两个 OBB 是否碰撞,您使用 SAT(分离轴定理):您必须将两个形状的所有点投影到两个形状的每个法线上。然后你看看两个形状的投影在每个法线上是​​否重叠,是否存在碰撞。如果至少有一个法线没有重叠,那么它们就不会发生碰撞。就是这样,要做到这一点,您将需要一种方法来在另一个返回标量的向量上进行向量的正交投影,以及查看两个间隔是否重叠的方法。

我有一些 Java 代码:

U 在 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;
}

两个区间的重叠:

/**
 * 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

}

这样您就可以使用一种方法来测试两个 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;

}

您将需要它来获得投影在向量上的两个形状的投影的最小值和最大值:

/**
 * 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;
}

我希望这可以帮助你 ;)

于 2017-12-24T14:26:34.223 回答