Sign in to follow this  
Raeldor

OBB and SAT Question

Recommended Posts

Hi All, I am reading a book on collision detection and it has a 'general' section on SAT. It says to test two polyhedral objects that the following axes must be tested... Axes parallel to face normals of object A Axes Parallel to face normals of object B Axes parallel to the vectors resulting from the cross products of all edges in A with all edges in B Testing an OBB against an OBB then that makes 3 tests for the face normals of the first object, 3 tests for the axes of the face normals of the second object and 3*3 tests for the axes edges of A against all axes edges of B. That brings the total to 15 tests. Is this correct? Would that make a comprehensive collision check for two OBB's? Thanks!

Share this post


Link to post
Share on other sites
Quote:
Original post by Raeldor
I am reading a book on collision detection and it has a 'general' section on SAT. It says to test two polyhedral objects that the following axes must be tested...

Axes parallel to face normals of object A
Axes Parallel to face normals of object B
Axes parallel to the vectors resulting from the cross products of all edges in A with all edges in B

Testing an OBB against an OBB then that makes 3 tests for the face normals of the first object, 3 tests for the axes of the face normals of the second object and 3*3 tests for the axes edges of A against all axes edges of B. That brings the total to 15 tests. Is this correct? Would that make a comprehensive collision check for two OBB's?

That is correct. Section 4.4.1 has the details on OBB against OBB and the next-to-last paragraph on page 102 talks about the 15 needed axes.

Share this post


Link to post
Share on other sites
Quote:
Original post by Christer Ericson

That is correct. Section 4.4.1 has the details on OBB against OBB and the next-to-last paragraph on page 102 talks about the 15 needed axes.


Haha, damn... I knew I'd seen that page before. I was looking for it earlier and couldn't find it. Good to know that the OBB follows the general rule though.

Thanks!

Share this post


Link to post
Share on other sites
Hello again,

I am looking for the code for the OBB intersection test now. I am a little confused why you are allowed to use absolute values for the rotation matrix. Why does this not screw up the rotation?

Also, is it possible to calculate the collison point, normal and penetration depth using this test?

Thanks

[Edited by - Raeldor on April 23, 2006 12:28:40 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Raeldor
I am looking for the code for the OBB intersection test now. I am a little confused why you are allowed to use absolute values for the rotation matrix. Why does this not screw up the rotation?
The absolute values come from the equation on page 102 which, when considered for each of the 15 different axes, turns into Table 4.1. The introduction of AbsR is justified in Section 4.4.2.

Quote:
Also, is it possible to calculate the collison point, normal and penetration depth using this test?
Not as such, but you can enhance the approach to help provide such measurements. See the last paragraph on page 158.

Share this post


Link to post
Share on other sites
Hi,

I'm still trying to get my head around this. Sorry if I am coming across as a bit 'thick', but I would like to understand fully how it works.

Your statement on page 102 'If t is the translation vector from A to B and R=[rij] (the rotation matrix brining B into A's coordinate frame)', should it really read 'If t is the translation vector from A to B expressed in A's coordinate frame and R=[rij] (the rotation matrix brining B into A's coordinate frame)'? It seems you are using a simple |t0| as T.L in the first three lines which seems to suggest that it has already been translated, yet you have not specifically said so in the introductory text.

If that is true, then I can see what's going on in the first three columns of the first three lines. You are taking u, t and eA as they are since they are all in the co-ordinate frame of A. I thought the formula for rB should be

rB=eB.L

So what's the logic behind this column in the first three rows? Are you translating eB into the coordinate frame of A on the fly? Ie, translating eB into the co-ordinate frame of the first axis (uA0) for the first line to get the length along that axis, and then ditto for the following lines?

Also, I am still not understanding why you are allowed to have absolute values of the rotation matrix. I can see why you need to add the epsilon values to cope with floating point errors that make 0 > 0 unstable, but how can R=Abs(R)? You have derived a rotation matrix to translate into A's coordinate frame and then you are changing it, so is it really still moving stuff into A's coordinate frame?

Sorry to ask what probably appear as lame questions, but I think understanding this will help me to understand a lot of other things too.

