DEMScape 
Summary: This Lightwave plugin reads USGS DEM files and creates a Lightwave object that approximates the landscape. Instead of creating a large uniform rectangular grid of heights, this plugin allows the user to specify the number of points in the final object, then proceeds to optimize the landscape, creating an irregular triangulated Lightwave object that best approximates the original terrain. If you are using Lightwave 6.5 or Lightwave 7.0, you may also be interested in the TextureScape and ElevationModels plugins.
This plugin uses routines written by Michael Garland and Paul Heckbert, distributed as part of their public domain SCAPE Terrain Simplification software. The algorithms used in this software are described in their technical report titled "Fast Polygonal Approximation of Terrains and Height Fields" (Technical Report CMU-CS-95-181).
Digital Elevation Model (DEM) files can be conveniently converted into polygonal models simply using a rectangular, uniform mesh. However, most DEM files contain a very large number of height values, resulting in prohibitively large grid sizes. For example, most of the 1:250,000-scale (1-Degree) DEMs I am working with contain 1201 x 1201 data points, so a straightforward conversion to a triangular mesh would result in 2,880,000 triangles! Sub-sampling the data prior to creating the triangular mesh is one way to reduce the size of the polygonal model. However, sub-sampling still results in a uniform mesh of points that ignores the fact that most landscapes have large, fairly flat areas that can be approximated by large polygons.
Top view of a sub-sampled DEM
(20 x 20 points, 722 triangles)
This plugin uses a greedy insertion algorithm to create an
irregular triangulated object instead of a uniform mesh. This allows
for a higher density of triangles in detailed areas of the landscape
(such as mountains and coastlines), and far fewer triangles in the
large, flat areas. The algorithm starts with the most simplistic
triangulation of the data (2 triangles) and uses a multi-pass
refinement method to progressively build the final object. Each pass
locates the height value with the highest error in the current
approximation, and inserts that point into the triangulation. This
minimizes the errors in the approximation and also allows the user to
specify the total number of points generated, which is the criterion
used to terminate the algorithm.
Top view of a 400 point triangulated
irregular network (783 triangles)
The images below show a perspective view of a DEM landscape at full
resolution, the same landscape sub-sampled to 2 smaller resolutions,
and 2 triangulated irregular networks (TIN) created with the DEMScape
plugin, that contain the same number of points as the sub-sampled
examples. Click on each image to view a larger version.
 |
 |
 |
 |
 |
