Click here to Skip to main content
16,018,057 members
Articles / Game Development

3D Computer Graphics from Scratch

Rate me:
Please Sign up or sign in to vote.
4.90/5 (80 votes)
1 Feb 2024CPOL8 min read 204.4K   5.3K   198   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.

Image 1

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

Image 2

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.

    Image 3

  • 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:

    Image 4

  • 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):

    Image 5

    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):

    Image 6

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

    Image 7

    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):

    Image 8

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

    Image 9

    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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
France 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

 
QuestionAccurate classic Greek Translation!! Pin
Mike Papadacos14-Feb-24 4:54
Mike Papadacos14-Feb-24 4:54 
QuestionNice article Pin
jochance5-Feb-24 7:30
jochance5-Feb-24 7:30 
AnswerRe: Nice article Pin
Orphraie5-Feb-24 11:06
Orphraie5-Feb-24 11:06 
QuestionMy vote of 5 Pin
Jeffamn2-Feb-24 7:02
Jeffamn2-Feb-24 7:02 
QuestionWhat is this ? Pin
Member 161947802-Feb-24 2:03
Member 161947802-Feb-24 2:03 
AnswerRe: What is this ? Pin
dandy722-Feb-24 3:02
dandy722-Feb-24 3:02 
GeneralRe: What is this ? Pin
Member 161947802-Feb-24 6:02
Member 161947802-Feb-24 6:02 
GeneralRe: What is this ? Pin
PIEBALDconsult2-Feb-24 6:04
mvePIEBALDconsult2-Feb-24 6:04 
GeneralRe: What is this ? Pin
dandy722-Feb-24 6:29
dandy722-Feb-24 6:29 
GeneralRe: What is this ? Pin
Member 161947802-Feb-24 6:51
Member 161947802-Feb-24 6:51 
GeneralRe: What is this ? Pin
Orphraie2-Feb-24 9:41
Orphraie2-Feb-24 9:41 
GeneralMy vote of 5 Pin
Stylianos Polychroniadis1-Feb-24 23:20
Stylianos Polychroniadis1-Feb-24 23:20 
QuestionCannot download the 7z file Pin
Shao Voon Wong1-Feb-24 20:59
mvaShao Voon Wong1-Feb-24 20:59 
AnswerRe: Cannot download the 7z file Pin
Orphraie2-Feb-24 0:39
Orphraie2-Feb-24 0:39 
GeneralMy vote of 5 Pin
Ștefan-Mihai MOGA1-Feb-24 13:28
professionalȘtefan-Mihai MOGA1-Feb-24 13:28 
Questioncould you some sections on how to compile your projects? Pin
Southmountain17-Feb-23 6:00
Southmountain17-Feb-23 6:00 
AnswerRe: could you some sections on how to compile your projects? Pin
Orphraie17-Feb-23 6:34
Orphraie17-Feb-23 6:34 
QuestionMessage Closed Pin
26-Aug-20 23:11
professionalanjali9026-Aug-20 23:11 
QuestionMessage Closed Pin
26-Aug-20 23:11
professionalanjali9026-Aug-20 23:11 
GeneralA poor article, despite possible intent Pin
SMDtheone24-Jul-20 17:47
SMDtheone24-Jul-20 17:47 
GeneralRe: A poor article, despite possible intent Pin
Orphraie25-Jul-20 0:49
Orphraie25-Jul-20 0:49 
GeneralTerminology Pin
SMDtheone25-Jul-20 8:08
SMDtheone25-Jul-20 8:08 
Again, calculus has very little to do (if anything at all) with trigonometry.
Calculus - Wikipedia[^]
Trigonometry - Wikipedia[^]
I notice that you are in France, so it may be a language issue. Next time try using "calculation" instead of "calculus".
SMD

GeneralRe: A poor article, despite possible intent PinPopular
_Allover_17-Feb-23 2:10
professional_Allover_17-Feb-23 2:10 
GeneralRe: A poor article, despite possible intent Pin
YDaoust2-Feb-24 1:44
YDaoust2-Feb-24 1:44 
GeneralRe: A poor article, despite possible intent Pin
Orphraie2-Feb-24 2:19
Orphraie2-Feb-24 2:19 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

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