Jump to content

  • Log In with Google      Sign In   
  • Create Account


Like
0Likes
Dislike

Box Filtering Height Maps for Smooth Rolling Hills

By Graham Wihlidal | Published Oct 23 2004 02:03 PM in Game Programming

If you find this article contains errors or problems rendering it unreadable (missing images or files, mangled code, improper text formatting, etc) please contact the editor so corrections can be made. Thank you for helping us improve this resource



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

height="379" alt="" border="0">
Unfiltered


"379" alt="" border="0">
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.








Comments

Note: Please offer only positive, constructive comments - we are looking to promote a positive atmosphere where collaboration is valued above all else.




PARTNERS