如何在平移/旋转后重新计算轴对齐的边界框

Question

当我第一次加载我的对象时，我用最大和最小 (x,y,z) 点计算初始 AABB。但这是在物体空间中，物体在世界各地移动，更重要的是，它在旋转。

每次平移/旋转对象时如何重新计算新的 AABB？这基本上发生在每一帧。每帧重新计算新的 AABB 是否会是一项非常密集的操作？如果是这样，有什么替代方案？

我知道 AABB 会使我的碰撞检测不那么准确，但是实现碰撞检测代码比 OBB 更容易，我想一次迈出这一步。

在从以下答案中获得一些见解后，这是我当前的代码：

 typedef struct sAxisAlignedBoundingBox {
    Vector3D bounds[8];
    Vector3D max, min;
} AxisAlignedBoundingBox;

void drawAxisAlignedBoundingBox(AxisAlignedBoundingBox box) {
    glPushAttrib(GL_LIGHTING_BIT | GL_POLYGON_BIT);

    glEnable(GL_COLOR_MATERIAL);
    glDisable(GL_LIGHTING);

    glColor3f(1.0f, 1.0f, 0.0f);

    glBegin(GL_LINE_LOOP);
        glVertex3f(box.bounds[0].x, box.bounds[0].y, box.bounds[0].z);
        glVertex3f(box.bounds[1].x, box.bounds[1].y, box.bounds[1].z);
        glVertex3f(box.bounds[2].x, box.bounds[2].y, box.bounds[2].z);
        glVertex3f(box.bounds[3].x, box.bounds[3].y, box.bounds[3].z);
    glEnd();

    glBegin(GL_LINE_LOOP);
        glVertex3f(box.bounds[4].x, box.bounds[4].y, box.bounds[4].z);
        glVertex3f(box.bounds[5].x, box.bounds[5].y, box.bounds[5].z);
        glVertex3f(box.bounds[6].x, box.bounds[6].y, box.bounds[6].z);
        glVertex3f(box.bounds[7].x, box.bounds[7].y, box.bounds[7].z);
    glEnd();

    glBegin(GL_LINE_LOOP);
        glVertex3f(box.bounds[0].x, box.bounds[0].y, box.bounds[0].z);
        glVertex3f(box.bounds[5].x, box.bounds[5].y, box.bounds[5].z);
        glVertex3f(box.bounds[6].x, box.bounds[6].y, box.bounds[6].z);
        glVertex3f(box.bounds[1].x, box.bounds[1].y, box.bounds[1].z);
    glEnd();

    glBegin(GL_LINE_LOOP);
        glVertex3f(box.bounds[4].x, box.bounds[4].y, box.bounds[4].z);
        glVertex3f(box.bounds[7].x, box.bounds[7].y, box.bounds[7].z);
        glVertex3f(box.bounds[2].x, box.bounds[2].y, box.bounds[2].z);
        glVertex3f(box.bounds[3].x, box.bounds[3].y, box.bounds[3].z);
    glEnd();

    glPopAttrib();
}

void calculateAxisAlignedBoundingBox(GLMmodel *model, float matrix[16]) {
    AxisAlignedBoundingBox box;
    float dimensions[3];

    // This will give me the absolute dimensions of the object
    glmDimensions(model, dimensions);

    // This calculates the max and min points in object space
    box.max.x = dimensions[0] / 2.0f, box.min.x = -1.0f * box.max.x;
    box.max.y = dimensions[1] / 2.0f, box.min.y = -1.0f * box.max.y;
    box.max.z = dimensions[2] / 2.0f, box.min.z = -1.0f * box.max.z;

    // These calculations are probably the culprit but I don't know what I'm doing wrong
    box.max.x = matrix[0] * box.max.x + matrix[4] * box.max.y + matrix[8] * box.max.z + matrix[12];
    box.max.y = matrix[1] * box.max.x + matrix[5] * box.max.y + matrix[9] * box.max.z + matrix[13];
    box.max.z = matrix[2] * box.max.x + matrix[6] * box.max.y + matrix[10] * box.max.z + matrix[14];
    box.min.x = matrix[0] * box.min.x + matrix[4] * box.min.y + matrix[8] * box.min.z + matrix[12];
    box.min.y = matrix[1] * box.min.x + matrix[5] * box.min.y + matrix[9] * box.min.z + matrix[13];
    box.min.z = matrix[2] * box.min.x + matrix[6] * box.min.y + matrix[10] * box.min.z + matrix[14];

    /* NOTE: If I remove the above calculations and do something like this:

             box.max = box.max + objPlayer.position;
             box.min = box.min + objPlayer.position;

             The bounding box will move correctly when I move the player, the same does not
             happen with the calculations above. It makes sense and it's very simple to move
             the box like this. The only problem is when I rotate the player, the box should
             be adapted and increased/decreased in size to properly fit the object as a AABB.
    */

    box.bounds[0] = Vector3D(box.max.x, box.max.y, box.min.z);
    box.bounds[1] = Vector3D(box.min.x, box.max.y, box.min.z);
    box.bounds[2] = Vector3D(box.min.x, box.min.y, box.min.z);
    box.bounds[3] = Vector3D(box.max.x, box.min.y, box.min.z);
    box.bounds[4] = Vector3D(box.max.x, box.min.y, box.max.z);
    box.bounds[5] = Vector3D(box.max.x, box.max.y, box.max.z);
    box.bounds[6] = Vector3D(box.min.x, box.max.y, box.max.z);
    box.bounds[7] = Vector3D(box.min.x, box.min.y, box.max.z);

    // This draw call is for testing porpuses only
    drawAxisAlignedBoundingBox(box);
}

