Stephanie Smullen

Computer Science and Engineering

Stephanie-Smullen@utc.edu

Slides are available at
zog.utc.edu/~vislab/Terrain/Part1.htm

Terrain Visualization: Data and Programming

• Heightfields
• Texture drapes
• Coordinate systems
• File formats
• Simple display software
• Simple programming example
• Programming issues
• 3D game engines

Data structures for storing surface elevation data

• Heightfields (Heightmaps) ⇒ a rectangular or raster image with 1 channel of information -- the height
• a two-dimensional grid - like a bitmap - except values represent elevation instead of color
• Two basic parts
• dimensions - number of samples across and down
• height values (aka, sample, elevation value) in a grid according to these dimensions
• like a bitmap - more samples ⇒ greater resolution

Data structures for storing surface elevation data (cont.)

• Polygonal or triangular 3D mesh
• collection of vertices, edges and faces
• many possible formats (Wikipedia summary)

Heightfields - Advantages

• efficient storage for representing lots of tiny undulations in a landscape
• can use 2D bitmap interfaces for editing
• can be converted to a polygonal mesh
• well defined 2D topology makes it easy to texture or "paint" heightfields by projecting the bitmap onto the groundplane
• some texturing issues

Heightfields - Disadvantages

• no 2D location in the heightfield can have more than one height value associated with it
• not possible to model rocks, bridges, caves, or terrain with slopes more than 90 degrees

A simple heightfield raster image

Interpreted as heights

Sources of heightfield data

• The three layer "cake" was hand generated for program testing
• Any data that could be expressed in a 2 way contingency table
  
  

  Dissertation	Tier 1	Tier 2	Tier 3	Tier 4
  Theory, History	100	148	91	136
  ....
  Business, Finance	58	60	44	58

  • School tier column - horizontal, dissertation category row - vertical, frequency = height value
• Random height values
• Function defined height values

Sources of heightfield data (cont.)

• Any 2D bitmap
• Grey scale -- black ⇒ 0 to white ⇒ maximum height
• Color -- requires a color mapping -- blue could be 0, red could be maximum height
• HLS (hue, lightness, saturation) easier to use than rgb (red, green blue)
• Terrain renderers -- Terragen
• Many game engines include heightmap and texture map generators
• CryEngine, Far Cry level editor, Crisis
• Electron toolset (Neverwinter Nights)

Sources of heightfield data (cont.)

• Real world terrain
• Proprietary mapping information
• US Department of Agriculture's Geospatial Data Gateway
• provides multiple resolution Digital elevation models available by US county, or 1:24,000 scale topoquad index
• for US only
• US Geological Survey Seamless National Map
• allows user to download digital elevation models, hillshade, and imagery using interactive web mapping application
• download items by drawing an area of interest

USDA site

Select "Get Data"

Select "Select "Quick County" - enter Albemarle, VA

Preview the 30 meter Charlottesville quad file

Since there is no format choice, continue to step 4

Enter information in step 4, and go to step 5 confirmation

Place order

Receive email, and click link to download

Your Gateway order 915893 has been processed and is ready for download.

.....

Ordered Items:
National Elevation Dataset 30 Meter (60 meter AK)
Size: 97.86 megabytes (9 files). Download compressed size: 80.00 megabytes (2 maps).
ftp://anonymous:915893@gateway2.ftw.nrcs.usda.gov/Gateway/915893/elevation_NED30M_915893_01.zip

Click on the link to download. Ensure the link is complete because some it may be on subsequent line(s).
Total data package size is 97.86 megabytes (80.00 megabytes compressed)

Texture Drapes

• Heightfield converted to a polygon mesh - triangular or rectangular

Texture Drapes (cont.)

• The texture is subdivided similarly
• "decaled" (applied) to each face

This texture

Applied to the "cake"

A more reasonable texture gives

Concerns

Slopes > 30 or 40 degrees

• apparent distance between adjacent height values much greater in 3 dimensions than in 2
• pixels in the image noticeably stretched to provide coverage
• Possible solutions
• use a procedural (computer generated realistic representation) texture
• increase the texture resolution
• areas of moderate slope are 'overpainted' with 'more' pixels
• stretched appearance of steeper slopes still noticable

Concerns (cont.)

• texture each final heightfield polygon by mapping to its slope instead of groundplane
• edges where polygons meet are usually quite noticeable
• use a separate list of polygons for the steep areas - polygon edges will tend to show
• provide the renderer with a list of the heightfield points in all three dimensions, oversampled, and texture the terrain with individually painted polygons or other objects
  
  visually stunning results - significantly slower rendering

