Sign in to follow this  

AABB Frustrum Culling

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

I know this has been disscussed to death, but I don't understand the implementation of it from this tutorial:

http://www.racer.nl/reference/vfc_markmorley.htm

Mainly what I don't understand is well, near enough the entire thing. I'm OK on my understanding of spherical frustrum culling, well enough to implement it, it works well on my engine, but what is the reason why the dot product of the plane and the position of the sphere has to be calculated? Isn't a dot product just an angle? I would appreciate it if you guys can not only explain to me what's happening in the sample of code below, but reinforce my knowledge on sphere frustrum culling.


bool CubeInFrustum( float x, float y, float z, float size )
{
int p;
for( p = 0; p < 6; p++ )
{
if( frustum[p][0] * (x - size) + frustum[p][1] * (y - size) + frustum[p][2] * (z - size) + frustum[p][3] > 0 )
continue;
if( frustum[p][0] * (x + size) + frustum[p][1] * (y - size) + frustum[p][2] * (z - size) + frustum[p][3] > 0 )
continue;
if( frustum[p][0] * (x - size) + frustum[p][1] * (y + size) + frustum[p][2] * (z - size) + frustum[p][3] > 0 )
continue;
if( frustum[p][0] * (x + size) + frustum[p][1] * (y + size) + frustum[p][2] * (z - size) + frustum[p][3] > 0 )
continue;
if( frustum[p][0] * (x - size) + frustum[p][1] * (y - size) + frustum[p][2] * (z + size) + frustum[p][3] > 0 )
continue;
if( frustum[p][0] * (x + size) + frustum[p][1] * (y - size) + frustum[p][2] * (z + size) + frustum[p][3] > 0 )
continue;
if( frustum[p][0] * (x - size) + frustum[p][1] * (y + size) + frustum[p][2] * (z + size) + frustum[p][3] > 0 )
continue;
if( frustum[p][0] * (x + size) + frustum[p][1] * (y + size) + frustum[p][2] * (z + size) + frustum[p][3] > 0 )
continue;
return false;
}
return true;
}

Share this post


Link to post
Share on other sites
First, the dot product of two vectors is not an angle - it's a distance = |A|*|B|*cos(theta). That's the magnitude of vector A times the magnitude of vector B times the cosine of the angle between them.

Second, do you understand that the distance being calculated is the distance along the plane normal from the plane to the point?



In the picture above, the plane is represented by the thin red lines between the axes. The plane actually extends to infinity in all directions perpendicular to the normal. The plane normal is the red vector and it's one unit long. I show the direction of the normal extended to the point of interest.

The green line is a vector formed by subtracting the coordinates of a point in the plane from the coordinates of the point. I've chosen the intersection of the plane with the Y axis, but it could be any point in the plane.

The thick blue line is the dot product of the green line with the normal. The length of that blue line is the distance from the point to the plane.

Unfortuanately, the total derivation of the equations in the link you posted (and the equations you posted above) is somewhat lengthy but is based on the fact:

frustum[p][0] + frustum[p][1] + frustum[p][2] = frustum[p][3]

Those equations say "If the point at the end of the blue line in the plane is further from the origin than frustum[p][3], then the original point at the other end of the blue line is 'above' the plane."

Hope that helps.

Share this post


Link to post
Share on other sites
Pick the AABB vertex by plane normal. (check the sign on each axis of the normal and choose the best point*)
Check it against the plane. (check the sign of distance to plane (dot(n,p)-d)
Do that for every plane.
It's much faster.

*almost everything depends on the direction of frustum plane normals - whether they are pointing away from frustum..

Share this post


Link to post
Share on other sites
Cheers guys, I think I understand it better now. Here's what I just wrote, can you see any immediate problems or optimisations I can do? (Snake5 I'm not sure exactly what you mean)


bool DXCamera11::BoxInFrustrum(XMFLOAT3 Position, float Size)
{
XMVECTOR vBoxVertices[8];
vBoxVertices[0] = XMVectorSet(Position.x-Size, Position.y-Size, Position.z-Size, 0.0f);
vBoxVertices[1] = XMVectorSet(Position.x-Size, Position.y-Size, Position.z-Size, 0.0f);
vBoxVertices[2] = XMVectorSet(Position.x-Size, Position.y+Size, Position.z+Size, 0.0f);
vBoxVertices[3] = XMVectorSet(Position.x-Size, Position.y+Size, Position.z+Size, 0.0f);

vBoxVertices[4] = XMVectorSet(Position.x+Size, Position.y-Size, Position.z+Size, 0.0f);
vBoxVertices[5] = XMVectorSet(Position.x+Size, Position.y-Size, Position.z+Size, 0.0f);
vBoxVertices[6] = XMVectorSet(Position.x+Size, Position.y+Size, Position.z-Size, 0.0f);
vBoxVertices[7] = XMVectorSet(Position.x+Size, Position.y+Size, Position.z-Size, 0.0f);

for(int i = 0; i < 6; i++)
{
XMVECTOR Plane = XMLoadFloat4(&m_ViewFrustrum[i]);

bool Intersection = false;

for(int i = 0; i < 8; i++)
{
XMVECTOR PlaneDotProduct = XMPlaneDotCoord(Plane, vBoxVertices[i]);
XMFLOAT4 fPlaneDotProduct;
XMStoreFloat4(&fPlaneDotProduct, PlaneDotProduct);

if(fPlaneDotProduct.x > 0)
{
Intersection = true;
continue;
}
}

if(!Intersection) { return FALSE; }
}

return TRUE;
}

Share this post


Link to post
Share on other sites
One trick you can use to speed things up is to wrap a sphere round your box. Since the sphere test is much quicker you can save a lot of work (you only need to test the box if the sphere intersects the plane).

It can also be helpful to remember for each object which plane it last failed on, and then test that one first next time. There's a good chance that it'll still be the wrong side of the same plane in the next frame.

Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this