//my oriented b-box structure
typedef struct
{
vector2f Pos; //Box centre position
vector2f Axis[2]; //Axis vectors (normalised)
vector2f Ext; //Box half extents
} obb2f;
//Intersection function
bool IntOBBOBB2D(vector2f I[4], const obb2f* B1, const obb2f* B2)
{
const vector2f* Axis[4] = {B1->Axis, B1->Axis + 1, B2->Axis, B2->Axis + 1};
vector2f Norm, dL;
float min1, max1;
float min2, max2;
float r, r1, r2, p1, p2, d = float_max;
uint J;
//The algorithm successively projects the two boxes onto each other's axes
// and performs overlapping tests on those axes. The four potential separating
// axes for the boxes B1 and B2 are: B1->Axis[0], B1->Axis[1], B2->Axis[0],
// and B2->Axis[1].
for (J = 0; J < 4; J++)
{
//Project B1 onto the current axis
p1 = Axis[J]->X * B1->Pos.X + Axis[J]->Y * B1->Pos.Y; //Projected box centre on the axis line (2D dot product)
r1 = fabsf(Axis[J]->X * B1->Axis[0].X + Axis[J]->Y * B1->Axis[0].Y) * B1->Ext.X; //Projected half-span of the box extent X
r1 += fabsf(Axis[J]->X * B1->Axis[1].X + Axis[J]->Y * B1->Axis[1].Y) * B1->Ext.Y; //Projected half-span of the box extent Y
min1 = p1 - r1; //Minimum projected box extent
max1 = p1 + r1; //Maximum projected box extent
//Project B2 onto the current axis
p2 = Axis[J]->X * B2->Pos.X + Axis[J]->Y * B2->Pos.Y;
r2 = fabsf(Axis[J]->X * B2->Axis[0].X + Axis[J]->Y * B2->Axis[0].Y) * B2->Ext.X;
r2 += fabsf(Axis[J]->X * B2->Axis[1].X + Axis[J]->Y * B2->Axis[1].Y) * B2->Ext.Y;
min2 = p2 - r2;
max2 = p2 + r2;
//Find the overlap length on this axis. If the boxes are separate,
// the overlap length will be negative and the test fails.
r = min(max2, max1) - max(min2, min1);
if (r < 0.0f) {return false;}
//Save the smallest penetration depth found and the direction axis of the penetration
if (d > r)
{
d = r;
Norm.X = Axis[J]->X;
Norm.Y = Axis[J]->Y;
}
}
//Distance between two box centres
dL.X = B2->Pos.X - B1->Pos.X;
dL.Y = B2->Pos.Y - B1->Pos.Y;
//Make sure normal points to box B1
if (dL.X * Norm.X + dL.Y * Norm.Y > 0.0f)
{
Norm.X = -Norm.X;
Norm.Y = -Norm.Y;
}
/*
In the final implementation I will plan to return the penetration depth and
the normal vector as well. But for now, I'd like to focus on computing
the four intersection points. I'm pretty much stuck here...
*/
I[0].X = ???;
I[0].Y = ???;
I[1].X = ???;
I[1].Y = ???;
I[2].X = ???;
I[2].Y = ???;
I[3].X = ???;
I[3].Y = ???;
return true;
}
Finding OBB - OBB Intersection Points in 2D
Author
I'm writing a 2D car sim game with collisions, and my current research is focused on OBB - OBB intersection tests. I found oliii's posts (just one of many) extremely helpful - if you're still around, cheers oliii! I have been doing some additional reading on this topic, ranging from papers by David Baraff, David Eberly, various game physics books... etc. I think I have the SAT basics understood, and I have been toying around with code based on oliii's implementation.
However, in addition to simple overlap tests, or finding the box interpenetration length and its direction, I would also like to compute the intersection points of the two boxes. I realise using intersection points directly is not the most robust way of doing collision handling, particularly when interpenetration is deep. But for the moment I would like to compute the intersection points purely for the learning experience. I have to admit, this the bit that is doing my head in.
My initial idea is to use the computed overlap range for each axis projection, and somehow construct the points for the 2D overlapping area. Like with many things, the Devil is in the details, and need bit of help with this. Is there specific algorithm for this?
I think oliii's tutorials and code cover computing intersection info as well, so you might look around a bit more and see if you can find those particular tutorials.
Meanwhile, what are the four intersection points supposed to represent? Why four of them?
Meanwhile, what are the four intersection points supposed to represent? Why four of them?
There's probably an easier way to compute the overlapping area. If you look at clipping, you can basically get the polygon that is the intersection of the two objects (as long as they are convex). It's actually a good exercise in itself, since it can be quite useful (I use it for 3D face-face collisions).
The SAT in itself is a bit limited when it comes to finding the actual intersection area. What it can return is the overlap depth and direction. But for the actual overlapping area, you'd have to do something else.
The SAT in itself is a bit limited when it comes to finding the actual intersection area. What it can return is the overlap depth and direction. But for the actual overlapping area, you'd have to do something else.
Quote:Original post by oliii
The SAT in itself is a bit limited when it comes to finding the actual intersection area. What it can return is the overlap depth and direction. But for the actual overlapping area, you'd have to do something else.
In the case of predicting the first time of contact (using SAT), you can determine which "features" are in contact. For example, you might know that the vertex of one OBB is just touching an edge of the other OBB. This information allows you to reduce the dimension by 1 for the intersection test. And you know that there *must* be an intersection (generic find-intersection queries must be prepared to determine that there is no intersection).
Author
Thanks for the replies!
My assumption is that you can get up to 4 intersection points for 2D box overlaps, is that not?
Ah yes, the SH clipping algorithm - oddly enough that did not occur occur to me!
If I were to go with the clipping method, the sanest way of doing this is by transforming one of the OBB to an AABB type and clip the other against it?
Something like:
1. Transform OBB1 to an AABB
2. Transform OBB2 by the same amount so it's relative to the AABB
3. Do the SAT job, exit if not over lapping
4. Find the corners of OBB2 and clip its edge lines against the AABB
Quote:Meanwhile, what are the four intersection points supposed to represent? Why four of them?
My assumption is that you can get up to 4 intersection points for 2D box overlaps, is that not?
Quote:What it can return is the overlap depth and direction. But for the actual overlapping area, you'd have to do something else.
Ah yes, the SH clipping algorithm - oddly enough that did not occur occur to me!
If I were to go with the clipping method, the sanest way of doing this is by transforming one of the OBB to an AABB type and clip the other against it?
Something like:
1. Transform OBB1 to an AABB
2. Transform OBB2 by the same amount so it's relative to the AABB
3. Do the SAT job, exit if not over lapping
4. Find the corners of OBB2 and clip its edge lines against the AABB
Quote:Original post by Tachikoma
If I were to go with the clipping method, the sanest way of doing this is by transforming one of the OBB to an AABB type and clip the other against it?
No necessarily. I'd just clip without transform, it's not that much harder.
Author
Cool. After playing around I decided to drop the clipping concept as it was an overkill. But it was a good exercise, and I might use it somewhere else one day.
I have a couple more questions which is not exactly related to the original questions (I did not want to start another thread.)
I have implemented my 2D collision handler, which calculates the contact or impulse forces between the dynamic body (the car's bounding box) and immovable objects, such as a road barrier (bunch of lines, really). I'm satisfied with the results for the most part, but it is still not perfect. Two questions:
1. I need to deal with a tricky situation while the car scrapes flat along the road barrier. I can move the car back and forth, when the bounding box is flat against the barrier, but I can not turn away from the barrier and get back onto the centre of the road. The scenario is similar to having a cube block flat on the table and you can't rotate it because the table contact points at the cube corners is pushing back. Does that make sense?
From a physics perspective, one could say that is a desirable reaction, as it prevents barrier penetration due to angular motion. But from a gaming perspective this is not always ideal, because the player can't turn back onto the road! Bit of a dilemma really, as both behaviours are needed, so I was hoping to get some ideas on best way of dealing with this. I have provided some sample code that handles with car-barrier collisions.
2. I need some suggestions on resolving interpenetrations neatly. At the moment I'm just using the penetration depth to push the car back until there is no intersection (this hack is also in the code below). In case you're wondering, I'm also using very basic sweep tests somewhere else, which gets activated only when the car's velocity goes above a certain threshold. In that case, I test whether the car over stepped the barrier line; and if so, I project the car's OBB on the direction vector and see what position is the first point of contact along that trajectory (relative to previous car location). Then I activate intersection tests at that computed position and pass the results into the code below. Is this a sound strategy?
I have a couple more questions which is not exactly related to the original questions (I did not want to start another thread.)
I have implemented my 2D collision handler, which calculates the contact or impulse forces between the dynamic body (the car's bounding box) and immovable objects, such as a road barrier (bunch of lines, really). I'm satisfied with the results for the most part, but it is still not perfect. Two questions:
1. I need to deal with a tricky situation while the car scrapes flat along the road barrier. I can move the car back and forth, when the bounding box is flat against the barrier, but I can not turn away from the barrier and get back onto the centre of the road. The scenario is similar to having a cube block flat on the table and you can't rotate it because the table contact points at the cube corners is pushing back. Does that make sense?
From a physics perspective, one could say that is a desirable reaction, as it prevents barrier penetration due to angular motion. But from a gaming perspective this is not always ideal, because the player can't turn back onto the road! Bit of a dilemma really, as both behaviours are needed, so I was hoping to get some ideas on best way of dealing with this. I have provided some sample code that handles with car-barrier collisions.
2. I need some suggestions on resolving interpenetrations neatly. At the moment I'm just using the penetration depth to push the car back until there is no intersection (this hack is also in the code below). In case you're wondering, I'm also using very basic sweep tests somewhere else, which gets activated only when the car's velocity goes above a certain threshold. In that case, I test whether the car over stepped the barrier line; and if so, I project the car's OBB on the direction vector and see what position is the first point of contact along that trajectory (relative to previous car location). Then I activate intersection tests at that computed position and pass the results into the code below. Is this a sound strategy?
//Car : Vehicle struct//P : Contact point//N : Contact normal (N->t also holds penetration depth)//dt : Time stepvoid CarAddContactForce(CarRec* Car, vector2f* P, vector3f* N, float dt) { vector2f VT, d; float jl, ja, jd, m, NdotV, NdotVT, DxN; //Distance of collision point relative to the car centre d.X = P->X - Car->Pos.X; d.Y = P->Y - Car->Pos.Y; //Find the tangential velocity vector in local space // (along the X axis), then tranform it into world space m = sqrtf(sqr(d.X) + sqr(d.Y)) * Car->AngVel; VT.X = m * Car->AngCos; // X = m * cos(a) - 0 * sin(a) VT.Y = m * Car->AngSin; // Y = m * sin(a) + 0 * cos(a) //Find the dot product between velocities and normal. Bodies are colliding // when NdotV < 0, resting when NdotV == 0, and separating when NdotV > 0. NdotV = N->X * Car->Vel.X + N->Y * Car->Vel.Y; NdotVT = N->X * VT.X + N->Y * VT.Y; //Exit if both the linear and angular motion is separating if ((NdotV > CAR_REST_VEL) && (NdotVT > CAR_REST_ANGVEL)) {return;} //Calculate acceleration to compensate for interpenetration m = N->t / sqr(dt); //Find 2D cross product between normal and distance vector, // and the denominator used by the impulse equations DxN = d.X * N->Y - N->X * d.Y; jd = 1.0f / (Car->rcp_Mass + sqr(DxN) * Car->rcp_Iner); //Calculate the linear and angular motion impulses if colliding, otherwise // handle "at rest" conditions and only compensate for interpenetration. jl = (NdotV < -CAR_REST_VEL) ? -(1.0f + CAR_ebl) * NdotV * jd + m : m; ja = (NdotVT < -CAR_REST_ANGVEL) ? -(1.0f + CAR_eba) * -fabs(NdotV) * jd + m : m; //Accumulate contact forces and moments Car->FContact.X += jl * N->X; Car->FContact.Y += jl * N->Y; Car->MContact += ja * DxN; Car->FCount++; Car->MCount++; Car->Coll = true; }This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
