Tuesday, 2 July 2013

The heightmap: from concept to template

If you want to render a terrain, a heightmap is a handy tool to have at your disposal.  This post explores one way to create an abstraction of this concept using the new C++ standard.    
In its essence, a heightmap is simply a matrix of numbers where an element at {c,r} indicates the height of the terrain at some location.  It is a handy data structure and is also a compact way to store the details of a terrain.   The image on the right hand side is an example of a heightmap shown as a 2D image (taken from Wikipedia). The height is determined by the value of the white colour: a whiter pixel indicates a higher level for the terrain at that point.  You should be able to imagine where the hills and valleys are by looking at this image long enough.
As you can expect, compact storage comes with a cost: less data equals less detail.  The granularity of the terrain is determined by the size of the matrix, and also by the size of the data type used for its elements.  For instance if the elements are stored as a bytes the terrain height ranges from 0 to 255.  The height cannot be 23.5 … there is only 256 levels to choose from. 
Getting back to the abstraction: It seems reasonable that a heightmap needs at least three parameters.  These are: (a) the number of columns m, (b) the number of rows n and (c) the data type of the elements, elemT.   We should now be able to implement this abstract concept as a  C++ class template
First, we need is to choose a data structure for the matrix data.  We want a structure that is fixed in memory and stores consecutive elements in sequence.  This constraint will make the heightmap very useful for rendering in OpenGL.   The std::array container is well suited for this purpose. 
Often we want to address the elements in the array using the {c,r} pair as index.  For this reason, I provided an overloaded () operator that can throw std::out_of_range. The code for our class template Heightmap, is shown in Listing 1. 
Listing 1:

Fine and well you say, the meaning is clear, but what is the use of it all?  Ok, let’s develop a more concrete concept that actually does do something.  How about loading the heightmap from an image file, and writing it back? 
Consider the image shown above.  Using my favourite image editor paint.net, I converted this image to an 24-bit BMP file and resized it to be 50 x 50 pixels.  I want a BMP file because this is a file format SDL handles very nicely; the size is an arbitrary choice. 
The fact is, the handy SDL library provides all the heavy lifting we need.  The SDL_LoadBMP function creates an SDL_Surface which contains the pixel data in row order.  The pixel data depends on the pixel format declared in the BMP file.  The 24 bits means the data contains 3 bytes per pixel.  Note that the 3 bytes represents an RGB value where R = G = B. Here 0 is black and 255 is white. Clearly, the R, G and B values are not all needed in the matrix: one byte is enough. 
Let’s call our new abstraction HeightmapWithByte: it is a Heightmap with elemT = unsigned char.   The code for this abstraction is shown in Listing 2.   The read and write members of this new class template allows us to  swap heightmap data from and to a BMP file. 
Listing 2:

The code for the functions invoked on line 5 and line 11 are shown below in Listing 3.   Both functions assume the the 24-bit per pixel format.  Line 2 refers to a simple wrapper class in GameEx (a Github repo of mine)  that manages the SDL_Surface.  The pitch of an SDL surface is a notable concept.  It is the number of bytes in a render line. It is the next number after the image width that is divisible by 4.   For example if you have 50 pixels per row, the SDL surface has a pitch is 52.  The consequence is that each row has 2 padding bytes appended in the pixel data of the surface.  So, be extra careful if your fingers itch to unroll that for-loop ;-).        
Listing 3:

Let's put it all together is a small example program. The snippet in Listing 4 reads the input bitmap, inverts the heights so that the highs are low and lows are high. Then it writes the heightmap to an output BMP file. The image on the right hand side is an enlargement of the output produced by this snippet.  If you compare with the original you’d notice the pixilation effect brought about by the radical transformation of the original input (described above).
Listing 4:

By the way, that for_each call in the snippet is a very handy macro defined in GameEx.  It works very well with all standard containers, including the new std::array
There you have it: a few lines of C++ to chew on.  Have fun!
After thoughts:
There is follow-on post about terrain rendering you can read.

No comments:

Post a Comment