Sign in to follow this  
51mon

How to determine which cells that's inside the frustum?

Recommended Posts

Hi I got the scene divided into a axis aligned grid. Each cell(cubic) is filled with particles and I only want to make render calls to cells inside the frustum. The camera can have any yaw/pitch/roll. I have tried to find a efficient method to find the right cells, but not really succeeded. Does anybody know of a good way? Thanks

Share this post


Link to post
Share on other sites
just classify each cell against each side of the frustum, usually you have 5-6 planes defining the frustum, so you can just check the cell against each of them, there is a smart way to classify an axis aligned bounding box against a plane to see which side it is on but I can't remember. you could however just construct the 8 points of the cell and check each in turn against the plane, as for checking whether a point is in-front, in-back or coinciding with a plane you have to get the dot product of the point with the plane normal - the distance, if this value is < 0 it is to the back, if it is > 0 it is in-front, if it is 0 it is coinciding.

Share this post


Link to post
Share on other sites
The first way of looking at this problem, which is how game developers often treat the problem, is as follows:

From this point of view, the first piece to this puzzle is in the individual AABB-frustum tests. Fast versions of these tests do exist, so you can google a bit to find a book that has this. Alternately, you can approximate an AABB conservatively by a sphere; this is easy to test against a plane (just plug into plane equation; equivalently, this is a dot product in homogeneous coordinates) Likewise, you can approximate a frustum by a cone; point-cone (and sphere-cone) intersection tests are easy; they're just dot products themselves. The question becomes, how do you trade off accuracy of clipping (which is good, since it eliminates geometry) against speed of the clipping operations themselves?

The other part of the puzzle, from this point of view, has to do with organizing these tests in an efficient way. What people often do is represent the world by an octree of AABBs. You test each of the 8 blocks of your top level against the frustum. Any block entirely inside, you treat as inside; any block entirely outside, you treat as outside; and for any block partially inside and partially outside, you recur on its children. Other hierarchies exist as well of course. K-D trees, general BSP trees, etc. But octrees are the most commonly discussed.

So here's one example of an algorithm based on this general approach: I'd use an octtree hierarchy of cells, and, since I know that I'll just recur if my test isn't accurate (and I'll get my accuracy that way), just use a bounding sphere test, since it's cheap.

A second way of looking at this problem, which I see less often but which makes some sense to me, is to look at this as the problem of rasterizing your frustum to the voxel grid, in the same way that you rasterize triangles to the screen. I haven't thought a ton about this, but it seems like an interesting problem that you might be able to work out.

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