Software and mathematics

Previous - Vector projection | Next - Lines |

Matrices are not a requirement for transforming positions or geometry. Often it is more efficient to build the needed formulas like we did, as allocating, building and multiplying matrices does not come cheap. Where matrices are most handy is when we have an hierarchy of components where a parent component influences the transformation of a child component. In that situation matrices are an indispensable tool. All the formulas presented here use the OpenGL conventions. This means we will post-multiply matrices and vectors. If for some reason you need matrices for pre-multiplication instead, you only need to transpose the given matrices.

When passing matrices to an API, make sure you know whether it uses row-major or column-major order. Row-major order matrices are stored one row after another. Like the following matrix.

With the indexes indicating the place where each element is in memory. Column-major order would be stored one column after another.

Both memory schemes have their advantages. However it has no impact on the actual mathematics. These are only two ways to index a matrix in memory. Code-wise this doesn’t have to make a difference if you use named fields. The following code

```
struct Matrix {
float a, d, g, b, e, h, c, f, i;
};
Matrix m;
float *column_major_matrix = &m.a;
```

would give you a column-major order matrix to pass to OpenGL, while your calculations would keep using the same field names as a row order matrix with sequential fields names. Just remember that mathematics wise, it doesn’t make a difference, OpenGL uses matrices mathematically like they are written here, it just stores it at different indices in memory.

Given the following matrix

The point or vector (x, y, w) can be transformed by calculating

Which is the matrix product of a matrix with a matrix. Matrices can only be multiplied if the amount of columns of the first matrix matches the amount of rows of the second. This is why we write our vector as a column. Keen observers will notice that the elements of our resulting vector are the dot products of the rows of the matrix with the input vector.

We are not going to use general matrices, but are going to focus on linear transformations. In our case, the last row of a matrix {g, h, i} is always {0, 0, 1} so we never need to store this row, and it’s values can be hard coded into multiplication formula.

You might be wondering what the w is doing here Since we are doing 2D, there shouldn’t be a third dimension. The w is a convenience in case you want to transform both points and vectors. A point would have w equal to 1, while a vector would use w equal to 0. This makes sure a point is translated and a vector not. Since we are going to transform points, we can keep w equal to 1.

```
function Transform:transform(x, y)
return x * self.a + y * self.b + self.c,
x * self.d + y * self.e + self.f
end
```

This matrix does exactly nothing to our input. Multiplying points or vectors with this matrix is like multiplying with 1.

```
function Transform:__init(values)
local matrix = values or {1, 0, 0, 0, 1, 0}
self.a, self.b, self.c, self.d, self.e, self.f =
matrix[1], matrix[2], matrix[3], matrix[4], matrix[5], matrix[6]
end
```

This is the same as adding the vector to our point.

```
function Transform.Translation(x, y)
return Transform({1, 0, x, 0, 1, y})
end
```

This is the formula we derived in angles, rotating around the origin.

```
function Transform.Rotation(angle)
local c = math.cos(angle)
local s = math.sin(angle)
return Transform({c, -s, 0, s, c, 0, })
end
```

This is multiplication with a scalar.

```
function Transform.Scale(x, y)
y = y or x
return Transform({x, 0, 0, 0, y, 0})
end
```

As an example, let’s revisit scaling from a given center. We can make a matrix that does this by combining 3 matrices.

Note that since we post-multiply, the matrix that is going to be applied first to the vector, is on the right. The vector follows a transformation path from right to left. In case we were pre-multiplying transformations, the vector would have been be a row matrix on the left, and the order of the matrices would be inverted and the matrices themselves be transposed.

Back to our post-multiplied transformation example. Multiplying the first two matrices gives us

Multiplying these we get

Applying this matrix to (x,y) gives us

after grouping the scaled terms, we get the previous formula to scale from a given center

This formula is of course several magnitudes more efficient than allocating, building and multiplying these three matrices. Only when we don’t know in advance what combination of transformations we are going to have to do, does it make sense to switch to matrices.

Instead of allocating, building and multiplying translation, rotation or scale matrices with our current transformation matrix, we can do better. Since we know the layout of these matrices in advance, we know which elements in our transformation matrix will be modified, and how. This allows us to only do the minimum amount of calculations needed

Applying a translation only affects the translation of the transform. However the translation itself is modified by the transform’s rotation and scale.

```
function Transform:translate(x, y)
self.c = self.c + x * self.a + y * self.b;
self.f = self.f + x * self.d + y * self.e;
end
```

Applying a rotation only affects the rotation and scale part of the transform. It is unaffected by the translation, nor does it modify the translation.

