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.

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.

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]

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".

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

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.

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]

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.

Thanks to all of you!

I got a pretty good understanding of this now!
Keep up the good work...

/Johan