• Advertisement

Archived

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

[Question]:axis-aligned box and oriented box

This topic is 4986 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
I am going to an OBB-OBB collision system. I have studied the separating axis method, but I wanted to find another, a more powerful solution (I am that kind :)). And I reduced it to OBB-AABB collision test almost the same way as Charles did. Fast face vertex test, and edge-edge test quite differently than Charles.

Share this post


Link to post
Share on other sites
@Oliii
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 :)

No doubt all the best algos are equivalent. Everything is in the implementation details. The quaternion stuff in fact is an optimization of the interface. It takes the needs of one kind of user into account. It's specially profitable for someone who uses OBBoxes as collision volumes around dynamic physical bodies. If I can bring something, it's possibly how to mix floating point stuff and logical operations to eliminate redundant tests.

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

Here are some options one could choose to minimize memory requirements :

- For many small dynamic objects, let the quaternion of the 'OBBox' be a reference to the quaternion of the physical body, this saves 12 bytes. If the center of the OBBox can be identified to the center of gravity (maybe by slightly growing the box), nothing more is required. Translation is given by the mass center of the body in world space. This saves 16 bytes.

So optimally, 2 pointers and 3 floats (extents) are required. Next 8 or 16 bits precision extents could be used. And since SIMD have nice 16bit to float unpack instructions ... Conclusion : less than 128 bits per ABBox, usable in real time, should be possible.

- Now for OBBtrees, I haven't thought much of it recently and I don't know if someone proposed highly compressed an optimized implementations. I suppose sharing common referentials (quaternion+translation) and thus storing AABoxes instead of OBBoxes is a possible track.

SIMD optimisations would work on those platforms.
The algo in itself is good, and my intuition is it's mathematically optimal, I see no possible redundance atm. I mean it's good in floating point, so no doubt it would certainly adapt well to the instruction set of the VU. Still I don't know it enough to be pedantic here.

there are optimised versions of the OBB-OBB tests
Do you have a pointer to one of the best you know atm ? In the ones I have seen, there were (true, not 1/constant) divisions for instance. There is none in my computations. So if I understand you well, you say the order of magnitude is around 15*(10-15) = roughly 200 elementary flops. I think it does better.

Well it depends on the conditions of use, because the initial quaternion stuff costs a lot of flops (50-75 ?). And for dynamic OBBoxes, the transformation has to be done anyway. So this should be added to the 'score' of the routines that use a 4x3 Matrix + Extents as inputs.


@vajuras
I'll send you the html doc once it's done.

SIMD instructions the same for both AMD and Intel chips?

Basically two technologies : 3DNow and SSE. Some machines can do both, some only one of them. That's righlty one of the reasons I created this VSIMD (Virtual SIMD) in order to be more productive, and hide some uncompatibilities betweens many variants of hardware.

so I am not sure how much it would be to port
I have no idea if the concepts in VSIMD could also work for the VU. There may be killing details. For instance the emms stuff inherited from MMX is quite a pain on Intels. I know that the PS2 architecture is really uncommon. But I wish I could find someone who could test and try to implement the lower layers of VSIMD in native VU or other SIMD code. Even if some crossplatform features would be ruined, it could still be worth trying it.

Pierre Tierdman
OK thanks I have heard about OpCode. But I did not have much time to read col det articles with the attention required lately.

Anyway running a collision test under 10 clocks sounds pretty good to me.
Hmm this was just a guess. And it's only the first rejection test, the easiest by far. It's after the quaternion stuff and before the rest. What's true is that a centered AABox against an OBBox can be done in roughly 10 cycles.

I am writing the html paper before the code this time. Usually I do the reverse, but here you might understand why. Complex math, and complex code. I prefer to analyse it very carefully. Nonetheless I guess very well the clock cycles. It's pretty obvious when the number of elementary instructions is around 10 and schedules well, that you get a bit less than one clock per SIMD op usually. That's my experience.

The code in question is just around that simple line :

AbsDist = abs(Sb.x*Mb.X) + abs(Sb.y*Mb.Y) + abs(Sb.x*Mb.Z) + Sa - abs(Mb.O)

Where Mb is the matrix of B viewed in the local axes of A.
Where S is the extents (or scale or size as you wish) vector.
Where abs opearates abs on each vector.
AbsDist contains the minimum absolute distance for the 3 axes.



@szinkopa
I hope you can give a bit more details so that we can compare. Maybe the two solutions can reinforce each other, as proven in another thread ;)

Share this post


Link to post
Share on other sites
Charles:

How many point-linesegment test does your solution need?

3 (projections) * 4 (points on A) * 12 (edges on B) = 144

This is the worst case. This can be probably optimized somehow.

And how do you test a linesegment with a point fast?


My idea is that during vertex-face test I store, where a particular vertex is from the box. When I have tested all the vertices (16), I know where they are with respect to the other box.
After that I go over the edges (24), and for an edge from its 2 vertex info I can easily decide two thing about this edge: it is surely not colliding, or it is surely colliding. If none of them is true, then I do the Point-LineSegment test you mentioned. But I know from the vertex info, with which edge my current edge may collide.
So this method is a speedup for your edge-edge method. Most of the lines will thrown out in this test. I tried it with 2 books :)

As you can see, it is not absolutely clear yet, but I think it can work very efficiently if well implemented.

Share this post


Link to post
Share on other sites
How many point-linesegment test does your solution need ?
I am currently wrting the details about it. It's the last step I need to write in my docs.

In fact it's not about line segments really, it's about ifinite lines, hyperplanes. There is no collision if a separating plane exist. So after the point/plane and plane/point tests, if the projected AABox is in the positive half space of one of the lines (2D hyperplane), there is no collision. If none is found the boxes collide. The computation is much faster than :

3 (projections) * 4 (points on A) * 12 (edges on B) = 144

Exploiting the nearest vertex trick (reading the signs of the line directions gives the index of the vertex), and the parallelism of four opposite edges of a rectangle, only three (2D) dot products, and a few comparisons need to be performed per projection. With 3 projections, that's 9 dot products.

(*) Or cross product, which is equivalent here, since a^b = a*perp(b) with perp(x,y) = (-y, x).

Else I think you implicitely use the Voronoi (diagram) space partition around your boxes. There are 6+12+8 such cells around a box. I need to think about it a bit and try to see what you are suggesting. I'll post here later. I know that Voronoi partition is great to determine contact points very quickly. My algo is just a collision test : YES NO atm. But I think I can slightly modify it to find and return the eventual contact points.

[Edited by - Charles B on June 25, 2004 3:39:49 AM]

Share this post


Link to post
Share on other sites
I have just looked up this Voronoi regions method. It seems to be the same that I imagined. I have almost reinvented the wheel :)

Share this post


Link to post
Share on other sites
V-Clip and Lin-Canny use Voronoi regions. I have had a look at V-clip, but my idea is different from that. Lin-Canny also searches one point on both polyhedron whose distance is minimal.
I also want to use Voronoi regions, but I want to know if two objects collide or not, and if they collide then where the collision point is, to be able resolve it.

I have to think through my idea, I cannot describe it in more details yet.

Share this post


Link to post
Share on other sites

  • Advertisement