Making a 2D Physics Engine: The Math

Making a 2D Physics Engine: The Series

This is the first article in the Making a 2D Physics Engine Series.

1. Making a 2D Physics Engine: The Math
2. Making a 2D Physics Engine: Spaces and Bodies
3. Making a 2D Physics Engine: Shapes, Worlds and Integration
4. Making a 2D Physics Engine: Mass, Inertia and Forces

Introduction

Why do we need physics in games?

Physics in games helps us simulate a semi-realistic world with which gamers can easily relate to. From the first Donkey Kong game to the latest The Last Of Us, physics help materialize a world. Physics can be realistic or unrealistic depending on the type of game you're developing. This series of articles will hopefully give you an idea along with the algorithms of how physics engines work and give you enough knowledge to implement your own version of Box2D from scratch!

What do I need to know to simulate physics in my games?

You can always choose to code your own physics engine (which is the main focus of this series of articles) or you can use some commercially or freely available engines like NVIDIA's PhysX Engine and Havok Physics that you can use in your projects. All game engines come with a physics engine bundled with them, though you still will have to implement game-specific physical entities/simulations such as a vehicle engine, boat, buoyancy, air resistance, and so on. All of these require knowledge in vectors and matrices in both 2D and 3D. This article will go through some of the more important concepts of vectors and matrices required for implementing 2D physics in your games.

Vectors

Let's start with the most basic concept of points and direction in 'n' dimensions: Vectors.

What are Vectors?

A vector is a geometric object used to "carry" point A to point B. It has a magnitude as well as a direction. It is commonly used to represent "vector" quantities like forces, velocities which were talked about in high school physics.

Representing a Vector

A Vector in the 'n'th dimension has 'n' components. 2D, 3D and 4D vectors are commonly used. A vector can be represented as a column matrix, i.e. an nD vector is represented as an n*1 matrix. It can also be represented as an ordered set, like so: (\(a_1, a_2, \ldots a_{n-1}, a_n)\)

The components of any vector of 2D or 3D vectors are generally represented by the x, y and z alphabets which also represent the corresponding cartesian coordinates of that vector.

The contents below are targeted towards 2D vectors, but can easily be extended to 3D vectors.

Vector Operations

Length of a Vector

The length (or magnitude) of a vector is equal to the Pythagorean distance between it and the origin (zero vector). It can be represented as follows: \(\mathbf{||A||} = \sqrt{a_1^2 + a_2^2 + \ldots + a_n^2}\)

In code, it can be defined as follows:

float length(Vec2 vec)
    return sqrt(vec.x * vec.x + vec.y * vec.y)

In many cases which require comparision of distances, the expensive sqrt operation is avoided and the square of the length of the vector is used instead.

float sqrLength(Vec2 vec)
    return vec.x * vec.x + vec.y * vec.y

Normalization of Vector (Unit Vector)

A unit vector is a vector whose length is 1. It is commonly used to represent directions like normals and tangents. To get the unit vector (direction) for a specific vector, that vector is divided by it's length. This process is called normalization.

Vec2 normalized(Vec2 vec)
    return vec * (1 / length(vec))

Multiplication of Vectors

Vectors can be multiplied by a scalar as well as another vector of the same dimensions.

Multiplication of a Vector with a scalar

Vectors can be scaled by a scalar, i.e. each of its components will be multiplied by the scalar.

Multiplication of a Vector with another vector

Two vectors can be multiplied using the Dot (Scalar) Product or Cross (Vector) Product.

Dot Product

The dot product is the sum of the component-wise product of two vectors. It returns a scalar.

The dot product is one of the most used vector operations as it is closely related to the cosine of the angle between the two vectors.

cos theta = A dot B / (length(A) * length(B))

or

cos theta = normalized(a) dot normalized(b)

One important thing to remember is that if two vectors are perpendicular to each other, their dot product will be equal to zero (as cos theta = 0).

Cross Product

The cross product is a popular operation in 3D. The cross product, denoted a × b, is a vector perpendicular to both a and b and is defined as

Where n is the vector perpendicular to both a and b.

The cross product is properly defined only for 3D vectors. But since 2D vectors can be considered as 3D vectors lying on the XY plane, the cross product of any two 2D vectors can be defined as the cross product of their 3D planar representations, resulting in a vector along the Z axis which can be represented as a scalar (representing the magnitude of the Z axis vector).

Similarly, a 2D vector crossed with a scalar will result in another 2D vector perpendicular to the original 2D vector.

The cross product for 2D vectors looks as follows:

// Two crossed vectors return a scalar pointing in the z direction
float cross(Vector2 a, Vec2 b)
  return a.x * b.y - a.y * b.x;
 
//A vector crossed with a scalar (z-axis) will return a vector on the 2D Cartesian plane
Vector2 cross(Vector2 a, float s)
  return Vec2(s * a.y, -s * a.x);
 
