Archived

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

Separating Axis Test

This topic is 5582 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

I''ve never heard of this test! Perhaps I know it by some other name. Could you explain what the test is supposed to test for please?

Thanks,

Timkin

Share this post


Link to post
Share on other sites
Objectcollision... Box to box.

Got the name from Gino Van Den Bergens paper "Efficient Collision Detection of Complex Deformable Models using AABB Trees". (Nice title )


Share this post


Link to post
Share on other sites
hmmm, do you mean that you align the bounding box to an arbitary axis to encompass the model ??

Its my duty, to please that booty ! - John Shaft

Share this post


Link to post
Share on other sites
I guess I mean that.
Projecting the boxex it to 15 different axis (axises? ) to see if all overlap, or something like that.

The main question is, how do you calculate these axis''s... (Gotta brush up my 3d-english)

/Johan

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
you do the same exact transformations for the bounding box as you did for the object, thus they shall end up centered upon each other.

Share this post


Link to post
Share on other sites
quote:
Original post by MisterAnderson42
There are many docs and code for the separating axis tests at www.magicsoftware.com


Thanks for the link MA42... that''ll help me figure out whether I understand what this ''test'' is!

Timkin

Share this post


Link to post
Share on other sites
Check out my webpage (The physics docs):

http://homepage.ntlworld.com/j.owens1/Main.html

It''s really called the Separating Plane Test ( Basically a test to see if there is a plane which separates the two objects - and if so this means that they don''t intersect ) but I think I also got that wrong in my doc :-)

It''s actually really simple however it''s one of those things that''s explained really badly in Mathenese, and mine isn''t much better. One thing - Make sure you know what a dot product does and how to project a vector onto another vector as this is what this mainly relies on.

Share this post


Link to post
Share on other sites
I actually think that the basic concept behind a seperating axis test isn''t all that difficult. Basically, the separating axis test detects if two boxes (or whatever volume you like) overlap by projecting their extents on all possible seperating axes. If the projections of the boxes overlap on one of those seperating axes, the boxes must also overlap.

In the 2D case, there are only 2 seperating axis (X and Y). So, a 2D seperating axis test for two boxes may be a simple as:

// Determine if there is overlap in X.
bool overlapX = (box1.maxX < box2.minX || box1.minX > box2.maxX);

// Determine if there is overlap in Y.
bool overlapY = (box1.maxY < box2.minY || box1.minX > box2.maxX);

// Determine if there is overlap.
bool overlap = (overlapX || overlapY);

It gets a bit more complicated in 3D, because there is a whole bunch of seperating axes in 3D space, but the principle remains the same.

HTH,

Jim Offerman
lead developer
Crevace Games
www.crevace.com

Share this post


Link to post
Share on other sites
Oops. I should check my links before I post. Try http://www.magic-software.com/Doc.html
(note the hyphen I was missing...)

His docs there give example code for triangles. In the source code section, there is code for OBBs as well.

quote:
I''m still having trouble finding a good explanation to this. How do you determine these 15 axis?


From Dave Eberly''s book, 3d game engine design:
Let the first box have center C0, and axes A0, A1, A2 .... Let the second box have center C1, axes B0, B1, and B2 ..... The potential separating axes are of the form C0 + sL where L is one of Ai, Bj, or Ai cross Bj for 0<= i <= 2 and 0 <= j <= 2.

I suggest looking at this book if you are serious about using this test to its full extent. He derives the most optimal way to test against each axis.

Example code for OBB-OBB test, aproached in much the same way as Dave Eberly does: http://www.gamasutra.com/features/19991018/Gomez_5.htm
(this is in the member area of gamasutra, joining is free and only takes a minute):

I remember another article at gamasutra, but cant seem to find it. It was a bit more intuitive to understand. It went like this. Both objects in the test must be convex. For each plane in object 1, check which side of the plane all of the points in object 2 are on. If the are all on the outside, this is a separating plane, and there is no collision. If all planes are checked, and no separating plane is found, then there must be a collision.

This test is very simple to understand and implement, and doesn''t require too many computations (each "side check" is only a dot product) as long as the convex objects are kept to a small number of points and planes (use Qhull). And it is quite simple to check the last separating plane first, as it is still likely to be a separating plane after one game timestep.

