gdalgorithms-list

RE: [Algorithms] ROAM

[Jenny A. <aj...@fr...>]

Hi Paul,

Just start your search here :
www.vterrain.org

Alexandre JENNY
WWW.LE-GEO.COM

-----Message d'origine-----
De : Paul Adams [mailto:fr...@fu...]
Envoyé : mardi 8 août 2000 10:58
À : gda...@li...
Objet : [Algorithms] ROAM


Hi all,

I just checked out the image of the day on www.flipcode.com that showed a
landscape using the ROAM algorithm.  The landscape does look nice so I
decided I may move my arse and look into landscape rendering which I
promised myself I would do for some time now :-)

Just wondered if there are any pointers to good documentation about ROAM or
other such algorithms for LOD on landscapes...  I guess there are plenty but
any ones that stick out from the rest ?

(appolagies,  i am new to the list :)

Thanks

Paul.







_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Re: [Algorithms] ROAM

[Martin G. <bz...@wi...>]

Check out Ben Discoe's www.vterrain.org - excellent links, tutorials, etc.

-----Original Message-----
From: Paul Adams <fr...@fu...>
To: gda...@li...
<gda...@li...>
Date: 08 Àâãóñò 2000 ã. 12:09
Subject: [Algorithms] ROAM


>Hi all,
>
>I just checked out the image of the day on www.flipcode.com that showed a
>landscape using the ROAM algorithm.  The landscape does look nice so I
>decided I may move my arse and look into landscape rendering which I
>promised myself I would do for some time now :-)
>
>Just wondered if there are any pointers to good documentation about ROAM or
>other such algorithms for LOD on landscapes...  I guess there are plenty but
>any ones that stick out from the rest ?
>
>(appolagies,  i am new to the list :)
>
>Thanks
>
>Paul.
>
>
>
>
>
>
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>

RE: [Algorithms] ROAM

[Andrew G. <And...@ho...>]

I found an article on Gamasutra a great help when I was first writing my own
implementation a while back;

http://www.gamasutra.com/features/20000403/turner_pfv.htm

It contains a pretty straightforward explanation and sample code. Step
through the code and draw what it's doing to the landscape and patches on
paper, you'll pick it up pretty quickly.

Andrew Grant -
HotHouse Creations



> 
> 
> Hi all,
> 
> I just checked out the image of the day on www.flipcode.com 
> that showed a
> landscape using the ROAM algorithm.  The landscape does look nice so I
> decided I may move my arse and look into landscape rendering which I
> promised myself I would do for some time now :-)
> 
> Just wondered if there are any pointers to good documentation 
> about ROAM or
> other such algorithms for LOD on landscapes...  I guess there 
> are plenty but
> any ones that stick out from the rest ?
> 
> (appolagies,  i am new to the list :)
> 
> Thanks
> 
> Paul.
> 

Re: [Algorithms] ROAM

[Paul A. <fr...@fu...>]

RE: [Algorithms] ROAMThanks all..

Paul..
  ----- Original Message -----=20
  From: Andrew Grant=20
  To: 'gda...@li...'=20
  Sent: Tuesday, August 08, 2000 10:25 AM
  Subject: RE: [Algorithms] ROAM


  I found an article on Gamasutra a great help when I was first writing =
my own implementation a while back;=20

  http://www.gamasutra.com/features/20000403/turner_pfv.htm=20

  It contains a pretty straightforward explanation and sample code. Step =
through the code and draw what it's doing to the landscape and patches =
on paper, you'll pick it up pretty quickly.

  Andrew Grant -=20
  HotHouse Creations=20




  >=20
  >=20
  > Hi all,=20
  >=20
  > I just checked out the image of the day on www.flipcode.com=20
  > that showed a=20
  > landscape using the ROAM algorithm.  The landscape does look nice so =
