15,907,000 members
Articles / Game Development

# 3D Computer Graphics from Scratch

Rate me:
1 Feb 2024CPOL8 min read 192.5K   5.3K   197   88
Study of 3D graphics in video games with minimal prior knowledge of mathematics
This article will explore the foundation of 3D computer graphics through the simplification of how GPU render 3D geometric elements on screen.

## Introduction

A starting point for the introduction of 3D graphics would be to delve into its historical origins, the foundation of geometry was laid during ancient Greece with significant contributions from figures such as Thales, Pythagoras, and Euclid, who is often regarded as the "father of geometry".

• "Geometry" has its roots in Ancient Greek, `γεωμετρία` (geometria) composed of two elements:
1. Γῆ (Ge): This element means "Earth's land"
2. Μέτρον (Metron): This element means "measure" or "measurement"

When combined, the term `γεωμετρία `means the study of spatial relationships defined by practical measure, analyze and describe features of the Earth's land, for real-world applications such as agriculture, construction, and navigation.

Euclid wrote a book called Element where he provided specific definitions for several fundamental geometric terms:

• «`Σημεῖόν ἐστιν, οὗ μέρος οὐθέν`» could be translated by «A point is, of which part is none», this definition emphasizes the geometric indivisibility of a point, hence its only measurable attribute is the distance between two points.
•
• «`Γραμμὴ δὲ μῆκος ἀπλατές`» «A line, however, has length without breadth» emphasizing the idea that a line has only one measurable attribute, its length.
•
• «`Γραμμῆς δὲ πέρατα σημεῖα`» «The extremities of a line are points», underlying that a line is composed of points, since a line can have different length.
•
• «`Σῶμά ἐστι τὸ μῆκος, πλάτος, βάθος ἔχον`» «A solid is that which has length, breadth, and depth», meaning that a solid has 3 measurable attributes that do not overlap between them
•
• «`Τριγώνου δεξιοῦ τὸ τετράγωνον τῆς ὑποτείνουσης τοὺς τετραγώνους τῶν περὶ τὰς ἄλλας πλευρὰς ἰσότητα πεποιήκαμεν`» «In a right-angled triangle, the square on the hypotenuse is equal to the sum of the squares on the other two sides», we will keep this proposition to explain rotation spatial transformation later on.

With these in mind, we can build any geometric elements with just points.

Hence I do not rely on modern 3D graphics techniques to render geometric elements but the definition of points as Euclid set in his "Element" book.

## Introduction

Euclid did not introduce the concepts of axes, coordinates and dimensional space as known as Cartesian coordinate system, but a comprehensive analysis of points and lines can lay down its foundation.

Euclid's statement "`Γραμμῆς δὲ πέρατα σημεῖα`" also highlights the spatial relationship between the endpoints of a line, the relative spatial position between them where the length tell that position.

Hence, if points do have a spatial relationship between them and if any geometric elements can be shaped with points, each points inside a geometric element possesses a unique spatial position, relative to that element.

To precisely determine the relative spatial position of a point inside a more complex geometric element other than a line, we may trace the shortest line from this point to the other point within  each of the existing or imaginary measurement lines, establishing a network of interconnected points that defines their relative spatial position.

And the best candidate to build any geometric elements with a set of points is a ` στερεὰ `(sterea), a geometrical solid such as `παραλληλεπίπεδον `(parallelepiped), since its lines draw the length, breadth, and depth without overlapping each others, hence each point inside a `παραλληλεπίπεδον `will have a set of 3 measurements/distances between them and the corresponding points within the length's line, breadth's line and depth's line of the `παραλληλεπίπεδον`.

Later on, those measurement components will be called coordinates, coordinates relative to the measurement lines, which will be called axes, where each axis open a dimensional space.

In ancient Greece, measurements were often based on geometric and proportional relationships rather than standardized units as we have today, hence `πῆχυς `(Cubit) and `στάδιον `(Stadion) were used as counting units to set the distance in construction.

Euclid had a `Κανών` (ruler) to draw his geometrical element that had no numerical value markings, a `πῆχυς `could not fit the size of a ruler to draw geometrical elements, hence the metric system that came in the late of 19th century was the best choice as measurement units.

Now that we have lay down the foundation of Cartesian coordinate system, we have one more study to achieve, while we logically can move a point on a straight line by adding a variable number to one of its 3 measurement components, we have one spatial transformation left, moving a point on curved line, known as rotation.

And the rotation do have the circle as perfect geometric candidate since it has a single reference point located in its center for all points inside, visually rotating around the said reference point.

As Euclid stated above «In a right-angled triangle, the square on the hypotenuse is equal to the sum of the squares on the other two sides»,  emphasizing that a right-angled triangle had a spatial relationship between its three line's length, such as, known as Pythagorean theorem:

`HypotenuseLength × HypotenuseLength = FirstSideLength × FirstSideLength + SecondSideLength × SecondSideLength `

