==============================================================================
                    Information on the Z-Buffer algorithm                    
                              by John De Goes                                
==============================================================================

  Disclaimer:                                                                 
             I assume no responsibility for any ill effect this file (or imp- 
            lementation thereof) is capable of doing to you, your spouse, any 
            and all of your possessions, or anything or anyone related to you 
            or your existince.                                                
                                                                               
  Lack of warranty:                                                           
                  There is no warranty for any file included in this archive, 
                  nor is any expressed or implied. If you wish to make use of 
                  these files,  you must assume full responsibility for what-  
                  ever effect they might cause upon anyone or anything.        
                                                                              
  Note: You may not modify this file in any way with out the author's         
        express permission. You may distribute it however.                    
                                                                              
==============================================================================

------------------------------------------------------------------------------
  Assumptions
------------------------------------------------------------------------------

I will assume you have some basic knowledge of 3-space coordinates and
transformations. I will also assume that the Z coordinate increases as it
moves into the screen. You also must draw your polygons in a top to bottom
fashion. If you've read Flights Of Fantasy (C. Lampton, Waite Group Press),
you won't have any problems. If you have not yet bought a copy of Flights Of
Fantasy, and you would like a great introduction to 3D graphics, then rush
right out to the nearest bookstore and pick up a copy. And no, I don't work
for the Waite Group Press, it's just a good book <g>

------------------------------------------------------------------------------
  Introduction to the Z-buffer algorithm
------------------------------------------------------------------------------

The Z-buffer algorithm, invented by E. Catmull, has been around since the
1970's. Because of it's simplicity, and because it can handle just about
any 3D primitive, it has become the number one choice for hardware accelerated
3D boards. Only recently however, have PC developers started to look at the
Z-buffer algorithm as an alternitive to depth-sorted algorithms. This is
mainly because of the increased memory and speed of the modern PC.

------------------------------------------------------------------------------
  Description of the Z-buffer algorithm
------------------------------------------------------------------------------

Unlike depth-sort algorithms, the Z-buffer is an image-precision algorithm,
meaning it operates at the pixel level rather than the object level. Depth-
sort algorithms are termed object-precision algorithms because they deal with
hidden surface removal at the object level. For the most part, object-
precision algorithms tend to be fairly independent of the size of the
viewport. On the other hand, image-precision algorithms are directly dependent
on the size of the viewport. Although for certain applications object-
precision is faster than image-precision, in multi-thousand polygon
enviroments image-precision can actually outperform object precision.

With most depth-sorted algorithms, all the objects in the world are drawn in a
back-to-front manner, requiring allot of sorting and a bunch of tests to
correctly order the polygons in a back-to-front manner. Some methods require
polygons to be non-intersecting. Others require that all polygons in the
world remain stationary.

The Z-buffer algorithm imposes no such limitations. As a matter of fact, the
Z-buffer imposes no limitations at all. It does require that you have a good
amount of memory, and a fast processor though.

The idea behind the Z-buffer algorithm is that you perform a test on every
pixel of every polygon that you draw. The test involves comparing the Z
coordinate of the point you're drawing with the Z coordinate of the last point
written on that x,y screen point. You know the Z coordinate of the last point
written, because you stored it in the Z-buffer when you wrote the pixel. If
that pixel has not yet been written, the Z-buffer at that x,y point holds the
value that it was cleared to before the rendering process began. The pixel is
only written if the Z coordinate of the point you're drawing is closer to the
viewer than the Z coordinate of the last point written. If the Z coordinate of
the point you're drawing is closer to the viewer than the last point written
at that position, then the Z value is stored in the Z-buffer and the pixel is
written to the screen.

Reread the last paragraph until you get it, as it's the key to understanding
Z-buffering.

------------------------------------------------------------------------------
  Polygon implementation details
------------------------------------------------------------------------------

The Z-buffer is a 2-dimensional array consisting of float values. In this
array is eventually stored the Z coordinates of your polygons. For instance,
if you drew a Z-buffered triangle that was directly facing the viewer (and was
five Z units away), your Z-buffer would look something like this:

         ========    
        |   55   |
        |  5555  |
        | 555555 |
         ======== 

