3D Coding

Here I will present a basic 3D system (rotating, lit cube) and add other extensions in further tutorials. I'll explain everything that needs to be done to get the final product, and there are explanatons in the source code too. It's not optimized, so that you can see what's really going on.

Display

The first requirement for 3D graphics is to be able to display something. I used VBE 2 for SVGA resolution (that means you need UNIVBE 5.1 or later, and compile the code with svga.c, ie: gcc 3d.c svga.c -o 3d.exe ...). My code's somewhat faster than Allegro, so I used it, because no complicated functions are required for these purposes. If high resolution is too slow for you, then use mode 13h, but it's not worth it for now, since we're only displaying a single cube. All you need is a 486 with a local bus video card.

Basics

You need to understand a few concepts that come up in 3D frequently. Three dimensional space has length, width and depth. These can be described with a coordinate system containing (x, y, z) values corresponding to each dimension. These values mean the displacement of a point along each 'axis'. An axis is an imaginary line running horizontally left or right, vertically, or horizontally in and out of the screen. These are all perpendicular to each other and can be described using 'vectors'. A vector is described by (x, y, z) coordinates and is thought of as a line running from (0, 0, 0) through the specified coordinate. This way the x axis is represented by (1, 0, 0), ie. a line from (0, 0, 0) (also called the origin) going 1 unit to the right. The same is true for the other axes. A 'vertex' is a point in space also described by (x, y, z) coordinates which symbolize the amount of displacement along each of the axes. Vertices are used to describe an object and are points where two or more lines on the object's surface meet.

Projection

So let's begin with simple points (single vertex) first. The whole foundation of 3D graphics is to be able to plot a 3D point (which describes a 3d object) on a 2D screen. This is done by using the depth or z value to affect the x,y coordinates, ie: by dividing each by z and plotting the result. This has the effect of creating less displacement as the depth increases, called perspective. Objects farther away appear smaller.

The view point is usually at the origin, looking straight into the screen along the z axis. Even if your application requires the camera to move around and rotate, you actually move and rotate the whole world around it (all the objects at the same time). This is to simplify the perspective projection function. It looks something like this:

screen.x = screen_center.x + distance*(vertex.x / vertex.z)
screen.y = screen_center.y - distance*(vertex.y / vertex.z)

