Archived

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

Halo Vortex

Dynamic ATB

Recommended Posts

I''ve got a question about constructing of ATB, or octree for dynamic objects. How do I create it. I mean, what does it look like in the beggining and after I add the first object, he procedure for adding more of them(Unlike static meshes, bounding space is unknown, so I can''t create one "root" AABB with min(x,y,z)-max(x,y,z) and then just start fitting everything inside like in a usual octree). Any links or help will be nice.

Share this post


Link to post
Share on other sites
Adding an object into an existing tree seems like it could be a little quirky, but just managing a tree isn''t too bad. Create the initial ABT with the object''s initial positions. As an object moves, so does it''s bounding box. Update those parameters and bubble them up the tree. Compute how well (actually how poorly) the current ABT satisfies the splitting criteria at each node and when a node reaches a certain level of "badness" (Yann calls it degeneracy, I believe), then rebuild the tree from that node down. You need to do some work at runtime, but you won''t be doing it every frame and there should be fewer dynamic objects than static so it should be alright.

I''ve no experience with adding more objects to an ABT, so I''ll leave that to someone who has such experience.

karg

Share this post


Link to post
Share on other sites
Nah, I understand that. But from where does dynamic ATB starts? Unlike static meshes, you don''t have main, "world''s bounding box", so you just can''t start subdividing this bounding box - dynamic objects can move anywhere.

1) So the question is, what does dynamic ATB looks like when there''s yet no dynamic objects added?
2) How do I add a dynamic object to the scene (like a missile, that was just fired from a battleship), taking into account that it can overlap with other dynamic objects?

Share this post


Link to post
Share on other sites
What kind of ABT are you referring to? There isn''t just one, so you can pretty much handle dynamic objects in any way you please, perhaps make a totally new tree?

If you want to use an ABT, simply adjust the AABBs to enclose the dynamic objects. This is very bad though if you get out into big open space (right over a valley between two mountains, for instance). The ABT will get very degenerated and the AABBs will grow like crazy. Perhaps you could add nodes in runtime for open spaces? Can be tricky with the free-form ABT...

The only way to figure it out, is to sit down and think of what will happen and experiment a little.

Share this post


Link to post
Share on other sites
Maybe these links on ABT would be helpful.

http://www.gamedev.net/community/forums/topic.asp?whichpage=1&pagesize=20&topic_id=123169 - ABT
http://www.gamedev.net/community/forums/topic.asp?topic_id=133512 - more on ABT
http://www.gamedev.net/community/forums/topic.asp?whichpage=1&pagesize=20&topic_id=132062 - guess what? ABT

Share this post


Link to post
Share on other sites
I haven''t checked the specific links given, but I''m pretty sure I haven''t seen anything about adding objects to a dynamic ABT and only a mention of creating and maintaining them. As I said before, a scene will likely have an initial position for some dynamic objects. Just build an ABT the same as a static one to start. Then when you move the objects, update their bounding boxes, propogate the new AABBs up the tree and recalculate the error metrics as you go. When the error gets too great (have to experiment on what too great an error is) then rebuild the tree from that node down.
That takes care of a fixed number of dynamic objects. Now some conjectures on adding objects:
One easy way is to just add the object as a child of a random leaf and update the AABBs up the tree like a moving object (as above). This could obviously lead to terrible results, but it will get you up and running. A more sophistocated version might search down the existing tree, find the "closest" node and add the new object as the "closest" node''s sibling. (the "closest" node would be replaced by a new parent with the "new" and "closest" as children of the new parent). Again propogate the AABBs up the tree and rebuild as necessary.
The rebuilding would keep the tree from becoming too unbalanced, and the error tolerance would control how unbalanced it could become before the tree is rebuilt, which is a pretty expensive operation. The rebuild for a dynamic ABT should emphasize speed over finding the optimal solution. It''s going to get rebuilt again anyway, so good enough is fine here. Try picking a few random split planes, along with dead center (classic quad-, octree style) and find the best amoung those.
One other thing that comes to mind is if a subtree is rebuilt, but that subtree''s parent needs to be rebuilt, it may be better to rebuild one or two nodes up from that parent. It could happen that the tree needs to be rebuilt at the bottom level, and the next level up, and the next level up, and the next...
It would be nice to try to avoid that by just jumping up a few levels. Don''t know how that would work exactly, but something to try.

karg

Share this post


Link to post
Share on other sites
There's alot of threads about ABT. Now, isn't ABT just a KD-tree with AABBs using various thickness of the sides? They seem to be created in the standard way which can be read in tons of papers.

EDIT: This sounded almost rude. I'm just curious.

[edited by - __fold on October 28, 2003 7:17:15 AM]

Share this post


Link to post
Share on other sites
Yeah, it''s actually just a binary tree. The unique thing about it is the error or fit function that is used to create split planes. A "good" tree is determined by this function which has a rather large domain. This compliates things, as it''s not stored in sorted order. Inserting items into the "best" location seems to be too expensive for runtime use. Therefore, some aproximation method would probably work best.
There are various other things that make it sightly different from a vanilla binary tree, like only the nodes contain information and the nodes can overlap. A slightly modified version of the standard algorithms needs to be used.

karg

Share this post


Link to post
Share on other sites