Fractal-Wavelet terrain generation

This is a paper I wrote at Arizona State University for a graduate level computer graphics course (CSE 508). I intended to do something with it, but here I am 28 years after graduating, and I've done nothing :(. So I might as well put it out for anyone to use as they see fit. If you find it interesting, or make practical use of this material, I'd love to hear about it / see what you've done. Drop me a line at POstrowski@gmail.com!

---------------

In this paper I will derive a fractal terrain generation algorithm. Unlike most fractal terrain generators, the fractal I will derive and use will have wavelet properties. This will allow the terrain detail to be created only when needed, saving computing power and memory. The detail that is not yet created will be best approximated by the previous detail level.

First, we must decide what is means to be the best representation of a higher resolution terrain. The best representation must preserve some properties of the terrain such as

1. Overall shape.
2. Surface area.
3. Volume under the surface.
4. Surface gradients.
5. Altitude at key points.

The concept of preserving overall shape (1) would be nice, but is little too vague to pursue. In order to preserve the surface area (2) we cannot, by definition, use a fractal since each application of the fractal pattern will increase the surface area. Preserving the volume under the surface (3) would be nice, and appears possible to do, so I keep this property in the 'to preserve' list. Preserving the surface gradient (4) seems very important, and also seems plausible, so it remained in the 'to preserve' list. Preserving the Altitude at key points (5) sounds good at first, but may lead to a classic under-sampling problem. We also recall that in other wavelet approximations, the lower resolution approximation does not necessarily contain any of the same data values from the higher resolution version. I thus did not try to preserve this property.

To represent the terrain data, there are 2 immediately obvious possibilities. The first, and simplest, would be to create a grid and give the altitude at each of these points. A more complex representation would be to define a set of discrete landmark points in 3D, and define a connectivity map. This would lead to the possibility of cliff overhangs, and with extra work, even natural bridges, neither of which are possible with a regular square grid. It should also be obvious that the complexity of this type of representation might take more than one school semester to develop a wavelet for. I thus opted for using a grid. If we use a grid, then groups of three vertices form a plane, more specifically a triangle. These triangles are the smallest element of the terrain, and therefore are the target for the fractal-wavelet. I wanted the triangle to be of a shape such that it could be broken down into smaller similar triangles. It would also be nice if a single triangle could be broken down into just two similar triangles. I thus elected to use a symmetric right triangle as my base triangle:

   

	Base Triangle	First Subdivision into A and B

Since each element of the terrain is just a triangle, we should analyze what data a triangle may contain. The shape of the triangle is predefined and thus contains no information. The heights of the corners contain all the information. In this case, the information can be translated from 3 heights to 3 other unit of information in a different basis. In this case, we translate the information into: 1) the volume under the surface, 2) the x-gradient and 3) the y-gradient, exactly the properties I had on my ‘to preserve’ list. It can easily be shown that these three pieces of information uniquely define any triangle of the above defined type. Things are looking good. Now we can begin working on the fractal itself.

The fractal must introduce a new point midway along the hypotenuse of the triangle, while preserving the gradients and volume under the original triangles. We wish the surface to be C0, that is not have any ‘rips’ in it. Therefore, any change to a triangles side or hypotenuse, must also affect other triangle that shares the same side. Therefore, the fractal pattern will actually operate on pairs of triangles as such:

The height of the midpoint on the hypotenuse is the linear interpolant between two opposing corners. Here, I have arbitrarily chose to use corners 2 & 3. Corners 1 & 4 could have chosen equally well, as long as the convention is consistent throughout the algorithm. After the fractal is applied to this square, we know that the height of point 5 will increase or decrease by a pseudo-random value that we call dH. If this point goes up, the volume will also increase, but the overall gradients will not be affected. If the point goes down, the volume under the square will decrease. We know then that we must alter the heights of 1,2,3 and/or 4 such that the volume once again equals the original volume. If we adjust any single value, we will alter the overall gradient. Since we wish to preserve the gradient, we must adjust every point by an equal amount. To compute the amount by which we must adjust these points, we must know the total change in volume from the change at point 5. From geometry, we know that the volume change is equal to the volume of a pyramid with height dH, which is dH * Area of base/4. We will define the area of one square, the base, to be one. Thus: volume change = dH /4. We also need to know the change in volume as a result of changing the height of the surrounding points (points 6, 7, 10 & 11 below):

If we alter the height of point 6, 7, 10 and 11 we will affect the volume of the entire shaded area. Assuming that each point is altered by a value dH’, we compute the total change in volume to be 4*dH’. Since these two volumes must cancel each other out, we know that 4*dH’ =- dH /4. Thus dH’ = -dH/16.  

The resultant fractal then is the summation of the smaller pyramid plus the valley-like shape shown in the gray shaded area on the previous figure. The resultant fractal looks like this:

The peak of this fractal pattern is NOT dH, because the inner pyramid is sitting upon the plane that has been moved down by 1/16 dH (=dH’). The new point therefor has its height changed by 15/16 dH. Likewise, if any of the surrounding grid squares have already been fractalized, then their newly created points must be lower by 1/32 dH. Also, if the fractal pattern is applied to an edge square, then the volume displacement equation must be re-computed, since the fractal pattern cannot use all the surrounding squares to recoup the deviated volume. Alternately, the fractal pattern could be made to wrap around the grid to the opposite side. This is the simplest solution, and although some may have an esoteric objection to this practice, it is a practical and mathematically sound solution.

