Jump to content

  • Log In with Google      Sign In   
  • Create Account

Simple collision: AABB or OBB?


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
17 replies to this topic

#1 schupf   Members   -  Reputation: 216

Like
1Likes
Like

Posted 03 September 2011 - 02:39 PM

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?

Sponsor:

#2 Darkbouncer4689   Members   -  Reputation: 110

Like
0Likes
Like

Posted 03 September 2011 - 03:19 PM

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




#3 schupf   Members   -  Reputation: 216

Like
1Likes
Like

Posted 03 September 2011 - 03:45 PM

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)

#4 Darkbouncer4689   Members   -  Reputation: 110

Like
0Likes
Like

Posted 03 September 2011 - 03:53 PM

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.

#5 schupf   Members   -  Reputation: 216

Like
0Likes
Like

Posted 03 September 2011 - 06:35 PM

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?

#6 Darkbouncer4689   Members   -  Reputation: 110

Like
0Likes
Like

Posted 03 September 2011 - 06:53 PM

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

#7 schupf   Members   -  Reputation: 216

Like
2Likes
Like

Posted 04 September 2011 - 02:34 AM

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?

#8 Darkbouncer4689   Members   -  Reputation: 110

Like
0Likes
Like

Posted 04 September 2011 - 02:10 PM

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.

#9 Krohm   Crossbones+   -  Reputation: 3245

Like
1Likes
Like

Posted 05 September 2011 - 02:13 AM

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)

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.

Posted Image 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. Posted Image 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? Posted Image

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.

#10 Darkbouncer4689   Members   -  Reputation: 110

Like
0Likes
Like

Posted 05 September 2011 - 02:51 PM

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

#11 Krohm   Crossbones+   -  Reputation: 3245

Like
2Likes
Like

Posted 06 September 2011 - 01:25 AM

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.

Yes, I understand your position, but I think it was worth stressing this more. Maybe it's just me but I think the message completely got lost.
Yes, I understand this position very well. I still think it's not worth spending 6+ months on physics... because after 2 months, one will still be scratching the surface, I can tell for experience, and there's at least another few dudes around here that will agree.
Problem with physics is: unless you use it in creative ways, it's assumed to be there. Let's do the city-major comparison: who do you think will get more preference?
  • The mayor which spent $ on fixing and maintaining the sewers, ensuring no one gets flooded.
  • The mayor which spent $ on a new stadium.
Although many companies claim to "have interest in acquiring complete know-how in developing internal technologies to leverage our customer's potential" the truth I had to learn in the hard way is they don't even have the means to evaluate this property. Therefore, the more you bring them, the better.

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.

Yes, it's C++ related. The idea is that stronger assumptions give faster code. For JS, all bets are off as this is implementation dependent at best but in case of JS in Unity, they claim not messing up with type can produce faster code. I look forward to your JS-based project!

If you are trying to make a fps where picking has to be 100% accurate then OBB's may not be enough.

Probably need to elaborate on this. A thing is the broadphase, a thing is the narrowphase. AABB based broadphase has proven to be good enough. The goal of the broadphase is to be a fast rejection test, and AABB has demonstrated to be the fastest test around.
The narrowphase later takes all the potential collisions and resolves them in detail by computing "collision distances", this data is also used to improve stability as far as I've understood. The narrowphase uses solid's effective "shape". Most of the time, this is already a rough approximation. Personally I think convex hulls are the real deal, but Bullet also allows to resolve narrowphase collisions using generic meshes. Their performance seems to be really bad but that's what we get for accurate per-triangle collision.

There's nothing really wrong about what you're doing as far as I know, it's just pre-2003 collision detection, it worked well and can still work; I am surprised you pulled this out in 2 months but if it works for you, that's just great.

#12 Darkbouncer4689   Members   -  Reputation: 110

Like
1Likes
Like

Posted 06 September 2011 - 03:05 AM

Well you seem to be very knowledgable. You must have a few years of experience in the industry. I'm going to pick your brain for a minute if you don't mind.

I have read Real-Time Rendering's chapters on collision detection, I have Ericson's Real Time Collision Detection, and I have Eberly's 3D Game Engine Architecture. Either I missed something or I am using outdated resources. Some of the techniques you are talking about are the first I've heard of them.

I thought it went

Sphere -> AABB -> K-DOP -> OBB -> Triangle

I didn't even know anything else existed (outside of weird things like cones, ellipses or capsules).

