Sign Based Z-Buffers

Hidden surface removal is a key component of any 3D engine. Unfortunately, it is often difficult to achieve a decent speed with the most popular method; the z-buffer. Personally, I fell in love with the z-buffer's ease of use. Compared to most systems in use it is not only easier to understand, but also easier to implement. The problem? It's slow. The reason? It needs to be cleared once per frame. If the need to clear the z-buffer could be eliminated then the algorithm would be next to perfect.

I intend to show you how the above can actually be achieved. Through a simple programming trick you can render an infinite number of frames without clearing the z-buffer. There is only one restriction, which I will explain as well. However, in my own opinion, the restriction is minor and in most cases not even an issue.

The theory of the Z-Buffer

I'm sure most of you know the theory behind the z-buffer algorithm, but I'll provide a brief introduction to those who aren't as familiar. Basically a z-buffer is just that, a buffer filled with z co-ordinates. When rendering polygons you are required to interpolate every pixel's z value and compare it to the z-buffer. If your z is closer to the viewer that the current z value in the z-buffer, you plot your pixel and readjust the z-buffer value, otherwise the pixel is ignored.

In other words, the z-buffer has the same dimensions as your rendering surface, except instead of holding colour values, in holds z values. As you can see, the algorithm is extremely simple to explain and implement. Another advantage is that it has no ordering requirement. Polygons can be rendered in any order, unlike other systems which require them to be sorted.

The disadvantage here is that after every frame you must clear the z-buffer back to zero. You don't want to be comparing the new polygon's z values with old ones in the z-buffer from the previous frame. This is what we will be eliminating.

Getting rid of the Z-Buffer clear

In the tradition of the z-buffer, this addition to the algorithm is also extremely easy to understand and implement. In fact, any existing z-buffer implementation should require very little change to fit this system. There are but two alterations. I will explain them each briefly then describe how the two work together to create this new z-buffer system.

The secret is in what you put into the z-buffer. Instead of putting in the actual z value, we will alternate between positive and negative versions of the actual z value. Perhaps you can see what is about to happen already. There will be no need to clear the z-buffer to zero, because by the time you're inserting the positive numbers into the z-buffer, it will be filled with negative numbers which, of course, are less than zero. By contrast, when you're inserting negative numbers, the z-buffer will be filled with positive ones.

The last change is in your testing code. When you're inserting positive numbers nothing changes, you continue to test and plot the pixel if its z is greater than the value in the z-buffer. However, when inserting negative numbers you plot the pixel if its negative z is less than what is in the z-buffer.

The concept is simple. There is no need to clear the z-buffer back to zero because all existing numbers in the z-buffer will be of the opposite sign of what you are testing. Essentially they already are zero, or rather non existent. With the alternating testing code they will always be farther away then the pixel you are testing.

In other words, by switching the sign and test code you essentially perform your z-buffer calculations on one side of zero, and then the other side of zero in the next frame. Each frame clears the opposite side of zero simply by plotting pixels (sense the z-buffer will be of opposite sign, and therefore non-existent, the first round of pixels will always pass the z-buffer test, and will be plotted, erasing previous opposite sign values for the next frame).

Perhaps some code will help explain this. It is a simple concept, but perhaps a little difficult to explain in print without code.

// odd frame number
if(view->frame_num & 1) {
  if(view->zbuf[z_offset] > -z) {
    view->zbuf[z_offset] = -z;
    fputpixel(address, c);
  }
} else {
  if(view->zbuf[z_offset] < z) {
    view->zbuf[z_offset] = z;
    fputpixel(address, c);
  }
}

As you can see, it's really very simple to incorporate this into your current code. This code simply checks the frame number to see if it's divisible by 2 to determine wether this frame is even or odd. My code uses negative z's on odd frames, and positive z's on even frames, but it really doesn't matter which you choose.

The Restriction

As I mentioned previously, this method does have one restriction. Perhaps some of you have discovered this already; with this method you must use the entire z-buffer each frame. If you don't, then the other size of zero will not be cleared. In other words, there will be z values left over in the z-buffer that shouldn't be. While it can produce an interesting effect it probably isn't what you'd want in a professional product.

The solution? I'd like to suggest you don't particularly have to worry about it. If you are developing a game then you will certainly be using the whole z-buffer at all times. In fact, many 3D programs will use the entire z-buffer, and for these programs the restriction is not an issue.

For those products that do not use the entire z-buffer there is a solution. You could simply put a large polygon in the background that covers the entire z-buffer. Texture map it and make it your background image, if you wish. However, if you aren't using the entire z-buffer you are, no doubt, simply displaying a single 3D object on a black background, in which case perhaps a regular z-buffer would suffice. It all depends on how fast your polygon routines are for large polygons versus how fast you can clear the z-buffer. Obviously, you simply use the fastest method.

All and all, though, if you're using the entire z-buffer you'd be hard pressed to find a faster solution than the sign based z-buffer.