• Advertisement
Sign in to follow this  

Point of collision

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

ok, so i have these 2d boxes boxes wich have different widths heights and rotations (2d obbs). ive up to this point used the separation axis theorem for these kind of things, but now i hit an obstacle. i need to get the point of collision this is going to be used in a rigid body physics part of my 2d game engine so ill need the calculations to be fast ive looked at Box2D wich ive gotten redirected to. but i find the source poorly documented leading to a copy paste scenario (upp til now ive been able to understand everything ive put into the engine. i dont want to change that) so anyone have code wich is documented or some articles wich explain how to do this?

Share this post


Link to post
Share on other sites
Advertisement
for me, it goes like this :

the static SAT should give you the MTD, The minimum translation distance. or in the form of a normal of collision and intersection depth.

- Take the normal of collision or MTD, and find the support points along that vector.

in 2D, you will either get a vertex, or two points forming an edge.


int Poly::GetSupportPoints(const Vector& Dir, Vector* support)
{
int count = 0;
const float threshold = 1.0E-8;
float mind;
for(int i = 0; i < m_NumVerts; i ++)
{
float d = m_Vert.DotProduct(Dir);
if(i == 0 || d < mind)
{
mind = d;
}
}

for(int i = 0; i < m_NumVerts; i ++)
{
float d = m_Vert.DotProduct(Dir);
if(d < (mind + threshold))
{
support[count] = m_Vert;
count++;
if (count >= 2) return count;
}
}
return count;
}

you may need a bit more work than that if you plan on having colinear edges. But for simple cases, that will do.




Now, with those points of collision you have several scenarios.

1) vertex on poly A - edge on Poly B.
2) edge on poly A - vertex on Poly B.
3) edge on poly A - edge on Poly B.

you should never get a vertex-vertex collision, but if you do, the vertices themselves are the contact points, obviously.

vertex-edge type is easy. one of the contact point is the vertex, the other is the projection of that vertex onto the edge.

edge-edge is not that hard. you will have two pairs of contact point. In the case of an edge-edge collision, both edges wil be parallel. If you trace a line

along the edge direction, out of the four vertices, you will see that you need to take the two vertices that are the 'innermost' and compute their

corresponding contact on the other object by projecting the vertex onto the other object's edge.



Vector Edge_GetClosestPoint(const Vector& P, const Vector& A, const Vector& B)
{
Vector AB = B - A;
Vector AP = P - A;
float ab_ab = AB.DotProduct(AB);
float ab_ap = AP.DotProduct(AB);
float t = ab_ap / ab_ab;
t = (t < 0.0f)? 0.0f : (t > 1.0f)? 1.0f : t;

return A + t * AB;
}

int Poly::GetContactPoints(Vector* supportA, int numA,
Vector* supportB, int numB,
VectorPair* contacts)
{
switch(numA + numB)
{
// error!
default:
case 0;
case 1:
return 0;
case 2:
return Poly::GetContactPoints_VertexVertex(supportA[0], supportB[0], contacts);
case 3:
if(numA > numB)
return Poly::GetContactPoints_EdgeVertex(supportA, supportB[0], contacts);
else
return Poly::GetContactPoints_VertexEdge(supportA[0], supportB, contacts);
case 4:
return Poly::GetContactPoints_EdgeEdge(supportA, supportB, contacts);
}
}

int Poly::GetContactPoints_VertexVertex(const Vector& PA,
const Vector& PB,
VectorPair* contacts)
{
contacts[0].ContactA = PA;
contacts[0].ContactB = PB;
return 1;
}

int Poly::GetContactPoints_VertexEdge(const Vector& PA,
const Vector* edgeB,
VectorPair* contacts)
{
contacts[0].ContactA = PA;
contacts[0].ContactB = Edge_GetClosestPoint(PA, edgeB[0], edgeB[1]);
return 1;
}

int Poly::GetContactPoints_EdgeVertex(const Vector* edgeA,
const Vector& PB,
VectorPair* contacts)
{
contacts[0].ContactA = Edge_GetClosestPoint(PB, edgeA[0], edgeA[1]);
contacts[0].ContactB = PB;
return 1;

}


struct Vsort
{
Vector P;
float d;
int bd;

Vsort(const Vector& Pos, const Vector& Dir, int body)
{
P = Pos;
d = Pos.DotProduct(Dir);
bd = body;
}

static in Compare(const void* v0, const void* v1)
{
Vsort* V0 = (Vsort*) v0;
Vsort* V1 = (Vsort*) v1;
return (V0->d > V1->d)? 1 : -1;
}
};

int Poly::GetContactPoints_EdgeEdge(const Vector* edgeA,
const Vector* edgeB,
VectorPair* contacts)
{

// direction of sorting
Vector Dir = edgeA[1] - edgeA[0];

// Store the vertex information
Vsort V[4] = { Vsort(edgeA[0], Dir, 0),
Vsort(edgeA[1], Dir, 0),
Vsort(edgeB[0], Dir, 1),
Vsort(edgeB[1], Dir, 1), };


// sort the points along the colinear edge direction.
// take the two middle points as the contacts
// sort the vertices by 'd' value
qsort(V, 4, sizeof(V[0]), Vsort::Compare);

for(i = 0; i < 2; i ++)
{
// Vertex belonged to body A
if(V[1+i].bd == 0)
{
contacts.ContactA = V[1+i].P;
contacts.ContactB = Edge_GetClosestPoint(V[1+i].P, edgeB[0], edgeB[1]);
}

// Vertex belonged to body B
else
{
contacts.ContactA = Edge_GetClosestPoint(V[1+i].P, edgeA[0], edgeA[1]);
contacts.ContactB = V[1+i].P;
}
}
return 2;
}



[Edited by - oliii on June 27, 2007 8:56:26 AM]

Share this post


Link to post
Share on other sites
I've got an example working if you want. It's using that code.

Share this post


Link to post
Share on other sites
there was a bug in the support point calculations.

As for the code, I can publish it, but it's part of a more general collision system I've been messing around. So code might not be that self explanatory. Hey, might be fun anyway.

Share this post


Link to post
Share on other sites
here you go

It's compiled using VS9 orca beta, since I don't have any other compiler.

It's also using the reflection trick, so the collision shapes (sphere/box/convex objects) are not explicitely typed. A neat way to do collision detection between various types of objects.

It's using the glfw framework extension. If you have problems with the project, give me a shout.

It's also not using polygons yet, just boxes and spheres, however, the basis is there. It's all inherited from a common Convex class, and accelerator finctions are added to speed up the sphere-box, sphere-sphere and box-box tests. However, you can switch on a default SAT test for all those tests, to see how it works using purely the SAT aslgorithm (yes, it also works for sphere-sphere and sphere-box, however, it's highly inneficient).

I plan on extending that code to use swept SAT at some point. I have an idea on how to do this for sphere vs polygons/boxes as well. Not dissimilar to the GJK algorithm in some respect.

The code is not optimised, so it should be easy to read.

Share this post


Link to post
Share on other sites
Thanks to your source i got things to work :)
so, im currently heading forward onto collision response!

thanks a bunch!

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement