Rendering

Rasterization: Z-buffer Algorithm

The purpose of this post is to understand and implement the z-buffer algorithm to solve the visibility problem. The visibility problem is the problem of deciding which elements of a scene are visible and which are hidden.

Introduction to Rasterization

Rasterization transform an image from a vector graphics format to a raster image(composed of pixels and dots) for output in a monitor, printer or for storage(bitmap file format). Rasterization is the most popular technique for producing real-time 3D computer graphics. Compared with other rendering methods(such as ray-tracing), Rasterization is extremely fast.

The Z-buffer Algorithm

The idea of the Z-buffer algorithm is to use a 2D matrix(z-buffer or depth-buffer) to store the depth of the closest object to the observer’s view. When a object is rendered, the depth of a generated pixel(z coordinate) is stored in the depth buffer. If another object must be painted in the same pixel, the depth of the new pixel is compared with the stored depth, if the new pixel’s depth is closer than the stored depth then the value of the pixel in the z-buffer is overriden. The z-buffer will allow to reproduce depth perception correctly.

Depth representation with Z-buffer

The previous example shows two objects in a 3D-space transformed to a 2D projection-plane. The second row shows the values of the Z-buffer matrix and how the Z-buffer algorithm process overlapping.

An important characteristic of the z-buffer is the granularity. The granularity of a z-buffer defines the scene’s quality. A 16-bit z-buffer could result in artifacts(called z-fighting or stitching) when two object are very close each other. As higher z-buffer size, better image quality will be rendered, avoiding artifacts but the problem cannot be entirely eliminated without additional algorithms. 24-bit or 32-bit Z-buffer is more accurate. A 8-bit Z-buffer is almost never used because it has too little precision.

Z-fighting with multiple colors and textures over a grey background

Pseudo-Code

The following pseudo-code shows how Z-buffer algorithm works. The algorithm receives as input the list of polygons Plist = {P1, P2, …, PN} and return a color array COLOR(x, y) representing the color for each pixel in the projection plane.

  • Given: A list of Polygons Plist={P1, P2, …, PN}
  • Output: A color array
  • Initialize:
    • zBufferArray(x, y) = maxDepth -> array of depths for the projection plane.
    • colorArray(x, y) = backgroundColor -> array of colors for the projection plane.
  • Begin:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    FOREACH polygon IN Plist DO {
      FOREACH pixel(x, y) IN polygon DO {
          CALCULATE zDepth OF polygon AT (x, y)
          IF (zDepth < zBufferArray[x, y]) THEN
              zBufferArray[x, y] = zDepth
              colorArray[x, y] = color AT polygon[x, y]
          END IF
      END FOREACH
    END FOREACH
    RETURN colorArray

The Implementation

The Z-buffer algorithm was implemented using the javascript library P5.js. The algorithm iterates over an array of polygons, each of them with a matrix of pixels representing the color and depth of each pixel. So, each value in the matrix is a quadruple representing the three main colors in RGB format(Red, Green, Blue) and the last item of the quadruple is the depth of the polygon for that pixel. As a result, the implementation return a matrix of colors representing the color for each pixel in the representation view which is shown to the viewer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
function zBuffer(polygons) {
  let zBufferArray = [];
  let colorArray = [];
  /* Initialize arrays */
  for (let i = 0; i < this.config.sketchHeight; i += 1) {
    let bufferRow = [];
    let colorRow = [];
    for (let j = 0; j < this.config.sketchWidth; j += 1) {
      bufferRow.push(Infinity);
      colorRow.push(this.backgroundColor);
    }
    zBufferArray.push(bufferRow);
    colorArray.push(colorRow);
  }
  // Iterate over all polygons
  for (let i = 0; i < polygons.length; i += 1) {
    const polygon = polygons[i];
    for (let j = 0; j < polygon.length; j += 1) {
      const pixelRow = polygon[j];
      for (let k = 0; k < pixelRow.length; k += 1) {
        // Check z-depth of pixel
        if (pixelRow[k][3] < zBufferArray[j][k]) {
          zBufferArray[j][k] = pixelRow[k][3];
          colorArray[j][k] = pixelRow[k];
        }
      }
    }
  }
  return colorArray;
}

Results

After implementing the z-buffer algorithm in Javacript Library P5.js. Two images were generated, the first one, the image in 2D of the representation view of the polygons. The second one, the image of the depth representation using z-buffer.

2D Representation view of the 3D original image

The above image shows the representation of Z-buffer in grayscale. As darker the polygon is, closer to the viewer is. The Z-buffer algorithm is extremely fast, compared with some ray-tracing algorithms. That is why Rasterization is most common used in Video games image rendering, because it allow games to feel real, allowing at least 30 frames per second rates, depending of the video card adapter.

Z-buffer representation of polygon depths of the 3D original image

References

  1. W.K. Giloi, J.L. Encarnação, W. Straßer. “The Giloi’s School of Computer Graphics”. Computer Graphics 35.
  2. N. Calvo. Computación Gráfica: El espacio de la imagen. Link
  3. University of Helsinki. The z-Buffer Algorithm. Link
  4. Wikipedia. Z-buffering. Link
  5. D. Rousset. “Tutorial part 4: learning how to write a 3D software engine in C#, TS or JS – Rasterization & Z”. Link
Intro

Introduction: My First Post

  • Edward Camilo Carrillo
  • 22 years
  • Web Developer - Student
  • Bogotá - Colombia

I’m web developer and student in the National University of Colombia. I’m a proactive person, always eager to learn new topics. I like all topics related with Software Engineering, Software Architecture and Algorithms. I’m part of TLÖN research group, focused in the development new tools to manage and control distributed and decentralized networks.

Interests

  • Software Architecture
  • Software Engineering
  • Algorithms
  • Ad-hoc networks

Projects

  • PicStory: Social network to publish and share photos.
  • UNBikeTracker: App to track bikes using a GPS device.
  • jDocumenter: Tool to document Java code in XML.
  • HardTLÖN: Module to obtain distributed resources in an Ad-hoc network.
  • RubikCube: Operator to arm and disarm a Rubik cube.