Archived

This topic is now archived and is closed to further replies.

radiogeak

AABB Tree Help

Recommended Posts

radiogeak    122
I have programmed the easier trees such as a binary tree and b-tree. Now i''m trying to find out how to create an AABB tree. I''ve looked all over the net and can''t find a single good example! Yes, there are cuts of source code here and there, but the commenting is usually horrible and there are many includes that aren''t accessible. I have searched book stores and online book stores, but have not found a book that covers them. Can anyone help out on my thirst of knowledge for AABB trees? Thanks.

Share this post


Link to post
Share on other sites
SimmerD    1210
DirtyPunk has an example on FlipCode, and there is an article in Game Gems2 that is useful.

I have a working version, but I just took a look at it and it wouldn''t make a great example.

Are you trying to put triangles in the tree or obects, or?

Is it a dynamic tree or static?

Share this post


Link to post
Share on other sites
radiogeak    122
Its a dynamic tree. I am in the process of creating a top-down 3d shooter and I need to get collision detection in. Also, if you know a better way to do this, then i'm all ears.

Yah, I checked his code out, but the includes aren't in the zip file (which some external code is used in the aabb tree code), there isn't any reference on how to implement it, ect, which still leaves me confused.

[edited by - radiogeak on January 17, 2004 12:23:58 PM]

Share this post


Link to post
Share on other sites
SimmerD    1210
Here is what I suggest. Start with a huge root node that contains coordinates from -max_float to +max_float.

The root node has 2 children whose bounding boxes may overlap each other, but are fully contained within the root.

The root node also has a std::vector or std::list of objects whose bounding sphere or box is fully within this node.

Each child node may contain 1 or 2 child nodes and 1 or 2 leaf nodes ( max of 2 children total ).

Each non-leaf node is recursively defined like the root node above.

The leaf nodes contain all the static triangles in the level for collision purposes.

Leaf nodes contain some # of triangles ( like 6-20 ).

Dyanmic objects put into the deepest non-leaf node of the tree in which they fit without overlapping a child node''s bounding box. This is similar to how you would place dynamic objects in a quad or octtree.

Build your tree of triangles alone ( with no objects in it ). Then place dynamic objects in the non-leaf nodes, based on their bounding boxes, and the bbox of each object.

Share this post


Link to post
Share on other sites