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]

I've got an example working if you want. It's using that code.

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.

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.