Sign in to follow this  

Frustum culling without plane-AABB checks?

This topic is 4822 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
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
Quote:
Original post by technobot
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.



You're forgetting that for any reasonable FarPlane distance (i.e. Far Plane is not right there within 50 meteres). Your outer and plane bounding AABB-s will be gigantic (esspecially with 45 degree camera angles) causing a lot of objects to pass those tests. I'm preety sure your method will be a lot slower than plain AABB-Frustum testing. AABB-Frustum testing is actually preety fast if its done properly (esspecially if you use FrameCoherency and Masking).

Share this post


Link to post
Share on other sites
Quote:
Original post by A Guy from CRO
You're forgetting that for any reasonable FarPlane distance (i.e. Far Plane is not right there within 50 meteres). Your outer and plane bounding AABB-s will be gigantic (esspecially with 45 degree camera angles) causing a lot of objects to pass those tests. I'm preety sure your method will be a lot slower than plain AABB-Frustum testing. AABB-Frustum testing is actually preety fast if its done properly (esspecially if you use FrameCoherency and Masking).

The objects may pass the outer AABB test, but they will still be rejected by the final point-plane test, so that's ok. As for speed, an optimised AABB-frustum test would still require more calculations without frame coherency and masking, and while I'm not sure about it, it may be possible to utilize frame coherency for this test as well. Anyway, testing is the only way to know for sure.

Share this post


Link to post
Share on other sites
Of course they'll pass the final point'plane test but I'm saying your outer AABB and plane AABB's are encompassing a large chunck of the scene causing it to be very very unoptimal as they'll reject very few objects and the whole point of pretest's is fast early rejection. It all has to come down to point-plane test anyway, but I think your method will be slover.

Anyway, if you test, please post the results, I'd be interested in a comparison.

Share this post


Link to post
Share on other sites
Frustum vs AABB is very cheap if you do it correctly, there's definitely no need to test all corners against all planes. Taking the sign of the components of the planes normal vector can give you a bitmask that can be used to look up the only two vertices of the AAB you need to test. This can be done once per plane per frame, and then all you need to reject a AABB is two dot products.

Anyway, using sphere-sphere or sphere-frustum tests for early out is fine, but your frustum-AABB test should really be fast. If it isn't, something is wrong.

Share this post


Link to post
Share on other sites
I haven't got to the testing part yet, but I've realized that although my idea may test faster than the conventional approach against each individual quadtree node, it will probably turn out to be slower for an entire quadtree, since it does not descriminate between the "completely-inside" and "intersecting" cases. So unless I'll find a way around this shortcomming, I'm going to ditch this idea.

Share this post


Link to post
Share on other sites
Quote:
Original post by technobot
it will probably turn out to be slower for an entire quadtree, since it does not descriminate between the "completely-inside" and "intersecting" cases.


,-) see, exactly thats the reason why i usually would even advice to NOT use a tree for culling in some cases like smallish terrains with just a few hundred or thousand patches/leaves/whatever. the overhead of traversing the tree and doing extra work to detect complete and partial intersections often takes longer than just brute force testing all of them quick and dirty. though i guess with the right method you can minimize the extra work quite well.

Share this post


Link to post
Share on other sites

This topic is 4822 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.

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