AABB Frustrum Culling

Started by
3 comments, last by Adam_42 13 years, 4 months ago
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[0] * (x - size) + frustum[1] * (y - size) + frustum[2]    * (z - size) + frustum[3] > 0 )      continue;    if( frustum[0] * (x + size) + frustum[1] * (y - size) + frustum[2]    * (z - size) + frustum[3] > 0 )      continue;    if( frustum[0] * (x - size) + frustum[1] * (y + size) + frustum[2]    * (z - size) + frustum[3] > 0 )      continue;    if( frustum[0] * (x + size) + frustum[1] * (y + size) + frustum[2]    * (z - size) + frustum[3] > 0 )      continue;    if( frustum[0] * (x - size) + frustum[1] * (y - size) + frustum[2]    * (z + size) + frustum[3] > 0 )      continue;    if( frustum[0] * (x + size) + frustum[1] * (y - size) + frustum[2]    * (z + size) + frustum[3] > 0 )      continue;    if( frustum[0] * (x - size) + frustum[1] * (y + size) + frustum[2]    * (z + size) + frustum[3] > 0 )      continue;    if( frustum[0] * (x + size) + frustum[1] * (y + size) + frustum[2]    * (z + size) + frustum[3] > 0 )      continue;    return false;  }  return true;}
Currently trying to make a planet renderer. After many hours of work, somehow I know It'll never be complete.
Also, If I help you, please give me an ++
Advertisement
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

[0] + frustum

[1] + frustum

[2] = frustum

[3]

Those equations say "If the point at the end of the blue line in the plane is further from the origin than frustum

[3], then the original point at the other end of the blue line is 'above' the plane."

Hope that helps.

Please don't PM me with questions. Post them in the forums for everyone's benefit, and I can embarrass myself publicly.

You don't forget how to play when you grow old; you grow old when you forget how to play.

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..
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);		bool Intersection = false;				for(int i = 0; i < 8; i++)		{			XMVECTOR PlaneDotProduct = XMPlaneDotCoord(Plane, vBoxVertices);			XMFLOAT4 fPlaneDotProduct;			XMStoreFloat4(&fPlaneDotProduct, PlaneDotProduct);			if(fPlaneDotProduct.x > 0)			{				Intersection = true;				continue;			}		}		if(!Intersection) { return FALSE; }	} 	return TRUE;}
Currently trying to make a planet renderer. After many hours of work, somehow I know It'll never be complete.
Also, If I help you, please give me an ++
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.

This topic is closed to new replies.

Advertisement