Terrain Generation with a Heightmap

  CU_Terrain.zip (713.8 KiB, 10,894 hits)

In this tutorial, we’ll learn how to generate terrain from a gray scale image known as a height map. We can use the color of each pixel in the height map to specify the height of the corresponding terrain vertex. A darker gray means lower terrain and a lighter gray means higher terrain. Each pixel is represented by a byte. Therefore, the height value of a vertex is represented by a byte in the height map.

A file format that has 1 byte per pixel is the RAW file format. A RAW file is just a linear array of bytes, no header junk, no extra information, just the data that we want to read. You can create your own height map in a paint program that exports to the RAW format or you can use a program that generates the file for you. I used Terragen to generate my RAW file.

RAW File and Terrain TextureHeight MapTerrain Texture

WireframeOnce we read in the height data, we can generate our vertex data. To generate the terrain, we will create a grid out of a single indexed triangle strip. If you read the texturing tutorial, you may remember me briefly mentioning a CTriangleStripPlane class I wrote to generate a grid with a customizable number of vertices. If we apply this to our terrain, we can make the grid have a vertex for each pixel in the height map. The only difference this time is that instead of a flat grid, each vertex has a y-value (height) that is determined from the value read in from the height map.

The grid will be built with a single triangle strip in a snake-like motion. We’ll render the bottom row of quads (2 triangles put together) from left to right. Then we’ll move to the next row up and render right to left. We keep going back and forth until the grid is complete.

When we move up to the next row, we can’t just go straight up from the last vertex in the previous row. Take a look at the diagram below. The figure on the right side of the diagram depicts the triangle strip from a side view. If we were to go straight up and our target vertex wasn’t perfectly in line with the last 2 vertices, an extra triangle would be rendered as shown by the orange line. To prevent this extra triangle, we have to use what are called degenerate triangles, or triangles with no volume. A triangle with no volume will not be rendered. To create the degenerate triangle, we simply repeat the last vertex of each row. However, since each adjacent triangle has the opposite winding, we need to repeat the vertex once more or else the triangle would be considered back-facing.

Triangle strip

The easiest way to texture terrain generated from a height map is to just stretch one texture across the surface of the grid. You can painstakingly create your own in a paint program or you can do what I did and have one generated by a terrain program like Terragen. If your texture is too small, the terrain will lose a lot of the texture detail. This is because there just isn’t enough pixel information in the texture to expand to when viewed close up. So the bigger and more detailed the texture, the better the terrain will look. The cost of this is more memory consumption. My texture is 1024×1024. Even at this size, the terrain is a bit pixelated when viewed close up.

To implement our terrain, we will create a terrain class called CTerrain. This class will encapsulate all the functionality and information needed to generate the terrain from a RAW file and a texture.

#include "stdafx.h"
#include "CWorldTransform.h"
#include "CTriangleStripPlane.h"
#include "CUtility.h"
#include "CVertexBuffer.h"
#include "CIndexBuffer.h"
#include "CustomVertex.h"

class CTerrain : public CWorldTransform
{
public:

    CTerrain();
    ~CTerrain() { Release(); }

    BOOL Initialize( LPDIRECT3DDEVICE9 pDevice, char* rawFile, char* terrainTexture );
    void Render( LPDIRECT3DDEVICE9 pDevice);
    void Release();

private:
    CVertexBuffer m_vb;
    CIndexBuffer m_ib;
    LPDIRECT3DTEXTURE9 m_pTexture;
    UCHAR* m_pHeight;
    UINT m_numVertices;
    UINT m_numIndices;
};

CTerrain is basically an encapsulation of a vertex buffer and an index buffer. The only methods are to create, render, and release the terrain.

