Simple collision: AABB or OBB?

Started by
16 comments, last by schupf 12 years, 7 months ago
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?
  1. The mayor which spent $ on fixing and maintaining the sewers, ensuring no one gets flooded.
  2. 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.

Previously "Krohm"

Advertisement
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. =(
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.
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 [font="Courier New"]btDbvtBroadphase [/font]is AABB based. Furthermore, [font="Courier New"]btGhostObject [/font]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! wink.gif

Previously "Krohm"

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!


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...;)

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....
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?!

This topic is closed to new replies.

Advertisement