AABB box intersection test

This topic is 1180 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

I'm trying to get view frustrum culling working. I found a neat, cheap way in an article to test if an AABB intersects the view frustrum: https://fgiesen.wordpress.com/2010/10/17/view-frustum-culling/ method5

I don't particullarly care if a model is partially inside the view frustrum (not yet anyway - maybe its more important later on?) so it just tests if its in or not.

Also I keep the AABB in object space and use world-view-projection matrix to retrieve the planes.

The issue I have is that it never reports that the AAB isn't in the frustrum - no matter how I orient myself, the AABB is always inside or partially inside. Are there any obvious bugs?

float signum(float val)
{
if (val > 0.0f) return 1.0f;
if (val < 0.0f) return -1.0f;

return 0.0f;
}

FrustrumPlanes GetFrustrumPlanes(const Mat4& WVPMatrix)
{
FrustrumPlanes ret;

ret[0] = WVPMatrix[3] + WVPMatrix[0];
ret[1] = WVPMatrix[3] - WVPMatrix[0];
ret[2] = WVPMatrix[3] - WVPMatrix[1];
ret[3] = WVPMatrix[3] + WVPMatrix[1];
ret[4] = WVPMatrix[2];
ret[5] = WVPMatrix[3] - WVPMatrix[2];

for (Plane& plane : ret)
plane = glm::normalize(plane);

return ret;
}

bool DoesAABBIntersectViewFrustrum(const Vec3& aabbCenter, const Vec3& aabbExtent, const Mat4& WVPMatrix)
{
FrustrumPlanes planes = GetFrustrumPlanes(WVPMatrix);

for (const Plane& plane : planes)
{
Vec3 signFlip(signum(plane.x), signum(plane.y), signum(plane.z));
if (glm::dot(aabbCenter + aabbExtent * signFlip, Vec3(plane)) > -plane.w)
return true;
}

return false;
}


Share on other sites

I think your issue might be the wrong space. If you want to keep your AABB in object space, then you must transform the frustum into the objects object space too (in this case you would need the inverse MVP matrix). But if you want an easy, quick way,I wouldn't transform the frustum into object space of each object (you need to calculate the inverse transform).

To keep it simple, you should test the world space AABB vs the world space frustum. Calculate the frustum planes once and test it versus all world space AABBs. To create your AABB, you need to calculate the world AABB form your model orientation and object space AABB (which is althoug called OBB, oriented bounding box). Check this site for an example of how to get your world AABB from an OBB. The advantage of this is, that you only need to recaluclate the AABB of each object if its moves or rotates, which isn't needed for most static models.

Share on other sites
A short note on not wanting to know if it intersects. If you want to have some sort of space partitioning in the near future (for culling and more), it can be useful to know if it intersects, to determine whether you need to check the children aabb's within a bigger aabb (partition of your world).

Share on other sites

Are you sure you want to build an instance of the frustum each time you're classifying the six planes? One problem is that you're creating two instances which can be slow.

For instance, If you're using a camera frustum you can consideer giving a frustum instance to the camera and construct it using the camera parameters when it is time to update the camera matrices.

Enumerate the frustum planes, give an instance to the container class and use an update function that compute the frustum planes based off the matrix or camera perspective projection parameters. You can also make an structure containing the classification information.

Something like:

bool FrustumAabb( const AABB& _aAabb, const Frustum& _fFrustum, F_FRUSTUM_CLASSIFY& _fcClassify );

or just:

bool FrustumAabb( const AABB& _aAabb, const Frustum& _fFrustum );

In the intersection method:

for each object
if ( FrustumAabb( object.aabb(), camera.frustum() ) )
quack
Edited by Irlan

Share on other sites

You forgot to handle the near clipping plane, which should be:

ret[4] = WVPMatrix[3] + WVPMatrix[2];

It is always a mistake to simplify the near plane “just because it’s only a small difference”.

Are there any obvious bugs?

#1: Your formulation of the math is suspect.
The plane’s dot product is with the center of the AABB.

But assuming the math works, you definitely will always get a positive (true) result because:

#2: You are returning true if the AABB is in front of (or intersecting) any plane on the frustum, which will always be the case in a well formed frustum.

You should instead be checking for the opposite, and returning false if the AABB is fully behind any plane in the frustum.

You should return true only if the AABB is in front of or intersecting all planes.

Additionally, Irlan is correct in mentioning the use of enumerated values for the frustum.

Furthermore, a plane<->AABB test must return either. FRONT, INTERSECT, or BACK.

If you are concerned about performance (as you should be with a frustum test) you will store planes with a -W (negate them after you extract them from the matrix).  This simplifies many plane equations, such as the one you have posted, which requires you to repeatedly (perhaps 100 times per frame instead of 6?) negate the W.

Also your implementation of signum() has branches.  You should use something more efficient while properly returning [-1, 0, 1].

L. Spiro

Edited by L. Spiro

Share on other sites

Object space AABB culling work by first combining model matrix and viewProj matrix and then extracting planes from that. Because you don't actually care about planes but just the test result you should defer the plane calculation until its used then early out will save a lot more math. You actually don't need the distance but just the comparison result so you can omit the normalization.

