From sbaker@link.com  Mon Dec  8 11:57:06 1997
X-VM-v5-Data: ([nil nil nil nil t nil t nil nil]
	["10830" "Mon" "8" "December" "1997" "10:55:36" "-0600" "Steve Baker" "sbaker@link.com" "<Pine.SGI.3.96.971208094500.3128A-100000@sutcliffe.bgm.link.com>" "243" "Re: Tri-strips, culling, clockwise/counter-clockwise" "^From:" nil nil "12" nil "Tri-strips, culling, clockwise/counter-clockwise" (number " " mark "  R  Steve Baker       Dec  8  243/10830 " thread-indent "\"Re: Tri-strips, culling, clockwise/counter-clockwise\"\n") nil nil]
	nil)
Received: from lfkw10.bgm.link.com (bgm.link.com [130.210.2.10])
	by meserv.me.umn.edu (8.8.8/8.8.6) with ESMTP id LAA15125
	for <curt@me.umn.edu>; Mon, 8 Dec 1997 11:56:58 -0600 (CST)
Received: from sutcliffe.bgm.link.com (sutcliffe.bgm.link.com [130.210.236.18])
          by lfkw10.bgm.link.com (8.8.6/HTI-Hack-8.8.4) with SMTP
	  id LAA11749 for <curt@me.umn.edu>; Mon, 8 Dec 1997 11:56:03 -0600 (CST)
X-Sender: steve@sutcliffe.bgm.link.com
Reply-To: Steve Baker <sbaker@link.com>
In-Reply-To: <199712081623.KAA16146@kenai.me.umn.edu>
Message-ID: <Pine.SGI.3.96.971208094500.3128A-100000@sutcliffe.bgm.link.com>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
From: Steve Baker <sbaker@link.com>
To: "Curtis L. Olson" <curt@me.umn.edu>
Subject: Re: Tri-strips, culling, clockwise/counter-clockwise
Date: Mon, 8 Dec 1997 10:55:36 -0600 (CST)

On Mon, 8 Dec 1997, Curtis L. Olson wrote:

> This weekend I grouped all the tri-stripes by winding in the .obj
> file.  Now, when I read in the file and build the display list, I just
> make an extra call or two to glFrontFace().  This seems to work just
> fine.  I may have been confused about my degenerate example, the
> tri-stripper seems to be doing the latter good form of repeating
> vertices.
 
The degenerate example is *fine* and saves significant performance
compared to introducing additional strips. I prefer your vertex reversing
trick to introducing glFrontFace calls all over the place - because
they may cause a wholesale trashing of OpenGL state information and a
bad degrading of performance.

> As you say though, this is probably not be a good general solution for
> arbitrary objects....

No, I think you'll end up rewriting (or at least debugging) that tstrip
program before the fat lady sings....but at least this solution lets you
do something more interesting first.

> What do you do about matching up terrain sections of various LOD.
> I can see the potential for gaps developing between them because
> the edges will be approximated differently.

Ah! You have a knack for finding the truly DEEP issues!

Matching LOD's is a real pain. There are many kludges - but no good
solutions. All the arguments below apply equally for when you have
many more than two levels of detail.

* Make sure that every vertex on the edge of a high LOD tile is also
  present on the edge of the lower LOD tiles.

  BENEFITS -  This is a 'perfect' solution in that there are never
         any visual anomalies.

  SNAG - It results in low LOD tiles that look like star-bursts that
         have *far* more polygons than you'd like - and which look
         *terrible*.

* Add vertical 'skirts' at the edges of tiles to fill in the gaps
  between adjacent LODs.

  BENEFITS - Since the skirt is probably (*see below) only needed
         on lower LOD tiles, it only needs a handful of polygons.
         If it drapes down below the tile to a depth equal to the
         lowest point on the edge of the high detail tile, then
         there can be no gaps. Assuming your low detail tiles are
         quite a bit simpler than the high detail ones, this can
         save a lot of polygons. However, if there isn't much
         difference in the polygon counts of the low tile compared
         to the high detail tile, then the number of polygons in
         the skirts can get unbearably large.

  SNAG - It's hard to texture and shade the skirts since they are
         vertical. Even if you make them slope outwards somewhat,
         they still look a bit ugly.

  WARNING: If your database paging/LOD selection routines are not
         perfect, it's possible that you might see a high detail
         tile *beyond* a low detail one (especially given the
         effects of perspective).

* Build 'transition' tiles that have high resolution edges on
  one or more sides and low resolution edges on the other. Use
  these tiles to 'bridge' between high and low LOD tiles.

  BENEFITS - This looks great and is a low polygon solution.
         With care, you can even arrange to switch to the
         intermediate tiles sooner than you would have had to
         bring in the low LOD tiles.

  SNAG - You need a lot of permutations and combinations of
         high and low resolution edges - that means that you
         consume a lot of RAM and disk space with multiple
         copies of intermediate tiles.

* Force all the polygon edges along the sides of low LOD tiles
  to be lower than the lowest corresponding point along the
  high LOD tile. Hence, since the eyepoint is always on the
  high detail side of the edge, you never see a gap.

  BENEFITS - Utterly minimal polygon count. Simplicity.

  SNAG - There is a big down-step from high detail to low
        that can look bad when the eyepoint is at very
        high altitudes over rough terrain.