With all the blanks representing zero. If we drew another polygon as big as
the screen on this Z-buffer that was 6 units away it would look like this:

         ========    
        |66655666|
        |66555566|
        |65555556|
         ======== 

The rest of the polygon didn't show because 5 is closer to the viewer than 6.
What follows is a few examples Z-buffers.

        ========       ========       ======== 
       |55555555|     |66666666|     |55555555|
       |55555555|  +  |66666666|  =  |55555555|
       |55555555|     |66666666|     |55555555|
        ========       ========       ========

        ========       ========       ======== 
       |44444444|     |11111111|     |11111111|
       |3333333 |  +  | 222222 |  =  |3222222 |
       |222222  |     |  3333  |     |222222  |
        ========       ========       ======== 

        ========       ========       ======== 
       |55555555|     |6543210 |     |5543210 |
       |  555555|  +  | 6543210|  =  | 6543210|
       |     55 |     |  654321|     |  654321|
        ========       ========       ======== 

        ========       ========       ========   
       |55555555|     |22222222|     |22222222|
       |55555555|  +  |44444444|  =  |44444444|
       |55555555|     |66666666|     |55555555|
        ========       ========       ======== 

Study those neat little ASCII drawings for a while. You'll get it if you
stare at them long enough. The end result of the rendering process will be
that the Z-buffer contains the Z-coordinate of every point that is visible.

Here's how we would declare a Z-buffer in C/C++:

float Z_Bufer[Width][Height]; /*If viewport large, use malloc(or C++ new)*/

The number of elements in the Z-buffer coresponds to the number of pixels in
the viewport. To read the Z value at a particular x,y, we could use the piece
of C code that follows:

float ReadZ(int x, int y)
    {
    return Z_Buffer[x][y];
    }

To write a Z value at a particular x,y, we could use the following:

void WriteZ(int x, int y, float z)
   {
   Z_Buffer[x][y] =  z;
   }

And our structure for storing Z values and x,y values is as follows:

struct Screen_Point
     {
     int X, Y;  /*The X and Y values for the screen point*/
     float Z;   /*A '1/Z' value at the screen point*/
     }

Of course, the Z-buffer read/write functions are much too slow to actually
use. We should directly access the Z-buffer from within our polygon renderer.
Nevertheless, I will refer to these functions for clarity's sake.

Before we use our Z-buffer for each frame, it is necessary to clear it to
zero. So our basic outline for a Z-buffer is as follows:

for every frame do
    begin
        transform 3D points
        elimenate unnecessary polygons
        clear Z-buffer to zero
        draw all polygons
    end

The Z values we want to deal with are actually 1/Z values. Doing it this way
enables us to linearly interpolate the Z values across polygon edges. This
also mean we will have inverted Z, so points that are far away will have small
numbers, and points that are close to the viewer will have larger numbers. To
do this not-so-miraculous feat, we put some code in our projection function.
As the 3D points are projected onto the screen, we store a 1/Z value at that
x,y point. Like this:

Screen_Points[i].X = World_X * Distance / Z;
Screen_Points[i].Y = World_Y * Distance / Z;
Screen_Points[i].Z = (float) 1 / Z;
    
Where Screen_Points is an array of polygons screen vertices.

Ok. Let's draw some polygons! What we have to do now is linearly interpolate
the 1/Z values amoung our polygon edges. This is VERY important for you to
understand. Suppose we have a polygon edge that goes from Screen_Point[0] to
Screen_Point[1]. We need to interpolate the 1/Z value from Screen_Point[0] to
Screen_Point[1]. Just remember we have THREE points to interpolate. The two
edges of the polygon AND the scanline we're drawing. As we draw our polygon
in horizontal strips, we use the interpolated 1/Z coordinate (interpolated
between our two edges) and use that value for the Z coordinate at that x,y
point. We then put code as follows:

if (ReadZ(x,y) < Z)
   {
   WriteZ(x,y,Z);
   /*If texture mapping, assign a value to color*/
   Write_Pixel(x,y,color);
   }

It looks as if that's wrong however, because we are checking to see if the
point stored in the Z-buffer is smaller than the point we are working with (Z
increases toward screen). But because our Z coordinates are actually 1/Z, we
must check for the reverse of what we normaly would (less-than as opossed to
greater-than). That's why we clear our Z-buffer to zero instead of some high
number.

