2D polygon-based collision detection and response


Introduction

This is a tutorial demonstrating how to perform collision detection in 2D action games (Mario, space invaders, etc…), both efficiently, and accurately. The collision detection is polygon-based, not sprite based. There is a difference in design in both approaches.

Sprite based detection performs check on pixels of a overlapping pixels of sprites, and detects collisions that way. Polygons use vector maths to accurately calculate the point, time and direction of impact. While the polygon is only an approximation of the sprite itself, it has advantages over sprite systems.

Features

Due to the algorithm in use, the system can only handle convex polygons, such as triangles, quads, hexagons, circular shapes. For non-convex polygons, you can de-compose the polygons into convex parts, like triangles.

It will work equally with fast moving, or slow moving polygons. No matter how fast an object travels, the collision will not be missed. It also deals with overlaps, and pushes intersecting objects apart.

The demo also supports segment-polygon intersections. This is useful for modeling bullets.

It also provides a simple physics system, modeling elasticity, some basic friction, and static friction. It is useful for keeping characters up a slope.

an example of a rigid body system is also there, implementing Chrsi Hecker's physics tutorials.

There is also support for segment-polygon intersection calculations, to model things like bullets and laser beams.

Limits

Sorting collisions. By that I mean, it might not process collisions in order. This can be a problem for very fast objects. Once a collision is detected, it is processed straight away. Ideally, you’d look for the first collision, process it, and then look for some more. But for a 2D action game, this is usually overkill.

Requirements

The usual stuff, a compiler, the demo is based on a GLUT (GL Utility Toolkit) framework, so download the small GLUT SDK if you haven’t got it, and an opengl compatible video card.

You also need at least a basic understanding of vector maths. The tutorial doesn’t really stretch beyond a dot product, but it helps if you are already comfortable with basic vector operations.

A basic understanding of physics is required. As long as you understand the concept of velocity and simple position updates and time-based movement, you’ll be fine.

for rigid bodies, you'll have to read carefully Chris Hecker's tutorials. It requires a lot more work, but it's well worth it, and not that hard after all :)

table of content

Tutorial 1 - The method of separation axis
Tutorial 2 - Extending the method of separating axis for collision response
Tutorial 3 - Extending further for fast moving objects
Tutorial 4 – Basic Arcade Collision response
Tutorial 5 – Dealing with rotations
Tutorial 6 – Calculating contact points
Tutorial 7 – Rigid Body Dynamics


Tutorial 1 - The method of separation axis

That is the core of the collision detection. The principle is very easy, and very simple to implement. It’s also fast, and solid, since no divisions are involved in the calculations.

I’ll take the simple example of two boxes tested for collisions.

[image 1a] : A Separation Axis

The algorithm tries to determine is it is possible to fit a plane between two object. If such a plane exists, then the object are separated, and cannot intersect.

To determine if the objects are separated, it is simply a matter of projecting the objects onto the normal of the plane, and comparing the intervals and see if they overlap.

So, there is obviously an infinite number of planes that can fit between two separated objects. But it has been proved you only have to test a handful of planes. For boxes, from the picture above, you can see the plane normal is the major axis of Box B.

It can be shown that for boxes, the separation planes to be tested are the planes with normal equal to the axes of both boxes. So for 2 boxes, you only need to test 4 separation planes in total. Out of the 4 planes, once you found a separation plane that separates the boxes, then you know the box cannot intersect, and you return a no collision flag.

If the 4 planes cannot separate the boxes, then the box must be intersection, and there you have a collision.

To extend this to generic polygons, the algorithm remains the same. Only the number of planes to be tested changes. And the separation planes have normal in the direction perpendicular to the edges of each polygon. On the diagram below, you can see two separation planes being tested. on the red separation plane test, you can see the two intervals overlapping. However, on the blue test, the intervals do not overlap. So the blue plane is a separation plane, and the objects do not intersect.


[image 1b] : Two Separation Axes

So, we have now an algorithm to detect if yes or no, the polygons are disjoint or intersecting.
The code can be split into 3 parts.
  1. The generation of the separation axis that needs to be tested,
  2. The calculation of the intervals of each polygons along an axis (the separation plane normal),
  3. And the test determining of the intervals overlap or not.


