3D 中两个框之间的交集 space

Question

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

我不知道这是否是常用的方法，但我的想法是将任何固体对象（如网格或相机）绑定在 3D 盒子内，这会比我得到更准确的结果一个球体。

这个框由八个顶点定义

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

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

我想如果我确定所有的盒子都平行于 XZ 平面，我可以简单地检查盒子 1 的所有顶点与盒子 2 的 min/max 坐标，如下所示：

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

但这行不通，因为网格可以旋转。有我可以使用的数学公式吗？

Answer 1

可以通过分离轴定理 (here, here and here) 来完成两个定向边界框（或更一般的两个对象之间）之间的交集。

对于对象之间的一般相交测试，正在搜索一个平面，使得两个对象位于不同的半空间中，并且该平面不与其中一个对象相交。例如，可以在 Gamasutra article.

中找到它的实现

Answer 2

/测量 3D 边界框之间的重叠，参数化为 (ry, h, w, l, tx, ty, tz)/

inline double box3DOverlap(tDetection d, tGroundtruth g, int32_t criterion = -1)

using namespace boost::geometry;
Polygon gp = toPolygon(g);
Polygon dp = toPolygon(d);

std::vector<Polygon> in, un;
intersection(gp, dp, in);
union_(gp, dp, un);

double ymax = min(d.t2, g.t2);
double ymin = max(d.t2 - d.h, g.t2 - g.h);

double inter_area = in.empty() ? 0 : area(in.front());
double inter_vol = inter_area * max(0.0, ymax - ymin);

double det_vol = d.h * d.l * d.w;
double gt_vol = g.h * g.l * g.w;

double o;
if(criterion==-1)     // union
    o = inter_vol / (det_vol + gt_vol - inter_vol);
else if(criterion==0) // bbox_a
    o = inter_vol / det_vol;
else if(criterion==1) // bbox_b
    o = inter_vol / gt_vol;

return o;

3D 中两个框之间的交集 space

Intersection between two boxes in 3D space

3d

collision-detection

linear-algebra