Home | Gaming | Programming | Play Online | Contact | Keyword Query
Games++ Games & Game Programming

GAMES++
Games++ Home
Games++ Gaming
Games++ Programming
Beta Testing Games
Free Online Games
Hints & Cheats

BROWSER UTILITIES
E-mail This Page
Add to Favorites

SITE SEARCH

Web Games++

AFFILIATES
Cheat Codes
Trickster Wiki
Game Ratings
Gameboy Cheats
PlayStation Cheats
BlackBerry Games
Photoshop Tutorials
Illustrator Tutorials
ImageReady Tutorials

ADVERTISEMENT

ADVERTISEMENT

Information on the Z-Buffer Algorithm

3D Graphics Programming

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

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;

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

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.

Copyright © 1998-2007, Games++ All rights reserved. | Privacy Policy