Jump to content
  • Advertisement

Archived

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

[Question]:axis-aligned box and oriented box

This topic is 5078 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

what are the properties of them? Are they same? If there are articels talks about this, really appreciated. In a source code file I saw the box structure contained 3 entries: MgcVector3 m_kCenter; MgcVector3 m_akAxis[3]; MgcReal m_afExtent[3]; What's they means? [edited by - sambsp on June 11, 2004 1:22:00 AM]

Share this post


Link to post
Share on other sites
Advertisement
Hi,

The Dave Eberly code you''re refering to is for an OBB (oriented bounding box). The center is the center of the box. The three axes can be any orthonormal basis. The extents tell you the ''radius'' of the box along each axis.

An AABB (axis-aligned bounding box) is a special case of an OBB where the three axes correspond to the world axes. This greatly simplifies things and allows for a lot of shortcuts.

An AABB can just be defined by a center and three extents. It''s often also defined by two corners, min[3] (the minimum x, y, and z values) and max[3] (the maximum x, y, and z values).

There''s much more that can be said, but that should get you started at least.

Share this post


Link to post
Share on other sites
I need more detailed information about these 2 boxes, like why we use obb but not aabb?
Is there any articles I can refer to?

Share this post


Link to post
Share on other sites
An OBB will turn with the object, so the front of the box will always correspond to the front of the object, even if you lay it flat along the ground or put it at a 45 degree angle. An AABB will not be able to cope with this, and will simply encompass the entire thing in an axis aligned box. So if you have a tall, thin box and you rotate it 45 degrees, with an OBB you'll still have a tall, thin box. With an AABB you will now have a short, squat box with a lot of empty space in the corners that will still count as a collision.

Edit: Here is an article (When Two Hearts Collide: Axis Aligned Bounding Boxes) about AABB.

Share this post


Link to post
Share on other sites
The short answer is that an OBB may fit your object more tightly than an AABB. This means that anything that requires a bounding box intersection test to happen (rendering, narrow-phase collision detection) will happen less often (i.e you'll get fewer 'false positives'), and you'll save some CPU time.

The downside is that most operations you'll want to perform are more difficult with OBBs than AABBs. So it's a tradeoff between efficiency and ease of implementation.

Share this post


Link to post
Share on other sites
http://www.gamasutra.com/features/19991018/Gomez_5.htm
http://www.magic-software.com/Documentation/DynamicCollisionDetection.pdf (might be a bit heavy)
http://www.owlnet.rice.edu/~comp650/Spring01/presentations/OBB/OBBTree.ppt

ect...

OBBs bind objects tighter. imagine a steel bar, sitting diagonally on a table, the AABB will be massive, but the OBB will just wrap around the bar a lot tighter.

AABBs are a lot faster to compute, so good for dynamic 'broad-phase' culling (frustum culling, collision culling, AI, ...), where speed is more important than accuracy.

OBBs are a lot more difficult to compute usually, although not always. If you want to fit an OBB around a mesh, you have to compute the covariance matrix, and find the eigen vectors of that matrix to get the orientation of the box.

for collision detection, it's a lot more maths to do a two-OBBs test than a two-AABBs test.

OBBs can be made of an AABB and an orientation matrix as well. this is usually the case for binding a box around a model. Models are often themselves axis aligned (or should be), in the model space (like, with orientation = identity matrix, and placed at origin). Then the tightest bounding box in model space is a simple AABBox. When the object rotates, the orthonormal basis of the matrix can be extracted very easily, and this orthonormal base and the AABB can be used to form a OBB if you wish to.

in collision detection with meshes, there is still debates (at least in my head) on which to use. An OBB tree, or an AABB tree. OBBs are tighter and neater, and less space is wasted. On the other hand, AABB tests are faster, and easier to compute. They also take less memory space, and can be compacted efficiently.

Also, when testing two trees for intersections, OBBs do not require any extra work, but to do a AABB vs an AABB when at least one of them has an orietnation, then you need to implement an AABB-OBB intersection test anyway.

Share this post


Link to post
Share on other sites
Expanding the topic, in case sambsp knows more now it might be interesting for him.

Oii I am writing a paper on a slightly modified algo fo OBB/OBB. It's equivalent to the 15 axes algo but enhances more quick, early rejection and is perfectly adaptated for SIMD, compressing many tests and symetries as multiple SIMD logical operations. Would you mind to review it before I decide to submit here at Gamedev ?

My goal is to show how an (my) optimized SIMD library can help boost typical routines.


Shortly presented this looks like this :

I consider the inputs are two axis aligned Boxes oriented by a Quaternion and translated by a Center position on world space. This spares from AAB (3 extents) -> OBB transfos in a typîcal physics engine. And this (BQC) is more compact (10 floats) than the Center, Axis, Extents (CAE : 15 floats).


It's based of the separating plane theorem.

1) First I transform the second OBB (B) in the local coords of the first (A). I have now B in a temporary CAE format. It's a quaternion division (<=> multiplication) followed by a conversion to a rotation matrix + new translation. I takes roughly 40 cycles in 3DNow.

