Fractal Terrain Generator – Example 9.3

F303 Kopie

While not typically something used by landscape architects, many Computer Generated Landscape artists use procedural world generation software to create landscapes that have no basis in actual, real world landscapes, but can look astonishingly life-like. Employing the logic and algorithms of some of these “world creators” could be useful for landscape representation, and maybe even design, although I’d have to think a bit about a specific design application, since it is unlikely I will be getting a commission to design a new mountain range anytime in the near future, but if you have the $$, I’m up to the challenge!  Anyways, one of the most used of these world generators is a program called Terragen and of course, they use many different kinds of algorithms to achieve their results. One common algorithm for generating mountains, which is used by Terragen I believe, is a fractal process called the Midpoint Displacement algorithm. It’s pretty simple and if you know Grasshopper and Anemone well enough it shouldn’t be too hard to program. The results, depending on the settings, can generate mountainous landscapes that look astonishingly like the real thing. Of course, there are some major problems with it that I will describe later, but first I will explain the logic and the Grasshopper script, and then give a few concluding comments.

Step One – Initial Variation (Optional)

F03_SABefore running the algorithm itself, I setup a simple process in Grasshopper that allows you to manipulate the four corner points of a square up and down to create some initial terrain variability. The algorithm will still work with a flat square, but you may want to add this step. Here is an image of the script, which should be self-explanatory.

F03_Script01

Step Two – Diamond Square Algorithm – 1st Recursion

F03_SB

The image above shows the steps run by the loop for each recursion. First, the midpoint of the four sides of the modified rectangle are found and a line is drawn to connect the midpoints. The intersection point in the middle is identified, and will always have a “Z” value that is the average of the “Z” value for the four corners. This point is then moved up or down by a random amount, which is scalable using simple multiplication. If the scale factor is low, the end terrain will be rather flat, if it is high, the end terrain will be very rugged. In the image example, the point is moving up, but it could just as easily (depending on the random seed) be moving down. Lines are then redrawn between the midpoints to connect to this new point. One trick will be getting the rectangles to connect properly, so this will be like wiring a bomb. Be aware that each new side will be used in 2 of the four new rectangles. You will also need to create lines connecting the corner points with the midpoints. Each set of four lines is joined into a single polyline. I should now have 4 non-planar rectangles, where I had Just one before. The corner points of these rectangles are used to generate a patch surface. You could also try a mesh, such as a Delauney mesh, for slightly different results.

Next Steps – Diamond Square Algorithm – Further Recursions

F03_SCThe rectangles undergo the same process. But in the second recursion, we will have four rectangles, with four different random movements up and down. The third recursion will have 16… and so forth. You can see the roughness of the patch surface increasing after each recursion.

Further Steps

F03_SDAt some point you may want to bake the surface and use the original rectangle to trim the edges down since the parts of the patch surface outside of the points moved up and down aren’t useful. You can also draw contours on your surface in grasshopper.

Variations

F4_03PNow some time to show some variations. Here, instead of using a patch surface, I plugged the points into the Delauney mesh component, and then generated the contours. You can see, especially in the example on the right, that the grid comes through very strongly. This is one of the weaknesses of the “Midpoint Displacement Algorithm”, which can be modified slightly to create the “Diamond Square Algorithm” to get better results (at least according to Wikipedia 😉 )

Anyways, the variation here is simply changing the scale factor, or “roughness”. In the first example it is rather low (.10) and in the last it is quite high (.50)

F4_06p

Another thing you can do as in the three images above is vary the corners of the initial square. All these examples have the same random seed and roughness factor.

F4_09p

The last thing you can do, as with any algorithm that uses randomness, is change the seed. You can see the results can be quite different (all these examples have the same roughness and starting rectangle). It is usually the first recursion, and to some degree the second recursion that have the most effect on the final outcome. So controlling the results of the first recursion will allow you to get terrain that is more to your liking.

After about 5 recursions, the algorithm doesn’t do much new for your landscape except dramatically slow your computer down. So depending on what you need, 5 recursions seems to be a good limit.

Below is an image of the script I used. Most of the components are common except for the CCX (Intersection) component, which identifies a point where two lines intersect.

F03_Script02

So fractal terrain can have its uses, but to what degree is natural form actually dictated by fractal behavior? It is an interesting scientific and philosophical question. If you go down in scale even further, often a rock from a mountain will have roughness that approximates the roughness of a mountain range. Some people even describe landscapes in terms of their fractal geometry. (See this article on Fractal Geometry in Landscape Ecology). One glaring error with this algorithm, however, is that the midpoint displacement algorithm generates as many minima as maxima, in other words, as many valleys as peaks. in actual landscapes, minima are very rare. Part of the reason is because of the effects of water and erosion. When minima do occur, they fill with water and erosional sediment. Either they fill up to a point where they become essentially a flat plane, or the water spills over and begins to erode the walls of the basin. So this algorithm could actually be a good starting place, but other processes would need to be added to make a “realistic” landscape. But for its simplicity, and for what it does, it is pretty impressive.

Advertisements