flipCode - Tech File - Alex Champandard [an error occurred while processing this directive]
 Alex Champandard Click the name for some bio info E-Mail: alex@base-sixteen.com

 10/06/1999, Dynamic LOD, Landscape Generation and much more...

Well, a great summer is suddently coming to an end, and it's nearly time to go into hibernation... erm, to University. So I thought it might be better to get some ideas out of my head before the nasty beer monster gets hold of them ;) I'd love to hear any coments what so ever about all this stuff.

Dynamic Level Of Detail On Next Generation Video Cards

Most articles on future video cards seem to oppose T&L with high fillrate as if there was a compromise to be made. The ultimate video card would obviously provide the best of both these techniques. But until then, we will to have to put up with two different trends.

So far all the LOD algorithms people write about seem to be based on parametric surfaces, like Q3A's quadratic bezier patches. Such algorithms would nicely take advantage of T&L, by sending a greater number of smaller polygons to the video card. But a card with high fillrate would not be taken advantage of.

And this why I got the idea of using a fillrate based dynamic LOD algorithm. The key is "Parametric Texturing", like the shader in Q3A can render, but with dynamic LOD. The main concept being you split up your texture into different layers which you overdraw onto your polygons. The difference being that my LOD algorithm would dynamically associate an importance coefficient to each layer, depending on the LOD settings: distance, angle with the camera, card fillrate, user settings... The shader would then only render a certain number of the most important layers. I doubt this concept is new, but I've never heard of it before. I'm probalby just stating the obvious, but some people may benefit ;)

So with a totaly parametric engine, you would be able to take advantage of both types of next generation video cards. A high fillrate capable video card would render a smaller number of bigger polygons, with more texture layers applied to them. A video card with fast T&L would render a greater number of smaller polygons, but with less passes for the shader. And in the more distant future, you would be able to have higher LOD levels in both algorithms.

Random Landscape Generation

Over the past few days, I've been implementing core algorithms for my landscape generation tool codenamed GeoMorph. I've come accross quite a few different techniques to actually generate the terrain.
Perlin Noise

Perlin noise is composed by adding interpolated random noise functions at different frequencies and amplitudes. It's ideal for modeling landscapes since they can be easily zoomed and resized, without loss of data. You can of course combine various layers of perlin noise by multiplying them or adding them together, like Terragen does. Terragen also uses ridged perlin, which is most effective when overlayed to an existing terrain. I'm not entirely sure how this function is generated, but it creates variable size peaks at variable frequency in the landscape. I'd like to hear from you if you have any idea on how to generate ridged perlin.

Fractal Subdivide and Displace

This method is based on the diamond square algorithm, which basically takes neighbouring points in the heightmap and fills in the height value in between by taking the average plus a random coefficient. For better results, you can also use fractional brownian motion to generate your random values. You can easily make sure your map wraps around by repeating the first line and row as the last.

Binary Raise and Lower

The original algorithm I came accross was applied to a sphere. You simply choose a random plane that splits your sphere into two parts, and raise all the vertices on one side of the plane, and lower the vertices on the other side. Repeat that step until the aspect of the planet is satisfactory. You can hack this algorithm to make it work on a bitmap, by using inverse spherical projection. This is slow, but your map will wrap around. I didn't really mind my map wrapping around, so I converted the algorithm to 2D. You pick a random line that splits your bitmap into two parts, lower all the points on one side, and raise the point on the other. With about 5000 iterations, the results are very satisfactory. The map doesn't look like it's on a grid as much as the previous method.

Height Reassignment

This is just another one of my ideas for the moment, but it should work :) Basically, you define a function, that takes a height and returns another height. So your function could take the heights from the range 0..31 and turn them into a plane with slight random bumps, and the values from 32..255 could form some low altitude mountains. This is what the function would look like:

This simple hack solved the problem of non realistic landscapes. Indeed most of the algorithms above do not generate realistic landscapes, with vast planes and smooth transition between different types of features.
Of course once you've generated the base landscape, you can modify it manually with raise and lower tools. And obviously smooth, sharpen, dirt and erode filters. That last filter being the most difficult to come up with. I've started a thread in the general discussion about landscape generation, if any of you are interested by joining in ;)

Microsoft Foundation Classes

Once I'd got the core of GeoMorph running in console mode, I new the best thing to do would be to add a nice user interface to it all. So I told the wizzard to create a standard MFC application for me. I compiled and ran it: that was exactly what I needed. As I started browsing through the source, everything seemed to me a little too much over the top. I have to admit my measly few weeks of Windows programming experience didn't help me much. I definetly miss the good old days of C and assembler, where you have total control over everything... On the other hand, I have enjoyed my initiation to OOP until now, but pushing it too far is ridiculous. Some people have been trying to convince me that OOP isn't a very good way of doing things, and I'm starting to see their point. It's obviously a step forward, but there's much more room for improvement ;)

Anyway, a couple hours of work and a good book on MFC would obviously do the trick. But i'm not too sure if spending some of my time learning about the foundations of an OS that will self-destruct in about 3 months is a good idea. So I rebooted into linux, just by principle... I'll try GTK tomoro ;) If any of you have had good or bad experiences with GTK, I'd love to know... I'll probably benefit more from learning about linux programming anyway. I have to admit I'm looking forward to that, since the only other experience I had of porting OpenVL to X-Windows was extremely pleasant.

No doubt I will be doing more MFC in the future, but I'm not really looking forward to that right now ;) Of course, not only MFC seems tedious when you compare it to the pleasures of teaching yourself OpenGL!

More On Bezier Patch Clipping

In my last techfile update, I mentionned clipping against cubic bezier patches. I've had a bit more feedback about this, and I've realized how short sited I've been. I was worying about differences in tessellation on current hardware: big cracks appear between patches tessellated at level 2 and 4, for example. Admitedly that's quite a big problem, but it won't be for long ;) In the near future, we'll be talking about tessellation levels of 512 to 2048... Until we reach those counts, where dynamic lanscape LOD is much more stable, I don't expect to see many bezier curve based terrain engines in games.

The same thing applies to collision detection. For high poly counts, if you were to clip against each tessellated poly, that would get quite slow. That's why I think the obvious way is to find the theoretical intersection between patches and 3D lines. Now the problem is finding that intersection efficiently. I was thinking of using the Newton-Rhapson technique, but that would be quite expensive. I'll probably have to read more papers on raytracing bezier patches before I can find the quickest way. Any comments welcome.

New Web Site

I redesigned my web site weeks ago, and it's been gathering up dust on my hard disk until a few days ago. I've finnaly got it up and running now. There's not much new content at all, but it's easier to browse ;) You can find it here.

Well, that's it for now... hope all that was usefull to someone ;)

Alex

• 01/05/2002 - A.I., Websites and Voxels
• 03/05/2001 - State Of The Art Character Animation
• 01/24/2001 - Alternate Programming Languages
• 01/11/2001 - The Sound Of Silence
• 09/20/2000 - Engine prototypes, yet more landscape LOD and hard body physics
• 07/13/2000 - Good Practice (TM)
• 06/13/2000 - Revision Week Indeed
• 04/11/2000 - Escape From Inactivity ;)