Equation 1 Turning the principle of curvature analysis into finished images is a two-stage effort. The first is the actual analysis and the second is utilizing the analysis to create some form of detail-suggestive image.
The simple reality is that terrain data is not made up of mathematical functions - it is made up of discreet points. So, there is no inherent mathematical function to determine the curvature of the terrain at any point; approximations are unavoidable.
There exist methods for extracting curvature of arbitrary polygonal meshes by curve approximation, curve interpolation and similar methods. But terrain representations usually encompass a very small, structured subset of polygonal geometry.
The very nature of the terrain suggests some means of approximation. First, raw terrain data is very regular. All points are spaced evenly on a regular grid aligned with an axis. The distances from one point to its neighbors are known and constant. Only the y-value varies from point to point--it is, after all, a height field. This suggests that curvature can most easily be approximated in four discreet directions - along the terrain’s x-axis, along the z-axis, along the axis 45 degrees between the positive x- and z-axes and 45 degrees between the positive x- and negative z-axes. The opposite directions are unnecessary; the curvature would be the same whether from looking it from the “front” or the “back”. Certainly more directions would provide a more complete understanding of the contours of the terrain but only these four directions can be directly derived from the source data. Any direction between these cardinal orientations would require us to infer information from the height field. If we were to do this, we might as well use more complex methods directly to obtain the curvature. At this stage, the goal is to find a reasonable, low-cost approximation. So, at this stage, whatever means is used to calculate the actual curvature value, it should be performed along those four, discreet axes. Later, choices can be made regarding the utilization of those quantized values.
Four directions implies four planes; one plane with a normal in each of the four directions. The intersection of the plain and curve form an approximate space curve. Again, this curve is in 2-space. So, for a simple function, expressed in terms of x, the curvature at a point, p, can be calculated with the following equation:
Equation 1
So, the challenge now becomes deriving values for the first- and second-derivatives at p. For my research, I implemented four different methods of approximating the value, each with its own particular resultant characteristics. Two are based on a derived quantity - specifically derived vertex normals, which I refer to as normal based approximations. The other two are based strictly on the actual terrain dataset, referred to as geometry based approximations.
Because these approximations are based on vertex normals, the actual method of deriving those normals plays a great role. I tested three different means: edge-based, triangle based and quad based. Edge based normals look at the edges radiating from the vertex in pairs. The slope of the edges to the neighbors in one direction are calculated independently and averaged together and then the same with the slopes of the edges in the orthogonal direction. These two slopes are converted to vectors, added together and normalized to create the vertex normal.
The triangle based method uses the same neighboring vertices as edge-based, but instead of examining edges, four imaginary triangles are constructed from the five vertices (four neighbors plus center vertex creating a open tetrahedron). Each triangle’s normal is calculated and the four normals are averaged to create the vertex normal.
The quad based method uses the eight nearest neighbors to the target vertex. Instead of four imaginary triangles, four quads are constructed. Their normals are evaluated and then averaged together to create the vertex normal. If the quad itself is not planar, than its normal is an average of two triangles that form the quad.
The results of the edge-based and the triangle-based methods seem to be basically the same. However, the quad-based method yields slightly different results. Figure 1 shows the same terrain smoothed by each of the algorithms. The edge-based (a) and triangle-based (b) methods both have the same kind of noisy patterns in the high contrast region on the left side of the ridge--the side in shadow. The quad-based image has a smoother look. The intuitive reason should be clear--the quad-based method takes into account twice as many vertices so the resultant normal has a more "averaged" quality. Obviously a noisier distribution of normals will lead to a noisier curvature calculation. Examinations of curvature algorithms will all use the quad-based smoothing.
|
|
|
|
||
|
(a) |
(b) |
(c) |
Equation 1 will always yield non-negative values. It is strictly a measurement of curvature and doesn't care whether it's curving inward or outward. In reality, the range of the function spans [0, infinity). In practice, the actual range could be much, much smaller (experimental evidence has shown something in the range of [0, 2] to be a more realistic value with the majority of the values landing below one.) Currently, each of the curvature algorithms accepts a scaling parameter which will evenly scale all of the curvature values. This simplistic scaling can (and should) be later replaced with some means of level control, to create a greater distinction between the meaningful curvature values and the meaningless, noisy curvatures. But for now, scaling is sufficient.
The first and, in many ways, simplest approach utilizes only two normals: the normal of the vertex in question and the normal of the immediate neighbor in the direction of calculation (i.e., one of the four directions listed earlier). The first and second derivatives arise naturally from the usage of normals. The first derivative is merely the slope of the tangent through the vertex. The tangent is perpendicular to the normal and so, given the normal, obtaining the slope of the tangent is trivial. The second-derivative is merely the change of slopes. The slope is calculated for the target vertex and the neighbor nearest to the vertex in the direction of analysis. The average change in slope is calculated by taking their difference and dividing by the distance between the points. Then the curvature equation above is applied and the curvature for the given direction is stored. The process is repeated for each of the three other directions.
The second method is very similar to the first. There are two differences. The first is implied by the name, the normals from three vertices are used. The third normal comes from the neighboring vertex in the opposite direction from the direction of analysis. The curvature is calculated for both pairs of vertices (previous-target and target-next). The results are averaged together to generate the curvature value.
The three-normal approach also has a second layer of utility. This additional functionality takes advantage of the unique characteristic of the terrain dataset. It is a trivial task to select the nth neighbor in any of the eight compass directions. Because of this, the three-normal approach can also examine the target vertex with a second set of neighbors some arbitrary distance away. The curvature from these three vertices is calculated as it was for the immediate neighbors, and then the result is multiplied to the previous curvature result. This has the effect of pushing curvature values away from 1.0. Numbers smaller than 1.0 get even smaller and number bigger than 1.0 get even bigger. In effect it takes the local curvature phenomenon, compares it with a "bigger picture" and reconciles the two cases. So, a tight ridge becomes tighter and noise gets diminished.
The first of the two geometry-based approximations is the three-vertex approach. As its name implies, it uses three vertices to calculate the curvature. It uses the target vertex and its two immediate neighbors along the vector to the viewpoint. It calculates the slope of the two edges connecting those three points and calculates the second-derivative to be the difference in the two slopes divided by the point distance and the first derivative as the average of the two slopes.
This approach could also use a secondary set of vertices at some specified distance, d > 1, to offer the same kind of reinforcement as the three-normal technique uses, but this has yet to be implemented.
The last of the curvature algorithms doesn't actually use Equation 1. Instead, it uses the inner product of the edges extending from the target vector to its neighbors to calculate the cosine of the angle between them. The range of this function is [-1, 1] but in practice the range is [-1, 0] because very little terrain data (particularly high-resolution terrain data) has angles between adjacent edges less than 90 degrees. The cosine of the angle is then subtracted from 1 and the result is treated as a curvature value. This has several significant differences from the previous three approaches. First, it's output values are clamped in the range [0, 1], whereas Equation 1 has no actual upper bound. Secondly, the function is ideally attuned to the type of curvature we're seeking. At 90 degrees the slope of the function is -1 and as the function approaches 180 degrees the slope gradually goes from -1 and then accelerates towards 0 closer to 180. This means the function is most sensitive towards differentiating "curvature" nearer 90 degrees than 180 degrees. This is ideal because if two edges are 180 degrees away from each other, nothing of significance is happening there and it can happily be ignored.
Finally, the same distance reinforcement could be applied to this algorithm as has been applied to the three-normal algorithm.
To help visualize the results and characteristics of the algorithm, the mesh has been colored to represent curvature data. For each vertex the greatest curvature value is mapped as an intensity level (with curvature values above 1.0 clamped to 1.0). The following figure illustrates the characteristics of each algorithm.
|
|
|
|
||
|
(a) |
(b) |
(c) |
||
|
|
|
|
||
|
(a') |
(b') |
(c') |
|
|
|
|
|
(d) |
(e) |
|
|
|
|
|
|
(d') |
(e') |
The differences between figures 2.b and 2.c clearly illustrate the reinforcement of the second set of calculations. On the whole (b) has less noise than (a), which is to be expected because of the greater sampling. (c) and (e) offer the highest contrast. (d) seems to be similar to either (a) or (b), but tends toward higher values. There are other, more subtle differences not immediately apparent in these small images. For example, (c) creates a narrower band of high curvature along the upper-right coastline than either (a), (b) or (d).
Utilizing curvature is otherwise known as drawing lines. Having analyzed and cached the information regarding curvature for the terrain, it behooves us to put it to work. This paper discusses two basic approaches to using the curvature (and suggests several variations). The two approaches are called "line" shading and "hatch" shading. Others are certainly possible.
Although the focus of this research is view-independent rendering, these approaches are consistent and compatible with many view-dependent methods. The obvious complement to the following shading algorithms is a simple view-dependent, contour algorithm which draws "contour edges".
The principles behind line shading arise naturally from the issues raised in the background, which led to the use of curvature analysis: the desire to connect significant points. Line shading attempts to trace paths through points of high curvature. The direction the path takes is determined by the direction of the greatest curvature value associated with a vertex. The union of all these paths creates a static framework, which can be drawn, view-independently, to represent the terrain. Several parameters control the overall quality and character of the resultant image.
The algorithm, in its simplest incarnation, is straightforward. For each point, the curvature is tested. If the curvature exceeds a certain threshold, the point is added to a list and the two vertices in the directions perpendicular to the direction of maximum curvature are tested as well. This continues in both directions until each end hits a vertex with insufficient curvature to pass the threshold test. The ordered list of vertices is tested for a minimum length, if long enough, a "line strip" is drawn. Each vertex in the line strip is colored black, but given an alpha equal to its curvature. So, more significant vertices (i.e. higher curvature) will appear darker.
Currently, this algorithm only follows paths in discreet directions (one of the four tested directions.) One possible refinement is to blend the four discrete directions together, weighting the unit vectors according to the curvature in each direction to find an average direction and follow the path in that direction. Points in the path would no longer simply be points from the height field and curvature values would have to be interpolated for these new points from its neighbors. The four-direction path algorithm can recognize when one path merges with another and can eliminate redundancy in drawing paths. When paths can follow arbitrary directions and pass through unique points, paths that might, in principle, merge could end up lying next to each other. Special care must be taken in drawing paths in these blended directions. Perhaps blending them in discrete amounts would balance this difficulty with the ease of path administration.
Combinations of curvature scaling, line widths, minimum path lengths and minimum thresholds can create vastly different rendering styles.
The following figure shows several variations of the line shading style with varying parameters.
shaded
|
|
|
|
|
(a) |
(b) |
|
|
|
|
|
|
(c) |
(d) |
|
|
|
|
|
|
(e) |
(f) |
|
|
|
|
|
|
(g) |
(h) |
|
|
|
|
|
|
(i) |
(j) |
|
|
|
|
|
|
(k) |
(l) |
|
|
|
|
|
|
(m) |
(n) |
Fig # |
Curv. Style |
Curv Dist |
Curv. Scale |
Has Contours |
Min. Len |
Line Width |
Fig # |
Curv. Style |
Curv Dist |
Curv. Scale |
Has Contours |
Min. Len |
Line Width |
a |
3 norm |
2 |
6 |
no |
6 |
1 |
h |
2 norm |
n/a |
3 |
no |
5 |
1 |
b |
3 norm |
2 |
6 |
yes |
6 |
1 |
i |
Edge |
n/a |
2 |
yes |
5 |
1 |
c |
3 norm |
2 |
11 |
yes |
2 |
1 |
j |
3 Vert |
n/a |
2 |
no |
5 |
1 |
d |
2 norm |
n/a |
2 |
no |
5 |
1 |
k |
2 norm |
n/a |
1 |
no |
5 |
1 |
e |
2 norm |
n/a |
11 |
no |
2 |
1 |
l |
Edge |
n/a |
1 |
yes |
5 |
1 |
f |
2 norm |
n/a |
6 |
no |
2 |
1 |
m |
3 Vert |
n/a |
1 |
no |
5 |
1 |
g |
3 norm |
2 |
3 |
yes |
5 |
1 |
n |
3 norm |
1 |
1.5 |
no |
2 |
6 |
Hatch shading is another means of using the curvature analysis. Rather than trying to create continuous contours, hatch shading focuses on each point, individually. It relies on a similar principle as pointillism--the idea that the effect of light at discreet, regular locations can combine to form a coherent image of the whole object.
In its first and, again, simplest incarnation the algorithm iterates through each of the points, evaluates its curvature value and draws a stroke of parameter-determined length. Like line shading, the color of the stroke is black and its opacity is determined by the magnitude of the greatest curvature at that point. The stroke is generated on the tangent plane at the vertex. Its direction is determined by the projection onto the tangent plane of the weighted curvatures -- the four directional vectors are summed, each multiplied by the curvature value in that direction and the resultant vector determines the direction of the stroke. The stroke can be drawn either in the direction of greatest curvature or perpendicular to it. Varying stroke length, stroke width and curvature values yield a wide range of different rendering styles (as seen in Figure 4 on the following page.)
shaded
|
|
|
|
|
(a) |
(b) |
|
|
|
|
|
|
(c) |
(d) |
|
|
|
|
|
|
(e) |
(f) |
|
|
|
|
|
|
(g) |
(h) |
Fig # |
Curv. Style |
Curv Dist |
Curv. Scale |
Has Contours |
Hatch Len. |
Line Width |
Hatch Dir |
a |
3 norm |
2 |
4 |
no |
0.75 |
1 |
With |
b |
3 norm |
1 |
4 |
no |
0.75 |
1 |
With |
c |
3 norm |
1 |
4 |
no |
0.75 |
1 |
Perp. |
d |
2 norm |
n/a |
4 |
no |
0.75 |
4 |
Perp. |
e |
2 norm |
n/a |
8 |
no |
0.25 |
1 |
Perp. |
f |
3 norm |
2 |
8 |
yes |
0.75 |
1 |
Perp. |
g |
3 norm |
1 |
3 |
no |
2.15 |
2 |
Perp. |
h |
3 vert |
n/a |
2 |
no |
0.45 |
3 |
With |
Researched and written by Sean Curtis with a great deal of help from Pete Shirley and Dave Gallup (August 16, 2004).
Sean Curtis (scurtis-junk@cs.utah.edu) Remove the -junk (gotta love spammers).
