Background

The fundamental question that must be answered in trying to build a view-independent system is "Which features are so significant that they should be drawn no matter what?" Before a single frame is ever drawn, decisions must be made concerning what is to be drawn and what is to be left out -- to say nothing of how it is to be represented.

It seems apparent, when considering terrain, that there are several features that carry that significance: ridges, valleys, creases, etc.; or, to put it another way, areas of rapid change. At first, my thoughts tended toward a simple analysis of local extrema and then somehow linking these extrema into coherent lines or contours. However, this approach had several obvious flaws. First, interesting trends in the data which aren't explicitly extrema fall through the cracks--like a slope ending in a flat plane, such as a coastline where water meets land. Secondly, finding local extrema doesn't give any context for how they should be connected. Both of these could be dealt with - but the solutions would extend the algorithm in unwanted directions with increased complexity, which remove it distantly from the original, simple algorithm for dealing with local extrema.

A second, and far superior, approach presented itself after reading a paper on suggestive contours (DeCarlo, et al). Although suggestive contours are view-dependent, the idea of using the curvature of a function to identify features seemed to solve both of the problems that the extrema approach left unresolved.

First, the case of one region of basically uniform slope quickly transitioning into a different uniform slope, but without any significant local extrema, can be resolved with curvature. This case can be thought of as a crease. Away from the crease the surfaces forming the crease will have relatively low curvature. But at the crease, the curvature will increase in magnitude. So, the points along the transition will have a greater curvature value than their immediate neighbors, and this delineation can be detected and used as a base for a method of artistic rendering.

Second, curvature analysis implies a means for determining connectivity. The curvature is calculated on a function in 2-space - created by a plane intersecting the terrain data. For a given vertex in the terrain, there is an infinite number of planes that can intersect the terrain and pass through that vertex. In general, we chose to define the intersecting plane by the plane spanned by the normal of the vertex in question and the projection of the vector from the vertex to the viewpoint onto the vertex's tangent plane. What this means is that the curvature value is associated with an explicit direction. With the vertex normal constant, varying the second vector will cause a different plane to intersect the terrain and that intersection will form a different poly line on the plane. The poly line is an approximation of the space curve whose curvature is to be determined.

Picture a piece of terrain with a ridge running parallel with the x-axis. If we choose an intersection plane that is parallel with the x-axis and upon which the ridge in the terrain lies, the resultant intersecting space curve will have almost no curvature. However, if we rotate the plane ninety degrees around the vertical axis, the intersecting space curve will have a significantly greater curvature value. Quite simply, a vertex will likely have one direction of maximum curvature. The neighboring vertices it would most likely connected to form some sort of contour are in the directions perpendicular to the direction of maximum curvature. So, knowing what the maximum curvature is and in which direction it occurs implies a viable connection to some subset of its neighboring vertices.

So, curvature analysis seems to provide one of the strongest foundations for meaningful analysis of terrain's most significant features.

Researched and written by Sean Curtis with a great deal of help from Pete Shirley and Dave Gallup (August 16, 2004).