Hand picked articles on Flash Development and Software Design: April 2013

There are many reasons you might want to create a custom physics engine: first, learning and honing your skills in mathematics, physics and programming are great reasons to attempt such a project; second, a custom physics engine can tackle any sort of technical effect the creator has the skill to create. In this article I would like to provide a solid introduction on how to create a custom physics engine entirely from scratch. Physics provides a wonderful means for allowing a player to immerse themselves within a game. It makes sense that a mastery of a physics engine would be a powerful asset for any programmer to have at their disposal. Optimizations and specializations can be made at any time due to a deep understanding of the inner workings of the physics engine. By the end of this tutorial the following topics will have been covered, in two dimensions:

Simple collision detection
Simple manifold generation
Impulse resolution

Here’s a quick demo:

Prerequisites

This article involves a fair amount of mathematics and geometry, and to a much lesser extent actual coding. A couple prerequisites for this article are:

A basic understanding of simple vector math
The ability to perform algebraic math

Collision Detection

There are quite a few articles and tutorials throughout the internet, including here on Tuts+, that cover collision detection. Knowing this, I would like to run through the topic very quickly as this section is not the focus of this article.

Axis Aligned Bounding Boxes

An Axis Aligned Bounding Box (AABB) is a box that has its four axes aligned with the coordinate system in which it resides. This means it is a box that cannot rotate, and is always squared off at 90 degrees (usually aligned with the screen). In general it is referred to as a “bounding box” because AABBs are used to bound other more complex shapes.

An example AABB. The AABB of a complex shape can be used as a simple test to see if more complex shapes inside the AABBs can possibly be intersecting. However in the case of most games the AABB is used as a fundamental shape, and does not actually bound anything else. The structure of your AABB is important. There are a few different ways to represent an AABB, however this is my favorite:

struct AABB
{
  Vec2 min;
  Vec2 max;
};

This form allows an AABB to be represented by two points. The min point represents the lower bounds of the x and y axis, and max represents the higher bounds – in other words, they represent the top left and bottom right corners. In order to tell whether two AABB shapes are intersecting you will need to have a basic understanding of the Separating Axis Theorem (SAT). Here’s a quick test taken from Real-Time Collision Detection by Christer Ericson, which makes use of the SAT:

bool AABBvsAABB( AABB a, AABB b )
{
  // Exit with no intersection if found separated along an axis
  if(a.max.x < b.min.x or a.min.x > b.max.x) return false
  if(a.max.y < b.min.y or a.min.y > b.min.y) return false

  // No separating axis found, therefor there is at least one overlapping axis
  return true
}

Circles

A circle is represented by a radius and point. Here is what your circle structure ought to look like:

struct Circle
{
  float radius
  Vec position
};

Testing for whether or not two circles intersect is very simple: take the radii of the two circles and add them together, then check to see if this sum is greater than the distance between the two circles. An important optimization to make here is get rid of any need to use the square root operator:

float Distance( Vec2 a, Vec2 b )
{
  return sqrt( (a.x + b.x)^2 + (a.y + b.y)^2 )
}

bool CirclevsCircleUnoptimized( Circle a, Circle b )
{
  float r = a.radius + b.radius
  return r < Distance( a.position, b.position )
}

bool CirclevsCircleOptimized( Circle a, Circle b )
{
  float r = a.radius + b.radius
  r *= r
  return r < (a.x + b.x)^2 + (a.y + b.y)^2
}

In general multiplication is a much cheaper operation than taking the square root of a value.

Impulse Resolution

Impulse resolution is a particular type of collision resolution strategy. Collision resolution is the act of taking two objects who are found to be intersecting and modifying them in such a way as to not allow them to remain intersecting. In general an object within a physics engine has two main degrees of freedom (in two dimensions): movement in the xy plane and rotation. In this article we implicitly restrict rotation and use just AABBs and Circles, so the only degree of freedom we really need to consider is movement along the xy plane. By resolving detected collisions we place a restriction upon movement such that objects cannot remain intersecting one another. The idea behind impulse resolution is to use an impulse (instantaneous change in velocity) to separate objects found colliding. In order to do this the mass, position, and velocity of each object must be taken into account somehow: we want large objects colliding with smaller ones to move a little bit during collision, and to send the small objects flying away. We also want objects with infinite mass to not move at all.

