Fractal Terrain Generation

The fractals need a generic form. The only function a fractal terrain generator must provide is one to evaluate the fractal to a given level expanded around a certain spot.

The generator presumably needs coarser-level evaluations before it can produce the finer-level ones. These grids of evaluated fractals can be stored in a separate class, so we have two classes here: the fractal evaluator itself, and a manager class that holds buffers of generated terrain at various levels. I will refer to these classes as FractalTerrain and FractalTerrainManager, respectively.

A given type of terrain fractal would have some parameters (at a minimum, a random number seed based on the planet's unique id number.) For a planet, you would create one FractalTerrain with the planet parameters, and one FractalTerrainManager.

The coordinate system

The FractalTerrainManager will hold the terrain data in its active, partially expanded form for the whole planet. We would like to be able to enforce a gross map on the planet (so we can make Earth). Also, the surface of the planet should be an actual sphere.

This can be accomplished by having several (many) square fractals drawn onto facets that are mapped to the surface of the sphere. We can do the mapping by circumscribing a cube into the sphere (so the corners just touch the sphere's surface), then dividing each face of the cube into a square grid and projecting the grid points radially out to the surface (see figure, below). I am partial to a square-grid coordinate system: triangular systems are too hard to deal with when going back and forth between different levels of resolution.

All of this stuff is the responsibility of the FractalTerrainManager. The output of the FractalTerrainManager will be a list of strips of triangles, which makes up the terrain that should be drawn given the player's current view.

This facet system has a side effect, which is that at six points on the sphere (corresponding to the corners of the cube) there are highly distorted squares. I expect that handling the cube edges and corners will be a bookkeeping pain.

I will use a Cartesian coordinate system of x, y. x and y are integers, and reflect the scale of the most detailed level of fractal expansion (i.e., x+1 is one finest-level square to the east of x). We also need a facet number, say 1 to 6. I will wrap the finer expansion into the x, y coordinate, so that each facet has smoothly varying internal coordinates. So, a global coordinate is described by (facet, x, y). I will arbitrarily say that looking down on each facet from above, +x is to the right and +y is up, and (0,0) is the lower left corner.

If there are N levels of potential fractal expansion below the non-fractal map level, then the non-fractal grid squares are space by 2^N.

In the figure, I show an 8x8 coarse grid in each of the six facets, and a further 8x8 grid in one of the coarse grid squares. This reflects a 3-level expansion of the terrain fractal.

The coarsest-level map

These top-level grid squares will be pregenerated, maybe by some sort of geologic model or, in the case of earth, by a user-defined map. They will include information as to at least the four corner altitudes and a fractal roughness parameter. If we have about 1000 of these squares, for the earth they will be 600 km on a side. This is good enough to enforce a rough map. This is illustrated in the figure.

When the user it a long way from the planet, the texture map enforced on the sphere will be based on this map. We need to smoothly insert an increasing patch of fractal expansion as the user approaches the surface.

Deciding where to expand fractals

The least sophisticated approach to this is to use the planetary texture- mapped sphere at a certain distance from the viewer, and within concentric smaller and smaller spheres perform more and more detailed expansions. This has two problems that I see: bad definition of mountain peaks, and long- distance shadows.

Mountain peaks are going to visible from quite a distance. The exact silhouette of the peak will be visible, and it will be pretty annoying if as you drive or fly toward it at a constant altitude, the peak keeps changing shape. So, high-altitude spots are deserving of more detailed expansion than low altitude patches.

Mountains and valleys both cast shadows, which are visible from quite a high altitude. This means that rough terrain needs relatively more expansion when the user is directly above it.

Here is the interface for the manager:


interface FractalTerrainManager {

   // make any necessary updates to the fractal based on the player reaching
   // position (r, theta, phi) relative to planet center.

   public void updateFractalExpansion( double r, double theta, double phi );

   // return triangle strips that are currently expanded and visible.
   //  returns the number of strips to draw,  returns
   // a pointer to the array of strips

   public void getTriangleStrips( int *nStrips, TriangleStrip **stripList );
};

Here is the interface for the fractal:


interface FractalTerrain {

   // evaluate the fractal into  from longitude  to  and 
   // latitude  to  on facet 

   public void evaluateFractal( int seed, int x1, int y1, int x2, int y2,
      int facet, int level, FractalTerrainManager myManager );
};

A simple example fractal:

a( x, y ) = x + LARGE_PRIME * y + OTHER_LARGE_PRIME * planet seed
z( x, y ) = z interpolated from higher level adjacent squares +
   random( -1, 1, seed from a(x,y) ) * roughness( coarsest-square( x, y ) )
   * scale-distance

here, random( a, b, c ) is a random number between a and b seeded from c

scale-distance is the side of a square at this level to some power greater than 1

roughness( coarsest-square( x, y ) ) is the roughness parameter from the square at the level above the fractal (I need a better terminology here.)

Home | Terrain Generaion