Terrain Tutorial

Implementation Details

In this section we'll see how to implement the algorithm presented in the previous section. We'll see how to compute the line that divides the terrain, and how to compute the displacement for each iteration.

Finding a Line Which Divides the Terrain to displace the heights

The first problem is how to create a random line which divides the terrain. A first approach could be to find a line crossing the origin with a random inclination. However this approach creates a terrain which is anti-symmetrical, i.e. if we have a mountain in one place, we'll have a depression on the other side. Therefore, to avoid this trap the line should not cross the origin in the general case.

The line formula is

    
	ax + bz = c
	
	where  a*a + b*b = 1 and c >= 0

The formula above is know as the Normal Form. A simple way of obeying the restriction above is to consider

    
	a = sin(v)
	b = cos(v)
	
	where v is a random value.

Therefore a line, in its Normal Form, is an equation of two variables: v and c. So how do we compute the pair v,c so that the line actually divides the terrain?

Assuming that we're using the Normal Form, the distance from a point (x1,z1), to a line, ax+by-c=0, is defined by:

    
	dist = a*x1 + b*z1 - c

The distance will be negative for all points on one side of the line, zero for points in the line, and positive for points on the other side of the line.

Assuming that the terrain is centered on the origin the distance from the line to the origin, i.e. the point is (0,0), is defined solely by c.

    
	dist = a*0 + b*0 - c = -c

Therefore we only have to select a value for c which is smaller than the distance from the furthest point in the terrain to the origin. Assuming that the terrain has a width w, and a length l, then c should be defined in the interval [ -d/2, d/2 ], where d is defined as the square root of the sum of the squares of both w and l.

    
	d = sqrt(w*w + l*l)

The following code resumes what was explained above:

    
	v = rand();
	a = sin(v);
	b = cos(v);
	d = sqrt(w*w + l*l);
	// rand() / RAND_MAX gives a random number between 0 and 1.
	// therefore c will be a random number between -d/2 and d/2
	c = (rand() / RAND_MAX) * d - d/2;

Then, we iterate for each terrain point and displace its height, or y coordinate, by a certain amount. Points on one side of the line will have their height increased, whereas points on the other side will have their height decreased. The following pseudo code illustrates this iterative process

    
	for each point (tx,tz) in the terrain do {
		if (a*tx + b*tz - c > 0) 
			height(tx,tz) += displacement;
		else
			height(tx,tz) -= displacement;
	}

Another approach to find a line which divides the terrain, is when the line is constructed by selecting two random points from within the terrain. Assuming two points are given (x1,z1) and (x2,z2), the line equation is

    
	ax + bz + c = 0 
	
	where
	
		a = (z2 - z1)
		b = -(x2 - x1)
		c = - x1*(z2-z1) + z1*(x2-x1)

The height displacement for each terrain point is computed as before.

Yet another approach to this problem is proposed on the excellent book "Game Programming Gems". The two random terrain points, (x1,z1) and (x2,z2) are used to build a vector v1 where

    
	v1 = (x2-x1, z2-z1)

Then for each terrain point (tx,tz), another vector vt is computed where

    
	vt = (tx-x1,tz-z1)

Afterwards the y component of the cross product is computed and its signal will provide the direction of the displacement. The following pseudo code illustrates this approach.

    
	for each point (tx,tz) in the terrain do {
		if ((x2 - x1) * (tz - z1) - (z2 - z1) * (tx - x1)) > 0 
			height(tx,tz) += displacement;
		else
			height(tx,tz) -= displacement;
	}

The Displacement Factor

Another issue of this algorithm, is by how much we should displace the terrain heights at each iteration. The simplest solution is to consider the displacement a constant at every iteration. Another approach is to decrease the height displacement at each iteration without letting it reach zero. We could drop linearly the displacement factor from iteration 1 to iteration n, and then just keep it constant for iterations greater than n. For instance, to decrease the height displacement linearly as the number of iterations increases we could write in pseudo code:

    
	if ( i < n ) 
		dispi = disp0 + (iterationsDone / n) ( dispn - disp0) 
	else
		dispi = dispn
	where
	
		disp0 is the initial displacement
		dispi is the displacement for iteration i
		dispn is the displacement for iteration n

Special care must be taken when choosing the value n, as well as dispn. If dispn is much smaller than disp0 then the value of n should be sufficiently large, otherwise the displacement factor will decay too fast and the initial iterations will leave significant marks on the terrain. In this case if n is not large enough then the faults created by the first iterations will be visible regardeless of how many iterations we run.

[Previous: The Fault Algorithm] [Next: Simple Variations]