Hence if the` ὑποτείνουσα `(hypotenuse) has always the same length (known as circle's size), a circle can be drawn if we vary the length of the first side between 0 to 1 and find the corresponding length of the second side, such as:

`SecondSideLength = sqrt(1 - FirstSideLength × FirstSideLength)`

In programming, it could be translated with the c++ code below that I have added in the demo:

```auto CircleSize = 1;

for (auto FirstSide = 0.0; FirstSide <= CircleSize; FirstSide += 0.001)
{
auto SecondSide = sqrt(pow(CircleSize, 2) - pow(FirstSide, 2));

//
// Top-right quarter part of the circle
//
auto X =  FirstSide;
auto Y =  SecondSide;

//
// Top-left quarter part of the circle
//
auto X = -FirstSide;
auto Y =  SecondSide;

//
// Bottom-right quarter part of the circle
//
auto X =  FirstSide;
auto Y = -SecondSide;

//
// Bottom-left quarter part of the circle
//
auto X = -FirstSide;
auto Y = -SecondSide;
}```

While we could use that way to rotate points, the lack of a rotation measurement known as angle, will rotate the points without accuracy

Unfortunately, I haven't found a connecting bridge between the Pythagorean theorem and trigonometric functions that is using angles instead of using a right-angled triangle properties to draw a circle, thus the comprehensive analysis of Euclid's book stop here and we must leap toward modern geometry era.

Trigonometric functions such as `sin(θ)` and `cos(θ)` where `θ `represent the angle of a point on the circle's line relative to the measurement X line of the circle and return the corresponding relative position to its measurement lines.

Those measurement lines are commonly called X and Y

Hence, we will start with a visual study of the trigonometric circle to achieve rotation of points.

First we set a point at `0°` (`x = 1`, `y = 0`) and we apply a rotation on this point by` ``+90°` (+ is anticlockwise and - is clockwise) around the center, the result to find is `x = 0`, `y = 1`.

And the general formulas to find this result is:

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

It's relatively simple to retrieve this equation from scratch and later, we will see that this formulas is just the linear form of the Z rotation matrix.

Here's the methodology:

• We have a circle with two measurement lines (known as 2D) with a radius of 4.

• We set a point, rotate it and try to retrieve the equation that lead to its new position, thus once we have operate on a P(X, 0) and  P(0, Y) combinations, we will find the equation to rotate any P(X, Y)
• Let's begin with P(4, 0), visually a red dot:

• We rotate this point of +90° and try to find the equation of its new position, 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) with θ = 90, we have:
```X′ = cos(θ)
Y′ = X × sin(θ)```
• Trying with other angles for P(4, 0) give a slightly different equations (using mathsisfun) but where combined, gives this result:
• ```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′ = Y × -sin(θ)
Y′ = cos(θ)```
• Trying with other angles for P(0, 4) give a slightly different equations but where combined, gives this result:
```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, the situation where X or Y equal 0 do generate different equations, let's see what happen when X and Y values are below 4 and above 0:

• Hence, we set the 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 elsewhere.

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(θ)|
|_________________|_________________|```

What will happen if we have X and Y above 0, it should be a mix of both of them:

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

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

To close this visual study, let's try with P(X, 0) and P(0, Y):

• A rotation being applied on P(4, 0) of +90°, visually the result to find is P(0, 4):
```X′ = 4 × cos(θ) - 0 × sin(θ) = 0 ✔
Y′ = 4 × sin(θ) + 0 × cos(θ) = 4 ✔```
• A rotation being applied on P(0, 4) of +90°, visually the result to find is P(-4, 0):
```X′ = 0 × cos(θ) - 4 × sin(θ) = -4 ✔
Y′ = 0 × sin(θ) + 4 × cos(θ) =  0 ✔```

Now that we have retrieve the general formulas for rotating a point P(X, Y) on a XY circle from scratch, we can jump on rotation matrices study.

• As said earlier, this formulas is just a linear form of the Z rotation matrix (XZ plane rotation matrix), multiplied by the measurement components of the point, also called vector.

```Rotation matrix on z:                                 Vector:
_______________ _______________ _______________       _______________
|               |               |               |     |               |
|    cos(θz)    |   -sin(θz)    |       0       |     |       x       |
|_______________|_______________|_______________|     |_______________|
|               |               |               |     |               |
|    sin(θz)    |    cos(θz)    |       0       |  ×  |       y       |
|_______________|_______________|_______________|     |_______________|
|               |               |               |     |               |
|       0       |       0       |       1       |     |       z       |
|_______________|_______________|_______________|     |_______________|```

A 3D coordinate system can be described with several 2D coordinate systems, such as every planes drive the rotation spatial transformation everywhere in a 3D coordinate system.

