Ming-Lun "Allen" Chou | 周明倫

This post is part of my Game Math Series.

A quaternion is a very useful mathematical object devised by Sir William Rowan Hamilton as an extension to complex numbers. It is often used to compactly represent 3D orientations with just four floating-point numbers, as opposed to using a 3-by-3 matrix that contains nine floating-point numbers, and it has other nice properties that I will talk about later.

As its name suggests, a quaternion is composed of four components, one in the real part, and the other three in the imaginary part. A quaternion is usually denoted as:

where is the real part, denotes the three imaginary axes, and denotes the three imaginary components.

For brevity, I will use the notation below to represent a quaternion:

The Fundamental Formula for Quaternions

Below is the fundamental formula that governs the arithmetics of quaternions:

With this formula, we can derive the following identities:

Continue reading →

This post is part of my Game Math Series.

I first saw this technique in an article, Hacking Quaternions, written by Jonathan Blow (author of Braid).

To normalize a vector, you divide its individual components by its length.

const Vec3 Normalize(const Vec3 &v)
{
  const float len_sq = v.x * v.x + v.y * v.y + v.z * v.z;
  const float len_inv = 1.0f / std::sqrt(len_sq);
  return Vec3(v.x * len_inv, v.y * len_inv, v.z * len_inv);
}

The bottle neck of this function is the one divided by a square root, since the square root function is generally not fast. We can do better by using a polynomial approximation of the function around if all we want is to re-normalize unit vectors, which is a very common scenario in games.

Jonathan Blow says that it is more than enough to approximate the function with a polynomial of degree 1 (a straight line); for demonstrative purposes, however, I will show how to approximate around using a polynomial of degree 2 (a quadratic curve). I will use the method covered in this post.

Our polynomial of degree 2 includes three terms:

Continue reading →

This post is part of my Game Math Series.

We have seen how to approximate a function using polynomials in this post. A good candidate for polynomial approximation would be the sine function, for it is used a lot in games and is not a cheap function to call. This is essentially the same task as approximating the consine curve, since the cosine curve is just a shifted sine curve.

The sine curve is periodic, so will just focus on the domain

We will first try to match a quarter of the sine curve, a downward “hill”.

Continue reading →

This post is part of my Game Math Series.

Polynomials

A polynomial is an expression consisting of linear combination of products of variables raised to non-negative integer powers. In this post, I will specifically focus on polynomials of a single variable, namely polynomials of the form:

The polynomial above are said to have degree if the coefficient is non-zero.

Polynomial Curves

We can create curves with polynomials by using the equation .

For instance, we can create a parabola with :

Continue reading →

This post is part of my Game Math Series.

Splitting Matrices into Blocks

When performing matrix multiplication, we can split matrices into “blocks”. The matrix multiplication can then be performed as if each block is a single matrix element, given that we split the matrices in a way that the multiplication of block matrices are of legal dimensions.

For instance, a product of two 4-by-4 matrices can be viewed as a product of 2-by-2 matrices, where each matrix element is a 2-by-2 block matrix. Since a 2-by-2 matrix can be legally multiplied by another 2-by-2 matrix, such splitting scheme is valid.

Let’s look at an example with numbers:

We can split each of these matrices into four 2-by-2 block matrices:

where , , and .

Continue reading →

This post is part of my Game Math Series.

Definition of Matrix Multiplication

Let and be a -by- matrix and an -by- matrix, respectively. Let denote the element in the matrix on row and column (zero-based indexing), “element (, )” for short.

From the definition of matrix multiplication, we know that:

Essentially, element (, ) of the matrix product is the dot product of -th row from and -th column from .

We can compute matrix multiplication by performing one dot product per element in the resulting matrix product . However, there are two alternative ways to look at the matrix multiplication operation that can sometimes make your life easier. I learned these neat tips from the “Linear Algebra and Its Applications” course when I was studying at National Taiwan University back in Taiwan.

Linear Combination of Columns

The -th column of the matrix product is a linear combination of columns from the left matrix , where the coefficients of linear combination are from the -th column of the right matrix .

Continue reading →