Simple example of what impulse resolution can achieve. In order to achieve such effects and follow along with natural intuition of how objects behave we’ll use rigid bodies and a fair bit of math. A rigid body is just a shape defined by the user (that is, by you, the developer) that is implicitly defined to be non-deformable. Both AABBs and Circles in this article are non-deformable, and will always be either an AABB or Circle. No squashing or stretching allowed. Working with rigid bodies allows for a lot of math and derivations to be heavily simplified. This is why rigid bodies are commonly used in game simulations, and why we’ll be using them in this article.

Our Objects Collided – Now What?

Assuming we have two shapes found to be intersecting, how does one actually separate the two? Lets assume our collision detection provided us with two important pieces of information:

Collision normal
Penetration depth

In order to apply an impulse to both objects and move them apart, we need to know what direction to push them and by how much. The collision normal is the direction in which the impulse will be applied. The penetration depth (along with some other things) determine how large of an impulse will be used. This means the only value that needs to be solved for is the magnitude of our impulse. Now let’s go on a long trek to discover how we can solve for this impulse magnitude. We’ll start with our two objects that have been found to be intersecting:

Equation 1

\[ V^{AB} = V^B - V^A \] Note that in order to create a vector from position A to position B, you must do: endpoint - startpoint. \(V^{AB}\) is the relative velocity from A to B. This equation ought to be expressed in terms of the collision normal \(n\) – that is, we would like to know the relative velocity from A to B along the collision normal’s direction:

Equation 2

\[ V^{AB} \cdot n = (V^B - V^A) \cdot n \] We are now making use of the dot product. The dot product is simple; it is the sum of component-wise products:

Equation 3

\[ V_1 = \begin{bmatrix}x_1 \\y_1\end{bmatrix}, V_2 = \begin{bmatrix}x_2 \\y_2\end{bmatrix} \\ V_1 \cdot V_2 = x_1 * x_2 + y_2 * y_2 \] The next step is to introduce what is called the coefficient of restitution. Restitution is a term that means elasticity, or bounciness. Each object in your physics engine will have a restitution represented as a decimal value. However only one decimal value will be used during the impulse calculation. To decide what restitution to use (denoted by \(e\) for epsilon), you should always use the lowest restitution involved in the collision for intuitive results:

// Given two objects A and B
e = min( A.restitution, B.restitution )

Once \(e\) is acquired we can place it into our equation solving for the impulse magnitude. Newton’s Law of Restitution states the following:

Equation 4

