15,798,826 members
Articles / Game Development

# 3D Graphics Engine with Basic Math on CPU

Rate me:
16 Feb 2023CPOL7 min read 170.9K   5K   186   67
Minimal 3D Math required explanation plus 3D graphics engine coding
This project will help you to understand the basic math behind graphics engines by reproducing a part of GPU graphics pipeline on CPU, and to make a 3D graphics engine based on voxels that is aiming to be a game engine.

• This project is made with Visual Studio 2022, .NET Core 7 using WPF.
• You would need to install BusDog in order to be able to use keyboard/mouse with the engine.
• `ImportTexture` is bugged, it displays only 1 pixel of the image.

## Introduction

A voxel is a non divisible point within a space, like an atom that composes the material, this is my definition. For other engines, voxels are defined as volume of pixels, like in Minecraft/Roblox and I don't use this definition.

## Background

This article was possible with my wish to see a video game with texture and object blended together, built with voxel.

## Using the Code

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

• What is a space?
• What is a dimension?
• What is an axis?
• What are trigonometric functions?
• What is a coordinate system?
• What is a rotation matrix?
• What is a rotation and translation?

Now let's give answers to these questions:

A `space`(universe) is a geometric shape of `N-dimension`, constituted of `coordinates `that grid the `space`.

A `grid `is used to structure geometry shape.

An `axis `is a static vector on a grid used to normalize movement on the grid.

`Trigonometric functions` are functions such as sin(θ) and cos(θ) where θ represent the angle around an axis and draw a circle in a 2D plan.

A `rotation matrix` is a set of equations made with trigonometric functions.

A `coordinate system` is constituted of numbers placed on axis, determining the position of a geometrical element such as a point within the system usually represented by a graph.

A geometric element cannot exist outside a geometric shape.

A 1D `space` is represented by a single line in one direction/`axis`: ----------------------------

To move an object on this axis, the equations are:

 `x' = Point.x + x` To move right `x' = Point.x - x` To move left
```  -3  -2  -1   0  +1  +2  +3
X--|---|---|---|---|---|---|-- ```

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 in 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 to `translate` the object on `x``-axis`.

But we can also rotate the object around the center of the 2 `axes`, for doing that, an addition is not enough, we need to call math operators 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 `axes`.

