11.2 - Hidden Surface Removal¶

The Painter’s Algorithm¶

A human artist creates a painting by painting the background first and then painting layer on layer until the the last thing to paint is the elements in the foreground. This can be simulated in a computer by sorting the models in a scene according to their distance from the camera and then rendering them from back to front. It is a simple algorithm, but it has the following problems:

• Sorting is time consuming. If the camera or the models are moving, sorting is required before every render.
• The individual triangles that compose a model must also be sorted based on their relationship to the camera. Fast rendering is dependent on a model’s data being stored in a GPU’s memory and never being modified. Sorting a model’s triangles breaks this scheme.
• If triangles intersect, they can’t be sorted so that one of them is closer to the camera than the other one. To render them accurately, their intersection but be found, or the triangles must be split into smaller triangles that can be sorted.

This is called the painter’s algorithm and it is rarely used in practice, except to render transparent models, which we will discuss in lesson 11.4.

The Z-Buffer Algorithm¶

A “z-buffer” is a 2D array of values equivalent in size to the color buffer which stores the pixel colors of a rendered image. Each value in a z-buffer represents the distance between an object rendered at that pixel and the camera. Remember that the camera is always at the origin looking down the -Z axis. Therefore the Z value of an element represents the distance from that element to the camera.

To render a scene, every value in a z-buffer is set to the maximum value each element can hold. As each pixel that composes a graphics primitive is rendered, the z-component of its geometry is compared to the current value in the z-buffer. If the z-component is less than the value already in the z-buffer, this object is closer to the camera, so its color is placed in the frame buffer and the z-buffer‘s value is update to this new z value. If an object’s z-value is greater than the current z-buffer value the object is not visible to the camera because there is a closer object in front of it. The following pseudocode explains this algorithm nicely. The clearBuffers function is called once to initialize a rendering. The renderPixel function is called for every pixel of every primitive that is rendered. (These functions are implemented for you in the graphics pipeline; you don’t implement them.)

void clearBuffers() {
  for (x = 0; x < image_width; x++) {
    for (y = 0; y < image_height; y++) {
      zbuffer[x][y] = maximum_z_value;
      colorbuffer[x][y] = background_color;
    }
  }
}

void renderPixel(x, y, z, color) {
  if (z < zbuffer[x][y]) {
    zbuffer[x][y] = z;
    colorbuffer[x][y] = color;
  }
}

The z-buffer algorithm is the most widely used method for solving the hidden surface problem. It has the following major advantages over other hidden surface removal algorithms:

• No sorting is required. Models can be rendered in any order.
• No geometric intersection calculations are required. The algorithm produces the correct output even for intersecting or overlapping triangles.
• The algorithm is very simple to implement.

Disadvantages of the z-buffer algorithm include:

• A z-buffer requires a non-trivial amount of memory. For example, assuming each value in a z-buffer is a 32 bit floating point value, a rendered image that is 1024x768 pixels requires 3MB of memory to store its z-buffer.
• Every pixel of every primitive element must be rendered, even if many of them never write their color to the frame buffer.
• If two primitives are in exactly the same place in 3D space, as their positions are interpolated across their respective surfaces, the z values for each object will typically be different by a very small amount due to floating-point round-off errors. These small differences will alternate between primitives for adjacent pixels resulting in random and weird patterns in a rendering. This is called “z-fighting” and it can be avoided by never placing two primitives in the same location in 3D space.

WebGL Implementation of the Z-buffer Algorithm¶

The WebGL graphics pipeline does not automatically perform hidden surface removal. You must enable it with this command:

gl.enable(gl.DEPTH_TEST);

Since WebGL is a “state machine”, you only need to execute this command once, unless you want to turn hidden surface removal on and off for special types of rendering. To disable hidden surface removal you call gl.disable(gl.DEPTH_TEST);

There are three buffers that typically need clearing before a rendering begins. These are identified using enumerated type constants defined inside the WebGL library. (Never use the numerical values; always use the constant names.) These values are “bit flags”. Notice that each value has a single bit set. You can combine “bit flags” into a single value using a bit-wise or operation, which in JavaScript is a single vertical bar, “|”. (Note that any value specified with a leading 0x is a hexadecimal value (base 16).)

const GLenum DEPTH_BUFFER_BIT   = 0x00000100;
const GLenum STENCIL_BUFFER_BIT = 0x00000400;
const GLenum COLOR_BUFFER_BIT   = 0x00004000;

To clear the frame buffer and the z-buffer at the beginning of a rendering you call the gl.clear() function. The input argument is a single integer containing “bit flags” that indicate which buffers to clear. You can clear one, two, or three buffers simultaneously. The command