Well, now we have a nice fractal that has many properties of wavelets, with which we may create a random terrain. But a true wavelet can also be used to go from a high-resolution image/object to a lower resolution version. First then, let’s take a look at what happens to the resolution of the grid as the fractal pattern is applied. We begin with a 4 by 4 square grid. After we fractalize it one level, we have a grid that has an extra point at the center of each previous grid square. The dotted lines show the projected new grid lines. By tilting our reference frame 45°, we find that we are still left with a square grid. This square grid can then be fractalized just like the previous one, giving us an 8 by 8 grid, twice the original dimensions, with the same orientation:

In 1-D, we are altering two points at low res by a value N, and offsetting this adjustment by altering 1 a hi-res point by value -4N.

	Original 4 X 4	1st fractal level	2nd fractal level 8 X 8

If this is the forward fractalization-wavelet pattern, then the reverse fractalization-wavelet pattern must begin with the 8 X 8 grid and end with the 4 X 4 grid. In the forward transformation, a new point is generated by ‘stealing’ some of the volume from its surrounding neighbors in equal quantities. The reverse transform then is to re-distribute the extra volume to each of its neighbors in equal quantities, until the height of the point to be removed is the same as would be interpolated between its two controlling corners. We can visualize this easier in the 1-D linear case.  

Increasing the resolution in 1-D:

1-D wavelet:

From the diagram above, the red triangle under the X-axis (on the left side of the Y-axis) has a area of length*height/2 = 2.25*1/2 = 1.125. The area of the blue triangle above the X-axis (on the left side of the Y-axis) has an area of length*height/2 = .75*3/2 = 1.125. So its clear that applying this wavelet to any 1-D linear waveform will increase the resolution, but will not alter the volume of the waveform.

Decreasing the resolution in 1-D:

	High Resolution Image	Relocation Operations	Low Resolution Image

 

As we push the point that we are removing down, we pull the neighbor point up such that the area remains constant under the line. When the line connecting the neighbors passes over the removal point, we have the lower resolution image. The push and pull operations, shown as gray arrows above, are actually the very same fractal pattern we created earlier. To do this in 2-D, we merely need to raise four points as we lower the one point we are removing until the line connecting the two appropriate corners intersects the point of removal itself. When the fractal pattern is applied to increase the resolution of the image, the new point changes by a value of dH, relative to the connecting line (which also moved by -dH/16). If we reduce the image, the ratios between the change in the height of the removal point and the connecting line must move by similar proportions as in the increasing pattern. Therefore, the connecting line should move up 1/16 the distance between itself and the point of removal, while the point of removal lowers itself into the connecting line:

Decreasing the resolution in 2-D:

These ratios do not appear to maintain constant volume from the above diagram, however, keep in mind that I have drawn the 1-D case, using the 2-D ratios. Now that we have the complete fractal-wavelet, let’s find out what else we can do with it. First of we can decompose graphic images. Both a graphic image and the landscape information have the same format. one uses the data values to describe color and intensity information, the other uses the data values to define the altitude. If we use this fractal-wavelet to decompose a graphic image, we can treat any RGB image as three separate landscapes. The first ‘landscape’ would be the red component of the image. The second and third landscapes would correspond to the green and blue components. We could then tessellate the image into Gouraud-shaded triangles, decompose these into larger Gouraud-shaded triangles, and so on until we have only the four corner’s intensities for each the red, green and blue components of the image. If we can break up a complex dataset, such as an RGB data value into 3 discrete data and operate on them separately, it seems logical that we could break up any complex dataset, such as vector fields into x-component and y-component vectors, even z-component vectors.

For the initial purpose of this wavelet, that of terrain generator, a few complexities can be added so give more realistic terrain. First of all, to help imitate the effects of erosion, the allowable range for the deviation of the new point’s height should have a lower limit such that the new point will never go below the lowest height of its 4 neighbor points. This removes most of the local minimums. Local minimums in reality frequently form lakes, and there are few lakes that reside on the sides of mountains. Local minimums may still be created when surrounding areas are built up, but this is less likely to occur. This restriction should, of course, only be applied to terrain that is above the water level, should a water level be defined. Secondly, the terrain from one section of land to another varies in its roughness. The roughness should be included in the pseudo-random calculation of the height deviation dH. The rougher the terrain, the more variation allowable for the new points. I have noticed empirically that roughness does have a positive correlation to local altitude. For example, the tops of mountain (whose material is generally composed of harder rock) have many more abrupt changes in altitude (e.g., cliffs and fissures). The third complexity that should be added is applicable only when the generator is to be used for entire continent generation. A real-world continent is not fractal in nature, it does not have mountains that exceed 3 to 5 miles in height. As a result, the roughness (maximum height of deviation relative to hypotenuse length) should be limited by some type of non-linear function that gives very low deviation values for large triangles. The simplest implementation would be to set an upper limit to the magnitude of all deviations in terms of the scale of the generated landscape. Another complexity that can be incorporated is the floral distribution. The density and type of floral covering in an area can easily be used to create a realistic coloring scheme for the landscape. To go into detail about the placement and representation of flora in a landscape could easily cover another complete paper, but allow me say that it could be represented very nicely with these fractal-wavelets.

In conclusion, the fractal-wavelet has the following properties:

1. It preserves the local gradients.
2. It preserves the volume under the surface.
3. It can be used to increase or decrease resolution.
4. It can be recursively applied to infinity.
5. Each application doubles or halves the number of data points.
6. It can be extended into 3D, perhaps higher.
7. The wavelets have local support.

One very useful application of these fractals as terrain generators, would allow a user to enter a landscape at any resolution, perhaps a 16 X 16 grid, giving a rough approximation of a certain terrain. The program can then be used to flush-out the rest of the terrain, keeping any key point such as mountains and valleys intact. The wavelets can also be very useful for multi-resolution modeling of existing terrain. In my own biased opinion, I feel these wavelets are extremely powerful tool useful for many applications.