Box Filtering Height Maps for Smooth Rolling Hills
by Graham Wihlidal

Introduction

Real-time terrain is an extremely common element within most 3D engines, and generally serves as the building block for outdoor scenes.

One of the most common methods of terrain rendering is using height values to perform displacement mapping on a flat mesh grid; a method of visualizing geometry based on a source image, and scaling factors for vertex positioning. Using this technique for terrain results in sharp edges, and is generally something to avoid when developing the visuals for a cutting-edge game, especially if the environment for the game is best suited with smooth hills.

The sharp edges produced when working with height maps generally result from noise in the source image, and can be removed using one of many convolution filters. The easiest type of convolution filter to implement is Box Filtering, and will be utilized in this example to remove noise present in terrain height maps prior to rendering.

Box Filtering Technique

Box filtering, also known as average or mean filtering, is a method of reducing the intensity variation between pixels in an image, and is a commonly used technique to reduce noise.

This type of filtering is accomplished by replacing each pixel value with the average value of its surrounding neighbors, including itself. Doing so removes large intensity variations between pixels, and produces a much smoother displacement map.

A convolution filter is a simple mathematical operation which is commonly used in image processing operations. Convolution filters provide a way of multiplying two numerical arrays together, generally of different sizes, but of the same dimensionality, to produce a third numerical array which is the result of the filter operation. Of the two input arrays, one is generally the source image to process, and the second array is commonly referred to as a filtering or convolution kernel. The resultant array has the same dimensionality as the source image array.

The convolution is performed by sliding the filtering kernel over the image through all positions where the kernel fits within the boundaries of the image. This is not always the case in regards to edge smoothing though, as some implementations handle bounds checking so that the edges may be filtered as well.

Box filtering can be thought of as a convolution filter, because it too is based around a filtering kernel. This kernel represents the size of the surrounding area that will be sampled. The most common convolution filter for the box technique is a 3x3 cell size, as shown in figure 1. A larger kernel can be used for severe smoothing, or several iterations of a smaller kernel can be used to achieve similar results.

Figure 1

Using this technique, we can box filter any terrain height map, and produce smooth rolling hills, with hardly any noticeable edges.

Algorithm Example

void BoxFilterHeightMap(unsigned long width, unsigned long height,
                        float*& heightMap, bool smoothEdges)
{
  //     width: Width of the height map in bytes
  //    height: Height of the height map in bytes
  // heightMap: Pointer to your height map data
  
  // Temporary values for traversing single dimensional arrays
  long x = 0;
  long z = 0;
  
  long  widthClamp = (smoothEdges) ?  width : width  - 1;
  long heightClamp = (smoothEdges) ? height : height - 1;
  
  // [Optimization] Calculate bounds ahead of time
  unsigned int bounds = width * height;
  
  // Validate requirements
  if (!heightMap)
    return;
  
  // Allocate the result
  float* result = new float[bounds];
  
  // Make sure memory was allocated
  if (!result)
    return;
  
  for (z = (smoothEdges) ? 0 : 1; z < heightClamp; ++z)
  {
    for (x = (smoothEdges) ? 0 : 1; x < widthClamp; ++x)
    {
      // Sample a 3x3 filtering grid based on surrounding neighbors
      
      float value = 0.0f;
      float cellAverage = 1.0f;
      
      // Sample top row
      
      if (((x - 1) + (z - 1) * width) >= 0 &&
          ((x - 1) + (z - 1) * width) < bounds)
      {
        value += heightMap[(x - 1) + (z - 1) * width];
        ++cellAverage;
      }
      
      if (((x - 0) + (z - 1) * width) >= 0 &&
          ((x - 0) + (z - 1) * width) < bounds)
      {
        value += heightMap[(x    ) + (z - 1) * width];
        ++cellAverage;
      }
      
      if (((x + 1) + (z - 1) * width) >= 0 &&
          ((x + 1) + (z - 1) * width) < bounds)
      {
        value += heightMap[(x + 1) + (z - 1) * width];
        ++cellAverage;
      }
      
      // Sample middle row
      
      if (((x - 1) + (z - 0) * width) >= 0 &&
          ((x - 1) + (z - 0) * width) < bounds)
      {
        value += heightMap[(x - 1) + (z    ) * width];
        ++cellAverage;
      }
      
      // Sample center point (will always be in bounds)
      value += heightMap[x + z * width];
      
      if (((x + 1) + (z - 0) * width) >= 0 &&
          ((x + 1) + (z - 0) * width) < bounds)
      {
        value += heightMap[(x + 1) + (z    ) * width];
        ++cellAverage;
      }
      
      // Sample bottom row
      
      if (((x - 1) + (z + 1) * width) >= 0 &&
          ((x - 1) + (z + 1) * width) < bounds)
      {
        value += heightMap[(x - 1) + (z + 1) * width];
        ++cellAverage;
      }
      
      if (((x - 0) + (z + 1) * width) >= 0 &&
          ((x - 0) + (z + 1) * width) < bounds)
      {
        value += heightMap[(x    ) + (z + 1) * width];
        ++cellAverage;
      }
      
      if (((x + 1) + (z + 1) * width) >= 0 &&
          ((x + 1) + (z + 1) * width) < bounds)
      {
        value += heightMap[(x + 1) + (z + 1) * width];
        ++cellAverage;
      }
      
      // Store the result
      result[x + z * width] = value / cellAverage;
    }
  }
  
  // Release the old array
  delete [] heightMap;
  
  // Store the new one
  heightMap = result;
}

Screenshots

Unfiltered

Filtered

Conclusion

I would like to point out that box filtering is not the only solution to smooth sharp edges in terrain, and generally will not be a decent convolution filter to use in certain situations. For example; if you want to have sharp cliffs and canyons, box filtering will smooth your cliffs into a gentle slope. In this case, what you would want to add to your filtering operation is edge detection; also known as a “Smart Blur”, which smoothes noise patterns without adversely affecting sharpness or fine details in the height map. Using this filter method will smooth noise, but leave your cliffs and canyons recognizable as such.

The example provided with this article is simplistic, and even though the algorithm is fairly optimized, a couple optimizations were neglected to preserve readability. The out of bounds testing could be simplified further, and the loop conditionals could also be evaluated prior to processing.

The ability to specify whether or not to perform edge smoothing is dependent upon your implementation. Having the option to disable edge smoothing will allow terrain blocks to be tileable, as long as the height map was designed properly. With edge smoothing, and multiple blocks of terrain, cracks would appear between the blocks, and skirting would be required to remove them.

Terrain rendering is a popular and important topic for 3D graphics, and height mapping is just one method of visualizing terrain geometry. It is my intent with this article to help improve the quality of your terrain engine using box filtering as a simple, yet effective way of removing sharp edges.

Discuss this article in the forums

Date this article was posted to GameDev.net: 10/23/2004
(Note that this date does not necessarily correspond to the date the article was written)