gl.clear(gl.COLOR_BUFFER_BIT | gl.DEPTH_BUFFER_BIT);

clears the color and depth buffers, or more specifically, the color buffer and the z-buffer. Every pixel in the color buffer is set to the background color. Every element in the z-buffer is set to the maximum z-value possible.

WebGL Details¶

Note that, depending on the attributes of your WebGL context, the default behaviour is to automatically clear the off-screen frame buffer after each refresh of the on-screen canvas window. Therefore, you actually do not need to call gl.clear() before each rendering. However, you can modify the attributes of your WebGL context to prevent this automatic clearing operation by setting the preserveDrawingBuffer attribute of the WebGL context to true. This must be done when the context is initially created like this:

context = canvas.getContext('webgl', { preserveDrawingBuffer : true } );

(See this WebGL API page for a list of all the possible attributes of a WebGL context.) Even if you turn off automatic clearing of the canvas frame buffer, most browsers seem to clear them anyway on page refreshes. Therefore performing non-standard rendering techniques in a browser can be difficult. To guarantee predicable behaviour you should always clear the frame buffer and z-buffer as the first step of any rendering operation.

For general rendering the gl.enable(gl.DEPTH_TEST); and gl.clear(gl.COLOR_BUFFER_BIT | gl.DEPTH_BUFFER_BIT); commands are the only commands you will ever need. However, WebGL gives you tools to control the z-buffer at a finer level of detail for special rendering problems. You may never need the following commands, but you should know they exist.

• gl.depthMask(bool flag) : Enables or disables writing to the z-buffer. This allows you to render a model to the frame buffer but not update the depth of those pixels. You might want to do this if you render a transparent model and you want objects further away from the camera to still be rendered. This only makes sense if you are blending colors during rendering. See the alpha blending discussion in lesson 11.4.
• clearDepth(float depth), where depth is a value between 0.0 and 1.0. This sets the value used to clear the z-buffer. The “depth” is a percentage of the range of values that can be stored in the z-buffer. The default value is 1.0, which clears a z-buffer to its maximum value.
• depthFunc(enum func), where the parameter can be one of: gl.NEVER, gl.ALWAYS, gl.LESS, gl.EQUAL, gl.LEQUAL, gl.GREATER, gl.GEQUAL, gl.NOTEQUAL. This gives you fine grain control over the test that determines whether a color is written to the frame buffer.

Given the ability to set these extra values for the z-buffer algorithm, we can describe the algorithm in more detail using the following pseudocode:

void clearBuffers() {
  for (x = 0; x < image_width; x++) {
    for (y = 0; y < image_height; y++) {
      zbuffer[x][y] = maximum_z_value * depthPercentage;
      colorbuffer[x][y] = background_color;
    }
  }
}

void renderPixel(x, y, z, color) {
  if (depth_text_is_enabled) {
    switch (depthFuncMode) {
      case NEVER:    condition = false;
      case ALWAYS:   condition = true;
      case LESS:     condition = (z <  zbuffer[x][y]);
      case EQUAL:    condition = (z == zbuffer[x][y]);
      case LEQUAL:   condition = (z <= zbuffer[x][y]);
      case GREATER:  condition = (z >  zbuffer[x][y]);
      case GEQUAL:   condition = (z >= zbuffer[x][y]);
      case NOTEQUAL: condition = (z != zbuffer[x][y]);
    }
    if (condition) {
      if (zbufferWriteEnabled) { zbuffer[x][y] = z; }
      colorbuffer[x][y] = color;
    }
  else {
    // No hidden surface removal
    colorbuffer[x][y] = color;
  }
}

Experimentation¶

Using a WebGL demo program from a previous lesson, make the following suggested changes to see the effect of these z-buffer commands on a rendering.

• In line 128, change gl.enable(gl.DEPTH_TEST); to gl.disable(gl.DEPTH_TEST);. This turns off hidden surface removal. After re-starting the program, notice the strange renderings. You are basically seeing the “painter’s algorithm” without any sorting. The triangles are drawn one after the other and the ones you see are the last ones drawn.
• Comment out line 67 that clears the buffers. What a rendered mess!
• Enable the depth buffer, clear the color buffer, but don’t clear the depth buffer. Does the rendered results make sense?

Glossary¶

hidden surface removal

An algorithm for determining the visible triangles in a scene. Or, an algorithm for determining the hidden triangles in a scene and not rendering them.

painter’s algorithm

Sort the graphic primitives in a scene and render them back to front.

z-buffer algorithm

For every rendered pixel, store its distance from the camera and only render a different object for that pixel if the object is closer to the camera.

bit flag

An integer number that has a single bit set to one.

bit flags

An integer number where each bit represents a different “flag”.