I=20
  > decided I may move my arse and look into landscape rendering which I =

  > promised myself I would do for some time now :-)=20
  >=20
  > Just wondered if there are any pointers to good documentation=20
  > about ROAM or=20
  > other such algorithms for LOD on landscapes...  I guess there=20
  > are plenty but=20
  > any ones that stick out from the rest ?=20
  >=20
  > (appolagies,  i am new to the list :)=20
  >=20
  > Thanks=20
  >=20
  > Paul.=20
  >=20

RE: [Algorithms] ROAM

[Discoe, B. <ben...@in...>]

> From: Johan Hammes [mailto:jh...@mw...]
> Has anyone seen a decent implementation of ROAM?

That depends on whether you mean implementations of the *full* ROAM
algorithm.  There have been many variations, the most popular of which omit
the split-and-merge queues (split-only ROAM), which tends to be a win in
both code complexity and speed.

To the best of my knowledge, there has not been a fast, publicly available
*full* implementation.

Split-only, on the other hand, has plenty very fast implementations, as
listed at http://vterrain.org/LOD/implementations.html

..including the overall fastest known CLOD implementation to date,
SMTerrain, which is a split-only ROAM approach.

> What is the amount of cpu time used by the algorithm per frame
> for a standard scene with about 3000 triangles in the view?

I'm afraid it's not as simple as that.  The answer will vary by CPU speed,
memory speed, memory latency, bus speed, card speed, camera location, camera
movement, and cache size!  Believe me, i have done tests in regards to most
of these factors, and an algorithm which uses negligible time in one
configuration can significantly affect framerate in another.

The best advice is: implement the application you want, use the scenery you
want, run it on the hardware you're targeting, set up some speed test based
on expected camera movement, and THEN compare speed and visual quality
between the terrain LOD algorithms you are comparing.

> The first publication on roam was horribly slow

Well a publication is just words, surely it was not slow, except it was hard
to read :)
If you mean the first full ROAM implementations, yes they there were
reportedly generally slow by those who did them.

-Ben
http://vterrain.org/

Re: [Algorithms] ROAM

[Johan H. <jh...@mw...>]

> > The first publication on roam was horribly slow
>
> Well a publication is just words, surely it was not slow, except it was
hard
> to read :)
> If you mean the first full ROAM implementations, yes they there were
> reportedly generally slow by those who did them.

Very funny (I actually laughed a lot)
No, I mean the first publication that I read on ROAM that also stated CPU
time to compute. This was in the order of 25ms per frame on a  PIII
computer. The point is that there are algorithms out there that runs at
about 0.4ms per frame (with about 7000 triangles in the list), and I was
wondering whether the original full ROAM was so horribly slow and badly
implimented, and whether someone has managed an implimentation that will run
in less than 1ms on a PIII,
or whether it is a sub optimal approach to start off with and will never run
this fast?

These times are obviously approximate, and refers only to the time spent in
the algorithm, not in rendering any of the triangles generated.

Johan Hammes

RE: [Algorithms] ROAM

[Tom F. <to...@mu...>]

You haven't mentioned the hybrid of geomipmapping and VIPM, i.e. you do
(non-morphing) geomipmapping, but the transitions between levels of detail
are done with VIPM, so there's less popping.

Definately search through the archives - there's been tons of wide-ranging
discussions about this. I think the current consensus is:

ROAM: excellent quality for a given number of triangles, but speed is hard
to achieve with the standard algorithm. Good for changing landscapes (i.e.
blowing up hills, etc)

ROAM meets VIPM: I'm not sure about the status or details on this - it's the
ROAM principles, but with far more precalculation. Sounds promising.

Geomipmapping: very fast, works with changing landscape with minor work,
otherwise data can be completely static.

Geomipmapping with VIPM: transitions between LOD levels are done with VIPM,
rather than just swapping in different index blocks. Reduced popping means
fewer triangles can be used for equivalent quality (or higher quality for
the same tri count). Works with changing landscape.

