RE: [Algorithms] LOD terrain

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

> From: Thatcher Ulrich [mailto:tu...@tu...]
> 
> On Mar 01, 2001 at 02:07 -0000, Tom Forsyth wrote:
> 
> > Sorry - this was a comment on using the pre-defined index list
> > version, not on Rottgers. Though you can use a similar thing to
> > Rottgers method to force edge split amounts to agree (you perform it
> > on tiles that are bigger than 2x2 - 8x8 or something).
> > 
> > But then I prefer the "flange" method myself for fixing seams - even
> > simpler :-)
> 
> I've been mulling this one over a little.  I've always been a little
> uncomfortable with the flanges approach to crack fixing, although my
> discomfort is based on theory only, I haven't actually tried it.  It
> just seems like there would either be cases where the seams would show
> up, or you'd have to be somewhat conservative with the seams and
> possibly burn fill rate.  The idea of making a quadtree of static/VIPM
> tiles is a really appealing one though -- for decent-sized tiles, it
> should give super-speedy rendering, minimal CPU overhead, *and* truly
> scalable LOD.
> 
> I came up with a crack-filling approach I'm more comfortable with, and
> it's really just a slight variation on flanges: for non-leaf tiles,
> you have a set of edge vertices that correspond to the vertex-error
> for that tile size.  You have the possibility of matching up on any
> side with tiles that are either one size larger, or one size smaller.
> Considering the interface to the smaller neighbors, basically you know
> that they will share the current tile's edge verts, plus add in some
> more verts interspersed in between.  So, in the larger tile, you take
> all those verts and generate a mesh made of a set of *vertical*
> triangles, which bridge the gaps.  Think of it as a sort of thin
> vertical "ribbon" running around the outside edge of the tile.
> 
> The ribbon just becomes a permanent part of the tile's static
> geometry, and always gets rendered.  Where the tile interfaces with
> the same size tile or a larger tile, the ribbon is basically excess
> baggage, but where it interfaces with a smaller tile, it neatly caps
> the cracks.  The ribbon shouldn't look too bad, as long as you can
> maintain a pretty good maximum vertex error.  Basically it will always
> be smaller than your worst vertex pop, so as long as the vertex pops
> are within reason, then the ribbon shouldn't hurt any worse.
> 
> For texturing, you don't do anything special, just keep the regular
> mapping of u,v to x,z (or x,y depending which plane is horizontal);
> since the geometry is vertical, the ribbon essentially has 1-D
> texturing, but that shouldn't matter since, on screen, its geometry
> should approximate a line anyway.
> 
> For the leaf tiles, no ribbon is necessary, so if the viewer inspects
> a seam closely, she should be looking at leaf tiles and not be able to
> detect anything fishy.  The ribbon is also compatible with windowed
> VIPM; the ribbon is just invariant geometry.  There would be some
> popping of the ribbon as the tile selection changed.
> 
> Thinking about it some more, the ribbon really is just a type of
> flange; apologies if I've just belabored an obvious point :)

I didn't like to say.... No probs - typing-out-loud is good for you.

The only real difference between ribbons and flanges is the slope. One
advantage ribbons have is that their texture coords don't go outside the
original tile. Going outside it has implications for quadtree texturing (or
indeed any texturing). So ribbons are certainly simpler. If they don't look
bad, cool (need to experiment - need more hours in the day).

> Anyway,
> flange or ribbon, like Tom says this method is just perfect for
> quadtree texture tiling.
> 
> The drawbacks, vs adaptive quadtrees:
> 
> * memory? -- you need to store x,y,z for every vert; the quadtree
> gives you the horizontal coords implicitly, and the vertical coords
> can be 8 or 16 bits, more than making up for the quadtree structure
> overhead.  Question: can hardware happily accept 16-bit integer vertex
> coords, instead of floats?  You can tweak the view matrix to get the
> desired fixed-point scaling, and 16 bits should be plenty of
> precision, but I'm not sure if modern hardware will choke on it.  With
> 6-byte verts, it might actually be a memory win vs. quadtrees.  Also,
> tiles could be decompressed before use (same principle applies to
> quadtrees, but it's tricky).

No, hardware can't generally accept 16-bit fixed-point. I think OpenGL
allows you to feed them in (? my memory is hazy), but few or no hardware
actually accepts them natively. That may change in future - 16bit vertex
data is good for discrete objects as well, and does indeed save bandwidth -
you scale to the actual object size by tweaking the object matrix.

You can construct the tiles on the fly. There's no reason you can't store
the vertex data in a highly compressed form (e.g. heightfield) and construct
it in a VB as it comes on-screen, in range or whatever.

One of the beauties of the quadtree approach is that until you need a level,
because you're close enough, it doesn't have to be loaded off disk and
decompressed and take up memory.

> * collision testing -- the quadtree gives you super efficient
> collision testing using the same data used for rendering, whereas for
> static/VIPM tiles, the bigger the tile, the more painful the collision
> testing at the leaves.  I think the solution here is to add a few
> levels of partitioning within the leaves, strictly for
> collision-testing purposes.  Could even be some very tight linear
> quadtree format; I haven't thought it through.  Seems like this could
> be finessed.

Surely collision detection needs to be done on the highest LoD all the time?
I think you want to keep the collision stuff away from the graphics stuff -
that way leads to pain. I would do the following:

(1) Swizzle the heithfield. It makes it far easier to stream in chunks, fits
the quadtree liek a glove, and improves memory access times.

(2) Construct your vertex data dynamically as needed from the heightfield
data. The VIPM tiles will span multiple quadtree nodes (16x16 or something),
but that's fine.

(3) Do collision detection using the quadtree.

> * deformable terrain is pretty much out.

Well, yeah. Though you could just ignore the deformations if they were
fairly local (e.g. a crater), though still move the vertices. The VIPM error
is unlikely to be too outrageous.

> I think this is my new favorite theoretical terrain LOD scheme.
> 
> -- 
> Thatcher Ulrich <tu...@tu...>
> ==  Soul Ride -- pure snowboarding for the PC -- http://soulride.com
> ==  real-world terrain -- physics-based gameplay -- no view limits


Tom Forsyth - Muckyfoot bloke.

What's he up to now?
http://www.muckyfoot.com/startopia/cam.html