TERRAIN RENDERING FOR A GEOGRAPHICAL INFORMATION SYSTEM

Paul Coddington

Northeast Parallel Architectures Center

February 1996

THE INTERACTIVE JOURNEY

Terrain Rendering for a GIS  The Interactive Journey

The Living Schoolbook

The Living Schoolbook Project is a joint project between the Northeast Parallel Architectures Center (NPAC), the School of Education at Syracuse University, NYNEX, and Columbia University, on the application of high performance computing and communications (HPCC) to K-12 education.

Several pilot projects involve designing multimedia educational applications, including interactive simulations, which will be hosted on computing facilities at NPAC and delivered to schools in Syracuse and other parts of New York state via the NYNet ATM network.

This is a prototype for the use of the National Information Infrastructure (better known as the Information Superhighway) for education.

The Interactive Journey

As a part of the Living Schoolbook project, NPAC is developing a flight simulator interface to spatially-referenced multimedia information about New York state. This is an example of a Geographical Information System (GIS).

Students will be able to take an interactive, virtual flight over dynamically rendered 2D and 3D views of the state, select landmarks or towns, and obtain multimedia information about these places by clicking on an area, which will display information on that area via a Web browser.

This method could also be used for interactive journeys over other areas, such as Mars.

Application Requirements

The goal is to provide realistic, real-time, interactive 2D or 3D renderings of the terrain of a particular area such as New York State or Mars.

The data sets are very large and must be stored on a high-end server. The results are viewed on client computers that access the server over the Internet.

3D rendering is very compute-intensive and data-intensive. The amount of processing power available on the server and clients, and the amount of bandwidth available on the network connecting them, may vary substantially.

The basic requirement for the terrain rendering application is that it be portable and scalable. The resolution and frame rate of the application should gradually be reduced as the computing and communication resources are reduced.

Paul Coddington, NPAC, paulc@npac.syr.edu  February 96, CPS713-TR-4

WEB TECHNOLOGIES

Terrain Rendering for a GIS  Web Technologies

Old Technologies for the Interactive Journey

Initially the Interactive Journey used standard Unix client/server technologies running over the Internet:

• A graphical user interface (GUI) written in Tcl/Tk, running on the client.

• Unix socket-based client/server program to transfer data and images from a server to the client.

• A scalable parallel rendering program, running on a high-performance server, to generate real-time 3D images that are sent to the client.

• Spatially referenced information is displayed in a Web browser run by remote control using a Netscape API.

New Technologies for the Interactive Journey

The new implementations of the Interactive Journey use recently-developed Web technologies:

• Java (for 2D journey) and VRML (for 3D journey) are used to provide the user interface running on the client.

• Transfer of data and images is done using standard HTTP requests (could also be done using sockets in Java).

• 3D rendering is done on the client using a VRML browser.

• Information is displayed in a Web browser using hyperlinks from Java and VRML displays.

Comparison of Old and New Technologies

Old: Custom GUI programs (and Tcl/Tk) have to be installed on each client, users have to find and run the standalone program. New: Java applet or VRML viewer are automatically run by just clicking on a hyperlink in the Web browser.

Old: Software is specific to a particular operating system. New: Software is completely portable.

Old: Have to write routines for passing data over networks using sockets and custom client/server programs. New: Data is passed using standard HTTP protocols.

Old: Need to run a dedicated server for the data. New: Data is served from a standard Web server.

Old: Need to write complex programs to do the rendering. New: Uses built-in rendering routines in Java and VRML.

Client-side vs Server-side Rendering

In the near future, personal computers will have powerful graphics acceleration hardware, to support computer games. In that case, client-side rendering (such as VRML) should be used.

However, current personal computers cannot do real-time 3D rendering of large scenes, and do not have hardware support for crucial aspects of terrain rendering such as texture mapping. In this case, it may be more efficient to do the rendering on a high-speed server, and just pass rendered images to the client.