Quadtree VIPM: similar to geomipmapping with VIPM, but each chunk in the
landscape has custom tesselation, rather than the generic geomipmapping one.
Seams are fixed up with flanges or ribbons (flanges are usually quicker), so
there's no changing LoD according to what a block's neighbour does, which
can improve speed. Custom tesselation means even fewer tris / more detail
for given tri budget, but lots of precalculation required, and each area of
landscape has its own VIPM index list, so there's a lot more memory. Does
not work well with changing landscape, because the geometry affects which
tesselations are used.

And finally: just draw everything. Works just fine for games with a low
viewpoint that don't need to draw very far, e.g. FPS games.


Did I forget anyone?


Tom Forsyth - purely hypothetical Muckyfoot bloke.

This email is the product of your deranged imagination,
and does not in any way imply existence of the author.

> -----Original Message-----
> From: Trent Polack [mailto:tr...@vo...]
> Sent: 30 July 2002 02:40
> To: gda...@li...
> Subject: [Algorithms] ROAM
> 
> 
> I was just sitting here, in the middle of coding the ROAM 
> implementation for
> my "Focus on 3D Terrain Programming" book for Premier Press. 
> Now, the book
> is all about terrain, but focuses more on its applications to game
> development than anything else... Which leads me into my 
> question. I have
> three main algorithm chapters in the book:
> 
> Chapter 5: Geomipmapping. The algorithm is very GPU-friendly, 
> simple to
> implement, and just generally a very good CLOD algorithm.
> 
> Chapter 6: Stefan Roetgger's Quadtree algorithm. While it is far more
> CPU-intensive than geomipmapping, this algorithm is a bit 
> more balanced and
> "powerful" than geomipmapping. What it lacks in speed, it 
> makes up for in
> mesh consistancy and detail.
> 
> Now, chapter 7 is where the dilemma is. I could teach the 
> reader all about
> ROAM, but I'm wondering if I should really bother. Its a 
> great algorithm,
> and I do not doubt its power, but I really do think its 
> lacking in speed, at
> least compared to the previously mentioned algorithms.
> 
> Now, what I was thinking, was that in Chapter 7 I could write 
> about several
> different approaches to making a very fast and stable terrain 
> engine, such
> as some variations on the geomipmapping algorithm discussed 
> in Chapter 5.
> But, I really need some opinions here (Plus, I've been writing almost
> constantly for the last three days, and my thought process seems to be
> rather broken.), what do you guys think?
> 
> -------
> Trent Polack
> tr...@vo...
> Thought of a lifetime: "NARF!"
> 
> 
> 
> 
> -------------------------------------------------------
> This sf.net email is sponsored by: Dice - The leading online job board
> for high-tech professionals. Search and apply for tech jobs today!
> http://seeker.dice.com/seeker.epl?rel_code=31
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_id=6188
> 

Re: [Algorithms] ROAM

[Mark D. <duc...@ll...>]

Tom Forsyth wrote:
> ROAM: excellent quality for a given number of triangles, but speed is hard
> to achieve with the standard algorithm. Good for changing landscapes (i.e.
> blowing up hills, etc)
> 

The main ideas of ROAM continue to be relevant:
  - split+merge queue
  - do as much work per frame as you have time for
  - happens in optimal order
  - fastest frustum culling around
  - flexibility to do lots of things with the split+merge priorities
    - line-of-sight correction
    - correct object placement (no floating or interpenetration)
    - easy silhouette enhancement
  - fast updates for dynamic terrain (as Tom mentions)
  - excellent frame-to-frame coherence (especially important for cached
    chunk implementations, see next item)

> ROAM meets VIPM: I'm not sure about the status or details on this - it's the
> ROAM principles, but with far more precalculation. Sounds promising.

Simplest case: use an AGP chunk of 256 uniform-size triangles to draw each
"ROAM triangle".  I've got free source that gets 40M tri/sec draw rates
right now with a fractal terrain created on the fly using this.

