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

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

Channel: javidx9

Views: 1,680,517

Keywords: one lone coder, onelonecoder, learning, programming, tutorial, c++, beginner, olcconsolegameengine, command prompt, ascii, game, game engine, 3D, 3D graphics, 3D engine, code-it-yourself, code it yourself, projection matrix, vertex, triangles, rotating cube, vectors

Id: ih20l3pJoeU

Length: 38min 45sec (2325 seconds)

Published: Sat Jul 14 2018