Data reduction in terrain modelling

Written by Paul Bourke
June 1994

A common characteristic of terrain modelling/rendering exercises is the vast amount of data involved. This is particularly severe where the spot height information is a result of some automated survey or when it results from digitised contours. In addition there are a number of activities which require very different levels of detail, for example the detail required for high quality renderings may be quite high. The information that a 3D modelling package can handle while retaining user interaction may be quite low. The need for multiple terrain representations can arise naturally in modelling applications, for example it may be necessary to acquire a more course terrain model for interactive modelling and substitute a more detailed version for final presentation. As with many computer based activities there is often a gap between what one might like to and what is practical given disk, memory, or processing resources.

There are two common representations for computer based terrain models. The first consists of a triangular mesh of polygons, this is normally the result from a triangulation process. One advantage of this approach is that it naturally generates detail in the regions that are sampled more frequently, these are normally the regions which have more height variation. This representation is a more faithful representation of the underlying data since the sample points are generally the vertices of the triangular mesh.

The second form of representation is as a regular mesh of rectangular polygons, these are generated by estimating the heights at each corner of the mesh cells. The main advantage with this is that multiple resolution meshes can be readily generated from the same dataset of spot heights. This form is tend to provide more 3D visual cues as the wire frame rendered mesh acts a type of slope based shading.

Triangulation example

In this example the original digitised aerial survey resulted in 600,000 spot heights, covering a rectangular region of 42km by 64km. Converting this directly to a triangular mesh would result in a surface of approximately twice that number of polygons, 1.2million!. This number of polygons would certainly be a handful for most software packages especially if interactive 3D control was necessary.

One approach to data reduction is to filter the spot heights file so as to evenly distribute the points over the region. This is done by checking the distances between all points so that no two points are closer than some user chosen distance. An improved approach would be to incorporate the height variation between neighbouring points so that highly sampled areas are better represented, this assumes that regions are densely sampled because of increased height variation.

Below are some examples of the surface and the number of resulting polygons for 1,3,and 5km filter distances.

5km radius, 116 polygons

3km radius, 316 polygons

1km radius, 2600 polygons

Notice there are only a few polygons in the lake regions where no sampling was necessary.

Gridding example

This example uses another terrain database containing 100,000 points over a 650m square area. These were used to produce a gridded representation at a user selected resolution and thus file size. This very precise control of resolution is not possible in the previous filtering process, the user didn't know the resulting number of polygons beforehand. The exact size of the grid cells is also precisely known which can be useful for rough distance estimates.

The following are some examples of 10, 20, and 65 square meshes showing the number of polygons involved.

10x10 grid, 65m grid size, 40 polygons

20x20, 32.5m grid size, 200 polygons

65x65, 1m grid, 1850 polygons

There is normally a further overhead if a rectangular mesh surface is to be used for rendering purposes because the 4 point facets above will generally not be coplanar. The simplest solution is to split each facet into two along the diagonal thus increasing the number of polygons by a factor of 2. A better method is to interpolate the midpoint, unfortunately this increases the number of polygons by a factor of 4.

In summary, the two representations can be used to create a terrain model of any desired data size. Indeed one would normally generate a number of surfaces with different resolution, the particular one used at any given time would depend on the applications ability, the response times, and quality/precision goals.