Intersection between two boxes in 3D space

问题:

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

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.

This box is defined by eight vertices

    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.

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?

回答1:

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

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.

回答2:

/measure overlap between 3D bounding boxes, parametrized by (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;