Adaptive case: use adaptive chunks, precomputed (see Alex Pomeranz's thesis
at www.cognigraph.com/ROAM_homepage) or cached (see upcoming IEEE Vis paper
by Joshua Levenberg).  The cache entries are static until replaced.
Both have research implementations that are not avaiable yet.  Thatcher
Ulrich's chunk demo is very similar in flavor in terms of the way chunks
are built, but the way boundaries are handled are much simpler with
the ROAM-style approach (there are no special fix-ups on the boundary
at all).

Next fancier case: sliding window "VIPM" ideas for the chunks.  Allows
"fractional splits" of a ROAM triangle patch.  Not implemented yet
as far as I know.  Seems straightforward, but a lot of implementation
work, and perhaps not that big an improvement (see next point).

My sense is that at this point the triangles are getting really small
on current graphics hardware, and that adaptivity within a chunk is
becoming less important.  For my 40Mtri/sec code, I just make a single
strip pattern hand-tuned to maximize vertex cache coherence and
minimize degenerate triangles.  The critical inner loops are very
fast compared to on-the-fly adaptive techniques with chunk caching.
So for now I'm sticking with uniform triangle sizes within a tri patch,
and keeping the CPU/memory-intensive adaptivity in the splitting and
merging of tri patches.

> And finally: just draw everything. Works just fine for games with a low
> viewpoint that don't need to draw very far, e.g. FPS games.
> 

Only if the number of triangles total is small enough of course.
Personally the terrain in all the games I've been playing lately
is really crude compared to what is possible at high frame rates.

Trent Polack wrote:
> > Now, chapter 7 is where the dilemma is. I could teach the
> > reader all about
> > ROAM, but I'm wondering if I should really bother. Its a
> > great algorithm,
> > and I do not doubt its power, but I really do think its
> > lacking in speed, at
> > least compared to the previously mentioned algorithms.

ROAM speed depends heavily on the details of the implementation.
Is 40Mtri/sec fast enough?  Just put AGP "patches" per ROAM tri.
I'll give my linux+nvidia code-in-progress to anyone who asks so
you can see this yourself.  You get a few thousand patches displayed
per frame, so you are really back in the situation we were in in 1996
when we first came up with ROAM (CPU dealing with 3000-6000 tris),
except now each "triangle" is a 256-triangle chunk, and ROAM is
*more* approprate than before since it optimizes the limited budget
of chunk-cache updates available per frame.

Also, there are lots of enhancements/variations on ROAM floating out
there, lots of implementation notes, and more coming out all the
time.

Overall I'd say the nicest aspect of ROAM, in hindsight, is that
it is really easy to "get" the idea of a minimal ROAM implementation
and code it up in a day, and then gradually add more and more
optimizations as your performance analysis dictates.  Other techniques
generally require a big ramp-up time before you get much of
anything going, at least for the scalable algorithms out there.
This makes it very attractive for anyone learning how to make
a display system for large terrains for the first time.

Cheers,

--Mark D.

Re: [Algorithms] ROAM

[Josh <jos...@pa...>]

I'd just like to announce that the code for my research implementation
is now available at http://www.technomagi.com/josh/vis2002/ .

I'm sure more optimizations are possible (I'm not using tri-strips,
for instance).  I get about 18M tri/sec on a laptop GeForce 4.

