Heightfield Terrain Rendering Paper

Niklas Elmqvist d97elm at dtek.chalmers.se
Wed Mar 25 16:11:49 CET 1998


To aid those fortunate people who don't have to tangle with Word 6.0, I've
converted the NDL paper on terrain rendering to plain ASCII. During this
process, all pictures were removed of course, as well as some of the
initial layout -- I had to groff the entire file after saving it as text
to do the line breaks. Therefore, things may look a little messy in
places, but it should be readable. 

Of course, I don't make any pretense of having written this myself -- the
whole paper is the property of Numerical Design Limited (NDL).
</disclaimer>

>------ Cut here ------<

Sorted Height Field Rendering
-----------------------------

Mark Finch and Lars Bishop

Numerical Design Limited


Abstract 

We present a straightforward and efficient algorithm for
the real-time rendering of height field data in sorted order  em-
ploying  continuous  LOD.   The method presented generates a spa-
tially and temporally  continuous  skin  of  antialiased  texture
mapped  triangles without the overhead of tree structures or off-
line computing of supplemental data.  The triangles  forming  the
skin  are generated in sorted order at a constant rate throughout
the frame in time linear to the number of triangles generated.


1. Introduction

The optimum tessellation of a height field is dependent  on  both
the intent of the application and the data set.  In contrast with
existing surface reconstruction and visualization algorithms  for
which  the rendered surface is the focus, the work presented here
targets applications rendering a height field, typically terrain,
as a setting or environment in which the user moves unconstrained
at ground level or low altitude.  This environment is expected to
be  detailed  and varying, populated with dynamic models, and en-
hanced by shading, fog, and other dramatic visual  effects.   The
requirements  of  such  applications  are discussed in Section 2,
while Section 3 outlines selected recent research as relating  to
these needs and the resulting design decisions.

The  full  algorithm is detailed in Section 4 in a top down fash-
ion.  Care is taken to refer design  and  implementation  details
back  to  the  stated system goals.  Top level system components,
which are not technically part of the tessellation  process,  are
described to the degree on which the rendering depends on them.

Experimental  data  and analysis is presented in Section 5.  Per-
formance figures and trends gathered from  a  133MHz  Pentium  PC
with and without hardware acceleration demonstrate the scalabili-
ty of the system.


2. Design Issues

The terrain rendering system was designed around a clear  set  of
requirements.  The system must provide high performance and qual-
ity on current low end systems, but take advantage of higher  end
platforms  as well as future advancements.  In particular, faster
processors, graphics accelerators, and  multiprocessing  environ-
ments  should controllably improve speed and/or quality.  Texture
mapping is assumed indispensable  to  augment  geometric  detail.
The  tessellation  of the terrain database cannot be uniform, but
rather sampling must be dynamically budgeted based on importance.
It  is further assumed that sampling the database while maintain-
ing adequate frame rates will not be adequate to bound errors  to
within  a  few  pixels.   Therefore, as terrain moves from coarse
tessellation to finer it must be smoothly morphed  to  avoid  the
distracting  "popping"  effect.  For load balancing with graphics
hardware or in multiprocessor  environments,  triangles  must  be
steadily produced throughout the frame.  These triangles are ide-
ally generated in sorted order, front to back in the presence  of
Z-buffering,  or  back to front for the painter's algorithm.  Fi-
nally, the system must provide a general and  friendly  interface
to the application layer, providing a high degree of control both
in database management and rendering, while hiding the complexity
of the underlying system.

The  following  list  summarizes  the requirements of the terrain
rendering system: 

* Importance driven geometric reduction
* Antialiased texture mapping
* Shading
* Smooth morphing
* Vertex Matching (No T-junctions)
* Separable loading (pages)
* Separable rendering (strips)
* Sorted triangle generation
* Broad scalability
* On-the-fly tunability
* Low overhead
* Graceful degradation under stress

There is obvious overlap between some requirements, while  others
interact  in more subtle ways.  Their impacts on design decisions
are highlighted later as the design is detailed.


3. Prior Work

