Terrain Generation Tutorials, Part 2: Height Maps

Introduction

There are many ways to create terrain in games programming. One method is to use a pre-made height map containing the height data of a terrain over an area. This tutorial will cover how to use these heightmaps with the the grid we made in this tutorial. If you have not yet generated a grid of any size with any cell count, you will need that to complete this tutorial. I will also not provide any insight to the creation of the heightmaps, going off the assumption you know this/have heightmaps ready for use.

Theory

A heightmap is stored as a simple greyscale image where each pixel represents a height value between 0 and 255. For pixels that are completely black, the height is maximum. For pixels that are completely white, the height is minimum. These values are then projected onto a grid and used to represent the y values. Heightmaps will typically be stored in a .raw file format, but other file extensions could still be valid. We will assume a .raw file format for this tutorial.



Figure 1 - An example height map.

Code

Sampling the Heightmap

Firstly, we need a method that can extract the height map data from our image. For now, let's build a seperate namespace called HeightMapLoader with a function that can extract that data and return a vector of floats.

PseudoCode:
list<float> HeightMapLoader::LoadHeightMap(char* fileName, constant int width, constant int depth) { list<unsigned char> pixelData(width * depth); inputStream heightMapRaw; // Read entire Height Map raw data from file list<float> clampedHeightData(depth * width, 0); // For each element in the heightMap, clamp the values between 0 and 1 return clampedHeightData; }


It's worth noting that I intentionally clamp the pixel values down between 0 and 1 to help with scaling later down the line. For example, if I want my terrain to be taller, I can scale the y values by a factor of 10. This is a lot easier to predict and visualise when the values are between 0 and 1.

The next step is to alter the GridBuilder class we developed in the previous tutorial to handle a height map. We will do this by adding three new methods. BuildWithHeightMap(...) and ApplyHeightMapToVertices(...) will deal with the new heightmap loading. The third method, BuildGridGeometry(...) is simply a method to construct the returned Geometry data, added to avoid code duplication between Build(...) and BuildWithHeightMap(...).

Geometry* GridBuilder::BuildWithHeightMap(const Box gridSize, const XMFLOAT2 cellCount, char* heightMapFileName) const { std::vector<float> heightMapData = HeightMapLoader::LoadHeightMap(heightMapFileName, cellCount.x, cellCount.y); vector<Vertex> vertices = BuildVertexList(gridSize, cellCount); ApplyHeightMapToVertices(vertices, heightMapData); vector<unsigned long> indices = BuildIndexList(cellCount); return BuildGridGeometry(vertices, indices, gridSize); }

void GridBuilder::ApplyHeightMapToVertices(std::vector<Vertex>& vertices, std::vector<float>& heightMapData) { for (int i = 0; i < vertices.size(); ++i) { if (i > heightMapData.size() - 1) return; vertices.at(i).position.y = heightMapData[i]; } }


For now, I have cheated a little bit by simply returning out of the ApplyHeightMapToVertices(...) method if the array exceeds the heightMapData size. This is because, for a 10x10 grid, we will need 11x11 vertices. So when we request a 512x512 grid to match the height map size, we will have 513 x 513 vertices, causing an vector index out of bounds exception when we attempt to apply height map data that was never created. We will tackle this issue later in the tutorial.

I came across an issue when developing this code, where the grid started to break when the cell count was too large. This was to do with the lack of information that could be stored 2 bytes of data, as the index numbers would begin exceeding the maximum possible size. You may remember in the grid tutorial, we constructed the index buffer with a byte width of sizeof(WORD) * static_cast<UINT>(indexCount). This needs to be changed to a type that is larger than 2 bytes. In my case, I used LONG, which is 4 bytes. This also required changing the vector array of indices from vector<unsigned short> to vector<unsigned long>. Lastly, with this change, we need to tell DirectX that the input format has changed for the indices, which we do by setting the DXGI_FORMAT to DXGI_FORMAT_R32_UINT (Or equivalent 32 bit value) in IASetIndexBuffer(...).

ID3D11DeviceContext* deviceContext = _direct3D->GetDeviceContext(); deviceContext->IASetVertexBuffers(0, 1, &appearance->Model->VertexBuffer, &appearance->Model->VBStride, &appearance->Model->VBOffset); deviceContext->IASetIndexBuffer(appearance->Model->IndexBuffer, DXGI_FORMAT_R32_UINT, 0); deviceContext->IASetPrimitiveTopology(D3D11_PRIMITIVE_TOPOLOGY_TRIANGLELIST);


And now, to show the terrain with the heightmap applied [Figure 2].



Figure 2 - A height map applied to the scene

Unimpressed? Let's try scaling the height by 10... [Figure 3].



Figure 3 - A height map applied to the scene with adjusted y values.

Extra Work

Normal, Tangent and Binormal Considerations

If your application used any normal, tangent or binormal calculations for graphical techniques such as bump or parallax occlusion mapping, the terrain will break for these techniques [Figure 6]. This is due to all the normals pointing upwards [Figure 4], where they instead need to be pointing perpendicular to each polygon face [Figure 5].



Figure 4 - Height map slice with incorrect normals.



Figure 5 - Height map with corrected normals. Note that the red line represent the half way vector between the two normals that would be drawn at each vertex.




Figure 6 - An example of parallax occlusion mapping breaking on the height map terrain.



To remedy this, we need to calculate the tangents and binormals then recalculate the normals for each vertex. Code for this can be found at Rastertek, if you wish to consult his Bump Mapping tutorial for the code. Once sorting out the tangets, binormals and normals, parallax occlusion and bump mapping should work a lot better on the terrain.



Figure 7 - Terrain with the fixed binormals, tangent and normals.


Grid Map Interpolation

We previously discussed an issue where we have one more row and column of vertices than we do height map data. A potential fix to this would be to simply change that the cellCount represents the amount of vertices, rather than the amount of cells. This is particularly... unexciting. Let's do grid interpolation instead!

The concept behind this technique is quite a bit simpler that the implementation. It involves mapping the grid provided by the application onto the heightmap, then samples each nearby pixel on the heightmap with a weighting to each one depending on its distance [Figure 8]. These final pixel values are then interpolated to give the final height value for that vertex on the grid.



Figure 8 - Interpolation on the top row of a grid. Lower rows are more complex to calculate as more pixels need to be sampled across rows.



I'm sure the following code can be refactored and simplified somewhat, but here is the Interpolation code for each row. The column interpolation is very simular to this, only it operates on the pixels in a single row. I have excluded it to save space while also giving you something to think about.

PseudoCode:
list<float> InterpolateHeightMap(byRef list<float> pixelData, constant byRef float2 cellCount, constant byRef Box heightMapSize) { list<float> interpolatedHeightData; for (row = 0; row < cellCount.y; ++row) { set heightPosition to (heightMapSize.Height / (cellCount.y + 1)) * row; set rowOneIndex to round((heightMapSize.Height / (cellCount.y + 1)) * (row - 1)) * heightMapSize.Width; set rowTwoIndex to round((heightMapSize.Height / (cellCount.y + 1)) * row) * heightMapSize.Width; set rowThreeIndex to round((heightMapSize.Height / (cellCount.y + 1)) * (row + 1)) * heightMapSize.Width; set percentageShare to heightPosition - floor(heightPosition); if rowOneIndex >= 0 set rowOneWeighting to (1 - percentageShare); else set rowOneWeighting to 0; if rowThreeIndex < (heightMapSize.Height * heightMapSize.Width) set rowThreeWeight to percentageShare; else set rowThreeWeight to 0; list<float> rowOne; list<float> rowTwo; list<float> rowThree; set rowTwo to InterpolateHeightMapRow(pixelData, cellCount, heightMapSize, rowTwoIndex); // Code to check if any of the row indexes are equal. If they are, the data from another row can simply be copied opposed to recalculated for (column = 0; column < rowOne.size(); ++column) { if rowOneWeighting > 0 set rowOneWeight to rowOne.at(column) * rowOneWeighting; else set rowOneWeight to 0; if rowThreeWeighting > 0 set rowThreeWeight to rowThree.at(column) * rowThreeWeighting; else set rowThreeWeight to 0; append interpolatedHeightData with (rowOneWeight + rowTwo.at(column) + rowThreeWeight) / 2; } } return interpolatedHeightData; }




Figure 9 - 512x512 Heightmap interpolated onto 100x100 grid.




Figure 10 - 512x512 Heightmap interpolated onto 789x789 grid.



Comments