For a long time I've been fascinated with algorithmically producing fractal landscapes.  The main application of this that interests me is creating fantasy worlds for gaming (video, pencil and paper, etc.).  This is a tricky problem, but I realized recently that random landscaps won't really work when you already have some preconcieved notions of what the world should look like.  Then I set out to create an interactive landscape editor.

The basic functions of such a program are pretty easy.  Create a flat 2-d projection of a 3-d grid,  preferably using triangles, and represent the Z axis (height) with color.  Then provide tools to raise and lower the landscape, add roughness, maybe channels from water, etc.  If you know the height at each grid point, the problem then becomes how do you find out the height between grid points?

This is necesarry for several features.  First, we want to make pretty pictures, and we need to know the height of the terrain at any given point in order to color it in.  This could be done with a number of methods such as open-GL 3d surface projection and coloring.  The problem with using a 3d system for that is that we won't achieve quite the same control over mapping heights to a color map.  If we know the actual height values at every point, we can make up cool custom gradients very easily.

Second, I want to be able to create higher resolution maps out of lower resolution ones.  There are two approaches to this, you can either subdivide the existing grid while maintaining the form, i.e. subdivide each triangle into a number of triangles in the same pattern and with the same angles, or throw out the existing grid and make up a new, finer grid using the heights on the old map wherever the new points happen to fall.  This latter option is much easier (and may be the only method), but doesn't preserve the "key points" on the map, which at times will create a nice softening effect.  For either of these options we have to be able to interpolate for any given point by hand.  Any other method, such as using a 3D rendering system, would require that the 3D system generates a fine-grain Z-buffer that we could examine.  And even then, we wouldn't get points where we wanted them, only the nearest pixel.

The math for this is actually pretty easy, but non-obvious to me.  I got to have a fun math lesson with my father who explained the concept of basis functions.  In the terrain we're creating, we have a series of triangles, each with a flat surface.  If we have enough flat triangles the world will look smooth, so that's enough for now.  But finding out the slope of each triangle is a little tricky, unless you know you'll be working with a specific type of regular grid.

I decided to use a grid of equalateral triangles, 60 degrees on a side, with a side length of 1 unit.  This means that they arrange nicely into hexagons if you grab all six triangles around any given point, and produce an easy to compute, but very nice looking grid.  The math was pretty straight forward at that point, we drew out a hexagon of triangles, made the center point (0,0), found the position of the other points, and came up with a slope function for each triangle that made the Z value zero around the perimiter and one in the middle, creating a little mountain.

This is a cool system, because if you know those six formulas you can produce any landscape.  The trick is finding the slope function for any arbitrary triangle knowing those six slopes, which it turns out is as simple as adding.  I'm not going to draw any pictures for this right now, but it's not too hard to visualize.  If you shift the values so that each point around the triangle becomes (0,0) in turn, you will wind up with three of the six triangles around the initial hexagon, one for each point.  Each slope will make one point around your triangle height one, and the other two points zero.  Then all you do is scale each slope function by the height at the point that makes it 1, and add them together.

Ok, that's a bit compressed, but in my case there are only two different triangles to compute slope functions for.  Assuming that we have the following values:

j = cos( 60 )

k = sin( 60 )

l = j / k

m = 1 / k

We can define all of the slope functions and all of the triangles.  The grid rows vertically are k apart (.86), and points are 1 apart horizontally on each row.  The rows appear to be shifted by j (.5) to the right for every odd numbered row.  I'll list my triangles quickly by verticies, counter clockwise starting with the origin:

1. (0,0), (1, 0), (j, -k)
2. (0,0), (j, -k), (-j, -k)
3. (0,0), (-j, -k), (-1,0)
4. (0,0), (-1,0), (-j, k)
5. (0,0), (-j, k), (j, k)
6. (0,0), (j, k), (1, 0)

If you wind up drawing these out you'll notice that triangles 1, 3, and 5 are the same orientation, and that 2, 4, and 6 are another.  That means that half our triangles will combine the slopes of 1, 3, and 5, and the others will use 2, 4, and 6.  No problem, but we also have to adjust for each arbitrary triangle that we come accross not actually having it's points at (0,0).  If we number the verticies around our triangle from 0, 1, 2, 0 being slope 1, 2 being slope 3, and 3 being slope 5 we wind up with the following equation (x,y,z are the point we're computing for, xn, yn, zn are the x, y, and z values for a given vertex n):

z = z0 * (-x + x0 + l * (y - y0) + 1) + z1 * (x - x1 + l * (y - y1) + 1) + z2 * (-m * (y - y2) + 1)

That's not so bad.  I should probably have pictures, but all the ones I have are in a sketchbook.  Anyway, they won't all be this mathey :)