The use of triangulated irregular networks (TINs) is  often  dis-
counted in real-time terrain rendering literature.  The complexi-
ty of TIN generation relegates it to an off-line process[11], and
once  generated, the TIN model does not lend itself to operations
trivial for Regular Square Grids (RSGs).  For instance, while ex-
cellent  work  has  been  done in creation of multiresolution TIN
models [5], matching of regions of  differing  resolution  (crack
prevention) may offset the gains.  It is often neglected that for
many typical data sets and application requirements,  a  TIN  may
provide  such data compression that rendering the full resolution
TIN may be more efficient in time and space than is possible  us-
ing  techniques  that facilitate view dependent multiple Level Of
Detail (LOD) selection.  It is therefore not  lightly  that  TINs
are  deemed inappropriate for the work presented here.  While ef-
ficient  terrain  inquiry  methods  have   been   developed   for
TINs[9,10],  the  expected  frequency  of such operations for the
targeted applications requires such operations to be done not on-
ly in constant time, but with a very low time constant.  More im-
portantly, the benefits of TINs diminish as they are  constrained
beyond feature matching.  Respecting texture map boundaries elim-
inates the gains of condensing large flat  expanses  into  a  few
large  triangles.  Similarly, limiting screen space triangle size
would require on-the-fly triangle reduction or  further  limiting
the retriangulation.

RSGs,  while  not  tessellating a height field as well as TIN ap-
proaches[6], operate fast enough to allow view dependent  tessel-
lations  in  real  or near-real time.  They are primarily distin-
guished by their vertex selection  method   (triangles  generated
are implied by which vertices are selected for a given frame).  A
simple but effective method is the division of the  height  field
data (which may be considered infinite in horizontal extent) into
fixed size "pages".  Each frame, each visible page is tessellated
uniformly  at some LOD determined by the page's data and the eye-
point.  Adjacent pages of differing resolution are  stitched  to-
gether with fill triangles.[3]

Greater  compression  for  the  same quality rendering may be ob-
tained by selection of vertices  on  an  individual  basis.   Re-
stricted  quad  tree approaches so select vertices such that tes-
sellating the resulting set of vertices with a continuous  match-
ing skin is highly efficient. [5]  The nature of vertex selection
varies widely in intent and cost.  Gross et. al. provide an inno-
vative  marriage of minimizing model space error while accounting
for importance to the view[7], while Lindstrom et. al. attempt to
bound screen space error.[8]


4. Method


4.1 Overview

It is convenient to define the LOD quantity of an RSG in terms of
the base 2 logarithm of its sampling interval,  such  that  LOD=0
refers  to  sampling  every value in the base height field, LOD=1
samples every other height, etc.  The direct relation of the  LOD
with  the  sampling rate is then clear, and throughout this paper
the two will be used interchangeably.

Real-time multiresolution height field rendering  as  implemented
by  RSG  algorithms  may  be logically broken into two processes.
The first is vertex selection for a given frame based on some im-
portance  criterion which is generally a weighted function of lo-
cal geometry and importance to the viewer.  The selection process
is  further  constrained such that the output set of vertices may
be efficiently converted to a continuous skin of triangles  with-
out  T-junctions.   It is generally sufficient that the LOD never
change by more than a small fixed number between two adjacent re-
gions  (e.g. 2 in [7] and 1 in [8,12]).  The second process gath-
ers the selected vertices, converting them into a form  palatable
to  the  rendering  engine (e.g. attaches shading and texture map
coordinates) and feeds them into the rendering pipeline.

The system presented here collapses both operations into a single
pass  over  the  visible  portion  of  the height field.  A small
bounded amount of computational work per  triangle  selects  ver-
tices, generates triangles preserving spatial and temporal conti-
nuity, and feeds them into the graphics pipeline in sorted order.
This  is made possible by recognizing that, for the target appli-
cation domain, the need for a uniform screen space triangle  size
far outweighs the need to bound fidelity to the data.

Uniform  sized screen triangles are essential for low end systems
relying on software rasterizers, for which perspective correction
exacts  significant  cost.  Even on hardware accelerated systems,
however, regulating the maximum screen size of triangles  enables
the  effective  use of Gouraud shading to provide extremely cheap
dramatic effects.  For example, the standard technique of  apply-
ing  "fog"  to fade triangles into the horizon cannot interpolate
between vertex fog values when a single triangle  may  cover  the
flat  expanse from the viewer to the far clipping plane.  In that
case, fogging must be applied on a per pixel basis.  Local light-
ing  effects for explosions or night scenes rely on adequate den-
sity of vertices on the screen to allow the interpolation of  il-
lumination  values.   Alternate  methods  of overlaying these and
other effects onto triangles of unknown extent and depth complex-
ity  are  expensive in system resources, artistic and engineering
work, or both.

As methods which provide dense tessellation in  regions  of  high
spatial frequency rely on large triangles in flat regions to off-
set the cost [2], the prohibition of large triangles  by  texture
map  boundaries  and  screen  size  limiting precludes their use.
Fortunately, the sampling densities achievable here, augmented by
texture  maps  for  fine  detail,  are sufficient to provide com-
pelling realism on a wide range of terrain types and  on  a  wide
scale of systems, from low end consumer level PCs up.

