Simple collision: AABB or OBB?

Started by
16 comments, last by schupf 12 years, 7 months ago
Hi,

I have a little terrain (maybe like 100 x 100 meters) with some trees, houses, rocks etc. The player moves around this little
map and I need collistion detection against the objects and picking (the user should be able to pick certain objects, for example trees have to be highlighted if the mouse cursor is over a tree).

Now I wonder what could be a good and simple (!) approach to solve my collision detection/picking. If possible I want to avoid "sophisticated" structures like kd-tree.
Should I just give every object an OBB and iterate through all objects and make a collision test player vs object OBB? Any other suggestions?
Advertisement
Most people will respond with the following "it depends".

Probably the biggest thing it depends on is how accurate you want your collision to be. If you just want an easy and fast collision/picking system, then sphere/sphere and ray/sphere are easy and very fast.

If you want more accurate collision then obviously we can move to AABB/OBB. These depend on a lot of factors as well. Will the objects be static or dynamic? Will the objects be aligned with the axis or not?

If the objects are static and aligned with the axis, then an AABB fits just as well as an OBB and has faster/simple collision algorithms. If the object is dynamic then you have to update the AABB under rotation, and you will get bad fits when the objects gets rotated.

Depending on how much time you have, you can move on to OBB's, but I will warn you ahead of time that computing minimum OBB's and implementing ray/OBB and OBB/OBB collision tests are not trivial and they are also more expensive than the other two.

As for terrain collision, a general technique is to cast a ray downward and perform a triangle/ray intersection test and then just keep the player above the height of the triangle they are standing on.

-Dark


Thanks for your reply!

All my objects are static. The only thing that moves is the player. Some objects are rotated (for example some houses) and for these objects an AABB would be pretty bad.

Yes, spheres are fast but if the object has a "long shape" (like a long house), the bounding sphere gets to big and the player stops moving meters before he even touches the house. AABBs are also very bad for the rotated houses.

What do you think about this: All my scene objects return a polymorphic bounding volume object, which can be a sphere or AABB or OBB. For most of the objects I return an AABB and for the rotated houses I return an OBB. Good/bad idea?

I also thought about a 2 pass system: All objects return an AABB and only if the player partially overlaps with the AABB, I make an OBB test.

Do you think its ok to just linearly iterate over all my scene objects and just test every object with the player? (I guess I have around 50 objects)

What do you think about this: All my scene objects return a polymorphic bounding volume object, which can be a sphere or AABB or OBB. For most of the objects I return an AABB and for the rotated houses I return an OBB. Good/bad idea?


Yes. It is important to have multiple types of BV's for different objects. For example, if your object was circular, a sphere would fit it better than an OBB, so there would be no point in the object having an OBB.


I also thought about a 2 pass system: All objects return an AABB and only if the player partially overlaps with the AABB, I make an OBB test.


This is also a standard design. My engine has a sphere for all objects which I use as a quick check. Only objects that have intersecting spheres move on to the more expensive OBB/OBB check.



Do you think its ok to just linearly iterate over all my scene objects and just test every object with the player? (I guess I have around 50 objects)


If you aren't trying to make a full blown game engine this is probably fine. However, if the number of objects in your scene starts to get out of control you will need to implement some type of spatial partitioning system such as a BVH (bounding volume hierarchy). With these you can eliminate large groups of objects with a single intersection test.
And who should be responsible for building the BVH? Currently I am only telling the scene manager: place this tree at this position, this stone here and so on. I guess computing a good BVH automatically by the engine is not that trivial, is it?
Currently I only know about the theory of spatial partitioning algorithms such as BSP, BVH, and OctTrees. I will be implementing some type of spatial partitioning into my engine in the next few months, but until then I can't offer much advice on the details of it unfortunately.

I would imagine you could just recursively build the BVH as a tree structure, with the leaf nodes being a single BV. How you group the clusters of BV's is still a bit unclear to me though.

