gdalgorithms-list

Re: [Algorithms] Terrain performance comparrisons

[Charles B. <cb...@cb...>]

In fact, I would say that all this concern for terrain LOD is absolutely 
ridiculous.  Rendering the terrain is just about the easiest aspect of any 
system that would make use of it.  Say, for example, that I want to a huge 
continuous MMORPG with detailed terrain.  What kind of problems do I have 
(that are directly related to the large world and desire to have far view 
distances and seamless movement) ?

1) seamless paging/streaming of lots of data
2) LOD/locality of network data
3) network prediction and lag compensation for many/far entities
4) server distribution and seamless links
5) LOD for all the game logic in the distance
6) LOD for all the characters, plants, shaders, etc.
7) LOD for the client-side physics engine
8) LOD for the terrain rendering

Hmm, terrain rendering is just about at the bottom.  As a concrete example, 
have a look at Planetside or Asheron's Call 2.  Sure, both could be served 
by a better terrain renderer, but in terms of the failings that need 
improvement, terrain rendering is way down the list.

At 01:17 AM 7/29/2003 -0400, Thatcher Ulrich wrote:
>2. In my opinion, the *real* reasons people don't always use LOD (of
>    whatever flavor) are based on practical engineering economics, not
>    anything social or purely technical.  The fact is that except for a
>    few game genres, like flight sims, there are way more important
>    things on the agenda than scalable LOD.
>
>    Take shading.  Maybe 50% of the traffic on this list concerns
>    shading techniques.  And that's because quality of shading has huge
>    leverage over the player experience, and is still heavily
>    resource-constrained.  Whereas LOD generally isn't making or
>    breaking anybody's game nowadays, due to faster hardware.  So
>    anything (e.g. LOD) that takes developer time and makes shading
>    more complicated has to have an extra big payoff, over and above
>    any intrinsic benefit.



--------------------------------------------------------------------------------------------
Charles Bloom    email "cb"    http://www.cbloom.com 

RE: [Algorithms] Terrain performance comparrisons

[Jon W. <hp...@mi...>]

> continuous MMORPG with detailed terrain.  What kind of problems do I =
have=20
> (that are directly related to the large world and desire to have far =
view=20
> distances and seamless movement) ?
>=20
> 1) seamless paging/streaming of lots of data
> 2) LOD/locality of network data
> 3) network prediction and lag compensation for many/far entities
> 4) server distribution and seamless links
> 5) LOD for all the game logic in the distance
> 6) LOD for all the characters, plants, shaders, etc.
> 7) LOD for the client-side physics engine
> 8) LOD for the terrain rendering

You forgot:

0) PC hardware "compatibility"

Cheers,

				/ h+

RE: [Algorithms] Terrain performance comparrisons

[Jon W. <hp...@mi...>]

> what are the major contending algorithms for modern systems?
> the three I've decided to try out are ChunkedLOD, Roam 2.0 and=20
> Geomipmapping.
> Are there any others which have feature sets drastically=20
> different from these=20
> three?

