Fast, Scalable Terrain Visualization

GLOBEtrotter

Download zipped source (compiles on Windows and Linux) Download zipped executable and data files

1. The Program

1.1 Using GLOBEtrotter

GLOBEtrotter is an attempt to render the world on a computer screen, in 3D, on Windows and Linux, interactively, with easy navigation. The controls are shown below:

Hit the spacebar to toggle the wireframe view!

As you can see, the top half of the screen is dedicated to showing actual terrain in 3D. Dragging the mouse around the top will let you change your compass direction, or look up or down. The bottom righthand window is used for changing your position in the world.

1.2 Features

Implemented features include:

Adaptive tesselation allows complicated areas to be highly tesselated, while flat areas (such as the ocean) remain coarsely tesselated. The technique I use was pioneered by Lindstrom [1].
Elevation data has been reorganized to be more contiguous on-disk, making for faster out-of-core usage.
View-frustum culling means that we don't draw triangles outside of the field of view. The data window shows which triangles are actually drawn.
Texture mapping was used to "paste" an image of the world onto our 3D geometry.
Compiles on Linux and Windows; binaries are available for both.

2. The Theory

2.1 Three Steps to Terrain Visualization

Terrain visualization requires the following steps; each of these steps will be covered later.

Terrain Data Collection: terrain data must somehow be collected or mined.
Terrain Data Reformulation: that initial data must be stored in a convenient data representation
Terrain Rendering: the reformulated terrain data should be shown to a user in an interactive way

The goal of this project was to achieve scalable terrain representation, with an interactive (ie sufficiently fast) rendering rate, using the techniques described in Lindstrom [1].

2.2 Level of Detail Rendering, in a Nutshell

Collected terrain data sets may be very large (sometimes on the order of terabytes). This presents a problem: how can we render a massive model with limited computational resources?

Level of detail rendering (LOD) provides an answer. Luebke [2] defines LOD's essential idea well: "when rendering, use a less detailed representation for small, distant, or unimportant portions of the scene." One might not even model things that are unseen; objects behind the viewer, for example, don't need rendering resources at all.

The two basic approaches for achieving LOD rendering are compared below:

Top Down Bottom Up

Basic Idea Divides the terrain up hierarchically, from the top down. Simplifies the terrain from the most detailed data set to one or more simple versions. A lack of hierarchy opens up the question, "where should we refine next?"

Image Analogy This is like resizing an image by resampling it: fast, but lacking in quality. This is like resizing an image by filtering it: slow, but accurate.

Advantages Convenient retesselation of the terrain, meaning that view-dependent LOD is easy. Provides a better fit to the terrain, with less polygons.

Disadvantages Retesselation takes time, and may not provide the best fit to the terrain. Does not intuitively lend itself to view-dependent LOD rendering, because of the lack of hierarchy.

Modern techniques combine "top down" and "bottom up" approaches, to combine the best of both worlds: some "bottom-up" preprocessing is done to get a better fit to the terrain, and "top-down" runtime processing is done to make simplification/refinement choices manageable.

2.3 Lindstrom's approach

This project will use Lindstrom's approach to LOD terrain rendering, which will be described in a moment.

First, realize that the basic idea is to tessellate our elevation map into triangles that abut against each other. If the world were truly flat (no mountains or terrain variations), and rectangular, we could use only two triangles. Terrain is much more complicated than that, so we'll be dividing our area into many triangles.

Like the approach described in Duchaineau [3], Lindstrom's approach is hierarchical. It relies on the idea that we may split any right triangle into two more triangles, by bisecting its longest edge.

3. The Implementation

GLOBEtrotter was designed to achieve the three steps outlined in section 2.1. These steps will be outlined in order.

3.1. Terrain Data Collection

I used the GLOBE dataset as my elevation data. That data has the following characteristics, as quoted from their web page:

The Global Land One-Kilometer Base Elevation (GLOBE) digital elevation model (DEM) is a global data set covering 180^o West to 180^o East longitude and 90^o North to 90^o South latitude. The horizontal grid spacing is 30 arc-seconds (0.008333... degrees) in latitude and longitude, resulting in dimensions of 21,600 rows and 43,200 columns. At the Equator, a degree of latitude is about 111 kilometers. GLOBE has 120 values per degree, giving GLOBE slightly better than 1 km gridding at the Equator, and progressively finer longitudinally toward the Poles.
The horizontal coordinate system is seconds of latitude and longitude referenced to World Geodetic System 84 (WGS84). The vertical units represent elevation in meters above Mean Sea Level. The elevation values range from -407 to 8,752 meters on land. In GLOBE Version 1.0, ocean areas have been masked as "no data" and have been assigned a value of -500.