Since my engine is in JS, obviously I won't have as much CPU power as a c++ engine, thus I knew triangle/triangle tests were out the window. I was hoping that OBB collision (or multiple OBB's for a single object) would be accurate enough to not need triangle/triangle.

You said that AABB are proven to be the fastest. Having to update AABB's under rotation was the factor that drove me away from them, but if you say they are best then I will add more support for them in my engine. You are actually the first person I've ever seen claim that a certain BV is best, do you have any resources or data on this?

I do have things "working" in the sense that I can compute minimum spheres and minimum or approximated OBB's offline and I have an optimized 15 separating axis test for OBB/OBB intersection as well as sphere/spere, ray/sphere, ray/obb. The hard part is knowing what the optimal (fastest) design would be.

I hope to make a Sims like game with the engine. So I believe the extent of my physics would just be picking and collision.

I welcome any advice on a fast collision/picking design.

Thanks,
Dark

P.S. I'm sorry Schupf. I thought spending the last 2 months on collision/picking gave me enough knowledge to be helpful, I guess I was wrong. =(

#13 Infernal-rk   Members   -  Reputation: 135

Like
0Likes
Like

Posted 06 September 2011 - 10:00 AM

I do not see a reason to go from AABB to OBB. Do one or the other.

scene graph culling(not vs view frustum, isolate the world zone/node your character is in and test against objects in that same zone/node)->Sphere->AABB/OBB->COLLISION triangle mesh

The collision mesh can approximate your normal mesh with little modelling effort.. no texturing really required. If you really want, you can have the collision mesh change shape along with any bones controlling animation of the normal mesh so you can use this on animating objects. Want it faster? do smaller ellipsoids and spheres to approximate your collision surfaces of the object.

That would be my approach at least.

#14 Krohm   Crossbones+   -  Reputation: 3245

Like
1Likes
Like

Posted 06 September 2011 - 12:46 PM

I have read Real-Time Rendering's chapters on collision detection, I have Ericson's Real Time Collision Detection, and I have Eberly's 3D Game Engine Architecture. Either I missed something or I am using outdated resources. Some of the techniques you are talking about are the first I've heard of them.

I thought it went

Sphere -> AABB -> K-DOP -> OBB -> Triangle

I don't know about the 3rd edition of RTR but the 1st edition definitely cuts short on CD&R... it's only 20 pages (+ the chapters dealing with intersection methods). I've only skimmed through Eberly's by means of inter-library sharing and I don't remember much. Those tests are incrementally more accurate but I never intended them as being "nested", I always considered those to be one or another. AFAIK Unreal Tech decided to go with AABB or K-DOP. I suppose they're using one or the other, I don't think they "nest" the tests (although as I previously wrote, using a very gross grained test with a more accurate convex hull might eventually make sense in some situations).

Problem is, CD&R is really overlooked. Problems such as stability, tunneling, pre-emptive contact point generation, internal-edge issues, restitution, convex decomposition, framerate independant determinism... Don't even get me started on rigid body dynamics or destruction. I didn't know, or grossly overlooked them as well. That's why I embarked in trying to make it work by myself. If I knew that from beginning, I would have just used middleware.
On the pro side, it is possible to do CD without considering those issues... as long as the world is kept simple and the framerate is high enough. But let's make this clear: it's far from being a "complete" CD system as there are nowadays. This does not imply it will be insufficient, but I feel the need to make sure everybody has a clear understanding of the limitations.

You said that AABB are proven to be the fastest. Having to update AABB's under rotation was the factor that drove me away from them, but if you say they are best then I will add more support for them in my engine. You are actually the first person I've ever seen claim that a certain BV is best, do you have any resources or data on this?

I have googled a while for the 'academical' papers, but didin't find them. They were too many years ago. Anyway, if you just download Bullet, you'll see btDbvtBroadphase is AABB based. Furthermore, btGhostObject reports potential collisions by AABB. Check out Bullet Broadphase, it will probably help you!
It is my understanding all broadphase algorithms used in bullet resolve potential collision pairs in the broadphase by the means of AABB only... perhaps they don't even rotate (what's going on isn't quite crystal clear to me, I've just searched the forums). This however is for broadphase.
Narrowphase must go by using a more accurate test. In case of bullet that's the actual shape used. By application's point of view, that's already an approximation: in narrowphase, AABB is just way too gross-grained to be useful at all. I actually allow only spheres, OBB and convex hulls.