Thus, we need to gather all those 2D rotation matrices that do compose a 3D coordinate system and there are 3 of 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       |
|_______________|_______________|_______________|```

Finally, in order to achieve a rotation on Euclid's points in a 3D coordinate system, we do need to multiply the 2D rotation matrices above, between them and where the order of the multiplication matters, but we will take a closer look on that in the next tutorial heading this one.

## History

• 1st February, 2024: Article/Code update, starting from Euclid's works to explain computer graphics.
• 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.

 Missing sample mesh file? tma2k221-Nov-19 3:49 tma2k2 21-Nov-19 3:49
 Re: Missing sample mesh file? Orphraie22-Nov-19 11:37 Orphraie 22-Nov-19 11:37
 4th image from the top is missing littleGreenDude14-Nov-18 6:58 littleGreenDude 14-Nov-18 6:58
 Re: 4th image from the top is missing Orphraie14-Nov-18 7:40 Orphraie 14-Nov-18 7:40
 Re: 4th image from the top is missing littleGreenDude14-Nov-18 8:51 littleGreenDude 14-Nov-18 8:51
 Nice article Kenneth Haugland30-Jul-18 2:51 Kenneth Haugland 30-Jul-18 2:51
 Re: Nice article Orphraie8-Oct-18 11:17 Orphraie 8-Oct-18 11:17
 Using Matrices Stefan_Lang11-Jul-18 22:26 Stefan_Lang 11-Jul-18 22:26
 It's not that hard to use matrices. Here is a small example for 2D transformations: Let C = (cx, cy) be the center of a rotation in the 2D plane, and you want to express a rotation of a given point P = (px, py) by the angle phi around that point as a simple equation. How do you do that? You can express the rotation around the origin as a 2x2 matrix C++ ```R = / cos(phi) -sin(phi)) \ \ sin(phi) cons(phi) /``` This matrix doesn't help you right away, however, because the center of rotation is not the origin - it is C. Therefore, you need to perform a trick: 1. you transform the coordinate system in such a manner that C is the new origin 2. then you use express the coordinates of P using that new coordinate system 3. now you can use the standard rotation matrix on P', the new coordinates of P, to get Q' 4. then you revert the coordinate transformation to get the real coordinates of Q, the rotated point. This is not as hard as it sounds: 1. the required transformation is just a translation that subtracts C. For any point A = (ax, ay): C++ `A' = A-C` 2. to get the new coordinates of P, just subtract C from P: C++ `P' = P-C = (px-cx, py-cy)` 3. apply the standard rotation matrix to the transformed point: C++ `Q' = R*P' = R*(P-C)` 4. revert the coordinate transformation: C++ `Q = Q'+C = R*P'+C = R*(P-C)+C` If you want to perform this transformation on many points, you can even simplify it: C++ ```Q = R*(P-C) + C = R*P - R*C +C = R*P + C' , with C' = (C - R*C)``` This reduces the whole transformation to just one matrix operation and one vector addition. This kind of transformation is called affine transformation in mathematics, and most 2D and 3D operations used in graphic kernels are just that: affine transformations. The nice thing about expressing transformations in this manner, using vectors and matrices, is that they trivially scale up from 2D to 3D, and even higher, if you want: If C an P are 3D points and R a 3D rotation matrix, the formula is just the same! GOTOs are a bit like wire coat hangers: they tend to breed in the darkness, such that where there once were few, eventually there are many, and the program's architecture collapses beneath them. (Fran Poretto)modified 16-Jul-18 3:58am.
 Re: Using Matrices Orphraie23-Sep-19 20:59 Orphraie 23-Sep-19 20:59
 Re: Using Matrices Stefan_Lang23-Sep-19 22:11 Stefan_Lang 23-Sep-19 22:11
 Re: Using Matrices feanorgem25-Sep-19 8:17 feanorgem 25-Sep-19 8:17
 Re: Using Matrices Bob100025-Sep-19 1:00 Bob1000 25-Sep-19 1:00
 Premultiply feanorgem11-Jul-18 5:30 feanorgem 11-Jul-18 5:30
 Re: Premultiply Orphraie11-Jul-18 6:04 Orphraie 11-Jul-18 6:04
 Re: Premultiply Stefan_Lang11-Jul-18 21:44 Stefan_Lang 11-Jul-18 21:44
 Re: Premultiply Orphraie12-Jul-18 2:45 Orphraie 12-Jul-18 2:45
 nice BillW336-Jul-18 2:16 BillW33 6-Jul-18 2:16
 Re: nice Orphraie8-Oct-18 11:15 Orphraie 8-Oct-18 11:15
 Learn 3D Math made by the GPU by Creating a 3D Engine on CPU Doom For Ever18-Jun-18 9:41 Doom For Ever 18-Jun-18 9:41
 Re: Learn 3D Math made by the GPU by Creating a 3D Engine on CPU Orphraie18-Jun-18 11:39 Orphraie 18-Jun-18 11:39