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:
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:
A simplified view of the regular terrain mesh is:
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:
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:
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.
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.
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.
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 );
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):
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:
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:
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:
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);
// Loop across and up
for (int z=0;z<numVertsZ;z++)
for (int x=0;x<numVertsX;x++)
// Create the verts
// Increment x across
// Increment Z
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:
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:
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:
for (int z=0;z<numCellsHigh;z++)
for (int x=0;x<numCellsWide;x++)
// first triangle
// second triangle
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.
- If you are interested in rendering terrain in real time with real time calculation of textures Greg Snook's book 'Real Time Terrain Generation ...' is very good. It must be good as it has a version of my T2 program on it :). You can find details on the Resources page and Greg has a web site here: Mighty Studios.
- Programs for generating terrain and textures include FreeWorld3D and the popular Terragen. For a list of others see these links here: 3D Links.
- For collisions with terrain see Terrain Following