bool Intersect(Polygon A, Polygon B)
{
    for(I = 0; I < A.num_edges; I ++)
    {
        Vector N = Vector(-A.EdgeDir[I].y, A.EdgeDir[I].x);
        if (AxisSeparatePolygons(N, A, B))
            return false;
    }
    for(I = 0; I < B.num_edges; I ++)
    {
        Vector N = Vector(-B.EdgeDir[i].y, B.EdgeDir[I].x);
        if (AxisSeparatePolygons (N, A, B))
            return false;
    }
    return true;
}

void CalculateInterval(Vector Axis, Polygon P, float& min, float& max)
{
    float d = Axis dot P.vertex[0];
    min = max = d;
    for(I = 0; I < P.num_vertices; I ++)
    {
        float d = P.vertex[I] dot Axis;
        if (d < min)
            min = d;
        else
        if(d > max)
            max = d;
    }
}

That's it. an algorithm to detect collisions between 2D polygons, which is fast, and solid. The Edge directions do not have to be normalised. So you can avoid storing edge directions all together, and building the edge directions from vertices of the polygons directly.

for(J = A.num_vertices-1, I = 0; I < A.num_vertices; J = I, I ++)
{
    Vector E = A.vertex[I] – A.vertex[J];
    Vector N = Vector(-E.y, E.x);

    if (AxisSeparatePolygons(N, A, B))
        return false;
}


Tutorial 2 - Extending the method of separating axis for collision response

Detecting if polygon intersects is useful, but we’d like to be able to do more. What if when polygons intersect, I’d like to move the polygons away from each other so they stop intersecting?

The method of separating axis can be used as well, with a little bit of extra work. It can return the depth of penetration, and the direction required to push polygons away so they stop intersecting. A combination of both the depth and direction of intersection is also called the MTD, or minimum translation distance. That’s the minimum vector required to push objects apart to stop them intersecting.

To calculate the MTD, we can use the separation axis to our advantage.

When objects are intersecting, we know the interval calculated on each separation axis for both objects intersect. The amount of intersection of the two intervals along that axis provides a push vector, that you need to apply to either object so that the object’s projection stop intersecting along that axis

[image 2a] : The push vector

“Push Vector” is the vector you need to apply to push A so it stops intersecting with B so A and B stop intersecting.

Obviously, you can’t just push the objects along a random axis. The candidate axis for the push is the axis where the amount of overlap between the two intervals is minimum. And that push vector provides the minimum translation distance.

bool Intersect(Polygon A, Polygon B, Vector& MTD)
{
    // potential separation axes. they get converted into push
    vectors Vector Axis[32];
    // max of 16 vertices per polygon
    int iNumAxis = 0;
    for(J = A.num_vertices–1, I = 0; I < A. num_vertices; J = I, I ++)
    {
        Vector E = A.vertex[I] – A.vertex[J];
        Axis[iNumAxis++] = Vector(-E.y, E.x);
   
    if (AxisSeparatePolygons(N, A, B))
            return false;
    }
    for(J = B. num_vertices–1, I = 0; I < B.num_vertices; J = I, I ++)
    {
        Vector E = B.vertex[I] – B.vertex[J];
        Axis[iNumAxis++] = Vector(-E.y, E.x);
   
        if (AxisSeparatePolygons (N, A, B))
            return false;
    }
   
    // find the MTD among all the separation vectors
    MTD = FindMTD(Axis, iNumAxis);

    // makes sure the push vector is pushing A away from B
    Vector D = A.Position – B.Position;
    if (D dot MTD < 0.0f)
        MTD = -MTD;

    return true;
}

bool AxisSeparatePolygons(Vector& Axis, Polygon A, Polygon B)
{
    float mina, maxa;
    float minb, maxb;

    CalculateInterval(Axis, A, mina, maxa);
    CalculateInterval(Axis, B, minb, maxb);

    if (mina > maxb || minb > maxa)
        return true;

    // find the interval overlap
    float d0 = maxa - minb;
    float d1 = maxb - mina;
    float depth = (d0 < d1)? d0 : d1;

    // convert the separation axis into a push vector (re-normalise
    // the axis and multiply by interval overlap)
    float axis_length_squared = Axis dot Axis;

    Axis *= depth / axis_length_squared;
    return false;
}

