Generating Parametric Terrain

I would go for something like this:
1-First use standard algoritems (perlin-noise, hills, fault-lines,...) to get general shape of terrain.
2- Convert this to parametric surface
3- Use algoritems simmilar to metaballs to add or remove terrain. This could be used to both create caves and add overhangs. The hard part here is to decide where to add or remove, to create natural looking shapes. Perlin noise will probably be very usefull here again.
4- Then, as last part, use noise to add local detail. This part will probably be just before you render a patch, not even stored with data.

You might as well add some erosion simulation in there. A global one before 1 and 2 and small local scale one between 3 and 4.
Point 1 is same as standerd hightmap approach, so you can find tons of info about it.

I'd just use vector-valued function(for example,3 perlin noises)
to generate surface. I mean something like

Vec3 surfacefunc(Vec3 p){
return somematrix*VectorNoise(p)+othermatrix*p;
}
Vec3 surface[1024*1024];
for(y=0;y<1024;y++){
for(x=0;x<1024;x++){
Surface[x+y*1024]=surfacefunc(Vec3(x,y,0));
}
}

so by cnanging matrices i can make it to produce heightfield terrain, or terrain with overhangs, or something else.

Also this code generates from plane. It's possible to generate from different topological things such as sphere, toroid, toroid with N holes,etc.....

[Edited by - Dmytry on October 11, 2004 3:28:52 PM]

if you want it realistic, then it's way harder than just noises.
i've been at geological faculty for 6 months working on similliar project.
it's almost impossible IMHO.

Well, totally realistic is hard . But even simple things, like perlin noise (i mean multioctave perlin) is pretty realistic.
Realistic enough for current rendering methods.
And of course there i posted simplest example. Of course surfacefunc can be(and in any real-world project will be) alot more complicated.

BTW, Voxel World is 100% procedural(zero artwork(i only choose colors)).
My clouds is also 100% procedural.

And noise based generation is only a start. It can be continued by different erosion simulations and other post-processing. All this can create landscapes that average Joe can't tell from reality (the rendering after that is another thing).

Three years ago I wrote an engine that could generate and render at interactive FPS a quasi infinite terrain with 1cm details (shaded). There was a very intricated correlation between a CLOD and quad-tree based algo (a kind of mix between chunked LODs and GeoMipMaps) and bicubic interpolation + seeded fractals. The seed was made of two 32 bit digits.

Check the thread "post a picture of your terrain engine" (Google will find).

Thus infinite terrain for 64bits of data and zero artist work. Memory and hardware requirements were also very low.

Quote:

Original post by Charles B Three years ago I wrote an engine that could generate and render at interactive FPS a quasi infinite terrain with 1cm details (shaded). There was a very intricated correlation between a CLOD and quad-tree based algo (a kind of mix between chunked LODs and GeoMipMaps) and bicubic interpolation + seeded fractals. The seed was made of two 32 bit digits. Check the thread "post a picture of your terrain engine" (Google will find). Thus infinite terrain for 64bits of data and zero artist work. Memory and hardware requirements were also very low.

link to that post

BTW: Google didn't find :/

Thanks for making the dirty job for me. I was in hurry. But I just realized I have kept the linky in my bookmarks ;/ Shame on me, next time I'll try to be less lazy.

BTW to expand the discussion and be more in topic. I still plan to take the main ideas and experiences I got from this demo to generalize the concept to arbitrary shapes and terrain generation procedures (fractal/streaming/mixed). But my optimal cross-platform math library is a priority atm and it will be used intensively later for such 3D softwares.

The main benefit of heightmaps was for collision detection, quick occlusion culling and quick self (static or dynamic) shadowing tricks (which were not implemented on the GDev sample but worked in a separate demo). Today with shaders or even SSE it would be quite possible on custom 'Bezier patches'. (very small rocks casting shadows). The fractal part and culling are very easy to port to arbitrary patches.

If someone is interested I can give some details and elements of my preliminary studies for this next gen terrain renderer.

Ok, so to summarize and combine the suggested approaches, one would go something like this:


Generate some preliminary mesh. This could be a simple heightmap-like mesh or one that already has some overhangs and such. To do the latter, use a function that returns a full coordinate given a point input, rather than just a height. [Note: if the input is on a regular grid or similar, it may be a good idea that the returned point is horizontally not too far away from the input point]

Once the preliminary mesh is ready, overhangs etcetera can be added by locally applying special brushes, which may be caulculated from e.g. an erosion model (this may not be necessary if the preliminary mesh already contains such features).


Since I'm dealing with a planet renderer, are those things doable in realtime or near-realtime? I suppose the point->point function can be made fast enough, not sure about the brushes/erosion... For that matter, is there some way to approximate erosion, preferably with a speed/quality tradeoff and/or an incremental refinement option? I'm affraid I'm not very fluent when it comes to erosion simulation..

Charles B, I would love to hear some more details on the algorthims you are using/intending-to-use. Note that I'm more interested in the generation of problematic features, since I know quite well how to generate simple (heightmap-like) tarrain.

Original post by technobot
To me total planet rendering is the grail. The objectives must be maximized to find the right concepts capable of evolving to this grail. What would a perfect planet renderer deliver ? Instant access to any viewpoint with all the necessary sensible details. Realistic and various shapes. Additionally vegetation, and anything you can put on a planet surface.

