Learn 3D Math made by the GPU by Coding a 3D Engine on CPU

wqaxs36, 13 Nov 2018

This article will explain you the basic 3D math applied on video games.

Download Demo - 1.8 MB

(You need Visual Studio 2017 to compile the project and a CPU that support AVX instructions)

Introduction

This article will help you to understand how 3D calculations are made inside the GPU.

But also to make a 3D Engine for voxel.

A voxel is just a point within a space, like an atom that composes the material, it's my own definition after, for the other engine, voxel are just cube of pixels like Minecraft and I don't use this definition for my voxel engine.

Also, this 3D engine does not use matrices calculations, it uses the linear equation. I do that just because I don't like matrices, it's out of my understanding of math concept.

Background

This article was possible with my wish (2010) to see a game with texture and object built only with voxel.

Using the Code

First of all, we need to ask few questions before:

What is a space?
what is an axis?
What is a plane?
what is a dimension?
What are trigonometric functions?
What is a vector?
What is a matrix?
What is a rotation and translation?

Now let's give anwsers to these questions:

A space is defined by a number of axes in unique directions that form the dimensions of the space.

A plane is formed by 2 axes/2D space.

And to form an axis, we use mathematical equations as additions and trigonometric functions where each number is visually a coordinate within the axis.

A vector is a point into the space localized by coordinates on the different axes that compose the space.

A 1D space is represented by a line in one direction/axis where X represents each point of this line, it's its coordinate: X ----------------------------

To add an object in a 1D space, we just need X as coordinate for the object's point and to move this object, just apply X = X + Object[Point][X].

-3 -2 -1 0 +1 +2 +3 X --|---|---|---|---|---|---|--

By consequence, the object moves within the same line.

A translation is done within a line, 1D space, so we have 1 translation possible on X-axis.

A 2D space is just a 1D space with another line in a direction at 90° of the X-axis where Y represents it:

To add an object into this 2D space, we need to set 2 coordinates for each point of the object and to move the object, we apply an addition like we did before for translate the object on X or Y-axis.

But we can also rotate the object around the center of the 2 axis, for doing that, an addition is not enough, we need to call a math operator that is designed for rotation calculations.

A rotation is done within a plane, 2D space, so we have 1 rotation possible around the center of the two axis.