Vector FindMTD(Vector* PushVectors, int iNumVectors)
{
    Vector MTD = PushVector[0];
    float mind2 = PushVector[0] dot PushVector[0];
    for(int I = 1; I < iNumVectors; I ++)
    {
        float d2 = PushVector[I] * PushVector[I];
        if (d2 < mind2)
        {
            mind2 = d2;
            MTD = PushVector[I];
        }
    }
    return MTD;
}

Once you found the MTD vector when objects intersect, to separate them, it’s simply

A.Postion += MTD * 0.5f;
B.Position -= MTD * 0.5f;

Obviously, if object A is static, like part of the environment, the B will be pushed by the full MTD (B.Position -= MTD), while A will not be pushed.

Tutorial 3 - Extending further for fast moving objects

The method above works well with slow objects. But when objects travel fast, the collision system will loose accuracy, missing collisions, or even allow objects to teleport past each other, which is a really bad idea.

Here again, we can use the method of the separation axes, extend it further, and use the algorithm for detecting both collisions forward in time, and overlaps.

The principle remains the same, and is better explain with a picture :)

[image 3a] : Dynamic Separation Axis

Again, it’s just projection maths. if intervals are disjoint, project the velocity along the separation axis, and calculate the time for the two intervals to touch.

Compared to the ‘static’ separation axis algorithm, there is one extra axis we have to test. this is obviously an axis related to the displacement (or velocity) vector.

So, for each separation axes, there are 3 choices.
  1. The intervals overlap.
  2. The intervals are disjoint, but will collide forward in time.
  3. The intervals are disjoint, but will not collide forward in time, or will collide too late.

The third option means that the objects won’t collide this frame, and that the separation axis does indeed separate the objects. So there is no collision between objects for that frame.

The AxisSeparatePolygons() function will reflect that, and return either the amount of overlap, or the calculated time of collision. To differenciate the two, when an overlap is detected, a negative number will be returned. If a collision forward in time is detected, a positive number is returned. the function will look like that

bool AxisSeparatePolygons(Vector Axis, Polygon A, Polygon B, Vector Offset, Vector Vel, float& t, float tmax);

Where Offset is the relative position of polygon A to polygon B, and Vel is the relative velocity of polygon A to polygon B.

When it comes to finding the plane of collision, the algorithm is very similar to the MTD search. Only this time, the collisions forward in time take priority over the overlaps. If collisions forward in time are found, the latest one is selected.

If none are found and we detected overlaps only, then as before, the smallest overlap is used.

The collision detection function then returns the normal of collision, and either the depth of collision (a negative number), or the time of collision (a positive number).

The final pseudo code looks like this…

bool Collide(   const Vector* A, int Anum,
                const Vector* B, int Bnum,
                const Vector& xOffset, const Vector& xVel,
                Vector& N, float& t)
{
    if (!A || !B) return false;
      
    // All the separation axes
   
// note : a maximum of 32 vertices per poly is supported
   
Vector xAxis[64];
    float taxis[64];
    int iNumAxes=0;

    xAxis[iNumAxes] = Vector(-xVel.y, xVel.x);
    float fVel2 = xVel * xVel;
    if (fVel2 > 0.00001f)
    {
        if (!IntervalIntersect( A, Anum, B, Bnum, xAxis[iNumAxes], xOffset, xVel, taxis[iNumAxes], t))
            return false;
        iNumAxes++;
    }

    // test separation axes of A
    for(int j = Anum-1, i = 0; i < Anum; j = i, i ++)
    {
        Vector E0 = A[j];
        Vector E1 = A[i];
        Vector E = E1 - E0;
        xAxis[iNumAxes] = Vector(-E.y, E.x);
       
        if (!IntervalIntersect( A, Anum, B, Bnum, xAxis[iNumAxes], xOffset, xVel, taxis[iNumAxes], t))
            return false;

        iNumAxes++;
    }

    // test separation axes of B
    for(int j = Bnum-1, i = 0; i < Bnum; j = i, i ++)
    {
        Vector E0 = B[j];
        Vector E1 = B[i];
        Vector E = E1 - E0;
        xAxis[iNumAxes] = Vector(-E.y, E.x);

        if (!IntervalIntersect( A, Anum, B, Bnum, xAxis[iNumAxes], xOffset, xVel, taxis[iNumAxes], t))
            return false;
        iNumAxes++;
    }
   
    if (!FindMTD(xAxis, taxis, iNumAxes, N, t))
        return false;

    // make sure the polygons gets pushed away from each other.
    if (N * xOffset < 0.0f)
        N = -N;

    return true;
}