These math operators are called trigonometric functions: `sin()` and `cos()` that take the angle between the two lines: [center, object's point] `x-axis` for cos() and `y-axis` for `sin()`.

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

And the calculation to find this result is:

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

It's quite easy to retrieve this equation from scratch, it's what I did and surprisingly I have 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, rotate it and try to retrieve the equation of its new locations, we will find the final equation once we have operate on a couple of different XY combinations.
• Let's begin with P(4, 0), a red point:

• Now we rotate this point of +90° (θ) and try to find the equation of 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 value with Y at zero (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 values with X at zero , 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 summarize:
``` _____ ________________ ________________
|     |                |                |
|     |     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 that we have, what if we have P(X, Y), it should be a mix of both the 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 is working:

```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 is working, so at the end, the final equations on a XY plane is:

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

But 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 ✔```

Good, all is working, you can test this equation with your own XY and angle values to verify if it's working.

This equation is also surprisingly (as said earlier) just a linear form of the Z rotation (XZ plane rotation matrix)` `matrix, multiplied by the point called `vector`, where `Z` is the center of the both `axes`).

```Rotation matrix on z:                                 Vector:
_______________ _______________ _______________       _______________
|               |               |               |     |               |
|    cos(θz)    |   -sin(θz)    |       0       |     |       x       |
|_______________|_______________|_______________|     |_______________|
|               |               |               |     |               |
|    sin(θz)    |    cos(θ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(θx)    |   -sin(θx)    |
|_______________|_______________|_______________|
|               |               |               |
|       0       |    sin(θx)    |    cos(θx)    |
|_______________|_______________|_______________|```

### Y Rotation Matrix (YZ Plane Rotation Matrix)

``` _______________ _______________ _______________
|               |               |               |
|    cos(θy)    |       0       |   -sin(θy)    |
|_______________|_______________|_______________|
|               |               |               |
|       0       |       1       |       0       |
|_______________|_______________|_______________|
|               |               |               |
|    sin(θy)    |       0       |    cos(θy)    |
|_______________|_______________|_______________|```

### Z Rotation Matrix (XZ Plane Rotation Matrix)

``` _______________ _______________ _______________
|               |               |               |
|    cos(θz)    |   -sin(θz)    |       0       |
|_______________|_______________|_______________|
|               |               |               |
|    sin(θz)    |    cos(θ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` `axes `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).

### XYZ Rotation Matrix (XY YZ XZ Planes Rotation Matrix)

``` ______________________________ ______________________________ ____________________
|                              |                              |                    |
|      cos(θy) × cos(θz)       |      cos(θy) × -sin(θz)      |      -sin(θy)      |
|______________________________|______________________________|____________________|
|                              |                              |                    |
| -sin(θx) × sin(θy) × cos(θz) | sin(θx) × sin(θy) × sin(θz)  | -sin(θx) × cos(θy) |
|    + cos(θx) × sin(θz)       |     + cos(θx) × cos(θz)      |                    |
|______________________________|______________________________|____________________|
|                              |                              |                    |
| cos(θx) × sin(θy) × cos(θz)  | cos(θx) × sin(θy) × -sin(θz) | cos(θx) × cos(θy)  |
|    + sin(θx) × sin(θz)       |    + sin(θx) × cos(θz)       |                    |
|______________________________|______________________________|____________________|```

Now, we just need to multiply this `rotation matrix `(based on object's angles) to the `vector `point of the object to be able to `rotate `the object around `XYZ` `axes`.

```Obj Vec:    Rotation Matrix:
_____     _______________________________________________________________________________
|     |   |                             |                            |                   |
|  x  |   |      cos(θy) × cos(θz)      |     cos(θy) × -sin(θz)     |     -sin(θy)      |
|_____|   |_____________________________|____________________________|___________________|
|     |   |                             |                            |                   |
|  y  | × | -sin(θx) × sin(θy) × cos(θz)|sin(θx) × sin(θy) × sin(θz) |-sin(θx) × cos(θy) |
|     |   |    + cos(θx) × sin(θz)      |    + cos(θx) × cos(θz)     |                   |
|_____|   |_____________________________|____________________________|___________________|
|     |   |                             |                            |                   |
|  z  |   | cos(θx) × sin(θy) × cos(θz) |cos(θx) × sin(θy) × -sin(θz)|cos(θx) × cos(θy)  |
|     |   |    + sin(θx) × sin(θz)      |   + sin(θx) × cos(θz)      |                   |
|_____|   |_____________________________|____________________________|___________________|```

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

The camera is defined by three `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 three `vectors `to a `rotation matrix` (based on camera's angles) separately because we need each of them to be able to move the camera `Forward/Backward/Right/Left/Up/Down`.

And, adding the result to the object vector.

Example: If press W, `Forward vector` is used
If press S, `-Forward vector` is used
If press D,   `Right vector` is used
...

```Object Vector:           Forward Vector:
__________________       __________________
|                  |     |                  |
|         x        |     |         x        |
|__________________|     |__________________|
|                  |     |                  |
|         y        |  +  |         y        |
|__________________|     |__________________|
|                  |     |                  |
|         z        |     |         z        |
|__________________|     |__________________|

Object Vector:           Forward Vector:
__________________       __________________
|                  |     |                  |
|         x        |     |         x        |
|__________________|     |__________________|
|                  |     |                  |
|         y        |  -  |         y        |
|__________________|     |__________________|
|                  |     |                  |
|         z        |     |         z        |
|__________________|     |__________________|

Object Vector:           Right Vector:
__________________       __________________
|                  |     |                  |
|         x        |     |         x        |
|__________________|     |__________________|
|                  |     |                  |
|         y        |  +  |         y        |
|__________________|     |__________________|
|                  |     |                  |
|         z        |     |         z        |
|__________________|     |__________________|```

Finally, we multiply another `rotation matrix` (based on camera's angles) with each `vector` point from the object to be able to move the object depending on the camera angle (modified with the mouse movement).

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

• 16th February, 2023: Code update, Added basic ray tracing feature (it gives Doom graphics), Set the `Evo `project as startup project in EvoEngine.sln and build always in x64, there are two rendering methods, with `Direct2D` or with `Writeable Bitmap`
• 12th June, 2018: Initial version

Written By
France
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

## Comments and Discussions

 Re: Premultiply Orphraie11-Jul-18 7:04 Orphraie 11-Jul-18 7:04
 Re: Premultiply Stefan_Lang11-Jul-18 22:44 Stefan_Lang 11-Jul-18 22:44
 Re: Premultiply Orphraie12-Jul-18 3:45 Orphraie 12-Jul-18 3:45
 nice BillW336-Jul-18 3:16 BillW33 6-Jul-18 3:16
 Re: nice Orphraie8-Oct-18 12:15 Orphraie 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 Orphraie18-Jun-18 12:39 Orphraie 18-Jun-18 12:39
 Avast refuses downloading Sample Doom For Ever18-Jun-18 9:57 Doom For Ever 18-Jun-18 9:57
 I could not download samples due to blockings by AVAST Free AntiVirus... Am I the only one ?
 Re: Avast refuses downloading Sample Orphraie18-Jun-18 10:12 Orphraie 18-Jun-18 10:12
 Re: Avast refuses downloading Sample Doom For Ever18-Jun-18 10:32 Doom For Ever 18-Jun-18 10:32
 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 Orphraie14-Jun-18 8:04 Orphraie 14-Jun-18 8:04
 Re: Try this as one of your tables - created in Word Daniele Rota Nodari11-Nov-19 0:17 Daniele Rota Nodari 11-Nov-19 0:17
 I fell miss of some concepts and some complements Samuel Teixeira14-Jun-18 4:27 Samuel Teixeira 14-Jun-18 4:27
 Re: I fell miss of some concepts and some complements Orphraie14-Jun-18 7:59 Orphraie 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 Orphraie12-Jun-18 23:55 Orphraie 12-Jun-18 23:55
 Re: My vote of 5 Arun Virupaksha13-Jun-18 0:09 Arun Virupaksha 13-Jun-18 0:09
 Re: My vote of 5 Orphraie13-Jun-18 0:22 Orphraie 13-Jun-18 0:22
 Re: My vote of 5 Orphraie8-Oct-18 12:20 Orphraie 8-Oct-18 12:20
 Tables: a bad idea Patrice T12-Jun-18 17:32 Patrice T 12-Jun-18 17:32
 Re: Tables: a bad idea Orphraie12-Jun-18 21:22 Orphraie 12-Jun-18 21:22
 Re: Tables: a bad idea Patrice T12-Jun-18 22:02 Patrice T 12-Jun-18 22:02
 Re: Tables: a bad idea Orphraie12-Jun-18 22:08 Orphraie 12-Jun-18 22:08
 Last Visit: 31-Dec-99 19:00     Last Update: 10-Dec-23 23:03 Refresh ᐊ Prev123 Next ᐅ

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.