Vector2 cross(float s, Vector2 a)
  return Vec2(-s * a.y, s * a.x);

Vector2 Struct Pseudocode

In the programming language of your choice, the Vector2 structure should look as follows. You can change the names according to your choice.

struct Vector2 {
    float x, y;

    float length() {
        return sqrt(x * x + y * y);
    }
    float sqrLength() {
        return x * x + y * y;
    }
    
    Vector2 operator *(Vector2 v, float s) {
        return Vector2(v.x * s, v.y * s);
    }
    
    void normalize() {
        float inv_len = 1 / length();
        x *= inv_len; y *= inv_len;
    }
    
    float dot(Vector2 a, Vector2 b) {
        return a.x * b.x + a.y * b.y;
    }
    
    // Two crossed vectors return a scalar pointing in the z direction
    float cross(Vector2 a, Vec2 b) {
        return a.x * b.y - a.y * b.x;
    }
    //A vector crossed with a scalar (z-axis) will return a vector on the 2D Cartesian plane
    Vector2 cross(Vector2 a, float s) {
        return Vec2(s * a.y, -s * a.x);
    }
    Vector2 cross(float s, Vector2 a) {
        return Vec2(-s * a.y, s * a.x);
    }
}

Note that all instances the Vector2 structure, like all primitives in most languages, should be copied by value and not by reference, unless explicitly required. Reference copying of vectors will lead to unnecessary problems and invisible bugs.

Matrices

A matrix is a rectangular array—of numbers, symbols, or expressions, arranged in rows and columns—that is treated in certain prescribed ways. Matrices are generally used in Computer Graphics and physics to transform a point from one basis to another, which includes rotation, translation and scaling.

In this article I will only be covering 2x2 matrices which are used to rotate 2D vectors.

Why Matrices?

If you remember high school mathematics, multiplication of a \(l \times m\) matrix by a \(m \times n\) matrix results in a \(l \times n\) matrix. In this case, a 2x2 matrix multiplied by a vector represented as a 2x1 matrix gives another 2x1 matrix (2D vector). This makes it mathematically easier and computationally efficient to transform a vector. An important transformation, rotation, will be covered in the next few sub-sections.

Rotation in 2D

Each object has an orientation. In terms of rotation, orientation is synonymous with position (i.e the rotation of the object at an instant), angular velocity (the rate of change of orientation) is synonymous with velocity and torque with force. Since objects in 2D can only rotate about the imaginary z-axis, the orientation of a 2D body is a scalar which represents the rotation about the z-axis in radians. Since the distance of the point from the origin must stay constant (by the definition of rotation in angular kinematics), a rotating point will always lie on the circumference of a circle with center as the origin and radius equal to the distance from the origin.

Rotating a Vector by some angle

In a 2D Cartesian plane, for some vector P(x, y), where the angle through which P should be rotated is "theta" then

This comes directly from the trigonometric compound angle formulae after converting the vectors into polar form.

Using Matrices to Rotate a Vector

Look at the above equation again. I've presented it in matrix form so that it's easier to obtaining the rotation matrix after creating a matrix equation. Try and find the rotation matrix yourself before moving ahead.

The formula for matrix-matrix multiplication for a 2x2 and 2x1 matrix will look somewhat like this:

Now compare this result to the result of the previous equation.

From the above relation, we can conclude that

Matrix2 Structure Pseudocode

A 2*2 matrix structure would look as follows:

struct Matrix2
{
    float m00, m01
    float m10, m11;
    
    //Create from angle in radians
    void set(real radians) {
        real c = cos(radians);
        real s = sin(radians);

        m00 = c; m01 = -s;
        m10 = s; m11 =  c;
    }
    
    Matrix2 transpose() {
        return Matrix2(m00, m10,
                       m01, m11);
    }
    
    Vector2 operator*(Vector2 rhs) {
        return Vec2(m00 * rhs.x + m01 * rhs.y, m10 * rhs.x + m11 * rhs.y);
    }

    Matrix2 operator*(Matrix2 rhs ) {
    return Mat2(
      m00 * rhs.m00 + m01 * rhs.m10, m00 * rhs.m01 + m01 * rhs.m11,
      m10 * rhs.m00 + m11 * rhs.m10, m10 * rhs.m01 + m11 * rhs.m11);
    }
}

Just like the Vector2 structure, the instances of the Matrix2 structure must also be copied by value.

What Next?

The next article will get you started on making a very basic physics engine with the code. It will include concepts such as shapes, bodies and integration of velocities and forces. I hope to cover collision detection, collision resolution, concave shapes, broad phasing, raycasting, extending to 3D and other such concepts in future articles. I will try to split it into as many articles as I can because it can be a lot to take in!

If you have any comments/suggestions please do let me know!

History

13 Sep 2015: Initially posted

5 Nov 2017: Language and content improvements