learn

Code-It-Yourself! 3D Graphics Engine Part #1 - Triangles & Projection



Sharing buttons:

hello and welcome to part one of a new

series programming 3d graphics from

scratch in this series we're going to

start from nothing and develop quite a

feature-rich

software rasterizer which will allow us

to explore 3d graphics in an interesting

way

the example I'm showing on the screen

shows the one lone coda phrase rendered

using a full 3d rastering pipeline and

you can see it is even shaded and lit

accordingly I've implemented a

first-person shooter style camera and we

can elevate the camera up and down too

now we won't get quite that far in this

episode this is just episode 1 we're

really going to look at the fundamentals

that are required as part of a 3d engine

but that's the series progresses I'm

going to add more and more features to

turn this into quite a sophisticated 3d

engine now when you hear 3d engine you

might think of the terms OpenGL DirectX

or Vulcan these days we won't be looking

at those exactly instead what I'd like

to present is the theory and the

mathematics and the ideas that go behind

the graphic API so that we know and love

and what I hope to show by the end of

the series is just how complicated it is

to make your favorite games look very

pretty indeed and I'll demonstrate that

the number of calculations per triangle

and per pixel is simply huge now there's

one thing we can't get away from with 3d

graphics and that is mathematics but

don't click stop just yet I'm going to

try and present it in a style that's

maths friendly and the nice thing about

3d engines is even if you don't have

strong mathematics ability you can still

use most of the parts of a 3d engine as

as black boxes you don't necessarily

need to know how they work but you need

to know what these magical functions do

and over time by using such functions

you can actually develop a really

intuitive understanding of what's going

on behind the scenes so let's get

started rather oddly I'm going to start

this tutorial by saying there's no such

thing as 3d graphics

and that's simply because if we try to

represent a 3d shape on a screen of

course this screen is two-dimensional so

even though the object looks 3d what

we're actually trying to generate in the

end is a sequence of 2d shapes that give

the illusion of 3d on the screen

so taking this cube as an example I can

see I've got a top piece and I've got a

side piece and I've got a front face

should be a little squarer than that and

so the purpose of a 3d engine is to take

a three-dimensional geometrical data and

convert it into these 2d shapes so we

might define our cube as being a series

of eight vertices which I'll mark here

with the red dots don't forget there's

one we can't see and from this very

early stage even though it might seem

strange I'm going to suggest that all of

our dots are grouped into triangles so

this front face here I'm marking out in

blue consists of two triangles and the

same applies for the top face and the

side face and even the faces we can't

see in the background and the reason I'm

doing this is a triangle is a very

simple primitive in fact it's the

simplest 2d shape and as will become

apparent it's convenient to group

vertices together in some meaningful way

and because triangles are the simplest

2d primitive it's possible to represent

any two-dimensional shape using nothing

but triangles

and finally when it comes to drawing

triangles on a screen there are some

very optimized algorithms to do this

because a triangle consists of straight

lines well not straight when Javid draws

them and there are also some neat

algorithms to fill in a triangle and

shade it on the screen again using

straight horizontal lines will look at

rasterization in a later part of this

series but what I'm trying to emphasize

is that triangles are really important

and so in this video we're going to look

at how we can take a collection of

vertices in three-dimensional space form

a surface of a solid object out of

triangles and projects these triangles

to the screen for the user to see now

because this is a new series and I'd

like to show how to do this from scratch

I'm actually going to show you how to

create the visual studio project

necessary to do this and in part that's

because visual studio 2017 has changed

the way projects are created and so I

feel it might be useful to demonstrate

how to set up a project to start

something from scratch so I'm going to

go to file new project and I want to

choose windows console application of

course I'm going to be doing all of this

with the console game engine but don't

let that put you off simply because the

maths and the ideas don't change

regardless of the interface that you're

going to use select a console

application and give it a name I'm going

to call this one olc engine 3d now in

previous versions of Visual Studio when

you click OK

it would give you some more options it

no longer does this instead it creates a

project for you and fills it full of

files well the first thing I'm going to

do is delete everything except the dot

CPP file that it is created for me

bye-bye

and then going to remove this line

standard afx that's for the precompiled

headers I'm not interested in using

those and even though I've removed the

I actually need to go into properties of

the project go to C++ expand that open

and choose the precompiled headers

option and tell it that no I don't want

to use precompiled headers and click

apply what I do want to use is the

console game engine so I'm going to

include it and I'm going to make sure

that the header file that contains the

console game engine is also in the

project directory now we go and I'll add

that file just because I like to see all

the files my project is using into my