It  is  important  to note that any vertex selection method which
outputs a set of vertices satisfying the single LOD step  between
adjacent regions could be used as the front end of the sorted or-
der triangle generation method presented here.  If in addition to
the Boolean on/off of a vertex, it provides a fractional value in
the range [0..1) indicating how on that vertex is, temporal  con-
tinuity though vertex blending (smooth morphing) will also be es-
tablished.  While the resulting hybrid system would be quite pow-
erful, for the reasons stated above, it would be less appropriate
for our targeted application domain.


4.2 Data Organization

The terrain database is broken  at  the  application  level  into
units  referred  to  as pages.  All pages of a given data set are
square height fields of the same dimensions.  Their  world  space
size  is  also uniform.  The height field dimension is a power of
two plus one on an edge, the adjacent edges of two  pages  having
the same values.  Also associated with each page is a set of tex-
ture maps of  descending resolution.

In a typical  application,  an  entire  terrain  data  set  would
severely  tax  the  memory management system if loaded as a unit,
severely compromising system performance  and  causing  excessive
start  up times.  The page based system allows the application to
keep only the current region of interest in memory, asynchronous-
ly  prefetching  pages before they come into view, and discarding
pages that have been passed.[3]  The page based system  also  al-
lows  critical optimizations.  An entire page may be culled based
on its bounding volume.  Lighting, fogging and clipping  are  re-
stricted  to those pages which require them.  In practice the ex-
tent of a terrain texture overlaid onto the terrain height  field
defines the page size.

There  is  a  clear  tradeoff  on selection of page size.  Larger
pages allow a greater reduction in the number of triangles drawn,
while  smaller pages allow more efficient rendering of those tri-
angles.  The rendering engine, particularly in the presence of 3D
hardware, may impose a cap on texture size and hence page size.


4.3 Selection Of  Footprint

All  terrain  potentially  visible from a viewpoint lies within a
polyhedron formed by the intersection of the  view  frustum  with
the  planes  of  maximum  and minimum height of the database. The
footprint of the view on the terrain is the  projection  of  this
polyhedron onto the domain of the terrain height field. Since the
terrain is considered to be of infinite extent, its bounding  re-
gion  is  only  finite  in the height dimension.  No terrain data
outside of this footprint could be visible, and need not be load-
ed  into memory [3].  However, any page at least partially inside
this footprint is potentially visible.  Again, large  pages  will
require  loading of large amounts of height and texture data when
only a small fraction of the page is visible.

The footprint obtained is a convex planar polygon containing  all
potentially visible terrain data.  The application is notified if
any pages within the footprint have not  yet  been  loaded.   The
footprint is then rastered out to generate the terrain triangles.
Currently, the footprint is rastered back to front along the hor-
izontal  dimension most perpendicular to the view direction.  The
capability to raster front to back is a trivial  extension.   The
front-to-back regular grid nature of triangle generation makes it
possible to interleave the drawing of objects above  the  terrain
with  terrain  generation  so  that the objects correctly obscure
(and are obscured by) the terrain[12].

The rastering operation breaks the terrain into strips  a  single
triangle  in  width.   The  width of a strip reflects the current
sampling rate and strips may be further subdivided  as  described
below.

It  is important to note that each strip depends only on the pre-
vious strip's tessellation to prevent cracks.  While global solu-
tions  may only begin producing triangles at the tail end of pro-
cessing, this system begins feeding the graphics pipeline immedi-
ately.   Furthermore, as will be seen the work to generate a tri-
angle remains nearly constant, so triangle  generation  continues
throughout  at a steady rate.  This is an important consideration
in the presence of multiple processors or  asynchronous  graphics
hardware.


4.4 Generation of Terrain Geometry

Figure 3  Merging quads to coarser level of detail.

The strip generation process creates the geometric representation
of the terrain by stepping  along  in  the  horizontal  direction
(called  the minor direction) that is closest to perpendicular to
the view direction, generating sets of  triangles  that  complete
quadrilaterals  of  the  given LOD size.  The border of each quad
contains the current vertex being  examined,  the  next  previous
strip  vertex,  and vertices from the front edge of the strip di-
rectly behind.  The quad  may also contain other vertices between
these,  in order to allow splitting of quads when moving to finer
LODs and to ensure that no cracking occurs.  This is  illustrated
in Figure 1.

