<!-- MHonArc v2.4.4 -->
<!--X-Subject: Heightfield Terrain Rendering Paper -->
<!--X-From-R13: @vxynf Syzdivfg <q97ryzNqgrx.punyzref.fr> -->
<!--X-Date: Wed, 25 Mar 1998 15:11:53 +0000 -->
<!--X-Message-Id: Pine.SOL.3.96.980325160611.27313A-100000#licia,dtek.chalmers.se -->
<!--X-Content-Type: text/plain -->
<!--X-Head-End-->
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<html>
<head>
<title>MUD-Dev message, Heightfield Terrain Rendering Paper</title>
<!-- meta name="robots" content="noindex,nofollow" -->
<link rev="made" href="mailto:d97elm#dtek,chalmers.se">
</head>
<body background="/backgrounds/paperback.gif" bgcolor="#ffffff"
text="#000000" link="#0000FF" alink="#FF0000" vlink="#006000">
<font size="+4" color="#804040">
<strong><em>MUD-Dev<br>mailing list archive</em></strong>
</font>
<br>
[ <a href="../">Other Periods</a>
| <a href="../../">Other mailing lists</a>
| <a href="/search.php3">Search</a>
]
<br clear=all><hr>
<!--X-Body-Begin-->
<!--X-User-Header-->
<!--X-User-Header-End-->
<!--X-TopPNI-->
Date:
[ <a href="msg00894.html">Previous</a>
| <a href="msg00896.html">Next</a>
]
Thread:
[ <a href="msg00897.html">Previous</a>
| <a href="msg00888.html">Next</a>
]
Index:
[ <A HREF="author.html#00895">Author</A>
| <A HREF="#00895">Date</A>
| <A HREF="thread.html#00895">Thread</A>
]
<!--X-TopPNI-End-->
<!--X-MsgBody-->
<!--X-Subject-Header-Begin-->
<H1>Heightfield Terrain Rendering Paper</H1>
<HR>
<!--X-Subject-Header-End-->
<!--X-Head-of-Message-->
<UL>
<LI><em>To</em>: <A HREF="mailto:mud-dev#null,net">mud-dev#null,net</A></LI>
<LI><em>Subject</em>: Heightfield Terrain Rendering Paper</LI>
<LI><em>From</em>: Niklas Elmqvist <<A HREF="mailto:d97elm#dtek,chalmers.se">d97elm#dtek,chalmers.se</A>></LI>
<LI><em>Date</em>: Wed, 25 Mar 1998 16:11:49 +0100 (MET)</LI>
</UL>
<!--X-Head-of-Message-End-->
<!--X-Head-Body-Sep-Begin-->
<HR>
<!--X-Head-Body-Sep-End-->
<!--X-Body-of-Message-->
<PRE>
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#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
</PRE>
<!--X-Body-of-Message-End-->
<!--X-MsgBody-End-->
<!--X-Follow-Ups-->
<HR>
<!--X-Follow-Ups-End-->
<!--X-References-->
<!--X-References-End-->
<!--X-BotPNI-->
<UL>
<LI>Prev by Date:
<STRONG><A HREF="msg00894.html">Re: [MUD-Dev] World Persistence, flat files v/s DB v/s ??</A></STRONG>
</LI>
<LI>Next by Date:
<STRONG><A HREF="msg00896.html">3D engines for MUDs</A></STRONG>
</LI>
<LI>Prev by thread:
<STRONG><A HREF="msg00897.html">RE: [MUD-Dev] 3D engines for MUDs</A></STRONG>
</LI>
<LI>Next by thread:
<STRONG><A HREF="msg00888.html">Re: [MUD-Dev] META: Broken mail headers</A></STRONG>
</LI>
<LI>Index(es):
<UL>
<LI><A HREF="index.html#00895"><STRONG>Date</STRONG></A></LI>
<LI><A HREF="thread.html#00895"><STRONG>Thread</STRONG></A></LI>
</UL>
</LI>
</UL>
<!--X-BotPNI-End-->
<!--X-User-Footer-->
<!--X-User-Footer-End-->
<ul><li>Thread context:
<BLOCKQUOTE><UL>
<LI><STRONG>(fwd) Re: Roleplaying</STRONG>, <EM>(continued)</EM>
<ul compact>
<LI><strong><A NAME="00907" HREF="msg00907.html">(fwd) Re: Roleplaying</A></strong>,
s001gmu <a href="mailto:s001gmu#nova,wright.edu">s001gmu#nova,wright.edu</a>, Thu 26 Mar 1998, 19:41 GMT
<UL>
<LI><strong><A NAME="00909" HREF="msg00909.html">Re: [MUD-Dev] (fwd) Re: Roleplaying</A></strong>,
Katrina McClelan <a href="mailto:kitkat#the486,bradley.edu">kitkat#the486,bradley.edu</a>, Thu 26 Mar 1998, 21:59 GMT
</LI>
</UL>
</LI>
<LI><strong><A NAME="00908" HREF="msg00908.html">Re: [MUD-Dev] (fwd) Re: Roleplaying</A></strong>,
Ling <a href="mailto:K.L.Lo-94#student,lboro.ac.uk">K.L.Lo-94#student,lboro.ac.uk</a>, Thu 26 Mar 1998, 20:13 GMT
</LI>
</ul>
</LI>
<LI><strong><A NAME="00897" HREF="msg00897.html">RE: [MUD-Dev] 3D engines for MUDs</A></strong>,
Koster, Raph <a href="mailto:rkoster#origin,ea.com">rkoster#origin,ea.com</a>, Wed 25 Mar 1998, 15:51 GMT
<LI><strong><A NAME="00895" HREF="msg00895.html">Heightfield Terrain Rendering Paper</A></strong>,
Niklas Elmqvist <a href="mailto:d97elm#dtek,chalmers.se">d97elm#dtek,chalmers.se</a>, Wed 25 Mar 1998, 15:11 GMT
<LI><strong><A NAME="00888" HREF="msg00888.html">Re: [MUD-Dev] META: Broken mail headers</A></strong>,
Chris Gray <a href="mailto:cg#ami-cg,GraySage.Edmonton.AB.CA">cg#ami-cg,GraySage.Edmonton.AB.CA</a>, Wed 25 Mar 1998, 07:06 GMT
<UL>
<LI><strong><A NAME="00920" HREF="msg00920.html">Re: [MUD-Dev] META: Broken mail headers</A></strong>,
J C Lawrence <a href="mailto:claw#under,engr.sgi.com">claw#under,engr.sgi.com</a>, Tue 31 Mar 1998, 23:53 GMT
<UL>
<LI><strong><A NAME="00923" HREF="msg00923.html">Re: [MUD-Dev] META: Broken mail headers</A></strong>,
Caliban Tiresias Darklock <a href="mailto:caliban#darklock,com">caliban#darklock,com</a>, Wed 01 Apr 1998, 00:21 GMT
</LI>
</UL>
</LI>
</UL>
</LI>
<LI><strong><A NAME="00880" HREF="msg00880.html">UML/Commercial v Free Muds</A></strong>,
Greg Munt <a href="mailto:greg#uni-corn,demon.co.uk">greg#uni-corn,demon.co.uk</a>, Wed 25 Mar 1998, 03:07 GMT
</LI>
</UL></BLOCKQUOTE>
</ul>
<hr>
<center>
[ <a href="../">Other Periods</a>
| <a href="../../">Other mailing lists</a>
| <a href="/search.php3">Search</a>
]
</center>
<hr>
</body>
</html>