visual studio project and of course if

you're on a different operating system

now you can use the OpenGL version or

the STL version of the console game

engine even though it says game engine

in the title all we're really doing here

is accepting input from the user and

displaying things on a 2d screen the

fact that this house game engine there

doesn't imply we're going to be using

any of the game engine features which is

important because I don't want you to

think that I'm hiding interesting

technology and clever functions in the

console game engine and exploiting them

to generate 3d graphics

I'm not regular viewers of the channel

will know that we need to create a

subclass of the OLC console game engine

and so I'm going to call it olc engine

3d which inherits from the console game

engine let's just give it a quick

constructor

and there are two functions we must

override the first is on user create and

the second is on user update

for now I'll make these return true and

that tells the game engine that

everything is fine and it should

continue running in our in main function

we need to create an instance of this

class and we should try to create an

instance of the console using it using

the construct console function and for

this application and indeed this series

I'm going to use quite a high resolution

console of 256 characters wide by 240

characters high and each character is

going to be 4 by 4 pixels width and

height an oh dear quick error number 1 I

need to publicly include the console

game engine there we go

so if we can successfully construct the

console I want to start it else I would

display some sort of error message as is

typical in some of my videos I don't

tend to do all of the error capture code

that's to keep the code as clear and

concise as possible finally I'll name

the application 3d demo and a quick

reminder by default now unicode will be

enabled and this is important because I

think it is the singular most popular

question I've been asked since starting

this channel how to enable the Unicode

and thankfully Microsoft do that for me

now well now because I want to

demonstrate all of this from scratch I'm

not going to be using a maths library to

help me we're going to do absolutely

everything so I'm going to create a

structure called BEC 3d and this is

going to hold three floating-point

values X Y & Z which represent a

coordinate in 3d space

I'm also going to create a second

structure called triangle which is going

to group together three vector E DS

as the series progresses we'll be adding

more features to this triangle structure

finally I'm going to create a third

structure called mesh and a mesh is

going to represent the object it's going

to group together triangles and you'll

notice a little red wiggly line has

appeared and that's because at long last

I finally removed the using namespace

STD from the header file as I can here

most of the people on discord cheering

right now and I can't argue that it is

good practice not to include using

namespace in your header files but to

keep this code clear I'm actually going

to use it here so a quick recap we've

got a mesh which contains a vector of

triangles that represents an object and

we've got a triangle which contains

three vertices or vector 3ds these are

the points that define the outline of

the triangle I'm going to add now to our

main class a mesh and I'm going to call

it mesh cube and in on user create I'm

going to populate that mesh with the

vertex data to define a cube made of

triangles and I'm going to use this with

some nifty initializer lists I'm going

to keep the cube simple and define it as

a unit cube in these three dimensions so

each side of the cube is one unit long

and we'll assume the origin of the cube

is at 0 0 0 x y&z therefore this point

becomes 1 0 0 0 1 0 and 1 1 0 I've drawn

the cube edges so we can see what's

going on a little more clearly and this

obviously becomes 0 1 1 in fact it's

each one of these coordinates of the

back is the same as the one at the front

except the Z component is 1 so this one

up here is 1 1 1 and this one is 1 0 1

and the 1 hidden is 0

zero-one and I'm going to top the

convention that this face is South the

face round the back is north this face

is east and that face round the back

there is West this one's the top and

therefore the one underneath I'm going

to call bottom and now I can start to

think about my triangles but there's

something important about the triangles

which will come to again later on and

that is what the order of the points

that we define the triangle in and I

want to always use a clockwise order so

I'm going to take from zero zero zero up

here all the way along and because it's

a triangle I now need to come back down

to the original point you'll notice I've

gone in a clockwise direction

and I want to do the same now for my

second triangle up to the top back down

and along again in a clockwise direction

and I want to do exactly the same for

the remaining faces

always retaining this clockwise ordering

using initializer lists I can define the

vertices manually and I group them into

South East North West and top and bottom

but I'm also using a neat trick that

I've got to initialize a list inside the

other initializer list so this sub

initializer list will initialize the

triangle with three vectors whilst the

outside initializer list initializes the

standard vector I'm going to use the

fill command in on user update to clear

the screen from the top left to the

bottom right and after we've cleared the

screen we're going to need to draw our

triangles and because our triangles are

neatly contained inside a vector inside

of mesh I can use an auto for loop to

iterate through them all

but of course it's not this simple the

objects exist in 3d space and the screen

is in 2d space so we need to come up

with a way of condensing that foodie

space to the 2d screen and this is

