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

Question

当我第一次加载对象时,我使用max和min(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(在世界空间).它很可能旋转(不再是轴对齐)

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

对于新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 opengl3 you would use an uniform instead

更干净吧

Answer 2

是的，您可以变换 8 个角顶点并对结果进行最小/最大，但有更快的方法，正如 Jim Arvo 在他的Graphics Gems (1990)一章中所描述的那样。

在性能方面，Arvo 的方法大致相当于 2 次变换而不是 8 次，基本上如下（这将 boxA转换为 box 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 在Real-Time Collision Detection ( photo ) 中对此进行了描述。

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