# Frustum culling using loose octrees

This topic is 2826 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 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

##### 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 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 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

Restored post contents from history.

##### 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 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 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 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

1. 1
2. 2
3. 3
Rutin
15
4. 4
5. 5

• 10
• 9
• 9
• 11
• 11
• ### Forum Statistics

• Total Topics
633682
• Total Posts
3013312
×