called projection so how do we turn our

3d vertices into 2d vertices for

projection onto the screen well first of

all let's define our screen which is

going to be some sort of rectangle with

a width and a height because screens

come in all shapes and sizes it's useful

to reduce the three-dimensional objects

into a normalized screen space and so

I'm going to suggest that if we

partition the screen this way and this

way and we label this as minus one and

this is positive one and up here as

minus one and this as positive one we've

normalized the screen space obviously

that gives us zero zero in the middle of

the screen

and because the width and height can be

different we want to scale movements

within the screen space accordingly so

we're going to use the aspect ratio

which I'll call a and define that as

being the height over the width and this

will be the first of several assumptions

about how we're going to transform our

3d vector X Y & Z into our screen space

vector and I'm going to demonstrate this

by accumulating the operations required

normalizing the screen space has an

additional advantage that anything above

+1 or below minus 1 definitely won't be

drawn to the screen so let's just draw

in some imaginary boundaries here this

object exists entirely within the

visible viewing space but this object on

the right straddles the boundary so

we'll never see this side of the object

however humans don't see screens in that

manner they see instead what's called

the field of view and we can cast array

that way and we'll cast array that way

so at this point it's minus 1 and plus 1

on the screen but also out here in our

space this is also minus 1 and plus 1

and of course this makes a lot of sense

because objects that are further away

well we can see more space the further

away it is and as we approach the screen

we occupy more of the screen with our

objects if the field of view is

particularly narrow how crudely draw in

here is a blue triangle it has the

effect of zooming in on the object and

if the field of view goes really wide it

has the effect of zooming out we see

more stuff and this means we need a

scaling factor that relates to the field

of view and we'll say that the field of

view is theta well one way to think

about a scaling factor is to draw a

right angle triangle right down the

middle of our field of view

say that the right angles and as this

angle increases so this is now theta

divided by two our opposite side of the

triangle increases and so it stands to

reason that since we've got the angle of

a triangle its opposite side and it's

adjacent side that we might want to

consider looking at the tangent function

but of course it's tangent of the field

of U divided by 2

but there's a slight problem here if we

take a point and we increase our field

of view the scaling factor that we get

as a result of this equation gets larger

and naturally if we reduce theta the

scaling factor gets smaller so this has

the rather odd effect that if we

increase the field of view we start

displacing all of our objects outside of

it and naturally if we decrease our

field of view we scale them less so more

objects can appear and this is a

contradiction to what we've just said

that increasing the field of view is the

same as zooming out so what we want is

the exact opposite of this indeed we

want the inverse of it this gives us

some more coefficients to add to our

transformation where F is equal to 1

over tan of theta over 2 since we've

gone to the trouble of normalizing x and

y and realistically all we're interested

is in x and y because this is a 2d

surface in the end we may as well also

attempt to normalize Z and the reasons

for this might not be immediately

apparent but as we'll see in future

videos knowing what Z is in the same

space as x and y can be really useful

for optimizing our algorithms and

handling other interesting drawing

routines like transparency in depth

choosing a scaling coefficient for the z

axis is somewhat more simpler on again a

frustum and this is the z axis going

forward into the distance the furthest

distance of objects that we can see will

be defined by this plane at the back

which I'm going to call Zed far now you

might assume that means where the screen

is at the front that would be zero but

that's not quite the case because the

players head isn't resting against the

screen the player would injure their

eyes where in fact there is a small

distance here I'm going to call that Zed

near which is the distance represented

from the play's head to the front of the

screen and Zed far is from the place

head to the furthest distance we want to

be able to view in the in the engine if

I put some imaginary numbers next to

this so let's say our far plane is at 10

and our near plane is at 1 to work out

where the position of a point in that

plane really is we need to first scale

it to a normalized system so in this

case our Zed far-

RZ near is equal to 9 so we want to take

our point and divide it by 9 that will

give us a point between 0 & 1 but we've

decided that our far plane should be 10

so we need to scale it back up again so

this is implying that we have for our z

axis scale factor something that looks

like this Zed far divided by Zed far -

Zed near but this still leaves us with a

bit of a discrepancy here so we'll also

need to offset our transformed point by

this discrepancy scaled - well

fortunately we know where that

discrepancy is so we can take our

equation up here and simply multiply it

by Z near but we're going to offset it

from the final result so this becomes Z

far multiplied by Z near over Zed far

take xenia and so now if we look at our

initial coordinates and look at the

final transformed coordinate well it's

starting to look a bit complicated and

we're not even quite finished yet

intuitively we know that when things are

