Re: [Algorithms] Terrain performance comparrisons

[Lucas A. <ack...@ll...>]

Daniel Duhprey wrote:

>On Thu, 24 Jul 2003, Tom Forsyth wrote:
>
>-->If you have any specific questions, I'm sure we'll be happy to help :-)
>
>I have some questions :)
>
>I took it upon myself to try to analyze the modern contenders for "terrain 
>engine of the year" to see if any of them performed as a panacea in the realms 
>of quality and performance.  Having been frustrated by the algorithm of the 
>week syndrome that seems to prevail; I figured I'd wind up needing to have a 
>couple easily swappable plugins for our engine (maybe even needing to switch 
>between algorithms depending on the context).
>
>I'm really trying to come up with a general solution for a general game 
>engine (even if that "general" solution is a set of swappable plugins that 
>present an identical, or similar, interface.)
>
>The questions:
>
>what are the major contending algorithms for modern systems?
>  
>
Hi Daniel,

I'd nominate the modern ROAM derivations (2.0 and so forth) for 
performance, generalization and flexibility, the similar yet 
oh-so-simple "Visualizations of Large Terrains Made Easy" by Lindstrom 
and Pascucci (and damn it if Valerio beats us at Settlers of Catan again 
tonight) for the simplicity/performance tradeoff, VIPM methods (I still 
hate this name, Mark D thinks we should call em "progressive vertex 
array sliding window" methods - since view independance isn't the main 
point, but VIPM seems to have stuck with this crowd) either as stand 
alone method or for per-chunk GPU optimizations of a CLOD optimizer. 
 There are also lots of domain-specific and cross-domain approaches, 
like T.Ulritche's ChunkedLOD you mentioned.  

It really depends on where your interests are, what you consider 
'major,' and what kind of 'modern system' you have.  I'm obviously in 
the ROAM camp and there are necessarily a set of considerations that 
come with that.  

Geomipmapping is cute (mipmapping easy, GPU use, yay!), but not so smart 
(ok, maybe I'm a CLOD junkie), and not a real contender in my book.

>the three I've decided to try out are ChunkedLOD, Roam 2.0 and Geomipmapping.
>Are there any others which have feature sets drastically different from these 
>three?
>  
>
Almost certainly, but it comes down to what you need to do.  Your 
"general game engine" still needs some fixed scope to start from.

Do you:

Need CLOD adaptivity?  This might be important for simulations 
(requiring high-fidelity object-on-terrain placement), or irrelivant if 
the terrain is just a pretty backdrop.  It's also a scalability 
consideration - is being able to view from 50,000 feet and then zoom in 
to a nose-on-the-ground viewpoint necessary?  Can you rely on always 
having some particular type of viewpoint (eg, eye-level and X meters 
away for a FPS) or is more flexibility required?

Have to work from a classic pre-made heightfield?  Or want to generate 
it procedurally as needed?

Have a fixed time-per-frame budget?  

Need strict screen-space error bounds?  Some methods can deliver on 
this, others make greedy approximations, and still some are just wild 
guesses.

Have CPU utilization limits?  Or to put it another way, is your terrain 
rendering prioritized over AI routines?

Have a GPU to use?  Have to use it?  Must prefer it to CPU use?

Require "geomorphing"?  This is, IMHO, a case of trying to solve the 
wrong problem.  Still, some people demand it.

Have memory budget or access pattern issues?  This is likely to 
important on consoles.

Require discontinuous viewpoint motion often (which kills incrimental / 
time-space coherent algorithms away)?

Need to load areas dynamically as the viewpoint travels?  This pertains 
to extreme world size/detail situations, and your platform's storage 
modes (memory vs disk vs network streamed).

Have certain texturing requirements or limitations?  Tiles or splatting 
or one-big-texture?

Want to modify the terrain at runtime?  We all like to blow stuff up (or 
even build stuff), but do you NEED to?

Benefit from being able to generalize your LOD to non-terrain features? 
 This could be useless for your app, or a huge win.


The bottom line is that you really need to know your platform, audience, 
and so forth to pick the right feature set to shoot for.  The more of 
these sorts of questions you can answer for yourself, the better you can 
evaluate the various options.

ROAM derivitives can address just about all of em (possibly 
simultaneously - if you're a really sharp), but (despite deceptive 
appearences) it is NOT an easy algorithm to master (I've been studying 
it for years - ROAM 2.0 improves, but it's still a steep 
learning/performance curve).  Others will excel in certain areas and 
fail elsewhere.

>If I want to maintain backwards compatibility with older systems should I use 
>an older algorithm (original roam) or do the newer ones still work even if you 
>can't assume there's a fast GPU?
>  
>
ROAM 2.0 is an all-around improvement over classic ROAM, but some things 
like chunk-output won't benefit an older system (as it's really a GPU 
utilization technique).  Some techniques are GPU exclusive, some utterly 
fail in GPU utilization, and some can work well either way.  If you're 
just starting development, will you even want to think about pre-GPU HW 
support by the time your system is in a released game?  Why not support 
the GBA as well then?  (notice: that was a joke.  although we could 
discuss the merits of terrain engines in portable game systems ...)

>Is it inherently impossible to boil down a set of options for terrain into 
>some kind of common subset? (e.g., all can be heigtmap based, all can deal 
>with texture palletes, all have a similar error metric, etc.)
>
>Thanks in advance
>
>  
>
I'm afraid so, not all terrain algorithms are cut from the same cloth 
(raycasting anyone?  nurbs/curves/subdivison surfaces?  TINs?).  The 
most popular subset is easily "heightfield based."  Some other subsets 
might be these you described or portions of the elements I listed above.

So, maybe the options don't boil down into a single subset.  Regardless, 
the game-terrain-flavors you want your renderer to support still might.

-Lucas