Someone already sent me some changes to get it working with Linux
(not very difficult), but I haven't had time to verify and incorporate
them yet (I'm very busy trying to finish my thesis these days).

Josh Levenberg
(please cc: jo...@te... on replies since I don't regularly read 
this list)

Mark Duchaineau wrote (July 30th):
* SNIP*
> Simplest case: use an AGP chunk of 256 uniform-size triangles to draw each
> "ROAM triangle".  I've got free source that gets 40M tri/sec draw rates
> right now with a fractal terrain created on the fly using this.
> 
> Adaptive case: use adaptive chunks, precomputed (see Alex Pomeranz's thesis
> at www.cognigraph.com/ROAM_homepage) or cached (see upcoming IEEE Vis paper
> by Joshua Levenberg).  The cache entries are static until replaced.
> Both have research implementations that are not avaiable yet.  Thatcher
> Ulrich's chunk demo is very similar in flavor in terms of the way chunks
> are built, but the way boundaries are handled are much simpler with
> the ROAM-style approach (there are no special fix-ups on the boundary
> at all).
* SNIP *

[Algorithms] Re: ROAM

[Eric G. <eg...@gl...>]

> Now, chapter 7 is where the dilemma is. I could teach the reader all about
> ROAM, but I'm wondering if I should really bother. Its a great algorithm,
> and I do not doubt its power, but I really do think its lacking in speed, at
> least compared to the previously mentioned algorithms.

I second previous replies on the ROAM algorithm (and family, since there are
so many variants depending on how far the implementation goes, its goals, etc.).
It is still quite valid and IMO will remain so.
Geomipmapping can only go so far when terrain and visible range get large,
and pure quadtree is CPU bound.

For illustration, the implementation I've been playing with uses chunks in a
similar fashion to Seumas McNally Treadmarks / split-only ROAM, with infinite
terrain, but either brute-force rendering (for chunks close to the observer) 
or ROAM patches ("far" chunks). This allows high-triangle count for the 
short-range (ala geomipmapping), while still allowing long visibility range.
Far chunks don't need many triangles, meaning that even a basic ROAM
implementation is already very effective (drastic triangle count reduction, 
"optimal" tesselation ie. quality, limited memory use,  simplified screen-space error 
computation etc.). 
Seams are solved by simply force-splitting along brute-force/ROAM chunks edges
(simple and fast, only adds a minimum of triangles).
During render, the brute-force chunks are sent to the graphics hardware first,
which allows some GPU/CPU parallelization of the ROAM computation 
while automagically "sorting" the chunks front-to-back (good for early Z tests).
(Delphi source code available at http:\\glscene.org, part of the library)

IMHO you cannot expose terrain rendering without explaining at least the most
basic forms of ROAM, especially if the reader wants to leave the short-range
terrain rendering area later on (flight-sims f.i.). 
You often have to make choices and trade-ofs, but knowing the full range of tools
available helps in making those choices, by allowing to pick or combine whatever
suits your own specific case.

Eric Grange
eg...@gl...

RE: [Algorithms] ROAM

[Tom F. <to...@mu...>]

I'd still like to see it compared with CPU-light schemes like VIPM and even
the really simple one of geomipmapping. Both of these put the load almost
entirely on the video card, which is essential if you want to actually have
an application, rather than just fly around a terrain.

I'm not saying they're necessarily better (OK, actually I am :-), I'd just
like to see all the options compared side-by-side.


Tom Forsyth - Muckyfoot bloke and Microsoft MVP.

This email is the product of your deranged imagination,
and does not in any way imply existence of the author.

> -----Original Message-----
> From: Josh [mailto:jos...@pa...]
> Sent: 28 November 2002 04:56
> To: gda...@li...
> Cc: jo...@te...
> Subject: Re: [Algorithms] ROAM
> 
> 
> I'd just like to announce that the code for my research implementation
> is now available at http://www.technomagi.com/josh/vis2002/ .
> 
> I'm sure more optimizations are possible (I'm not using tri-strips,
> for instance).  I get about 18M tri/sec on a laptop GeForce 4.
> 
> Someone already sent me some changes to get it working with Linux
> (not very difficult), but I haven't had time to verify and incorporate
> them yet (I'm very busy trying to finish my thesis these days).
> 
> Josh Levenberg
> (please cc: jo...@te... on replies since I don't 
> regularly read 
> this list)
> 
> Mark Duchaineau wrote (July 30th):
> * SNIP*
> > Simplest case: use an AGP chunk of 256 uniform-size 
> triangles to draw each
> > "ROAM triangle".  I've got free source that gets 40M 
> tri/sec draw rates
> > right now with a fractal terrain created on the fly using this.
> > 
> > Adaptive case: use adaptive chunks, precomputed (see Alex 
> Pomeranz's thesis
> > at www.cognigraph.com/ROAM_homepage) or cached (see 
> upcoming IEEE Vis paper
> > by Joshua Levenberg).  The cache entries are static until replaced.
> > Both have research implementations that are not avaiable 
> yet.  Thatcher
> > Ulrich's chunk demo is very similar in flavor in terms of 
> the way chunks
> > are built, but the way boundaries are handled are much simpler with
> > the ROAM-style approach (there are no special fix-ups on 
> the boundary
> > at all).
> * SNIP *
> 
> 
> 
> -------------------------------------------------------
> This SF.net email is sponsored by: Get the new Palm Tungsten T 
> handheld. Power & Color in a compact size! 
> http://ads.sourceforge.net/cgi-bin/redirect.pl?palm0002en
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_id=6188
> 

RE: [Algorithms] ROAM

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

You can compare to Thatcher's chunk-lod-demo :

http://sourceforge.net/project/showfiles.php?group_id=31763&release_id=103643

At 12:44 PM 11/28/2002 -0000, you wrote:
>I'd still like to see it compared with CPU-light schemes like VIPM and even
>the really simple one of geomipmapping. Both of these put the load almost
>entirely on the video card, which is essential if you want to actually have
>an application, rather than just fly around a terrain.
>
-------------------------------------------------------
Charles Bloom    cb...@cb...    http://www.cbloom.com

RE: [Algorithms] ROAM

[Tom F. <to...@mu...>]

True, but for a real apples-to-apples comparison it probably needs to be in
the same framework/application. Also, Thatcher's chunk-lod is yet _another_
separate case because he's doing vertex morphing as well, which again pushes
CPU time up but also increases quality-per-triangle.

So that's three methods Josh missed - any more want to pile in while we're
ripping him a new one :-)