bool AxisSeparatePolygons ( Vector N, Polygon A, Polygon B, Vector Offset, Vector Vel, float &t, float tmax)
{
    float min0, max0;
    float min1, max1;

    CalculateInterval(N, A, min0, max0);
    CalculateInterval(N, B, min1, max1);
   
    float h = Offset dot N;
    min0 += h;
    max0 += h;

    float d0 = min0 - max1; // if overlapped, do < 0
    float d1 = min1 - max0; // if overlapped, d1 > 0

    // separated, test dynamic intervals
    if (d0 > 0.0f || d1 > 0.0f)
    {
        float v = Vel dot N;

        // small velocity, so only the overlap test will be relevant.
        if (fabs(v) < 0.0000001f)
            return false;

        float t0 =-d0 / v; // time of impact to d0 reaches 0
        float t1 = d1 / v; // time of impact to d0 reaches 1
        // sort the times.
        if (t0 > t1)
        {
            float temp = t0;
            t0 = t1;
            t1 = temp;
        }
        // take the minimum positive
        taxis = (t0 > 0.0f)? t0 : t1;

        // intersection time too late or back in time, no collision
        if (taxis < 0.0f || taxis > tmax)
            return true;

        return false;
    }
    else
    {
        // overlap. get the interval, as a the smallest of |d0| and |d1|
        // return negative number to mark it as an overlap
        taxis = (d0 > d1)? d0 : d1;
        return false;
    }
}



bool FindCollisionPlane (Vector* Axis, float* taxis, int iNumAxes, Vector& Ncoll, float& tcoll)
{
    // find collision first
    int mini = -1;
    tcoll = 0.0f;
    for(int i = 0; i < iNumAxes; i ++)
    {
        if (taxis[i] > 0.0f)
        {
            if (taxis[i] > tcoll)
            {
                mini = i;
                tcoll = taxis[i];
                Ncoll = Axis[i];
                Ncoll.Normalise(); // normalise axis
            }
        }
    }

    // found a collision
    if (mini != -1)
        return true;

    // nope, find overlaps
    mini = -1;
    for(int i = 0; i < iNumAxes; i ++)
    {
        float n = Axis[i].Normalise(); // axis length

        taxis[i] /= n; // normalise interval overlap too

        // remember, those numbers are negative, so take the closest to 0
        if (mini == -1 || taxis[i] > tcoll)
        {
            mini = i;
            tcoll = taxis[i];
            Ncoll = Axis[i];
        }
    }
   
    return (mini != -1);
}



So there you have it, a system that detects polygon collisions either forward in time, or when overlapped, and return the collision plane, and depth/time of collision.

Tutorial 4 – Basic Arcade Collision response

So, what to do next? Well, you can make the two objects bounce off each other by a given amount, add a bit of friction in the mix, and also add some basic static friction as well, to stop player sliding down slopes.

That part uses the simple velocity reflection algorithm. Also, to make the collision response more interesting, objects are set to have mass (rather, inverse masses).

Inverse masses are more useful, as having an inverse mass of 0 means, the object as an infinite mass, and is therefore unmovable. Also, it is more physically accurate to use inverse masses in the velocity response.

Ok,so we know that polygon A, at position PA and velocity VA, collided with polygon B, at position PB and with velocity VB. Ncoll and tcoll defined the collision plane.

If the collision was an overlap, we first separate the two objects, like explained below.

if (tcoll < 0)
{
    if (A.InvMass == 0)
        PB += Ncoll * tcoll;
    else if (B.InvMass == 0)
        PA -= Ncoll * tcoll;
    else
    {
        PA -= Ncoll * (tcoll * 0.5f);
        PB += Ncoll * (tcoll * 0.5f);
    }
}

Then, we can call the collision response code.

To simplify, we can consider a particle hitting a plane.

