DETAILS
The algorithm used to generate fractal landscapes is a 3D extension of the 2D Random Midpoint Displacement (RMD) algorithm. The RMD algorithm is a random extension of midpoint displacement. The idea is as follows:
1. Take a line and find its midpoint.
2. Find the height of the midpoint.
3. Displace the height by a set amount.
4. Recurse on each of the lines created, reducing the displacement value by a set amount on each step.
5. Stop when desired resolution is reached.
The random extension of this is to select a random value, within a range that decreases on each step, for the displacement value.

There are a few ways to extend this RMD algorithm to three dimensions. One method that works on a square matrix is called the Diamond-Square algorithm, so named for its two steps. Here are the necessary steps:
Square Step:
1. Given four points in a square shape.
2. Find the centre (midpoint) point of the square.
3. Calculate this midpoints height value by averaging the heights of the four corners.
4. Displace the midpoint by a random value in the range (-sigma, sigma).
5. Proceed to Diamond Step, for each of the diamonds created by this step, with the same sigma value.		 Diamond Step:
1. Given four points in a diamond shape.
2. Find the midpoint of the square.
3. Calculate the height value of the midpoint by averaging the four corners.
4. Displace the midpoint by a random value in the range (-sigma, sigma).
5. Proceed to Square Step, for each of the diamonds created by this step, with a new sigma value.
sigma(new) = sigma * 2^roughness
This process can be terminated when the desired size of matrix is acquired.

Note: Due to the nature of the diamond-square algorithm, the matrix size needs to be of size 2^n + 1, where n is a positive integer.
- previous - back to main - next -
Hosted by www.Geocities.ws

1