2.1 Random midpoint displacement method


Random midpoint displacement method introduced by Fouriner et al. [4] represents de facto standard in fractal terrains generation techniques. The principle is as follows.

An initial square is subdivided into four smaller squares (see Figure 2). Let us have four points tex2html_wrap_inline571 tex2html_wrap_inline573 tex2html_wrap_inline575 tex2html_wrap_inline577 . In the first step we add one vertex into the middle. The vertex is denoted by tex2html_wrap_inline579 , where


The added vertex is shifted in z-coordinate direction by random value denoted by tex2html_wrap_inline583 . This procedure is recursively repeated for each subsquare, then for every their descendants, and so on.

Figure 2: First four steps in random midpoint displacement method

In order to be resulting surface fBm, the random number tex2html_wrap_inline585 must be generated with Gaussian distribution tex2html_wrap_inline587 and in the i-th iteration step the variation  tex2html_wrap_inline591 have to be modified according to


where H denotes Hurst exponent [6] ( tex2html_wrap_inline595 ). From equation (1) we can see, that the first iteration has the biggest influence to the resulting shape of the surface and influence of the others decreases.

In the second step we calculate the points on the edges of initial square. We virtually rotate square by tex2html_wrap_inline597 and calculate the values as in the previous step. The problem is in the cases when the new point has just three neighbors (the encircled points in Figure 2). In this case we calculate the average of three neighbors only. The error produced on the border could be neglected.

In the next step we virtually rotate the square back by tex2html_wrap_inline597 and we recursively apply the first two steps on the four new squares as is mentioned above. This recursive process ends after given number of iteration.

Fractal dimension D of surface is obtained by


An example of fractal terrain obtained with random midpoint displacement algorithm is in Figure 3. The fractal dimension of this surface is D=2.5.

Figure: Example of fractal terrain with fractal dimension D=2.5. (a) wire frame model (b) the same model textured

Ivo Marak - marak@sgi.felk.cvut.cz