Quads of a given LOD must be aligned to that LOD - for example, a
quad at the coarsest LOD is the size  of  a  page,  and  must  be
aligned  to  page boundaries.  Thus, every vertex in a page has a
coarsest possible LOD value (determined by its alignment  in  the
page).   This  greatly simplifies the quad generation process and
ensures that quads never cross  page  boundaries.   There  are  a
small,  finite  number of quad configurations; Every LOD uses the
same configurations, scaled to that LOD's quad size.

Figure 2 Splitting quads to finer level of detail.


4.5 Geometric LOD Transitions

Figure 1  Terrain quads at two levels of detail.

The level of detail selected at a given vertex is a  function  of
that vertex's position and the relative position of the eye.  The
exact nature of the function is arbitrary, subject  to  the  con-
straint  that  no  generated  triangle cross two LOD transitions.
Currently a log distance to the eye function  is  implemented  to
provide constant screen space triangle size as:

LOD = LUT[ DistToEyeSq(vertex)*LODScaleFactor]

As  the  function  is implemented as a lookup table, other scalar
functions of distance may be easily implemented by  the  applica-
tion providing an alternate lookup table.

As the stripping process moves along, there are two major transi-
tions that may occur; Splitting to a finer LOD, and merging to  a
coarser  LOD. Note that both of these transitions ensure that the
front edge of a strip never moves forward or backward in the  ma-
jor direction from its starting position, even in the presence of
merging or splitting.

A split occurs when the stripping process determines that the LOD
function  evaluated  at  the current vertex indicates a change to
the next finer LOD. It splits by drawing a splitting quad of  the
current size and then creating a new strip that recursively draws
the further of the two strips that will continue on at the  finer
LOD  as  shown  in  Figure 2.  Once the rear "fill-in" strip com-
pletes, the current strip continues on with the same front  edge,
but starting with quads half as large as before.

A merge occurs when the process determines that the strip direct-
ly behind the current quad is further back than the size  of  the
current  LOD,  and  that the current front edge is aligned to the
next higher LOD.  This may be determined by  examining  two  ver-
tices.   If  the  criteria are met, the process draws the merging
quad in Figure 3 at the size of the new, coarser LOD and  contin-
ues on with the process, generating quads at the new LOD.

Figure 4 Possible Quadrilateral Constructions

A  quad  must use the same vertices along its back edge that were
used for the front edge of the quad or quads directly behind  it,
so as not to produce cracks in the terrain.  Since we assume that
the LOD function will never change more than one level up or down
in  the space of a quad, there are only three possible configura-
tions of the back edge of the new quad; It must span  one  vertex
(quad behind it is double the size), two vertices (quad behind it
is the same size), or three vertices (two quads of half size  are
behind)  that  were used for the previous strip.  This may be de-
termined by examining at most three vertices.  Due to overlap  in
the method between the various cases, the correct quad configura-
tion can be entirely determined by (at most): examining the  cur-
rent  vertex's alignment with respect to the next higher LOD, ex-
amining 2 vertices for usage in the current frame, and evaluation
of the LOD function at the current vertex.

Vertices  are allocated only when used for a given frame's repre-
sentation, allowing for simple and fast  determination  of  which
vertices are and are not part of a given frame.  Also, since ver-
tices along the edges of a page represent the  same  vertices  as
those  along  the  edges  of  another page, the stripping process
copies edge vertices forward across page boundaries.

Any strip continues adding quads in the minor direction until the
next quad would either be part of a page that is not in the visi-
ble footprint (the strip has run off the edge of the screen),  or
until  the  next  quad  would cause a shift to a coarser LOD that
would cause the current strip to expand forward (the strip was  a
recursive "fill-in" strip at that LOD).  Thus the stopping crite-
ria require only a small, constant amount of work per quad.

The following section details the quad generation process in  our
current  implementation.  It  should  also be noted that the quad
creation process is repeated for each frame. The expense of  this
process  is so low that this repetitive calculation represents an
extremely beneficial time/space tradeoff over the entire  perfor-
mance spectrum of target machines.


4.6 Pseudocode for Quad Generation Process.

This  section  describes in detail the method used at each vertex
in the stripping process to decide what level of detail is to  be
used,  the  triangles  to be generated, and the next vertex to be
considered.  Figure 4 shows all possible quad configurations  for
a  given  set  of major and minor stripping directions.  Assuming
that we are in the stripping process at some vertex  P,  stepping
along at a current LOD of L, then the next quad will be generated
according to the following method:

