13,797,648 members
alternative version

Stats

41.8K views
70 bookmarked
Posted 12 Jun 2018
Licenced CPOL

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

, 13 Nov 2018
This article will explain you the basic 3D math applied on video games.

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

Introduction

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

• 12th June, 2018: Initial version
• 10th 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)
• 12th July, 2018: Article update, added the 2D rotation equations build from scratch
• 14th 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)
• 27th 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
• 15th 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)
• 20th October, 2018: Code update, SDL2 adoption, the major problem with WinAPI is that fullscreen mode isn't natively support
• 25th October, 2018: Code update, first implementation of a GUI for the Engine manage by WinAPI, SDL just manage the Level window
• 30th 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)
• 31th October, 2018: Code update,  fixed SetWorldTransform_() bug, added header data on Object file and multiple objects support.
• 13th November, 2018: Code update,  GUI has been improved.

Share

 France
No Biography provided

You may also be interested in...

 Pro

 First PrevNext
 4th image from the top is missing littleGreenDude14-Nov-18 7:58 littleGreenDude 14-Nov-18 7:58
 Re: 4th image from the top is missing wqaxs3614-Nov-18 8:40 wqaxs36 14-Nov-18 8:40
 Re: 4th image from the top is missing littleGreenDude14-Nov-18 9:51 littleGreenDude 14-Nov-18 9:51
 Nice article Kenneth Haugland30-Jul-18 3:51 Kenneth Haugland 30-Jul-18 3:51
 Re: Nice article wqaxs368-Oct-18 12:17 wqaxs36 8-Oct-18 12:17
 Using Matrices Stefan_Lang11-Jul-18 23:26 Stefan_Lang 11-Jul-18 23:26
 Premultiply feanorgem11-Jul-18 6:30 feanorgem 11-Jul-18 6:30
 Re: Premultiply wqaxs3611-Jul-18 7:04 wqaxs36 11-Jul-18 7:04
 Re: Premultiply Stefan_Lang11-Jul-18 22:44 Stefan_Lang 11-Jul-18 22:44
 Re: Premultiply wqaxs3612-Jul-18 3:45 wqaxs36 12-Jul-18 3:45
 nice BillW336-Jul-18 3:16 BillW33 6-Jul-18 3:16
 Re: nice wqaxs368-Oct-18 12:15 wqaxs36 8-Oct-18 12:15
 Learn 3D Math made by the GPU by Creating a 3D Engine on CPU Doom For Ever18-Jun-18 10:41 Doom For Ever 18-Jun-18 10:41
 Re: Learn 3D Math made by the GPU by Creating a 3D Engine on CPU wqaxs3618-Jun-18 12:39 wqaxs36 18-Jun-18 12:39
 Try this as one of your tables - created in Word davesmills14-Jun-18 4:59 davesmills 14-Jun-18 4:59
 Re: Try this as one of your tables - created in Word wqaxs3614-Jun-18 8:04 wqaxs36 14-Jun-18 8:04
 I fell miss of some concepts and some complements pySamuel14-Jun-18 4:27 pySamuel 14-Jun-18 4:27
 Re: I fell miss of some concepts and some complements wqaxs3614-Jun-18 7:59 wqaxs36 14-Jun-18 7:59
 Re: I fell miss of some concepts and some complements enhzflep17-Nov-18 1:46 enhzflep 17-Nov-18 1:46
 My vote of 5 Arun Virupaksha12-Jun-18 22:31 Arun Virupaksha 12-Jun-18 22:31
 Re: My vote of 5 wqaxs3612-Jun-18 23:55 wqaxs36 12-Jun-18 23:55
 Re: My vote of 5 Arun Virupaksha13-Jun-18 0:09 Arun Virupaksha 13-Jun-18 0:09
 Last Visit: 13-Dec-18 1:29     Last Update: 13-Dec-18 1:29 Refresh 12 Next »