I'm going to give you some rough equations (no optimizations), but they should
get you started. For calculating the 1/Z at a particular x, with the polygon
edge(or line) moving from x1,y1,z1 to x2,y2,z2 the code is as follows:

float Z_Slope = (float)(z2 - z1) / (float)(x2 - x1);
float Z = z1 + ((X_Point - x1) * Z_Slope);

Where z1 and z2 are the 1/Z (at that vertex) values we discussed earlier, and
x1 and x2 are the coordinates of the edge or line. y1 and y2 are not used
because we are drawing from top to bottom and know what y coordinate we are
on.

And remember, we have THREE seperate versions of these variables. One for each
of the two edges of the polygon, and one for when we draw each horizontal
scanline. In the latter case, the z1 and z2 are the 1/Z coordinates of the
two edges.

To summarize, we draw our polygon as normal, except as we draw the
polygon's edges we also calculate two 1/Z  values at the two edges of the
polygon we are currently drawing. As we step accross pixels from the left side to
the right, we calculate yet another 1/Z value. This is the value we use for
the test. We calculate it by using the equations above with x1 as the left
side of the polygon's edge, x2 as the right side of the edge, z1 as the left
edges's 1/Z value and z2 as the right edges 1/Z value. This gives us the 1/Z
value for that pixel. Each one of these uses the equations discussed
previously.
            
Don't forget 2D clipping is effected by this. I hope to release some source
for clipping Z-buffered polygons.

                                Polygon   
                                   /\   
left edge has it's own x,1/Z      /..\     right edge has it's own x,1/Z  <= scanline we are drawing
                                 /    \     
                                /      \   
                               /        \
                               \        /  y is constant for entire edge
                                \      /
                                 \    /
                                  \  /
                                   \/

if (NoComprehend())
   goto top;        <grin>

------------------------------------------------------------------------------
  Optimizations
------------------------------------------------------------------------------

First we'll move Z_Slope outside the inner loop, and we'll use incremental
calculations.

float Z_Inc = (float)(z2 - z1) / (float)(x2 - x1);   
float Z = z1;

Then for every pixel (or increment in scanline) we put:

Z += Z_Slope; /*only one add per pixel or edge*/

That's about all the mathamatical optimizations you'll get. The next step to
draw the polygon out of 'constant Z' lines. A discussion on constant Z lines
is too lengthy for this article to cover. Suffice it to say it involves
drawing your polygon out of slanted lines instead of horizontal ones.

Using fixed-point math will also speed you up a bit on 486's. Also if you're
drawing walls and floors only, you can build two custom polygon renderers. One
for walls, and one for floors. In two these cases it's easy to draw the
polygons out of constant Z lines because you can hard-code it in you're
renderer. Walls you draw out of vertical strips, floors out of horizontal. The
advantage to this is you don't have to increment Z for each scanline. Saving
you one floating point addition.

Also, if you're texture mapping or doing advanced shading, you can jump a leap
over other algorithms by doing a ROUGH FRONT-TO-BACK sort in each frame (or in
every other frame).

------------------------------------------------------------------------------
  Special effects and suggestions
------------------------------------------------------------------------------

Front object detection can easily be accomplished with a Z-buffer. Before
moving the viewer to the new point, check the center (and maybe a few sides)
of the Z-buffer to see if they're too close (1/(ReadZ(x,y)).

Morphing terrain is no problem either. Clouds look good. Gourand shading is
easy because you have the Z at each pixel (1/Z gives you the world Z). Polygon
piercing is a cinch (and it's accurate). Depth shading is so easy you wouldn't
believe it. Depth shading can also be made to extend in a circlar fashion
around the viewer (which is accurate, unlike most games).

I know I've rushed it, but we've covered 20 years in 20 minutes <g>

------------------------------------------------------------------------------
  Last words
------------------------------------------------------------------------------

Dedication: to Jeff, Andre, Christopher, Chris and anybody else who's
            helped me through the tough times I've encountered.

If you don't get all this, contact me at one of addresses below (or better
yet, send me a message through GAMEDEV) and I'll be happy to clarify it for
you.

Internet: 104047.2713@CompuServe.COM
CompuServe: John De Goes at 104047,2713

