PDA

View Full Version : Random Terrain Generation



Jeff_Wilson63
09-19-2009, 09:36 PM
I've always had severe problems with fractal terrain generators. I've looked at a lot of maps, and the terrain they generate just don't look real to me.

Problem 1: Distribution

If you were to diagram the distribution of points in the standard fractal generator, you would likely find it follows a standard distribution curve. Unfortunately, terrain doesn't do that on Earth. While I don't know what it looks like in reality, it probably follows something like a concave curve coming to a point instead of the smooth convex curve of the standard distribution.

However, it occurs to me that you might be able to fake the proper distribution by applying a geometric function. Does anyone know how to "flatten" a grayscale image and then apply pixel^x function to it in a program like GIMP?

Problem 2: Fractal Lines

The fractal algorithms used for terrain aren't biased in terms of direction. Unfortunately, again, the real world doesn't work that way. The action of tectonic plates create fractal lines not radiating fractals. What fractal generator has ever created a structure like the Japanese islands?

Is there a fractal generator for producing marble veins or crumpled-paper-like patterns?

Problem 3: Erosion

Erosion makes hard edges smooth. It can also fill basins and cut canyons.

Is there some way to represent erosion on a fractal map?

Coyotemax
09-19-2009, 10:25 PM
#3 Sounds to me like you're asking about Wilbur :)

form what i've seen it does a Great job of handling that aspect. there's a few threads here that talk about it, and waldronate (one of the users here) is the programmer for it (and Fractal Terrains, if i recall).

the download and tutorial links are at http://www.ridgenet.net/~jslayton/software.html

waldronate
09-20-2009, 02:59 AM
1) The distribution on earth is very approximately exponential with an exponent above 1 for altitude values above the continental slope breakpoint and below one when below that. http://www.ridgenet.net/~jslayton/cshelf/index.html is something I did very long ago to demonstrate the idea.

I don't know the exact techniques to do exponential modifications in a typical paint program, but it should be fairly straightforward to implement such items using Python in GIMP or JavaScript in Photoshop.

2) The traditional way to achieve what you're after is to use different rules at different scales. In traditional Perlin-based noises, applying an absolute value to the first few octaves (largest scales) to get ridgelines and the using regular gaussian distributions after that will get a reasonable result. The best solution is to allow a human to specify the largest-scale features and then allow the randomization code to fill in the details.
Marble veins and crumpled paper are common noises in many libraries. POV-Ray, for example, has a 3D marble texture (I can't remember if it has a crumpled-paper-style or not as it's been quite a whlie since I played with it).

The biggest problem with simple fractal generators is that they tend to give mountain ranges that run down the centerlines of the land areas. Real mountains tend not to do that except for isolated volcanic islands.

You give the Japanese island chain as an example. It was formed by both tectonics and volcanism, two processes that aren't simulated in a typical terrain generator. However, a semi-plausible-at-first-glance version can be made by many generators that incorporate Musgrave's Ridged Multifractal generator. It gives long chains and swirling parts. If human intervention is allowed to specify some required parameters such as sea/altitude percentage and to pick an appropriate view of the noise function them I wouldn't be surprised to see results that are acceptable at first glance. More advanced generators should be able to do better.

There is usually a tradeoff between directability and quality. A typical noise-based generator doesn't give really much of any control over the output. Many newer works that give better user control are limited to their input training material (image synthesis algorithms such as the one from Howard Zhou are one example). There was a good paper at SIGGRAPH this year about multi-resolution image synthesis that looked like it might solve a lot of these problems, though.

3) Erosion is the toughest problem for terain generators today. Doing it on a generated grid is computationally expensive and the typical models used seem to fall prey to a scale problem. Most of the fluvial erosion models are good on the 1-meter-per-sample scale, but look progressively less convincing as scale increases, to the point where the small-scale model is generating rivers hundreds of miles across on larger terrains. It's the problem of assuming that one sample on the map is a specific size (e.g. 1 meter), while the map is really keeping a different scale (500 meters per sample). These systems also tend to have the "flaw" that the world needs to be pregenerated before being eroded.

Some of the the most visually convincing fractal generators provide the opportunity for the user to change rules at each scale (GeoControl is an example of this sort of generator). Erosion in that case is a rule that applies to scale levels. The erosion is usually implemented as a rule based on divergence and other parameters. In this sort of synthesis system rule can be tweaked at each level, but they can have the problem that there's not much for the user to do at the coarsest scales except pick rules and put in a few little spots.

I see that Wilbur has already been cited in this thread as an example of a system that can perform erosion. It's particularly amusing to me because while technically what Wilbur does might be considered erosion, it is probably one of the worst possible models. GeoTerSys has a more plausible erosion model, but the scaling issues described above is often visible in its output.

RobA
09-20-2009, 10:33 AM
However, it occurs to me that you might be able to fake the proper distribution by applying a geometric function. Does anyone know how to "flatten" a grayscale image and then apply pixel^x function to it in a program like GIMP?

The swiss army knife for Gimp is mathmap, which is available as a gimp plugin: http://www.complang.tuwien.ac.at/schani/mathmap/

It is the most user friendly way of mathematically manipulating pixels (http://www.complang.tuwien.ac.at/schani/mathmap/stills.html) in Gimp.

Here, for example, is a snip for applying an exponent function on a greyscale image/selection by adjusting a user slider (pow):


filter ident (image in, float pow: 0.2-4)
in(xy)^pow
end

-Rob A>

Redrobes
09-20-2009, 01:54 PM
It's particularly amusing to me because while technically what Wilbur does might be considered erosion, it is probably one of the worst possible models. GeoTerSys has a more plausible erosion model, but the scaling issues described above is often visible in its output.Thats quite amusing too cos I dont have anything special in GTS either. It does fluid flow not too bad. Its quite good at more viscous flow like glacier and lava where it gets more plastic but the erosion on the rock is based on the water flow over it and some simple gradient stuff. Its not all that great really. The best I have seen is from WorldMachine though I think GeoControl has some good stuff in it too. To be honest I don't think any of the apps does it really super well. Its a hard problem really. On the surface it seems simple but applying those simple algos does not give the expected nice results. So I think most of us are missing something cruicial. I am no geologist to know enough about the geo physics to model it mathematically.

GTS can do exponential height map modifications. When it does it, it applies it to both the rock and the water at the same time. You need that if you have a water map cos otherwise the water model is completely out compared to the rock.

But I wanted to post that I believe Image Magick can also do height map exponentials as you can do math functions on a per pixel basis and it can do them in 16bit tho I find IM unnaturally slow for large bitmaps.

Jeff_Wilson63
09-20-2009, 06:46 PM
I've downloaded MathMap, but don't know when I'll have a chance to play with it. For those who would like to play with textures here's an algorithm that you might try.


set st = !lowest pixel value to modify!
set fn = !highest pixel value to modify!
set md = !exponential modification!
for each pixel valued from st to fn
(
set v = !starting pixel value!
set !ending pixel value! = ((v-st)^md*((fn-st+1)/((fn-st+1)^md))) + st
)

Values of md below 1 will flatten lowlands, making lowlands flatter and highlands more spikey. Values of md above 1 will raise highlands, making highlands flatter and lowlands more crevasse-like. Note that the working equation preserves the range used, though it will leave gaps.

For erosion, two things occur to me. First the algorithms may not work when you're dealing with an area that isn't completely affected by water. Second, the 'weakness' of an area may need to be taken into a account. Block an outflow with salt and water will eventually it wear away no matter how steep the incline involved. Possibly this could be handled by generating a second texture for the relative strength of the terrain.

I will take a look at Wilbur.