You could look into the article series on general geometry LOD which=20
Jon Blow just finished in Game Developer (it's a five-part series).

> If I want to maintain backwards compatibility with older systems=20
> should I use=20
> an older algorithm (original roam) or do the newer ones still=20
> work even if you=20
> can't assume there's a fast GPU?

In the end, you have to transform the verts somewhere. The difference=20
between algorithms is in their assumptions about what the cost of a=20
vertex is, and what the appropriate vertex count vs work trade-off is.=20
Still, touching memory means touching memory; examine a million verts=20
to find the optimal 7000 might be much slower than examining a few=20
tree nodes and drawing 9000. YMMV.

Cheers,

			/ h+

Re: [Algorithms] Terrain performance comparisons

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

Jonathan Blow wrote:

>My recent email about software complexity issues touches on the
>subject that Luis brought up about algorithm adoption ostensibly
>being a social issue.  I think there are definite technical issues here
>as well, so I wanted to bring those up.
>

Naturally.  Social limitations don't imply that technical issues don't 
exist.

>Luis Ackerman wrote:
>  
>

And now I'm being mischaracterized ^_^
No hard feelings.

>It's important to remember this: ideally, we don't want to LOD at all.
>Any graphics LOD indicates a mismatch between what is being
>rendered, and what actually exists, in the game world.  That mismatch
>*will* show up sometimes in gameplay.  If the mismatch causes
>big enough problems, which it often will regardless of the algorithm
>in use, we need to deal with those.
>  
>

Well, pulling ideals out of a hat doesn't solve anything.  Ideally I'd 
like an infinitely fast computer.  Lacking that, LOD is a practical 
approach to the problems at hand.  It does have drawbacks, and 
workarounds, but like anything there's a cost/benefit decision.

This leads to an interesting point though, which is that the triangle 
isn't a perfect graphics primitive and we're pretty rapidly reaching the 
point where they become a big bottleneck.  You can draw your own 
conclusions about what future non-triangle-centric systems will do, but 
I think all the approaches that scale well will tend to do LOD under the 
hood, pretty much for free.

>Right, and this is my big problem with CLOD.    CLOD 
>algorithms spend all this software complexity -- a finite and highly-contended
>resource, as mentioned earlier -- and what do we get?  In such an algorihtm's
>raw form, we get a guarantee that the spatial error for every vertex on the
>screen is bounded.  Okay; it's unclear whether that's worth all the effort, 
>but at least it's something solid that can be said about what these algorithms 
>achieve.  But wait!  In order for the system to run smoothly, we need 
>to give up this guarantee.  So now what can we say about the
>algorithm's achievement?  It "generally makes it so that vertices are within
>the error threshold most of the time as long as you're not stressing the
>system too hard".  Is that all?  I can do that with a static mesh algorithm,
>so why all the fuss?  
>ROAM handles morphing surfaces better than static mesh LOD, but
>in those cases I can just use geomipmapping.  So I'm just not sure what
>ROAM buys me for all that effort.  That's all.  If someone convinces me
>that there is a large, clear payoff, I will happily go back to using CLOD
>algorithms.
>  
>

Cheap, fast, good - pick any 2.  This really just wraps back to the 
original discussion about what requirements you have.  Some things are 
going to be more appropriate for some problem domains.  

IMHO, the big win for CLOD is scalability, which most games just aren't 
going to take advantage of.  They could eventually though, when someone 
writes a game to escape all artificial limitations and creates an 
unbounded content domain.  Memory will remain a limiting factor, but 
scales of interaction don't have to.

>Now as people keep optimizing CLOD algorithms, they are becoming
>more like static mesh algorithms, so maybe the two will meet at some point.
>
>   -Jonathan.
>  
>

Seeing all the approaches have different deficiencies that people are 
trying to overcome, some amount of convergence can be expected.

-Lucas

Re: [Algorithms] Terrain performance comparrisons

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

I agree, you can't compare the performance of algorithms except in a 
theoretical sense (and we know how well that reflects in practice). 
 What you can compare is the performance of specific implimentations. 
 Even different implimentations of a single algorithm can have hugely 
varying speed and quality differences (as is the case with ROAM for 
example, all the way from unusable crap to better than you could have 
hoped for).  Your particular needs, goals, and preferences will 
obviously have a large impact on what you consider best.  If you could 
outline your problem domain and the constraints on your solution, 
perhaps we could help make some informed recommendations.

-Lucas


Andras Balogh wrote:

>It's very difficult to compare different terrain rendering algorithms
>objectively. Performance depends on so many things that it is very
>hard to do fair comparisons. Quality measurements are also
>troublesome, it's like comparing MP3 with Vorbis... Which one is
>better? The more people you ask, the more answers you will get.
>
>Every method has its advantages and drawbacks. You have to balance
>tradeoffs and choose wisely, depending on your requirements.
>
>Well, I know I didn't help much, but I just can't... :(
>
>
>Bandi
>
>
>Thursday, July 24, 2003, 1:38:59 PM, De Boer wrote:
>
>  
>
>>Anyone know of a paper where a number of terrain algorithms are compared
>>objectively in terms of speed/quality? Most of the time I see a paper say on
>>an extension to an algorithm and they state how much extra fps the extension
>>had on the old algorithm. Quality isn't usually even measured. But is there
>>any papers dedicated just to "comparing" terrain algorithms as objectively
>>as possible? Although opinions of "which algorithms are best" would be
>>useful I am really looking for papers with objective measurements (opinions
>>seem to vary way too much).
>>    
>>
>
>  
>
>>Here is the old original msg from 2000 if you don't remember it:
>>    
>>
>
>  
>
>>>Concerning the speed of terrain LOD algorithms:
>>>      
>>>
>
>  
>
>>>If i made performance claims on my site, people would certainly complain
>>>      
>>>
>>that the results are entire based on context (type of >dataset, amount of
>>camera motion) and that their implementation is really fast if i had only
>>tested it their way :-)
>>    
>>
>
>  
>
>>>In fact, it's even harder than that to make meaningful comparisons, since
>>>      
>>>
>>some algorithms (e.g. LK, TV) enforce a global error >metric, while others
>>(ROAM, SM) enforce a polygon count target. The first kind will have
>>framerates that will vary widely, while >the second will produce relatively
>>stable performance.
>>    
>>
>
>  
>
>>>A lot of the discussion on the Algorithms list has been about how many
>>>      
>>>
>>triangles/second each implementation gets through the >rendering pipeline,
>>which seems to me a rather silly metric - it's fps at a level of perceived
>>quality, NOT raw throughput, that >is the value of a LOD algorithm.
>>    
>>
>>>-Ben
>>>http://vterrain.org/
>>>      
>>>
>
>  
>
>>-Ryan De Boer
>>    
>>
>
>
>  
>