• 10/23/04 08:03 PM
    Sign in to follow this  

    Box Filtering Height Maps for Smooth Rolling Hills

    General and Gameplay Programming

    Myopic Rhino

    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.



      Report Article
    Sign in to follow this  


    User Feedback

    Create an account or sign in to leave a review

    You need to be a member in order to leave a review

    Create an account

    Sign up for a new account in our community. It's easy!

    Register a new account

    Sign in

    Already have an account? Sign in here.

    Sign In Now

    There are no reviews to display.