Anyway, HTH.

Share this post


Link to post
Share on other sites
quote:
Original post by MisterAnderson42

From Dave Eberly's book, 3d game engine design:
Let the first box have center C0, and axes A0, A1, A2 .... Let the second box have center C1, axes B0, B1, and B2 ..... The potential separating axes are of the form C0 + sL where L is one of Ai, Bj, or Ai cross Bj for 0<= i <= 2 and 0 <= j <= 2.




Then you just compare if any of the vertices are overlapping based on that axis right?

My math is a little rusty.
I'll look into the resources you gave me.



Thanks again!
/Johan



[edited by - JohanK on August 30, 2002 2:58:06 AM]

Share this post


Link to post
Share on other sites
C0 + sL is a line (or axis), not a plane. In essence, all points in both OBBs must be projected onto this line and compared for overlap. Though, many assumptions can be made by the structure of the geometry so that only one or two points need to be projected per axis. This is how you tell what vertices to compare. One must examine each axis on a case by case basis and determine what the farthest extents of the box are along that axis. For example, the farthest extent of box 1 in the A0 direction is simply a/2, where a is the "width".

Share this post


Link to post
Share on other sites
quote:
Original post by MisterAnderson42
C0 + sL is a line (or axis), not a plane.


I figured that out two seconds after posting, that''s why I removed that part of the post. (I referred to C0 +sL as a plane if you''re wondering over MA42s post).

How do you project a given vertex onto a line?

Thanks
/Johan

Share this post


Link to post
Share on other sites
quote:
How do you project a given vertex onto a line?

It is simplest to do when that line passes through the origin. This is why it is convienint (as both Dave and the gamasutra article do) to transform box 2 into box 1''s coordinate space and performing these tests in that space. So, C0 is the 0 vector. In that case, the projection of a vertex onto that line is (L dot v) / ||L||, where v is the vector in question.

Share this post


Link to post
Share on other sites
So you just make sure that the axis you are testing agains always passes through the origin...

When using the equation;

(L dot v) / ||L||

Does L have to be aligned to the x axis or is it enough that it passes through the origin.

If not, the resulting value of the equation, is it the length you have to travel along the L axis or just the x-component.

Another thing,
First translating box 2 into box 1's coordinate space, that is only helpful for the first three test right, don't you have to translate box 1 into box 2's coordinate space to test axis b0,b1 and b2?

The 9 cross products between box a and b, do they always pass trough origin?

(Sorry for my bad english, hope you guys understand this anyway).

/Johan

[edited by - JohanK on September 1, 2002 9:34:02 AM]

Share this post


Link to post
Share on other sites
quote:
Does L have to be aligned to the x axis or is it enough that it passes through the origin.

Only has to pass through the origin. (note: a vector always passes through the origin. Really for the given equation to work, the line C0 + sl must pass through the origin, meaining C0 is 0)
quote:
If not, the resulting value of the equation, is it the length you have to travel along the L axis or just the x-component.

The length along L. My calc book terms it the component of V along L. It is not *really* a length, because it can be negative. Formally: the point L * projection given above = point on the line of L closest to V. If this is confusing, find websites on the dot product, they will explain this in much more detail than I am.

quote:
Another thing,
First translating box 2 into box 1''s coordinate space, that is only helpful for the first three test right, don''t you have to translate box 1 into box 2''s coordinate space to test axis b0,b1 and b2?

One does not have to do this. b0, b1, and b2 are perfectly good separating axis no matter where they are centered. True, it would be much more convienient to place them at C1 (thus transforming box 1 into box 2''s space), as the comparisions become simpler.

quote:
The 9 cross products between box a and b, do they always pass trough origin?

As I said above, these axes are just axes. They can be "placed" anywhere for the purposes of the test. The purpose of transforming box 2 into box 1''s coordinate space is so that they can share a common origin, C0 and the axes of the space are aligned along the axes of the box to simplify some of the tests. There is no need to transform them at all. One could simply test these boxes for overlap on all these axes against the origin of the world space.

Share this post


Link to post
Share on other sites