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

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

但它没有按预期工作......我做错了什么？

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（在世界空间中）。它很可能旋转（不再轴对齐）。

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

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

这不是最优的（AABB 方面）。您将获得大量空白空间，但从性能角度来看，重新计算整个网格的 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

更清晰，对吗？

Answer 2

是的，您可以变换八个角顶点并对结果进行最小/最大处理，但是有一种更快的方法，如 Jim Arvo 在 Graphics Gems (1990) 的章节中所述。

在性能方面，Arvo 的方法大致相当于两次变换，而不是八次，基本上如下（这将框 A 变换为框 B）

// Split the transform into a translation vector (T) and a 3x3 rotation (M).

B = zero-volume AABB at T
for each element (i,j) of M:
   a = M[i][j] * A.min[j]
   b = M[i][j] * A.max[j]
   B.min[i] += a < b ? a : b
   B.max[i] += a < b ? b : a
return B

Arvo 方法的一种变体使用中心/ 范围表示而不是最小/最大，这是由 Christer Ericson 在实时碰撞检测中描述的（照片）。

Graphics Gems 文章的完整 C 代码可以在此处找到。

Answer 3

引用之前的回复AABB @ 堆栈溢出：

“遗憾的是，如果你的角色轮换，你需要重新计算你的 AABB ......

Skurmedel

---

受访者的建议和我的建议是，一旦你有 AABB 工作，就实施定向边界框，并且还要注意，你可以制作网格部分的 aabb比每个物体都用一个巨大的盒子更准确地伪造​​碰撞检测。

Answer 4

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

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

还有一个问题是朝哪个方向旋转（？）。如果总是在一个方向，则只能在该方向放大 AABB。

您也可以选择使用边界球来代替 AABB。那么你就不用关心旋转，缩放也不是问题。

Answer 5

为什么不使用你的 GPU？今天我通过渲染几个帧来实现这个问题的解决方案。

1. 将相机暂时放置在物体上方，指向物体
   向下看向物体。
2. 仅渲染您的对象，没有灯光或
   任何事物。
3. 也使用正交投影。
4. 然后读取帧缓冲区。黑色像素的行和列意味着模型不存在。击中一个白色像素 - 您击中了模型 AABB 边框之一。

我知道这并不是适用于所有情况的解决方案，但根据一些先验知识，这是非常有效的。

有关屏幕外渲染的信息，请参阅此处。