Terrain

Note: these notes were updated in March 2008 to correct some errors (mainly due to the z direction being shown incorrectly on the diagrams and hence making the calculations confusing).

Terrain can be modelled in a number of different ways, the method described here is to create a regular grid from cells. Each cell has two triangles and 4 shared vertices:

terrainCell1

As you can see from above each cell is made from 4 vertices. We divide this into two triangles. The first uses vertices 0,1 and 2 while the second uses vertices 0,2 and 3. Remember in Direct3D the vertices must be defined in clockwise order.

Each vertex will have position, normal and texture co-ordinates. We want the triangles to share the vertices and therefore share the normal. With correctly created normals this will create a nice Gouraud shaded terrain. More on normal creation in a minute.

Here is a picture of a textured terrain and then below it the bottom right section of the same view in wire frame mode showing the grid structure:

textured terrain

terrain mesh

A simplified view of the regular terrain mesh is:

terrain mesh

Creating the Mesh

We will need to decide in advance how many grid cells across and down we require. Obviously the more cells the greater the detail of the mesh but we end up using many more triangles and vertices. It is a trade off in quality versus performance.

To determine how many triangles we will need we will look at a very simple case of a 4 by 4 cell terrain mesh:

terrain grid

You can see we have 4 cells across and 4 up. Each row has 2 times the number of triangles as it has cells. We have number of cells + 1 vertices across. So the number of triangles is numCellsWide*2*numCellsHigh. The number of vertices is (numCellsWide+1)*(numCellsHigh+1). For the above example we therefore have 32 triangles and 25 vertices.

If we had a larger mesh say 32 by 32 cells we would have 2048 triangles and 1089 vertices so you can see how the amount of required data can grow.

Advanced note: for very large mesh you can split the mesh up and use different level of detail (LODs) depending on the distance from the camera. Stitching issues between different mesh with different LOD can be an issue. For a good discussion of these methods take a look at the book Real Time 3D terrain Engines by Greg Snook (details on the resources page).

To create the above mesh we will need to have two loops x and z. We will fill in the vertices first as before with vertex buffers and then calculate the triangles. The vertices creation is easy enough you simply increment x each time until the end of the row, then reset x and increment z and repeat until they are all done. Each time you fill in the vertices x and z values. The y value is set to a height, it would be 0 for a flat terrain, more on this later.

Triangle creation is more difficult. From the picture you can see that the first triangle will use vertices 0,5 and 6. The second triangle in a cell will use vertices 0,6 and 1. The picture below shows this for the first few rows of the above mesh:

cell_mesh

There is a detailed description of the required coding steps below : Terrain Creation In Detail

Vertex Heights (y value)

The heights of your vertex points determine the hilliness of your terrain. There are many ways to create these heights, the simplest being the use of a random number. A more advanced method is to use a heightmap. A heightmap is a bitmap where the colour values are grayscale values that represent the height at each point. So you could have a 4 pixel by 4 pixel bitmap with varying grey colours to use to assign heights to the above mesh. A white colour would be a maximum height and a black colour the lowest height. This method has historically been used in the creation of golf games, flight simulators etc. Other methods include procedural creation and methods involving simulating the effect of water on a surface; for information on more advanced techniques look on the internet.

Normals

If your mesh is not flat you have to create correct normals for each of the vertex (otherwise they are all 0,1,0 - pointing straight up). These normals will be used in the shading calculations to create a curved look to the terrain. To create these normals you have to take the average of all the triangle normals that connect to the vertex.

TerrainNormals_tris

So in the above image to calculate the normal for V4 you would need first to calculate the triangle normal of the connecting triangles (ones that share this vertex), there are 6 of them altogether: T0,T1,T2,T7,T6 and T5. We add up all these triangle normals and then divide by 6 to get the average normal which is then assigned to the vertex. The calculation of these normals can be done after creating your vertex and triangle indices. Note that if every triangle is the same size you do not actually have to divide by 6 but can simply normalise the result.

Advanced note: if your mesh were not a regular grid as described here, for best results you would need to weight the affect of each connecting triangles normal by the relative size of that triangle. See here.

Texture Co-ordinates

For any texture the UV co-ordinates are 0,0 for top left and 1,1 for bottom right. If you go beyond 1 it causes the texture to be repeated. For your terrain you could use just one texture and make the top left vertex have tu=0 and tv=0 and the bottom right vertex have tu=1 and tv=1. For vertices in-between you will need to assign a fractional amount. However it is probably better to tile the texture and make sure your texture has mip maps (or get them generated on load) and then set the filtering like this:

device->SetSamplerState( 0, D3DSAMP_MINFILTER, D3DTEXF_LINEAR );
device->SetSamplerState( 0, D3DSAMP_MAGFILTER, D3DTEXF_LINEAR );
device->SetSamplerState( 0, D3DSAMP_MIPFILTER, D3DTEXF_LINEAR );

Collisions

Collision with terrain is done quite differently to collisions between objects. Bounding boxes will not work in this case. We could cast a ray and carry out ray triangle collisions tests or if we just want to position things on the terrain we could find the height at a point. Since we are using a regular grid (above) finding the correct grid cell that a collision has occurred in is actually quite simple. We just use the position offset into the grid and divide by the cell size to determine the index of the correct cell. Once we have the cell we could calculate a rough height from the nearest vertex or use an average of the cell vertices but for complete accuracy we need to determine the triangle in the cell that is collided with and then calculate the height in that triangle. For details on how to do this please see the Terrain Following notes.

