Jump to content
  • Advertisement

Archived

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

joanusdmentia

AABB tree bottom-up construction

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

Firstly, at the moment this is solely for collision detection and not frustum culling. Oh, and it''s binary. i.e. each AABB node encloses 2 child AABB nodes. Ok. I currently have bottom-up construction working. The problem is it takes something like 5 minutes (on a 1700XP) and 160MB to build a tree of a 1000 poly geometry!! I''m currently doing it the slowest way imaginable. For each leaf node I''m calculating the distance to every other node, sorting the nodes by distance using std::map. Then these std::map''s are sorted into another std::map by the shortest distance for the node the first std::map corresponds too. Now as far as I can tell, this should give about a really decent heirrachy as it always pairs off nodes with the the nearest neighbour. Should the nearest neighbour have another neighbour that''s closer, the the original node will get paired with the second nearest neighbour, etc... Now my question is what other ways are there to do this? Are there any statistical approaches which avoid having to sort absolutely everything? Also, would generating the tree top-down and splitting it based on density produce a better tree? I don''t think it would, but I not too sure either. Joanus D''Mentia

Share this post


Link to post
Share on other sites
Advertisement
*drop*

Speaking of dropping, first of all, you should drop std::map. It''s a nice and convenient thing, but definitely not suited for this kind of time and memory critical task. Try to stay with plain old data arrays here. While they are more messy, they will take far less memory and be faster for your type of application. If you absolutely want to use an STL container, try to stick with more basic types, such as std::vector or std::list. They will be more efficient.

Hmm, now to your algorithm. I''m not exactly sure what you are doing. OK, so you are trying to find node pairs with the minimum distance between them, and group them pairwise into hierarchic tree. So far so good. But how do you create those primary leaf nodes in the first place ?

If I were you, I would go with a top-down approach. It''s much easier, and a lot faster. The result might or might not be better than your current approach, as with all hierarchical data structure, this depends on your geometry. But also on how you generate your leaf nodes in the first place. The problem with your approach, is that time complexity will tremendeously increase, as soon as you use it on more complex geometry.

Share this post


Link to post
Share on other sites
quote:

Speaking of dropping, first of all, you should drop std::map



Was going to anyway, it was just get everything working initially.

quote:

Hmm, now to your algorithm. I''m not exactly sure what you are doing. OK, so you are trying to find node pairs with the minimum distance between them, and group them pairwise into hierarchic tree. So far so good. But how do you create those primary leaf nodes in the first place ?



Sorry, I should have had that in my initial post. The primary use for the AABB tree will be for face accurate collision detection between dynamic geometries. Each leaf nodes corresponds to a single face in the geometry. I pair off leaf nodes to get the first set of internal nodes in the same way, the only difference being I use the face centers instead of the AABB centers to calculate the distances.

quote:

If I were you, I would go with a top-down approach. It''s much easier, and a lot faster. The result might or might not be better than your current approach, as with all hierarchical data structure, this depends on your geometry. But also on how you generate your leaf nodes in the first place. The problem with your approach, is that time complexity will tremendeously increase, as soon as you use it on more complex geometry.



I''m really not too concerned about the speed of constructing the tree, if worse comes to worse it can be calculated overnight using a tool and loaded at run-time. Memory on the other hand could be a problem. Do you know of any other methods for bottom-up construction? And I guess more importantly do you know if bottom-up construction generally results in a better tree heirrachy than top-down?

Hmm, perhaps splitting it up using an octree so that there are a few hundred faces in each leaf, and then only trying to pair off the faces in those leaves would work. Oh well, if I don''t get this working well soon I''ll give top-down a go.


Joanus D''Mentia

Share this post


Link to post
Share on other sites
An update...

Fixed the memory usage problem. Instead of storing the calculated distances of every object to every other object I just keep recalculating it whenever I need it. Despite all the extra maths being done it actually runs quicker as well since it''s not doing so many allocations.

Still, any suggestions for other construction methods are more than welcome.


Joanus D''Mentia

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!