3D 空间中两个框之间的交点 [英] Intersection between two boxes in 3D space

问题描述

我想为我的图形引擎实现一个碰撞检测系统.

I want to implement a collision detection system for my graphic engine.

我不知道这是否是常用的方法，但我的想法是将任何实体对象(如网格或相机)绑定在 3D 框内，这会给我比球体更准确的结果.

I don't know if it is the common way to do it but my idea was to bound any solid object (like a mesh or the camera) within a 3D box, which would give me much more accurate results than a sphere.

这个框由八个顶点定义

    x0 = min(vertices.x)-off   // parsing mesh's vertices for the minimum x
    y0 = min(vertices.y)-off
    z0 = min(vertices.z)-off
    x1 = max(vertices.x)+off   // off avoids 2D bounding on 2D objects
    y1 = max(vertices.y)+off
    z1 = max(vertices.z)+off
    boundingBox[0] = vec3(x0, y0, z0);
    boundingBox[1] = vec3(x0, y1, z0);
    boundingBox[2] = vec3(x1, y0, z0);
    boundingBox[3] = vec3(x1, y1, z0);
    boundingBox[4] = vec3(x0, y0, z1);
    boundingBox[5] = vec3(x0, y1, z1);
    boundingBox[6] = vec3(x1, y0, z1);
    boundingBox[7] = vec3(x1, y1, z1);

将边界框转换为世界坐标后，我正在寻找一种方法来检查它们之间是否存在交集，但我不知道如何使用线性代数来做到这一点.

After having transformed the bounding box to world coordinates, I'm looking for a way to check if there is an intersection between two of them, but I don't know how to do it with linear algebra.

我想，如果我确定所有的框都平行于 XZ 平面，我可以简单地根据 box2 的最小/最大坐标检查 box1 的所有顶点，如下所示:

I thought that if I was sure that all the boxes were parallel to XZ plane I could simply check all the vertices of box1 against min/max coordinates of box2, like this:

for(int i = 0; i < 8; i++) {
    if(box1[i].x >= box2.minX && box1[i].x <= box2.maxX) &&
      (box1[i].y >= box2.minY && box1[i].y <= box2.maxY) &&
      (box1[i].z >= box2.minZ && box1[i].z <= box2.maxZ) {
        // collision here
    }
}

但这行不通，因为网格可能已经旋转了.有我可以使用的数学公式吗?

But this is not going to work since meshes could have been rotated. Is there a mathematical formula that I can use?

推荐答案

两个有向边界框(或更一般的两个对象之间)之间的交集可以通过分离轴定理(这里，这里和这里).

Intersections between two oriented bounding boxes (or more general between two objects) can be done by the separating axis theorem (here, here and here).

对于对象之间的一般相交测试，一种是搜索一个平面，使两个对象位于不同的半空间中，并且该平面不与其中一个对象相交.例如，可以在这篇 Gamasutra 文章.

For a general intersection tests between objects, one is searching for a plane such that the two objects lie in different halfspaces and the plane does not intersect one of the objects. An implementation of this can for example be found in this Gamasutra article.

这篇关于3D 空间中两个框之间的交点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！