Server-sided rendering can only be used for a very small number of “priviledged” clients without degrading performance. Client-sided rendering has no such restrictions, but the quality of the rendering may be reduced due to insufficient hardware resources on the client.

Some combination of client and server computing, such as on-the-fly preprocessing by the server, may be the best option.

Paul Coddington, NPAC, paulc@npac.syr.edu  February 96, CPS713-TR-9

Networking Issues

Require about 20 frames per second for realistic animation. A typical frame size would be 640 × 480 pixels, and ideally each pixel would have 24 bits of color information. This requires 150 Mbits per second of bandwidth (an order of magnitude larger than Ethernet speeds) to send the raw images from a server where it is rendered to a client for display.

The alternatives are to use on-the-fly image compression, or to send polygon data for the scene (or part of the scene) to the client, and do the rendering on the client, which is the approach used in VRML.

Even VRML data is quite large, since current implementation uses ASCII data format and no compression. However it is possible to use standard text compression, such as gzip.

Image Compression

Images need a lot of data, and animated images hog even more bandwidth, so they must be compressed. JPEG compression has become the standard for images, MPEG for video. Other methods include Wavelet and Fractal compression.

JPEG decreases image quality (i.e. is lossy), but at compression ratios of 10:1 the image is virtually indistinguishable from the original, and generally 20:1 looks fine.

However JPEG compression algorithms are too slow for real-time animation (about 0.2 seconds to compress a 320 × 200 image on a DEC Alpha). Fast parallel or hardware implementations could be used. Decompression is fast, and cheap special purpose chips will soon become standard features.

JPEG compression is used for 2D images, and can even be done on-the-fly for accessing arbitrary sections of large satellite images.

Paul Coddington, NPAC, paulc@npac.syr.edu  February 96, CPS713-TR-11

GEOGRAPHICAL INFORMATION SYSTEMS

Terrain Rendering for a GIS  Geographical Information Systems

Introduction to GIS

The United States Geological Survey (USGS) defines a Geographical Information System (GIS) as

“a computer system capable of assembling, storing, manipulating, and displaying geographically referenced information, i.e. data identified according to their locations.”

Many types of geographical data can be used:

• Elevation

• Satellite image

• Digital line graph

• Land use / Land cover

• Geographic place names Integrating these different data sets is a non-trivial problem.

Paul Coddington, NPAC, paulc@npac.syr.edu  February 96, CPS713-TR-13

Terrain Rendering for a GIS  Geographical Information Systems

Elevation Data

Elevation data is available from USGS as a Digital Elevation Model (DEM). This is obtained by digitizing contour lines on USGS topographical 1:250,000 scale maps. The data is set up as points on a grid covering a 1 degree quadrant with 90m resolution. 30m resolution data is being developed, but currently is only available for about half the US.

Data for New York state requires about 500 Mbytes, for the entire US it is about 10 Gbytes. This will increase 9-fold for 30m resolution data.

The US Defense Mapping Agency has 90m resolution data for the entire world, but it is classified. The only available world-wide data has 1km resolution, which is the same as is available for Mars!

Terrain Rendering for a GIS  Geographical Information Systems

Example DEM Data

2D image, with brightness increasing with height.

3D image with shadowing.

Digital Elevation Model (DEM) data for part of the Cascade mountains in Washington state.

Paul Coddington, NPAC, paulc@npac.syr.edu  February 96, CPS713-TR-15

Satellite Image Data

Landsat satellite image data for most of the earth is available at 30m resolution, in several spectral bands. Satellite image data at better than 1 km resolution is also available for Mars and Venus from NASA JPL.

This data first has to be preprocessed to correct for distortion caused by varying elevations, using the DEM data, so that it becomes like a 2D map. Then the values from the different spectral bands must be combined to create a realistic true-color RGB image. Both of these pre-processing steps are quite tricky.