[Image 4a] : Reflective collision response

V, being the incoming velocity of the particle, V’ the resulting velocity of the particle bouncing on the plane with normal N.

V’ = V – (2 * (V . N)) * N

that’s for a perfect reflection. the particle will bounce with the same energy.

this is quite boring, but it’s easy to see that we can make the particle bounce less by adding an elasticity factor.

V’ = V – ((1 + elasticity) * (V . N)) * N

Elasticity is in the range [0, 1]. and elasticity of 0 means, the particle will just slide on the plane. Elasticity of one, the particle will bounce with no energy lost.

Similarly, we can had some fake friction, more like drag. if we decompose the velocity along the normal of the collision, and the collision plane, we can do both elasticity and friction at the same time, very cheaply.

[image 4b] : Reflective Collision Response with Drag friction

here, the velocity is decomposed along the normal of the plane, and the plane of collision. The elasticity will affect the response along the normal of the plane (Vn), while the friction will affect the tangential component of the velocity (Vt).

again, the coefficient of friction is a number in the range [0, 1]. 0 means no friction, 1 means the particle will stop dead on.

Vn = (V . N) * N;
Vt = V – Vn;
V’ = Vt * (1 – friction) + Vn  * -(elasticity);

Simple as that.

for static friction, simply detect when the length of vector Vt is below a given value. If so, set Vt to (0, 0), or set the coefficient of friction to be slightly above 1 (1.001f).

now, to compute a response for two objects colliding. The principle is the same. However, the calculations are based on the relative velocity of the objects, which gets reflected like above. Then a part of the response gets added to each objects.

The coefficients are slightly changed, since now we work in relative terms.

Vector V = Va – Vb; // relative velocity
Vn = (V . N) * N;
Vt = V – Vn;

if (Vt.Length() < 0.01f) friction = 1.01f;

// response
V’ = Vt * -(friction) + Vn  * -(1 + elasticity);

Va += V’ * 0.5f;
Vb -= V’ * 0.5f;

this will apply a response equally to objects A and B.

to make it more interesting, A and B can have different masses. Obviously, you can expect the lighter object to get most of the response, while the heavier one will be less perturbed by the collision. So, we can use the masses to linearly scale the response on both objects. an heavy object, with a very small inverse mass, will move less, even not at all if is mass is infinite (i.e. his inverse mass is 0).

Va += V’ * (InvMassA) / (InvMassA + InvMassB);
Vb -= V’ * (InvMassB) / (InvMassA + InvMassB);




Tutorial 5 – Dealing with rotations

Rotating objects are often found in arcade games, obviously. Colliding with them adds a little more complication. The standard way of rotating a sprite is through a single angle scalar, usually in the range [0, 2 * PI]. However, matrices can be used to store away expensive trigonometric calculations, and an angle can therefore be converted to a 2x2 matrix using a combination of trigs (sines and cosines).

A simple way of handling collisions of rotating objects is to keep a copy of the original polygon, but transform to the current object’s position and orientation. This is too easy J , so I decided to expand a bit, and produce an algorithm that is more on par with a general collision detection system, that can also (and should) apply in 3D.

If you are unsure about matrix maths, and their relations to vectors, linear algebra, and trigonometry, you can have a look at this brief article. http://www.gamedev.net/reference/articles/article1832.asp

To keep things short, the usual way of colliding two rotating and translating objects is to convert one object into the other object’s space, therefore limiting the transformations required to only one object during the collision detection phase. Converting to model space can be quite confusing, but if you stick to the basic algebra, it becomes simple.

So far, the collision detection was already converting one object into the other object’s space, by calculating the relative position and velocity of one object to another. Adding orientation does complicate things slightly.

Consider two objects A and B, with position PA and PB, orientation OA and OB, and displacement DA and DB. To transform Object A into it’s own model space, where PA = Origin, OA = IdentityMatrix, and VA = Vector(0, 0), we need to aply transformations to objectA.

consider the forward transforms, doing exactly the reverse, and transforming a point from local space into world space.

Pworld = Plocal * OA + PA
(Pworld – PA) = Plocal * OA
(Pworld – PA) * OAT = Plocal * OA * OAT
so,
Plocal = (Pworld – PA) * OAT

similarly, to transform a directional vector using a forward transform,

