# Frustum culling discrepancy

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

## Recommended Posts

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);

##### Share on other sites

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? :D 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

##### Share on other sites
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

##### Share on other sites

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

##### Share on other sites

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

##### Share on other sites

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

##### Share on other sites

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.

##### Share on other sites

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

##### Share on other sites

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.

##### Share on other sites

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

##### Share on other sites

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

##### Share on other sites

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.

##### Share on other sites

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

##### Share on other sites

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.

##### Share on other sites
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 .

##### Share on other sites

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.

##### Share on other sites
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

##### Share on other sites

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?

##### Share on other sites
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.

[attachment=18370:post-130777-0-65583200-1381581484.jpg]

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.