Jump to content
  • Advertisement
Sign in to follow this  
Downie

Frustum culling using loose octrees

This topic is 2745 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 am implementing frustum culling for dynamic objects into my engine and have been reading a lot about "loose octrees". Well I say "alot" but really it's just lots of posts of people saying how good they are and that they gave O(1) insertion and deletion. I understand the principles that the octants are treated as being larger than they are and that the loose factor can go up to 2. This means that an object can be inserted into a single node based on it's size. The trouble is that alot of the articles don't use a "k-factor" of 2 (probably to get a tighter fit) and therefore lose the fast insertion/deletion; instead they maintain an adjacency structure so you can traverse all nodes at a given depth and test the centre of the object with each node.

I only need a rough culling test and I'd like to have the O(1) insertion time and have worked out the formula for calculating the depth (level) that an object should be inserted. However I cannot find any articles that discuss a formula to calculate an exact node from the size and position of an object.

Have I totally misunderstood the algorithm and am I looking for something that isn't possible? If anyone can point me to any good papers or articles (I've read http://tulrich.com/geekstuff/) then that would be great.

PS It may be worth mentioning that I am using a linear octree stored in a 1D array

Thanks for any help

Share this post


Link to post
Share on other sites
Advertisement
I have heard that the equation I am looking for may be in a games programming gems book. If anyone can post the equation for me then I would be delighted

Cheers

Share this post


Link to post
Share on other sites

I have heard that the equation I am looking for may be in a games programming gems book. If anyone can post the equation for me then I would be delighted

Cheers


Have you tried CiteSeer

Share this post


Link to post
Share on other sites

[quote name='Downie' timestamp='1300214982' post='4786130']
I have heard that the equation I am looking for may be in a games programming gems book. If anyone can post the equation for me then I would be delighted

Cheers


Have you tried CiteSeer
[/quote]

Cheers, I've found a couple of articles that look interesting. I'll post back any results

Share this post


Link to post
Share on other sites

I don't see the problem. For each node in tree if partially inside check sub-tree if fully inside set all sub-trees as inside if fully outside set all sub-trees as outside Pablo

Edited by jbadams
Restored post contents from history.

Share this post


Link to post
Share on other sites
Well, if you've got your level, and k=2, you're there

since an object fits inside the node, any bounding box with it's centre in the node will fit, if you calculated the level correctly. (worst case scenario: centre of bb on the edge of "tight" node, bb's dimensions is equal node's dimensions. Half of the bb is outside the "tight node", but each side of the "tight" is padded by the same amount (half dimension) of loose.

or, in pseudo

int depth; //you got this

int horizontalNodeIndex = depth*(bb.centre.x / sceneBB.width)

Share this post


Link to post
Share on other sites

Well, if you've got your level, and k=2, you're there

since an object fits inside the node, any bounding box with it's centre in the node will fit, if you calculated the level correctly. (worst case scenario: centre of bb on the edge of "tight" node, bb's dimensions is equal node's dimensions. Half of the bb is outside the "tight node", but each side of the "tight" is padded by the same amount (half dimension) of loose.

or, in pseudo

int depth; //you got this

int horizontalNodeIndex = depth*(bb.centre.x / sceneBB.width)


Cheers. It was just that last horizinatlNodeIndex equation I was looking for.


Thanks guys

Share this post


Link to post
Share on other sites
Oh by the by how do you mark things as solved in the new GameDev??? I used to edit the post title but I can't see where to do that

Share this post


Link to post
Share on other sites
You shouldn't mark as solved anyway, as that might disencourage further people from posting in the thread and contributing to the discussion :)

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!