(Notation:

	P+/-M denotes a step of the current LOD size forward or back from
	P in the major direction.

	P+/-m is the same for the minor direction.

	P+2M  and  P+M/2  denote  steps of twice and half the current LOD
	size

	LODFUNC(P) is the LOD function evaluated at P):

GenerateNextQuad()  {
     SWITCH(P's alignment with respect to LOD L+1)     {
          CASE (Aligned in minor direction (major irrelevant))
               NormalQuad()
          CASE (Aligned in major but not minor direction)
               if(vertex at P-M has been used this frame)
                    NormalQuad()
               else // Merging to higher LOD {
                    Draw quad shown in figure 4 E),
                    advance,
double step size (L = L + 1) and advance again
}
          CASE (Not aligned in either direction)
               if(LODFUNC(P) > L)  // End of rear fill-in strip
                    End Strip
               else
if(vertex at P-M has been used this frame)
                    NormalQuad()
          else           // Matching higher LOD behind
                    Draw quad shown in figure 4 C) and advance twice
}
}

NormalQuad()   {
if(LODFUNC(P) < L)  // split to lower LOD    {
          Draw quad shown in figure 4 D)
          Draw recursive fill in strip of LOD L-1 starting
 at P+m/2-M/2
     Halve step size (L = L - 1) and advance
}
else {
     if(vertex at P-M-m/2 has been used this frame) // Regular
               Draw quad shown in figure 4 B) and advance
     else
               Draw quad shown in figure 4 A) and advance
}


4.7 Starting a New Strip

The method described above defines the progression of the  method
for  recursive  strips, whose starting positions and LODs are set
by the parent strip creating  them,  as  well  as  for  top-level
strips  already  underway.  The starting position and LOD of top-
level strips are handled differently.  For the following  discus-
sion,  the  term "major (minor) direction page" refer to the line
of pages that share the same major (minor) direction  coordinate.
In the current method, a strip always stays within a major direc-
tion page.

Top level strips always begin on a page boundary in the minor di-
rection.   When a new top-level strip is begun, the front edge of
the previous strip (which was constant  in  the  major  direction
across  the entire strip) is checked to see if it fell on a major
direction page boundary.  If not, then the starting  position  of
the  new  strip  in the minor direction is the same as it was for
the last strip.  If the last top-level strip had its  front  edge
on  a  major direction page boundary, then the visible page foot-
print is checked to find the starting and ending pages in the mi-
nor direction for the new major direction page.  The new starting
minor page boundary is used for the strip.

The major direction position of the new strip is  dependent  upon
the  starting  LOD of the new strip.  The starting LOD of the new
strip is found by starting at the vertex that is located  at  the
intersection  of the front edge of the previous strip and the new
strip's minor direction starting position.  The initial  estimate
of  the  starting  LOD is set to the starting LOD of the previous
strip and position and LOD estimate are adjusted as necessary.


4.8 Texture LOD

Each page has associated with it a sequence of  texture  maps  of
decreasing  resolution.   These  are provided by the application.
Ideally, to avoid edge effects, the global texture map should  be
repeatedly  filtered and decimated, the downsampled versions then
being diced into page units.  Filtering after dicing will produce
unpleasant  effects  along  all page boundaries.  Like the height
field data, the adjacent edges of adjacent texture maps should be
equal.  That is, the last texel on a given row should be equal to
the first texel on the same row of the next page.  Each  triangle
generated  will be matched with a single texture map of appropri-
ate resolution from the page's list, providing a strong degree of
texture antialiasing with or without hardware support.

While  pyramidal  mipmapping  is a powerful and efficient tool in
the display of models, its current implementations make it  inap-
propriate for the display of terrain databases.  The texture mem-
ory available even on high end graphics systems  is  insufficient
to  hold  the textures for the entire visible section of the ter-
rain at resolution high enough for the  terrain  closest  to  the
viewer.  Unfortunately, in current systems the entire mipmap must
be loaded into texture memory, even if only the  top  few  lowest
resolution, and hence lowest memory usage, levels will be used.

For  a  database containing the range of scale that terrain does,
the system must allow the selection of texture map resolution  on
a  per  triangle  basis.  Only those texture resolutions actually
selected are loaded into texture memory,  allowing  large  exten-
sions to the yon clipping plane without significant drain of sys-
tem resources, while maintaining high quality resolution  in  the
vicinity of the camera.

This  system  also  allows  the application to quickly load a low
resolution texture for a page coming  into  view,  and  start  an
asynchronous load of the higher resolution maps.  The low resolu-
tion texture will be used until the high resolution load is  com-
pleted, helping to avoid stalls at start up, as the camera moves,
or as data arrives over the network.