What are your goals with this system? If you havent started any kind of BV system I can tell you that it took me quite a few hours to get all of that implemented, so trying to juggle a spatial partitioning system at the same time is not a good idea.

If you want a well done collision detection system with picking you are looking at having to implement the following:

ray/triangle
ray/sphere - easy
ray/AABB + ray/OBB - These two are basically the same algorithm with some optimizations made for AABB's

Sphere/Sphere - easy
AABB/AABB
OBB/OBB - 15 separating axis test

Minimum Sphere BV construction
Minimum AABB BV construction
Minimum/approximation OBB BV construction - Computing a minimum OBB can be much too time consuming to do at load time. If you have a system where you can compute BV's offline then it will give much better fits. Otherwise you can use an approximation algorithm that computes a covariance matrix and eigenvectors.

Implementing all of that is probably a good two months of work unless you are a math wiz, which I am not =)

Don't get discouraged though, it's all doable, just trying to share my experiences to give you some insight into what lies ahead.
-Dark

P.S. You can probably find some good open source implementations of all the above. David Eberly's website is a great resource. www.geometrictools.com
Thanks for your information. Very helpful!

I know thats a lot of work (and many hours to debug :D ). But the difficulties of writing a game and an engine is also part of the attraction:)

Another question: Would you recommend using the same structures for collision/detection and culling? For example is it a good idea to make collision/detection AND culling just based on bounding volumes on the objects. Or is it better to use bounding volumes for collision/picking and some other structure (cells, quadtree) for culling?
Even if you use some spatial partitioning system for culling (such as a quadtree or BVH) you will still at its core be doing intersection tests. These tests will be frustum/BV instead of BV/BV. You could of course make a sphere BV around your view frustum and do sphere/BV intersection tests as well.

There may be some type of spatial partitioning that doesnt use intersection tests, but quadtrees, octtrees, BSP trees and BVH's definitely do.

I should also mention that view frustum culling without some type of spatial partitioning system will be inefficient.
Perhaps it is just me, but I think this thread has gone so wrong it's hard to believe.

I have a little terrain (maybe like 100 x 100 meters) with some trees, houses, rocks etc. The player moves around this little map and I need collistion detection against the objects and picking ... what could be a good and simple (!) approach to solve my collision detection/picking?
Simplest solution: use a collision detection library. Such as Bullet or PhysX (I'm currently using the former).
In particular, note that Bullet uses allows different kinds of broadphase tests, one of those is an AABB tree. None seem to use OBB. AABB rejection tests, simply put, is so fast it greatly compensates the loss of precision. This behavior emerged in various other papers.

Bullet can do the CD&R for you in a large array of cases. In principle, collision detection between static and dynamic objects become essentially transparent to the application. Kinematic objects however are not transparent by definition. You will need to write the glue and this glue will be application-dependent.

Picking is pretty much supported in Bullet by using ray casting and it's both fairly flexible and accurate. I haven't looked at the performance of this functionality yet, but from a 10,000ft view, it seems promising. PhysX also supports raycasting AFAIK.

In both cases you'll need to go a bit through the hoops to link bullet collision objects to your gameplay-specific entities. In some pathological cases, this can be a bit troublesome (but it's probably an unfortunate byproduct of my current design).

Some objects are rotated (for example some houses) and for these objects an AABB would be pretty bad.
In this case you would fetch the physics API with a different Collision shape. No need to mess up with different representation. In case of Bullet, you could eventually encode this as an opaque blob (although I don't suggest to do that). You have prenty of collision shapes available including heighfield and convex hull. Want to be really accurate? Gimpact trimeshes will do.

What do you think about this: All my scene objects return a polymorphic bounding volume object, which can be a sphere or AABB or OBB. For most of the objects I return an AABB and for the rotated houses I return an OBB. Good/bad idea?
Probably bad in most naive implementations. Bullet does this under the hood but in some seriously elaborated way - AFAIK it's basically doing all the "casts" in advance to select an algorithm for accurate collision, then dispatch. Broadpase is probably AABB or OBB at best.

DarkBouncer, what you write about this is correct in line of principle - this info must be stored somewhere - but devil is in the details and what you seem to suggest has the potential to make this performance critical path more difficult to optimize by the compiler. Therefore, I'd avoid it.

I also thought about a 2 pass system: All objects return an AABB and only if the player partially overlaps with the AABB, I make an OBB test.
Nonsense. If the rough collision test matches, I don't think it's worth doing another fast-rejection test which 1) is not so fast 2) it's going to likely fail. Do yourself a favour: optimize your life instead, get the job done and use a physics API!