where:
screen_center is the coordinate of the middle point on the screen, ie: (x_res/2, y_res/2). If you didn't use this, you would never see negative coordinates - not good.
distance is a constant that specifies how far the imaginary view point (the phisical viewer) is behind the view plane (screen), or the 'field of view' which it translates to - smaller numbers give a wider FOV (you can see more through a keyhole if you're closer to it). I find 256 or 512 to give good results, and the multiplication gets nicely optimized.

Rotating the world is one of the reasons why you separate your object's coordinates from what you see on the screen. You should usually create your objects relative to a fixed center (0, 0, 0), so a box would be defined by two of its corners at (-1, -1, -1) and (1, 1, 1). As you can see, the object's center is at (0, 0, 0). These are called object coordinates, and are going to stay the same. You use them to get the world coordinates after you transform them to the appropriate location. For animations you transform them by different amounts to give the sense of movement. This is another reason for not changing the object coordinates: after too many transformations the coordinates would get screwed up by rounding errors, so that even if you rotate them a full 360 degrees, you won't end up where you started. Ok, so the world coordinates are the ones that you are going to finally display on the screen after perspective projection.

Transformations

But how do you move 3D points around (transform them)? Simple displacement or translation is done by adding or subrtacting from the point's coordinates. If you want to move a point to the right you add 1 to its x coordinate, for example. You can also scale an object by multiplying each of its vertices by a given value. Rotation is a bit more complicated, because you have to use sine and cosine functions on each coordinate. The rotation occurs around the origin and is done separately around each axis by the given angle. This means that you have to work with object coordinates, as for scaling. The order of rotations around each axis also matters. Here's the algorythm:

x, y, z are the coordinates of the point to be rotated,
ax, ay, az are the angles the object is to be rotated by around each axis,
rx, ry, rz are the rotated coordinates

ry = y*cos(ax) - z*sin(ax) // rotation around the x axis
rz = z*cos(ax) + y*sin(ax)

rz = rz*cos(ay) - x*sin(ay) // around y
rx = x*cos(ay) + rz*sin(ay)
^ note: this rz is the one you started with, not the one you got from the previous line; same goes for the next axis
rx = rx*cos(az) - ry*sin(az) // around z
ry = ry*cos(az) + rx*sin(az)

I think a very simple optimization won't hurt here. Sin and cos are calculated very slowly by the fpu, and if you don't have one, it's even worse. What you can do is set up an array of values that contain the sines and cosines of their indexes. It's done very simply with a for loop:

double sin[360]

for(a=0; a<360; a++)
sin[a]=sin(a);

Now all you do is use sin[angle] instead of sin(angle). Of course, you'd need a different name for the array to avoid conflicts. Another thing: the above statements won't work in actual code, because the sin() function takes angles in radians, not normal degrees (there are 2pi radians in a full circle). This is another advantage of the lookup table, you can work in degrees. Well, not exactly... In the code I used an array of 256 values, simply because they can be described by an 8 bit index which wraps around at every full circle, ie: 365º is really 5º. The only difference is that you will work with different angles, for example: 90º is 64, 180º is 128, etc. If you wanted to use an array of 360 values, then you'd have to go: sin[angle%360] which is much slower, so that you don't go over the limit of the array. All these transformations should be done on object coordinates, and the result stored in world coords. There is also a way to do all of the transformations, even the projection, at once using matrices, but it's not necessary for the current application.

Now that you have points all over space, and you're able to move them around, they can be used to form coherent objects. As I said before, an object should be defined as centered at the origin, for reasons I've already talked about. Objects are usually defined by points at their corners or on their surface. These points are called 'vertices' (vertex in singular). Neighbouring vertices are collected and connected using lines for wireframe display or used as vertices of 'polygons' for solids.

Polygon Scan Conversion

Polygons are two-dimentional (flat) shapes bounded by straight lines going from one vertex to the other. Usually triangles are used, because they always define a flat surface. For the example I used quadrilaterals, since they can be used more intuitively for a cube. By the way, polygons are plotted in two dimensions, 3D vertices are first converted to 2d using perspective projection shown above. There are many ways to draw polygons, but the main idea is to find the lines connecting the vertices and fill in the inside. The way you find an edge between two points is by using the good old y=mx+b line equation from highschool math class. In case you forgot (I didn't, cause I learned it last year :-), this equation uses an x coordinate to find a y on the line. 'm' stands for the slope of the line and b for its y-intercept (the point where x is 0). Basically all we need from here is the slope. It is defined by rise/run, ie: delta_y/delta_x; but we need x in function of y, for reasons I will explain later. Since you have the two endpoints (x1,y1) and (x2,y2), you can easily get the slope by:

m=(x2-x1)/(y2-y1)

This gives you the amount by which x changes every time you increase y by one. Now all you need to do is start at the first coordinate and each time you increment y, add m to x. It would look something like this.

   m=(x2-x1)/(y2-y1);
   x=x1;

   for(y=y1; y < y2; y++)
   {
      edge[y]=x;
      x+=m;
   }

Now I'll tell you why we needed the x coordinates. The reason is the way you fill the poly: you draw horizontal lines at each y coordinate, and you need the two endpoints. It's done with horizontal lines instead of vertical because it's much easier and faster to program. But wait! You only have one side so far. What you need to do is set up two arrays, one for the left edge(s) and one for the right. As you trace each edge, put it on the appropriate side. This is a bit tricky. I'll explain the triangles first.

First you need to sort the vertices by height. Now you can trace an edge from the top to the bottom vertex in one edge buffer, and from 1 to 2 and 2 to 3 in the other buffer. The problem here is that you don't know which side each edge should go into. Its only implication is that you might have to swap the endpoints when you're drawing your horizontal line. The other thing you can do is find the point on the long edge which is at the same height as the middle vertex. If you work out the math, this becomes:

m=(V0.x-V2.x)/(V0.y-V2.y)
x=V2.x+(V2.y-V1.y)*m

Now you subtract the middle vertex's x coordinate from the one you just got, and if the result is negative, the middle point is to the right, otherwise to the left of the long side. You use this to decide which sides belong to which edge buffer. If for some reason you can't implement it, one of the examples on the shading page does.

For polygons with more sides, you go around from one vertex to the next and trace the edges. There is no easy way to automatically put them in the right edge buffer, so you have to decide while you're tracing the side. If there was no other edge at a particular y coordinate, then the present line's x coordinate is put into both buffers. If there was another line at the particular location in the buffer you're trying to write, then you only replace the existing value if your present edge's x coordinate is more to the right, or more to the left, depending on which side it is. This means that if you have a point at 100 in both buffers and your point is 250, then you write your value to the right buffer, since it is more to the right then 100. On the other hand you can't write to the left one, because the value already present is more to the left.

   int left_edge[scr_y_res], right_edge[scr_y_res];


   for (y=y1; y < y2; y++)
   {
      if(xright_edge[y])
         right_edge[y]=(int)x;
      x+=m;
   }

This method can be used for polygons with any number of vertices, as long as they are not concave (ie: four or more sides going through the same y coordinate). Now all you have left to do is connect the two edges with a horizontal line at every y coordinate on the screen. This second method is too slow for triangles though, because of all the checks while filling the buffers, so don't use it. In general there is no reason to use anything other than triangles.

Now that you have two edge buffers, you just draw the horizontal lines from one to the other. You start at the top and work downwards:

   for(y=V0.y; y < V2.y; y++)  // for triangle with vertices sorted by height
   {
      x1=left_edge[y].x;
      x2=right_edge[y].x;
   
      for(x=x1; x < x2; x++)
      {
         putpixel(x, y, c);
      }
   }

Sorting and Backface Removal

But your object still doesn't look solid at all. That's because the back sides show up in front half the time. A logical solution is arranging the polys so that back sides stay at the back. You can sort the sides by their z value and then draw them back to front. You need to use the average z value across the polygon. You get this by adding all the z values together and dividing the result by the number of vertices of the poly. You can use any sorting algorythm you want. This still doesn't fix everything, especially with few sided polyhedrons like my cube. The next method will correct everything and also speed things up. This is about finding out if the polygon is facing towards the viewer or away. It's called 'backface culling' and is done by finding out if the vertices of the poly are in clockwise order. For this reason you should create your objects with the vertices in the right order. What you need is two vectors originating fron the same point. You get these by choosing three consecutive points and subtracting the middle one from the other two. Now you basically use the z part of the cross product (explained below) of the two vectors, which is either positive or negative, according to the points being in clockwise or anticlockwise order. You only draw the sides that are facing you, so at least half of them will always be invisible (for closed objects), saving display time. The equation is:

if ((x1*y2 - x2*y1) > 0) then clockwise

Shading

So you have a solid looking object moving around... But not quite. To make it look more realistic, you have to make the colors of its sides respond to a light source, ie: if the light rays hit the side perpendicularly it is the brightest. The brightness decreases until the polygon's edge-on to the light source when it recieves no light, same thing if it's totally facing away. But how do you find out which way it's facing? Now the 'surface normals' come into play. These are vectors that are perpendicular to the plane of the poly. So how do you get that? You use another mathematical operation called the 'cross product' (×). The cross product of two vectors is always perpendicular to both of them. This how you find it:

A and B are vectors whose cross product is C (also a vector)

A × B = C
Cx=Ay*Bz - By*Az
Cy=Az*Bx - Bz*Ax
Cz=Ax*By - Bx*Ay

To find the normal of a poly, you take 3 consecutive vertices in clockwise order (the order matters, otherwise you get a vector pointing the opposite way). You subtract the middle one from the other two and you get two vectors which you can use in the cross product. Great! Now you got a vector perpendicular to your poly. But for some reason this is not the end. You should also make it of length 1, that's why it's called a normal! You use the Pythagoran theorem (l=sqrt(delta_x²+delta_y²) to find its length, then divide each dimention by it. Since a vector always originates at 0, you don't need delta values.

l=sqrt(x²+y²+z²)
normal=(x/l, y/l, z/l)

This a slow process especially because of the square root and divisions. You calculate normals in object space when you initialize your object, and rotate them together with the vertices, because you can't calculate them every time you wanna display it. So now you need to find the angle between the normal and the light vector... Another new operation: the 'dot product' (•). This one's really simple:

A • B = (Ax*Bx + Ay*By + Az*Bz)
cos(angle)=(N • L) / (|N| * |L|)

where |N| is the length of vector N - the normal

Remember that we made the normals of length one, so you just did away with the division! Also notice that the result is the cosine of the actual angle. This is quite helpful, because it means that the possible values range from -1 to 1. Since arccos(1) is zero degrees, we know that it means maximum light intensity. 0 is 90 degrees and negative nubmers are totally facing away from the light. These values can be used very nicely at lighting, you just specify the maximum brightness of your poly. If this is multiplied by the angle, it gives you the intensity of light that you actually see if the light doesn't hit it perpendicularly. There's also the possibility of ambient light, which is scattered light that reaches even in shadows. You just add a certain value to the light intensity, so that you never get total darkness.

Intensity = Ambient + Max_obj_color*(Normal • Light)

I guess this is about it... Now you can draw flat shaded objects, which is a pretty good start. At least I hope you can. I might have left out some things and confused you with others, so if something's not clear, just ask me. I'm sure there's still lotsa work to be done on this tutorial.

Source Code and Programs

Source and Executable containing all the stuff from this tutorial. It's pretty well commented and explains the subtleties of programming specific parts of the system.

SVGA.C - my "graphics library", needed to compile the example source code. Get svga.h if you don't want errors.