Other Considerations

Registration of image to terrain

• twinned GPS coordinates
• uv mapping -- optionally, artistically adjusted

Texture image blurring to protect privacy or security

Multiple resolutions to support LOD (level of detail)

Coordinate Systems

• GPS - degrees (0 to 360), minutes (0 to 60), seconds (0 to 60)
• Plain maps
• many older municipal maps -- feet and inches
• also historical maps

Coordinate systems: UTM (Universal Transverse Mercator Grid)

• world divided into 60 north-south zones -- each covering a strip 6° wide in longitude
• numbered consecutively beginning with Zone 1 (180° to 174° west longitude)
• eastward to Zone 60 (174° to 180° east longitude)

US UTM zones

US 48 States

UTM (cont.)

• in each zone - coordinates measured north and east in meters
• northing values are measured continuously from zero at the Equator, in a northerly direction
• to avoid negative numbers for locations south of the Equator,Equator assigned a northing value of 10,000,000

UTM (cont.)

• central meridian through the middle of each 6° zone is assigned an easting value of 500,000 meters
• values to the west of this central meridian are less than 500,000; to the east, more than 500,000

See USGS fact sheet

Terrain file formats

• DEM
• DRG
• DLG
• DOQ
• SDTS
• GeoTIFF
• TIN
• MRSID
• JPG2000

DEM (Digital Elevation Model) files

• USGS (US Geological Survey) has 5 basic types of elevation data
• 7.5-minute DEM corresponds to the USGS 7.5-minute topographic quadrangle map series for all of the United States
• 30-minute DEMs provide coverage for the conterminous United States - correspond to the east or west half of the USGS 30- by 60-minute topographic quadrangle map series (1:100,000-scale)

DEM files (cont.)

• 1-degree DEM - National Imagery and Mapping Agency (NIMA), 1- by 1-degree units that correspond to the east or west half of the USGS 1- by 2-degree topographic quadrangle map series (1:250,000-scale)
• Alaska: 7.5 and 15-minute DEMs correspond to the USGS 15-minute topographic quadrangle map series in Alaska

DEM files (cont.)

• they are currently producted by interpolation from vectors or digital line graph (DLG) hypsographic and hydrographic data
• details are available at the USGS Factsheet
• A description of the DEM file format is here

10 and 30- minute DEM files

10 and 30- minute DEM files Close up

DRG (Digital Raster Graphics)

• most made by scanning published paper maps on high-resolution scanners
• raster image is georeferenced and fit to the UTM projection
• colors usually standardized to duplicate the line-drawing character of the published map
• average data set size of a 7.5-minute DRG is about 8 megabytes in TIFF v. 6.0 with PackBits compression
• More information is available from USGS
• the self extracting example (fsee_sample.exe) file
• extracts to these 3 files
• The mapping information is shown on the next page

DRG Example File

DLG (Digital Line Graphics)

• vector representations of cartographic information derived from USGS maps and related sources
• the following types of information may be available

Public Land Survey System (PLSS)	Township, range, and section lines
Boundaries (BD)	State, county, city, and other national and State lands such as forests and parks
Transportation (TR)	Roads and trails, railroads, pipelines, and transmission lines
Hydrography (HY)	Flowing water, standing water, and wetlands
Hypsography (HP)	Contours and supplementary spot elevations
Non-vegetative features (NV)	Glacial moraine, lava, sand, and gravel
Survey control and markers (SM)	Horizontal and vertical monuments (third order or better)
Man-made features (MS)	Cultural features, such as buildings, not collected in other data categories
Vegetative surface cover (SC)	Woods, scrub, orchards, and vineyards

• More information is available here

DOQ (Digital Orthophoto Quadrangle)

• computer-generated image of an aerial photograph in which the image displacement caused by terrain relief and camera tilt has been removed
• black and white (B/W), natural color, or color-infrared (CIR) images with 1-meter ground resolution
• USGS produces three types of DOQs
• 3.75-minute (quarter-quad) DOQs cover an area measuring 3.75-minutes longitude by 3.75-minutes latitude
• 7.5-minute (full-quad) DOQs cover an area measuring 7.5-minutes longitude by 7.5-minutes latitude
• Seamless DOQs are available for free download from the Seamless site. DOQs on this site are the most current version and are available for the conterminous U.S
• More information is available from EROS USGS site