Dworld = Dlocal * OA
Dworld * OAT = Dlocal * OA * OAT
so
Dlocal = Dworld * OAT


and again, to convert an orientation using a forward transform

Oworld = Olocal * OA
Oworld * OAT= Olocal * OA * OAT
so

Olocal = Oworld * OAT


so here we go, to convert the position of object B into A’s local space,

PB’ = (PB – PA) * OAT
DB’ = (DB – DA) * OAT
OB’ = (OB) * OAT


Similarly, when we are testing separation axes, we have to remember that we are still in local space, and need to transform the separation axes from local space of B into local space of A.

and again, to calculate the intervals of object B locally, using an axis transformed into the local space of A, we have to inverse the axis back into the local space of B.

I’m sure this can cause a lot of confusions J As I said earlier, Another solution is basically not bother about local space, and transform beforehand the polygons of A and B into world space, and do the intersection test all in world space. The downside is, you have to keep a copy of the base collision polygon in each objects, since each of these will need to be calculated into world space individually. The advantage is, you do not have to re-compute the transformations every time you process a collision. This is fine for 2D games, but when it comes to 3D, then you don’t really want to transform objects every frame just for the purpose of collision detection, especially if the objects are stored into trees and have complex shapes.

Tutorial 6 – Calculating contact points

To move on to rigid body dynamics, we need a way to calculate the exact contact points between two colliding polygons. this is not very difficult in 2D, but can get quite complicated in 3D. For the 2D case, we can consider two cases for contact points. a point-edge contact, or an edge-edge contact.

This process is hardly worth a tutorial, but it’s well suited for a nice visualisation demo :)


[image 6a] : point-edge contact
[image 6b] : edge-edge contact
Point-Edge contact
Edge-Edge contact


Here, I’m only considering the overlap case, but for the collision case, it would be the same principle.

So, Given a collision normal direction, in the Point-edge contact, how to find the contact points?

For contact A, it is rather straight forward. We need a so-called support mapping function, which returns the point on the polygon the lowest along a given direction. Very much like the CalculateInterval() function in the first tutorial.

int FindSupportPoints(const Vector& N, float t,
                      const Vector* A, int Anum,
                      const Vector& PA, const Vector& VA,
                      const Matrix& OA, Vector* S)

{
    Vector Norm = N ^ OA;
    float d[32];
    float dmin;
    dmin = d[0] = A[0] * Norm;

    for(int i = 1; i < Anum; i ++)
    {
        d[i] = A[i] * Norm;

        if (d[i] < dmin)
        {
            dmin = d[i];
        }
    }

    int Snum = 0;

    const float threshold = 1.0E-3f;

    for(int i = 0; i < Anum; i ++)
    {
        if (d[i] < dmin + threshold)
        {
            S[Snum++] = Transform(A[i], PA, VA, OA, t);
           
            if (Snum == 2)
                return Snum;
        }
    }
    return Snum;
}


Here, the first part of the function finds the minimal of the polygon. The second part simply finds all the points very close to that minimal, so if the normal of collision is perpendicular to an edge, two points will be returned. The points are stored in world space, the function Transform makes sure the contact points found for that polygon are converted to world space, and if it is a collision forward in time, the point will be translated to the moment of collision.

Vector Transform(const Vector& Vertex, const Vector& P, const Vector& V, const Matrix& xOrient, float t)
{
    // convert point into world space
    Vector T = P + (Vertex * xOrient);

    // collision forwatd in time, need to translate to moment of collision
    if(t > 0.0f)
        T += V * t;
    return T;
}


For points on B, you simply need to find the support points in the opposite direction.

The physics will later on require pairs of contact points on both objects to work out the collision impulses which will make the object tumble. You can see on the diagrams what pairs of contacts you need to generate depending on the type of collision.

So, with calls to FindSupportPoint() you end up with either one or two contact points on each object. In case of a one-to-one contact, you don’t need to do anything. At the moment, one-to-one contacts are not supported, but can be easily extended into the separation axis algorithm.

In case of a one-to-two contact, it’s simply a point-versus-edge collision like in the first diagram above.

In case of a two-to-one contact, the same thing applies, except objects are swapped around.