I think the best to figure it all out is to think in terms of mapping and textures. There is a very strong analogy I hope everyone realizes. Take :
- displacement maps <=> terrain perturbations
- mesh <=> geometric base support for the scene (sphere or plane)
- mipmaps <=> terrain octaves
- trilinear filtering <=> geomorphing

Simply the analogy is theoretical. Do not count a future HW will do it all alone soon. It's not the same scale. We're on the 'mesh', part of it, interacting. Much more details and more complexity is required.

To do the latter, use a function that returns a full coordinate given a point input, rather than just a height.

So what does this function represent ? It's a parametric (and continuous) surface. (s,t) -> x,y,z, etc... In s,t coords it's a kind of 'texture'. This is mapped on a base surface. Height maps are just a special case where the mapping is uniform on the base surface : plane z=0 (implictely x=s and y=t), and the function has only one component z=height(s,t).

Generate some preliminary mesh. This could be a simple heightmap-like mesh or one that already has some overhangs and such.
This is your lowest frq octave. My terrain just started a recursion with a quad. But I could also choose any height map. This corresponds to the smallest mip map. The difference with mip mapping is that instead of having absolute (rgba) values, octaves are best defined relative to the previous level. This helps having infinite precision and handle CLOD better for big terrains. Example :
AbsSmp(s,t, LOD+1) = AbsSmp(s,t, LOD) + k*RelSmp(s,t, LOD+1)

k represents an amplitude decay factor. The metric scale of the LOD. For instance, with k=2, 8bits can represent 256meters at LOD 0 and 1/256 meter at LOD 16. Geomorphing can be seen as interpolating (filtering/blending) between discrete LODs.

The global function, the infinitesimal surface, is just in theory the infinite serie (summation) of every octave from LOD 0 to infinite LOD. To approach high details, at a certain level, highest LODs are necessarily made of fractals or actual texturing tricks. But there are many ways to define intermediates LODs. For instance :

Once the preliminary mesh is ready, overhangs etcetera can be added by locally applying special brushes, which may be caulculated from e.g. an erosion model (this may not be necessary if the preliminary mesh already contains such features).
Overhangs can easilly be created procedurally through extrapolation of perturbations. Note that there has to be some continuity. The difficulty is topological changes with holes. You have to split the surface into several connected pieces, each being mappable rather homogeneously in s and t.

Anyway chunked LODs, texture splatting, etc... all these algos in fact respond same issue. AGAIN. We're ON the mesh. Thus much more realtive details, CLOD. The surface is never seen entirely, too big, it only exists virtually. Only smoothly connected portions of it are seen at one given time. Dynamic caching, procedural techniques are thus fundamental. Even the topology is too complex to keep globally unified at a certain LOD. But locally, at the right scale (cf the k factor) even the topology remains of the same dimension. Just like the planet seen from outer space : a simple sphere, with some very small normal displacements.


Since I'm dealing with a planet renderer, are those things doable in realtime or near-realtime ?

That's totally certain, though a huge work to do. Check a recent discussion in the math forum about an homogenous mapping of a sphere (this started with some ray casting issue). Using octahedron based subdivision offers a clear bridge between the traditional quadtree applied to a plane and a uniform subdivision applied to a sphere. Only a few advantages (free implicit params and euclidian regularity) are lost when the heightmap is no more planar.

For that matter, is there some way to approximate erosion, preferably with a speed/quality tradeoff and/or an incremental refinement option ?

There is surely a cheap way of doing so. Let an erosion or material factor be a component of the parametric function. This factor could interfere with the seeded fractals (dig more in the local normal direction) and reflect erosion.

Note that normally erosion deals with volumes, that is what's under the ground. That is at least several layers or interfaces (that is surfaces) between different types of materials. I think this could well be approximated by a few more components on the function.

Every kind of refinement thus becomes a question of higher LOD extraction. It's very important to note that if this generalized model works for many parameters (terrain = serie of multi-component bivariate functions), anything realtime can be imagineable. If erosion was simulated with realistic physics entirely, this could only be done in a costly preprocessing stage. Thus for real time, it could only be done for the lowest LODs. If you want a planet renderer capable of speedy camera movements, capable of realistic details, you need linear performances and a huge bandwidth to generate great ammounts of procedural details on the fly.

To sum up, think of it :
1) A good CLOD + every culling ensures a constant ratio between memory + processing requirements and the screen resolution at any instant.
2) A perfect dynamic engine with CLOD ensures a constant rate of regeneration of details.
3) Last, camera speed matters. If you move fast, less details are perceptible, thus required, because of motion blur.

These 3 predicates are the most important to ensure a constant and high frame rate. My demo three years ago was meant to prove this works in practice too. You could run at any speed, brake, have details appear quasi imperceptibly. Changing from traditional flat height maps to spherical planets with local overhangs or holes does not have to change this acquired result. It's just a question of using the adequate algorithms and implementations. Keeping the three predicates in mind is what's essential.


Charles B, I would love to hear some more details on the algorithms you are using/intending-to-use. Note that I'm more interested in the generation of problematic features, since I know quite well how to generate simple (heightmap-like) terrain.

I hope this started to answer to some of your concerns. I only gave the main directions. I hope you'll find some food for thoughts with it. To me it's far more important to expose the global vision I have first. If I had given some implementations details first they would have been only partially understood.

[Edited by - Charles B on October 13, 2004 7:59:39 PM]