Sign in to follow this  
Nameles

ABT, Octree, or kD-Tree

Recommended Posts

I know there have been many discussions about these data structures here, and I've read through several of them. Once I decide which I will use there is definitely no shortage of material to help me implement it. My questions are: Are there any significant differences between these data structures that make one better than the others when sorting mesh rather than polygons? Is there any significant difference algorithmically that make one better than the others for real-time modification? My model system breaks models into meshes similar to the D3D mesh objects. One thing I don’t want to do is split these meshes because the straddle the bounds of a node in my spatial data structure. I have two big reasons for not splitting meshes. First, I already have too many meshes, potentially 1500-2000 may visible at any given time (obviously I need occlusion culling but even with occlusion this is still possible). Second, splitting meshes will make real-time modifications of my spatial data structure nearly impossible for performance reasons. Since I may have up to 200 non-static (moving) meshes I really need to have the ability to modify the spatial data structure at runtime. If there is already a thread with these questions answered, I apologize for asking again. I did search but there were so many hits I couldn’t read them all. Also, most seem to deal with systems that split geometries and that’s not how I will be using the data structures.

Share this post


Link to post
Share on other sites
There are certainly differences between them for real-time update.

If you're going for a fully dynamic scene (ie. any of your 2000 objects might move often), you probably want to steer clear of kD trees as I know no good way of updating them quickly without them degrading. You could probably come up with something, but usually you'll end up just convering KD trees to one of the other algorithms :)

Octrees are easier to update on the fly, but it somewhat depends on what you do regarding objects spanning several subtrees: if you allow nodes to expand past their original size to encompass these objects then you'll have problems with tree degradation... you'll have to keep track of this and "fix" the tree every once and a while. Conversely if you store a pointer to the object in all of the leaves, you'll have some trouble moving objects around while keeping track of all these things.

The other negative aspect of octrees is that they tend to create arbitrary areas of the map where adjacent objects are a long way away in the tree (ie. the first subdivision... "near" objects that cross this boundary involve traversing ALL the way up and ALL the way back down the tree). There are ways to solve this by keeping adjacency pointers and such but that's just more fun, epsecially if your octree is allowed to spawn new subdivisions on the fly.

I don't know a lot about ABT's (if you mean adaptive binary trees), but I think they were created somewhat to solve these problem while sacrificing accuracy (ex. nodes can overlap and the tree is allowed to degrade somewhat as objects move). Again you'll have to deal with tree degradation as in the octree case, but the situation is somewhat simplified by only having a binary tree.

So basically I'd say that if you try to slog through the fun of octrees you'll end up implementing everything complex about ABT's, except in a more general case than necessary. It probably makes the most sense to use ABT's with a routine that rebalances/cleans up the tree run when the tree starts to get too degraded.

Share this post


Link to post
Share on other sites
Of course you could also have 2 trees - one for the static geometry and one for the dynamic geometry. Then you could use an ABT or Oc-Tree for the static geometry and a kD-Tree (or BVH) for the dynamic objects.
This means you have to travers two trees, but with so many dynamic objects in a scene this approach could still perform better than putting all objects in a single tree.

Share this post


Link to post
Share on other sites
First, I would say that kd-trees aren't really much good for dynamic manipulation and you'd better go with one of the others.

Octrees are paerhaps the easiest approach, you can make it slightly more optimul by using 'loose-octrees' by allowing the size of the volumes to grow slightly to encompass and object, expect this will lead to degredation of the octree so you have to do a run through and tighten every bound in the tree once in a while (like AndyTX mentioned), or perhaps automatically detect when a node becomes needlesly loose and tighten it there and then.

ABTs were originally designed for static geometry however they are often used by people for dynamic geometry also. You would have the same problems with ABTs as you would with loose-octrees (tree degredation) but (as AndyTX said) fixing this is slightly simpler (although octrees are a simpler system over-all).

Now, (and this it depends on how adventurous you feel): There is a variation on ABTs refered to as the 'liquid adaptive binary tree' (LABT). Few people know much about them but they are the uber solution to spatial partitioning with dynamic objects. If you are interested then check out one of my old threads but in paricular the post from Yann. To my knowledge this is the only thread he has openly talked about LABTs but he does talk about what they entail.

Good luck choosing
dmatter

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