12.2 - Hidden Surface Removal¶

The Painter’s Algorithm¶

A human artist creates a painting by applying the background paint first and then painting layer upon layer until the foreground objects are painted last. 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 drawbacks:

• 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 such that one of them is closer to the camera than the other one. To render them accurately, their intersection must be found, or the triangles must be split into smaller triangles that don’t intersect and then sorted.

This is called the painter’s algorithm and it is rarely used because of its drawbacks. However, it is used to render transparent models, which we will discuss in lesson 12.4.

The Z-Buffer Algorithm¶

A “z-buffer” is a 2D array of values equivalent in size to the color buffer that stores 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 its distance from the camera.

To render a scene, each element in a z-buffer is set to some “maximum value”. 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 in the z-buffer, this object is closer to the camera, so its color is placed in the color buffer and the z-buffer’s value is update. 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. This algorithm is explained nicely in the following pseudocode. The clearBuffers function is called once to initialize a rendering. The renderPixel function is called for each pixel of every primitive that is rendered. (Note: These pseudocode functions are “hardcoded” into the graphics pipeline hardware; you don’t implement them.)

void clearBuffers() {
  for (x = 0; x < image_width; x++) {
    for (y = 0; y < image_height; y++) {
      z_buffer[x][y]     = maximum_z_value;  // depth buffer
      color_buffer[x][y] = background_color;
    }
  }
}

void renderPixel(x, y, z, color) {
  if (z < z_buffer[x][y]) {
    z_buffer[x][y]     = z;                  // depth buffer
    color_buffer[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 color 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:

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 API. (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 color buffer and the depth buffer (z-buffer) at the beginning of a rendering call gl.clear(bit_flags). 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 buffer and depth buffers. Every pixel in the color buffer is set to the background color (gl.clearColor(red, green, blue, alpha)). Every element in the depth buffer is set to the maximum depth value (which defaults to 1.0, but can be changed using gl.clearDepth(depth)).

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

int     depth_test_func = LESS;  // DEFAULT
boolean write_depth     = true;  // DEFAULT
float   maximum_z_value = 1.0;   // DEFAULT

void gl.depthMask(bool flag) {
  write_depth = flag;
}

void gl.clearDepth(float depth) {
  maximum_z_value = depth;
}

void gl.depthFunc(enum func) {
  depth_test_func = func;
}

void gl.clear() {
  for (x = 0; x < image_width; x++) {
    for (y = 0; y < image_height; y++) {
      depth_buffer[x][y] = maximum_z_value;
      color_buffer[x][y] = background_color;
    }
  }
}

void renderPixel(x, y, z, color) {
  if (depth_test_is_enabled) {           // gl.enable(gl.DEPTH_TEST);
    if (passes_depth_test(x, y, z)) {
      if (write_depth) depth_buffer[x][y] = z;
      color_buffer[x][y] = color;
    }
  } else {                               // gl.disable(gl.DEPTH_TEST);
    color_buffer[x][y] = color;
  }
}

boolean passes_depth_test(x, y, z) {
  switch (depth_test_func) {             // gl.depthFunc(enum func);
    case NEVER:    condition = false;
    case ALWAYS:   condition = true;
    case LESS:     condition = (z <  depth_buffer[x][y]);  // DEFAULT
    case EQUAL:    condition = (z == depth_buffer[x][y]);
    case LEQUAL:   condition = (z <= depth_buffer[x][y]);
    case GREATER:  condition = (z >  depth_buffer[x][y]);
    case GEQUAL:   condition = (z >= depth_buffer[x][y]);
    case NOTEQUAL: condition = (z != depth_buffer[x][y]);
  }
  return condition;
}

Summary¶

In summary,

• To enable WebGL’s “hidden surface removal” algorithm, simply call gl.enable(gl.DEPTH_TEST); once.
  
  
• To get a specific background color, set the color once using gl.clearColor(red, green, blue, alpha) and then call gl.clear(gl.COLOR_BUFFER_BIT); at the beginning of each rendering.

Glossary¶

hidden surface removal

An algorithm for determining the visible geometric primitives in a scene. Or, an algorithm for determining the hidden geometric primitives 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”.

Self Assessment¶