Regards

Share this post


Link to post
Share on other sites
Not speaking for Christer here, but:
Quote:
Your statement on page 102 'If t is the translation vector from A to B and R=[rij] (the rotation matrix brining B into A's coordinate frame)', should it really read 'If t is the translation vector from A to B expressed in A's coordinate frame and R=[rij] (the rotation matrix brining B into A's coordinate frame)'? It seems you are using a simple |t0| as T.L in the first three lines which seems to suggest that it has already been translated, yet you have not specifically said so in the introductory text.
Yes, t is the difference vector as expressed in A's coordinate frame (or so it would appear). Looking at the code a bit later supports this.
Quote:
If that is true, then I can see what's going on in the first three columns of the first three lines. You are taking u, t and eA as they are since they are all in the co-ordinate frame of A. I thought the formula for rB should be

rB=eB.L
It might clear things up a bit to look at the equation for finding the projected radius of an OBB onto an arbitrary axis:
r = e0|A0.N| + e1|A1.N| + e2|A2.N|
Where e are the box extents, A are the box axes, and N is the axis. With an AABB this reduces to:
r = dot(e,abs(N))
Where the abs() function returns a copy of the input vector with each element set to its absolute value. Maybe this is what you were thinking of in your above example.
Quote:
Also, I am still not understanding why you are allowed to have absolute values of the rotation matrix. I can see why you need to add the epsilon values to cope with floating point errors that make 0 > 0 unstable, but how can R=Abs(R)? You have derived a rotation matrix to translate into A's coordinate frame and then you are changing it, so is it really still moving stuff into A's coordinate frame?
Consider again the OBB radius equation above. For the first 6 axes that we test, N is always an axis from the other box. You can see that over the course of these tests each axis of box A will be dotted with each axis of box B at some point. The exact same thing (axes dotted together) happens when B is rotated into A's space. The projected radius equation requires absolute values, so the elements of R cannot be used directly. However, we can simply take the absolute values of the elements of R and copy them into a new array.