| Full resolution 1201 x 1201 pts. 2,880,000 tris. |
Sub-sampled 60 x 60 pts. 6,962 tris. |
TIN 3600 pts. 7,157 tris. |
Sub-sampled 120 x 120 pts. 28,322 tris. |
TIN 14,400 pts. 28,700 tris. |
Obviously, the TIN landscapes display more detail in the mountain regions than the corresponding sub-sampled grids containing the same number of points. And even though the final TIN contains only 1% of the total number of points in the full resolution landscape, it is a fair approximation of the original.
Currently, the working versions of the DEMScape plugin are for the SGI and Intel platforms. I have successfully (?????) compiled the code on the Amiga, however I get a startup error when trying to run the plugin. I cannot figure out what the problem is, so I have included a pointer to the Amiga version and its own version of the source code (SAS/C does not support templates, so I have expanded the classes that use templates into the necessary individual classes). If you can figure out what the problem is, I would love to hear about it.
To install DEMScape, just copy the demscape.p file into your Lightwave plugins directory. Run the Lightwave Modeler and choose Objects->Custom->Add Plugin. After you select the demscape.p plugin from the file requester, you should now find a DEMScape entry in the Objects->Custom pulldown menu.
Choose Objects->Custom->DEMScape and you will be presented with the following information requester.
Here is a brief description of the options:
During each refinement pass, a new point is chosen to be inserted into the landscape. The triangular network must be updated to include this new point, and DEMScape uses either a Delauney method or a data-dependent method.
Delauney triangulation is the faster method, but it makes no use of the heights of the vertices. It only attempts to create well-shaped 2D triangles, completely ignoring the 3D structures of the landscape.
Data Dependent triangulation provides more control over the approximation method but is slower than the Delauney method. The data dependent method generates a slightly better quality approximation because the topology of the triangulation is based on the 3D fit of the surface to the original input points.
This is the total number of points that will be present in the final triangulated landscape.
Each height value will be multiplied by this value before being inserted into the landscape. This gives the user a little control over the total height of the landscape, since no effort is made to read horizontal or vertical scaling information from the DEM file.
The following information requester is only shown if the Data Dependent triangulation method was chosen in the first requester. The Delauney triangulation method does not require any of this information, and skips directly to the Load DEM File requester.
Here is a brief description of the options in the Data Dependent Triangulation requester. For more information about these options, you will need to read the technical report referred to in the summary section of this page.
This parameter controls the algorithm's supersampling resolution. 0 results in infinite supersampling, 0.8 in moderate supersampling, and a very large number (such as the default) results in no supersampling. The lower the number, the more time it takes to generate the landscape.
Determines the quality and amount of the data dependent triangulation. 0 results in pure data-dependent triangulation, 1 results in pure shape-dependent triangulation, and any value in between results in a hybrid of the two. Hybrid methods tend to yield the best overall approximations.
Three different ways for computing the error between the data in the height field and the triangulated surface. I don't see much difference in the landscapes generated by this choice, but it's here for you to experiment with if you'd like.
The Load DEM File requester expects you to choose a USGS DEM file or an STM (Simple Terrain Model) file. For more information about these formats (or at least how much I cheat reading the USGS DEM format :-), refer to the File Formats section at the end of this document. I do not create the landscape to scale in either the horizontal dimensions or the height of the landscape (I leave that up to you by providing the height scale requester), and I definitely don't correct for the spherical mapping of the USGS data. I do not try to use Lightwave as a GIS system, so the DEM reader is very simplistic and just provides a minimum solution for getting the height data into Lightwave.
Well, that's it! If you have made it this far, DEMScape is probably showing you a progress monitor while it creates the TIN object in the foreground layer of Modeler. The landscape's polygons will be assigned the current surface value. Further reduction of the polygons in the object might be achieved by using Lightwave 5.0's Polygon Reduction tool (just a guess since I don't have Lightwave 5.0 for either the SGI or the Amiga).
Warning: The USGS DEM reader code in this plugin is not very robust, so there could easily be USGS DEM files that it does not handle well (or at all). However, most of my tests were done on the 1-Degree DEMs found at the USGS/EROS Data Center's ftp site, and this plugin worked well on everything I tried from that site. (Check out the graphical interface to the USGS/EROS ftp site). If you have found DEM files that can't be read by the DEMScape plugin, I would be interested in knowing where I could find the offending files. There is no guarantee I would make the plugin work for them, but I would consider trying to enhance the DEM reader code appropriately.
If you are interested in creating your own height field files for use with DEMScape, you should probably look at the information about the STM binary format, since it is a very simple binary format (each data point is a short integer) with a very simple header. The STM reader in DEMScape automatically handles both big-endian and little-endian integers, so the STM file can be created on any platform, and still be read by DEMScape on any other platform.
Here are some programs that have been written to convert various types of digital elevation data into STM format.
mdem2stm: This is a MicroDEM to STM converter for the Intel platform. MicroDEM is a microcomputer mapping program written by Professor Peter Guth of the Oceanography Department, U.S. Naval Academy. He has also created an inexpensive shareware program called DEMConverter that will read and write a wide variety of DEM formats, as well perform some DEM file manipulations such as merge, thin, and subset. The mdem2stm converter is intended to work with the MicroDEM binary output saved from either MicroDEM or from DEMConverter. You can get mdem2stm.zip (Intel platform only), convert the MicroDEM binary to STM, then create the Lightwave landscape object using the STM capability of DEMScape. Please see the enclosed readme.txt for instructions on how to use this DOS command line program, and the necessary steps to correctly orient the final landscape in Lightwave.
3D ARTIST magazine, Issues #37, #39 and #40, have tutorials on the use of MicroDEM with Lightwave and World Construction Set. There are links on the 3D ARTIST web page that describe the articles and the web supplements.
Robert Thompson assisted another Lightwave Mailing List member with using the GTOPO30 data at the USGS EROS Data Center. His message is an excellent example of how to use MicroDEM and mdem2stm to convert the data into a format that DEMScape can read. The information about using GTOPO30 data with DEMScape is included below. Thanks Robert!
sdts2stm: The USGS has made 7.5-Minute digital elevation data available for download from the US GeoData web page. The data is in SDTS format, and each dataset contains a number of files (each file of the dataset contains the same first 4 characters in the filename), each containing specific information about the elevation data. The sdts2stm.zip archive contains the Intel executable (and source) that will read the appropriate SDTS files and create an STM file for consumption with DEMScape (many thanks to Ernie Wright for providing the Intel version of this converter).
The program runs from a command line, and takes 2 arguments:
sdts2stm sdts_fileset stm_file
Where sdts_fileset is just the common first 4 letters of each of the files found in the SDTS dataset, and stm_file is the name you want to assign to the resulting STM file. For example, to convert the Sabino Canyon, Tucson SDTS dataset, use the following command:
sdts2stm 1171 sabino_canyon.stm
Now use DEMScape to load the resulting STM file, and it will proceed to convert the data into Lightwave points and polygons. However, to be oriented correctly, the resulting object will need to be stretched -100% along the Z-Axis, and then all the polygon normals need to be flipped. These steps can be done easily with the standard Modeler tools.
img2stm: MOLA (the Mars Orbiter Laser Altimeter) is an instrument currently in orbit around Mars on the Mars Global Surveyor spacecraft. Four different resolutions (from .25 degrees/pixel to .031 degrees/pixel) of MOLA data in PDS format can be downloaded from the web (download both the topography data file and the corresponding PDS Label file). The .img topography data can be converted to STM format using the program in the img2stm.zip archive. The archive contains C source code and an MSDOS command line program. You will also find the NASAView program to be a valuable tool to view the data, and locate x,y coordinates for cropping the data with the img2stm converter.
The img2stm command line converter is very simplistic, so you'll need to do a little preparation before you can use it. First, look at the PDS Label file for the data, and determine the size of the MOLA .img file. Look for the entries titled LINES and LINE_SAMPLES. The LINES entry will be the y size of the image, and the LINE_SAMPLES will be the x size of the image. Now run the NASAView program and Open the .lbl file to see the grayscale image of the topological data. If you want to only convert a smaller rectangular portion of the image, use the left mouse button and write down the x,y coordinates of the upper-left and lower-right corners of the rectangular portion.
Now you'll run the img2stm converter from an MSDOS command line. It requires quite a few arguments, since it allows you to crop the data for the conversion:
img2stm img_sizex img_sizey startx starty endx endy file.img file.stm
Remember that the startx, starty, endx, and endy parameters all start numbering at 0, so the endx and endy will be 1 less than the image sizes if you want to convert the entire img file. So for example, I'll use the .25 degrees/pixel topographic map, ieg025t.img, and this first command will convert the entire dataset to STM format:
img2stm 1440 720 0 0 1439 719 ieg025t.img ieg025t.stm
This next example uses the same dataset, but crops the data to the rectangular area determined by the coordinates 800,128 (upper-left corner) and 1154,447 (lower-right corner):
img2stm 1440 720 800 128 1154 447 ieg025t.img ieg025t_cropped.stm
The converter will inform you if any of the startx, starty, endx, and endy parameters are out of range, and it will not create the STM file.
Now use DEMScape to load the resulting STM file, and it will proceed to convert the data into Lightwave points and polygons. However, to be oriented correctly, the resulting object will need to be stretched -100% along the Z-Axis, and then all the polygon normals need to be flipped. These steps can be done easily with the standard Modeler tools.
vdem2stm: Great news for those of you that have Vistapro DEM files. Ernie Wright has written a Vistapro DEM to STM converter for both Intel and Amiga platforms. You can get vdem2stm.zip (Intel) or vdem2stm.lha (Amiga), convert the Vistapro binary DEM to STM, then create the Lightwave landscape object using the STM capability of DEMScape. Thanks Ernie!!
Credit goes to Robert Thompson for this example of how to use MicroDEM and mdem2stm to convert GTOPO30 DEM files into the STM format for use in DEMScape.
1) Open MicroDEM and go to Options. We'll set some preferences here.
2) Close and reopen MicroDEM.
3) Use mdem2stm to obtain the STM file. Then use DEMScape to load the STM into Modeler. Read the mdem2stm readme file, you'll need to stretch the object in Modeler a -100% in the Z, rotate 90 in the Y and flip the polys.