Sign in to follow this  
jonathantompson

Help with OBB Collision Detection

Recommended Posts

I am trying to implement an OBB bounding volume hierarchy as in: S. Gottschalk et. al, "OBBTree: A Hierarchical Structure for Rapid Interference Detection". I have successfully generated the OBB Tree from a polygon soup, but I am having trouble testing OBB nodes for collision. My first question: 1. My collision code is reporting incorrect collisions. I think the issue stems from the fact that in my OBB code each OBB node has a rotation matrix and translation vector to describe orientation and position within the model frame, and then that model frame itself has a rotation and translation within the world frame. In Gottschalk's code, there is only one Rotation and one Translation for each OBB. Please let me know if any of the following is incorrect: My OBB tree is represented by something like this: class obbox { vector3 boxCenter; // Box center in model frame vector3 boxDimension; // Box half lengths matrix3x3 orientMat; // 3 columns are eigenvectors of // covariance matrix. }; But the OBB Tree is part of a rigid body object that has it's own rotation and translation vector: class rbobject { vector3 Trans; // Translation vector3 Rot; // Rotation } I have been using the detection code in Christer Ericson's book, Real-Time Collision Detection (page 103-105): http://books.google.com/books?id=WGpL6Sk9qNAC&lpg=PA101&ots=Pl4MjF4ciO&dq=Real-Time%20Collision%20Detection%20oriented%20bounding%20boxes&pg=PA101#v=onepage&q=Real-Time%20Collision%20Detection%20oriented%20bounding%20boxes&f=false In this, he has one rotation matrix and one translation vector to describe each OBB element. My confusion stems from the fact that I have two rotations and two translations for each OBB node. Instead I use the code below to find the R and T values in Ericson's code: matrix3x3 R_a = rbobject_a.Rot * obbox_a.orientMat; matrix3x3 R_b = rbobject_b.Rot * obbox_b.orientMat; // Matrix describing B in A's coordinate frame // A^-1 * B = A' * B for orthonormal A matrix3x3 R = Transpose(R_a) * R_b; vector3 t_a_world = (rbobject_a.Rot * obbox_a.boxCenter) + rbobject_a.Trans; vector3 t_b_world = (rbobject_b.Rot * obbox_b.boxCenter) + rbobject_b.Trans; vector3 t_a_b_world = t_b_world - t_a_world; // Bring translation vector into a's coordinate frame vector3 t = Transpose(R_a) * t_a_b_world ; Then the rest of the code is the same as in the text book. Is this correct? I can't see anything wrong with the matrix / vector manipulations, but I am getting incorrect collisions reported. My second question: 2. Can you test for leaf node collisions by using an OBB of close to zero thickness and which lies in the plane of the leaf triangle? I can't see any issue with this approach. Maybe the OBB collision test can be simplified if one of the lengths is known to be zero thickness (as described in Gottschalk's thesis), but the detection code should still work. Right? Thanks, Jonathan

Share this post


Link to post
Share on other sites
voguemaster    183
Hi,

Here are a few points to consider:

Assuming your matrix multiplication code is correct, what you're effectively doing is to transform an OBB node from rigid body A and another OBB node from rigid body B to a common coord system, in this case world coords.

Even if your calculations are correct, this may lead to problems because of floating point accuracy problems and error accumulation. If your objects are far from the origin (and they dont necessarily have to be very far), the representation of the OBBs will be inexact, leading to problems in detection.

Ideally, what you should do in this case, IMO is the following. I'm assuming you
have 2 rigid bodies (A and B) and that each has an OBB tree (BVH). Each OBB in a BVH has its center and orientation relative to its rigid body. Then:

1. Take an OBB from B and transform it to A's coordinate system. Now the common coord system is A's. The OBB from B is relative to A and the entire BVH of A is (naturally) relative to A.

2. Continue the algorithm as explained in Ericson's book. That is, given two OBBs in a common coord system, transform one to the other's coord system and perform the SAT test. So in this example, we may transform the OBB that came from B (now in rigid body's A coord system) to the local coord system of an OBB in A's BVH.
(that means that the OBB from B has been transformed to some orientation R and the OBB from A is in its local coord system, its orientation are e1, e2, e3).


In pseudo-code this might look something like this:

// compute transform from rigid body B to A coord system
Matrix R_a = rbobject.Rot
Matrix R_b = rbobject.Rot
Matrix R_b2a = Trans(R_a) * R_b
Vector t = (T_a - T_b)
Vector T_b2a = Vector(Dot(t, R_a1), Dot(t, R_a2), Dot(t, R_a3)) // dot t with each vector of the orientation matrix of rigid body A

// transform OBB from rigid body B to rigid body A coord system
obbox_b.orientMat *= R_b2a;
obbox_b.boxCenter = (R_b2a * obbox.boxCenter) + T_b2a; // since OBB from B has translation relative to B, we have to rotate its center vector to A's coord system and add the general transform from rigid body B to A

// now we have OBB from B in rigid body A coord system and an OBB from A, naturally in rigid body A's coord system, continue normally like Christer's code.


One thing to note is that the first part, computing the transform from rigid body B to A's coord system, remains constant for the entire calculation so it also saves computation time.


Now for debugging -

1. Try to test your code with simple cases first. Example: use only one OBB with known "easy" orientation per object. Test if the code works.

2. Orient the OBBs in both objects differently to see if the algorithm still works.

3. Once you have it working for one OBB, its trivial to scale it to the entire BVH.

4. If you can, try to have a visualization of the OBBs. Its quite easy to create a simple wireframe box that represents an OBB. When it isnt intersecting, it will be rendered in white. When intersecting another OBB, you could render it in red.


I hope it helps. Let us know how it works out.

Share this post


Link to post
Share on other sites
voguemaster    183
Hi,

Here are a few points to consider:

Assuming your matrix multiplication code is correct, what you're effectively doing is to transform an OBB node from rigid body A and another OBB node from rigid body B to a common coord system, in this case world coords.

Even if your calculations are correct, this may lead to problems because of floating point accuracy problems and error accumulation. If your objects are far from the origin (and they dont necessarily have to be very far), the representation of the OBBs will be inexact, leading to problems in detection.

Ideally, what you should do in this case, IMO is the following. I'm assuming you
have 2 rigid bodies (A and B) and that each has an OBB tree (BVH). Each OBB in a BVH has its center and orientation relative to its rigid body. Then:

1. Take an OBB from B and transform it to A's coordinate system. Now the common coord system is A's. The OBB from B is relative to A and the entire BVH of A is (naturally) relative to A.

2. Continue the algorithm as explained in Ericson's book. That is, given two OBBs in a common coord system, transform one to the other's coord system and perform the SAT test. So in this example, we may transform the OBB that came from B (now in rigid body's A coord system) to the local coord system of an OBB in A's BVH.
(that means that the OBB from B has been transformed to some orientation R and the OBB from A is in its local coord system, its orientation are e1, e2, e3).


In pseudo-code this might look something like this:

// compute transform from rigid body B to A coord system
Matrix R_a = rbobject.Rot
Matrix R_b = rbobject.Rot
Matrix R_b2a = Trans(R_a) * R_b
Vector t = (T_a - T_b)
Vector T_b2a = Vector(Dot(t, R_a1), Dot(t, R_a2), Dot(t, R_a3)) // dot t with each vector of the orientation matrix of rigid body A

// transform OBB from rigid body B to rigid body A coord system
obbox_b.orientMat *= R_b2a;
obbox_b.boxCenter = (R_b2a * obbox.boxCenter) + T_b2a; // since OBB from B has translation relative to B, we have to rotate its center vector to A's coord system and add the general transform from rigid body B to A

// now we have OBB from B in rigid body A coord system and an OBB from A, naturally in rigid body A's coord system, continue normally like Christer's code.


One thing to note is that the first part, computing the transform from rigid body B to A's coord system, remains constant for the entire calculation so it also saves computation time.


Now for debugging -

1. Try to test your code with simple cases first. Example: use only one OBB with known "easy" orientation per object. Test if the code works.

2. Orient the OBBs in both objects differently to see if the algorithm still works.

3. Once you have it working for one OBB, its trivial to scale it to the entire BVH.

4. If you can, try to have a visualization of the OBBs. Its quite easy to create a simple wireframe box that represents an OBB. When it isnt intersecting, it will be rendered in white. When intersecting another OBB, you could render it in red.


I hope it helps. Let us know how it works out.

Share this post


Link to post
Share on other sites
voguemaster    183
Hi,

Here are a few points to consider:

Assuming your matrix multiplication code is correct, what you're effectively doing is to transform an OBB node from rigid body A and another OBB node from rigid body B to a common coord system, in this case world coords.

Even if your calculations are correct, this may lead to problems because of floating point accuracy problems and error accumulation. If your objects are far from the origin (and they dont necessarily have to be very far), the representation of the OBBs will be inexact, leading to problems in detection.

Ideally, what you should do in this case, IMO is the following. I'm assuming you
have 2 rigid bodies (A and B) and that each has an OBB tree (BVH). Each OBB in a BVH has its center and orientation relative to its rigid body. Then:

1. Take an OBB from B and transform it to A's coordinate system. Now the common coord system is A's. The OBB from B is relative to A and the entire BVH of A is (naturally) relative to A.

2. Continue the algorithm as explained in Ericson's book. That is, given two OBBs in a common coord system, transform one to the other's coord system and perform the SAT test. So in this example, we may transform the OBB that came from B (now in rigid body's A coord system) to the local coord system of an OBB in A's BVH.
(that means that the OBB from B has been transformed to some orientation R and the OBB from A is in its local coord system, its orientation are e1, e2, e3).


In pseudo-code this might look something like this:

// compute transform from rigid body B to A coord system
Matrix R_a = rbobject.Rot
Matrix R_b = rbobject.Rot
Matrix R_b2a = Trans(R_a) * R_b
Vector t = (T_a - T_b)
Vector T_b2a = Vector(Dot(t, R_a1), Dot(t, R_a2), Dot(t, R_a3)) // dot t with each vector of the orientation matrix of rigid body A

// transform OBB from rigid body B to rigid body A coord system
obbox_b.orientMat *= R_b2a;
obbox_b.boxCenter = (R_b2a * obbox.boxCenter) + T_b2a; // since OBB from B has translation relative to B, we have to rotate its center vector to A's coord system and add the general transform from rigid body B to A

// now we have OBB from B in rigid body A coord system and an OBB from A, naturally in rigid body A's coord system, continue normally like Christer's code.


One thing to note is that the first part, computing the transform from rigid body B to A's coord system, remains constant for the entire calculation so it also saves computation time.


Now for debugging -

1. Try to test your code with simple cases first. Example: use only one OBB with known "easy" orientation per object. Test if the code works.

2. Orient the OBBs in both objects differently to see if the algorithm still works.

3. Once you have it working for one OBB, its trivial to scale it to the entire BVH.

4. If you can, try to have a visualization of the OBBs. Its quite easy to create a simple wireframe box that represents an OBB. When it isnt intersecting, it will be rendered in white. When intersecting another OBB, you could render it in red.

Hope it helps.

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