• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
RobMaddison

Frustum culling discrepancy

19 posts in this topic

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

Share this post


Link to post
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
0

Share this post


Link to post
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

 

 

1

Share this post


Link to post
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

0

Share this post


Link to post
Share on other sites

Nope... that's not it either. Why don't you use bounding spheres instead? biggrin.png 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
0

Share this post


Link to post
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
0

Share this post


Link to post
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.

Unless I've read it wrong?
0

Share this post


Link to post
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. smile.png

 

 

 


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
0

Share this post


Link to post
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
0

Share this post


Link to post
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.
0

Share this post


Link to post
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
0

Share this post


Link to post
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.

0

Share this post


Link to post
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 .
0

Share this post


Link to post
Share on other sites

Some reading about frustum culling.

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.

2

Share this post


Link to post
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
0

Share this post


Link to post
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?

0

Share this post


Link to post
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.
 
You can read more about this here:
 
 
L. Spiro
1

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  
Followers 0