Once the 2D images are created, they can be used directly for a 2D visualization of the terrain, or “draped” over the polygons created by the DEM data to make a realistic 3D image.

Terrain Rendering for a GIS  Geographical Information Systems

Example Satellite Image Data

Landsat image of Cape Cod

Paul Coddington, NPAC, paulc@npac.syr.edu  February 96, CPS713-TR-17

Digital Line Graphs

Digital Line Graphs (DLG) are made up of vector data marking objects such as roads, waterways, city, county, state and country borders.

Digital line graph of roadways

\underline{Other Data}

Land use / Land cover data is available from USGS. Areas are classified into 92 categories of land use (human activity such as residential, agricultural, etc) and land cover (vegetation, water, etc).

Geographic place name data is available from USGS, listing all known places, features and areas in the US that are identified by proper names. The database contains over 2 million place names referenced by geographic position.

Digital line graph, land use / land cover, and and geographic place name data could be overlaid onto satellite and elevation data.

OVERVIEW OF COMPUTER GRAPHICS

Terrain Rendering for a GIS  Overview of Computer Graphics

Computer Graphics

The goal of computer graphics is to show a virtual world. This virtual world is composed of many different objects. A rendering program takes the computer models of the objects and converts them into an array of pixels that are rendered on the computer screen to give an image of the virtual world. The virtual world in this talk consists of two milk cartons.

Object Representation

How the objects are represented in the object database has a major impact on the rendering performance, the quality of the generated image and the time needed to construct the virtual world database.

The milk cartons can be represented in two ways. In the first method, the milk cartons are represented as a milk carton object. The scene designer need only specify the dimension, the texture map and the color. Each object in turn is composed of number of rectangular and triangular 3D sub-objects. The sub-object is positioned relative to an anchor point of the object.

These objects are analytically defined, so there is no limit on resolving the details of the object. The resolution of the object is bounded instead by the surface texture map.

Polygon Representation

The second method of modeling an object is by polygons. Generally, 3 or 4 vertex polygons are used. Triangles are more often used because all vertices of a triangle are coplanar, so the polygon will have only one normal, which greatly simplifies some rendering computations such as shading. The scene designer will construct an object one polygon at a time, and then define the surface texture and the color for each of the polygons.

The motivation for defining an object by polygons is flexibility of the object representation. Each polygon is represented by a fixed set of points and edges joining the points. These points can be arbitrary positions in 3D space, so deforming an object is a relative simple task (e.g. a filled milk carton’s side can be slightly warped).

Terrain Rendering for a GIS  Overview of Computer Graphics

The Rendering Process

Rendering a 3D image requires the following computational procedures:

1. Transformation

2. Hidden surface removal

3. Clipping

4. Rasterization

Transformation

The positional placement of the objects relative to the viewer is done by transformations. The transformation process includes translation, rotation and scaling. Each individual transformation can be represented as a 4x4 matrix (one extra dimension for non-linear perspective scaling). These matrices can be multiplied together to form one final transformation matrix, which is used to transform the objects. Transformation is used to place the virtual world in the viewer’s perspective.