My version can be found here http://pastebin.com/3uJmYXPT

Share on other sites

Object space AABB culling work by first combining model matrix and viewProj matrix and then extracting planes from that. Because you don't actually care about planes but just the test result you should defer the plane calculation until its used then early out will save a lot more math. You actually don't need the distance but just the comparison result so you can omit the normalization.

My version can be found here http://pastebin.com/3uJmYXPT

Is the "frustrummatrix" just the inverse world-view-proj matrix? I guess it is row-major aswell? (I'm using column-major instead - but actually, does it really matter?)

Edited by KaiserJohan

Share on other sites

Object space AABB culling work by first combining model matrix and viewProj matrix and then extracting planes from that. Because you don't actually care about planes but just the test result you should defer the plane calculation until its used then early out will save a lot more math. You actually don't need the distance but just the comparison result so you can omit the normalization.

My version can be found here http://pastebin.com/3uJmYXPT

Is the "frustrummatrix" just the inverse world-view-proj matrix? I guess it is row-major aswell? (I'm using column-major instead - but actually, does it really matter?)

No need for inversing.Its just world-view-proj matrix. Its colum major.

Theory behind method can be found here. https://fgiesen.wordpress.com/2012/08/31/frustum-planes-from-the-projection-matrix/

Share on other sites

Thanks, I got it working almost.

One thing I dont understand though is now when I'm trying to implement INSIDE/PARTIAL/OUTSIDE cases, how should I proceed?

I have a pretty traditional scene graph, a root node and child nodes with leaves.

Here's how I understand it:

• if node is OUTSIDE, continue
• if node is PARTIAL, dont render models mesh, instead render its child meshes (?) but what if 4/6 planes are inside frustrum for example?
• if node is INSIDE, render full mesh(?)

Something like this is what I have right now:

    FrustrumIntersection IsAABBInFrustum(const Vec3& center, const Vec3& extent, const Mat4& frustumMatrix)
{
const Vec4 rowX(frustumMatrix[0].x, frustumMatrix[1].x, frustumMatrix[2].x, frustumMatrix[3].x);
const Vec4 rowY(frustumMatrix[0].y, frustumMatrix[1].y, frustumMatrix[2].y, frustumMatrix[3].y);
const Vec4 rowZ(frustumMatrix[0].z, frustumMatrix[1].z, frustumMatrix[2].z, frustumMatrix[3].z);
const Vec4 rowW(frustumMatrix[0].w, frustumMatrix[1].w, frustumMatrix[2].w, frustumMatrix[3].w);

FrustrumIntersection ret(FRUSTRUM_INTERSECTION_INSIDE);

// left, right, bottom, top, near, far planes
std::array<Vec4, 6> planes = { rowW + rowX, rowW - rowX, rowW + rowY, rowW - rowY, rowW + rowZ, rowW - rowZ };
float d = 0.0f, r = 0.0f;
for (const Vec4& plane : planes)
{
d = glm::dot(Vec3(plane), center);
r = glm::dot(glm::abs(Vec3(plane)), extent);

if (d + r > -plane.w)
ret = FRUSTRUM_INTERSECTION_PARTIAL;
if (d + r < -plane.w)
return FRUSTRUM_INTERSECTION_OUTSIDE;
}

return ret;
}


Never returns INSIDE, only PARTIAL or OUTSIDE. I assume I am calculating INSIDE case wrong?

And heres how I cull the scene graph and add to render queue:

    void Engine::CullModels(const std::vector<ModelPtr>& allModels, const Mat4& viewProjectionMatrix, const Mat4& parentTransform)
{
// TODO: not very cache-friendly
// this could be a CPU-hotspot for complex scenes
FrustrumIntersection aabbIntersection(FRUSTRUM_INTERSECTION_INSIDE);
for (const ModelPtr model : allModels)
{
if (!model)
continue;

Mat4 worldMatrix = parentTransform;
if (model->mSceneNode)
worldMatrix *= model->mSceneNode->GetNodeTransform();
const Mat4 worldViewProjMatrix = viewProjectionMatrix * worldMatrix;

aabbIntersection = IsAABBInFrustum(model->GetAABBCenter(), model->GetAABBExtent(), worldViewProjMatrix);
if (aabbIntersection == FRUSTRUM_INTERSECTION_OUTSIDE)
continue;

if (aabbIntersection == FRUSTRUM_INTERSECTION_INSIDE && model->mMesh != INVALID_MESH_ID)
{
const MaterialPtr material(model->mMaterial);
if (material)
mRenderQueue.emplace_back(Renderable(model->mMesh, worldViewProjMatrix, worldMatrix, model->mMaterialTilingFactor,
Vec4(material->mDiffuseColor, 1.0f), Vec4(material->mAmbientColor, 1.0f), Vec4(material->mSpecularColor, 1.0f), Vec4(material->mEmissiveColor, 1.0f),
material->mDiffuseTexture, material->mNormalTexture, material->mSpecularFactor));
else
mRenderQueue.emplace_back(Renderable(model->mMesh, worldViewProjMatrix, worldMatrix));
}

// if PARTIAL or INSIDE, go through children... is this correct?
CullModels(model->mChildren, viewProjectionMatrix, worldMatrix);
}
}