The OBB test can be highly optimized (even a bit beyond what's been presented here). IMO though all this optimization can make the test somewhat impenetrable, especially if you're new to the concepts behind the SAT.

This isn't really a suggestion per se, but just an idea for you to consider. In its simplest form, the OBB test can be written with relatively few lines of code, along with some simple support functions. Such an implementation is not optimal, but might be more expressive of the ideas involved and help you to get your head around the SAT test a bit better. I think that working through the simple implementation would shed some light on some of the more perplexing aspects of the optimized version.

The simple version is straightfoward enough that it could probably just be typed into a post, so let me know if you need any more info regarding that.

Share this post


Link to post
Share on other sites
Quote:
Original post by Raeldor
Also, I am still not understanding why you are allowed to have absolute values of the rotation matrix. I can see why you need to add the epsilon values to cope with floating point errors that make 0 > 0 unstable, but how can R=Abs(R)? You have derived a rotation matrix to translate into A's coordinate frame and then you are changing it, so is it really still moving stuff into A's coordinate frame?
I think this question is probably at the heart of your problems. Note that all the separating axis test is doing here is testing the equation on page 102

|T.L| > rA + rB

for each possible separating axis (of which there are 3 + 3 + 3 * 3 = 15).

Table 4.1 lists, for each of the 15 axes, exactly what each of the three subterms of that equation becomes, given the translation vector t, the matrix R to move B into A's space, and extents eAi and eBi for the two boxes. The code corresponds to table 4.1, pretty much line by line, except for the setup at the start.

The setup at the start computes (once) a number of subexpression that recurs in the expressions of table 4.1, namely the taking of absolute values of matrix elements. Specifically note that all the rij terms in the second and third column of table 4.1 always occur within an absolute value. Rather than recomputing these absolute values again and again, they're computed once at the top of the function.


Now you might ask how exactly we arrived at the expressions in table 4.1. As jyk already explained e.g. the radii values come from the the projection of the box radius onto the given axis, using this expression

r = e0|u0.n| + e1|u1.n| + e2|u2.n|

where ei are the box extents, ui are the box axes, and n is the axis the box is projected onto.

A thorough derivation of this expression can be found in Section 5.2.3 (page 161-164). The expressions in table 4.1 have simply had each axis substituted into the projected-radius expression above and then been simplified. The absolute values come from this projection-radius expression.

The first column of table 4.1 is also obtained through expression substitution and simplification.

Hope that helps.

Share this post


Link to post
Share on other sites
Ok, I think I am starting to understand this now, thank you for bearing with me. So, let's take the first formula for rB

eB0|r00|+eB1|r01|+rB2|r02|

This corresponds to the formula

r = e0|u0.n| + e1|u1.n| + e2|u2.n|

Because the dot product is commutative, this can be written as

r = e0|n.u0| + e1|n.u1| + e2|n.u2|

But in our example for the first line, the test axis is uA0 and the box axis is uB, so re-writing using the same variable names

r = eB0|uA0.uB0| + eB1|uA0.uB1| + eB2|uA0.uB2|

so therefore

r00=uA0.uB0
r01=uA0.uB1
r02=uA0.uB2

thus corresponding with your pre-computed matrix. Am I on the right track now?

So, next question is for tests 4 through 6, is it true to say that you are moving both t and eA into box B's coordinate space using the inverse matrix so you can use eB directly?

I think you are right, jyk. A simplified version would probably be easier to help get to grips with. Trouble is that most books that are aimed towards beginners tend to avoid OBB's in favor of ABB's for their simplicity, so the books that tend to address the issue are aimed towards people with a higher level of maths understanding (Ie, simplified and more efficient formulas but not necessarily an explanation of how it was arrived at). I guess what I am trying to do is bridge that gap. It's all helping me sharpen my math skills though, so overall it's not a bad thing.

Thanks again!

[Edited by - Raeldor on May 1, 2006 6:52:23 PM]

Share this post


Link to post
Share on other sites
Hello again,

Ok, so I have coded up a very basic version for OBB collision detection. I know it's very far from efficient, but I have it more for readability and learning the concepts. I am only detecting based on the axis of the boxes since I am not actually rotating the boxes yet (ie, they are still axis aligned).

The collision detection itself seems to work fine, but something is wrong with the collision normal and penetration distance. Collision on two of the sides works fine, but very strange results occur when I approach and collide with the box from the other two sides. In my algorithm, the penetration distance is the smallest overlap value, and the normal is the axis this overlap occurs on. Am I doing something wrong here?

Thanks!


bool OBB3::Intersects(OBB3* in_volume, Vector3& out_collisionPoint, Vector3& out_collisionNormal, float& out_penetration)
{
// for a box there are 15 tests
// first check each axis of each box

// set to high value because we will be comparing
out_penetration=9999.0f;

// check all 15 axis
bool gap=FALSE;
if (SATAxisGap(in_volume, this->GetAxisX(), out_collisionNormal, out_penetration))
gap=TRUE;
if (SATAxisGap(in_volume, this->GetAxisY(), out_collisionNormal, out_penetration))
gap=TRUE;
if (SATAxisGap(in_volume, this->GetAxisZ(), out_collisionNormal, out_penetration))
gap=TRUE;
if (SATAxisGap(in_volume, in_volume->GetAxisX(), out_collisionNormal, out_penetration))
gap=TRUE;
if (SATAxisGap(in_volume, in_volume->GetAxisY(), out_collisionNormal, out_penetration))
gap=TRUE;
if (SATAxisGap(in_volume, in_volume->GetAxisZ(), out_collisionNormal, out_penetration))
gap=TRUE;
/* if (SATAxisGap(in_volume, this->GetAxisX().Cross(in_volume->GetAxisX()), out_collisionNormal, out_penetration))
gap=TRUE;
if (SATAxisGap(in_volume, this->GetAxisX().Cross(in_volume->GetAxisY()), out_collisionNormal, out_penetration))
gap=TRUE;
if (SATAxisGap(in_volume, this->GetAxisX().Cross(in_volume->GetAxisZ()), out_collisionNormal, out_penetration))
gap=TRUE;
if (SATAxisGap(in_volume, this->GetAxisY().Cross(in_volume->GetAxisX()), out_collisionNormal, out_penetration))
gap=TRUE;
if (SATAxisGap(in_volume, this->GetAxisY().Cross(in_volume->GetAxisY()), out_collisionNormal, out_penetration))
gap=TRUE;
if (SATAxisGap(in_volume, this->GetAxisY().Cross(in_volume->GetAxisZ()), out_collisionNormal, out_penetration))
gap=TRUE;
if (SATAxisGap(in_volume, this->GetAxisZ().Cross(in_volume->GetAxisX()), out_collisionNormal, out_penetration))
gap=TRUE;
if (SATAxisGap(in_volume, this->GetAxisZ().Cross(in_volume->GetAxisY()), out_collisionNormal, out_penetration))
gap=TRUE;
if (SATAxisGap(in_volume, this->GetAxisZ().Cross(in_volume->GetAxisZ()), out_collisionNormal, out_penetration))
gap=TRUE;*/


// no seperating axis found
if (gap)
return FALSE;
else
return TRUE;
}

bool OBB3::SATAxisGap(OBB3* in_volume, Vector3 in_axis, Vector3& out_collisionNormal, float& out_penetration)
{
// seperating axis therom
// |t.l| > ra+rb
//
// projection of radius onto axis
// r=e0|u0.n|+e1|u1.n|+e2|u2.n|
// where e=box extents, u=box axis and n=axis

// calculate t, ra and rb
Vector3 t=this->GetCenter()-in_volume->GetCenter();
float ra=this->GetExtent().x*abs(this->GetAxisX().Dot(in_axis))+
this->GetExtent().y*abs(this->GetAxisY().Dot(in_axis))+
this->GetExtent().z*abs(this->GetAxisZ().Dot(in_axis));
float rb=in_volume->GetExtent().x*abs(in_volume->GetAxisX().Dot(in_axis))+
in_volume->GetExtent().y*abs(in_volume->GetAxisY().Dot(in_axis))+
in_volume->GetExtent().z*abs(in_volume->GetAxisZ().Dot(in_axis));

// do intersection test
if (abs(t.Dot(in_axis)) > ra+rb)
return TRUE;
else
{
float overlap=ra+rb-abs(t.Dot(in_axis));
if (overlap < out_penetration)
{
out_penetration=overlap;
out_collisionNormal=in_axis;
}
return FALSE;
}
}


Share this post


Link to post
Share on other sites
Note that you can bail as soon as an axis test fails (gap = true in your code); there's no reason to continue with the test once this has occured.

As for the other problem, without going into too much detail here your axis test function needs to consider not only whether the boxes overlap but the relative positions of their projections onto the axis. The projections are one-dimensional; therefore they can be viewed as lying on a number line going from lower values (left) to higher (right). As such, it can be said that the projection of the first box is either 'left' or 'right' of the second box's projection. The penetration vector is then built from the direction, the side, and the penetration depth associated with the 'minimum' separating axis (the axis along which the projections have minimum overlap).

In the end, it mostly comes down to bookkeeping; tracking the relevant info from axis to axis, and then deriving contact information from it if an intersection is detected.

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
Note that you can bail as soon as an axis test fails (gap = true in your code); there's no reason to continue with the test once this has occured.

I thought that was only true if I was not trying to get the penetration depth and normal? How will I know which overlap is smallest if I exit on the first intersection?

Share this post


Link to post
Share on other sites
Quote:
Original post by Raeldor
I thought that was only true if I was not trying to get the penetration depth and normal? How will I know which overlap is smallest if I exit on the first intersection?
You don't exit on the first intersection, you exit on the first non-intersection. This is what the SAT is based on: if the objects are found to be disjoint along any axis, they are known to be non-intersecting and the test terminates. This means that the non-intersecting case (generally the most common case, depending somewhat on the broad phase) is reasonably efficient, often terminating after only a couple of axis tests.

You do have to test each axis in order to a) determine intersection conclusively, and b) extract contact information. These go together in that (of course) if there is no intersection, there is no contact information.

