Quote:Original post by Basiror
however in my engine i keep the hierarchical scene subdivision independent from the implementation the matrix thing is actually quite scene dependent

the lookups might perform faster but rendering indoor environments will definitly be slower due to the lack of indoor pvs

the mappers need to place the PVS manually in the editor in my engine to get the optimum out of it

You can write a matrix or an octree hash map with the same interface (I derived them form the same virtual class).

Quote:Original post by RPTD
concerning updating the octree i never had troubles so far. ok, i'm using my own scripting language and there new/free is automatic. what i don't get is though why updating the octree should invalidate other elements. in my implementation i can update the tree with at most N steps (N beeing the depth) and all other elements are not changed at all. can you outline the problem there?

I was not precise and actually this fact depends by the octree implementation.
And my poor english does not help me! [smile]

I'll try to explain myself: if you create a deep tree with every leaves at the same depth (fixed depth octree) then erase an element do not invalidate the others or modify the tree so much. Probably you have to erase recursively some nodes but other nodes are not affected.

If you adopt a different tree with leaves at different depth then erasing an element (again) does not invalidate, strictly, the other iterators (ie pointers to octree nodes) but "invalidate" the structure; in practice you have to rebalance the tree (pull up nodes if you delete items or push down if you insert new ones).

I tested different solutions and the "fixed depth" octree is the simplest but also the most dangerous! Think for example about this 2D situation:

in a volume               V = (0,0) - (1,1)you have to insert the rect K (key = bounding box )                            K = (0.49, 0.49) - (0.51, 0.51) In practice K is a quad with edge = 0.02 centered in the middle of the main node

In this situation you will create nodes at the max depth! In fact recursively on each subdivision you have again a quad centered in the "pivot" of the parent.

If you apply this situation in a 3D octree you can have a very large number of nodes (8^x !!!) and this produce waste of memory and an incredibly large number of items. Make a "test" on a paper and you understand what I mean.

If you dont use a fixed depth octree you can insert K in the main quad; when you insert a new key K1 you can push both K and K1 to a deeper level until the max depth is reached or until the number of items in the same nodes (hash collisions) is less than a threshold you specify. And so on. I hope you have understood [smile] In this situation the tree is more memory greedy because
we have less nodes but the algorithm is also faster because you collect less items and traverse less nodes.

But we pay ths feature!
In this case when you destroy or insert a node you have to rebalance the tree. If you dont rebalance the tree the risk is that you "saturate" the octree space ( in practice the structure waste memory like a matrix and it is iterated slow like an octree)
Make a balanced tree can be usefull if the scene is static (and the octree can be "compiled" once); but if the scene is dynamic this can destroy its benefits.

In my opinion there is not a perfect data structure; for example there are different solutions in the case of meshes.
Or you can adopt an hybrid one.
Also it depends by the global space (the control volume), the number of items, the relative size of these items...I cannot generalize of course.
You have to test different algorithm to find the better (that is the fastest :) ).