Re: [Algorithms] Terrain performance comparisons

[Jonathan B. <jo...@nu...>]

> 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.

Hey man, you know what I meant.

> 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.

Well I just want to say that I don't seem to have any special interest in
dissing ROAM, as you may think.  I have used it as an example, because
it is one of the more well-known terrain systems.  I could have just as
easily made all the same negative statements about my system I 
presented at siggraph 2000 (and in fact I often do) -- but not many
people know how that system works, so that wouldn't be as
effective.


> I was expecting a reapparance of the "cycle of death" arguement, and I 
> just don't buy it.  Incremental algorithms do not require that you 
> always process all the possible work in a given frame.  As I noted:

Well the "cycle of death" is an actual physical
phenomenon.  If "computer science" is actually a science, then this is
one of the kinds of basic entities that it deals with, alongside, say,
the question of how long it takes to sort a group of objects.

So I think that complex algorithms should be designed around these 
core observations about what it means to be a certain kind of
computer program.  I'm not really satisfied with the approach of
"design an algorithm ignoring some of these facts, then add
workarounds."  What you're explaining here seems to be to
be a workaround that isn't very robust:
  
>> 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. 

I did a lot of this kind of thing in my system, and I never came up with
a solution that I thought was good.  

Due to the nature of the bucketing schemes that people tend to use,
you *cannot* delay reprioritization for very many frames in a row or else
you end up, essentially, having to re-do the whole thing from scratch.
When that happens, it's painful.

Duchaineau's original paper mentioned the Newton-Raphson-esque
thing, which is already about guessing how long you can go without
re-evaluating vertices.  Clearly, if you wait longer than your conservative
bound for reevaluation, you're likely to update things too late, i.e. suffer
a visual quality hit or a tessellation efficiency hit.  A little of that isn't
so bad, but how much is okay?  And why spend all this effort and CPU
time proving bounds on 70% of your vertices, only to violate those
bounds with the remaining 30%?

I'm not saying that there's no solution to this within the ROAM framework.
I am, though, rejecting your characterization of the matter as easy/simple.

> 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.

Another thing that I reject, not just about ROAM but about many published
algorithms, is the way they purport to be easy, but in fact are very 
complicated due to all the workarounds that need to go in there.
If I start off with one moderately complicated thing, then add 23
workarounds each of which is "easy", we very quickly end up with
something that is not "easy" at all.  So whenever someone says "Oh just
do this one augmentation, it's easy", that is a big warning signal.
If on the other hand, they say "you can do this one augmentation,
but then here's a list of 15 foul interactions that might happen with
other parts of your game system," then I am more likely to trust them.


Just so I can share the love and prove I'm not just a bitter anti-ROAM
curmudgeon -- Perspective Shadow Maps are the same way.
Don't use them.


> 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.

Here's an example of what I am talking about.  Your language is extremely
hedged in the above paragraph, and rightfully so, because the idea is a bunch
of hand-waving.  In practice the only robust way of knowing when the
update cost exceeds some threshold, is to wait for that to happen and then
measure that it happened.

> 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.

Well, this all depends on the nature of the non-incremental system, doesn't it?

Chunk LOD is basically doing nothing to update the mesh between frames.
2 times 0 = not very much.  [Yeah, it's doing something, but it's so amortized
as to be basically nonexistent; see earlier discussion about small-grain
versus large-grain coherence].

I'm not saying *all* non-incremental systems are better than *all* incremental
systems.  I am saying that incremental systems have inherent drawbacks
and so they should be avoided if a comparable non-incremental approach
is available.  
 
> 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.

I don't think it's a no-brainer at all.  I have never seen this successfully
done in a game, to the point where I couldn't see the detail snap
as I moved.  Have you?

I think this is one of those widely-held myths that seems like it ought to be
true, but in practice, ends up being not so true at all.

   -Jonathan.