further away they appear to move less so

this implies that a change in the

x-coordinate is somehow related to the

z-depth

in this case it's inversely proportional

as Zed gets larger ie further away from

the screen

it makes the changes in X smaller and

this is analogous for Y so our final

scaling that we need to do to our x and

y coordinates is to divide them by Z

let's start to simplify some of this out

I'll take our width in a height and

we'll call it a 4 aspect ratio we'll

take our field of view and we'll call

that f and let's take our said

normalization and we'll call that Q and

which you can see also applies here

which means a much simpler form would be

a F X / z f y / z and z q - said near q

we could go and implement these

equations directly but instead I'm going

to represent them in matrix form as this

allows us then to implement a function

which can multiply a vector by a matrix

something which we're going to use a lot

off in 3d graphics in the Cody self

asteroids video I already talked in

quite some detail about how matrix

multiplication works but just as a quick

recap we'll take this element of the

vector and multiply it by this element

of the matrix and this element of the

vector and this element of the matrix

this element of the vector and this

element of the matrix and we sum them up

and that gives us a result to put into

our new vector in this location so let's

start with the transformed X location so

I'm going to put the result here in the

top corner which

simply want AF the remaining entries are

zero so x x AF + y x 0 + said x 0 gives

us a F X Y is even simpler we're not too

concerned about the X component we just

want F and nothing else and similarly

for the Z we don't compare about the X

component either nor the Y but we do

concern ourselves with Q but we've got

some interesting addition to Zed that

we've got to have this little offset

that's okay

because as we're performing the matrix

calculation we're summing this column

multiplied by the vector so I can simply

include as one of the elements - Zed

near Q but hang on we've suddenly got

four elements in this column and we've

only got three elements of our vector as

an input so to make this happen

I'm going to extend our input vector

with a 1 this of course also means I

have to put in additional zeros for the

x and y elements but now I've got an

interesting scenario of multiplying a

four by one vector by a 3 by 4 matrix I

have to use the final column of a four

by four matrix to make this legitimate

so let me just fill in Zed Q - Zed near

Q so what do we do with this fourth

column well you may also notice that

we've not got to divide by Z anywhere in

there and I can't readily do that in

this calculation getting the divided by

Zed is going to need to be a second

operation in fact we're going to be

normalizing the vector with the Z value

so I do want to extract it and to do

this I'm going to 0 0 1 0 so this will

give me a fourth component of my

transformed vector which will simply be

Z and after I've performed the

transformation and then going to take

the last element of this vector and use

it to divide the others

giving us a coordinate in Cartesian

space and so where we bring this

structure all together is one this is

called the projection matrix and yes it

may seem like a scary bunch of maths but

this is actually probably one of the

more complicated transforms that we'll

need to do as part of the 3d engine and

as I've mentioned before you can really

treat it like a black box this

projection matrix will work for all 3d

applications and it's highly

customizable in terms of aspect ratio

field of view and viewing distance so

this means of course we now need a

matrix structure I'm going to call it

4x4 and I'm simply going to define a two

dimensional array explicitly and

initialize it to zero and the ordering

of this matrix is row followed by column

I'm going to populate the projection

matrix once in on user create because

the screen dimensions and field of view

are not going to change in my

application

we'll have our near plane distance along

the z axis and to set that to not point

what we're going to need the far plane

which I'm going to set to a thousand

let's not forget the important field of

view which I'm going to set to be 90

degrees next up is the aspect ratio

which I'm going to grab directly from

the console so it doesn't really matter

what size console you create

and for convenience I'm going to do the

tangent calculation as a one-off and

you'll notice here I've converted it

from degrees to radians let's create a

projection matrix mat proj that's quite

customary and I'm going to specify the

elements of the matrix directly row

column so we know that this is our W X

value that we've just seen in the slides

which was our aspect ratio times our

tangent calculation our H Y value was

just the tangent calculation directly

and here I've just filled in the

remaining options I've got a sneaking

suspicion that we're going to be doing

matrix vector multiplications a lot so

I'm going to create a function to do it

for me and so we're going to input one

of our vectors and I want to get a

different output vector because I don't

want to upset the input data and we need

to pass in the matrix performing the

multiplication is simple and I'm going

to write the x y&z components directly

to the output vector but don't forget we

had a mysterious fourth element which

I'm going to call W and we have to

include this when we're multiplying by

four by four matrix the only thing to

remember is that we're implying that the

fourth element of the input vector is

one so we can simply sum the final

matrix element now because we've got

four D and we need to get back to 3d

