[size="5"]Introduction
Everyone seems to like generating and rendering terrain. I got lots of email about my old fractal program as well as the article I wrote a couple years ago. The fractal program used the Mandelbrot set to generate the height data, so it had pretty limited usefulness. The algorithm used in this article and program is much more flexible and can generate very realistic and usable terrain.
The code in this project is all from the final project in my CSCI580 class I took Fall 1999. The project was on generating ecosystems, but this article only deals with generating terrain. The executable for the entire project is linked at the bottom of this page.
[size="5"]Spectral Synthesis & Procedural Functions
The spectral synthesis algorithm is taken directly out of Darwyn Peachey's chapter in Texturing & Modeling: A Procedural Approach by Ebert, Musgrave, Peachey, Perlin, and Worley. It's an exceptionally good book, I highly recommend it to anyone interested in learning about procedural techniques. The detailed description begins on p82 and I also use the spline interpolation function on p31. If you can, read that chapter over as they probably explain it better than I do as I'm trying not to plagiarize too much.
Spectral Synthesis is a noise function - which means it doesn't fit any easily noticable pattern. Noise functions are extremely useful, almost anything in nature can be approximated by some combination of pattern and noise. The trick is knowing how to combine them. Consider how powerful a relatively simple function like is outlined here can be. High end & photorealistic renderers use many procedural functions for generating realistic textures and models. Pixar's Renderman rendering system is designed around taking advantage of the power of procedural functions. Besides being able to generate lots of varying patterns, procedural textures hardly require any storage space because they can be generated at run time (or on the fly) instead of being stored as a 24-bit texture on disk. Procedural textures have not been taken advantage of much in the game industry - except probably in generating textures in Adobe Photoshop, or another paint program. Now that video cards are more powerful, games can produce incredibly detailed scenes, and procedural textures and models are going to be a requirement to generate the massive amounts of data necessary for a highly detailed world.
[size="5"]The Algorithm
Well, I hope I've given you some appreciation for how cool this stuff is - let's take a look at the algorithm.
Spectral synthesis is just slightly more complicated than throwing a bunch of random numbers into a 2d array. The difference is in how the 2d array is treated. Instead of just treating the 2d array as the texture itself (aliased white noise), it smooths it (with a spline function in this case) to produce some sort of continuity in the data.
But that still wouldn't generate a very convincing or useful (except in some cases) texture. The real cool part comes in when you start adding multiple passes. In this way, spectral synthesis is a sort of fractal function. It iterates a function with varying parameters over an array that accumulates the values. The varying parameters in this case are wavelength and amplitude. Here's an example (forgive the low quality of the images, they're taken from the app, which wasn't made for looking at the 2d data).
I only used 4 passes for my project, but you can see how well it works at higher number of passes. Now you wouldn't get these results if you just kept accumulating smoothed random noise - the higher frequency data would determine too much of the texture. What you want is for the lowest frequency pass to define the basic shape and further higher frequency passes to add detail. So there is an added scale for each pass related to the pass number. The above images were generated with a scaling factor of 0.8 per pass, while I used 0.4 in my project.
The [font="Courier New"][color="#000080"]fracSynthPass(...)[/color][/font] function:
/*
* fracSynthPass(...)
*
* generate basic points
* interpolate along spline & scale
* add to existing hbuffer
*/
void fracSynthPass( float *hbuf, float freq, float zscale, int xres, int zres )
{
int i;
int x, z;
float *val;
int max;
float dfx, dfz;
float *zknots, *knots;
float xk, zk;
float *hlist;
float *buf;
// how many to generate (need 4 extra for smooth 2d spline interpolation)
max = freq + 2;
// delta x and z - pixels per spline segment
dfx = xres / (freq-1);
dfz = zres / (freq-1);
// the generated values - to be equally spread across buf
val = (float*)calloc( sizeof(float)*max*max, 1 );
// intermediately calculated spline knots (for 2d)
zknots = (float*)calloc( sizeof(float)*max, 1 );
// horizontal lines through knots
hlist = (float*)calloc( sizeof(float)*max*xres, 1 );
// local buffer - to be added to hbuf
buf = (float*)calloc( sizeof(float)*xres*zres, 1 );
// start at -dfx, -dfz - generate knots
for( z=0; z < max; z++ )
{
for( x=0;x < max;x++ )
{
val[z*max+x] = SRANDOM;
}
}
// interpolate horizontal lines through knots
for( i=0;i < max;i++ )
{
knots = &val[i*max];
xk = 0;
for( x=0;x < xres;x++ )
{
hlist[i*xres+x] = spline( xk/dfx, 4, knots );
xk += 1;
if( xk >= dfx )
{
xk -= dfx;
knots++;
}
}
}
// interpolate all vertical lines
for( x=0;x < xres;x++ )
{
zk = 0;
knots = zknots;
// build knot list
for( i=0;i < max;i++ )
{
knots = hlist[i*xres+x];
}
for( z=0;z < zres;z++ )
{
buf[z*xres+x] = spline( zk/dfz, 4, knots ) * zscale;
zk += 1;
if( zk >= dfz )
{
zk -= dfz;
knots++;
}
}
}
// update hbuf
for( z=0;z < zres;z++ )
for( x=0;x < xres;x++ )
hbuf[z*xres+x] += buf[z*xres+x];
free( val );
free( buf );
free( hlist );
free( zknots );
}[size="5"]Adding some water
What I used to add water is very simple. It interpolates a spline with 4 colinear nodes - two on two of the edges, and two outside of the area. It then offsets them by some random values to make the river a little interesting. As the spline is interpolated, the height field is displaced - like shoveling out the dirt to make a bed for the river. It also stores data in an buffer I call the water buffer. It uses this to determine if a point is underwater, and if it's not how much water is available for plants at the given point.
[size="5"]Conclusion
This is a more powerful way to generate terrain than my previous programs. But I also hope this article helped illustrate the power of procedural methods for generating textures and models. Remember, I barely touched on the broad capabilities of procedural methods. Play around with it.
[size="5"]Links
- Texturing and Modeling: A Procedural Approach at Amazon.com
- Texturing and Modeling: A Procedural Approach at fatbrain.com
- Ken Musgrave's Home Page - one of the authors of the above book. Has lots of examples of procedurally generated textures and models.
- Pixar's Home page
- Some renderman info @ pixar.com