\[V' = e * V \] All this is saying is that the velocity after a collision is equal to the velocity before it, multiplied by some constant. This constant represents a “bounce factor”. Knowing this, it becomes fairly simple to integrate restitution into our current derivation:

Equation 5

\[ V^{AB} \cdot n = -e * (V^B - V^A) \cdot n \] Notice how we introduced a negative sign here. In Newton’s Law of Restitution, \(V’\), the resulting vector after the bounce, is actually going in the opposite direction of V. So how do we represent opposite directions in our derivation? Introduce a negative sign. So far so good. Now we need to be able to express these velocities while under the influence of an impulse. Here’s a simple equation for modify a vector by some impulse scalar \(j\) along a specific direction \(n\):

Equation 6

\[ V' = V + j * n \] Hopefully the above equation makes sense, as it is very important to understand. We have a unit vector \(n\) which represents a direction. We have a scalar \(j\) which represents how long our \(n\) vector will be. We then add our scaled \(n\) vector to \(V\) to result in \(V’\). This is just adding one vector onto another, and we can use this small equation to apply an impulse of one vector to another. There’s a little more work to be done here. Formally, an impulse is defined as a change in momentum. Momentum is mass * velocity. Knowing this, we can represent an impulse as it is formally defined like so:

Equation 7

\[ Impulse = mass * Velocity \\ Velocity = \frac{Impulse}{mass} \therefore V' = V + \frac{j * n}{mass}\] The three dots in a small triangle (\(\therefore\)) can be read as “therefore”. It is used to show that the thing beforehand can be used to conclude that whatever comes next is true. Good progress has been made so far! However we need to be able to express an impulse using \(j\) in terms of two different objects. During a collision with object A and B, A will be pushed in the opposite direction of B:

Equation 8

\[ V'^A = V^A + \frac{j * n}{mass^A} \\ V'^B = V^B - \frac{j * n}{mass^B} \] These two equations will push A away from B along the direction unit vector \(n\) by impulse scalar (magnitude of \(n\)) \(j\). All that is now required is to merge Equations 8 and 5. Our resulting equation will look something like this:

Equation 9

\[ (V^A - V^V + \frac{j * n}{mass^A} + \frac{j * n}{mass^B}) * n = -e * (V^B - V^A) \cdot n \\ \therefore \\ (V^A - V^V + \frac{j * n}{mass^A} + \frac{j * n}{mass^B}) * n + e * (V^B - V^A) \cdot n = 0 \] If you recall, the original goal was to isolate our magnitude. This is because we know what direction to resolve the collision in (assumed given by the collision detection), and only have left to solve the magnitude of this direction. The magnitude which is an unknown in our case is \(j\); we must isolate \(j\) and solve for it.

Equation 10

\[ (V^B - V^A) \cdot n + j * (\frac{j * n}{mass^A} + \frac{j * n}{mass^B}) * n + e * (V^B - V^A) \cdot n = 0 \\ \therefore \\ (1 + e)((V^B - V^A) \cdot n) + j * (\frac{j * n}{mass^A} + \frac{j * n}{mass^B}) * n = 0 \\ \therefore \\ j = \frac{-(1 + e)((V^B - V^A) \cdot n)}{\frac{1}{mass^A} + \frac{1}{mass^B}} \] Whew! That was a fair bit of math! It is all over for now though. It’s important to notice that in the final version of Equation 10 we have \(j\) on the left (our magnitude) and everything on the right is all known. This means we can write a few lines of code to solve for our impulse scalar \(j\). And boy is the code a lot more readable than mathematical notation!

void ResolveCollision( Object A, Object B )
{
  // Calculate relative velocity
  Vec2 rv = B.velocity - A.velocity

  // Calculate relative velocity in terms of the normal direction
  float velAlongNormal = DotProduct( rv, normal )

  // Do not resolve if velocities are separating
  if(velAlongNormal > 0)
    return;

  // Calculate restitution
  float e = min( A.restitution, B.restitution)

  // Calculate impulse scalar
  float j = -(1 + e) * velAlongNormal
  j /= 1 / A.mass + 1 / B.mass

  // Apply impulse
  Vec2 impulse = j * normal
  A.velocity -= 1 / A.mass * impulse
  B.velocity += 1 / B.mass * impulse
}

There are a few key things to note in the above code sample. The first thing is the check on Line 10, if(VelAlongNormal > 0). This check is very important; it makes sure that you only resolve a collision if the objects are moving towards each other.

Two objects collide, but velocity will separate them next frame. Do not resolve this type of collision. If objects are moving away from one another we want to do nothing. This will prevent objects that shouldn’t actually be considered colliding from resolving away from one another. This is important for creating a simulation that follows human intuition on what should happen during object interaction. The second thing to note is that inverse mass is computed multiple times for no reason. It is best to just store your inverse mass within each object and pre-compute it one time:

A.inv_mass = 1 / A.mass

Many physics engines do not actually store raw mass. Physics engines often times store inverse mass and inverse mass alone. It just so happens that most math involving mass is in the form of 1/mass.The last thing to note is that we intelligently distribute our impulse scalar \(j\) over the two objects. We want small objects to bounce off of big objects with a large portion of \(j\), and the big objects to have their velocities modified by a very small portion of \(j\). In order to do this you could do:

float mass_sum = A.mass + B.mass
float ratio = A.mass / mass_sum
A.velocity -= ratio * impulse

ratio = B.mass / mass_sum
B.velocity += ratio * impulse

It is important to realize that the above code is equivalent to the ResolveCollision() sample function from before. Like stated before, inverse masses are quite useful in a physics engine.

Hand picked articles on Flash Development and Software Design

Monday, April 8, 2013

Tutorial: Debugging Native Extensions

Saturday, April 6, 2013

How to Create a Custom 2D Physics Engine: The Basics and Impulse Resolution