Author Topic:   How to use overhangs/caves w/ terrain algorithms?
New Member
posted May 25, 2000 12:01 PM         
I was wondering if people have used other terrain characteristis like overhangs and caves in games. I am guessing that height maps can be used but you have to find a way to overlay multiple maps. Are there other terrain formats (DEM) that take into consideration other land forms? What about LOD algorigthm considerations? How would one go from a ROAM or adaptive Qtree algo to a BSP or octree algo when transitioning from outdoor to indoor terrain? Thanks, Jerry


Bryan T
posted May 26, 2000 03:49 PM            

I have not yet seen a terrain engine with LOD using caves/overhangs. Usually these features are pre-modeled objects implanted into the landscape. They often use their own LOD (several different models at different details).

Some of the work of Hoppe et. al. can maintain a continuous LOD for an arbitrary mesh, but it is neither fast, nor efficient for a game implementation.

The outdoor/indoor stuff is taken care of through different parts of the rendering engine, ie:

if (terrainVisible())


Thus the BinTriTree/QuadTree is not in the same pipeline as the BSP tree. Now, that's not to say it can't be done.. but what a chore it would be!

I could see combining a OctTree with a BinTriTree or QuadTree algorithm, they are functionally similar. Or perhaps a grid-aligned BSP that followed the lines of the BinTriTree. (Ok, just rambling now..)



posted May 26, 2000 07:37 PM         
i don't know much about programming, but i found this while searching around for digital terrain info...

page forward (~10 pages) until the title "Landscape Engine" appears.

apparently, the developer of this software uses multiple heightmaps to create subterrainian worlds.

the site also has a discussion forum that appears pretty active... hope that helps!


New Member
posted May 27, 2000 09:08 AM            
A great place for information on everything 3D or agorthmic is the algorithms e-mail list hosted at 3dgamedev.com

If you go to http://3dgamedev.com/lists/algo_list.asp
to get on the list.

The list is pretty active so I'd recommend the digest (it's easy to setup) then fire off the question, I think something called VIPM (which I think means Vertex Indpendent Progressive Meshes) might help for caves etc.
It seems to be based on the Hoppe stuff but seems to be getting faster and faster.

Hope this helps.



posted May 31, 2000 04:11 PM            
It's "View Independant Progressive Mesh", which is a bit misleading since the whole point of using a LOD scheme is view dependancy. A progressive mesh, as hoppes defines it, is a starting low LOD mesh, and a series of edge expansions (replacing one vertex with two, creating an edge between them, and adding two faces to the mesh). You create this progressive mesh by taking the original mesh and repeatedly apply the reverse of an edge expansion - an edge collapse (replacing two vertices that are the endpoints of an edge with one, deleting two faces from the mesh), using some sort of metric which collapses affect the mesh the least.

A VDPM (View Dependant PM) is something Hoppes created that starts with the base mesh of a PM, and then uses various veiw dependant metrics to perform certain edge expansions. He uses a scheme to determine the value of any specific edge expansion given the current view, and another scheme to determine if that expansion is legal (each edge expansion requires certain faces and vertices to be present before they can be performed). This allows for a rather optimal mesh, taking into account view frustum, view angle, and distance from every part of the mesh - but it's very complicated, and from I've seen, not practical for game use.

VIPMs, as used in LOD schemes, are also view dependant. However, the list of expansions will always be performed in the same order (the order is the reverse of the edge collapses used to create the low LOD mesh) - only the number of expansions performed is affected by the view metrics (usually only object-camera distance is used). So you start with the low LOD mesh, and the closer it is to the camera, the more of the edge expansions you perform. This far less processer intensive than VDPMs, and also more cache friendly. It works very well for objects in the game - like characters and whatnot, but it's tricky to use with terrain. With game objects, since they are relatively small, the lod required across the entire mesh will be similar. But for large objects, which commonly have only a small portion onscreen at a time and with large variation of distance from camera across the mesh, many triangles will be wasted.

The trick to using VIPMs with terrain is to break the terrain up into a bunch of VIPMs, and somehow hide the seams between them. Not easy =]

I've implemented VIPMs for game objects, and it works pretty well from what I can tell so far. I'm still wrestling with trying to get it to work with terrain, or any sort of large scale objects, though.



posted May 31, 2000 04:14 PM            
Also, I remember it being mentioned that Drakan used multiple heightfields with LOD to create caves and overhangs. Could be wrong on that though.



New Member
posted June 04, 2000 05:11 AM            
Cheers CheshireCat,

I joined the list in the midst of a massive discussion about VIPM but I had absolutely do idea what was going on! I've read Hoppes paper(s) but that was before I'd implemented anything myself. I think I may ahve to go back to them with a bit more experience under my belt.

Thanks for the explanation.