(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.