plib-devel

[Plib-devel] ROAM for plib

[Sam S. <sa...@sp...>]

Hi,

There's a good article on www.gamasutra.com on Adaptive LOD terrian using
ROAM.  Up until now my program has been using a naff quadtree implementation
written by me, and I'm convinced enough to move to this implementation.

I'm almost certainly going to move my project over to SSG (since it doesn't
use any Scene graph at all at the moment).

So I'm thinking that I could rework ROAM landscape's into the SSG API as a
couple of extra classes.  Would this be useful, or do you want this sort of
extra complexity kept out of it?

Sam

Re: [Plib-devel] ROAM for plib

[Steve B. <sjb...@ai...>]

Sam Stickland wrote:

> There's a good article on www.gamasutra.com on Adaptive LOD terrian using
> ROAM.  Up until now my program has been using a naff quadtree implementation
> written by me, and I'm convinced enough to move to this implementation.
> 
> I'm almost certainly going to move my project over to SSG (since it doesn't
> use any Scene graph at all at the moment).
> 
> So I'm thinking that I could rework ROAM landscape's into the SSG API as a
> couple of extra classes.  Would this be useful, or do you want this sort of
> extra complexity kept out of it?

I don't think it would be inappropriate to write a ROAM node for SSG.

I agree that it seems like a rather higher level feature than SSG would
normally implement - but it's a feature that would be VERY hard to implement
using only the existing SSG API - and it's popular enough to warrant being
something that SSG should not prohibit.

I havn't played much with ROAM - but the general wisdom seems to be
that implementing the entire algorithm is counter-productive - something
about one of the optimisations that - erm - pessimises.

Anyway - I think it's not a bad idea - but to steal an acronym from the
PPE group:  NIV12.  (Not In Version 1.2)

-- 
Steve Baker                  http://web2.airmail.net/sjbaker1
sjb...@ai... (home)  http://www.woodsoup.org/~sbaker
sj...@ht...      (work)

Re: [Plib-devel] ROAM for plib

[Sam S. <sa...@fp...>]

Hi,

Steve Baker wrote:

> I don't think it would be inappropriate to write a ROAM node for SSG.

Cool.

> I agree that it seems like a rather higher level feature than SSG would
> normally implement - but it's a feature that would be VERY hard to
implement
> using only the existing SSG API - and it's popular enough to warrant being
> something that SSG should not prohibit.
>
> I havn't played much with ROAM - but the general wisdom seems to be
> that implementing the entire algorithm is counter-productive - something
> about one of the optimisations that - erm - pessimises.

Yes.  I think you're refering to that fact that the original ROAM paper uses
a metric based on nested world- space bounds to work out the visible error
in the grid.  The gamasutra implementation uses a variance tree to do this
instead (as does Seumas McNally's Treadmarks's engine), which is a LOT
quicker :)

You can set up the visible error you wish to allow in different ways to do
some clever stuff.  The default implementation increases the allowed visible
error with distance (so less triangles get drawn the futher away thay are)
to implement the standard LOD for example.

But you could have some landscape features always drawn with a high LOD if
you wish - although to do this from one API will require a fair bit of
tinkering with gamasutra's ROAM engine.  I was thinking of having a second
height-map style thing that would specify error tolerance for this sort of
stuff (but that can come in the future :) ).

> Anyway - I think it's not a bad idea - but to steal an acronym from the
> PPE group:  NIV12.  (Not In Version 1.2)