Tom Forsyth - Muckyfoot bloke and Microsoft MVP.

This email is the product of your deranged imagination,
and does not in any way imply existence of the author.

> -----Original Message-----
> From: Charles Bloom [mailto:cb...@cb...]
> Sent: 28 November 2002 16:40
> To: gda...@li...
> Subject: RE: [Algorithms] ROAM
> 
> 
> 
> You can compare to Thatcher's chunk-lod-demo :
> 
> http://sourceforge.net/project/showfiles.php?group_id=31763&re
> lease_id=103643
> 
> At 12:44 PM 11/28/2002 -0000, you wrote:
> >I'd still like to see it compared with CPU-light schemes 
> like VIPM and even
> >the really simple one of geomipmapping. Both of these put 
> the load almost
> >entirely on the video card, which is essential if you want 
> to actually have
> >an application, rather than just fly around a terrain.
> >
> -------------------------------------------------------
> Charles Bloom    cb...@cb...    http://www.cbloom.com

RE: [Algorithms] ROAM

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

At 04:57 PM 11/28/2002 -0000, Tom Forsyth wrote:
>True, but for a real apples-to-apples comparison it probably needs to be in
>the same framework/application. Also, Thatcher's chunk-lod is yet _another_
>separate case because he's doing vertex morphing as well, which again pushes
>CPU time up but also increases quality-per-triangle.

The morph can be done in a vshader at the cost of more bandwidth.
Anyway, with terrain, the problem is not actually rendering, it's
managing the huge amount of data needed.  You could render the entire
earth at apparent 1-pixel screenspace error - the speed of the
algorithms is not the problem - it's the fact that the dataset is
collosal.

Clever paging and streaming are much harder than the rendering bits.

-------------------------------------------------------
Charles Bloom    cb...@cb...    http://www.cbloom.com

Re: [Algorithms] ROAM

[Conor S. <cs...@tp...>]

Don't forget brute force + bulk culling (maybe with a "get rid of stupid
triangles" pre process). If your view distance isn't that long, then it is
very much an option.