```
function Transform:rotate(angle)
local c = math.cos(angle)
local s = math.sin(angle)
self.a, self.b = self.a*c+self.b*s, -self.a*s+self.b*c
self.d, self.e = self.d*c+self.e*s, -self.d*s+self.e*c
end
```

Note that while this code works in lua, other languages might need temporaries.

Applying a rotation only affects the rotation and scale part of the transform. It is unaffected by the translation, nor does it modify the translation.

```
function Transform:scale(x, y)
y = y or x
self.a = self.a * x;
self.d = self.d * x;
self.b = self.b * y;
self.e = self.e * y;
end
```

The inverse matrix is the matrix for which if then . This matrix is very handy when creating editors for a game, or interaction, as the mouse or finger input needs the inverse camera transform. We’ll start with the inverse of the basic transformations. The inverse of the identity matrix is of course the identity matrix again.

We only need to translate in the opposite direction, so we switch the sign of the vector.

We need to rotate by the angle instead of . Since and we get

We need to inverse the scale factor. If we were scaling two times bigger, we need to scale two times smaller now.

For any general matrix

for which the determinant is not 0, we can calculate the inverse by calculating

The determinant of a matrix can be calculated by adding the product of the left-top to right-bottom diagonals and subtracting the products of the left-bottom to top-right diagonals. Another way is taking the sum of the top row elements multiplied by the determinants of the matrices obtained by removing the row and columns from which said elements are part. Either way gives us as determinant

That’s quite a lot of calculations for obtaining the inverse of a matrix. Luckily our transformation matrices are more specific, as the last row is always

If we take this into consideration, by replacing g, h, i with 0, 0, 1 respectively we get the following much simplified solution

The determinant can be simplified as well

Note that element i will always be 1 after division with the determinant. Also note that if there is no scale in the matrix, but only translation and rotation, the determinant will be 1.

```
function Transform:inverse()
local det = self.a*self.e-self.b*self.d
if det < 0.00001 and det > -0.00001 then return nil end
return Transform{
self.e/det, -self.b/det, (self.b*self.f-self.c*self.e)/det,
-self.d/det, self.a/det, (self.c*self.d-self.a*self.f)/det
}
end
```

This is very easy, as the translation has its own place in the matrix.

```
function Transform:getTranslation()
return self.c, self.f
end
```

The rotation is also still fairly easy, since we just need to get the sine and cosine. These are available in a, d, and b, e, we can use them with the arc tangents to obtain the angle.

Note that we strategically take a and d, not for example a and b. This is because both a and d are multiplied by the same factor. Since the arc tangent uses the slope, or d divided by a, this factor is eliminated.

```
function Transform:getRotation()
return math.atan2(self.d, self.a)
end
```

The scale poses a bit of a problem as we actually need to erase the rotation. Element a is equal to , while d is equal to . What we can do is make use of the fact that since is a normalized vector. If we write out , we have

Which we can write as

Extracting the common factor we get

So if we take the square root of the above formula we get

```
function Transform:getScale()
return math.sqrt(self.a * self.a + self.d * self.d)
math.sqrt(self.b * self.b + self.e * self.e)
end
```

If we want to transform an object by giving it a translation, rotation and scale, we need to do these individual transformations in the correct order. Two translations can be done in any order, as they are commutative. The same can be said for two rotations or two scales.

If however we do a translation after a scale, the translation will be influenced by the scale. Similarly if we scale before we rotate, the scale will use the old x and y axis instead of the rotated ones.

The correct order, for transforming an object, is to do the translation first, then the rotation and finally the scale.

```
function Object:transform()
translate(self.x, self.y)
rotate(self.angle)
scale(self.scale, self.scale)
end
```

Vertices emitted after these transformations will be first scaled in their local coordinate system. Then they will be rotated, and finally translated to their global position.

If we want a flexible anchor for scaling or rotating around, we need to add a translation so that the anchor becomes the local origin before scaling. We need to undo this translation afterwards so that our object is positioned correctly.

```
function Object:transform()
translate(self.x+self.anchorX, self.y+self.anchorY)
rotate(self.angle)
scale(self.scale, self.scale)
translate(-self.anchorX, -self.anchorY)
end
```

As you see we can combine our undo of the anchor with the positioning of the object, saving one transformation.

In a lot of cases, whether using transformations in a game scene, an animated character, or a GUI, there is a certain hierarchy of components where the transformation of a parent component influences the transformation of its child components. For example moving a window, will move its buttons as well.

When we look at one component, for example a button, we talk about its local transformation inside its parent, for example 10 pixels right and 20 down from the left top of the window, and its global transformation, the distance from the left top of the screen.