void drawObjectPlayer(void) {
    static float mvMatrix[16];

    if(SceneCamera.GetActiveCameraMode() == CAMERA_MODE_THIRD_PERSON) {
        objPlayer.position = SceneCamera.GetPlayerPosition();
        objPlayer.rotation = SceneCamera.GetRotationAngles();

        objPlayer.position.y += -PLAYER_EYE_HEIGHT + 0.875f;

        /* Only one of the two code blocks below should be active at the same time
           Neither of them is working as expected. The bounding box doesn't is all
           messed up with either code. */

        // Attempt #1
        glPushMatrix();
            glTranslatef(objPlayer.position.x, objPlayer.position.y, objPlayer.position.z);
            glRotatef(objPlayer.rotation.y + 180.0f, 0.0f, 1.0f, 0.0f);
            glCallList(gameDisplayLists.player);
            glGetFloatv(GL_MODELVIEW_MATRIX, mvMatrix);
        glPopMatrix();

        // Attempt #2
        glPushMatrix();
            glLoadIdentity();
            glTranslatef(objPlayer.position.x, objPlayer.position.y, objPlayer.position.z);
            glRotatef(objPlayer.rotation.y + 180.0f, 0.0f, 1.0f, 0.0f);
            glGetFloatv(GL_MODELVIEW_MATRIX, mvMatrix);
        glPopMatrix();

        calculateAxisAlignedBoundingBox(objPlayer.model, mvMatrix);
    }
}

但它不能正常工作……我做错了什么？

原文由 rfgamaral 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

只需重新计算转换后的 AABB 的 AABB。这意味着转换 8 个顶点（8 个顶点 - 矩阵乘法）和 8 个顶点-顶点比较。

因此，在初始化时，您在模型空间中计算 AABB：对于模型的每个顶点的每个 x、y、z，您检查 xmin、xmax、ymin、ymax 等。

对于每一帧，您都会生成一个新的变换矩阵。在 OpenGL 中，这是通过 glLoadIdentity 后跟 glTransform/Rotate/Scale（如果使用旧 API）来完成的。正如 lmmilewski 所说，这就是模型矩阵。

您第二次计算这个变换矩阵（在 OpenGL 之外，例如使用 glm ）。您还可以使用 glGet 获得 OpenGL 的结果矩阵。

您将 AABB 的八个顶点中的每一个乘以该矩阵。使用 glm 进行矩阵向量乘法。您将获得经过改造的 AABB（在世界空间中）。它很可能是旋转的（不再是轴对齐的）。

现在你的算法可能只适用于轴对齐的东西，因此你的问题。所以现在你通过 takinf 变换后的边界框的边界框来近似变换后模型的新边界框：

对于新 AABB 的每个顶点的每个 x、y、z，您检查 xmin、xmax、ymin、ymax 等。这为您提供了一个可以在裁剪算法中使用的世界空间 AABB。

这不是最优的（AABB-wise）。你会得到很多空白空间，但在性能方面，重新计算整个网格的 AABB 要好得多。

---

至于变换矩阵，在drawObjectPlayer中：

 gLLoadIdentity();
glTranslatef(objPlayer.position.x, objPlayer.position.y, objPlayer.position.z);
glRotatef(objPlayer.rotation.y + 180.0f, 0.0f, 1.0f, 0.0f);
glGetFloatv(GL_MODELVIEW_MATRIX, mvMatrix);
// Now you've got your OWN Model Matrix (don't trust the GL_MODELVIEW_MATRIX flag : this is a workaround, and I know what I'm doing ^^ )

gLLoadIdentity(); // Reset the matrix so that you won't make the transformations twice
gluLookAt( whatever you wrote here earlier )
glTranslatef(objPlayer.position.x, objPlayer.position.y, objPlayer.position.z);
glRotatef(objPlayer.rotation.y + 180.0f, 0.0f, 1.0f, 0.0f);
// Now OpenGL is happy, he's got his MODELVIEW matrix correct ( gluLookAt is the VIEW part; Translate/Rotate is the MODEL part
glCallList(gameDisplayLists.player); // Transformed correcty

我无法进一步解释……正如评论中所说，你必须做两次。顺便说一句，您不会在 OpenGL 3 中遇到这些问题和丑陋的解决方法，因为您将对自己的矩阵负全部责任。等效于 OpenGL 2：

 glm::mat4 ViewMatrix = glm::LookAt(...);
glm::mat4 ModelMatrix = glm::rotate() * glm::translate(...);
// Use ModelMatrix for whatever you want
glm::mat4 ModelViewMatrix = ViewMatrix * ModelMatrix;
glLoadMatrix4fv( &ModelViewMatrix[0][0] ); // In OpenGL 3 you would use an uniform instead

干净多了，对吧？

原文由 Calvin1602 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

为此，您必须遍历每个顶点，计算其在世界中的位置（乘以模型视图）并找到每个对象内的最小/最大顶点坐标（就像您第一次计算它时一样）。

您可以稍微缩放您的 AABB，这样您就不必重新计算它 - 将其放大 sqrt(2) 倍就足够了 - 您的旋转对象总是适合 AABB。

还有一个问题是你旋转的方向（？）。如果总是合二为一，那么您只能在那个方向上扩大 AABB。

或者，您可以使用边界球代替 AABB。然后你不关心旋转和缩放不是问题。

原文由 Łukasz Milewski 发布，翻译遵循 CC BY-SA 4.0 许可协议