Re: [Algorithms] Terrain performance comparrisons

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

Jonathan Blow wrote:

>>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.
>>    
>>
>
>Do you: Need to have your viewpoint move quickly, while rendering
>with nontrivial terrain detail?  If so, do not bother with any kind of
>frame-coherent CLOD (including any version of ROAM).
>
>In fact, I am still waiting for people to understand that frame coherence is
>to be avoided in games whenever possible.  I am going to submit a siggraph
>presentation on that (and some other things) for next year.
>
>   -Jonathan.
>
>  
>

You're welcome to "avoid frame coherence" as much as you like, and we'll 
see how much gamers enjoy headache inducing games.  What you probably 
meant is to forget exploiting coherence.

Frankly Jon, this is ridiculous.  We all understand that an 
incrementally updating algorithm must make exceptions for in-coherent 
cases, but this is allowed for in ROAM (in a simple and flexible 
manner), and dismissing it out of hand is simply not warranted.

I know this discussion has taken place at least several times in the 
past, but you still continue to publicly mischaracterize the ROAM family 
of algorithms.  I maintain that your particular implimentation 
experiences do not have any bearing on what ROAM is or is not capable 
of, and as such the biggest failings of ROAM remain social in nature, 
not technical.  This is not the proper forum an ongoing debate, so for 
the algorithms-list I will just restate the relevant technical points.

Despite frequent, rapid, or large discontinuous viewpoint/direction 
changes, your system MUST be presenting primarily coherent view 
sequences to the user, or else they would be left with a high-speed 
flickering slideshow instead of an animating 3d visualization.

Whatever coherence exists for the viewer in a given sequence of frames 
is also going to exist in the output mesh (and primarily in the 
hierarchy, not necessarily the rendered leaves, though they will tend to 
update in a spatially sparse manner).

Should the cost of updating the output mesh exceed that of creating a 
new one from scratch, this is an easy and correct fallback mode, which 
may then resume coherent updating as warranted.

The degree of view coherence can be measured from the changes of 
viewpoint, refinement priorities, and hierarchical frustum culling 
results of successive frames.  These factors are useful in deciding when 
the incremental update cost may exceed the from-scratch construction 
cost for a frame.

Exploiting frame coherence is abitrarily more scalable (both in 
framerate and output size) than not doing so, despite the issues with 
incoherent updates.  To double the fps of a non-incremental system (for 
a given framerate independant view motion) doubles the cost of the 
entire process (updating the mesh and rendering it), whereas it hardly 
impacts the mesh updating cost of an incremental system, since the 
change in work per frame would be cut half.  To double the output size 
has similar implications (besides doubling rendering time): for a 
non-incremental system it doubles the large update cost of rebuilding 
the mesh from scratch, whereas for an incremental system the it only 
doubles the small incremental change cost.

Finally, I'll observe that quickly moving viewpoints actually relieve 
the need for nontrivial terrain detail.  The details obviously become 
less relevant as the viewpoint moves increasingly fast (that's not to 
say there shouldn't be some detail, just that the particulars become 
increasingly irrelivant).  This is practically a no brainer.  ROAM can 
quite easily accomodate per-frame time constraints due to the nature of 
the dual-queue optimizing process: the work happens in order of most 
important to least important changes, so stopping the proccess early is 
ok (as the linear cost of incremental work brings diminishing returns), 
and successive frames will pick up where it left off to fill in the 
details when the view stabilizes again and coherence increases.

Our ongoing work indicates that ROAM will continue to cleanly scale into 
the hundreds of millions of triangles per second as hardware capabilites 
grow, and we're always curious to see how competing methods will fare 
and what new approaches will become popular.  Incidentally, my current 
research is on visibility algorithms for multires geometry, and despite 
the currently impressive adaptivity and robustness of the latest method, 
my biggest fear remains that its scalability will be limited without an 
incremental scheme to exploit coherence.

-Lucas