Heh.. Certainly not... I do have to have a life as well.  This'll take a
week or so to do I think (including the time needed to adjust the gamasutra
implementation to use fan-strips rather than drawing lots of individual
triangles.

And then I'd like to add frame coherence to it would be would nice, and
doesn't sound that hard. (Basically instead of recalculating your triangle
mesh every frame you adjust the previous one to fit.  If it's taking to long
to do you just draw the mesh anyway - this way when there's a lot of other
stuff getting drawn (i.e.. you're in a fire-fight), the LOD of the landscape
will degrade fairly gracefully).

And at some point in the future I'd really like to adjust ROAM to work in 3D
rather than just 2D so I can add stuff like caves and tunnels to the
landscape engine, but that's a far way off at the moment.

Sam

Re: [Plib-devel] ROAM for plib

[Steve B. <sjb...@ai...>]

Sam Stickland wrote:

> And then I'd like to add frame coherence to it would be would nice, and
> doesn't sound that hard. (Basically instead of recalculating your triangle
> mesh every frame you adjust the previous one to fit.

Hmmm - but I'd still want FOV culling on the individual ROAM height grids
(there could be many of them in an application like FlightGear where terrain
is paged from disk).

If a ROAM 'object' is entirely off-screen, then the ROAM algorithm would
not be executed on that frame for that object.  I really think it's important
to work that way.

> And at some point in the future I'd really like to adjust ROAM to work in 3D
> rather than just 2D so I can add stuff like caves and tunnels to the
> landscape engine, but that's a far way off at the moment.

That would be very cool.  Sounds tricky though.

If each ROAM 'object' is independent though, you could build things like
caves by having a height grid for the floor, another (inverted) one for
the ceiling and a third for the surface of the ground above the roof
of the cave.

That's nowhere near as nice as a full 3D implementation - but it certainly
makes caves and overhangs do-able with the present algorithm.

-- 
Steve Baker                  http://web2.airmail.net/sjbaker1
sjb...@ai... (home)  http://www.woodsoup.org/~sbaker
sj...@ht...      (work)

Re: [Plib-devel] ROAM for plib

[Tom H. <to...@bi...>]

At 12:02 AM 4/6/2000 , you wrote:
>Sam Stickland wrote:
>
> > And then I'd like to add frame coherence to it would be would nice, and
> > doesn't sound that hard. (Basically instead of recalculating your triangle
> > mesh every frame you adjust the previous one to fit.
>
>Hmmm - but I'd still want FOV culling on the individual ROAM height grids
>(there could be many of them in an application like FlightGear where terrain
>is paged from disk).

This can be done.

>If a ROAM 'object' is entirely off-screen, then the ROAM algorithm would
>not be executed on that frame for that object.  I really think it's important
>to work that way.

The way you do this is you have each square section of terrain as an 
object. Each object contains two ROAM Bin-tri trees and pointers to its 4 
neighbors. After you've culled each object to the view frustum (AABB works 
great) you take a quick pass through the visible objects and check 
neighbors to see if they're visible. The pointers inside the bin-tri trees 
that point to neighbors would be set to null if neighbors are culled, and 
the pointer to the neighbor if not.

For split only engine this works great. For a frame coherent model what is 
usually done is the objects that are off the screen have their priority set 
to 0 so they are tessellated as little as possible. This is easier than 
trying to find all the neighbor pointers in the tree and set them to null. 
This adds a several hundred triangles that will be clipped by the API to 
the rendering of each frame. This is probably acceptable.

> > And at some point in the future I'd really like to adjust ROAM to work 
> in 3D
> > rather than just 2D so I can add stuff like caves and tunnels to the
> > landscape engine, but that's a far way off at the moment.
>
>That would be very cool.  Sounds tricky though.

Very much so :) If he has a cool plan for it, I'd love to hear it (although 
the algorithms list is probably a better place for it).

>If each ROAM 'object' is independent though, you could build things like
>caves by having a height grid for the floor, another (inverted) one for
>the ceiling and a third for the surface of the ground above the roof
>of the cave.

The problem is defining how the ceiling and the floor come together. I 
don't see how two height fields opposing each other can be used to make 
convincing walls in a cave, but I guess its better than nothing :) If I was 
to go with a full 3D scene I would leave height fields behind and go with 
something else (Beziers with displacement maps perhaps).

>That's nowhere near as nice as a full 3D implementation - but it certainly
>makes caves and overhangs do-able with the present algorithm.

It seems like the area where the two height fields come together would look 
"bad".

Tom