Let me know if that didn't clarify the issue. One thing that can be confusing is how you define your per-axis support function. Some people define it positively (it returns true in the presence of an overlap), while others define it negatively (it returns true in the absence of an overlap). The logic can certainly be a bit confusing.

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
The projections are one-dimensional; therefore they can be viewed as lying on a number line going from lower values (left) to higher (right). As such, it can be said that the projection of the first box is either 'left' or 'right' of the second box's projection.

That's true, but the cross product simply gives me the length of the projection. How do I find out the position? I am assuming I will somehow have to project a line segment rather than just a vector onto the axis?
Thanks

Share this post


Link to post
Share on other sites
Actually, thinking about this a bit more, if I took the axis and used it as the normal for a plane, and then took the position of the OBB as the position of the plane I would have myself a plane equation. I could then check which side of the plane the other box position vector is on.

Would this work? Is this how it's done?

Thanks again

Share this post


Link to post
Share on other sites
Hmm, this is kind of working, yet not working. It brings up a question. If you have two objects colliding, technically there are two collision normals, one for each object, but facing opposite directions. Since you are testing axis from each object, doesn't this mean you need to know which objects axis you are testing in order to return the correct normal for the first box (ie, reverse the normal if you are testing axis from the second box?

Share this post


Link to post
Share on other sites
Quote:
Original post by Raeldor
Hmm, this is kind of working, yet not working. It brings up a question. If you have two objects colliding, technically there are two collision normals, one for each object, but facing opposite directions. Since you are testing axis from each object, doesn't this mean you need to know which objects axis you are testing in order to return the correct normal for the first box (ie, reverse the normal if you are testing axis from the second box?
Yes, this last bit is correct, more or less; you do need to keep track of which axis is being tested, and on which 'side' of the box the intersection occured with respect to the projections onto that axis.

