Re: [Algorithms] Terrain performance comparisons

[Thatcher U. <tu...@tu...>]

On Jul 25, 2003 at 01:49 -0500, Jonathan Blow wrote:

> I'm not saying frame coherence is 100% bad, because the fact is that
> we don't have viable non-coherent alternatives for a lot of tasks.
> Physics is a good example.  I just think people need to look
> carefully at their options and understand what they're doing.

Yeah, I agree with this last bit.  And I agree that fine-grained
frame-coherence a la ROAM is mostly obsolete.

"Frame coherence is generally bad" might be misleading though, IMO.
Modern high-performance computing depends entirely on memory
hierarchies that require temporal and spatial coherence to work
acceptably.  Coherence in games is getting *more* important (although
at a coarser grain), due to hard disks.  CPU/GPUs have gotten faster,
disks have gotten much bigger (but not much faster), and DVD's have
become a common distribution format.  A realistic game needs to
strictly limit the speed and mobility of the viewer in order to work
at all, by dividing the world into levels separated by discrete
loading events, or streaming sectors in the background, etc.  No game
can afford to randomly show a different part of the whole game-world
in successive frames, unless that game-world is unacceptably small.

Anyway, I suspect I'm railing against something you didn't exactly
say.  I just want to make sure coherence (at a coarser level) gets its
due, because IMO it's just about the most important aspect of terrain
LOD.

As I see it, choosing a terrain LOD algo boils down to:

* how much detail?

* how big?

* how fast can the viewpoint move?

* how are you going to manage that amount of data?

* does the terrain change?

and everything else falls out of that.  

My cookbook in a nutshell: if the amount of data is relatively small
(i.e. fits in RAM), then brute force, ROAM or its relatives, or
geomipmapping are probably what you want.  The minute you start
positing expensive procedural stuff, or large disk-based datasets,
then coherence becomes extremely important and you ought to think
about chunking.  If you can tolerate limited view distance, then
forget LOD; just string together portal-connected areas, or use a wall
of fog within the radius of a couple of chunks.  If you need big
aerial vistas then you should think about hierarchical chunking.

-- 
Thatcher Ulrich
http://tulrich.com