Subdivision

The most popular method of terrain synthesis is recursive subdivision, commonly called "plasma" (although there are other methods also called plasma). There's lots of demo code for this on x2ftp.oulu.fi, and I've implemented a couple of examples of subdivision methods in Java. The idea behind this method is to take your starting shape, usually a rectangle, and place random heights at the corners. Then you calculate the heights at the midpoints of each of the sides and the center by linear interpolation and add or subtract a random value from that height. Then recursively (or in a loop) you calculate the next levels of detail, adding smaller random values each time, until the map is complete.

Remember to scale the random factors added to each point by a value which is proportional to the lengths of the sides (the variance over 10 squares is larger than the variance over 5 squares)

This method can be made extremely fast when your stepsize is 2 and the map dimensions are a multiple of 2 as well. Unfortunately, this is a very difficult fractal when it comes to zooming in on an area. Unless you can control your random numbers at every conceivable x,y point, the edges of zoomed areas will not usually match up. This may not be an issue for your application; YMMV.

One major variation is to make the subdivision tile-based rather than edge-based -- some methods are described in SIGGRAPH Proceedings. Basically you generate all new corners for your tiles, and the original corners become the centers of new tiles.

Advantages: can be VERY fast.

Drawbacks: can show distinctive aliasing effects along the grid lines, tends to look most realistic from low angles (rather than from overhead), and doesn't give you rivers or vegetation. Can also give you problems joining together multiple tiles created with this method, unless you can work out a way to get the same random seeds for the edges.

This fractal suffers from a number of artifacts, usually ugly, due to the fractal characteristics of this method. These artifacts tend to be most visible when looking down from above, or when looking across the map directly down grid lines or diagonals. There are a few techniques that are used to reduce these artifacts:

Adding random values to old points at each level

Every point at each level of the subdivision gets a random component, instead of just the newly generated points. This gets very expensive, so you sacrifice the good aspects of this method.

Diamond-square method

Instead of calculating 4 edge points and the center of each square (which can actually often be reduced to 2 edges and the center...), first calculate the centers of all the squares at that level of detail, then repeat the calculation using the new centers and the endpoints of each side (the diamonds) to calculate the midpoints of the sides.

Reference: Miller, Gavin S. P., "The Definition and Rendering of Terrain Maps", SIGGRAPH Conference Proceedings, 1986, p.39

Offset squares

Create new points by subdividing each square into four smaller squares. The new points are actually offset from the old points, halfway along the line between the corner and the center, instead of at the center and the midpoints of the sides. Each of the four new points is based on a weighted average of the four old points surrounding it, and each point receives a different weighted average. This average is good because the divide can be performed with a shift:

   point 1 = ( 9 * a + 3 * b + 3 * c + 1 * d ) / 16;
   point 2 = ( 3 * a + 9 * b + 1 * c + 3 * d ) / 16;
   point 3 = ( 3 * a + 1 * b + 9 * c + 3 * d ) / 16;
   point 4 = ( 1 * a + 3 * b + 3 * c + 9 * d ) / 16;

Notice that each point is weighted more heavily towards the old points nearest it. This produces a fairly good rounded landscape without any randomness added in (demo courtesy of James McNeill).

Use a hexagonal grid instead of squares

This is discussed by Mandelbrot in Peitgen and Saupe's "The Fractal Science of Images"; it removes the unbroken straight lines that cause the obvious artifacts.

Midpoint subdivision is used in a lot of "plasma" demos (e.g., the Mars Demo), sometimes with non-linear scaling of the resulting heights (e.g., squaring or cubing heights above sealevel to exaggerate mountains).

Patrick Hahn's 'Plasma fractals' page
Robert Krten's fractal terrain generator (July 94 DDJ)
Randy Cox's fractal landscape project page
XMountains - mid-point displacement at work
XMountains in Java!
Spatial subdivision - Paul Bourke's fractal landscapes page

Up to the terrain synthesis page

Back to my home page

This page hosted by Get your own Free Home Page

Subdivision

Related pages