Jump to content
  • Advertisement
Sign in to follow this  
frankypoo

frustum algo in octree

This topic is 4731 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

So I made an octree to partition off groups of polygons; however, I'm having trouble throwing the viewing frustum in there. The problem is this. My virtual viewing frustum is a collection of points based on constants used when setting the projection matrix of the d3ddevice9. Yada yada... anyway, so I have 8 points that compose the viewing frustum. Now when I render my scene, I first check if all of those points are greater than the minimum vertex of the node's box and less than the maximum vertex (which means that the point under consideration is within the node.) If all 8 points of the viewing frustum are contained within the node box, then that node is too big and its children node need to perform the same test. If only some of the points are contained, then the node and the viewing frustum overlap, and I need to similarly break the node down into its children. Here's the problem... if none of the points are contained, that could either mean that the node is far away from the viewing frustum (which is the time-saving point of an octree), and therefore we only need ignore this node of the tree, OR that the node is contained within the viewing frustum, and not the other way around. I do not know how to test for this without constructing planes from the viewing frustum's points and doing a dotproduct test on every vertex of the node, which happens to be the common way octrees are implemented for some reason. Most octrees I've seen do this first, to test if the node is fully contained within the frustum, but never get around to testing if the frustum is fully contained within the node. Therefore (and I've tried them), the scene isn't rendered, since the root node (as the 1st node) checks if any of its points are within the frustum, which shows up false (since the FRUSTUM is bounded by the NODE) and the node is thereby considered occluded, and not broken down for further tests. Ok, tangent aside... so the plane dot-product test is great, but only tells you if the node is bounded by the frustum. If you want to know the converse (which you do, right?... maybe not, i'm new to this) then you'll have to see if the frustum is bounded by the node as well.... which entails 2 for loops, creating overhead. the frustum-in-node test is easy, because you just compare each point against two points (node min and max). So I do that one first to rule out the second test if it returns true. The second test takes more time, since there is no min/max of a dynamic trapazoidish pyramid, and since you need to dotproduct test each point against each plane ( O(N^2)). I'm wondering, is there a more efficient way to test whether the node is completely contained by the frustum? The best would be if I could somehow store information gathered from one loop that would tell me, when it's done, whether the node contains the frustum, the frustum contains the node, they overlap, or they don't touch. Any ideas?

Share this post


Link to post
Share on other sites
Advertisement
For the reasons you described, frustum culling is usually not expressed in terms of point-containment tests. Here's a brief description of a fairly standard method which avoids these problems.

As you suggested, the frustum is represented with 6 planes. The octree nodes are considered as axis-aligned bounding boxes.

A single AABB can easily be tested against a plane using two dot products. The result tells you whether the box is in front of, behind, or stradling the plane. If the box is found to be behind any one frustum plane, it is culled. This method can introduce the occasional false positive, but that is generally acceptable.

A hierarchical culling algorithm can be based on the above test alone. However, further optimizations can be made. For example, if a parent node is fully inside a frustum plane, none of its children need be tested against that plane. In this way, the results of previous tests can be propagated down the tree to avoid unnecessary work.

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!