Author Topic:   Terrain Representation
New Member
posted June 20, 2000 03:20 PM            
This message is kind of a spinoff of the wavelets for terrain post. I just made a new one because I find that I ignore ones that I think I've already read. Anyway....

It is interesting to note Bryan that a patch (not a ROAM style patch, but a cubic spline patch) based method will lend itself more easily to computing local minima and maxima and inflection points. So how do we achieve this sort of functionality with heightmaps? Well, if we construct a interpolating function that interpolates our heightfield samples nicely, then we can apply normal math methods to this to find the local minima and maxima of the reconstructed function. While this may not be exact, depending upon your interpolating function, it may achieve min-maxes that are very close to the sampled min-maxes. If this is indeed the case, then the idea of using a polynomial based landscape becomes even more useless since it's only assets now become 'smoothness' and trivial LOD implementations. Now we both know that the smoothness is not always something good. There are many cases in nature where we need sharp peaks and points. This cannot be accomplished with an cubic iterpolating function. Why? While it may be possible, the amount of control over the curvature and shape of the landscape becomes very limited. It becomes very hard to manipulate the polynomials to move in the ways that you want. And as the degrees of the function go higher, it becomes increasingly more difficult to control. The other issue then is the LOD. Current patch LOD methods (as far as I know) do not take into consideration the local minima and maxima. The LOD can be compared to removing or adding every other sample from a heightfield. It will not give the best results.

So what am I getting at? I don't know. I'm just rambling. Feel free to discuss. Maybe we can figure out a better way to store this stuff.


New Member
posted June 20, 2000 03:23 PM            
And by the way Bryan,
your idea of storing terrain with the local minima and maxima stored at higher levels intrigues me. Have you given any more thought to this?


Bryan T
posted June 20, 2000 09:18 PM            

The idea I had tossed around for awhile was this: Take a heightfield with one spike in it. As you move away from the spike, it will either turn into a mountain (tall and wide), a hill (short and wide), or dissapear altogether (depending on your algorithm).

This is not ideal. Preferably, you would maintan the spike up until the point where the node containing it's height sample goes out of sight. Otherwise, you have an extreme jump in elevation at that point (a 'pop').

So, given a regular subdivision recursive algorithm, the spike would be maintained longer if you placed it at one of the original corners of the terrain. Likewise, the centerpoint of the terrain, and the centerpoints of the four highest-level quads are also high in the tree.

Continue this thinking down a few more levels, say to level 5 of the tree. If all your 'spikes' were located at one of these nodes, you would be nearly guaranteed to have good looking terrain, since the spikes are so high up in the tree. (BinTrees have anywhere from 10-20 levels, so level 5 is pretty high up there).

Of course, no terrain algorithm so far handles spikes well, but they're good for illustrating this point.

--------- (switch topics) ----------

Now for non-aligned maxima/minima. It's rather a simple problem really. Basically scan the heightmap for the maximum and minimum heights based on a radius. Add all the height samples within a radius of 10 samples (with a circular distance metric, not orthagonal). The height map location with the highest value is the maxima for that radius, the one with the lowest is the minima for that radius.

Now, make a list of the 10 largest values for radius 10, and another list of the 10 smallest values for radius 10. Put all these values into a list of 'important terrain features'.

You could get really spiffy and locate the 5 most important features at radius 5, 7, 10, 13, 15, etc.. (eliminating duplicates). This would give even better definition that using just one radius.

This is not a math-based method like you are describing with aproximating the landscape using polynomials, etc.