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.
- Allows to perform good looking physics simply and accurately,
like bouncing, friction, deals with slopes in an automated fashion.
- The collision detection is more accurate for high-speed sprites.
In a sprite-based system, the objects can potentially jump past each
other in a time frame if they move too fast.
- It is based on vector maths, so can be extended to 3D, while a
sprite collision system is strictly limited to 2D.
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.
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.
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.
- The generation of the separation axis that needs to be tested,
- The calculation of the intervals of each polygons along an axis
(the separation plane normal),
- 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
“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 :)
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.
- The intervals overlap.
- The intervals are disjoint, but will collide forward in time.
- 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.
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.
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.
P
world = P
local * OA + PA
(P
world – PA) = P
local * OA
(P
world – PA) * OA
T = P
local * OA * OA
T
so,
Plocal
= (Pworld – PA) * OAT |
similarly, to transform a directional vector using a forward transform,
D
world = D
local * OA
D
world * OA
T = D
local * OA * OA
T
so
and again, to convert an orientation using a forward transform
O
world = O
local * OA
O
world * OA
T= O
local * OA * OA
T
so
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 6a] : point-edge contact](2D%20polygon_files/image006a.gif)
|
![[image 6b] : edge-edge contact [image 6b] : edge-edge contact](2D%20polygon_files/image006b.gif) |
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.
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 :
where :
- m is the mass
- N is the number of
vertices
- Pn is a Vertex[n] of
the polygon
- ||…|| means, the
‘norm’. In 2D, a cross product returns a float, so it will be
equivalent to finding the absolute value.
calculating the inertia from the density of the material constituting
the polygon you have the equation
Where :
- p is the density
- N is the number of
vertices
- Pn is a Vertex[n] of
the polygon
- ||…|| means, the
‘norm’. In 2D, a cross product returns a float, so it will be
equivalent to finding the absolute value.
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).
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!