RuTh's  RuThLEss  HomEpAgE


3D Game DesignEnglish
Programming Links
* INDEX * 3D game to-do list * 3D Engine to-do list ( chapter 1, 2, 3, 4, 5, 6, 7 ) *
* projection formula * transformation matrices * Bresenham algorithm * Scanline Polygonfill algorithm *
* Spieldesign / game design * Troubleshooting 3D * Irrlicht 3D engine * Blender for Beginners *

Chapter 5 -- Hidden Surface Removal With the Z-Buffer Algorithm

The need for Hidden Surface Removal (also known as Visual Surface Determination) only appears if you display more than one object, because they could obstruct each other. Just to show you the difference it makes: What would happen, if we skipped hidden-surface removal? Look at the following screenshot of three cubes. They are all the same size, but are placed into the world at different depths — so obviously the one in the back appears smaller than the one in the front. But as long as we do not explicitly deal with depth and hidden-surface removal, we'll keep on getting random display errors like the following.

The middle cube, which is furthest away, partially obstructs the right cube, which is the front-most!

Display error: The middle cube, which is furthest away,
partially obstructs the right cube, which is the front-most!

Whole backfacing polygons were already culled in chapter 2. Our routine however still ignores depth information and draws objects in the order they were defined, while we of course want objects in the back to be (partially) obstructed by objects in the front. Tieskoetter quickly uses the Painter's algorithm and only describes the better Z-Buffer algorithm, which I'll go for in this example.

Understanding the Z-Buffer Algorithm

Think of a 3-dimensional landscape. When a map is created, you get a top-down view of the landscape, but all height information is lost. This is usually okay for driving a car, but if you want to do something spacialy more sophisticated, like hiking or climbing, you need the height information. This is why there are 2D topographic maps with labeled contour lines.

An image of two hills in a landscape, and a topographic map's top-down view with encoded hight-information.

The map's lost height information is encoded ("buffered") in the labels/colors.
In this example, darker green means lower and lighter green means higher.

In a 3D game projection, a similar loss happens: Everytime you project a polygon from 3D to the 2D screen, you lose the depth information, also called the z-coordinate. But like the labels on the topographic map, we can save the otherwise lost depth information in its own 2 dimensional buffer, the so-called z-buffer.

The z-buffer consists of an array with the same amount of fields as there are pixels in the normal 2D framebuffer. For every z-coordinate of a pixel (x,y,z) that is lost due to projection, a z value is recorded in the array's field at position (x,y).

A normal 3D cube, and a grayscale-encoded map of its depth information.

If you'd assign a grayscale to each value in the z-buffer array and then draw it to the screen,
it would look like a topographic map, only for depth instead of height.
The brighter the grayscale, the more to the front the pixel is,
the darker, the deeper it is into the image.

Here's the scoop: Everytime before you plot another pixel P into the framebuffer at (x,y) with depth zp, you look at the z-value zbuf stored in the z-buffer at (x,y):

  • If the stored z-value zbuf is higher then zp, then P is closer to the viewer and obstructs the existing pixel!
    1. You overwrite zbuf in the z-buffer with the closer value zp.

    2. You plot the pixel P(x,y) to the framebuffer.

    3. Go to the next pixel.

  • If the stored z-value zbuf is lower then zp, then P is further away from the viewer and is obstructed by the exiting pixel!
    1. Leave the stored zbuf in the z-buffer as is.

    2. Don't plot P to framebuffer.

    3. Go to the next pixel.

The Mathmatics of the Z-Buffer Algorithm

The Z-Buffer algorithm is implemented into the inner loop of the drawFilledpolygon method (which itself employs the scanline polygonfill algorithm). Here is how we proceed, expressed in pseudo-code:

initialize z-buffer with max viewing distance
for each polygon do
  for each projected pixel P(x,y) do
    interpolate P's depth z 
    if( z < zbuffer(x,y) )  /* Yes, it is visible */
      set zbuffer(x,y) = z    /* remember this pixel depth */
      determine P's color c   /* color, shading etc */
      draw color c to framebuffer at (x,y) /* draw */
      /* Else, pixel is obstructed and not drawn */  

Only — When you head out to implement the z-buffer algorithm, you will quickly notice which piece of information you are missing: We only know the z-coordinates of the polygon's corners... While drawing the filled polygon, we never actually calculated any of the z-coordinates inside the polygons, since we only dealt with pixels after the polygon was already projected to the 2D screen, and the depth information was already lost. And we definitely don't want to use Matrix calculus on every single pixel! Luckily, there's an easier way: There's a formula to estimate all z-coordinates on a polygon of which only the corner coordinates are known. This estimation is called interpolation.




z-fighting (same z-value)


to be continued ... =-)

Related Links