如何在平移/旋转后重新计算轴对齐边界框？ [英] How to recalculate axis-aligned bounding box after translate/rotate?

问题描述

当我第一次加载我的对象，我用最大和最小（x，y，z）点计算初始AABB。但是这是在对象空间，对象移动世界，更重要的是，旋转。

When I first load my object I calculate the initial AABB with the max and min (x,y,z) points. But this is in object space and the object moves around the world and more importantly, rotates.

如何在每次翻译/旋转对象时重新计算新的AABB？这基本上每帧发生，是否将是一个非常密集的操作，重新计算新的AABB每帧？

How do I recalculate the new AABB every time the object is translated/rotated? This happens basically every frame, is it going to be a very intensive operation to recalculate the new AABB every frame? If so, what would be the alternative?

我知道AABB会使我的碰撞检测不太准确，但它比OBB更容易实现碰撞检测代码，我想采取

I know AABBs will make my collision detection less accurate but it's easier to implement the collision detection code than OBBs and I want to take this one step at a time.

以下是我现在的代码：

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

但它不工作，因为它应该

But it doesn't work as it should... What I'm doing wrong?

推荐答案

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

Simply recompute the AABB of the transformed AABB. This means transforming 8 vertices ( 8 vertex - matrix multiplications ) and 8 vertex-vertex comparisons.

所以在初始化时，你在模型空间中计算你的AABB： y，z的模型的每个顶点，你检查xmin，xmax，ymin，ymax，...

So at initialisation, you compute your AABB in model space : for each x,y,z of each vertex of the model, you check against xmin, xmax, ymin, ymax, ...

每一帧，你生成一个新的变换矩阵。在OpenGL中，这是通过glLoadIdentity，然后是glTransform / Rotate / Scale（如果使用旧的API）。这是模型矩阵，如lmmilewski所说。

Each frame, you generate a new transformation matrix. In OpenGL this is done with glLoadIdentity followed by glTransform/Rotate/Scale (if using the old API). This is the Model Matrix, as lmmilewski said.

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

You compute this transformation matrix a second time (outside Opengl, for instance using glm). You also can get OpenGL's resulting matrix using glGet.

您将每个AABB的八个顶点乘以此矩阵。使用glm进行矩阵向量乘法。你会得到你转换的AABB（在世界空间）。

You multiply each of your AABB's eight vertices by this matrix. Use glm for matrix-vector multiplication. You'll get your transformed AABB (in world space). It it most probably rotated (not axis-aligned anymore)

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

Now your algorithm probably only work with axis-aligned stuff, hence your question. So now you approximate the new bounding box of the transformed model by takinf the bounding box of the transformed bounding box:

为每个顶点的每个x，y，z新的AABB，你检查xmin，xmax，ymin，ymax，...这给了一个世界空间AABB，您可以在您的剪切算法中使用。

for each x,y,z of each vertex of the new AABB, you check against xmin, xmax, ymin, ymax, ... this gives you an world-space AABB that you can use in your clipping algorithm.

不是最优的（AABB-wise），你会得到大量的空白空间，但性能上，重新计算整个网格的AABB好得多。

This is not optimal (AABB-wise), you'll get lots of empty space, but performance-wise, it's much much better that recomputing the AABB of the whole mesh.

对于变换矩阵，在drawObjectPlayer中：

As for the transformation matrix, in 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中有这些问题和丑陋的解决方法：btw，因为你完全负责自己的矩阵。在OpenGL 2中是等价的：

Can't explain further than that... as said in the comments, you had to do it twice. You wouldn't have these problems and ugly workarounds in OpenGL 3, btw, because you'd be fully responsible of your own matrices. Equivalent in 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

更干净的权利

这篇关于如何在平移/旋转后重新计算轴对齐边界框？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！