In the case of a two-to-two contacts, it’s an edge-edge collision, and you need to find the intersection space between the edge, which will provide

First, the point-edge collision. In that case, the pairing contact point is simply the projection of the contact point on A onto the edge on B, or in more meaningful terms, the point on edge B the closest to the contact point on A.

Vector FindClosestPoint(const Vector& V, const Vector& A, const Vector& B, float* pt)
{
    Vector AV = V - A;
    Vector AB = B - A;
   
    float t = (AV * AB) / (AB * AB);

    if (t < 0.0f)
        t = 0.0f;
    else if (t > 1.0f)
        t = 1.0f;

    if (pt) *pt = t;

    Vector P = A + t * AB;
    return P;
}

In the case of edge-edge, the process is quite similar. Only, you need to sort the points direction perpendicular to the normal of collision, and take the two middle points. Then, you project those points onto the other segment to get the pairing contact point.

[image 06c] : Converting support poitns to contacts


With those contact points, then you are ready to write a basic rigid body system, where objects will collide and respond to collisions a lot more realistically than before.


Tutorial 7 – Rigid Body Dynamics

Instead of wasting a lot of energy trying to demonstrate rigid body dynamics, I’ll point to the best resource around.

http://www.d6.com/users/checker/dynamics.htm#articles

Here, all is revealed about how to implement realistic physics in 2D games.

I will talk about the extensions I made, though. First of all, calculating the inertia for a given convex polygon can be tricky. Just to remind you, inertia is for angular dynamics what mass is for linear dynamics. A high inertia is equivalent to a high mass, in the sense that the object will rotate with difficulty. A low inertia, on the contrary, make the object very susceptible to changes in angular velocities.

Mass and inertia are intricately linked, since they all depend on the size, and density, and ‘balance’ of the object. To talk through it quickly, as I’m no physics expert, I’ll just point to the equations, and where I got them from.

http://www.physicsforums.com/showthread.php?s=e251fddad79b926d003e2d4154799c14&t=25293&page=2&pp=15

in short, the equation for calculating the inertia is :

[image 07a] : Inertia of a convex polygon

where :


calculating the inertia from the density of the material constituting the polygon you have the equation

[image 07b] : Inertia of a polygon from density

Where :

Then from those two equations, you can deduce the equation to calculate the mass.

Another addition made to the system, is dealing with overlaps. This is simply to stop objects sinking into each other, since the impulse calculation used is very inaccurate at low velocities. To solve an overlap, it’s simply a matter of pushing the objects away from each others along the normal of collision, by the collision depth amount. That of course, applies only if an overlap is detected.

To make things slightly more accurate, the objects are displaced depending on the ratio of their masses, so the lighter objects will move be displaced more, while the heavier objects won’t be displaced as much. Of course, objects will infinite mass won’t be displaced at all.

As for the friction, the basic dynamic friction model is a Coulomb friction force, that adds an impulse to the objects with direction perpendicular to the tangential velocity, and with magnitude equal to ||u.Jn|| , where u is the coefficient of dynamic friction, and Jn the vertical collision impulse.

Static friction is always hard to model simply. I choose the solution of modelling static friction as if the object was colliding with an invisible step on the collision plane. Basically, a collision impulse, very similar to the collision impulse calculated for normal impacts, is computed. The collision impulse direction is going in the opposite direction of the velocity, while the magnitude is so that the contact velocity gets cancelled out (basically, the coefficient of restitution is slightly > 1).

[image 07c] : Modelling static friciton

And that’s it! The rest pretty much follows Chris Hecker’s instructions. The bodies tumble, collide, do all sorts of crazy things, in a relatively realistic manner.


Conclusion
 
You have the demo + code to play around with (mouse buttons to attract stuff, ‘p’ for pause and help, ect…). The demo also contains a function to do segment/polygon intersection test, that can be useful for modelling fast projectiles. It clips the segment to the polygon, returns the normals at the clip points… 

So, that should cover some of your collision and basic physics needs for your 2D action game. If I get good feedback, I might be inclined to improve the features, and ad more support, and discuss other aspects of physics for 2D games (tiles, BSP trees, an object oriented design for the whole thing, ...).
 
any problems, comments, suggestions, mail me at olivierrenault@hotmail.com

Enjoy!