#include "..\include\stdafx.h"
#include "..\include\CTerrain.h"

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
Summary: Default constructor.
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
CTerrain::CTerrain()
{
    m_pHeight = NULL;
    m_pTexture = NULL;
    m_numVertices = m_numIndices = 0;
}

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
Summary: Create a new Terrain object.
Parameters:
[in] pDevice - D3D Device
[in] rawFile - Name of the height map file
[in] terrainTexture - Texture file name
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
BOOL CTerrain::Initialize( LPDIRECT3DDEVICE9 pDevice, char *rawFile, char *terrainTexture )
{
    Release();
    
    // Load height map
    char path[MAX_PATH] = {0};
    CUtility::GetMediaFile( rawFile, path );
    std::ifstream heightStream;
    heightStream.open( path, std::ios::binary );
    if ( heightStream.fail() )
    {
        SHOWERROR( "Could not open height file.", __FILE__, __LINE__ );
        return FALSE;
    }

    // Get number of vertices
    heightStream.seekg( 0, std::ios::end );
    m_numVertices = heightStream.tellg();
    heightStream.seekg( 0, std::ios::beg );

    // Allocate memory and read the data
    m_pHeight = new UCHAR[m_numVertices];
    heightStream.read( (char *)m_pHeight, m_numVertices );
    heightStream.close();

    // Generate vertices
    UINT width = (int)sqrt( (float)m_numVertices );
    cuCustomVertex::PositionTextured* pVertices = NULL; 
    CTriangleStripPlane::GeneratePositionTexturedWithHeight( &pVertices, width, width, m_pHeight );
    m_vb.CreateBuffer( pDevice, m_numVertices, D3DFVF_XYZ | D3DFVF_TEX1, sizeof( cuCustomVertex::PositionTextured ) );
    m_vb.SetData( m_numVertices, pVertices, 0 );

    // Generate indices
    int* pIndices = NULL;
    m_numIndices = CTriangleStripPlane::GenerateIndices( &pIndices, width, width );
    m_ib.CreateBuffer( pDevice, m_numIndices, D3DFMT_INDEX32 );
    m_ib.SetData( m_numIndices, pIndices, 0 );
    m_vb.SetIndexBuffer( &m_ib );
    
    CUtility::GetMediaFile( terrainTexture, path ); 
    if ( FAILED( D3DXCreateTextureFromFile( pDevice, path, &m_pTexture ) ) )
    {
        SHOWERROR( "Unable to load terrain textures.", __FILE__, __LINE__ );
        return FALSE;

    }
    return TRUE;
}

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
Summary: Renders the terrain.
Parameters:
[in] pDevice - D3D Device
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
void CTerrain::Render( LPDIRECT3DDEVICE9 pDevice )
{
    pDevice->SetTransform( D3DTS_WORLD, GetTransform() );
    pDevice->SetTexture( 0, m_pTexture );
    m_vb.Render( pDevice, m_numIndices - 2, D3DPT_TRIANGLESTRIP );
}

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
Summary: Release resources
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
void CTerrain::Release()
{
    SAFE_DELETE_ARRAY( m_pHeight );
    SAFE_RELEASE( m_pTexture );
    m_vb.Release();
    m_ib.Release();
}

To create_ the terrain, we first read in the height data from the raw file. We can do this with the normal C++ file reading constructs. Since this isn’t a C++ tutorial, I won’t go over that part. After we read in the height data, we create_ the vertex and index data. Since this data is generated by the CTriangleStripPlane class, our Terrain class looks really simple. After we have all the vertex and index data, we shove them into their corresponding buffers.

Since the terrain is located in the CVertexBuffer and CIndexBuffer wrappers, rendering it is a snap. First we set the terrain transform and texture, then we call CVertexBuffer::Render(). A nice thing about the indexed triangled strips is that the number of primitives is always equal to the number of indices – 2.