4.9 Height Blending

As discussed above, it is assumed that the system will in general
be unable to maintain reasonable frame rates if it is required to
use a geometric sampling rate high enough to bound representation
errors  to  less than a few pixels in screen space.  As a result,
severe visual "popping" can result in the terrain  representation
as  the  camera moves closer to areas of the terrain that contain
high frequency changes in height.  This popping occurs  when  the
edge  between  two  adjacent vertices in one frame is broken into
two edges by the introduction of a non collinear vertex of a fin-
er LOD in the next frame.

The  system alleviates this popping by using an LOD function that
includes not only an integer value, but also  a  fractional  part
that  represents  the location of the current vertex with respect
to the near and far boundaries of its integer LOD function value.
This  fractional  part  is used to smoothly introduce vertices of
finer LODs as sections of the terrain come closer to the eyepoint
[2].   When  the  quadrilateral generation method described above
determines that a vertex is to be part of the current strip,  its
height value and those of two of its neighbors of the next coars-
er LOD are blended using a weighted average.

The averaging of the "new" vertex with these neighbors is weight-
ed  by a function of the new vertex's fractional LOD value.  This
causes a vertex to be that has just barely crossed  into  an  LOD
for which it is valid to lie collinear with respect to its coars-
er LOD neighbors.  As the new vertex continues to move closer  to
the  camera,  its  fractional LOD value will change smoothly, and
the vertex will smoothly rise or fall to its correct height.  The
two  neighboring  vertices are selected so that the new vertex is
blended with vertices that formed the endpoints of an  edge  that
cross over the new vertex's position.  This causes the new vertex
to break an edge into two edges smoothly.

Visually, this blending tends to cause smooth "morphing"  of  the
terrain,  without the jarring temporal discontinuities that occur
when discrete additions of vertices at their  correct  height  is
allowed.   The  cost of this blending is minimal and pays for it-
self by allowing LOD transitions to occur  at  much  closer  dis-
tances  to the camera than would be acceptable with discrete ver-
tex addition.

As a new vertex is introduced (or removed) collinearly to prevent
geometric  popping, in the absence of texture perspective correc-
tion, there remains a pop as  the  perspective  distortion  grows
(diminishes) from the changing tessellation.  For a small perfor-
mance price the blending may be moved from the single height  di-
mension  to a 3-dimensional interpolation from one of  the edge's
endpoints to the new vertex's natural position.[1]

Figure 5 Performance Time vs. Triangle Count


4.10 Tuning Parameters

The triangle generation process may be dynamically controlled  to
maintain  constant  frame rate through a small set of parameters.
It should be first noted that as the camera  rises  in  altitude,
maintaining  a  constant  screen  space triangle size reduces the
number of triangles necessary to cover the visible  terrain.   On
the other hand, as the camera lowers to the terrain, the apparent
horizon closes in.  Thus the yon clipping plane may be brought in
toward  the camera at low camera height to compensate for the in-
creasing number of triangles being generated,  providing  a  good
degree  of constancy in work load.  This may be fine tuned by ad-
justing the distance of the LOD transition  boundaries  from  the
eye  point  through a single scalar value.  The LOD scaling value
may be set on a frame by frame basis to regulate number of  poly-
gons generated, time per frame, or any other metric of the appli-
cation's choosing.  Note that none of these  manipulations  alter
the  overhead  of the system.  The work required to generate each
triangle remains constant.


5. Results

The described terrain algorithm has been implemented  in  C++  as
part  of an integrated graphics toolkit.  Performance testing was
conducted on a 133MHz Pentium-based PC with 32 Megabytes of  main
RAM.

The  tests consisted of "flying" the viewpoint in a circular pat-
tern around the data set, with the camera height  constrained  to
follow  the terrain.  The path constituted 1000 frames, with cam-
era position dependent only on frame number, not on  frame  rate.
A scene of infinite extent was created by tiling an 8x8 page data
set across the entire plane.  Each page consisted of  65x65  ver-
tices,  giving  a  maximum resolution of 8192 triangles per page.
The view footprint intersected an average of  35  pages  in  each
frame,  giving a maximum resolution of 286,720 polygons generated
per frame.

Performance results were gathered in three series, differing only
by  the  method  used  to  rasterize  the transformed and clipped
screen-space triangles.  The three rasterization methods were; No
rasterization, Microsoft's Direct 3D immediate ramp-mode software
rasterization, and rasterization by a 3Dfx Voodoo  Graphics-based
hardware  rasterizer  via  Direct 3D immediate RGB-mode.  The Di-
rect3D software rasterizers were chosen over  custom  rasterizers
for consistency across all tests. All tests were conducted with a
640x480 pixel framebuffer, with perspective correction  and  tex-
ture mapping turned on in both software and hardware rasterizers.