This math operator are the trigonometric functions: sin() and cos() that take the angle between the two lines: [center, object's point] and X-axis for cos() and Y-axis for sin().

Visually, I have an object point at 0° and x = 1, y = 0 and we apply a rotation of +90° (anticlockwise) around the center, the result is x = 0, y = 1.

And the calculus to found this result is:

x' = x.cos(90) - y.sin(90)
y' = x.sin(90) + y.cos(90)

It's quit easy to retrieve this equation from scratch, it's what I did and surprisingly I seen that this equation was the linear form of the Z rotation matrix.

Here's how I did it:

- We have a 2D XY circle with a diameter of 8.

- We set 1 point and rotate it and we try to retrieve the equation of its new locations, we will found the final equation once we operate on a couple of different XY combinations.

- Let's being with P(4, 0) a red point:

- Now we rotate this point of 90° and try to find the equation to find its new location, visually the result to find is P(0, 4):

X = sin(θ) = 1 ❌
X = cos(θ) = 0 ✔

Y = cos(θ) = 0 ❌
Y = sin(θ) = 1 ❌✔
Y = 4 × sin(θ) = 4 ✔

- So for P(4, 0) and θ = 90 we have:

X = cos(θ)
Y = 4 × sin(θ)

- Try with any other angles for P(4, 0) and different X coordinates (use mathsisfun for that), you will find the same equations, with 4 × for X, but it's not alterate the final equation:

X' = 4 × cos(θ) = X × cos(θ)
Y' = 4 × sin(θ) = X × sin(θ)

- Now we set the red point at P(0, 4):

- We rotate this point of 90°, visually the result is P(-4, 0):

X = cos(θ) = 0 ❌
X = sin(θ) = 1 ❌✔
X = 4 × -sin(θ) = -4 ✔

Y = sin(θ) = 1 ❌
Y = cos(θ) = 0 ✔

- So for P(0, 4) and θ = 90 we have:

X = 4 × -sin(θ)
Y = cos(θ)

- Try with any other angles for P(0, 4) and different Y coordinates, you will find the same equations, with 4 × for Y, but it's not alterate the final equation:

X = 4 × -sin(θ) = Y × -sin(θ)
Y = 4 ×  cos(θ) = Y ×  cos(θ)

- Now let's summary:

 _____ ________________ ________________
|     |                |                |
|  θ  |     P(X, 0)    |     P(0, Y)    |
|_____|________________|________________|
|     |                |                |
|  θ  | X = X × cos(θ) | X = Y × -sin(θ)|
|     | Y = X × sin(θ) | Y = Y ×  cos(θ)|
|_____|________________|________________|

As we can see different XY combinations generate different equations, so let's work on X and Y set above 0:

- Hence we set the red point at P(2, 4×√3/2):

- Now we rotate this point of 30°, visually the result to find is P(0, 4):

X = sin(θ) = 0.5  ❌
X = cos(θ) = √3/2 ❌

Y = sin(θ) = 0.5  ❌
Y = cos(θ) = √3/2 ❌

We have a problem, none of the trigonometric functions work, so we need to find the solution away while still working with sin() and cos().

Let's review the previous equations found:

 _____ ________________ ________________
|     |                |                |
|  θ  |     P(X, 0)    |     P(0, Y)    |
|_____|________________|________________|
|     |                |                |
|  θ  | X = X × cos(θ) | X = Y × -sin(θ)|
|     | Y = X × sin(θ) | Y = Y ×  cos(θ)|
|_____|________________|________________|

These are strange equations what we have, what if we have P(X, Y), it should be a mix of the both equations:

X' = X × cos(θ) X = Y × -sin(θ)
Y' = X × sin(θ) Y = Y ×  cos(θ)

X' = X × cos(θ)     Y × -sin(θ)
Y' = X × sin(θ)     Y ×  cos(θ)

Let's see if an addition works:

X' = X × cos(θ) + Y × -sin(θ)
     X × cos(θ) - Y ×  sin(θ)
Y' = X × sin(θ) + Y ×  cos(θ)

X = 2 × cos(θ) - 4×√3/2 × sin(θ) = 0 ✔
Y = 2 × sin(θ) + 4×√3/2 × cos(θ) = 4 ✔

Perfect, this equation works and you can try with any other angles for P(2, 4×√3/2) and XY coordinates, you will find the same result as visually, so at the end, the final equations on a XY plane is:

X' = X × cos(θ) - Y × sin(θ)
Y' = X × sin(θ) + Y × cos(θ)

But at the end, let's remove the doubt about P(X, 0) and P(0, Y):

- For P(4, 0), we apply a rotation of 90°, visually the result to find is P(0, 4):

X' = 4 × cos(θ) - 0 ×  sin(θ) = 0 ✔
Y' = 4 × sin(θ) + 0 ×  cos(θ) = 4 ✔

- For P(0, 4), we apply a rotation of 90°, visually the result to find is P(-4, 0):

X' = 0 × cos(θ) - 4 ×  sin(θ) = -4 ✔
Y' = 0 × sin(θ) + 4 ×  cos(θ) =  0 ✔

Perfect, all is working, you can try with other coordinates for the both combinations, you will find the same result.

This equation is also surprisingly (as we said) just a linear form of the Z rotation (XZ plane rotation matrix) matrix, multiply by the object point called vector: (phi is the angle around the axis in the context), where Z is the center of the 2 axis)

Rotation matrix on z:                              Vector:
 ______________ ______________ ______________       ______________
|              |              |              |     |              |
|  cos(phi_z)  | -sin(phi_z)  |       0      |     |       x      |
|______________|______________|______________|     |______________|
|              |              |              |     |              |
|  sin(phi_z)  |  cos(phi_z)  |       0      |  ×  |       y      |
|______________|______________|______________|     |______________|
|              |              |              |     |              |
|       0      |       0      |       1      |     |       z      |
|______________|______________|______________|     |______________|

And a 3D space is 2D space with another axis called Z and at 90° of the XY plan.

The moves possible are translation (addition equation) and rotation (sin and cos).

But now rotations are in number of 3, around Z, around X and around Y.

Because as we said before, a rotation is made on a 2D plane, but now we have a mix of 3x 2D space/plane:

- X/Y, Y/Z and Z/X.

So we need to gather all the rotation matrices and use them.

X Rotation Matrix (XY plane rotation matrix)

 ______________ ______________ ______________
|              |              |              |
|       1      |       0      |       0      |
|______________|______________|______________|
|              |              |              |
|       0      |  cos(phi_x)  | -sin(phi_x)  |
|______________|______________|______________|
|              |              |              |
|       0      |  sin(phi_x)  |  cos(phi_x)  |
|______________|______________|______________|

Y Rotation Matrix (YZ plane rotation matrix)

 ______________ ______________ ______________
|              |              |              |
|  cos(phi_y)  |       0      | -sin(phi_y)  |
|______________|______________|______________|
|              |              |              |
|       0      |       1      |       0      |
|______________|______________|______________|
|              |              |              |
|  sin(phi_y)  |       0      |  cos(phi_y)  |
|______________|______________|______________|

Z Rotation Matrix (XZ plane rotation matrix)

 ______________ ______________ ______________
