3

I'm creating my very first 3D game and I've run into a couple of problems.

I read about AABB intersectioning and the idea of building trees from it, but the one thing that I couldn't understand is, if my "character" rotates during the game, the concept of the axis-aligned isn't preserved!

I've checked a couple of libraries (like oz-collide, OPCODE, and more), and I've seen that the implementations were made for static objects, because it uses the boxes without an origin (for non static, all the nodes in the tree should be updated after each movement).

Those libraries supposed to be super-fast, and I had probably mistaken somewhere.

What is the explanation?

Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
Amir
  • 349
  • 6
  • 13
  • why not use the GPU?
    [check out my answer in another thread](http://stackoverflow.com/a/36682347/2378218)     – Yomi1984 Apr 17 '16 at 21:21

2 Answers2

2

Sadly yes, if your character rotates you need to recalculate your AABB, and it will not necessarily be a snug fit either. If you have a rectangle and rotate it so it's no longer rectiliniear the AABB will be bigger than the object.

The AABB is fast because the intersection test is very simple but as you've already discovered it becomes problematic when accurate intersections are needed on objects not aligned to the AABBs axes.

The AABB is still useful for quick tests, which I suspect those trees are made for. With a AABB tree you can quickly eliminate large swathes of objects from a more accurate testing phase. If the query returns a couple of extra objects it doesn't matter much. In your rotated character case this might mean that your character is regarded as in a region when he/she really isn't.

The AABB-tree lends itself to this with ease since each time you pass a test you go deeper into the tree and into more detail.

You can use a Oriented Bounding Box (OBB) when you need really accurate intersections. It can be implemented with the separating axis theorem. I see oz-collide has support for OBBs already.

There are alot of resources on OBBs, this one helped me: GPWiki on separating axis theorem

Here's an implementation.

You can calculate an AABB from an OBB if you need to.

Skurmedel
  • 21,515
  • 5
  • 53
  • 66
  • @Amir: Thanks, I think I am a bit inaccurate in my answer though. I looked at some other trees and realized that if you make an AABB for each triangle you get a quite accurate collision detection regardless (kinda like making an AABB for each atom). It will never be as accurate as doing an intersection test that accounts for rotated objects, but it will probably be much quicker. I guess many engines use a hybrid approach but I'm too ignorant to say much more about this :) – Skurmedel Nov 05 '10 at 00:55
  • Updated my answer to better reflect newfound enlightenment :) – Skurmedel Nov 05 '10 at 00:59
1

OZCollide works for moveable entities and is time independent (you just have to give a velocity vector). It also works for OBB (not only AABB).

Check the online documentation: http://www.tsarevitch.org/ozcollide/docs/ link broken

Caroline
  • 4,875
  • 2
  • 31
  • 47
sveltis
  • 11
  • 1