View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

# Frustum culling discrepancy

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

19 replies to this topic

Posted 11 October 2013 - 04:15 AM

Hi all

I've just noticed that my DIP calls is higher than it should be and it turns out I'm rendering things slightly outside my Frustum.  I'm using some code I found from the FlipCode website which checks each AABB corner against the frustum planes and I think there are some major flaws with it.

It returns -1if all of the AABB corners are outside a plane - this is fine.

It returns 1 if all of the AABB corners are inside all planes - this is also fine.

It returns 0 if the AABB is 'partly inside', i.e. if at least one point is inside the frustum.  This, I found doesn't work with situations like the one I've attached in the image.  In the image, the bounding box is not in the frustum, but using this method, it will return that it's intersecting.  Corner B1 is inside the frustum plane P2 and Corner B2 is inside the frustum plane P1, but it should be outside.

Is there a better way of handling intersecting boxes?  Can't quite get my head around what checks I need to do

	// if all points are behind 1 specific plane, we are out
// if we are in with all points, then we are fully in
for(int p = 0; p < 6; ++p)
{
int iInCount = 8;
int iPtIn = 1;

for(int i = 0; i < 8; ++i)
{
// test this point against the planes
if(m_frustumPlanes[p].DistanceToPoint(corner[i]) < 0)
{
iPtIn = 0;
--iInCount;
}
}

// were all the points outside of plane p?
if(iInCount == 0)
return(-1);

// check if they were all on the right side of the plane
iTotalIn += iPtIn;
}

// so if iTotalIn is 6, then all are inside the view
if(iTotalIn == 6)
return(1);

// we must be partly in then otherwise
return(0);


### #2/ slalrbalr   Banned

Posted 11 October 2013 - 07:08 AM

You have to add an extra check for whether ALL points are outside. In fact, this is the only thing you have to check.

Your example doesn't make much sense either. Do you mean that the AABB is larger than the frustum, and the frustum is inside the AABB? You could handle this by checking the frustum corners against the AABB planes - if all frustum points are inside the AABB, render the object.

Nope... that's not it either. Why don't you use bounding spheres instead? For AABB, it's not enough to check the corners - you'd have to treat the sides of the AABB and frustum as polygons, and check for polygon intersections to be able to tell if the AABB is "partly in".

Edited by tonemgub, 11 October 2013 - 07:47 AM.

### #3kalle_h  Members

Posted 11 October 2013 - 07:45 AM

bool static extentSignedTest(const Vector4f& p, const Vector3f& center, const Vector3f& extent)
{
return (dot(Vector3(p), center) + dot(abs(Vector3(p)), extent) < -p.w);
}

bool static isAABBInFrustum(const AABB& box, const Matrix44& frustumMatrix)
{
const Vector4f  rowX                    = frustumMatrix.getRow(0);
const Vector4f  rowY                    = frustumMatrix.getRow(1);
const Vector4f  rowZ                    = frustumMatrix.getRow(2);
const Vector4f  rowW                    = frustumMatrix.getRow(3);

const Vector3f& center =  box.getCenter();
const Vector3f& extent =  box.getExtents();

// Left and right planes
if (extentSignedTest(rowW + rowX, center, extent))
return false;

if (extentSignedTest(rowW - rowX, center, extent))
return false;

// Bottom and top planes
if (extentSignedTest(rowW + rowY, center, extent))
return false;

if (extentSignedTest(rowW - rowY, center, extent))
return false;

// Near and far planes
if (extentSignedTest(rowW + rowZ, center, extent))
return false;

if (extentSignedTest(rowW - rowZ, center, extent))
return false;

return true;
}


Fast and simple but really tight object/world/view space bounding box frustum test. Simply calculate modelViewProjection matrix and send that and boundinBox(center, halfExtent).

For static objects you can calculate world space AABB and just send viewProj matrix.

There is also extension for even better accuracy which test if frustum corner points are inside of AABB. That should be quite easy to extend for my algorithm

http://www.iquilezles.org/www/articles/frustumcorrect/frustumcorrect.htm

### #4L. Spiro  Members

Posted 11 October 2013 - 07:53 AM

POPULAR

Your check is painfully slow and should be heavily refactored. It’s not the correct logic for frustum culling—you don’t ever check on a point-by-point basis.

Assuming your AABB is in the following format:

	/**
* Class CAabb
* \brief A min-max axis-aligned bounding box.
*
* Description: A min-max axis-aligned bounding box.
*/
class CAabb {
// All is public.  This class has no secrets.
public :
// == Members.
/**
* The minimum X-, Y-, and Z- axis values.
*/
CVector3								m_vMin;

/**
* The maximum X-, Y-, and Z- axis values.
*/
CVector3								m_vMax;
};
And your frustum is an array of 6 planes, the code to check for being outside of the frustum (the only thing you need to cull) is as follows:

