17 Bit Software 2: Collection B/17Bit_Collection_B.iso/files/1345.dms/in.adf/cRender/render.doc

Text File | 1990-12-02 | 10.8 KB | 238 lines

(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.