A Universe of Triangles - Computerphile

Key Takeaways

we find everywhere actually that the best option is always to divide into triangles because any 3D surface in the universe is uh able to be approximated by fitting together triangles in talking about how 3D computer generated images are created and how they work there are a number of different questions that we need to address and problems that we need to solve and the first of those is how do we take a 3D object and represent it in the computer and so the way we do this is by using a coordinate system every day we have maps and graphs and things that all use this coordinate system it's called the cartisian coordinate system generally we have a two axes one called x one called Y and if we want to specify a point any point anywhere on the graph we have two numbers which represent the distances that we travel along each axis so if we have 2 1 we go one two one and there's 21 simple enough using this system we can represent any unique Point anywhere on the plane described by these axes and we can also you know go this way and this way to have negative points as well so that's plus X Plus y - x - Y and this way we we can have Min -2 minus one here so that's two Dimensions but uh if we want to specify points in three dimensions we simply add another axis going through the middle like this it's perpendicular to X and Y but obviously it's a 2d piece of paper so and this is called Zed so we'll call that plus Zed and this minus Zed so now we can have 21 and this is on plane zero in Zed so that's 2 one0 and this becomes minus 2 - one Z using this system and three number coordinates we can specify any unique Point relative to the origin here and the axes that we've specified what use is this when we want to describe something like a pyramid well typically what we want to do is use our coordinate system to specify the corners of the objects which we call vertices Let's uh get another piece of paper here let's describe the points of our pyramid using our 3D coordinate system let's call them A B C D and then round the back e using our coordinates a will be at 0 to0 say B will be at Min -1 in x 0 in y - one in Zed c will be at + one in X 0 in y - one in Z and so on for the other two using these coordinates we can specify the corners or the vertices of our objects but that's not quite enough because uh all we're doing is specifying the corners and our representation says nothing at all about the faces of the pyramid so how do we go about representing the faces well one way of doing it the simple way would be to specify a new set of vertices three vertices three coordinates for every face so we'll have one here one here one here one here one here one here one here one here one here Etc the problem is this incurs a lot of duplication of vertices so for example this vertex at the top point a on the DI is required by all four of these faces so if we're specifying three coordinates for every face we're duplicating the top one four times for a simple object like a pyramid that's not too much of a problem but if we have a model with 100,000 vertices in then the um wastage can be quite considerable so there is a better system for specifying the faces of of any geometry and and to do that we use a separate data structure to represent the faces which references the vertices that we've described using our uh cartisian coordinates so if we name them as we have done on the diagram a b c we can then say that this face is represented by vertices a b c and this face is a d and then this face is a d e and then this face is a e b and then we have a problem because when we come to represent the base of the pyramid it's a square and that doesn't really fit into our system of three vertices per face so what we could do is find some way of specifying that these faces all have three vertices each and this one has four and for another shape it might have five vert Toes or something like that but in practice it's better just to split the base into two triangles we find everywhere actually that the best option is always to divide into triangles because any 3D surface in the universe is uh able to be approximated by fitting together triangles and why are triangles so good for this purpose um well first of all it's the simplest polygon there's only three vertices in a in a triangle second of all more importantly any arrangement of three vertices in 3D space will always be co-planar which means that no matter how you arrange the three vertices of a triangle they will always lie on the same plane in space which is a crucial property if you want to approximate a surface with a simple two-dimensional polygon a set of them um it doesn't work for other types of polygon so a rectangle for example in this case it's okay because the vertices are all c-plan now they're nice and flat but if I were to lift one of them let's go with this one out of the plane of the other three we'd no longer have a valid rectangle because these three or AO planer but this isn't I mean there got a curved surface to it so it's not a proper rectangle anymore so for that reason using rectangles or higher order shapes other than triangles are surfaces that we are approximating might be in danger of having degenerate faces faces that aren't properly represented because we might have one vertex that's raised out of the plane of the face but triangles don't suffer from this problem Sean has asked me now to demonstrate how a cylinder might be represented by triangles so let's draw some triangles onto it so let's start with the circle at the top generally it's quite easy to subdivide into triangles but what we find is that this curved edge here will start to look a little bit jaggy with these straight edges which I've not drawn on very well but of course the more triangles we use the better the approximation to the circle so as we add more and more these straight lines approximate a curve better and better on the side of the cylinder we just use almost exactly the same principle we can create triangles like this I mean there are millions of ways to do this and it's the same situation as uh on the top uh whereby the more triangles we have the denser the tessellation the better approximation to the curved surface we'll get um so as you can see I mean any surface pretty much this a sphere anything can be represented by triangles any conceivable surface in the universe in three dimensions at any rate so there's a a further problem in that uh when we specify a triangle as a b c we're really specifying two triangles one on the front and one on the back in the pyramid we have the triangles facing out and the triangles facing in and sometimes we might want to be able to differentiate between which way a triangle is facing is it facing out or is it facing in and the way that is achieved is by being very careful about the order in which the vertex coordinates is specified so it's called winding when you basically decide yes because you're wind the winding for the indices the trick is we always go in One Direction clockwise or anticlockwise doesn't matter which as long as we're consistent so let's say and in fact I've actually done that here that going anticlockwise means a face is going outwards clockwise means a face is pointing inwards so let's have a look on this pyramid here we can see that a b c that's going anticlockwise this face is facing out a c d Yep they're going anticlockwise this face is facing out now the back face which is facing away from us is a d e which is going going clockwise so that's facing away from us so this way we can differentiate between triangles that are facing out or facing in which becomes very useful for example when we're drawing a triangle we might want to say well don't render the faces that are facing away from us we want to Cur those and not bother having to shade the pixels for those back two faces or we might want to say well we don't want to draw the faces that are looking towards us cuz we want to see the inside of an object if we're rendering a cutaway or something like that um so that's how winding Works in a nutshell it doesn't matter whether you go clockwise for forward front faces and anticlockwise for back faces or the other way around as long as you're consistent because further down the pipeline when we come to turn these triangles into pixels it might become important to know whether it's facing away or towards us with probably now covered enough to know roughly how geometry is represented inside the computer um we can represent vertices and faces made up of vertices um the next step is to take our description of an object and move it around in 3D space