(c) 1990 S.Hawtin. Permission is granted to copy this file provided 1) It is not used for commercial gain 2) This notice is included in all copies 3) Altered copies are marked as such No liability is accepted for the contents of the file. This document explains how the "render.c" program works, well it gives some hints as to what is going on. This document is split into two parts, first the theory, then the actual code itself. Theoretical Stuff If you know about three dimensional graphics, or if you are not interested I suggest that you skip this bit. The position of any point in space can be specified by three numbers, these three numbers can be collected into a "vector", for example [14 7 21] gives us a point that is 14 along 7 across and 21 up. We can specify the shape of a solid object by first saying where the vertices of the object are, then by specifying triangles to connect the vertices together. So for example could describe a simple object with 4 ; Number of vertices 0 0 0 ; Vertex 0 at x=0 y=0 z=0 80 0 0 ; Vertex 1 0 80 0 ; Vertex 2 0 0 80 ; Vertex 3 4 ; Number of triangles 3 2 1 ; Triangle 0 connects vertex 3 2 1 2 3 0 ; Triangle 1 1 0 3 ; Triangle 2 0 1 2 ; Triangle 3 remember in 'C' the first item in any list is usually item number 0. The order of the vertices in each triangle is important, I will tell you why later. Now once we have loaded this object into memory we want to display it on the screen, this is simple, all we have to do is draw all the triangles in the object and there the object will be. But you may ask how to we draw the triangle, ([80 0 0],[0 80 0],[0 0 80]) for example. Well the simplest way to draw it is to ignore the last component of the vector, just draw the triangle ([80 0],[0 80],[0 0]). The first problem with this simple approach is the fact that we want faces that are nearer to us to obscure the faces that are further away. We need to sort the faces according to how far away they are and draw the nearest ones last. Although this sounds like the right thing to do it suffers from one minor drawback, the fact that it doesn't work. The cases where it doesn't work are rare enough that I will ignore them. The second problem with this simple approach is that while a view down the z axis is entirely accurate, it does lack a certain sparkle, it fails to convey the shape of the object. Well we can get around this problem by using two different coordinate systems, the first set of coordinates is fixed relative to the object, the second set is fixed relative to the screen. Now when we want to display a triangle we must Transform the vertices to screen coordinates Sort the triangles according to their z positions Draw the triangles just using the x,y positions all well and good you say, but how do we turn [80 0 0] into a screen position[x y z]? The answer is that we use matrix maths. To transform a logical position into a screen position we must multiply the logical position vector by a "transformation matrix". If you understood that sentence you don't need to bother with the next bit, for us mortals however. A transformation matrix is a 3x3 square of numbers that transforms vectors from one coordinate system to another. So if we have a logical position [X Y Z] then we can work out its screen position from |A B C| [X Y Z] * |D E F| = [A*X+D*Y+G*Z B*X+E*Y+H*Z C*X+F*Y+I*Z] |G H I| all we need to do is work out the transformation matrix. In "real" three dimensional graphics the transformation matrix is 4x4, if you are interested in why this should be you should look it up, however for my simple system a 3x3 matrix is complicated enough. So how does a self confessed matrix illiterate work out the right matrix? Well I could have worked it out from first principles, or then again maybe not, but actually I looked up the matrix in a book, "The fundamentals of three-dimensional computer graphics" by Watt if you are interested. What I wanted was a matrix that would leave the origin in the same place but rotate the axis by "th" in one direction and "ph" in another, the matix is |-sin(th) -cos(th)*cos(ph) -cos(th)*sin(ph)| | | | cos(th) -sin(th)*cos(ph) -sin(th)*sin(ph)| | | | 0 sin(ph) -cos(ph) | so we now can be even more specific about how to draw our object Work out th and ph Work out the transformation matrix Multiply all the vertex positions Sort the triangles according to their z positions Draw the triangles just using the x,y positions so now can we get on with the coding? Well no, the next problem that comes up is the fact that we want to draw each face a different colour. The reason for this is easy to see, if you look around you will see that all three dimensional objects look different according to the light, if we want to create a solid object on the screen, even a white one, we must draw it with many different colours. So we must use a simple model of the illumination of the object, the simplest possible model is the "cosine" model, this assumes that the light source is in a certain direction. The amount of light reflected by the surface is proportional to the cosine of the angle between the light source and the normal to the surface. There, who said three dimensional graphics was complicated. The normal to a surface is a vector that is perpendicular to the surface, it shows which way the surface is facing. The amount of light hitting the surface will obviously be at a maximum when the surface is pointing directly at the light, and will be zero if the light is shining along the surface. A little bit of thought, and a lot of tilting large books under standard lamps, will convince you that the cosine rule previously stated is correct. *** WARNING *** The following paragraph contains serious hand *** WARNING *** waving and should therefore not be trusted. Well now, I can hear you say, how do we find the cosine of the angle between two vectors, let alone the normal to the surface. Well luckily there is this thing called the "dot product", if we have vectors V (say [X Y Z]) and U (say [I J K]) the "dot product" is V.U = X*I+Y*J+Z*K = |V|*|U|*cos(th) where "|V|" is the length of V and "th" is the angle between the vectors. Well isn't that convenient. But even better than that, the "cross product" of two vectors VxU = [J*Z-Y*K K*X-I*Z I*Y-J*X] gives a vector that is perpendicular to both the original vectors, we can work out the normal of any surface if we have two vectors in the surface, so if our triangle is ([X1 Y1 Z1],[X2 Y2 Z2],[X3 Y3 Z3]) we know that the vectors [X2-X1 Y2-Y1 Z2-Z1] and [X3-X1 Y3-Y1 Z3-Z1] are both in the surface then the normal to the surface is given by [Y1(Z3-Z2)+Y2(Z1-Z3)+Y3(Z2-Z1) Z1(X3-X2)+Z2(X1-X3)+Z3(X2-X1) X1(Y3-Y2)+X2(Y1-Y3)+X3(Y2-Y1)] but of course the question is which normal, the surface has two, one pointing into the object the other pointing out. This is why the order of the vertices in the triangles is important, if we get it wrong the program will think the face is pointing the wrong way and will get the illumination all wrong. There is another advantage to having the normal vector, if the z component of the normal vector is positive, that is the face is pointing away from the screen, and we don't need to draw it. This is because there must be a closer face pointing towards us. So with this final refinement we can draw our object with the following steps Work out th and ph Work out the transformation matrix Throw out faces pointing the wrong way Cross multiply all the vertex positions Work out the illumination on each face Sort the triangles according to their z positions Draw the triangles just using the x,y positions and that is what the CRender program does. There are a number of things you can do to improve the display, for example the illumination model is very simple, you could add shadows. The edges of the triangles could use some anti-aliasing. Practical Stuff The theoretical section skims over a number of rather interesting problems, so if we go through the "render.c" file I will point some of them out. You can look at this file and "render.c" at the same time in a number of ways, obviously one option is to print one or both files, another option is to use "memacs" from the "1.3 Extras" disk, then select "Window-Split Window" from the menu to look at both files at the same time. Right the first bit of "render.c" reads in the include files, as well as the system include files we read "3D.h", this defines things like "Vector", "Vertex" and "Triangle". Next we have some variables that control what is being displayed, these are directly controlled by the user, the program uses these global variables to control its behaviour. Next the global variables, these are where the program stores things that are needed all over the place, for example the object description, the current transformation matrix and so on. Things to note, firstly the object description doesn't take much space, space is allocated when the program runs, this means we don't have to guess what the largest object is when we write the program. Next the transformation matrix is 4x4, a real matrix, however this program only uses the top left 3x3 area. Now we get into the functions, trans_vertex() transforms a vertex from logical to screen coordinates, notice that we put the result into a long, this is because at one of the intermediate steps the number will be more than sixteen bits wide and we don't want any overflow. The cmpz() function compares the z coordinate of the centres of two triangles, the function is not directly called within the program, the qsort() call in display_object() uses the function to sort the triangles by z position. The display_object() function does most of the work in the program, in the algorithm it does the Throw out faces pointing the wrong way Cross multiply all the vertex positions Work out the illumination on each face Sort the triangles according to their z positions Draw the triangles just using the x,y positions parts. If you follow the function you will see that it goes through these five steps. The init_triangle() function takes an initial triangle and works out the position of the centre, and the normal vector. These two only need to be worked out once, when the triangle is initially loaded. The read_file() routine reads an object description file and creates all the data structures that the program needs, this bit of code is rather important but also boring.