Re: [Algorithms] Terrain performance comparisons

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

I recieved Jon's second comment immediately after sending my reply. 
 Funny that.

Jonathan Blow wrote:

[snip]

>So there is a dependency between the frame time and the effectiveness
>of all frame-coherent algorithms.  If there is a hiccup that causes one
>frame to go more slowly, the next frame is going to suffer and go
>more slowly as well (and this will keep propagating, through n frames).
>In the worst case, your dependency is so strong that the frame after
>the glitch is even *slower* than the glitch frame, in which case you
>get a sort of downward spiral effect and your frame rate plummets
>for a while.  
>
>This is pretty severe though, and much more common is just that
>these dependencies react to small changes in your frame rate, amplifying
>them.  So the upshot is, you increase the variance of your frame rate.
>That is still a very bad thing, because we like level, solid-feeling frame
>rates.  Frame-coherent algorithms, by definition, work against that.
>
>
>In general, I characterize frame-coherent algorithms as having
>"interactive volatility" -- because of the realtime nature of the sim, they
>behave badly.  Whereas for something like an offline batch renderer,
>they're fine; there is no constraint between realtime dt and simulation
>dt, so frame coherent algorithms are a 100% win there.  And that's
>the area in which the tradition of frame-coherent stuff arose: offline
>simulation and rendering, back before we had computers that would
>even do this stuff realtime.  But the problem is that people working
>on new algorithms today follow in this blind tradition of "frame 
>coherence is 100% good".  In fact it's one of the first weapons they
>pull from their holster when coming up with a new algorithm to do
>whatever.  And that's a bad thing.
>  
>

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:

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


If you need framerate stability, that's no reason to ditch coherence 
altogether.  The incremental approach can still be a big win.  Some of 
Mark D.'s more recent 2.0 flavor implimentations don't even update all 
priorities every frame (in addition to queuing pending mesh edits, 
client-server update style), so the queue updates are themselves queued. 
 It makes for a tight pipeline, and really it's really slick.  

-Lucas