Terrain Following

When using terrain in our game we will want to be able to position objects acutely on top of it. To do this we will need a way of determining the height at a point. If we are moving an object over the terrain (like a car) we also need to be able to work out the slope so that we can rotate the car correctly.

Note: these notes are described in terms of a left handed co-ordinate system where x is to the right, y is up and z is inwards. This matches with the Direct3D system. It should be fairly easy however to adjust to another system.

Finding the correct triangle

Our first step in finding the height at a point over the terrain is to determine the correct triangle. How easy this is depends on how the terrain was created in the first place. If you have created a regular grid terrain as described in the terrain notes the process is much easier than if your terrain is an irregular mesh. The two methods are described below

Finding the correct triangle in a regular terrain grid

With a regular grid each cell contains two triangles. Each cell has a fixed width and height. To determine the cell the collision point is in can be calculated quite easily. Given a position vector p, a position vector terrainMin holding the start point of the terrain and cellWidth and cellHeight equalling the dimensions of each cell:

int cellX = (p.x - terrainMin.x) / cellWidth
int cellY = (p.z - terrainMin.z) / cellHeight

Note: as a first step you may wish to check if the point is actually over the terrain e.g. p.x>=terrainMin.x && p.x<=terrainMax.x etc

terrainCell2

Now that we have found the cell the point is over we just need to determine which of the two triangles the point is in (v0,v1,v2 or v0,v2,v3). If in our regular grid each cell is square (cellWidth is the same as cellHeight) then we can determine the correct triangle by working out if the dx value is greater than the dz value, see below:

terrainCellOffsets

In the case show above dx > dz so the point is in the second triangle (v0,v2,v3). If dz > dx then the point would be in the first triangle (v0,v1,v2). dx is calculated as the point's x value minus the cells minimum x: dx=p.x-v0.x and likewise with z: dz=p.z-v0.z.. If the cell is not square you may need to carry out a point in triangle test as described below.

Now that the correct triangle has been determined the final step is to find the height of the point in that triangle.

Finding the correct triangle in an irregular terrain grid

If you have a terrain that is not a regular grid it becomes more difficult and more time consuming to find the correct triangle. In effect you have a triangle soup with no simple organisation to it. The task of determining if a point is within a particular triangle is one that is well researched and there are a number of methods available. I describe one method here: point in polygon. A brute force method would be to go through every triangle in our triangle soup doing this test until we came to the correct one. This would be really slow however and so we really need to organise our triangle soup somehow.

There are various methods of organising the triangle soup this (space partitioning) but a simple and quite effective method is to just collect triangles in buckets. To do this we create a regular grid of cells. Each cell will have a world minimum and maximum x and z value and contain a list of triangles. At start up we go through our terrain and allocate each triangle to one or more of these cells. It is 'one or more' because triangles will quite often overlap cell edges and in that case they should belong in both cells. When carrying out our collisions test we can now look up, in a similar way to using a regular grid, the correct cell. We can then loop through each triangle in the cell doing a point in polygon test until we find the correct triangle.

This method reduces the task significantly. Some tweaking will be needed to find the best size of each cell. You want each cell to contain a reasonable number of triangles. You do not want only a few triangles per cell or you may end up with a large overhead of cells and triangles in many different ones but on the other hand you do not want too many triangles per cell as the number of point in polygon tests will slow down your code. A balance between the two needs to be found.

Advanced Note: often when determining the height of a point over the terrain you will be using the same x and z value e.g. if the player has not moved since the last test. In this case you should only carry out the test if the position has actually changed. You may also find that tests commonly use the same values and in this case you could cache previous results for quick recall.

Height of a point in a triangle

Once you have found the correct triangle the next step is to determine the height of the point within that triangle.

triangle

To find the height in this triangle involves an equation derived from the fact that the dot product of a vector formed between two points on a plane with the plane normal will result in a value of 0. In other words and in terms of our diagram this can be written:

0 = N.(P-V0)

Where N is the triangle normal, P is the point and V0 is a vertex of the triangle. The calculation P-V0 results in a vector lying on the plane of the triangle.

We can expand and rearrange this formulae to get a formulae that will return the height of the point (y value) in terms of the other values. Firstly we expand out the formulae:

0 = N.x(P.x-V0.x) + N.y(P.y-V0.y) + N.z(P.z-V0.z)

The next step is to move the y calculation to the left hand side by moving the y term above and then dividing by N.y

P.y-V0.y = (N.x(P.x-V0.x) + N.y(P.z-V0.z)) / -N.y

Then we can rearrange to get the left hand side as just y like so:

P.y = (N.x(P.x-V0.x) + N.z(P.z-V0.z))/-N.y + V0.y

In terms of our triangle shown above dx can be calculated as p.x-v0.x and dz as p.z-v0.z and so the equation becomes:

P.y = V0.y+ (N.x * dx + N.z * dz ) / -N.y

This makes sense if you read it as: "the point's y value is calculated as how far it is in the x direction multiplied by the x normal added to how far it is in the z direction multiplied by the z normal reduced by the y normal value and added to the start height." Or perhaps not :)

When carrying out our test we will have access to all the values on the right hand side and can therefore calculate the height at the point P. If you have not stored the triangle normal you can calculate it each time, at the loss of some speed, like so:

N = (V1-V0) cross (V2-V0)

In other words the cross product of two vectors formed from two sides of the triangle.

Orientating an object on the terrain

The above described how to find the height at a point over the terrain and this will be all we need to do when positioning small objects however with larger object we would like to make them rotate to match the slope of the terrain under them.

If we take the case of a car it has four wheels that are normally in contact with the ground:

car1

We could determine the height of the terrain under each wheel and try to rotate our car so that each wheel is on the ground (by calculating pitch and roll) but an easier and more common approach is to use three points at the front of the car and one at the back.

car2

We can use our height at a point calculation to determine the height of the terrain for each of these points and hence calculate the pitch and roll:

car3

car4

The actual calculations just require a bit of simple maths e.g. to determine pitch if we have a height value for the front called frontHeight and the back called backHeight we can use the fact that the car is always straight (does not bend) to form a right handed triangle like so:

carAngle

We need to determine the angle of rotation so using our SOHCAHTOA rule

sin(angle) = opposite / hypotenuse

The opposite is the difference between height at the front and the height at the back and the hypotenuse is the distance between the front and back points of the car. A similar calculation can be done to determine the roll value.

Of course if the slope is very steep this method may cause some problems where the car appears to cut through the terrain. It can be quite difficult to prevent this in all cases but normally, with care taken in the creation of the terrain, the above works fine. The only solution to very steep terrain would be to allow the wheels to leave the surface of the terrain but then you are going to have to work out gravity etc. when moving the car and returning the wheels to the ground but there are still problem situations:

car5