I don't know what references you're using, but oliii from this site has made some tutorials available that cover this. Dave Eberly also has code on his site, but while perfectly good, his implementation is a bit involved and may not be the best for studying purposes. I've implemented this also (several times), but I don't think I have any nice clean source code for it lying around at the moment (otherwise I'd post some working example code).

Share this post


Link to post
Share on other sites
Hello again,

Sorry to keep bugging you about this. I think I have this working now, but the idea of finding out which side of the box you are on didn't work too well. I think this is because the axis being tested can be pointing either away from or towards the first box. For example, you get a different collision normal if your axis being tested is (1,0,0) as opposed to (-1,0,0) which technically is the same axis. Am I missing something here? How can I be assured the collision normal is pointing in the correct direction using this method?

In then end I did an angle test against the vector between the two centers and the collision normal to force the normal to be towards the first box. My code now looks like...

bool OBB3::SATAxisGap(OBB3* in_volume, Vector3 in_axis, Vector3& out_collisionNormal, float& out_penetration)
{
// seperating axis therom
// |t.l| > ra+rb
//
// projection of radius onto axis
// r=e0|u0.n|+e1|u1.n|+e2|u2.n|
// where e=box extents, u=box axis and n=axis

// calculate t, ra and rb
Vector3 t=this->GetCenter()-in_volume->GetCenter();
float ra=this->GetExtent().x*abs(this->GetAxisX().Dot(in_axis))+
this->GetExtent().y*abs(this->GetAxisY().Dot(in_axis))+
this->GetExtent().z*abs(this->GetAxisZ().Dot(in_axis));
float rb=in_volume->GetExtent().x*abs(in_volume->GetAxisX().Dot(in_axis))+
in_volume->GetExtent().y*abs(in_volume->GetAxisY().Dot(in_axis))+
in_volume->GetExtent().z*abs(in_volume->GetAxisZ().Dot(in_axis));

// do intersection test
if (abs(t.Dot(in_axis)) > ra+rb)
return TRUE;
else
{
// find the distance to the second box
// then calculate which side of the plane
// float d=abs(in_axis.Dot(in_volume->GetCenter()));
// float planeDist=this->GetCenter().Dot(in_axis)+d;

// calculate overlap and save smallest overlap
float overlap=ra+rb-abs(t.Dot(in_axis));
if (overlap < out_penetration)
{
// penetration distance is the overlap amount
out_penetration=overlap;

// collision normal should point towards
// THIS object
if (t.Dot(in_axis) > 0)
// if (planeDist > 0)
out_collisionNormal=in_axis;
else
out_collisionNormal=in_axis*-1.0f;
}
return FALSE;
}
}


Share this post


Link to post
Share on other sites
What you're doing may be a perfectly reasonable solution (I'd have to look at it carefully to say for sure). I've always done it by tracking the 'side' information from test to test, but YMMV.

