Jump to content
  • Advertisement
Sign in to follow this  
technobot

Frustum culling without plane-AABB checks?

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

I was just wandering, out of pure curiosity, is there some way to frustum-cull a quadtree without doing plane-AABB tests? I know one can approximate the frustum with a cone or sphere, even an AABB, but I was thinking maybe there is something more accurate?

Share this post


Link to post
Share on other sites
Advertisement
Just thought of something. Instead of checking if the AABB intersectes the frustum, check if the frustum intersects the AABB. In other words, rather than testing the AABB corners against the frustum planes, test the frustum corners against the AABB planes. Ok, technically you'd still be testing against planes, but since the planes are axis aligned, each test boils down to a single if statement. Any other ideas?

EDIT: On second thought, that might behave like an AABB-AABB test... I'll think about it some more and post back later.

Share this post


Link to post
Share on other sites
get the center of your AABB and test it against the frustrum plane

now compare it to the radius = distance (center->corner)

if the center is outside the frustrum and the distance to the plane is >=radius you can clip it away otherwise add it a list of nodes visible

Share this post


Link to post
Share on other sites
Basically what basiror is saying is treat the bounding box like a sphere. Find the center (C) and define a radius (R)for it, obviusly the box should include the sphere in this case.

Then you just do C*N - d <= R. Mind you that this function depends on how you define your plane. That is <N, -d> or <N, d> but i'm sure you can figure it out from there. The problem is that this is a quick check and does not guarentee and accurate cull based on the bounding box.

Most designs i have seen use both. You do the quick cull with a sphere that INCLUDES the bounding box. This requires 6 dot products, 6 subractions(or additions), and 6 comparisions. Then bases on the results of the sphere/plane collision, you compare the box to the planes (a slower test). So technically you do more work with the hope that the quick test will save you from doing the slow test.

--Ninj4D4n

Share this post


Link to post
Share on other sites
Ok, I thought about my earlier suggestion, and it indeed behaves like an AABB-AABB test, so not very accurate.

Quote:
Original post by Ninj4D4n
The problem is that this is a quick check and does not guarentee and accurate cull based on the bounding box.

The point is that an accurate cull is not necessary with modern hardware, so the question is: what is the best compromise between speed and accuracy? Keep the suggestions coming, I'll be thinking about this as well, and will post again later.

Share this post


Link to post
Share on other sites
Ok, I think I've got it. Represent the frustum by a set of 8 AABBs, plus the 6 planes. The AABBs are: an outer AABB that bounds the frustum, 6 AABBs that bound the individual frustum faces (one for each face), and an inner AABB, which is the volume left between the 6 faces' AABBs.

Then the test goes like this:
1. If the tree cell does not intersect the outer AABB, there's definitely no intersection. Else:
2. If the cell intersects the inner AABB, there definitely is an intersection. Else:
3. Using the direction from the center of the inner AABB to the cell center, select three of the faces' AABBs that may be between the two centers. Also select the closest cell corner.
4. The selected corner is most likely within one of the selected AABBs. If so, find that AABB and continue. Otherwise, then there is no intersection.
5. Test the corner against the plane of the corresponding frustum face. If the point is on the correct side of the plane, there is an intersection, otherwise there isn't one.

For most cases it will be one or two AABB-ABBB tests per tree cell, for the remaining minority it will be up to five AABB-AABB checks and one point-plane check. It's fast, and it's accurate.

Share this post


Link to post
Share on other sites
I don't think that's going to work well.

Imagine in 2D, your frustum represented as a simple triangle. Rotate it to 45° - that's going to be your worst case for AABBs. Draw that on a piece of paper.

You'll end up with an iner AABB empty; and the set of faces AABB that equal perfectly the outer AABB. What happens for your step 3. in that case ?

Any object fully in the frustum, will be hit by one or more of the faces AABBs - the result will not be very helpful. Actually, it will not be more helpful than the outer AABB result, if you see what i mean..

I'd go with the sphere test - it is much faster than the plane/AABB one, and is also much more accurate than your AABB-ed frustum idea.

Y.

Share this post


Link to post
Share on other sites
so many ways.. for boxes i just get the camera coords of a point, compare its x,y with the frustum width/height at the given position and be done with it. best case is half as many dot products, worst case is aborting later.

ie.
point - cam.pos
dotproduct with cam.forward
test near/far
dotproduct with cam.right
test +-width
dotproduct with cam.up
test +-height

and yes, height/width are easily calculated with tan(fov/2) and height*aspect.

of course a simple sphere-plane check is still faster than testing a box, so only use it for decidedly non-sphere-ish objects.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
First, a small note. In order for the algorithm I posted yesterday to work correctly, the faces' AABBs must not intersect each other. While this is automatically the case in 2D, in 3D this requires a bit of extra attention when constructing the AABBs. Note that to acheive this, each individual AABB does not need to cover the entire face to which it belongs, but together they should cover all the faces entirely. This is ok because steps 3-4 only select which point-plane test to perform in step 5, and because total accuracy is not required.

Quote:
Original post by Ysaneya
Imagine in 2D, your frustum represented as a simple triangle. Rotate it to 45° - that's going to be your worst case for AABBs. Draw that on a piece of paper.

You'll end up with an iner AABB empty; and the set of faces AABB that equal perfectly the outer AABB. What happens for your step 3. in that case ?

Any object fully in the frustum, will be hit by one or more of the faces AABBs - the result will not be very helpful. Actually, it will not be more helpful than the outer AABB result, if you see what i mean..

Yes, 45 degrees is indeed a problematic case, but all it does is waste step 2. As I wrote above, the purpose of steps 3 and 4 is merely to select which point-plane tests to perform in step 5. Since the final word depends on the point-plane tests (if steps 1 and 2 don't give a conclusive answer), it's still going to work, and it will be almost completely accurate. It's possible to make it completely accurate, but that would require up to three point-plane tests, not up to one. But I tend to doubt that it will be worth it (especially for terrain, which tends to be loosely populated).

Quote:
I'd go with the sphere test - it is much faster than the plane/AABB one, and is also much more accurate than your AABB-ed frustum idea.

Again, since the final word depends on a point-plane test, it is almost as accurate as a fully-fledged plane-AABB frustum check, which also makes it at least as accurate as the shpere test, probably more accurate. Since the AABB-AABB checks signifcantly reduce the number of required calculations, I think it is also faster: the sphere test requires up to five plane-sphere checks, each being a dot product and a couple additions/subtractions (I count a comparison as a subtraction, since that's more or less what the cpu does to compare two values). On the other hand my test requires (at most):
- steps 1-2: two AABB-AABB tests (12 subtructions);
- step 3: 3 subtractions and 3 look-ups to select the faces' AABBs and the cell corner;
- step 4: 3 point-AABB tests (18 subtructions);
- step 5: one point-plane test (a dot product and a substruction).
That's a total of one dot-product, 34 subtractions, and 3 look-ups.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!