Sign in to follow this  
ic0de

am I making a mistake with my frustum culling?

Recommended Posts

I am trying to test an AABB against a frustum, the frustum is set up as a 6x4 2d array (6 plane equations). Somehow my code isn't exactly right. Here it is:

bool AABBInFrustum(vec min, vec max)
{
	float m, n; 
        int i;

	for (i = 0; i < 6; i++) 
	{
                //basically two dot products
		m = (min.x * Vfrustum[i][0]) + (min.y * Vfrustum[i][1]) + (min.z * Vfrustum[i][2]) + Vfrustum[i][3];
		n = (max.x * fabs(Vfrustum[i][0])) + (max.y * fabs(Vfrustum[i][1])) + (max.z * fabs(Vfrustum[i][2]));

		if(m + n < 0) 
		{
			return false;
		}
		if(m - n < 0) 
		{
			return true;
		}
	} 

	return true;
} 

I got the algorithm from here:
http://www.cescg.org/CESCG-2002/DSykoraJJelinek/index.html
 

min and max in my code are the two farthest corners of an axis aligned bounding box, I think that might be where I made a mistake I think I need to do something to the points before they can be plugged into the algorithm but the source isn't quite clear. Anybody know how to fix it?

Edited by ic0de

Share this post


Link to post
Share on other sites
This is how I do it.
	/**
	 * Classifies an axis-aligned bounding box in relation to a given plane.
	 *
	 * \param _aAabb The AABB to test against the given plane.
	 * \param _pPlane The plane to test against the given AABB.
	 * \return Returns a plane classification.
	 */
	LSE_INLINE LSM_PLANE_INTERSECT LSE_CALL CClassify::Aabb( const CAabb &_aAabb, const CPlane3 &_pPlane ) {
		// Center of the AABB.
		CVector3 vC = (_aAabb.m_vMax + _aAabb.m_vMin) * LSM_HALF;
		// Positive extents.
		CVector3 vE = _aAabb.m_vMax - vC;

		// Compute the projected interval radius of _aAabb onto L(t) = _aAabb.c + t * _pPlane.n.
		LSREAL fR = vE[0] * CMathLib::Abs( _pPlane.n[0] ) +
			vE[1] * CMathLib::Abs( _pPlane.n[1] ) +
			vE[2] * CMathLib::Abs( _pPlane.n[2] );

		// Distance from box center to plane.
		LSREAL fS = _pPlane.n.Dot( vC ) - _pPlane.dist;

		// If less than R, return overlap.
		if ( CMathLib::Abs( fS ) <= fR ) { return LSM_PI_INTERSECT; }
		// Otherwise it is in front or back of the plane.
		return fS > fR ? LSM_PI_FRONT : LSM_PI_BACK;
	}
	/**
	 * Determines if the given AABB is partially or entirely inside the frustum.
	 *
	 * \param _aAabb The AABB to check for being partially or fully inside the frustum.
	 * \param _fFrustum The frustum.
	 * \return Returns true if the AABB is fully or partially inside the given frustum.
	 */
	LSE_INLINE LSBOOL LSE_CALL CTest::AabbFrustum( const CAabb &_aAabb, const CFrustum &_fFrustum ) {
		if ( (CClassify::Aabb( _aAabb, _fFrustum[LSM_FP_LEFT] ) == LSM_PI_BACK)
			|| (CClassify::Aabb( _aAabb, _fFrustum[LSM_FP_RIGHT] ) == LSM_PI_BACK)
			|| (CClassify::Aabb( _aAabb, _fFrustum[LSM_FP_TOP] ) == LSM_PI_BACK)
			|| (CClassify::Aabb( _aAabb, _fFrustum[LSM_FP_BOTTOM] ) == LSM_PI_BACK)
			|| (CClassify::Aabb( _aAabb, _fFrustum[LSM_FP_NEAR] ) == LSM_PI_BACK)
			|| (CClassify::Aabb( _aAabb, _fFrustum[LSM_FP_FAR] ) == LSM_PI_BACK) ) {
			return false;
		}
		return true;
	}
The frustum is made of planes and each plane is a CVector3 and float distance.
Don’t mix your types. For example, you are doing a dot product manually. Why? Use your primitive types everywhere so that what you are doing is not only clearer but easier and faster to code.


L. Spiro

Share this post


Link to post
Share on other sites

your bug is indeed in 

m = (min.x * Vfrustum[i][0]) + (min.y * Vfrustum[i][1]) + (min.z * Vfrustum[i][2]) + Vfrustum[i][3];
n = (max.x * fabs(Vfrustum[i][0])) + (max.y * fabs(Vfrustum[i][1])) + (max.z * fabs(Vfrustum[i][2]));

while you are using min and max, the paper actually states

Vector (mx,my,mz) represents the center of the AABB. Absolute values of the normal vector of the plane (a,b,c) transform all possible values to the first octant so its dot product with the vector representing a half of the AABB diagonal (dx,dy,dz) will be always positive.

 

so what you actually want to do is

 

 

m = ((min.x+max.x)*0.5f * Vfrustum[i][0]) + ((min.y+max.y)*0.5f * Vfrustum[i][1]) + ((min.z+max.z)*0.5f * Vfrustum[i][2]) + Vfrustum[i][3];
n = ((max.x-min.x)*0.5f * fabs(Vfrustum[i][0])) + ((max.y-min.y)*0.5f * fabs(Vfrustum[i][1])) + ((max.z-min.z)*0.5f * fabs(Vfrustum[i][2]));

Share this post


Link to post
Share on other sites

your bug is indeed in 

m = (min.x * Vfrustum[i][0]) + (min.y * Vfrustum[i][1]) + (min.z * Vfrustum[i][2]) + Vfrustum[i][3];
n = (max.x * fabs(Vfrustum[i][0])) + (max.y * fabs(Vfrustum[i][1])) + (max.z * fabs(Vfrustum[i][2]));
while you are using min and max, the paper actually states

Vector (mx,my,mz) represents the center of the AABB. Absolute values of the normal vector of the plane (a,b,c) transform all possible values to the first octant so its dot product with the vector representing a half of the AABB diagonal (dx,dy,dz) will be always positive.

 
so what you actually want to do is
 
 
 
m = ((min.x+max.x)*0.5f * Vfrustum[i][0]) + ((min.y+max.y)*0.5f * Vfrustum[i][1]) + ((min.z+max.z)*0.5f * Vfrustum[i][2]) + Vfrustum[i][3];
n = ((max.x-min.x)*0.5f * fabs(Vfrustum[i][0])) + ((max.y-min.y)*0.5f * fabs(Vfrustum[i][1])) + ((max.z-min.z)*0.5f * fabs(Vfrustum[i][2]));


 
Thank you, it works now

Share this post


Link to post
Share on other sites

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