Another thing I've always done differently (for the non-boolean test) is to deal with the boxes as projected intervals (min and max) rather than using the 'sum of radii' method. One reason for this is that the per-axis test can then be factored out and used for object types other than OBBs.

Share this post


Link to post
Share on other sites
I apologize ahead for bringing this thread up again, however I am facing with similar function and I think it will fit the best into here.

much like Raeldor (I think) , I am failing to understand how the projected radiuses of the cross product vectors are found;
I didn't saw any response to it on this thread too.

According to 'jyk' and 'Christer Ericson' , the general formula is:
[color=#1C2837][font=CourierNew, monospace][size=2]r = e[sub]0[/sub]|A[sub]0[/sub].N| + e[sub]1[/sub]|A[sub]1[/sub].N| + e[sub]2[/sub]|A[sub]2[/sub].N|[/size][/font][/color]
[color=#1C2837][font=CourierNew, monospace][size=2]
[/size][/font][/color]
[font="Arial"][size="2"][color="#1C2837"]for the cross product of vectors uA0 and uA1, regarding the projected radius of a;[/color][/size][/font]
[font="Arial"][size="2"][color="#1C2837"]
[/color][/size][/font]
[font="Arial"][size="2"][color="#1C2837"]ra =[/color][/size][/font]
[font="Arial"][size="2"][color="#1C2837"] eA0 * |dot(uA0, N)| + [/color][/size][/font]
[font="Arial"][size="2"][color="#1C2837"] eA1 * |dot(uA1, N)| +[/color][/size][/font]
[font="Arial"][size="2"][color="#1C2837"] eA2 * |dot(uA2, N)|;[/color][/size][/font]
[font="Arial"][size="2"][color="#1C2837"]
[/color][/size][/font]
[font="Arial"][color="#1C2837"][size=4]I believe the first line can be removed since N has a 90º angle with uA0 and cos(90) = 0 ...[/size][/color][/font]
[font="Arial"][color="#1C2837"][size=4]
[/size][/color][/font]
[font="Arial"][color="#1C2837"][size=4]regarding the second line:[/size][/color][/font]
[font="Arial"][size="2"][color="#1C2837"]
[/color][/size][/font]
[font="Arial"][size="2"][color="#1C2837"]N is (right handed cross product):[/color][/size][/font]
[font="Arial"][size="2"][color="#1C2837"]
N.x = (uA0.y*uA1.z) - (uA0.z*uA1.y);
N.y = (uA0.z*uA1.x) - (uA0.x*uA1.z);
N.z = (uA0.x*uA1.y) - (uA0.y*uA1.z);

so further expanding the second line (ignoring the third one, for now)
eA1 * dot(uA1, N) = eA1 * (
[size="2"]uA1.x * (uA0.y*uA1.z) - (uA0.z*uA1.y) +[/size]
[size="2"] uA1.y * [/size](uA0.z*uA1.x) - (uA0.x*uA1.z) +
uA1.z * (uA0.x*uA1.y) - (uA0.y*uA1.z)
);

To be honest, I even opened it further on, on a paper; I won't do it here though, since I didn't end up nowhere.
I do know in the table it listed that: ra = eA1 * |r20| + eA2*|r10|
hence the expanded value of dot(uA1, cross(uA0, uB0)) should be equal to r20.
however, in r20, we actually have dot(uA2, uB0);

I believe i'm missing something, but I can't find a direct connection between the 2 terms.
What am I missing then?

p.s.
I apologize for my notation in here; I'm not familiar with any better way to do so, not in a forum post anyway.[/color][/size][/font]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this