OBB and SAT Question
Author
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!
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.
Author
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!
Author
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]
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]
Quote:Original post by RaeldorThe 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.
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?
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.
Author
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
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
Not speaking for Christer here, but:
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.
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 beIt might clear things up a bit to look at the equation for finding the projected radius of an OBB onto an arbitrary axis:
rB=eB.L
r = e0|A0.N| + e1|A1.N| + e2|A2.N|r = dot(e,abs(N))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.
Quote:Original post by RaeldorI 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
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?
|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.
Author
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]
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]
Author
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!
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; } }This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