Cartesian space we're going to divide it

by element W but I don't want to do that

if W is equal to zero that's going to

cause me headaches so if W is not zero

then I want to take the output values

and divide them by the W now let's have

a think about how we draw the triangles

using our projection matrix we know that

we're going through this Auto for loop

picking out each triangle at the time we

don't want to upset the original

triangles so I'm going to create a new

triangle called tri projected and tri

projected is where I'm going to put the

result of my matrix multiplication so

I've got the input tri tri projected as

the output and map proj as the matrix

we're going to use in our multiplication

however we can't use the triangle

directly and we need to reference the

vertex inside and I'm going to repeat

this for the three vertices I like the

fact that it's explicit quite a while

ago now I added to the console game

engine the ability to draw a triangle

and this simply draws three lines

between the three coordinates that are

specified using the original draw line

function which has been around since the

beginning this makes drawing a triangle

a little simpler I'm going to take the x

coordinate and we'll do some cut and

paste here just to speed it up a little

bit and the y coordinate of 0.1 I'll do

point two and point three and the final

two arguments and how it appears on the

screen so I want to use solid pixels and

I'm just going to draw everything in

white so let's take a look well I can't

see a cube there but what I can see

right up in the top corner is a single

pixel and in a way this is to be

expected because our projection matrix

has given us results between minus one

and plus one so now we need to scale

that field into the viewing area of the

console screen so the first thing I'm

going to do is take a coordinate and

shift it to between zero and

- I'll do that for both x and y and I

know this is where people will be

screaming at me why are you not making a

special vector class why are you not

using operator overloading and we'll

come to that in later videos so let's do

that for all three points so now it's

between 0 & 2 I want to divide it by 2

and scale it to the appropriate size for

that axis I'll take the X and I'm going

to multiply it by 1/2 times the screen

width and you'll see here I've just done

it for the other two vertices as well so

let's take a look well I can certainly

see what looks to be a cube and some

triangles but something's not quite

right

there's no perspective on this and I'm

not really sure of the orientation so

what can be going wrong here well simply

put our cube has its origin at 0 and our

current viewing to the world is also at

location 0 and so this means our face

for example could very well be inside

the cube at this location that means

some of the cube is behind us and we're

still trying to draw it and this is

undefined so it's not unsurprising that

the result is a little bit useless at

the moment what we need to do is

translate our cube into the world away

from where the camera would be so

instead of projecting the triangle

directly I want to translate it first

and this is easily done for translation

and all we want to do is offset the

triangle in the z-axis into the screen

so we'll add 3 to all of the Zed

components of the triangle into our new

triangle triangle translated so this is

no longer the triangle we wish to

project

let's take a look and see if this has

made it any clearer perfect we've

definitely got some perspective action

going on now but because the scene is

static we can't really get a feel for

what's happening in 3d so I'm not going

to rotate the cube around its X and its

z-axis I'm not going to do the rotations

at the same speed because we'll become a

victim of what's called gimbal lock

so I'll bias the rotations per axis

differently I'm going to add two more

matrices that can perform the rotation

transform around a specific axis now I'm

pretty sure the mathematicians out there

will start screaming while surely we can

combine all of these matrices with

matrix multiplications and we can but

I'm not going to do in this video to

give the impression that something is

rotating I'm going to need an angle

value that changes over time so I'm

going to accumulate the elapsed time in

a variable called F theta and I'm going

to hard-code two rotation matrices one

for the Zed axis and one for the x axis

you can look these up on Wikipedia it's

fairly standard and they work in quite a

similar way as the rotation matrix that

I derived in the asteroids video since

we're not multiplying matrices just yet

I'm going to need more triangle States

for the intermediate transformations and

I still want my translation to be the

last thing that I do because the order

of transformations is quite important I

want to rotate it around the origin of

the object which is currently 0 0 0 and

then once it's rotated I want to

translate the rotated object further

into the Z plane so taking the original

triangle the first thing I'm going to do

is rotate it in the z axis the second

thing I want to do is rotate it in the x

axis I then want to update my

translation code to use the most

up-to-date triangle so now let's take a

look and immediately I think that's

perfect look at that a perfect cube

projected evenly and nicely onto the

screen rotating smoothly and the

triangles and the faces are very visible

and so that's that for part 1 of this

series in the next part we'll be looking

at how we can control the camera and

we'll also be looking how we can shade

the faces of the object as usual all the

source code is going to be available on

github please join the discourse server

and come and have a discussion if you've

enjoyed this video give me a big thumbs

up please and have a think about

subscribing until next time take care