Not only that, it looks great, never pops and you never have to worry about
the differences in display in multiplayer (which is a concern which has been
voiced on this list in the past, iirc).

Conor Stokes

> True, but for a real apples-to-apples comparison it probably needs to be
in
> the same framework/application. Also, Thatcher's chunk-lod is yet
_another_
> separate case because he's doing vertex morphing as well, which again
pushes
> CPU time up but also increases quality-per-triangle.
>
> So that's three methods Josh missed - any more want to pile in while we're
> ripping him a new one :-)
>
>
> Tom Forsyth - Muckyfoot bloke and Microsoft MVP.
>
> This email is the product of your deranged imagination,
> and does not in any way imply existence of the author.
>
> > -----Original Message-----
> > From: Charles Bloom [mailto:cb...@cb...]
> > Sent: 28 November 2002 16:40
> > To: gda...@li...
> > Subject: RE: [Algorithms] ROAM
> >
> >
> >
> > You can compare to Thatcher's chunk-lod-demo :
> >
> > http://sourceforge.net/project/showfiles.php?group_id=31763&re
> > lease_id=103643
> >
> > At 12:44 PM 11/28/2002 -0000, you wrote:
> > >I'd still like to see it compared with CPU-light schemes
> > like VIPM and even
> > >the really simple one of geomipmapping. Both of these put
> > the load almost
> > >entirely on the video card, which is essential if you want
> > to actually have
> > >an application, rather than just fly around a terrain.
> > >
> > -------------------------------------------------------
> > Charles Bloom    cb...@cb...    http://www.cbloom.com
>
>
>
>
> -------------------------------------------------------
> This SF.net email is sponsored by: Get the new Palm Tungsten T
> handheld. Power & Color in a compact size!
> http://ads.sourceforge.net/cgi-bin/redirect.pl?palm0002en
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_id=6188
>

RE: [Algorithms] ROAM

[Tom F. <to...@mu...>]

Four! Four techniques. Ah ah ah ah ah <thunder+lightning>

(geomipmapping, VIPM, chunks with CPU morph, chunks with GPU morph)


Agreed that in real "large world" apps the paging in and out of data is also
a very interesting problem. Though I can't help thinking the basics of
mipmapping (and swizzling, so that a square region is a single linear
access) heightfields should solve half the problem, and a good async-loading
streamer should solve the other half. Does it need to be any fancier?


Tom Forsyth - Muckyfoot bloke and Microsoft MVP.

This email is the product of your deranged imagination,
and does not in any way imply existence of the author.

> -----Original Message-----
> From: Charles Bloom [mailto:cb...@cb...]
> Sent: 28 November 2002 21:09
> To: gda...@li...
> Cc: jo...@te...
> Subject: RE: [Algorithms] ROAM
> 
> 
> 
> At 04:57 PM 11/28/2002 -0000, Tom Forsyth wrote:
> >True, but for a real apples-to-apples comparison it probably 
> needs to be in
> >the same framework/application. Also, Thatcher's chunk-lod 
> is yet _another_
> >separate case because he's doing vertex morphing as well, 
> which again pushes
> >CPU time up but also increases quality-per-triangle.
> 
> The morph can be done in a vshader at the cost of more bandwidth.
> Anyway, with terrain, the problem is not actually rendering, it's
> managing the huge amount of data needed.  You could render the entire
> earth at apparent 1-pixel screenspace error - the speed of the
> algorithms is not the problem - it's the fact that the dataset is
> collosal.
> 
> Clever paging and streaming are much harder than the rendering bits.
> 
> -------------------------------------------------------
> Charles Bloom    cb...@cb...    http://www.cbloom.com

Re: [Algorithms] ROAM

[Pierre T. <p.t...@wa...>]

> Agreed that in real "large world" apps the paging in and out of data is
also
> a very interesting problem. Though I can't help thinking the basics of
> mipmapping (and swizzling, so that a square region is a single linear
> access) heightfields should solve half the problem, and a good
async-loading
> streamer should solve the other half. Does it need to be any fancier?