First you need to classify the AABB with respect to a plane. And you should return enumerations, not integers. Enumerations are numbers with easily understood meanings. So starting with a classify method:
	/**
* 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;
}
And then you can easily just check the 6 planes on the frustum as a “test” method (a method that early-outs when a fail condition is met, but in exchange for this early-out it returns only true/false and no other information such as intersecting the frustum or being fully inside, etc.):

	/**
* 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;
}
In other words, instead of rendering anything that either intersects the frustum or is inside it, your logic should be flipped so that you don’t render what is outside the frustum.

L. Spiro

Edited by L. Spiro, 11 October 2013 - 07:54 AM.

Posted 11 October 2013 - 08:03 AM

Guys, just as I was typing my reply to tonemgub when I saw the other replies and the sphere check idea sounds like a great alternative.  I can fit that in without too many changes.

This frustum code was something from my testbed engine from years ago, I'm glad I revisited it and not so glad I just pulled it from the web without checking it too much!

Thanks a lot for all the replies

### #6Juliean  Members

Posted 11 October 2013 - 08:07 AM

Nope... that's not it either. Why don't you use bounding spheres instead? For AABB, it's not enough to check the corners - you'd have to treat the sides of the AABB and frustum as polygons, and check for polygon intersections to be able to tell if the AABB is "partly in".

I didn't want to downvote you, but just to have it on paper for someone who stumbles over this thread: This is plain and simple wrong. You can eigther do it like L.Spiro did, or alternatively you can use the normal of the plane to determine the one corner point of the AABB that needs to be checked. All other points are definately on the same side of the plane (* if you treat the intersection case the same as being inside, which is OK if you just want to do frustum culling). Like this:

bool AABB::InsidePlane(const Plane& plane) const
{
Vector3 vCenter = m_vCenter;
const Vector3& vNormal = plane.GetNormal();

if(vNormal.x >= 0.0f)
vCenter.x += m_vSize.x;
else
vCenter.x -= m_vSize.x;

if(vNormal.y >= 0.0f)
vCenter.y += m_vSize.y;
else
vCenter.y -= m_vSize.y;

if(vNormal.z >= 0.0f)
vCenter.z += m_vSize.z;
else
vCenter.z -= m_vSize.z;

float posDot = plane.Dot(vCenter);

return posDot >= 0.0f;
}


Checking against all 6 box points is extremely slow in comparison, but converting the AABB and frustum planes to polygons is outright insane.

Edited by Juliean, 11 October 2013 - 08:08 AM.

Posted 11 October 2013 - 10:44 AM

L. Spiro, how do you deal with situations where the AABB is not square?

### #8cdoubleplusgood  Members

Posted 11 October 2013 - 10:48 AM

I implemented frustum culling for my game following this instruction:

http://www.lighthouse3d.com/tutorials/view-frustum-culling/

Seems to work quite well. I also have non-cubic AABBs.

### #9L. Spiro  Members

Posted 11 October 2013 - 11:24 AM

L. Spiro, how do you deal with situations where the AABB is not square?

The above code handles all cases of 3D AABB’s stored as I showed (mins and maxes for each axis provided). There is no restriction on the dimensions of the AABB.
I assume you got confused by the fact that there is only 1 member for the mins and 1 for the maxes. These are each 3D vectors, each holding an x, y, and z value.

L. Spiro

Edited by L. Spiro, 11 October 2013 - 11:28 AM.

Posted 11 October 2013 - 04:07 PM

L. Spiro, how do you deal with situations where the AABB is not square?

The above code handles all cases of 3D AABB’s stored as I showed (mins and maxes for each axis provided). There is no restriction on the dimensions of the AABB.I assume you got confused by the fact that there is only 1 member for the mins and 1 for the maxes. These are each 3D vectors, each holding an x, y, and z value.L. Spiro

No, my bounding boxes are stored in the exact same way. What I meant was, if you've got an AABB which is the shape of, say a deep pizza box (perhaps it's a terrain patch with relatively small height changes), the sphere would cover the extents of the box in the x and z directions, but in the y direction the sphere would extend downward far beyond the extents of the polygons - that said, it's possible that if the camera frustum is pointing downwards toward the terrain, parts of the terrain could be drawn that are nowhere near in the frustum.

### #11/ slalrbalr   Banned

Posted 11 October 2013 - 04:25 PM

I didn't know about this little trick, so everyone please excuse me for mentioning polygons - that really was a bad idea, but IMO it was still a better idea than checking only the AABB corners -  I knew that wouldn't cut it (or I eventually reached that conclusion:) ), because all of the relations between the corners were being ignored.

So, just to put it all into words (and to make sure I embed it in my mind):

If the dot product of the AABB's "positive extent" vector ( extent = abs(anycorner - center) ) and the plane's normal ( dot(extent, normal) = the length of the projection of the AABB's extent onto the plane's normal) is greater or equal than the distance from the center of the AABB to the plane, then the AABB intersects with the plane.

If that's not the case, then if the sign of the dot product is the same as the sign of the distance, then the AABB is in front of the plane; if the signs are different, the AABB is behind the plane.

Neat... wish I'd thought of that.

non-cubic AABBs

L. Spiro, how do you deal with situations where the AABB is not square?

I don't think that makes sense... all AABBs are cubic parallelograms.

RobMaddison, you don't have to use bounding speheres anymore. The method described by L. Spiro and the others is for AABBs, so if you already have the min and max values for your objects' AABBs, you can use those directly, with this method - you don't have to convert the AABB into a sphere anymore (if that's what you were doing). Sorry if I set you on the wrong path...

Edited by tonemgub, 11 October 2013 - 04:30 PM.

### #12L. Spiro  Members

Posted 11 October 2013 - 11:27 PM

No, my bounding boxes are stored in the exact same way. What I meant was, if you've got an AABB which is the shape of, say a deep pizza box (perhaps it's a terrain patch with relatively small height changes), the sphere would cover the extents of the box in the x and z directions, but in the y direction the sphere would extend downward far beyond the extents of the polygons - that said, it's possible that if the camera frustum is pointing downwards toward the terrain, parts of the terrain could be drawn that are nowhere near in the frustum.

As mentioned by tonemgub, these are AABB’s, not spheres. For a pizza box centered around the origin, m_vMin could be CVector3( -10.0f, -2.0f, -10.0f ), and m_vMax could be CVector3( 10.0f, 2.0f, 10.0f ). There is no restriction on the dimensions along any axis.

L. Spiro

Posted 12 October 2013 - 01:33 AM

No, my bounding boxes are stored in the exact same way. What I meant was, if you've got an AABB which is the shape of, say a deep pizza box (perhaps it's a terrain patch with relatively small height changes), the sphere would cover the extents of the box in the x and z directions, but in the y direction the sphere would extend downward far beyond the extents of the polygons - that said, it's possible that if the camera frustum is pointing downwards toward the terrain, parts of the terrain could be drawn that are nowhere near in the frustum.Unless I've read it wrong?

As mentioned by tonemgub, these are AABB’s, not spheres. For a pizza box centered around the origin, m_vMin could be CVector3( -10.0f, -2.0f, -10.0f ), and m_vMax could be CVector3( 10.0f, 2.0f, 10.0f ). There is no restriction on the dimensions along any axis.L. Spiro

My apologies, I might not have described myself too well. I understand that these are boxes and not spheres, but you are taking a vector from the centre of the box to the maximum extent, which, for all intents and purposes, is effectively a radius and gives a sphere into which the square/rectangular box will fit.

It then looks like you multiply this radius vector by the normal of the plane. That is then used in the distance to plane check. I can't understand how this would work with an irregularly-shaped AABB, depending on which angle your frustum is at, you could be including something based on the 'radius' being used on the lowest extent.

Consider thus use case, the pizza box is standing up on its edge in line with your view vector, so basically you can just see the thin edge. Now if that pizza box goes just out of your frustum's right-hand-side plane, using this method I think you'd still be including it. If you imagine the [imaginary] sphere that results from the radius I spoke about in the previous paragraph, the radius value to check against the planes in this particular scenario is the still the centre of the box to the maximum extent, meaning part of it will be inside the frustum but none of the actual AABB will be.

Apologies if I haven't read the code properly but I've also tried it out and the results show a sizeable overdraw (or rather, draw inclusion), for irregular AABB extents.

### #14/ slalrbalr   Banned

Posted 12 October 2013 - 05:33 AM

for all intents and purposes, is effectively a radius and gives a sphere into which the square/rectangular box will fit.

The center and extent vectors do not describe a sphere, exactly. A sphere is described only by a vector center and a scalar radius, but in this case, the extent is a vector, not a scalar, so it is not a radius. You're probably just thinking of the length of the extent vector as a radius of a sphere, but when you think of it as only a sphere, you ignore the direction of the extent vector, which is also very important in this case.

It's complicated to explain how the whole method works - I'm not sure I understand it completely myself, but I assure you it does work correctly, no matter how the frustum is oriented.

for irregular AABB extents

What exactly are you reffering to as "irregular AABB extents"? You mean non-cubic extents? Those are handled correctly by the AABB-method - you just have to stop thinking about it as a sphere/plane check, and start using it. If you're getting bad results, maybe you have an error somewhere in your implementation.

Edited by tonemgub, 12 October 2013 - 05:41 AM.

Posted 12 October 2013 - 06:38 AM

Irregular

for all intents and purposes, is effectively a radius and gives a sphere into which the square/rectangular box will fit.

The center and extent vectors do not describe a sphere, exactly. A sphere is described only by a vector center and a scalar radius, but in this case, the extent is a vector, not a scalar, so it is not a radius. You're probably just thinking of the length of the extent vector as a radius of a sphere, but when you think of it as only a sphere, you ignore the direction of the extent vector, which is also very important in this case.

It's complicated to explain how the whole method works - I'm not sure I understand it completely myself, but I assure you it does work correctly, no matter how the frustum is oriented.

for irregular AABB extents

What exactly are you reffering to as "irregular AABB extents"? You mean non-cubic extents? Those are handled correctly by the AABB-method - you just have to stop thinking about it as a sphere/plane check, and start using it. If you're getting bad results, maybe you have an error somewhere in your implementation.

Yes, non-cubic extents, as L.Spiro explained.  I've drawn and attached a diagram of my thoughts.  Perhaps I'm missing something but if L.Spiro's fR and fS variables are calculated as per the diagram, you should be able to see where it might not work correctly.

### #16/ slalrbalr   Banned

Posted 12 October 2013 - 11:06 AM

Your fR vector is not drawn correctly. It should start at the center of the AABB and end at the left, on an imaginary plane that is parallel to the frustum plane and passes through the top left corner of the AABB (or whatever corner of the AABB is closest to the plane). I think this ensured by taking the absolute (or only positive) values of the extent vector's components - this is the part I'm not too clear on either. If this is not what you're getting from the algorithm, maybe your plane normals are not unit-length vectors, which they probably need to be in order for the dot product with them to return the length of the projection unaffected by the length of the normal. Your normals should also be pointing outwards, maybe. Also, in your drawing, the fR vector IS NOT the projection of the "max extent" vector onto the normal. The multiplication L. Spiro does there is the dot product vector-multiplication. You should really read the first paragraph from this wikipedia article: http://en.wikipedia.org/wiki/Dot_product And here's what the projection of a vector onto another vector looks like (the picture to the right): http://en.wikipedia.org/wiki/Dot_product#Scalar_projection_and_the_equivalence_of_the_definitions .

### #17kalle_h  Members

Posted 12 October 2013 - 11:34 AM

http://fgiesen.wordpress.com/2012/08/31/frustum-planes-from-the-projection-matrix/

There is simplest explanation how to create frustum from just simple matrix.

There is good read how to optimize the algorithm and why these tricks work.

http://fgiesen.wordpress.com/2010/10/17/view-frustum-culling/

AABB vs plane should be just two dots, one abs and comparision. Anything more complex is just wasterfull.

Tightest culling with AABB against frustum is achieved at object space. Creating frustum at object space is really simple and fast. And if you are only testing which side point is compared to plane you don't even need to normalize plane normals. Code at here: http://www.gamedev.net/topic/648803-frustum-culling-discrepancy/#entry5100532

Good thing with object space frustum culling is that you don't need to transform your AABB at all.  Also single matrix is more compact way to store frustum than using six planes. So less data is needed.

Posted 13 October 2013 - 01:14 AM

Apologies L.Spiro, I read the fR calculation completely wrong, I can see how it works now.

Kalle_h, that's some interesting reading. Thanks for adding a different flavour to it - for experience, I'll try both ways.

Thanks again for your time guys, much appreciated

Posted 13 October 2013 - 04:00 AM

Got this working now, thanks all.

Strangely though, my algorithm only works if I add the plane distance, perhaps my frustum planes normals point inwards and yours point outwards?

### #20L. Spiro  Members

Posted 13 October 2013 - 04:08 AM

Although you have said you understand, just to be very clear, I have used my equally impressive MS Paint skills to clarify the format of my CAabb class.

The purple dots are the mins and maxes.  There is no center value.

perhaps my frustum planes normals point inwards and yours point outwards?
I store plane distances as a negative because for most plane equations you have to invert the distance anyway, adding an instruction to the math.