SDTS Spatial Data Transfer Standard

• SDTS is to promote and facilitate the transfer of digital spatial data between dissimilar computer systems, while preserving information meaning and minimizing the need for information external to the transfer
• The seven parts of SDTS:
• Part 1 - Logical Specifications -- explain the SDTS conceptual model and SDTS spatial object types, components of a data quality report, and the layout of all SDTS modules
• Part 2 - Spatial Features -- a catalogue of spatial features and associated attributes, commomly used on topographic quadrangle maps and hydrographic charts
• Part 3 - ISO 8211 Encoding - for file exchange

SDTS Spatial Data Transfer Standard (cont.)

Part 4 - Topological Vector Profile -- efines how the SDTS base specification (Parts 1, 2, and 3) must be implemented for a particular type of data. The TVP limits options and identifies specific requirements for SDTS transfers of data sets consisting of topologically structured area and linear spatial features.

Part 5 - Raster Profile -- The Raster Profile is for 2-dimensional image and gridded raster data. It permits alternate image file formats using the ISO Basic Image Interchange Format (BIIF) or Georeferenced Tagged information File Format (GeoTIFF).

Part 6 - Point Profile -- The Point Profile contains specifications for use with geographic point data only, with the option to carry high precision coordinates

Part 7 -- Computer Aided Design and Drafting Profile -- specifications for an SDTS profile for use with vector-based geographic data

See the SDTS site for more information

Working with SDTS Files

• SDTS++ is a C++ toolkit for SDTS files
• Available from the USGS site
• sdts2dem Translator for SDTS DEM files to "native" DEM format
• Available from the University of Arizona site

Example SDTS Files

• This example SDTS file (174KB)
• Unzips into 19 files here
• Running sdts2dem
  
• Produces the Example.dem file
• The first few bytes of the file are shown in word wrap on the following page

East Chattanooga DEM file records

East Chattanooga DEM viewed with 3dem

NED (National Elevation Dataset)

• USGS no longer offers DEM or STDS files from their site
• NED files that are a combination and refinement of DEM and other data are updated regularly
• This Fact Sheet describes the data
• We looked at retrieving this data earlier
• The 30-meter file from Albemarle County, VA Albemarle County, VA
• Unzips into these 9 files
• For the purpose of web display -- Irfanview was used to convert the tiff file to png

The geographic information in the tiff files

GeoTiff files

• GeoTIFF represents an effort by over 160 different remote sensing, GIS, cartographic, and surveying related companies and organizations to establish a TIFF based interchange format for georeferenced raster imagery
• More information is available from the GeoTIFF site
• Libgeotiff is an open source library normally hosted on top of libtiff for reading, and writing GeoTIFF information tags
• The SVN repository is here

Other geographic data file formats

• TIN - Triangulated Irregular Network
• ESRI data format -- see this description
• MrSID - multiresolution seamless image database
• patented by LizardTech for encoding of georeferenced raster graphics, such as orthophotos
• JPG2000 - new wavelet compression format -- many files are delivered in this format. See the jpeg.org site

Simple display software

These are freeware/open source programs that are useful for viewing a variety of terrain files
• dlgv32 Pro is available here
• Open DLG, DEM and DRG files
• Limitied version of commercial software Global Mapper
• Free viewer Terra Explorer
• Microdem -- is a freeware mapping program from Peter Guth at USNA available here
• A viewer for the Mac is macdem
• A favorite of mine is 3dem

Program to read a simple DEM file

• The C++ class DemFile reads a DEM file
• The header information is stored in the C++ class DemHeader and the file information in the C++ class DemRecords

Programming issues - Ragged corners

• when working with non-"seamless" data set be aware that the corners (often lower left, upper right) are ragged
• this is the result of mapping a sphere onto a flat polygon

DEM Quad Format

Programming issues - Gridding

important problem with triangle-mesh heightfields is the blocky or aliased appearance of slopes, usually those nearest to the viewer - worse in areas of significant change in slope

• heightfield is composed of discrete samples so any digital image viewed close enough will exhibit 'jaggies'

• Phong shading is commonly employed to overcome gridding
• each component triangle is lit by using an average of the normals of its vertices across its surface to accurately determine the amount of reflected light

Programming issues - Gridding (cont.)

• ultimate solution is to increase the heightfield's resolution
• choose a resolution based on the expected highest resolution of the device the heightfield will be rendered to
• also take into account how closely the heightfield will be viewed
• it may be practical to use a separate, smaller heightfield for close-ups