The LOD function was constant during the course of each individu-
al  run, and was adjusted between each successive run to move the
LOD crossover points further away from the eyepoint.  This creat-
ed  a  sequence  of average per-frame triangle counts that ranged
from approximately 400 to 6000  generated  triangles  per  frame.
The  generated triangles per frame value represents the number of
triangles created by the terrain system,  and  includes  polygons
that may be clipped or culled by the renderer.

Figure 5 summarize the results of these tests.  The three "Gener-
ation" timing values represent the time spent running the  method
described  by  the  paper  to generate model-space triangle sets.
The three "Render" timing values represent the time spent in  the
(software)  geometric  front-end pipeline, including transforming
and clipping and the (software or hardware)  rasterization  back-
end pipeline.  Finally, the "Total" timing values show the sum of
the corresponding preparation and rendering values.

As can be seen from the figures, terrain preparation time is lin-
ear with respect to the number of generated triangles even with a
small number of generated triangles, showing that  the  algorithm
scales well over a wide range of resolutions.

Also,  the overhead for terrain generation is quite low, as noted
by the fact that terrain preparation itself (neglecting all  ren-
dering) attained an average of approximately 60 frames per second
at 400 output polygons.  At this number  of  generated  polygons,
the  terrain  system  was  generating an average of fewer than 12
polygons per page, attesting to the low per page overhead of  the
method.

Finally,  the  cost of terrain generation on a per triangle basis
is low compared to the software  geometric  front-end  (note  the
timing  curve  for  "No  Rasterization"), with software geometric
computations crossing over terrain generation at around 1000 gen-
erated triangles per frame.

Figure 6 Example image generated by method

Obviously  the  effectiveness  of  the tradeoffs employed in this
module can only be evaluated  within  applications.  Furthermore,
the  quality  improvement  provided  by  morphing vertex position
rather than permitting "popping" is subjective,[4]. However, Fig-
ure  6  gives  some idea of the level of quality maintained in an
application.

The screen shot in Figure 6 shows what the viewer sees in an  in-
teractive  fly-by application. Note that the terrain module main-
tains levels of detail for which the screen area of all  polygons
is  relatively  constant.  Figure 7 is a schematic diagram of the
tessellation used to create Figure 6, as viewed  from  above  and
behind  Figure 6's viewpoint, with page boundaries marked in dark
lines.

Our experience has been that acceptable quality levels  for  game
applications can be readily achieved, even on machines with no 3D
acceleration hardware. Using the Direct3D  software  rasterizers,
the  terrain  renderer provides acceptable visual quality at a 15
Hz frame rate by maintaining a level of detail such that approxi-
mately  400 polygons are sent to the graphics on an unaccelerated
133 MHz Pentium processor. Within a  game  application  utilizing
custom  software  rasterizers, the performance can be expected to
rise to over 20 Hz with similar geometric complexity.  With typi-
cal  consumer hardware acceleration the level of performance dou-
bles to either a 40 Hz frame rate or twice the geometric complex-
ity at the same frame rate.

Figure  7 Schematic representation of tesselation used for previ-
ous image with page boundaries and eyepoint marked.


6. Concluding Remarks

Rather than supplanting the existing approaches to  height  field
rendering,  we hope to have filled a gap in which such approaches
are inappropriate. Whether because of  fairly  uniform  frequency
content  in  the height field data, application needs for uniform
eye-space vertex density, or restrictions  on  tessellation  with
respect to texture map boundaries, for many applications weighing
in local geometry considerations into  the  tessellation  process
adds expense without allowing the benefits of those methods.  For
such applications, we have demonstrated a method with  which  the
results  of  a restricted quad-tree approach in which the weight-
ing between local geometry and proximity to viewer  is  zero  and
one  respectively,  may  be generated in less time and with added
benefits of sorting and blending.

By decoupling the vertex selection and triangle generation we al-
so  hope  to  have  shown  that other methods of vertex selection
might also reap these benefits by  selecting  vertices  by  their
method, possibly dependent on local geometry, followed by a sepa-
rate pass with our triangle generation  to  produce  the  sorted,
blended triangles for rendering.


7. Future Work

