Archived

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

Lord_Omega

OBB vs AABB collision detection???

Recommended Posts

hi @ all u motivated people! I''m currently working on an engine for a 3d space RTS game (if you have no idea of what I''m talking about...think of homeworld), and I''d like to figure out what type of collision scheme would be more efficient: OBB or AABB trees. OBBs should be a lot more expensive...but if we have a couple hundred bullets flying through space, collision testing could become quite nasty, especially if the majority of them passes the spaceships very closely. But still...OBBs *are* expensive. So, any suggestions?

Share this post


Link to post
Share on other sites
How accurate do you really need bullet collisions to be? I really doubt it needs the polygon-level accuracy given by AABB/OBB trees. Just using a single bounding volume for each object and then casting a ray along the bullet's tragectory would be enough.

[edited by - joanusdmentia on October 8, 2003 10:04:01 AM]

Share this post


Link to post
Share on other sites
For a 3D space game, I suggest you use an octree, with a few dozen to a couple hundred objects per leaf node. Another possibilty is to use an ABT instead (there are plenty of thread about ABTs in this forum - use the search function). Then for each object, use a bounding sphere or ABBB for quick, crude CD. If you want more accuracy, you can then use either an AABB or OBB tree for the objects. AABB trees are quicker, but are generally a bit less accurate. It doesn't really matter which one you use, since they won't be touched very often anyway (only when all simpler tests pass). Finally, for ultimate accuracy (if you want and need it), you can use polygon-level CD on the parts of the objects that pass all above tests.

But keep in mind that as joanusdmentia said, you probably don't need that much accuracy, considering the speed at which things typically travel through space.

EDIT: On second thought, perhaps one large ABBB tree (or an ABT, which is basically an adaptive form of an ABBB tree) would do a better job than an octree, since objects tend to be fairly far apart in space...

Michael K.,
Co-designer and Graphics Programmer of "The Keepers"



We come in peace... surrender or die!

[edited by - technobot on October 8, 2003 10:37:26 AM]

Share this post


Link to post
Share on other sites
Yep, I''m also worried about updating costs of AABB hierarchies.
Concerning accuracy...I really *need* polygon-level accuracy. And that''s probably, why bounding-volume-hierarchies need to be as efficient as possible.

Share this post


Link to post
Share on other sites
quote:
Original post by Lord_Omega
Yep, I'm also worried about updating costs of AABB hierarchies.
Concerning accuracy...I really *need* polygon-level accuracy. And that's probably, why bounding-volume-hierarchies need to be as efficient as possible.

Well, yes, if you make one large AABB tree, you'll need to update it every time your objects move... The problem is that for efficient CD, you need the tree to be balanced by the amount of objects in each node. In other words, in each level, the objects should be more or less evenly divided among the nodes of that level. This way at each comparison you'd be eliminating about half the objects. An AABB tree can do a better job at that than an octtree. An ABT can do an even better job, but it may be a bit tricky to implement (because of the required heuristics). You should probably go over the ABT threads around here to see if it's suitable for you.

Another possibility, since for efficient CD the nodes don't have to fit thightly to the objects (except when you reach the object level), is to use a loose AABB tree. Each node would be slightly larger than the sum of its child nodes, thus allowing for some freedom of movement. But you still need to make sure the tree is balanced somehow.

Michael K.,
Co-designer and Graphics Programmer of "The Keepers"



We come in peace... surrender or die!

[edited by - technobot on October 9, 2003 7:46:18 AM]

Share this post


Link to post
Share on other sites