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

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

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

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

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)

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

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

You shouldn't mark as solved anyway, as that might disencourage further people from posting in the thread and contributing to the discussion