The GLOBE dataset appears to be newer than the GTOP030 dataset, and had a more transparent file format.

3.2 Terrain Data Reformulation

We wish to reformulate our data into something that lends itself to LOD rendering. This means associating two pieces of data with each sampled elevation, and saving to a file that contains both elevation data and our new data.

(Remember that each elevation sample represents a potential midpoint of a right triangle. Inserting a midpoint means subdividing a triangle. When I refer to "the associated triangle" of an elevation sample, I'm referring to the triangle which has that midpoint.)

Each of our two pieces of data answers different questions for us, as follows:

How bad is the local approximation of this elevation sample? Put another way, if the corresponding triangle and all its children were subdivided to the most refined mesh, how much better would the geometric fit be? This question does not relate to the viewpoint, but rather to the geometric fit of the model over the terrain.
What scope does this sampled elevation have? For example, if the world were flat, and divided into two triangles, you might say that currently represented points have a lot of land associated with them. Inserting a point would affect a lot of geographic area, and is desirable. This represents a view-dependent part of the equation.

The first question can be answered by associating an elevation error with each sampled elevation. It is the maximum of the error of the corresponding triangle, and the elevation errors all of its subtriangles.

The second question, which addresses the scope of our sampled elevation, can be addressed by associating a radius with each sampled elevation point. The corresponding sphere, centered on that elevation point, should be big enough to hold the the points in all the subtriangles of the point's associated triangle.

3.3 Fast Terrain Rendering: what's fast, and what could be faster?

Once our model is tessellated into triangles, rendering these triangles is not too difficult; rendering them quickly can be a challenge, however. I have found my implementation to be reasonably fast, given its adaptive tesselation and view-frustum culling. However, there's always room for improvement.

The next sensible optimization, which I didn't have time to implement, is triangle stripping. Instead of sending 3 vertices per triangle to the graphics card, it's possible to send less by giving it a zig-zag pattern of vertices. By sending less vertices, we can get better performance.

The technique I used (to make for more contiguous disk access) is different than Lindstrom's, and although it's simpler, I suspect it is slower. I'd like to better understand the data layout that he suggests in [1].

References

Anyone interested in these topics should definitely read the following:

[1] Peter Lindstrom and Valerio Pascucci, "Terrain Simplification Simplified: a General Framework for View-Dependent Out-of-Core Visualization," in IEEE Transactions on Visualization and Computer Graphics, 8(3), pp. 239-254, July-September 2002.

[2] David Luebke, Martin Reddy, Jonathan D. Cohen, Amitabh Varshney, Benjamin Watson, Robert Huebner, Level of Detail for 3D Graphics, Morgan Kaufman, San Francisco, CA, 2003.

[3] Mark A. Duchaineau, Murray Wolinsky, David E. Sigeti, Mark C. Miller, Charles Aldrich, and Mark B. Mineev-Weinstein, "ROAMing terrain: Real-time optimally adapting meshes," in IEEE Visualization '97, Roni Yagel and Hans Hagen, Eds., Phoenix, Arizona, Nov. 1997, pp. 81-88, IEEE.

Credits

I'd like to thank my teacher, Lucia Lovison, who taught the class for which this work was done.

Generated on Sun Mar 23 14:37:05 2003 for GLOBEtrotter by

1.2.15

	Top Down	Bottom Up
Basic Idea	Divides the terrain up hierarchically, from the top down.	Simplifies the terrain from the most detailed data set to one or more simple versions. A lack of hierarchy opens up the question, "where should we refine next?"
Image Analogy	This is like resizing an image by resampling it: fast, but lacking in quality.	This is like resizing an image by filtering it: slow, but accurate.
Advantages	Convenient retesselation of the terrain, meaning that view-dependent LOD is easy.	Provides a better fit to the terrain, with less polygons.
Disadvantages	Retesselation takes time, and may not provide the best fit to the terrain.	Does not intuitively lend itself to view-dependent LOD rendering, because of the lack of hierarchy.