2) I compare the AAB of B with A. Which is equivalent to testing the 3x2 planes of A against the vertices of B. It can be done with not much more than 10 SIMD instructions, well parallelized. It rejects the majority of the tests in less than 10 clock cycles.

3) I test the 2x3 planes of B against A. It enhances the nearest vertex trick (AABox vs Plane) by checking two opposite planes against 8 vertices, all at once (x16 acceleration). It can be done with a great efficiency using the abs operator on vectors (apply abs() to each component), and multiplications by transposed matrices (thus dot products). I'd bet for 15-30 cycles in 3DNow, less in SSE.

4) I test the edges of A against those of B. Probably using the X=0, Y=0, Z=0 2D projections is the best way to do. Then the problem becomes point(A)/line segments(B). With 2D components, 3DNow is great. SSE can execute two 'threads' in parallel.

Note before 1), sphere/sphere early rejection works best.

Share this post


Link to post
Share on other sites
someone optimised the RAPID collision detection library the same way, by using a quaternion representation. However, I doubt they went into the same optimisation depths as you :)

one of the aspect of the OBB trees is the memory space it takes, can be potentially large.

(15 floats per OBB) * (4 bytes per float) * (number_of_tris) * (2) = 120 * num_tris.

so for only 1000 tris, on OBB tree will be well in the 100Kbs.

I'm not designing a collision system at the moment, at least professionaly, so performance is not an issue for me, but there is a lot of potential use for a fast OBB-OBB or ABB-OBB test, for things like ragdolls and well, general OBB tests.

If I was designing a collision system for a game, I'd be also concerned about the PS2 performance and vector unit optimisations, and for the XBox. I wonder how your SIMD optimisations would work on those platforms.

also, there are optimised versions of the OBB-OBB tests, which cuts down a lot of the crap in the naive calculations, reducing a separation axis plane to only something like 10-15 float muls and adds per axis.

Share this post


Link to post
Share on other sites
Greetz, Charles, if you would like, I could assist you with looking over your article. I have also played around with SIMD math for doing various things such as trasnforming multiple vertices in parallel, etc. One thing I was confused on- are the SIMD instructions the same for both AMD and Intel chips?

Quote:
Original post by oliii
If I was designing a collision system for a game, I'd be also concerned about the PS2 performance and vector unit optimisations, and for the XBox. I wonder how your SIMD optimisations would work on those platforms.


The PS2 has a Vector Unit processor which is basically the equivalent of SIMD (all the major game consoles can multiply 4 vectors in parallel these days). His library should be able to port to all these platforms. Of course, SIMD is diff for each platform so I am not sure how much it would be to port. There is also another belief- that if one optimizes his code correctly for the cache and cleverly vectorizes his code, it can achieve performance just as well as SIMD.

There is also OpCode which is a very nice AABB/OBB lib written by Pierre Tierdman. Did you compare your lib against it? Was just curious. Anyway running a collision test under 10 clocks sounds pretty good to me. What system are you using? On my 1.6ghz intel machine I get bout 11 clocks on a standard AABB Overlap test.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!