Terrain Creation In Detail

I have created terrain many times and I always have to use lots of paper to get it right - there are a lot of gotchas! The first issue is how do we specify our terrain. I normally do this by providing the number of cells I want across and down. We also need to define the size of our terrain so I specify minimum and maximum bounds (XZ plane only). So we will start with the following values (probably passed into the creation function as parameters):

D3DXVECTOR3 minBounds;
D3DXVECTOR3 maxBounds;
int numCellsWide;
int numCellsHigh;

At this stage I normally draw a small diagram for say a 4 by 4 cell terrain. This allows me to determine an algorithm for this test size that can then be applied to an arbitrary size. The diagram with some of the vertices shown:

cell_mesh

For the above diagram numCellsWide=4 and numCellsHigh=4. We can see that we will need 5 vertices wide by 5 vertices high, so the general formulae for the number of vertices is:

int numVertsX=numCellsWide+1;
int numVertsZ=numCellsHigh+1;

We will create the vertices first and then define the indices for each triangle. So we need a formulae for calculating each vertex position. We know we will have numVertsX*numVertsZ vertices in total so we use this value in creating our vertex buffer.

One big gotcha in creating the vertices is forgetting to take into account the Direct3D co-ordinate system. In Direct3D, for the above diagram, x is to the right and z is up the page (we are looking down on the diagram from directly above). So the vertex z value will increase as we go up the page (we start from the bottom).

The first vertex (v0) will therefore be at minBounds.x, 0, minBounds.z (I am just creating a flat terrain here so y will always be 0). The last vertex on the row (v4) will be at maxBounds.x, 0, minBounds.z. The last vertex of the whole terrain (top right) will be at maxBounds.x, 0, maxBounds.z. We can now work out the step value for both x and z values:

float stepX=(maxBounds.x-minBounds.x)/numCellsWide;
float stepZ=(maxBounds.z-minBounds.z)/numCellsHigh;

For our loop we will need to fill in each row. We set a start position and increment it with our step values as we loop. We need to keep track of the current vertex index so we add a count variable. Assuming a locked vertex array named vertices the whole loop is therefore:

// Set the start position
D3DXVECTOR3 pos(minBounds.x, 0, minBounds.z);

int count=0;
// Loop across and up
for (int z=0;z<numVertsZ;z++)
{
    pos.x=minBounds.x;
    for (int x=0;x<numVertsX;x++)
    {
        // Create the verts
        vertices[count].pos=pos;
        // Increment x across
        pos.x+=stepX;
        count++;
    }
    // Increment Z
    pos.z+=stepZ;
}

Right we have created our vertices, now we need to define the indices that make up each triangle. Taking another look at our example diagram we can see that the vertices for the first triangle will be V0,V5,V6 and for the second V0, V6, V1 (remember they must be defined clockwise for Direct3D or else they get culled and you see nothing!). We need to come up with a formulae for the general case. If the current vertex index is vIndex then:

indices[0]=vIndex;
indices[1]=vIndex+numVertsX;
indices[2]=vIndex+numVertsX+1;

We need to test this to make sure it is right. For our first case with vIndex as 0 we get 0, 0+5, 0+5+1 which gives the correct result of 0,5,6. We now need a formulae for the second triangle in the cell:

indices[3]=vIndex;
indices[4]=vIndex+numVertsX+1;
indices[5]=vIndex+1;

Calculating this gives 0,0+5+1,0+1 which gives the correct result of 0,6,1.

All that remains is to set up our loop to define all the triangle indices. A bit of care needs to be taken in specifying our loop limits. Since we are now looping per cell we need to go from 0 to numCellsWide. The full loop is therefore:

int count=0;
int vIndex=0;
for (int z=0;z<numCellsHigh;z++)
{
    for (int x=0;x<numCellsWide;x++)
    {
        // first triangle
        indices[count++]=vIndex;
        indices[count++]=vIndex+numVertsX;
        indices[count++]=vIndex+numVertsX+1;

                // second triangle
        indices[count++]=vIndex;
        indices[count++]=vIndex+numVertsX+1;
        indices[count++]=vIndex+1;

        vIndex++;
     }
     vIndex++;
}

For ease I increment the indices count within each assignment (count++). The vertex index is incremented twice at the finish of the x loop on purpose. If you look at the diagram again we do not want to calculate a triangle beginning with the last vertex (4) so we skip it and go straight on to the next row with vertex number 5.

We have finished! We now have a function that can create any density and size of terrain mesh we ask for. Further work will require altering the vertex y value (perhaps from a height map) and assigning texture co-ordinates.

Texture co-ordinates are quite easy to calculate. If you want the whole texture to cover the terrain simply set U and V values to 0,0 top left and 1,1 bottom right. For each vertex calculate how far across and down it is to get a value from 0 to 1. If you want to tile just increase the bottom right value e.g. 4,4 bottom right will cause the texture to tile 4 times across and 4 times down.