There was that thing called "clipmaps" in SIG97... IIRC the texture was like
40 million * 20 million texels. Nice :)

Pierre

Re: [Algorithms] ROAM

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

On Nov 29, 2002 at 10:28 -0000, Tom Forsyth wrote:
> Four! Four techniques. Ah ah ah ah ah <thunder+lightning>
> 
> (geomipmapping, VIPM, chunks with CPU morph, chunks with GPU morph)
> 
> 
> Agreed that in real "large world" apps the paging in and out of data
> is also a very interesting problem. Though I can't help thinking the
> basics of mipmapping (and swizzling, so that a square region is a
> single linear access) heightfields should solve half the problem,
> and a good async-loading streamer should solve the other half. Does
> it need to be any fancier?

No, I don't think so.  There are also some tradeoffs with whether and
how to compress the data.

The point is that with modern hardware, the details of HD and RAM
storage & paging are crucially important, since any reasonable LOD
algorithm can pretty quickly exhaust the data you can fit in RAM.

-- 
Thatcher Ulrich
http://tulrich.com

RE: [Algorithms] ROAM

[Tom F. <to...@mu...>]

Virtual texturing is a much cooler technology than clipmaps though. It's got
finer granularity, is (oddly) easier to implement, and has a wider
application.

Now we just have to wait for more than one IHV to implement it. It's not the
new lensflare, but it is the new bumpmapping, in that it's cool tech,
everyone agrees it's cool tech, but it'll take ten years after it was shown
to work to get mainstream use :-)


Tom Forsyth - Muckyfoot bloke and Microsoft MVP.

This email is the product of your deranged imagination,
and does not in any way imply existence of the author.

> -----Original Message-----
> From: Pierre Terdiman [mailto:p.t...@wa...]
> Sent: 29 November 2002 10:54
> To: gda...@li...
> Subject: Re: [Algorithms] ROAM
> 
> 
> > Agreed that in real "large world" apps the paging in and 
> out of data is
> also
> > a very interesting problem. Though I can't help thinking 
> the basics of
> > mipmapping (and swizzling, so that a square region is a 
> single linear
> > access) heightfields should solve half the problem, and a good
> async-loading
> > streamer should solve the other half. Does it need to be 
> any fancier?
> 
> There was that thing called "clipmaps" in SIG97... IIRC the 
> texture was like
> 40 million * 20 million texels. Nice :)
> 
> Pierre

Re: [Algorithms] ROAM

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

On Nov 29, 2002 at 11:07 -0000, Tom Forsyth wrote:
> From: Pierre Terdiman [mailto:p.t...@wa...]
> > There was that thing called "clipmaps" in SIG97... IIRC the
> > texture was like 40 million * 20 million texels. Nice :)
> 
> Virtual texturing is a much cooler technology than clipmaps
> though. It's got finer granularity, is (oddly) easier to implement,
> and has a wider application.
> 
> Now we just have to wait for more than one IHV to implement it. It's
> not the new lensflare, but it is the new bumpmapping, in that it's
> cool tech, everyone agrees it's cool tech, but it'll take ten years
> after it was shown to work to get mainstream use :-)

If you can't wait that long, use quadtree tiling :).  There's an
example in the chunked LOD demo.  It's a coarse-grained method to
solve the same problem without using any hardware extensions.  Public
domain code at the usual place:

http://sourceforge.net/projects/tu-testbed

One interesting advantage of doing it this way is that I could use
JPEG compression on the textures, so a 32K x 32K texture that normally
would have consumed several GB uncompressed, or 512MB (using
conventional hardware compression @ 4 bits/texel), instead took
~150MB.  By the same token, it's a good framework for doing some
procedural stuff.  On the other hand there's the usual time/space
tradeoff to deal with decompression.

-- 
Thatcher Ulrich
http://tulrich.com