#### Archived

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

# AABB Tree Help

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

## Recommended Posts

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 on other sites
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 on other sites
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 on other sites
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.

1. 1
Rutin
28
2. 2
3. 3
4. 4
5. 5

• 11
• 11
• 10
• 13
• 20
• ### Forum Statistics

• Total Topics
632948
• Total Posts
3009401
• ### Who's Online (See full list)

There are no registered users currently online

×