Code-It-Yourself! 3D Graphics Engine Part#2 - Normals, Culling, Lighting & Object Files

hello let's continue making a 3d graphics engine and for this video we're going to start with the code as we left it in the previous part of this series where we created a wireframe rotate in cubes and let me just run that there we go that's what we ended up with at the end of the last video in the previous video I spent a lot of time deriving what's called the projection matrix because I believe this is fundamentally the most important part of the 3d graphics engine translating that 3d model information into 2d imagery on the screen and before we get to full 3d world implementations there are still some more fundamentals that we need to do and that's what I aim to cover in this video even though the rotating cube is very nice it does actually show some things that we don't need in a 3d engine firstly we can see the sides of the cubes we shouldn't normally be able to see it's as if this is an ice cube we can see right through it so let's have a think about how we can remove the triangles that we can't see recall in the first video how we defined a cube it was a set of six faces divided into triangles and we took some effort to make sure that the winding of the triangles was consistent for the model of the cube we in fact decided to do a clockwise winding so the triangle consisted of this vertex then this vertex then this vertex and though important we didn't really go into the reasons why this was necessary while 3d engines exploit two main things firstly vertex geometry as we've seen but they also exploit the normals to the surface of the geometry and it's important that we can create these normals and just for the uninitiated and normal is an imaginary line which is perpendicular to the plane that contains the triangle remember a triangle is the most fundamental 3d primitive it can only exist in a plane so taking these two triangles at the front face of our cube unnormal some sticks out here these ones at the side it sticks out to the side and the ones at the top well they point upwards I don't need to draw all of these in but I'm sure you can imagine that the triangles that we can't see they also have normals as well but he starts getting a quantity to draw them on the screen so I won't now our model doesn't contain any normal data we're going to generate it as and when we need it this will differ from 3d engine to 3d engine implementations and as the engines become more sophisticated you will in fact see that it is quite common to include normal information as part of the model fortunately there are some geometric techniques for getting normals that are quite simple given two lines that are in a plane the normal can be represented as a third line that is perpendicular to both of those lines and fortunately for us in three dimensions there exists a mathematical function to generate this vector and it's called the cross product and this is one of those times where we start treating parts of the 3d mathematics as black boxes deriving the cross product and what the cross product actually means is quite complicated and I feel a little bit beyond the scope of this video and in full honesty a little bit beyond the scope of my understanding and indeed if you check out the cross product on Wikipedia you might be able to get a feeling as to why fortunately we can treat it as just a black box it will always give us the line that is perpendicular to the two other lines given to it essentially each component of our normal vector is a calculation between the other two components of the other two lines so the X component of our n vector in this case can be calculated as a Y times B Z minus a Z B Y the Y component very similar a said B X minus a X B Z and finally the Zed components a X B Y minus a Y B X and this is why declaring our triangles in a consistent order was quite important this triangle at the bottom of the screen is comprised of three vertices defined in a clockwise order so algorithmically I can get my a line by taking point 1 and subtracting from it point 0 and I can get my B line by taking point 2 and subtracting from it point 0 and so once I have my two lines I can compute the cross product to give me the normal to the triangle surface if however I didn't define these in a clockwise orientation and instead did it the other way round counter clockwise orientation that's fine but now when I calculate the cross product the normal will go in the opposite direction and this is completely acceptable so long as we remain consistent in the ordering of our vertices per triangle if we've created triangles with vertices in all sorts of different orders then the normals computed from the cross product would be facing up and down depending on the ordering of the triangle and this may make eventually our shapes look a little strange so I'm really just trying to enforce the point that consistency is key when creating the models so why is the surface normal an important feature well let's take a standard axis look at our X here Y here and our Z going off into the distance crudely speaking any of the triangles that have a normal whose Z component is negative we can see whereas those that have a normal that have a positive z component we can't so the normal of these triangles at the front may have the vector 0 0 minus 1 but the ones at the back that we can't see well they'll probably be 0 0 1 and so knowing the Zed can opponent weakened crudely optimize our cube to be consisting of only triangles that we can see and we'll see shortly this isn't entirely true and we can do a better job but let's implement this in code and see what happens I'm going to calculate the triangles normal after we have translated the triangle into world space but before we do any projection so we're still doing everything in 3d space I'll create three temporary vectors one which is the normal and two more that represent the lines calculating the lines is quite easy and we've just seen it's just a case of subtracting the points from the triangle I'm going to take the translated triangle and take the first point take its x-component and subtract from that the origin of our triangle which we know will always exist as point 0 naturally I need to do the same for all components and we're starting to see a bit of a theme here that we're getting a lot of repetition and we'll talk a little bit more about how to reduce this repetition in the next part of this series but for now I'm going to continue on in the manner that's familiar so far calculating line two is equally as simple except now we want the different points I've just shown that the normal is the cross products of the two lines so I'm going to implement that directly but there's something important to remember about normals is well it's normally normal to normalizer normal which means I need it to be a unit vector so I'm going to calculate the length of the normal using Pythagoras theorem and divide the individual components of the normal by that length the next section of code involves transforming the translated triangle from world space into screen space via the projection matrix but I only want to do all of this if I can see the triangle in the first place so I'm going to base doing this on the condition that the Z component of our normal vector is less than 0 so I'll wrap it in an if block let's take a look well straightaway we can see some improvement the triangles that are on the far side of the cube are definitely not visible however it's not quite right we can still see that there are faces that we shouldn't be able to see and this is because we've not taken projection into account we've got nothing that says where the eye is in world space relative to where that normal is and traditionally this is where we would introduce the concept of a camera now cameras do add a lot of complication and I'm going to commit to the entire next part of this video series to just cameras but for now I wish to represent the camera as a vector location in space and we're going to keep it fixed at zero zero zero two the main class I'm going to add a single vector called V camera and this represents the position of the camera in 3d space and this is an incredible simplification of how a camera will be implemented for a start there's no Direction information it doesn't imply which direction the camera is pointing and so really it's only acting as a bit of a placeholder for the next video if we take a side-on view of the world we can start to see what's causing this problem so here I've got the eye point of the user and we're looking from sidon along the z axis and let's assume I've got my cube somewhere up here if I draw our normals onto my cube we're filtering normals based on the z-component so in this instance we can certainly see that the Z component of the normal is less than zero as is this one however this one is greater than zero so we don't see these two faces at the back but we do see the two faces at the front the problem we've got is this face shouldn't really be seen because perspective with the field of view shouldn't allow for that to happen because we're not considering where the surface is in 3d space relative to where the camera location is we're assuming that all of our normals exist exactly on a plane directly in front of the camera so that normal up there is actually really just some normal here which of course we can't see this means that instead of just inspecting the Z component alone we need to look at the Z component relative to the line of projection from the camera to the location of that normal in 3d space so what we really need to detect is how much of the normal is in line with the imaginary line cast from the viewing position to the location of the normal in this normal example we can see that an angle there would be about 90 degrees and we shouldn't be able to see it we can see with this normal the angle is certainly greater than 90 degrees and we can't see it but the one face that we can see have not even really got the room to put in the angle shows that if it's less than 90 degrees we can see it this example is in two dimensions but if three dimensions working with degree starts to get a little fiddly but we can make a rash assumption that really what we're looking for is how similar is the surface normal to the line between the camera and where this normal exists unfortunately when we're dealing with vectors we have a function that can work out how similar two vectors are and it's called the dot product now what's interesting about the dot product is it's a scale of value a single number that tells us how similar two vectors are and it's defined as being something like this for three dimensional dot product it will look like this ax times BX plus a Y times B Y plus AZ times BZ and I think it is possible to see intuitively why this equation gives us a value of similarity between two vectors if we make an assumption that a is equal to 1 0 0 and B is equal to 0 1 0 we know that actually these have nothing in common one is in the x axis and one is in the y axis they are not similar at all which means this first component results in 1 times 0 it's at 0 the second component is 1 times 0 so that's 0 and the third component is 0 times 0 so that's 0 so the overall value of the dot product is 0 they're not similar it makes sense then as if the two vectors are the same we get a score of 1 but now let's assume that one of our vectors is actually indeed the direct opposite in one of the axes well now our score is minus one so let's take a look at this little 2d example with our black main vector and I'm going to test it against its red vector which is pointing in the same direction and of course will give us a dot product of 1 when they're not in the same direction at all that will give us a dot product of 0 none of the original vector projects onto the new vector and the final one the green one the vectors pointing in the opposite direction this will give us a score of minus 1 and note what I'm saying here assumes that the two vectors we're testing together have been normalized previously let's change the code so we're not just looking at the Z components of the surface in isolation instead we want to see how much of the Z component of the triangles normal is projected onto the line between where the camera is and the location of the trying in 3d space let's start by simply commenting that line out so I want to calculate the dot product between the line from the camera to the triangle and the normal I'll take the X component first the translated triangles position and we can take any point on this triangle because they all lie within the same plane and from that we'll subtract the camera coordinate which is 0 0 0 it might not be later on so that satisfies the X component we're going to need the Y and the Z components just do a little bit of code housekeeping here and we're going to see if that is less than zero can we indeed see this triangle let's take a look well that looks straightaway much better we now can no longer see any of the surfaces that shouldn't be visible the reason we could choose any point on the triangle for where the normal is in 3d space is of course the triangle exists entirely in a plane so the normal is pointing in the same direction for any position within that plane I think this is successfully made the cube look rigid but we can also test the theory if we instead look for values that are greater than zero we've effectively turned the cube inside out now we're only drawing the faces that are on the other side and occasionally we can see it's drawing five faces it's looking like an open box but let's put that back wireframe objects are very useful for debugging and seeing what's going on behind the scenes but they don't really reflect and realistic solid-body object in 2d space so let's look at filling in the triangles now and I'm going to cheat a little bit here because the console game engine has a routine called fill triangle so I'm going to change our draw triangle to simply fill triangle and let's take a look well we can certainly see a shape rotating around on the screen and the outline of it indeed looks like a cube but because there's no sufficient shading going on on the sides of the cube our brain simply can't interpret what we're looking at so we need to add a source of illumination and I'm only going to bother illuminating the triangle if we can see it because the more calculations that we're adding the more expensive it's becoming to draw triangles now the type of light I'm going to add is the most simplest form of lighting it's a single direction light and this sort of light doesn't exist anywhere in the real world it assumes that all of the rays of light are coming in from a single there action not a single point so I've created a vector 3d here indicating the direction the light is shining and you'll see oddly I've specified the Zed component to indicate that the light is shining towards the player and there's a reason for this and that's in our simple setup here we can assume that a triangle is more lit the more its normal is aligned with the light direction and we'll see in the next video that's not quite true but for this one it's sufficient to give us some clarity when trying to determine the shape of the object so having created a light Direction normal I also need to normalize it as we did before I'm going to take the the length of the light Direction vector and divided by that length this allows us to play with interesting light directions without any consequence and since we now have a method of determining the similarity of two vectors it's called the dot product I'm going to calculate the dot product between the normal of the triangle surface and the light direction now I have a problem with the console I don't have a very high resolution of colors to choose from in order to do intricate shading if you're implementing this engine using a platform that has RGB fair enough you can do what you need to do but I have done this before when I looked at how I could implement webcam viewing in the console we looked at color algorithms so I'm going to take some code directly from that that would take a value from between 0 & 1 and convert it to a grayscale scheme that is suitable for the palette of the console and in the webcam of the console video I created a function called get color and here it is I've just literally couldn't paste it in directly it takes the floating point luminance value between 0 & 1 and returns the symbol and console color combinations that reflect that luminance as a mixture of black gray and white character colors but also different shadings of the pixel is if you remember we emulated color by mixing together at different intensity pixels on the console we don't have RGB we're using color combinations and character combinations so I'm going to store the symbols that represent the color for the triangle and since my entire triangle will be shaded the same way I only need to store these per triangle we may consider looking at storing these per vertex in a future video going back to the lighting equations I can now extract the symbol and character information required to represent a particular shade of gray in the console simply by looking at what the dot product value is and I'm going to set the values of my triangles color and symbol to whatever is returned by this function but please remember this is really console specific stuff if you're doing this not on a console then it's much much simpler just choose the color and you need to we've just set the color and symbol values of the translated triangle we're now going to transform that translated triangle into a projected triangle so I need to make sure that that information gets carried on through - that's just a simple case of copying them over you might think well why didn't I just do this in the first place but I'm trying to encapsulate functionality so that the flow is easy to follow and as the engine develops in sophistication we'll be glad for these boundaries of encapsulation when we get to the point where we're drawing the triangle on the screen instead of choosing a solid pixel that's colored white we can now use the symbol and color information that's associated with the projected triangle however I'm just going to copy and paste this code and change it back to draw triangle I just want to back this up for later so let's change pixel solid to try projected dot symbol and we'll change the color to try projected dot com let's take a look and now we can see that the cube is illuminated with a light that looks like it's emanating from where the player is one of the reasons I wanted to keep this line is it's very useful for debugging we can fill the triangle but if I set this to FG black or indeed any other color I can now fill the triangle and draw the triangle so I can see the wireframe outline of the cube this could be quite useful for debugging let's face it cubes are a bit boring and especially games made from cubes they're incredibly boring so I could sit here and go through algorithms to generate spheres and cylinders and other interesting shapes to draw on the screen but I know that's not really what any of we want what we want is spaceships laser sharks and mecha unicorns so let's look at how we can implement a third party objects into the game engine so far we've manually crafted the cube and this is quite time-consuming and laborious and even for a simple shape it's surprising just how much data you need a slightly more sensible approach would be to use some 3d modeling software create the model and export it into a format that is easy for our game engine to read unfortunately there is such a format it's called the obj or object format you can download object files from the internet there's quite a few different repositories full of interesting shapes that have been modeled before but it's also very easy to make your own in software like blender blender is free I like it it's very powerful and very competent software so here I am very very quickly at building up a spaceship model for exporting to our game engine [Music] [Music] [Music] [Applause] [Music] one of the nice things about blender is you can visualize the normals and so I'm checking to make sure that the normals all point outside of the model this will ensure that our triangle winding order is consistent across the model but I won't be exporting this normal data as part of the object file it's important that the model consists solely of triangles that's because our game engine only understands triangles however object files are oblivious to actually how many points make up the surface polygons when we export the object file I don't really care about any of the other properties I just want the vertex data and the face data but I want to make sure just in case I've missed something that it automatically triangulates the faces for me now one of the nice things about object files and one of the little hidden secrets in Visual Studio which not many people know is that if I take the object file we've just created and drag it into visual studio it does indeed render it and you can drag it around I think this is quite nifty regardless we're going to build our own loading code to load the model from the file into a format that's more sensible for us I feel the best place to do this is in our mesh structure so I'm going to add a function called load from object file that takes a file name and that returns whether the file was loaded successfully or not let's have a quick look at what's inside an object file you can see it's in a human readable text format so that's useful the first two lines look like comments and junk and that's indicated by the hash symbol at the start of the line the next few lines start with a lower case of V and this indicates vertex this is the location of a single vertex in 3d space and we've got quite a few of them we have a line here s off I have no idea what that means so I'm going to ignore it and in the next few lines they begin with a lower case F which stands for face and in this case we can see that the face consists of three points and that's great because that means it's a triangle and all of our faces are triangles so we can interpret this line as being a single triangle in our graphics engine and the way this works is we'll build up a pool of vertices from these lines here and these numbers are the indexes into that pool as to which vertices we want this means we only need to record each vertex once but we can reuse it in other triangles so it's quite an efficient form of storage as we read through all of the triangles we get to the end of the file and it stops so this should be quite a simple thing to do I'm going to need some file handling functions so I'm going to include F stream and string stream and simply I'm going to open the file first if I can't open it I'm going to return false means the file can't be found I now need to create that ten pre-poo love vertices so I'm going to create a vector of my 3d type and just store that locally for now that will disappear once we finish loading the object because the mesh itself will store the triangles at the end I now want to iterate through the file extracting the data but I don't want to read from a file that has no data left so I'm just going to make sure that I've not hit the end of the file I'm going to make a dirty assumption here that one of the lines of the file doesn't exceed 128 characters I'm going to use the gate line function to read the whole line in in one hit it's a little inconvenient in these days to work with character buffers so I'm going to turn the line into a string stream and I can populate the stream in the same way that you would use C out if we look at the file again we can see that each line always starts with a character that describes what the line is as I read from the string stream in two variables I'm going to need somewhere to put this character even though I might not be interested in it so I'm going to create a temporary variable called junk it's a single character let's check to see what the line begins with if the character is of V then we know we're reading in a vertex in that case let's create a temporary vertex and because we've got everything in a nice string stream we can allow the standard library to really make all of this very easy for us so the string stream s I'm going to read in the character the front we know that's going to be a V in this case but we can consider it junk I'm not interested in it but I am interested in the three next values which we can read directly into V X V dot Y and V dot Z once we've compiled the vertex I'm going to add it to our temporary pool of vertices and that's it that's all that's required to read in the vertex information in a similar way if the line begins with an F I know really what I'm doing is making a triangle so I'm going to be reading in three integer values and exactly the same way I read in the vertex data I'm going to read in the junk character in this case is f and populate my array here with the three vertex indices and in a single hit I'm going to construct the triangle and push it to the triangle belonging to the mesh let's have a look at this line so this is the tries variable which relaxed to the mesh consisting of a vector of all of the triangles that the mesh is comprised of I'm going to add to that vector the three triangle locations but these are stored in my temporary pool of vertices so this is point zero of my triangle point one of my triangle and point two of my triangle you'll see that I'm indexing the temporary pool of vertices with the face ID value but I'm subtracting one from that and that's because rather frustratingly all of the information in an object file starts counting from 1 and not zero and that's great that's all the code I need to read in an object file into the triangle structure of my mesh let's waste no time in trying this so instead of defining the cube as a bunch of vertices directly I'm going to comment that out and instead even though it's called cube and now it's going to be a spaceship I'm going to use our load from object file function and I'm going to load the object file video ship dot obj normally you would test for errors but I'm not going to let's take a look well that's very nice but oh dear me all sorts of things going horribly horribly wrong here it kinda does look like the ship but it's a mess what's gone wrong well two things are happening here the first is we're not drawing on triangles in the correct order so that means we're actually drawing triangles that are further away on top of triangles that are closer to the users this makes the model look a bit like a mess the second problem we've got is a little less simple and we'll solve it with a hack for this part of the series but we'll actually solve it properly in the next and that is that as the triangles approach the camera position if you remember as part of the projection we divide them by the Z value well the set value gets smaller and smaller and smaller and indeed tends towards zero so this means when we're drawing the triangle the x and y values get much much much bigger and we saw as the ship was rotating it was stuttering because there was not enough performance of the computer to actually draw a triangle which is so huge in the time that we would expect it to to solve that problem we would need to implement clipping and we'll do that next time but for now what I'm going to do is position the ship far enough away from the camera that we know that none of the triangles are going to go too close to the camera we already offset the cube now the ship into the distance using this translation procedure here but we only offset it by three to push it further away from the camera I'm going to offset it by eight so now let's take a look we should certainly see it'll still look like a mess but we don't have any performance inconsistencies anymore because none of the triangles get drawn behind the camera and now that it's running smoothly we can start to see yes the triangles that are visible because of the surface normal but are behind of the triangles are still being drawn and this is a problem in a normal foodie engine we would have something called a depth buffer and that is where every pixel on the screen also has a Zed value associated with it so when we want to draw a new pixel we test that pixel against that value that's already in the depth buffer and if it's in front of that pixel we draw it and if it's behind it we don't we can't see it and that's great being in the console I don't have that luxury so instead what I'm going to do is take the midpoint value of the triangles take the Zed component at that midpoint and sort the triangles based on that value and we'll draw them from back to front this is called the painters algorithm so we draw the things that are furthest away first and draw the things that are closest to the camera last and this means we need to change the structure of our code ever so slightly so far we've both translated transformed projected and drawn our triangles in a single loop instead what I'm going to do now is accumulate the triangles we want to draw into a new vector and we know which triangles we want to draw because we've already cooled the triangles we can't see and we've illuminated them and we've performed the projection but instead of drawing them straight away I'm going to add them to this vector so I'll get rid of this draw code now that I have a vector of triangles that I need to raster I'm going to come out of my main loop and create a little Auto for loop which goes through all of the triangles in that vector and draws them this gives me a little space in between to sort the triangles unfortunately thanks to the algorithm component of the standard library they provide a sort function for us rather than writing our own which will never be as efficient as those that have been tried and tested by experts I'm just going to use the sort function from the algorithm library and modify it slightly for our needs so let's add in some sorting code the function is simply called sort but we need to give it a starting point in our vector triangles to raster dot begin we need to give it an ending point triangles to raster dot end and now we need to give it a sorting criteria now a triangle isn't just a number so it allows us to put in a little lambda function to actually implement the sorting criteria for us and it's going to test two triangles each time t1 and t2 I'll just put this little lambda on the line like that there we go very pretty so we want to get the midpoint Zed values of both triangles this will only give us an approximation so we may still see the occasional glitch but I was surprised at just how well this works and the midpoint is quite easy we take the three points that make up our triangle we take the Zed components of them then we average them we do that for triangle one we do that for triangle two and the lambda function is expected to return a boolean as to whether it should swap the positions of the two triangles in this case we're doing it if Z 1 is greater than Z 2 you may need to play around with the polarity of this to get it right so now we have a single loop which does the bulk of the transformations to sort out which triangles we want to send to our rasterizer for drawing we're sorting those triangles so that they're drawn in the correct depth order and then we're going to actually raster the triangles to the screen I'm not going to draw the wireframe outline so let's take a look and I think that's quite pleasing we've now got an illuminated optimized model being rendered to the screen and you can see that our said sorting method on the whole works very very well indeed it is a hack so there will be some slight imperfections and I think you can just see them on the edges of the wings but on the whole I'm pretty pleased with how that's come out and so that's that for this video now you might be thinking hang on that's not been very much but what we've established here is the very basic foundation of a 3d engine because in the next part of this series we're going to be looking at how do we move the camera around how do we start implementing 3d worlds and this becomes quite complicated and that's what we'll be looking at implementing the view matrix which represents the camera so we can put the camera at any point in the 3d world in any orientation and we'll also be looking at clipping which is quite an important way of optimizing at which parts of the triangles get drawn as we saw in this video if the triangle goes beyond the edges of the screen that it starts to cause problems for the rest because the triangles become too huge how do we cut down the triangles in order to make them fit into our world there'll be one other thing that we'll be looking at in the next video too and that is optimizing all this redundant code so far you've seen - everything on the X component then the Y component then the Zed component I feel that this is starting to become a little bit of a bottleneck for productivity so we might look at either creating our own or using existing matrix vector library to do this anyway as always the source code is available for this on github come and have a chat with us on the discourse server if you've enjoyed this video a big thumbs up please have a think about subscribing and I'll see you next time take care

Channel: javidx9

Views: 198,332

Keywords: one lone coder, onelonecoder, learning, programming, tutorial, c++, beginner, olcconsolegameengine, command prompt, ascii, game, game engine, 3d, 3d engine, triangles, normals, rendering, lighting, culling, object files, blender, 3d models

Id: XgMWc6LumG4

Length: 39min 40sec (2380 seconds)

Published: Sun Jul 29 2018