Author Topic:   Wavelets for terrain LOD
Chris C
posted June 15, 2000 07:36 PM         
Does anyone have any thoughts about using wavelets for terrain LOD? I know some of you are intrigued by the idea, so I'm going to try and introduce the topic and see if we can take it any further...

AFAIK, wavelets (a form of octave sub-band decomposition, similar to Laplacian Pymramid) encode the frequencies of a signal (in our case, a 2d landscape) logarithmically ie. each stage of coding represents 1/2 the previous stage's frequency band. The coding process is a sequence of stages that repeatedly sub-sample the previous stage's signal to half its frequency and output the difference between this signal sampled back up to its original frequency and the original (previous stage's) signal - this difference is output as a series of coeffecients, known as 'wavelet coefficients'. Of course, re-sampling the sub-sampled signal back up to its original frequency will result in aliasing (playing an 8khz audio sample at 44khz doesn't make it sound like CD-quality!), and it's the wavelet co-efficients that basically encode this so the original signal can be reconstructed exactly. The neat fact is that the whole coding process only needs as much storage as the original signal. This is a very rough explanation - try and find some 'wavelets in plain English' sites if you want a proper one!

So how on earth does all this fit in with landscapes? Well, the wavelet encoding process can be thought of (very loosely!) as producing a series of mip-maps in the frequency domain. This suggests that low frequency 'mip-maps' can be used for distant terrain and high frequency ones for close terrain. Sadly, when we have a terrain containing a high frequency mountain range (ie. lots of tall spikes!) this idea will break down as the spikes have very small/non-existent low frequency components and hence will cease to exist when they move into the distance - disappearing mountains is not a particularly desirable artifact when rendering terrain... This implies that we need to come up with a different way of handling the wavelet-based LOD, perhaps to take into account the magnitude of the frequency components. Which brings me nicely onto the idea of compression using wavelets - we can also throw away high frequency components that have a small enough magnitude. Of course many other more complex compression techniques exist, but this introduces the tempting possibility of realtime progressive decompression of landscape geometry.

Similar ideas can of course be applied to the landscape texture - there's been loads of research into using wavelets for image compression (JPEG 2000 uses wavelets) which could be adapted to handle huge landscape textures.

It remains to be seen if any of these ideas would actually produce a workable LOD algorithm that compares favourably with all the others out there - there are many issues that need to be investigated, but I hope that some of you may have some ideas/thoughts on the topic. I've rambled on for long enough...


New Member
posted June 18, 2000 02:40 PM            
Wavelets seem like a good idea for terrain. I've thought about them for a while although the specifics on wavelets I haven't investigated. My idea for not using wavelets was exactly as you specifed. Consider an image say 256x256. If you mip-map this down a level, to 128x128 you lose resolution. If you point filter this, you remove information, or samples. If you bi-linear filter this, you mediate your peaks and troughs. If you consider the example of the mountain sorrounded by valleys, then you will realize that point filtering will eventually remove the mountain (no samples left to depict it) and bi-linear filter smooths out the mountain. Both of these are undesirable effects. The same sort of effect happens with wavelets. This, to me, is not a good thing. I prefer the bin-tree sort of method whereby I can specify the tessellation level for certain areas depending on world coordinate bounds. This in essence preserves my mountains and troughs from the effects of LOD. I'd love to hear if you have any ideas on how to improve wavelets for use on terrains however.

And since we are on landscape geometry, I guess I'll add this. I don't feel that curved surfaces are a good solution for landscapes either. A lot of people think they are really cool nowaday and that using them for landscape would be awesome. Well, it isn't. For one, you can't shape your land like you can with heightfield. Peaks are nearly impossible due to the continuity with patches. And you don't end up with infinite resolution as some people think. You merely end up with infinite 'smoothness' as you get closer to your patch. And that's why I think terrain patch rendering sucks.


Bryan T
posted June 20, 2000 12:31 AM            
I thought wavelets were lossy compression? Similar to Fractal Image Compression, but not. I'll have to look them up again.

Anyway, they sound like a great idea at first, but the problems Draigan mentioned are important. I feel that future algorithms which incorporate wavelets or other LOD algorithms for the storage of landscape data will use special methods to hide these problems.

For instance, by slightly curving the plane that the viewer walks on, you create a horizon line which keeps distant objects from appearing. Much the same as fog, but in a more natural way (curvature of the earth).

Another idea I had was to 'solve' the landscape equation in 2D to find all the local maxima and minima. Then set all those points as 'important' on the landscape so they would be tessellated to full detail.

A simpler method would be to ensure that when you create the landscape to begin with, all the maxima and minima occur at higher-level nodes in your algorithm.



Chris C
posted June 24, 2000 11:06 PM         
After doing a bit more research on Wavelets, it's become clear that that using wavelets for multi-resolution geometry has been done many times before... The maths (math for you guys from the US!) is complex but essentially wavelets can be adapted to cope with all the things we'd like - ie. multi-resolution representation of terrain preserving all major features.

Bryan is correct - Wavelet compression *is* lossy. I don't think this will be too bad - we've never really investigated the difference between terrain compressed lossily and uncompressed terrain (I could be wrong!), but I reckon the difference will be not worth worrying about. I really need to do some detailed research, but I think it may be quite possible that wavelets will provide a multi-resolution representation of arbitrary terrain (possibly compressed) with (hopefully - I'm not totally sure yet) the same storage space as the original terrain. Applications to textures could also prove very useful, too.

Without all the wavelet jargon, what would be nice is a way of storing the terrain at different LOD's that takes no extra storage space, but preserves important features. This criterion is used in most multi-resolution techniques using wavelets, so we just need to special-case to terrain heightfields and we could have a new technique on our hands - I'm not speaking from experience yet, so don't take what I'm saying as gospel, but I think this could have important applications to huge terrains where chunks of terrain need to be spooled in at varying LOD's, along with their texture maps.

Check out some of the papers on the web for ideas, but beware they're probably DSP/math heavy!