An analytically defined object is moved by transforming the anchor point of the object. The transformation can therefore be done to the object as a whole, and thus takes time O(#objects). Transformation of a polygon-based object requires computation at each vertex, and thus takes time O(#vertices).

Hidden Surface Removal

Even when an object is within the field of view, it may still not be visible to the viewer – for example, an object located behind a closed door. These have to be eliminated from the object rendering list.

Hidden surface removal could also be done later in the rendering process (during rasterization), by just having objects closer to the viewer overwrite objects further away. However, this wastes considerable computation in unnecessary rendering of these hidden objects. It is cheaper to identify and remove them earlier in the rendering procedure, when the work is proportional to the number of objects rather than the number of pixels.

For polygon-based rendering, hidden surface removal can be done very fast by just culling the back-facing polygons.

\underline{Clipping}

Clipping is done to eliminate objects (or parts of objects) that are outside the field of view, for example, objects behind the viewer. Clipping also speeds up the rendering process since the eliminated objects do not need any further processing.

Clipping can also be used to eliminate unwanted objects, for example those that are too far away to have enough effect on the scene to warrant the amount of computation required to include them.

Rasterization

Rasterization is done to transform the data represented by the object database into a pixel-based image. Texture mapping, color computation, shading and anti-aliasing are done at this stage.

For a polygon based object, a scanline algorithm is commonly used to render the final image. The pixels are scanned a line at a time and their color is determined from the polygons that contribute to that part of the screen.

The colors of the polygons are specified either at the vertices, in which case interpolation is used to find the pixel color, or by a texture map, which can be transformed into the appropriate pixels.

A Z-buffering algorithm is used to ensure that objects closer to the image (along the z direction) are rendered last, so that partially obscured polygons are overwritten (as they should be).

PARALLEL RENDERING

Terrain Rendering for a GIS  Parallel Rendering

Parallel Rendering Algorithms

The rendering pipeline remains the same as the sequential algorithm, with polygon calculations (transformation, clipping, hidden surface removal) and pixel calculations (rasterization).

Both types of calculation are completely independent, so can trivially parallelize over polygons or pixels. However there are the usual problems of load balance and communication overhead that need to be overcome to get good performance, which is particularly crucial for real-time animation.

One advantage in doing animations is that successive frames are very similar. This allows dynamic load balancing, since the computational load for current frame can be used to load balance the next frame.

Problems with Parallel Rendering

Load balance is needed for the polygon calculation. A scattered or cyclic distribution may work well, or else do dynamic load balancing by using data on work distribution for previous frame to load balance the next frame.

Parallel overhead is incurred due to the two different data decompositions used (polygon domain and pixel domain). Since polygons are irregular they will overlap pixel regions on different processors. Polygons can be cut at processor boundaries.

Communications overhead must be minimized since a frame has to be rendered and displayed every 40 msec for real-time animation. Cannot afford too much communication if latencies and communications times are in the msec range. Overlap calculation and communication?

Ray-Based Algorithms

There are also parallel rendering algorithms based on raytracing and raycasting, which follow individual light rays to or from the viewer. These are inherently parallel (each ray is independent), however they require a copy of the entire dataset on each node, or else lot of costly data movement.

NASA JPL has developed a parallel “ray-identification” program using a method of this kind. This independently transforms pixels into the view plane, and uses Z-buffering for hidden surface removal. Scattered data decomposition is used for load balancing.

These methods produce high-quality results but are very computationally intensive. The JPL program has been used to make movies of simulated flights over Venus, Mars, and the Earth. It can be run interactively (1.5 fps) on a 256-node Intel Paragon.

TERRAIN RENDERING

Terrain Rendering for a GIS  Terrain Rendering

Rendering of Terrain

Terrain rendering is a special case of 3-D volume rendering:

• The objects are static – only the viewer moves.

• There is only a single simply connected object – the land surface.

• A terrain model is basically a 2-D surface with a variable elevation in the third dimension, which is much simpler than a general 3-D problem (sometimes called a 2.5 dimensional problem).

So there are a number of optimizations and simplifications that can be made for a terrain rendering program that cannot be done for a general purpose 3D rendering program.

Here we outline some of the techniques used to render terrain. Various parts can either be implemented in a terrain rendering program or preprocessor or done by the VRML rendering engine.

Paul Coddington, NPAC, paulc@npac.syr.edu  February 96, CPS713-TR-39

Portability and Scalable Rendering

For best results, the rendering must be done on a high-performance computer or a computer with graphics hardware. However the renderer should be portable, so it will run on parallel computers with different numbers of nodes, high-end graphics workstations, and even personal computers.

Our strategy is to make a scalable algorithm that will always run in near real time, by (gracefully) sacrificing image quality when there is less compute power available. This can be done relatively easily using polygon-based rendering by coarsening, i.e. reducing the number of polygons used.

This method requires handling two interesting problem areas:

• Keeping a constant frame rate for different computers and different scenes

• Creating optimal coarsenings of the polygons

Paul Coddington, NPAC, paulc@npac.syr.edu  February 96, CPS713-TR-40

Portability and Scalable Rendering

For best results, the rendering must be done on a high-performance computer or a computer with graphics hardware. However the renderer should be portable, so it will run on parallel computers with different numbers of nodes, high-end graphics workstations, and even personal computers.

Our strategy is to make a scalable algorithm that will always run in near real time, by (gracefully) sacrificing image quality when there is less compute power available. This can be done relatively easily using polygon-based rendering by coarsening, i.e. reducing the number of polygons used.

This method requires handling two interesting problem areas:

• Keeping a constant frame rate for different computers and different scenes

• Creating optimal coarsenings of the polygons

Paul Coddington, NPAC, paulc@npac.syr.edu  February 96, CPS713-TR-41

Terrain Object Representation

A terrain object is defined by an elevation (height) field and an image. The elevation field encodes information as elevation y for a specific (x, z) coordinate. The image gives the color associated with the coordinate. This information can be obtained from a digital elevation model (DEM) and a satellite image of the terrain.

A terrain is a simply connected surface (i.e. no disjoint sections), so terrain rendering is a special case of volume rendering, sometimes described as 2.5-D rather than 3-D. This allows some optimizations to be used in the rendering process.

The terrain data set is stored as a number of two dimensional grids. Each grid contains a subsection of the terrain data set. The data is stored as triangular polygons made by triangulating the square mesh used as the basis of the DEM.

Polygon Representation

The terrain data can be stored at different levels of resolution. Coarser resolution polygons can be used for terrain further from the viewer. This greatly reduces the computational requirement. Can do this very simply by just using a coarser mesh, but may be more effective to use an adaptive scheme with a very coarse mesh for flat regions (lakes, plains) and a less coarse mesh for mountains.

Shading and Shadowing

Because the light source remains constant and terrain is virtually non-reflective, shading and cast shadows do not change from one view to another. Thus a significant portion of the rendering process, the computation of shadows and shading, can be done in a preprocessing step.

Shading can be modeled as two separate processes:

Diffuse light is uniformly reflected from surfaces, i.e. does not depend on the angle of the surface to the viewer, only to the light source. Ambient light is radiated from all the objects in the scene, and is independent of the light source.

Diffuse light is blocked in areas of shadow, so must compute the areas in shade (occluded from the light source). Ambient light is not affected by shadowing.

Paul Coddington, NPAC, paulc@npac.syr.edu  February 96, CPS713-TR-44

Shading Model

Different materials have different parameters for ambient and diffuse reflection, which are used in a standard Lambertian shading model to calculate the intensities for ambient and diffuse light.

Example of a shaded terrain.

Paul Coddington, NPAC, paulc@npac.syr.edu  February 96, CPS713-TR-45

Shading Model

Ambient light I = I_{a}k_{a}
Diffuse light I = I_{p}k_{d} cos θ = I_{p}k_{d} \overline{N} · \overline{L}
Together I = I_{a}k_{a} + S_{i}I_{p}k_{d} \overline{N} · \overline{L}

I = total intensity
I_{p}(I_{a}) = diffuse (ambient) intensity
k_{a} = ambient reflection coefficient
k_{d} = diffuse reflection coefficient
\overline{N} = normal to the surface
\overline{L} = position of the sun
θ = angle between sun and normal
S_{i} = 0 if in shadow
= 1 if not in shadow

Terrain Rendering for a GIS  Terrain Rendering

\underline{Shadowing}

A Z-buffer algorithm is used to calculate the area in shadow, which is identified by finding the back-facing polygons.