Programming issues - Gridding (cont.)

• another popular solution is to use nonlinear sampling
• Renderman PatchMesh objects treat elevations as node points in spline curves, forming smooth spline patches instead of flat triangles-- since the spline patches must be tesselated this does slow rendering
• Terragen uses fractal subdivision - each heightfield triangle is broken into more and smaller triangles. Produces illusion of greater surface detail, but the tesselation slows rendering down
• other variations on displacement shading (creating more geometry than actually exists) are possible
• to improve the appearance of the generated areas, some kind of material - auxiliary texture - map is used to blend the materials smoothly, so that adjacent heightfield transitions evenly

Programming issues - Efficient Rendering of Heightfields

Simplest method is to build triangle mesh of all the points available BUT, you'll end up with very poor rendering performance

Alternative, Implement Level of Detail (LOD) techniques to render terrain with just enough data points

two-step process - draw only that which is truly visible (visibility determination) and level-of-detail management (LOD rendering)

• LOD management exploits the fact that heightfield cells farther from the eye occupy fewer screen pixels when drawn
• approximate several distant cells with just one that covers them all to produce an appropriate illusion
• this often work well when the terrain is mostly flat
• a series of textures - mipmap - can provide details at a variety of visibilities

Programming issues - Efficient Rendering of Heightfields

Mesh without LOD	Mesh with LOD

Programming issues - Efficient Rendering of Heightfields - Solutions

Progressive Meshing

• Hugues Hoppe (Microsoft Corporation)
• build a data structure that allows rapid extraction of different level of detail meshes that represent a good approximation of the target triangle mesh
• progressive meshing allows smooth transitions among levels of detail
• directed toward dynamic LOD
• He has many references available here

Programming issues - Efficient Rendering of Heightfields - Solutions

Multiresolution (or multi-scale) techniques make it possible for Web-based GIS applications to access large dataset.

• Kai Zu, Xiaofang, Xuemin Lin, "Direct mesh a multiresolution approach to terrain visualization," ICDE,pp.766, 20th International Conference on Data Engineering (ICDE'04), 2004
• Available from IEEE CS Digital Library

Programming issues - Efficient Rendering of Heightfields - Solutions

Real Time Optimally Adapting Meshes

• ROAM developed by Mark Duchaineauy and others operates on a binary tree constructed from the triangular mesh
• tries to tesselate the heightfield into the minimal number of triangles for the current camera location
• This structure is used, along with two priority queues, for incremental refinement of the scene
• See this site for more information or the ROAMing Terrain paper

Programming issues - Efficient Rendering of Heightfields - Solutions

Stateless One-pass Adaptive Refinement

• This algorithm, called SOAR, developed by Peter Lindstrom, Valiero Pascucci and others combines the techniques mentioned above but extends them by recursively dividing the triangular mesh using longest-edge bisection. Its main features are its adaptive refinement algorithm along with optional frustum culling and on-the-fly triangle stripping based on projected error.
• See SOAR Terrain engine site

Programming issues - Efficient Rendering of Heightfields - Solutions

classic visibility determination algorithm is the quadtree

• See Thatcher Ulrich's article here
• builds a hierarchical set of bounding boxes where the heightfield's overall bounding box is recursively subdivided into four smaller boxes, repeatedly, until the smallest boxes each contain only four cells

Programming issues - Efficient Rendering of Heightfields - Solutions (cont.)

if you know that a given box isn't visible - you know that all of its child boxes (and the heightfield cells within them) aren't visible

test the visibility of the largest box and recurse through its children, skipping over the invisible ones

quadtrees are used with LOD management to determine the heightfield cells and texture needed

Programming issues - Efficient Rendering of Heightfields (cont.)

quadtree concerns

• takes an enormous amount of memory - as much as some multiple of the heightfield itself
• suffers from noticeable "popping" - triangles abruptly changing size and position as you move nearer and farther from an approximated set of cells
• poor quadtree LOD implementations also suffer from gapping, where the edges of adjacent triangles fail to meet correctly

3D game engines

• Game engines rely on terrains for realism
• they can be used to develop learning games and display models
• open source
• OGRE
• Irrlicht
• Crystal Space
• Blender
• Open SceneGraph
• commercial
• Torque

Bats using the Irrlict game engine

• as a particle stream displayed on a grid
• with DEM terrain and bat texture

Questions?

Stephanie-Smullen@utc.edu

Web pages research and personal