Now the question is, at drawing time, how do we get the global transformation to transform our vertices?

We could of course travel all the way to the parent, then travel the path in reverse while multiplying the local transformations of every component we meet, but that would mean all lot of overhead by multiplying the same transformations for every component.

We could travel the tree depth first starting from the root, and store the global matrix for each component. While that might cost us quite some additional memory, having the transformation matrix stored can be handy for inverse transformations in the case of clicking or selection.

If we want a more flexible system, we can use a transformation stack. We can pre-allocate this stack to the maximum depth we expect, and place an identity matrix at the top. When we want to do some transformations in a component, we first push a copy of the current stack top onto the stack, do our modifications and pop the copy from the stack when we’re done. Note that no actual allocations or deallocations happen as we merely change the pointer or index indicating the current top.

```
local TransformStack = class()
function TransformStack:__init(n)
n = n or 32
self._stack = {}
for i=1,n do table.insert(self._stack, Transform()) end
self._index = 1
self._top = self._stack[self._index]
end
function TransformStack:push()
if self._index == #self._stack then error("Transform stack is full") end
local from = self._stack[self._index].matrix
local to = self._stack[self._index+1].matrix
for i=1,6 do to[i] = from[i]; end
self._index = self._index + 1
self._top = self._stack[self._index]
end
function TransformStack:pop()
if self._index == 1 then error("Transform stack is empty") end
self._index = self._index - 1
self._top = self._stack[self._index]
end
function TransformStack:top()
return self._top
end
```

Since we want the center of our camera view on the center of the screen, we do an initial translation.

```
function Camera:transform()
translate(screenCenterX,screenCenterY)
end
function Camera:transformPoint(x,y)
return x+screenCenterX, y+screenCenterY
end
```

We pan by translating the world in the inverse direction of the camera. If the camera goes left, the world moves right relative to the camera.

```
function Camera:moveTo(x,y)
self.x = x
self.y = y
end
function Camera:moveBy(x,y)
self.x = self.x + x
self.y = self.y + y
end
function Camera:transform()
translate(screenCenterX-self.x, screenCenterY-self.y)
end
function Camera:transformPoint(x,y)
return x+screenCenterX-self.x, y+screenCenterY-self.y
end
```

If we want to zoom in, we use a scale factor greater than 1, making everything bigger. For zooming out, we use a scale smaller than 1, making everything smaller on the screen.

If we translate the camera as well, this needs to be done before scaling, which in case of post multiplied matrices means multiplying the translation matrix last.

```
function Camera:zoomTo(s)
self.zoom = s
end
function Camera:zoomBy(s)
self.zoom = self.zoom * s
function Camera:transform()
translate(screenCenterX, screenCenterY)
scale(self.zoom)
translate(-self.x, -self.y)
end
function Camera:transformPoint(x,y)
return screenCenterX+self.zoom*(x-self.x), screenCenterY+self.zoom*(y-self.y)
end
```

If we need rotation as well, we do this after translating and before scaling. In our case, since we probably scale uniformly, thus x and y by the same factor, the order of rotation and scale isn’t that important, however if you use different factors for x and y, you need to be careful.

```
function Camera:rotateTo(angle)
self.angle = angle
end
function Camera:rotateBy(angle)
self.angle = self.angle + angle
function Camera:transform()
translate(screenCenterX, screenCenterY)
scale(self.zoom)
rotate(-self.angle)
translate(-self.x, -self.y)
end
function Camera:transformPoint(x,y)
x, y = x-self.x, y-self.y
local c = math.cos(-self.angle)
local s = math.sin(-self.angle)
return screenCenterX + self.zoom*(c*x-s*y), screenCenterY + self.zoom*(s*x+c*y)
end
```

Let’s pretend we are making an RTS game, and we want to select units using the mouse. This is easy when world and screen space match, but what if the camera allows us to pan around the screen, zoom out or even rotate the world to see what’s behind those trees?

A naive thought would be to transform all units one by one to screen space and test whether our mouse coordinates, which are given in screen space, are inside the transformed collision shapes, be it circles, triangles, boxes or polygons.

A much better way would be to just transform our mouse coordinates to world space, since it only requires one point transform. This is where the inverse transform comes into play, as we only have the camera transformation from world to screen, in order to transform from screen to world, we need to calculate the inverse transformation. Note that it is still faster than transforming many objects to screen space. Also, if the camera isn’t moving during selection, the inverse doesn’t need to be calculated every frame.

```
function love.mousepressed(x, y, button, istouch)
x, y = stack.top().inverse().transform(x, y)
-- Check for all selectable entities whether they intersect with x, y
end
```

Previous - Vector projection | Next - Lines |