OBB vs. OBB Collision Problem
Hello,
I am attempting to implement a new form of 2D collision detection in my latest game using Oriented Bounding Boxes, but I seem to have run into a dead end.
Detecting if a collision between two 2D OBBs occurs is easy enough; and this is how I do it: A vector is formed that spans the distance between the two objects' centers, forming an arbitrary axis. For each of the two OBBs, the half-length and half-width (these may not necessarily be equal) are projected onto this axis. The distance between the two centers (ie, the length of the vector forming the arbitrary axis) is measured, and if this distance is less than the sum of the length of the projected half-vectors, then a collision occurs.
The problem I am having is how to calculate the position of the collision itself, ie, where the objects are calculated to intersect. This position is vital to determine where, for example, to draw a cascade of sparks if two metal boxes collide, or whatever you like.
I would appreciate any assistance; I have been stuck on this for a little while now. Thank you!
Have you tested your intersection algorithm carefully, using boxes of various dimensions and orientations intersecting in various configurations? (I ask because it seems your intent is to implement the separating axis test, but what you describe is not in fact the SAT.)
Anyway, deriving a contact manifold using the SAT is a little tricky, but quite possible. In essence, it involves identifying the features of the two objects (boxes in this case) that project maximally (or minimally, as the case may be) onto the axis that is determined to be the last axis along which the objects intersect (if you're performing a swept test), or that is parallel to the minimum translational vector (if you're resolving a static collision). Once you've identified these features, you can clip them against one another to yield the contact manifold.
The first step though is to make sure that your collision detection algorithm and implementation are correct. It may very well be, but based on your description I'm a bit skeptical (or maybe I'm just misunderstanding).
Anyway, deriving a contact manifold using the SAT is a little tricky, but quite possible. In essence, it involves identifying the features of the two objects (boxes in this case) that project maximally (or minimally, as the case may be) onto the axis that is determined to be the last axis along which the objects intersect (if you're performing a swept test), or that is parallel to the minimum translational vector (if you're resolving a static collision). Once you've identified these features, you can clip them against one another to yield the contact manifold.
The first step though is to make sure that your collision detection algorithm and implementation are correct. It may very well be, but based on your description I'm a bit skeptical (or maybe I'm just misunderstanding).
Quote: Have you tested your intersection algorithm carefully, using boxes of various dimensions and orientations intersecting in various configurations? (I ask because it seems your intent is to implement the separating axis test, but what you describe is not in fact the SAT.)
Yes, this technique does seem to work well. In response to your other statement:
Quote:The first step though is to make sure that your collision detection algorithm and implementation are correct. It may very well be, but based on your description I'm a bit skeptical (or maybe I'm just misunderstanding).
I forgot to mention how the algorithm decides which half-vectors to use to project, if this makes any difference. A normal to the new axis is found, and then those half-vectors whose dot product to this axis are greater than zero are projected. You can see this in action here. The applet named "Figure 2" shows exactly the method I am using to project the half-vectors of a single box. In this case, the arbitrary axis formed is the equivalent of the center-joining line.
As for this:
Quote:Anyway, deriving a contact manifold using the SAT is a little tricky, but quite possible. In essence, it involves identifying the features of the two objects (boxes in this case) that project maximally (or minimally, as the case may be) onto the axis that is determined to be the last axis along which the objects intersect (if you're performing a swept test), or that is parallel to the minimum translational vector (if you're resolving a static collision). Once you've identified these features, you can clip them against one another to yield the contact manifold.
I'm afraid you've completely lost me there! Any diagrams or links would be helpful, if you have any on hand. Also, if there are easier ways of testing for OBB collision, I would certainly be open to ideas.
Assuming your collision detection does work, and referring to N.tutorials, you can see how they compute the MTD (minimum translation distance), if you look at the example with the triangle and the box.
When you drag the box so it intersects the triangle, along the triangle hypotenuse, you can see that the MTD will be along the normal of the hypotenuse.
That tells you which way the collision occurs, or which way to push, and by how much to push the box so it stops intersecting.
That MTD vector can also be used to work out the precise contact points between the objects.
first step is to find the 'support vertices' of the two objects. Again taking the box hitting the triangle hypotenuse, the support vertices of the box will be the bottom-left corner of the box, (the vertex on the box that when dot-product with the MTD, will give the minimum value). The support vertices of the triangle will be the two vertices of the hypotenuse themselves (the vertices of the triangle that when dot producted with the MTD, will give you the maximum value).
So now you have a vertex, hitting an edge (two vertices for the triangle, only one for the box). Then it's quite easy, the contact point is the corner of the box itself, and the contact point on the triangle is corner of the box projected on the hypotenuse.
In case you have two support points for each objects (the axis aligned boxes example), then you will need to sort the support points by computing their dot products against the vector perpendicular to the MTD (vector(-mtd.y, mtd.x)).
You will have 4 points assigned 4 values. Then you will have two pairs of contact points. The two points which values are sorted in the middle. And their pairing contact on the other object is the projection on that point against the opposite supporting edge.
inevitable plug.
NOTE : for the edge-edge case, I've used a different method. I computed the contact pairs by using teh point on the edge closest to the support points. Then I calculated the distance for each contact pairs, and took the two smallest.
When you drag the box so it intersects the triangle, along the triangle hypotenuse, you can see that the MTD will be along the normal of the hypotenuse.
That tells you which way the collision occurs, or which way to push, and by how much to push the box so it stops intersecting.
That MTD vector can also be used to work out the precise contact points between the objects.
first step is to find the 'support vertices' of the two objects. Again taking the box hitting the triangle hypotenuse, the support vertices of the box will be the bottom-left corner of the box, (the vertex on the box that when dot-product with the MTD, will give the minimum value). The support vertices of the triangle will be the two vertices of the hypotenuse themselves (the vertices of the triangle that when dot producted with the MTD, will give you the maximum value).
So now you have a vertex, hitting an edge (two vertices for the triangle, only one for the box). Then it's quite easy, the contact point is the corner of the box itself, and the contact point on the triangle is corner of the box projected on the hypotenuse.
In case you have two support points for each objects (the axis aligned boxes example), then you will need to sort the support points by computing their dot products against the vector perpendicular to the MTD (vector(-mtd.y, mtd.x)).
You will have 4 points assigned 4 values. Then you will have two pairs of contact points. The two points which values are sorted in the middle. And their pairing contact on the other object is the projection on that point against the opposite supporting edge.
inevitable plug.
NOTE : for the edge-edge case, I've used a different method. I computed the contact pairs by using teh point on the edge closest to the support points. Then I calculated the distance for each contact pairs, and took the two smallest.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement