Sign in to follow this  
Blazart

Perfect aabb frustum intersection test

Recommended Posts

Blazart    107

The only way I know how to do perfect aabb frustum intersection tests is using separating axis theorem. Where you project the vertices of the frustum and aabb onto some axii test for disjointness.

 

And this works fine but now I'm trying to get a frustum that extends forever and has no far plane. Can I extend SAT to  work with this type of frustum or is there another algorithm I can use?

Edited by ?W ?I ?R ?E ?D ?C ?A ?T

Share this post


Link to post
Share on other sites
GuyWithBeard    1892
You can do plane-AABB tests against all six planes of the frustum to do "normal" frustum-AABB testing, and if you want an infinitely far away back plane you simply leave out the test against the far plane. To construct the six planes you need the world corner points of the frustum, but shat should be easy.

Share this post


Link to post
Share on other sites
Blazart    107

You can do plane-AABB tests against all six planes of the frustum to do "normal" frustum-AABB testing, and if you want an infinitely far away back plane you simply leave out the test against the far plane. To construct the six planes you need the world corner points of the frustum, but shat should be easy.

 

VvxPxVh.png

Your algorithm fails for this case.

Share this post


Link to post
Share on other sites
JTippetts    12970
Does it need to be truly infinite, or can you get by with sufficiently large? That is, since none of the native floating point types has infinite range, can you just get away with locating your far plane near the upper limit of precision?

Share this post


Link to post
Share on other sites
Aressera    2919

This is the code that I use. It works, is fast, and you should be able to use it to ignore certain clipping planes (e.g. in directional light shadow mapping). Plus it will tell you if your AABB is inside, outside, or intersecting your frustum.

UInt ViewVolume:: intersects( const AABB3& box ) const
{
	const Plane3* planes = &near;
	UInt result = INSIDE;
	
	for ( Index i = 0; i < 6; i++ )
	{
                // planes have unit-length normal, offset = -dot(normal, point on plane)
		const Plane3& plane = planes[i];
		Index nx = plane.normal.x > Real(0);
		Index ny = plane.normal.y > Real(0);
		Index nz = plane.normal.z > Real(0);
		
		// getMinMax(): 0 = return min coordinate. 1 = return max.
		Real dot = (plane.normal.x*box.getMinMax(nx).x) + (plane.normal.y*box.getMinMax(ny).y) + (plane.normal.z*box.getMinMax(nz).z);
		
		if ( dot < -plane.offset )
			return OUTSIDE;
		
		Real dot2 = (plane.normal.x*box.getMinMax(1-nx).x) + (plane.normal.y*box.getMinMax(1-ny).y) + (plane.normal.z*box.getMinMax(1-nz).z);
		
		if ( dot2 <= -plane.offset )
			result = INTERSECTS;
	}
	
	return result;
}

Share this post


Link to post
Share on other sites
GuyWithBeard    1892

 

You can do plane-AABB tests against all six planes of the frustum to do "normal" frustum-AABB testing, and if you want an infinitely far away back plane you simply leave out the test against the far plane. To construct the six planes you need the world corner points of the frustum, but shat should be easy.

 

VvxPxVh.png

Your algorithm fails for this case.

 

That's true, you can get false positives for cases like this. In my experience that usually has not been a problem, but I'll leave that for you to decide. The good thing about using individual planes is that you can easily exclude any side of the frustum from the test, making it very flexible. Eg. I am excluding the near plane when doing shadow map rendering to allow objects that would normally be culled from the view to cast shadows onto the visible geometry.

 

Aressera's code is more or less what I suggested.

Share this post


Link to post
Share on other sites
clb    2147

Like discussed already, there is an important distinction to be made between Frustum-AABB intersection test versus a Frustum-AABB culling test. In the first problem, we want to accurately determine whether the two objects intersect. In the second, we want to quickly find (and reject) AABBs that are certainly outside the Frustum, but don't necessarily care if there are some false positives that pass the sieve (since whatever purpose the culling is for, later stages of the pipeline will handle the few undetected cases).

 

The code presented by Aressera in comment 5 is the commonly presented fast culling test. If you need a precise Frustum-AABB intersection test instead of a culling test, see a precise SAT test, for example in MathGeoLib here: https://github.com/juj/MathGeoLib/blob/master/src/Algorithm/SAT.h#L26 . The difference between the full SAT and the culling test is that the full SAT test tests the cross products of each pair of face normals of the two objects in question, which is enough to quarantee no false positives from occurring.

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