Creating a Fast and Stable 2D Pixel Perfect Rigid-Body Simulation using Verlet Integration
Jamie Cheng
June 13, 2003
Abstract
This paper describes a
simple implementation of creating a fast, stable, 2D rigid-body physics engine
that can take arbitrary sprites for the collision zones. We combine Jakobsen’s
work on advanced character physics [4] with pixel perfect collision detection
and resolution. The system allows designers to supply mass, restitution,
coefficient of static friction and kinetic friction, and supports the developer
with additional information such as the point and normal of collision.
The implementation as described in
here is not meant to be extremely accurate in regards to simulation, but rather
a relatively fast way to calculate realistic looking movement. For an in-depth
discussion on accurate simulations, refer to classic papers such as those by
Baraff [1]. The approach shown here combines old techniques of physically based
modeling with new ones (with respect to the game industry) of approximating
motion using Verlet Integration.
Table of Contents
3.1 Calculating the Collision Bitmap
3.3 Calculating the Collision Normal
4.1 Backtrack to point of collision
4.2 Determine exit velocity of objects
6 Extensions
to 3D and soft-body simulation
1 Introduction
Physics have become
increasingly important in the gaming industry, as developers strive to provide
the interactive environments that players seek. Classical approaches to
physical simulations are quite involving, and often
too slow for an independent developer striving for the low-end computers in a
shareware market. Often, independent developers do not even have the time to
implement these kinds of systems in a robust manner; for example, handling
multiple collisions elegantly and efficiently, or dealing with boundary cases.
The solution presented in this paper is simple to implement, yet stable even
under stressful circumstances, thanks to a tolerant yet rapidly convergent
method proposed by Jakobsen [4].
In general, you can
divide the physics simulation into these problem areas:
1)
Modeling
motion
2)
Collision
detection
3)
Collision
resolution
All three of these
parts are modular enough that you can use your own implementation of each. I
will give one implementation to each of these, but remember a specific implementation
of one is not necessary for the implementation of the others.
2 Modeling motion
Motion is modeled
according to Thomas Jakobsen’s paper in GDC2001, found here
[4]. Using his model, soft-bodies becomes a natural extension to the
system, as well as inverse kinematics such as 2D robotic arms (see section 6). Stability
is achieved because the model does not require correctness every frame, but
rapidly converges to one due to Gauss-Seidel relaxation. In addition, we gain efficiency
compared to classical approaches because under our implementation, only one
relaxation iteration is needed per frame, and less information is stored and
calculated.
2.1 The Model
Each rigid-body model
is made up of 2 particles constrained by a single stick constraint. Each
particle stores its acceleration for the current frame, its current position
and its previous position.
The position of the
model is the position of one of the particles, the current velocity is the
current position subtracted by the previous position, and the facing is derived
as the vector from the first position to the second particle. In addition,
mass, coefficient of static and kinetic friction, and
restitution is stored per model.
As you can see, this
system stores and computes a lot less information than the typical physics
engine which calculates torque, impulse, rotational velocity, linear velocity,
etc.
2.2 Changing Velocity
In order to change the
velocity of the current model, simply move the respective particles in the
direction of the desired velocity, or alternatively, move the previous position
in the opposite direction. The Verlet system will then take over, with
surprising accuracy.
2.3 Applying a Force
To apply a force to
the system, simply use the equation: F = MA. Then, derive the desired
acceleration and apply this to the model’s particles.
2.4 Applying Rotation
Applying rotation is a
lot subtler. In this system, there is no such thing as rotational velocity.
However, you can cause a rotation to happen by moving a particle in the
direction of rotation. Just moving a single particle will bias the model to
move in a certain direction linearly, thus you should also move another
particle in the opposite direction by the same magnitude (figure 1).
The pseudo code of
this may be:
Vector2 facing = GetFacing();
//get the direction
perpendicular to facing
Vector2 clockwiseRotate(facing.y, -facing.x);
clockwiseRotate *= rotate_amount;
//move the particles
m_particles[0]->Displace(clockwiseRotate);
m_particles[1]->Displace(-clockwiseRotate);
In addition, you may
forcefully displace the particles by a certain angle, rotating one particle
around the position of the other particle. This will give you more accurate
results if you wish to have absolute control on the amount of rotation and
rotational velocity applied.
3 Collision Detection
A pixel-perfect
collision detection system has several benefits over the polygonal based collision
systems: first, we do not need to calculate a double-dispatch – there is only
one type of collision zone; second, designers do not need to specify collision
geometry – the collision zone is extracted directly from the displaying sprite;
third, collisions are more precise and therefore should cause less frustrations
for players.
These of course all
pertain to a 2-dimensional system; it simply wouldn’t make sense to use
“pixel-perfect” detection in 3D, especially since all the models are polygonal
in the first place.
However, we note that
a pixel perfect collision detection scheme is by nature much slower than its
polygonal counterpart. Although the solution presented here is relatively fast,
if speed is more important than being pixel perfect, I would suggest using
primitives such as circles and OBBs to calculate the
collision information, instead of this one.
3.1 Calculating the Collision Bitmap
If you wish to use a
3D library such as Direct3D or OpenGL to display your sprites, then you need a way
to extract the collision bitmap from a rotated sprite. Even in DirectDraw, as
far as I know, you cannot extract the information of the sprite after rotation.
Thus, we present a relatively fast way to calculate the collision bitmap.
The idea is that we
can either rotate every single pixel of our collision bitmap (expensive), or we
can rotate the origin and iterate through the texture using the new coordinate
system (cheap).
First, grab the
texture information (LockRect in Direct3D). Next, we create a 2x2 rotation
matrix from our current model facing. This can be done using a dot product to
determine the angle of rotation, then creating the matrix from this angle
(there are other ways).
If
(<0,1> · facing) > 0
rotation = acos( facing.x
)
else
rotation = -acos( facing.x )
Matrix22
rotation_matrix = CreateRotationMatrix(
rotation )
Next, transform the
top left point of the texture by that matrix, and determine the basis vectors
of the new local coordinate system (xvec and yvec). Do this by multiplying the basis vectors <1,0> and <0,1> by the rotation matrix.
Vector2
xvec = <1,0> * rotation_matrix
Vector2
yvec = <0,1> * rotation_matrix
We then loop through
the texture to find all the collide-able pixels using the new local coordinate system.
For each of these pixels, use the non-rotated coordinate system position as an
entry into a collision bitmap.
Pseudo-code to
calculate the collision bitmap:
Vector2
rel_pos = origin*rotation
For
y = 0 to texture_ysize
Vector2 xpos = rel_pos
For x = 0 to texture_zsize
If( Collidable( texture[xorig.x][xorig.y] ) )
Collisionbitmap[x][y] = texture[xorig.x][xorig.y]
xorig
+= xvec
orig += yvec
3.2 Checking for Collision
To check for collision
between two objects, first determine the overlapping area of the two bounding
boxes. If they do not overlap, we return false trivially. Otherwise, do a
bit-wise AND operation on the overlapping areas.
At this point there
are three options. You can exit on the first non-zero AND operation, and return
a Boolean true. Or, you can calculate the number of colliding pixels. Finally,
you can calculate the point of collision by calculating the average position of
colliding pixels. Each of these has different uses in different situations, as
you will see.
3.3
Calculating the Collision Normal
In order to extract
the normal of impact, we derive an approximation to the gradient vector of the
overlapping area of the sprites [3]:
f(x,y)
:= returns the number of bits overlapping with one object stationary and the
other at location x and y
Ñf(x,y) ~= (f(x+1,y) – f(x-1,y), f(x,y+1) – f(x,y-1))
Since this gradient
vector points in the direction where the overlap increases the most, this can
be used as the normal of impact.
4 Collision Resolution
First, let us consider perfectly elastic collisions. This means that collisions retain kinetic energy, and act more like billiards and less like cars colliding that stick to each other after impact. To calculate the collision response, we use a strictly kinematical approach. Thus, instead of calculating the impulse generated at collision, we determine the exit velocity of the colliding objects. Here are the steps in determining the collision response.
4.1 Backtrack to point of collision
First we determine if the previous positions
of the objects are already colliding. If they do, we simply take the normal and
project the offending object in the direction of the normal until it is no
longer colliding. Otherwise, we calculate the point of
collision by bisection – continually bisect between the previous and the
current position until the point of intersection is found.
Pseudo-code to this:
If previous frame collides
//project in
direction of normal until no overlap
while(overlapping)
current_position1 -=
normal;
current_position2 +=
normal;
if no longer overlapping
penetrationPt1 =
current_position1;
penetrationPt2 =
current_position2;
overlapping = false;
else
//bisection --
backtrack until no collision
while overlapping or (diff1.Length() > tolerance)
Vector2 temp1 =
prevpos1 + (diff1 / 2);
Vector2 temp2 =
prevpos2 + (diff2 / 2);
If temp1 and temp2
overlapping
overlap = true;
current_position1 =
temp1;
current_position2 =
temp2;
else
overlap = false;
prevpos1 = temp1;
prevpos2 = temp2;
diff1 =
current_position1 - prevpos1;
diff2 =
current_position2 - prevpos2;
penetrationPt1 =
current_position1;
penetrationPt2 =
current_position2;
4.2 Determine exit velocity of objects
First, consider a single object colliding with a stationary line (figure 2). Calculate the component of the entering velocity in the direction of the normal of collision.
Vi := initial velocity
N := normal of collision
Ve :=
exit velocity
VN = (Vi · N) * N
If we subtract this
from Vi, we get a vector perpendicular to the normal.
Subtracting it again, we get a perfect reflection across the normal. This is a
completely elastic collision. To account for restitution, and thus a non-purely
elastic collision, we introduce a coefficient of restitution, which
lies between 0 and 1:
e :=
coefficient of restitution
Ve = Vi – (1 + e)*VN
Now, extending this to
multiple objects with different masses, we have to take into account that smaller
objects receive more of the kinetic energy. Thus, we take the inverse masses of
the objects and normalize it to 1.
inverseA := 1/(
inverseB := 1/(massB)
mA := inverseA / (inverseA + inverseB)
mB := inverseB / (inverseA + inverseB)
Finally,
VeA := ViA – (1 + e)*VNA*mA
VeB := ViB – (1 + e)*VNB*mB
4.3 Determine Rotations
This however does not
take into account rotation. To calculate rotations, we take the point of
collision, and project the relative velocity from the point of collision. Then
we take a dot product to decide which side of this line the center of mass of
the object lies (figure 3). The sign of the dot product determines the
direction of rotation (clockwise or anti-clockwise) and the magnitude of the
dot product determines the speed of rotation.
4.4 Kinetic Friction
To allow the objects
to stop instead of slide around on an infinitely smooth surface, we need
kinetic friction. The implementation of this is simple:
mk := coefficient of kinetic
friction
fn := magnitude of normal force
m := mass of object
N := normal of
collision
FF := frictional force
G := gravitational
force
A := acceleration of
object
Now,
fn =
m * (G · N)
To get a vector again, we need a direction – this direction is the direction perpendicular to N, and away from the relative velocity of the objects after collision.
D := direction
perpendicular to the normal of collision
R := relative
velocity of objects after collision
D
= <N.y, -N.x>
If
( D · R
) > 0
D
= -D
FF
= | mk * fn
| * D
So
FF = m * | mk * (G ·
N) | * D
m*A = m * | mk * (G ·
N) | * D
A = | mk * (G · N) | * D
Thus, we apply an acceleration of A to the
object in question. The coefficient of kinetic friction is the average of the
coefficients of kinetic friction of the two colliding objects.
4.5 Static Friction
In static friction,
the object has come to rest, and cannot accelerate again until it passes the
static frictional force.
ms := coefficient of static
friction
To see if the current
gravitational force is enough to overcome the static friction, we calculate the
following:
if
(!velocity.Length)
fs := m * G ·
D
if ( fs > ms * fn )
acceleration
= 0
This will give you the nice effect of an object sitting still on a small slope. If you nudge the object, it will begin to slide down until something stops it (e.g. kinetic friction). If you increase the slope past the critical angle, the object will slide down.
5 Optimizations
Here are a few ways to
greatly increase the speed of your physics system. In the accompanying demo, I
have only implemented the first of these techniques.
5.1 Optimized AABB
One of the easiest
ways to minimize the expense of the collision detection operation is to
calculate an optimized AABB (axis aligned bounding box) of your collision
bitmap. To do this, you can apply the 2x2 rotation matrix calculated from the
facing to 3 corners of the original texture, and find the extreme points using
a series of max and min operations. One of the corners becomes your origin, and
the other 3 are rotated with respect to this corner.
5.2 Sweep and Sort
To decrease the number
of calls to even check for bounding box overlap, you can use the proverbial
sweep and sort algorithm, presented in Baraff’s paper
[1]. This will bring your O(n2)
algorithm to an average of O(nlogn + k), where
k is the number of pairwise overlaps.
5.3 Using RLE
A third way to
increase the speed of collision detection is to use encode your collision bitmap
into RLE (run-length encoding). I have not implemented this myself, but Mike Hommel has a nice description of this [2].
6 Extensions to 3D and soft-body
simulation
If you replace the pixel perfect collision detection to a polygonal based one, you could extend the ideas shown here to 3D easily. In addition, the speed of your system will be greatly increased, as the bottleneck to this system is the many calls to the pixel overlap function. At this point, you will still reap the benefits of a stable, simple and fast implementation.
Extending your system to include soft-bodies is also simple – you can use the methods described in Jacobsen’s paper [4]. Since the system already embraces Verlet Particles, you can add new constraints to your models to create soft-bodies. For example, a few particles can be constrained loosely to one another and then tightly constrained to a rigid-body model particle to make a wrecking ball.
7 Conclusion
In 2D games, we are
often not looking for the most accurate simulations, but rather ones that
simply look realistic. In addition, 2D games based on collision
generally need collision accuracy down to the pixel. Speed, stability and ease
of implementation are also important. I believe I have touched on all these
areas, and provided a viable solution, as shown by the accompanying demo.
The ideas presented
here are by no means revolutionary. It is simply that when I set out to create
my simulation, I could not find a resource that had the implementation I was
looking for, so I figured others would benefit from my knowledge. I greatly
welcome any feedback, and would love to hear how I can improve my solution.
8 Special Thanks
To Raigan
Burns, and all the other FlipCoders that helped me out when I was struggling to get this
physics system up and running. Also to the team I work with in my spare time:
Mike Agon,
9 References
[1] David Baraff, An Introduction to Physically Based Modeling,
1997;
http://www-2.cs.cmu.edu/~baraff/sigcourse/
[2] Mike Hommel, Pixel Collision Detection Between
RLE Sprites, 1999;
http://www.flipcode.com/tfiles/mike01.shtml
[3] Ulf Ekström, A 2d collision detection tutorial including a C implementation