Monday, January 28, 2008

Procedural modeling readings: terrain generation

Here are some papers on generating terrain. Please make your reactions comments on this post.

Howard Zhou, Jie Sun, Greg Turk, Jim Rehg. (2007). Terrain synthesis from digital elevation data. IEEE TVCG, 13, 4, 834-838.

F. Kenton Musgrave, Craig E. Kolb and Robert S. Mace. (1989). The Synthesis and Rendering of Eroded Fractal Terrains. Proc. ACM SIGGRAPH, 41-50. There are additional unrestricted versions online but they are lower in quality. Here's a useful intro to Perlin noise, ref'd in this paper.




Unknown said...

Terrain from Digital Elevation:
Maybe I'm missing something in this paper, but I fail to see much of a procedural element to it. I really saw two stages: the height map synthesis and the actual rendering. The synthesis part seems more a combination of fancy "edge detection" and standard texture synthesis and thus more of an application of existing techniques. The only new thing here is using tree traversal instead of a raster scan. Considering the types of images they are going for (canyons, rivers, mountains, and other natural scenes) it is a really good application because of their tendency to meander about. It makes sense to match the most significant parts of the terrain first, then fill in the rest. I think their synthesis works really well for the cases they show. I'd be curious how it would work on terrains or even non-natural settings that may not lend themselves as well to the height-as-indicator category.

The second part, rendering the terrain from the height map, I wish they had spent a little more time on. Here they put graphcuts and Poisson techniques to good use but they do not go into much depth on why they chose these versus other possibilities.

Stuart Heinrich said...

Firstly, I think that using an example-based system to generate terrain is an excellent idea. It overcomes the flaws traditional of existing models that are based on total random generation, which does not give enough control, and does not produce sufficiently random

looking terrain, and hand-drawn elevation models, which are too painstaking to produce. It allows realistic details such as erosion to be achieved, without the computational necessity of actually simulating the physical processes behind that erosion. And most

importantly, it allows any type of geological deformation to be used, instead of being limited to what the simulator knows how to simulate. All you have to do is find some examples of the type of deformation,

and it will use that. I think this method of terrain simulation is better than anything ever done before, and we will start to see it being used in a lot of games and graphics in the future.

They note that traditional edge detection will not work for detecting ridges and valleys in terrain heightmaps. This is pretty obvious. The PPA algorithm they are using seems to work well. I would expect it to produce slightly more feathered graphs due to operating at such

a small local level. From an image processing standpoint, another method that could have been used is to make a local thresholded image (ie, where the threshold is set based on the distribution of the local neighborhood), and then erode this binary image to the skeleton -- which should find all the ridges the same as PPA.

They explain that this problem is a bit different from traditional image synthesis, specifically due to the existence of the long curvilinear features -- which explains why they switch from a raster scan placement order to a graph traversal. This seems like a wise

move to me, and it certainly produces better results for them -- although they probably could have gotten better results in the raster scan order had they tailored their algorithm for it more. Not that it matters.

The thin-plane spline interpolation is not something I am familiar with, but after reading this paper, I plan to read up on it -- because it sounds powerful.I am a little bit fuzzy on how they used graph cuts to merge features. I wish they had explained this in more

detail. Also for the Poisson seam remover. Perhaps if I had a previous knowledge of what they meant by a "Poisson equation" it would be obvious, so this too seems like something worth reading up on.

The results are impressive, I want my own implementation in a software package!

Stuart Heinrich said...

Surprisingly, Ken Musgrove's algorithm for erosion (which is not very realistic) produces results that are better than any of the other modern erosion papers I have been able to find. This is a video of Musgrove's erosion model implemented by a guy named John Beale. Unfortunately the algorithm is not very well documented. I have the source code for this, but it's too messy to understand.

New_bird said...

The procedural texture with making noise is really visual compelling. Just as Perkin wrote “Noise [salt] is boring, F (blah) [food without salt] can be boring, F(noise, blah) can be really tasty” It reminds me of three other noise applications. First, eddy current is burdensome noise in most electrical system, so people find different ways to eliminate it. But eddy current sensor, which just use eddy current to measure distance and so on, is one of contactless sensors. Second, recent vision experiments about visual receptive field pay more attention to random dot, random bar and so on. These noises are independent, which is easy to be used to measure visual characteristics. Third, it is about prediction theory, where prediction means to remove noise and estimate useful signal. But if there is no noise, estimating signal will be not possible.

The result of paper 2 , “The synthesis and rendering of eroded fractal terrains”, is also very impressive for me, and it had been provided about 19 years. It satisfies two condition: 1/fm and controllable random. As we know, power spectrum of a natural image is always consistent with 1/fm on the whole, and based on fractal terrain modeling can easily satisfied the requirement. In the same time, we know one natural like picture must not be periodic. Thus, I think the two conditions must be some reason why the algorithm is so successful to model terrains.

Ryan said...

Terrain from Digital Elevation:
I agree with Alex, that this does look a lot like texture synthesis. The automatic cut, paste, and smooth operation seems to have a lot in common with the methods described in our papers for next class. I do like the idea of providing a much more controllable and tuneable system for generating realistic landscapes. The example with the map of Middle Earth shows how useful an artistic tool this method can be.

Terrain with erosion by Musgrave, et al. -

It's interesting to look at the early work in a field like this one. I found it interesting that a large part of the discussion was on techniques to speed up rendering the terrain in a raytracer, which today would probably not be included. Discussions of speeding up rendering are still very real and important, but would likely be an entire separate paper from this one. It seems like they struck a pretty good balance between accuracy/realism and speed with their erosion technique. I wonder if (and how) the terrain would change if the weather effects of mountains could be added in. Most decent size mountain ranges get a substantial difference in rainfall on opposite sides as the mountains block moist clouds, so some attempt at modeling this might make for an interesting twist.