The current limiting factor in geometry reduction is that no quad
may be larger than a page.  The only reason for this is that tri-
angles  must  adhere  to texture map  boundaries.  An even higher
geometry reduction rate could be attained by allowing  blocks  of
pages  to  be  represented  by one quad by allowing the method to
skip vertices at scales larger than a page possibly by using  low
resolution  textures  spanning multiple pages (or no texturing at
all) for these quads.

Further removal of "popping"  and  sampling  artifacts  might  be
achieved  at  the  cost of increased storage by using a true mul-
tiresolution representation of the height fields.   Such a repre-
sentation  would ensure that vertices sampled by the terrain gen-
eration process at a given sampling rate (i.e. LOD) had been pre-
filtered by a kernel of appropriate scale.

The  terrain  method  could  be used to render "cave" or "tunnel"
scenes by drawing two terrain objects in an interleaved  fashion,
with  one  terrain  object  for  the floor, and the other for the
ceiling.  Care would have to be taken in "stitching" the two  ob-
jects together wherever they met, as well as stopping the drawing
of the terrain strips at such points to ensure  that  the  scenes
were not overdrawn incorrectly.  Other related research could in-
clude more generalized "stitching" of multiple terrain  datasets,
either to create more complex topologies, or to merge terrain ob-
jects of different base resolutions.

Finally, the method's incremental generation of terrain  geometry
(the  generation of individual strips) makes the method ideal for
multithreaded implementations.


8. References

[1] COHEN-OR, D., and YISHAY L. Temporal Continuity of Levels  of
Detail  in Delaunay Triangulated Terrain. In Proceedings of Visu-
alization '96, 1996, pp. 516, 37-42.

[2] COSMAN, M. A., A. E. MATHISEN, and J. A. ROBINSON.  A New Vi-
sual  System  to  Support Advanced Requirements.  In Proceedings,
IMAGE V Conference, June 1990, pp. 370-380.

[3] FALBY, J. S., ZYDA, M. J., PRATT, D. R., and  MACKEY,  R.  L.
NPSNET:  Hierarchical  Data Structures for Real-Time Three-Dimen-
sional Visual Simulation.  Computers & Graphics, 17(1), 1993, pp.
65-69.

[4] FERGUSON, R. L., ECONOMY, R., KELLY, W. A., and RAMOS, P. P.
Continuous Terrain Level of Detail  for  Visual  Simulation.   In
Proceedings, IMAGE V Conference, June 1990, pp.  144-151.

[5] FLORIANI,  L.  D.,  MARZANO, P. and PUPPO, E.  Multiresolution
Models for Topographic Surface Description.  In The  Visual  Com-
puter 1996, 12 pp. 317-345.

[6] FOWLER, R. J. and LITTLE, J. J.  Automatic Extraction of Ir-
regular Network Digital Terrain Models.  Proceedings of  SIGGRAPH
79.  In Computer Graphics 13(2), August 1979, pp. 199-207.

[7] GROSS, M. H., GATTI, R., and STAADT, O.  Fast Multiresolution
Surface Meshing.  In Proceedings of  Visualization  '95,  October
199, pp. 135-142.

[8] LINDSTROM, P. KOOLER, D., RIBARSKY, W. HODGES, L. F., FAUST,
N. and TURNER, G. A. Real-Time, Continuous Level of  Detail  Ren-
dering  of Height Fields. In Proceedings of SIGGRAPH 96.  In Com-
puter Graphics August 1996, pp. 109-118.

[9] SCARLATOS, L. L. A Refined Triangulation Hierarchy for Multi-
ple Levels of Terrain Detail.  In Proceedings, IMAGEV Conference,
June 1990, pp. 114-122.

[10] SCARLATOS, L. and PAVLIDIS, T.   Hierarchical  Triangulation
Using Cartographic Coherence.  In Graphical Models and Image Pro-
cessing 54(2), March 1992, pp. 147-161.

[11] SCHROEDER, W. J. and ROSSBACH, P. Managing the Complexity of
Digital  Terrain  Models.   Computers & Graphics 18(6), 1994, pp.
775-783.

[12] ZYDA, M. J., MCGHEE, R. B. MCCONKLE, C. M.,  NELSON,  A.  H.
and  ROSS,  R.  S.  A Real-Time Three-Dimensional Moving Platform
Visualization Tool.  Computers & Graphics 14(2), 1990.


-- Niklas Elmqvist (d97elm at dtek.chalmers.se) ----------------------
"You can't trample infidels when you're a tortoise. I mean, all you 
 could do is give them a meaningful look."	 
	- Terry Pratchett, Small Gods




More information about the mud-dev-archive mailing list