DarkBouncer, what you said is not standard design. Standard design is to perform a fast rejection test, if that fails, work it out in detail, perhaps using some kind of data structure to accelerate the whole thing. Stacking multiple gross-grained tests is not standard at best. If the nested test would be a convex hull I could understand, but sphere to box? It's like multiplying two random numbers together and claim better randomness, or encrypting data twice using two algorithms and claim the result is more hacker-resistant.

Do you think its ok to just linearly iterate over all my scene objects and just test every object with the player? (I guess I have around 50 objects)[/quote]I suppose it could be doable for 50 objects (I guess you have a iSomething processor) but don't expect this to last long.

And who should be responsible for building the BVH? Currently I am only telling the scene manager: place this tree at this position, this stone here and so on. I guess computing a good BVH automatically by the engine is not that trivial, is it?
The physics API. And trust me, it will dispatch fairly better than you.

If you want a well done collision detection system with picking you are looking at having to implement the following...
Don't get discouraged though, it's all doable, just trying to share my experiences to give you some insight into what lies ahead.
rolleyes.gif You are sadistic. Look, I really understand you want to share the pain but seriously, I don't see any reason to not use a physics API such as Bullet. If I look back I see myself scratching my head to the brains working on CD&R. ohmy.gif Why didn't I go for Bullet a couple of years ago? Why did I do that to myself? Why do you want to do this to someone other? sad.gif

Another question: Would you recommend using the same structures for collision/detection and culling? For example is it a good idea to make collision/detection AND culling just based on bounding volumes on the objects. Or is it better to use bounding volumes for collision/picking and some other structure (cells, quadtree) for culling?
You can use the same structure, but it must be built differently (at best) as the granularity involved need to be much different. Consider that even if you have 1k unique vertices per leaf, this is still very little for anything that is at least GeForce 4 (not 400 series, 4). Regardless of the data structure you use, unless you're doing AAA+ it will start to be pretty much the same thing as a linear scan once the leafs hold thousands, if not tens of thousands primitives.

If you use a physics API then I suggest to just build your system independently, the accuracy of physics API is just way overkill for culling on modern hardware.

Previously "Krohm"

Dear Krohm,

I stated that there were some opensource applications that would do all of the collision for him, I suppose I got into the details too much and that went unnoticed. Some people are building an engine for a portfolio, in which case I don't see how plugging in some opensource middleware shows that you understand how engines work at their core. It's probably just my opinion, but also my engine is in javascript, which I do not believe there are any quality 3d physics engines available in javascript, thus I had to do it from scratch.

I have not had time to tests the speed of a variety of different types of BV's, so I made a choice and ran with it. I would love some criticism of my design if it may save me weeks of redesigning in the future.

You state that having multiple BV's will be hard for the compiler to optimize, could you please give more detail about this? I'm assuming you are thinking of a game in c++, but even for my javascript engine im curious.

You also state that sphere to OBB is a bad idea. I actually got this idea right out of the pages of Real-Time Rendering. Are they wrong? You say if the fast rejection fails, work it out in detail. Do you mean triangle/triangle tests? I suppose this all depends on if one is happy with having an OBB being the most accurate level of collision in the game. If you are trying to make a fps where picking has to be 100% accurate then OBB's may not be enough.

Feel free to tear my design apart. I would rather you didn't spare my feelings then to have to redesign at a later point.

Thanks,
Dark

This topic is closed to new replies.

Advertisement