* Use 'continuous LOD'. Imagine you are looking down onto
  a terrain tile from vertically above. Require that each
  vertex and each edge in the low LOD tile is also present
  in the high detail tile. Typically this means that each
  low detail polygon is split up into progressively more
  polygons in the high detail tiles.

  Now when you switch a low LOD tile out, bring the high
  LOD tile in with all of it's vertices moved vertically
  up or down so that they lie on the low LOD terrain.

  This looks nice since you don't have to use transparency
  to fade between the terrain tiles and they don't 'POP' in.

  Now, you can 'morph' the high LOD vertices slowly (as a
  function of range) into their correct positions.

  With complicated data structures and a lot of messing around,
  you can arrange that the high LOD vertices that lie on the
  edge of a high detail tile don't morph until the corresponding
  vertices on the adjacent tile are also ready to morph.

  Hence the edges of the terrain tile stay in their low
  detail positions until the adjacent tile is also in high detail.

  BENFITS - When properly implemented, this is great.

  SNAGS - It's a BITCH to implement - and VERY,VERY nasty
          to get right.

          Consider that you have to morph the vertex NORMALS
          as well as their X/Y/Z's - if you colour the vertices
          of the terrain as a function of altitude then the
          colours have to be morphed too.

          Features on top of the terrain have to be morphed
          up and down too - or they will be either flying of buried.
          That's a lot harder to do than it sounds since
          they may be sitting on top of a polygon which is
          on the edge of the terrain tile - and hence will
          have one or two vertices morphing and the others not.

          For military simulators, the poor targetting computers
          go nuts when a building mysteriously floats up and
          down in height as you fly up to it.

* Don't use LOD at all for the actual terrain polygons. We do
  this on some systems - since a large fraction of the IG's
  throughput is spent drawing roads, rivers, cities, forest
  areas, etc - it is sometimes enough just to throw away
  all the 'decoration' at long range and just keep the terrain
  polygons themselves.

  BENEFITS - It's really easy. All those extra polygons don't
          cost as much as you might think given that the
          T-strip very well and (typically) only use a single
          texture pattern. Since a large fraction of the IG's
          time is spent switching material properties, these
          extra polygons are not necessarily too bad. Also,
          with most of the other schemes, it's necessary to
          FADE between the levels of detail to avoid the dreaded
          POP effect - since fading is pretty costly, not doing
          it for terrain is worth considering.

  SNAGS - Obviously, this can consume a lot of polygons - or
          alternatively, cause you to use lower LOD terrain
          closer to the eye than you might prefer. 

* Realising that there are gaps between the high and low LOD's,
  you simply clear the screen with a 'reasonable' background colour
  to try to make the gaps as imperceptible as possible.

  SNAGS - This looks particularly bad when you go from (say) land
          to ocean or vice versa. Whichever colour you pick to
          clear to looks 'obviously' bad for some parts of the
          terrain.

* Realising that there are gaps between the high and low LOD's,
  you DON'T CLEAR THE SCREEN - just the Z buffer. This results
  in the gaps between terrain tiles being filled with whatever
  colour was in the frame buffer on the previous frame.

  BENEFITS - The 'gap filling' colour kind-of automatically
          adjusts itself to the colour of the surrounding
          terrain - so this trick can work suprisingly well.

  SNAGS - This fails miserably for high speed (and high roll
          rates especially) since the holes get filled with
          sky colour. Also, the OpenGL spec says that the
          colour of these pixels is 'undefined' which means
          that the gaps between tiles could come out as
          any old colour on some OpenGL implementations.

* Treat the terrain as basically a flat plain - draw each range of
  mountains or hills as a separate polygonal model which is
  faded in LOD just like a building or any other feature.

  SNAGS - For basically flat deserts with the occasional pyramid
          (like most early PC-based flight sim games), this
          works OK - but if you want realism and real-world
          terrain, it is completely impossible to use.

* Generate the terrain on-the-fly from a height grid. Although
  you more or less have to have a regular grid to make this
  work (and hence can't easily do round earth for example),
  it does make it relatively easy to avoid gaps.

What do we do here at HTI ?

Well, I can't say we really like any of these kludges - but
we have used all of them at one time or another.

The most recent few systems have not used LOD for the terrain
skin at all - and just faded the 'decoration' in (roads, rivers,
etc) - on the high end SGI boxes that we use most often, we
have ample polygon capacity to do this and still maintain a
reasonable degree of terrain fidelity. The SGI's can *devour*
polygons (11 million triangles per second) - but slow down
drastically when you do a lot of texture map switching, or
if your polygons are not well T-stripped. Since terrain will
tstrip very well indeed - and is typically covered with one
gigantic generic texture, it renders at that high rate and
dropping out the very costly decoration is enough of a saving.

The terrain 'morphing' idea is very trendy - but has some significant
implementation difficulties - especially in the military simulation
field. The multi-million $$$ Lockheed-Martin systems use morphing
as their primary terrain LOD mechanism and it certainly works
well for them.

Given time, I could probably remember some other techniques
that we used too!

I'm open to any bright ideas!

>  Also, even though my meshes will be
> irregular within a section, the section boundaries will be regular.
> Is this acceptable, or do you try to do something fancier with section
> boundaries?

Well, you still end up with a lot of polygons in the low LOD tiles,
which tend to end up looking like star-bursts (ugh).

Let me know what you think.

Steve Baker                     817-619-8776 (Vox/Vox-Mail)
Hughes Training Inc.            817-619-4028 (Fax)
2200 Arlington Downs Road       SBaker@link.com (eMail)
Arlington, Texas. TX 76005-6171 SJBaker1@airmail.net (Personal eMail)
http://www.hti.com              http://web2.airmail.net/sjbaker1 (personal)

** Beware of Geeks bearing GIF's. **