|              |              |              |
|  cos(phi_z)  | -sin(phi_z)  |       0      |
|______________|______________|______________|
|              |              |              |
|  sin(phi_z)  |  cos(phi_z)  |       0      |
|______________|______________|______________|
|              |              |              |
|       0      |       0      |       1      |
|______________|______________|______________|

But we have a problem, if we are doing that, we will not be able to rotate an object around XYZ axis together, it's one rotation on one axis only with other angles set as "zero" because they are not present in the matrix chosen.

To fix that, we need to form 1 single matrix by multiplying XYZ matrices together (mul's order matter).

So instead having 3 rotations on 3 x 2D plane, we will have only 1 rotation for a 3D space.

XYZ Rotation Matrix (XY YZ XZ planes rotation matrix)

 _____________________________________ _____________________________________ _________________________
|                                     |                                     |                         |
|       cos(phi_y) × cos(phi_z)       |       cos(phi_y) × -sin(phi_z)      |        -sin(phi_y)      |
|_____________________________________|_____________________________________|_________________________|
|                                     |                                     |                         |
|-sin(phi_x) × sin(phi_y) × cos(phi_z)| sin(phi_x) × sin(phi_y) × sin(phi_z)| -sin(phi_x) × cos(phi_y)|
|    + cos(phi_x) × sin(phi_z)        |     + cos(phi_x) × cos(phi_z)       |                         |
|_____________________________________|_____________________________________|_________________________|
|                                     |                                     |                         |
|cos(phi_x) × sin(phi_y) × cos(phi_z) |cos(phi_x) × sin(phi_y) × -sin(phi_z)|  cos(phi_x) × cos(phi_y)|
|    + sin(phi_x) × sin(phi_z)        |    + sin(phi_x) × cos(phi_z)        |                         |
|_____________________________________|_____________________________________|_________________________|

Now, we just need to multiply this matrix to the vector point of the object to be able to rotate the object around XYZ axis.

And the result is:

Now it's almost finished, we need to create a camera to be able to navigate into the scene.

The camera is defined by 3 vectors: Forward, Right and Up:

                  X  Y  Z
Right/Left       (1, 0, 0)
Up/Down          (0, 1, 0)
Forward/Backward (0, 0, 1)

Then, we multiply these 3 vectors to a XYZ matrix separately because we need each of them to be able to move the camera Forward/Backward/Right/Left/Up/Down.

Example: If press W, Forward vector is used, if press D, Right vector is used, ...

Now that we have our 3 camera vectors, we just need to add them to each of points of the object to move, like that:

 Vector Object:           Forward Vector:          Backward Vector:         Right Vector:
  __________________       __________________       __________________       __________________
 |                  |     |                  |     |                  |     |                  |
 |         x        |     |         x        |     |         x        |     |         x        |
 |__________________|     |__________________|     |__________________|     |__________________|
 |                  |     |                  |     |                  |     |                  |
 |         y        |  +  |         y        |  +  |         y        |  +  |         y        |
 |__________________|     |__________________|     |__________________|     |__________________|
 |                  |     |                  |     |                  |     |                  |
 |         z        |     |         z        |     |         z        |     |         z        |
 |__________________|     |__________________|     |__________________|     |__________________|

Finally, we multiply another XYZ matrix based on the camera angle with each vector point from the object to be able to move the object depending on the camera position and angle.

That's all for now, I hope I will give updates often because this code is not perfect, it has some bugs and does not have all the features of 3D math.

History

12^th June, 2018: Initial version
10^th July, 2018: Code update, simplify the code and optimize it by removing one useless rotation matrix calculation to gain 40 FPS (60 FPS to 100 FPS for my computer: i3 6100)
12^th July, 2018: Article update, added the 2D rotation equations build from scratch
14^th July, 2018: Code update, ~~fixed the camera that had strange translation, Forward/Right/Up vectors was good but it was missing sign adjustment when moving the camera~~ (Not worked)
27^th July, 2018: Code update, loop of SetObject() has been parallelized with OpenMP to perform a ≈2x FPS, from 120 to 208 on my CPU. Thanks to my friend who shown me how to use Multithreading in order to boost the FPS
15^th October, 2018: Code/article update, better reading of the source code and first implementation of the engine skeleton of UE4 into VoxEngine (variable/function name)
20^th October, 2018: Code update, SDL2 adoption, the major problem with WinAPI is that fullscreen mode isn't natively support
25^th October, 2018: Code update, first implementation of a GUI for the Engine manage by WinAPI, SDL just manage the Level window
30^th October, 2018: Code update, GUI improvement, expansion of object coordinates to 64-bit float precision and implementation of AVX instructions in the code (you need at least a 4th Gen Intel CPU to run the Engine)
31^th October, 2018: Code update, fixed SetWorldTransform_() bug, added header data on Object file and multiple objects support.
13^th November, 2018: Code update, GUI has been improved.