#include "..\include\stdafx.h"
#include "..\include\CTriangleStripPlane.h"

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
Summary: Generates vertices with a position, normal, and texture coordinates to create an indexed 
triangle strip plane.
Parameters: 
[in/out] ppVertices - Pointer to an array to be filled up.
[in] verticesAlongWidth - Number of vertices along the width
[in] verticesAlongLength - Number of vertices along the length
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
void CTriangleStripPlane::GeneratePositionNormalTextured( cuCustomVertex::PositionNormalTextured** ppVertices,
        int verticesAlongWidth, int verticesAlongLength )
{
    SAFE_DELETE_ARRAY( *ppVertices );
    *ppVertices = new cuCustomVertex::PositionNormalTextured[verticesAlongLength * verticesAlongWidth];
    for ( int z = 0; z < verticesAlongLength; z++ )
    {
        for ( int x = 0; x < verticesAlongWidth; x++ )
        {
            float halfWidth = ((float)verticesAlongWidth - 1.0f) / 2.0f;
            float halfLength = ((float)verticesAlongLength - 1.0f) / 2.0f;
            (*ppVertices)[z * verticesAlongLength + x] = cuCustomVertex::PositionNormalTextured(
                (float)x - halfWidth, 0.0f, (float)z - halfLength,
                0.0f, 1.0f, 0.0f,
                (float)x / (verticesAlongWidth - 1), (float)z / (verticesAlongLength - 1)
            );
        }
    }
}

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
Summary: Generates vertices with a position, normal, and texture coordinates to create an indexed 
triangle strip plane.
Parameters: 
[in/out] ppVertices - Pointer to an array to be filled up.
[in] verticesAlongWidth - Number of vertices along the width
[in] verticesAlongLength - Number of vertices along the length
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
void CTriangleStripPlane::GeneratePositionTexturedWithHeight( cuCustomVertex::PositionTextured** ppVertices,
        int verticesAlongWidth, int verticesAlongLength, UCHAR* pHeight )
{
    SAFE_DELETE_ARRAY( *ppVertices );
    *ppVertices = new cuCustomVertex::PositionTextured[verticesAlongLength * verticesAlongWidth];
    for ( int z = 0; z < verticesAlongLength; z++ )
    {
        for ( int x = 0; x < verticesAlongWidth; x++ )
        {
            float halfWidth = ((float)verticesAlongWidth - 1.0f) / 2.0f;
            float halfLength = ((float)verticesAlongLength - 1.0f) / 2.0f;
            (*ppVertices)[z * verticesAlongLength + x] = cuCustomVertex::PositionTextured(
                (float)x - halfWidth, 
                (float)pHeight[z * verticesAlongLength + x], 
                (float)z - halfLength,
                (float)x / (verticesAlongWidth - 1), (float)z / (verticesAlongLength - 1)
            );
        }
    }
}

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
Summary: Generates 32-bit indices for an indexed triangle strip plane.
Parameters: 
[in/out] ppIndices - Array to be filled up.
[in] verticesAlongWidth - Number of vertices along the width
[in] verticesAlongLength - Number of vertices along the length
Returns: The number of indices
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
int CTriangleStripPlane::GenerateIndices( int** ppIndices, int verticesAlongWidth, int verticesAlongLength )
{
    int numIndices = (verticesAlongWidth * 2) * (verticesAlongLength - 1) + (verticesAlongLength - 2);

    SAFE_DELETE_ARRAY( *ppIndices );
    *ppIndices = new int[numIndices];

    int index = 0;
    for ( int z = 0; z < verticesAlongLength - 1; z++ )
    {
        // Even rows move left to right, odd rows move right to left.
        if ( z % 2 == 0 )
        {
            // Even row
            int x;
            for ( x = 0; x < verticesAlongWidth; x++ )
            {
                (*ppIndices)[index++] = x + (z * verticesAlongWidth);
                (*ppIndices)[index++] = x + (z * verticesAlongWidth) + verticesAlongWidth;
            }
            // Insert degenerate vertex if this isn't the last row
            if ( z != verticesAlongLength - 2)
            {
                (*ppIndices)[index++] = --x + (z * verticesAlongWidth);
            }
        } 
        else
        {
            // Odd row
            int x;
            for ( x = verticesAlongWidth - 1; x >= 0; x-- )
            {
                (*ppIndices)[index++] = x + (z * verticesAlongWidth);
                (*ppIndices)[index++] = x + (z * verticesAlongWidth) + verticesAlongWidth;
            }
            // Insert degenerate vertex if this isn't the last row
            if ( z != verticesAlongLength - 2)
            {
                (*ppIndices)[index++] = ++x + (z * verticesAlongWidth);
            }
        }
    } 
    return numIndices;
}

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
Summary: Generates 16-bit indices for an indexed triangle strip plane.
Parameters: 
[in/out] pIndices - Array to be filled up.
[in] verticesAlongWidth - Number of vertices along the width
[in] verticesAlongLength - Number of vertices along the length
Returns: The number of indices
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
int CTriangleStripPlane::GenerateIndices( USHORT** ppIndices, int verticesAlongWidth, int verticesAlongLength )
{
    int numIndices = (verticesAlongWidth * 2) * (verticesAlongLength - 1) + (verticesAlongLength - 2);

    SAFE_DELETE_ARRAY( *ppIndices );
    *ppIndices = new USHORT[numIndices];

    int index = 0;
    for ( int z = 0; z < verticesAlongLength - 1; z++ )
    {
        // Even rows move left to right, odd rows move right to left.
        if ( z % 2 == 0 )
        {
            // Even row
            int x;
            for ( x = 0; x < verticesAlongWidth; x++ )
            {
                (*ppIndices)[index++] = (USHORT)(x + (z * verticesAlongWidth));
                (*ppIndices)[index++] = (USHORT)(x + (z * verticesAlongWidth) + verticesAlongWidth);
            }
            // Insert degenerate vertex if this isn't the last row
            if ( z != verticesAlongLength - 2)
            {
                (*ppIndices)[index++] = (USHORT)(--x + (z * verticesAlongWidth));
            }
        } 
        else
        {
            // Odd row
            int x;
            for ( x = verticesAlongWidth - 1; x >= 0; x-- )
            {
                (*ppIndices)[index++] = (USHORT)(x + (z * verticesAlongWidth));
                (*ppIndices)[index++] = (USHORT)(x + (z * verticesAlongWidth) + verticesAlongWidth);
            }
            // Insert degenerate vertex if this isn't the last row
            if ( z != verticesAlongLength - 2)
            {
                (*ppIndices)[index++] = (USHORT)(++x + (z * verticesAlongWidth));
            }
        }
    } 
    return numIndices;
}