Are you sure there are no physics libraries ready to go for JS? It seems box2d has a port even to flash... but in case you need to do that, just don't even think about fetching to the physics the same assets you mangle for graphics, if 3D that's probably going to take you to performance hell in no time.

Dark, what you said is correct. I think you're just trying to be accurate, which is good. But getting stuff done faster is better! Posted Image

#15 Darkbouncer4689   Members   -  Reputation: 110

Like
0Likes
Like

Posted 06 September 2011 - 11:26 PM

Thanks Krohm,

I'm going to check out their design. It's always useful seeing what another engine does. It seems like I should add support for AABB (which will be easy) and perhaps convex hulls? It seems like convex hulls may be one of the most accurate tests. I'm not sure how expensive the tests for it are, I'd guess it depends on the number of faces on the CH, but it still may be faster than having multiple OBB's per object.

It seems I have a lot to look into, thanks for the resources!

#16 schupf   Members   -  Reputation: 216

Like
0Likes
Like

Posted 07 September 2011 - 07:21 AM

P.S. I'm sorry Schupf. I thought spending the last 2 months on collision/picking gave me enough knowledge to be helpful, I guess I was wrong. =(

No need to say sorry. To be honest I found your postings more helpful than the postings of Krohm. Basically Krohm just said: "Your ideas are stupid, use a Library". Since I want to LEARN something and want to implement it myself this is not very helpful...

I do not understand how I can stick to AABBs if I want precise collision detection. Most of my objects are small and it makes sense to use AABBs for those. But I also have some relatively large houses that are rotated. If the player runs against the wall I want him to slide along the wall. Thus I just NEED an OBB.

I thought about my system and I think I am going to implement this approach:
+ An AABB quadtree for culling (view frustum vs hierarchical AABB tests) and picking (ray vs hierarchical AABB tests)
+ Cells for collision detection for dynamic (moving) objects. In every frame I basicall do this:
For each dynamic object I detect the cell in which the object is and make an AABB/AABB test against all other STATIC (not moving) and dynamic objects in this cell
(If the dynamic object is on the border of some cells I test against all adjacent cells)

Do you think this design is ok? (Bear in mind I make a relatively small game and no Killzone 3...;)

#17 RobTheBloke   Crossbones+   -  Reputation: 2341

Like
0Likes
Like

Posted 07 September 2011 - 07:45 AM

I do not understand how I can stick to AABBs if I want precise collision detection. Most of my objects are small and it makes sense to use AABBs for those. But I also have some relatively large houses that are rotated. If the player runs against the wall I want him to slide along the wall. Thus I just NEED an OBB.

No, you need a triangle test. The purpose of AABB/OBB/Sphere tests is not to provide accurate collisions, but to reduce the amount of triangle tests that you need to perform (although, if you happen to have a world filled with boxes and spheres, then the fact it's fast & accurate is an awesome bonus). More often that not you'll use oriented capsules/spheres/boxes/cylinders to apprpoximate your shapes (again, in an attempt to reduce the amount of triangle tests). AABB's are utterly useless as the only collision primitive - they are only useful at reducing the number of tests.

To be honest. you just need to get AABB's working. An OBB/Ray test is exactly the same as an AABB/Ray test - albeit with the addition of transforming the ray into the local frame of the OBB. Pretty much any other collision primitve -> OBB test works in the same way. Transform the primitive into the local frame of the OBB, and do an AABB test.

Normally when people start down this route, they start writing box/box tests, before realising they need swept-box, swept-sphere tests. Before they know it, performance has ground to a halt, numerous bugs crop up, you start having nightmares of being chased down corridors by big balls before falling through what should be a solid wall. Eventually you scrap the whole lot and use PhysX/bullet instead. If you want to do it yourself for educational reasons, then go for it. Before you do however, at least take a look at bullet/PhysX to give you some hints on how to structure the public interface....

#18 schupf   Members   -  Reputation: 216

Like
0Likes
Like

Posted 07 September 2011 - 07:53 AM

I do not see why I would need a triangle test (which sounds crazy slow to me anyway!) if the OBB encases my house PERFECTLY. If my OBB/OBB test return an intersection, then I know I am intersection the house. No need to iterate through all the triangles of the house and player mesh.

Like I said, I just wanted to do this: Check in which cell the player AABB is. Test player AABB against all static object AABBs in this cell. If intersection and IF the static object has an OBB: Test player OBB against object OBB -> If again collision -> collision response.

Of course this is not a full blown collision detection system. Yet I see no reason why this system should be bad for my game?!




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS