Jump to content
  • Advertisement
Sign in to follow this  
Raeldor

OBB and SAT Question

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

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
Advertisement
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
Sign in to follow this  

  • 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!