This is the CTriangleStripPlane class you’ve been reading about all this time. The algorithm is described at the start of this tutorial, but the best way to understand the algorithm is to work it out on paper. You can use the figure at the beginning for reference. Notice in GeneratePositionTexturedWithHeight, that we are setting the Y value of the vertex to the corresponding value of the height array. This is the height array that we filled up with the height map values.

Note: if all you see is the blue background and no terrain, your video card probably doesn’t support 32-bit index buffers, which is the implementation in this tutorial. If that is the case, you’ll have to create_ a 16-bit index buffer, however, the terrain in this tutorial needs 32-bits, so you’ll have to create_ more than one index buffer. Once you render out the terrain, you’ll have something like the following:

Terrain

6 thoughts on “Terrain Generation with a Heightmap”

rob May 27, 2011 at 11:52 am

Chad, This is awesome. You need to put this entire site into a book(s). If you do, please open up on the quality of the printed book. For example, the size and price should be like

http://www.amazon.com/Perspectives-Microsoft-Comprehensive-Thomson-Technology/dp/142390589X/ref=sr_1_1?ie=UTF8&qid=1306524522&sr=8-1

Even if it takes you two or more books to put this entire site into print, I would buy them.

HappySDE August 16, 2011 at 2:33 am

Nice post. After implementation of it I found this info about degenerative triangles (look at Index buffer section ):

http://msdn.microsoft.com/en-us/library/bb205133%28v=vs.85%29.aspx

An index buffer can stitch together multiple line or triangle strips by separating each with a strip-cut index. A strip-cut index allows multiple line or triangle strips to be drawn with a single draw call. A strip-cut index is simply the maximum possible value for the index (0xffff for a 16-bit index, 0xffffffff for a 32-bit index). The strip-cut index resets the winding order in indexed primitives and can be used to remove the need for degenerate triangles that may otherwise be required to maintain proper winding order in a triangle strip. The following illustration shows an example of a strip-cut index.

so this code become more simpler:

for(size_t z = 0; z < m_z-1; ++z)
{
for(size_t x = 0; x < m_x; ++x)
{
ret.push_back(WORD(x + m_x* z ));
ret.push_back(WORD(x + m_x*(z+1)));
}

//Degenerate strip:
ret.push_back(0xFFFF);
}

Jeremy Trifilo November 26, 2011 at 7:48 pm

I Would be very much interested in the executable for this. I’m very new to DirectX C++ and I would like to learn as much as possible. I have one main question can the camera move around in this? I haven’t actually read any code yet I do plan on doing so soon though and try to retyping the whole thing and testing out what each thing in the examples do.

But if you could also provide a download for the executable or tell me if the camera can be moved around while in this example because that 300+ fps seems really high and very interesting at the same time.

Lukás September 19, 2013 at 8:02 am

I have 700+ FPS. How can i calculate Proxy from that?

Comments are closed.

Leave A Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

<code> For inline code.
[sourcecode] For multiline code.