Sign in to follow this  
yilatil

Frustum Culling

Recommended Posts

I have a question about space partitioning related culling/collision det. systems;

As you know a camera transformation, therefore the frustum, can change nearly every frame. so, should I rebuild my for example octree in every frame? isn't this a bit expensive?

Share this post


Link to post
Share on other sites
Nope. I assume here you have a static scene like a terrain that you want to render using octrees. In this scenario, you build your octree once, and then each frame you parse it from root to leafs and check against the new frustum, which is indeed changing.

If a certain node from the tree is outside the frustum, you stop checking that branch and you don't send anything to the renderer from it. If it is completely inside the frustum, you stop checking that branch and send to the renderer all its children that can be rendered. If a node intersects one ore more planes of the frustum, you can further check that branches' children until you get to the nodes that are either completely outside or inside the frustum.

However, if the geometry is changing, you have to rebuild that area of your octree.

Hope this helps.

Share this post


Link to post
Share on other sites
Thanks for the reply. Here is a quick second question:

What is the best definition for the objects in nodes? for example should I form the tree as a tree of meshes or tree of triangles or simply in vertex level? and how far should I go with the nodes? I believe detailing the tree as 1 vertex per node could lead a huge tree with huge iteration time..

Share this post


Link to post
Share on other sites
Hi yilatil,

I think you're missing the point. At each node the octree defines a finite area of space. In this space is child nodes which define the sum of "space" of the parent.

When constructing your octree, you should set a leaf node size limit so you recursively divide the space until this limit is reached - this is where your leaf nodes are. You assign items to your leaf nodes if their bounds either intersect or contain the item bounds [depending on implementation].

In your case I would assign faces (or triangles) to the leaf nodes if the bounds of the triangle intersect the leaf then you can find all triangles within a certain distance of a point in space very quickly.

The leaf node size limit will depen on your needs. For example, if you gave large triangles that have bounds of say 40,40,40, it wouldn't make any sense to have leaf nodes that have bounds of [1, 1, 1] as lots of leaf nodes would contain the same trianlge.

Hope this helps,

Cheers,

Chris

Share this post


Link to post
Share on other sites
s3mt3x is right. Imagine all your scene fits in a huge cube. You then imaginary split the cube in 8 identical cubes. Now you can say which triangles of your meshes are in which of the 8 cubes (octree = oct - tree which means 8 tree, each node is split in 8). Then you pick up each of these 8 cubes and split it in 8 little cubes each. You can go as deep as you need, for example there is no point when a certain little cube contains only a part of one triangle or so.

LE: if after a split you find that a node contains empty space, you can eliminate it from the tree (and by doing that you are eliminating that part of the scene space from your frustum testing, speeding up things a bit).

[Edited by - meeshoo on October 12, 2010 6:20:35 PM]

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