Selection of updates and accuracy criteria

A major aim of an MT-generator is to maintain overall information on terrain (both shape and attributes) as accurate as possible at the coarsest level of detail already, while a more and more detailed descriptions are progressively stored in the higher levels of detail (i.e., at nodes that belong to deeper levels in the MT). The general policy to achieve this goal is: in refinement algorithms, to perform first those updates which improve detail best; in simplification algorithms, to perform first those updates which cause the least loss of detail.

The concept of detail here may depend on different criteria, concerning either accuracy, or resolution, or both, and it is application dependent. In particular, it is possible to consider:

• The error in approximating terrain elevation: each triangle approximates a portion of terrain, and its approximation error can be measured by the vertical distance between it and data points it spans (see Figure ).
• The error in approximating terrain slope, which can be measured in a similar way at each triangle, by comparing its slope with that of triangles representing the same portion of terrain at the highest resolution.
• The error in approximating some other field defined on terrain, such as temperature, rainfall, etc., still measured in a similar way.
• The error in approximating line features defined by given data segments. This permits to incorporate a multiresolution representation of such lines within the MT (each feature will be represented with a progressively larger number of segments across the various levels of detail).
• The error made in subsuming thematic attributes of terrain (such as soil type, land use, etc.) represented by each triangle with a single attribute. This can be measured by the area covered by the triangle having an attribute different from that stored at it.
• The size of triangles, which can be expressed either by the area, or by the perimeter, or by the longest edge, or by a combination of such values. This is a criterion more related to resolution of representation, rather than to its accuracy.

Figure: The approximation error of triangle t is equal to the maximum vertical distance of p₁, p₂, p₃, p₄ from the plane of t, and occurs at point p₁.

DETTO SOPRA PIU' SEMPLICEMENTE We assume that the known data for the original terrain are a set P of points and a set L of lines where the terrain elevation is known. We define the error of a triangle t as the maximum vertical distance between a point of P, or a point on a line of L, and the triangular surface patch described by t

Figure: A TIN at uniform accuracy, measured by elevation error, but variable resolution. Note that bigger triangles represent flat terrain areas.

Since different applications may be concerned with different concepts of detail, none of the concepts listed above can be best for all applications. However, building a different MT for every application would be impractical. On the contrary, a reference model can be built by taking into account just one such criterion, or a combination of few of them. The accuracy/resolution of each triangle of the model, according to the other criteria, can be computed off-line after the model has been built, thus making it suitable to multiresolution queries that need concepts different from those considered during construction. A practical observation in support to such an approach is that even models built by random sequences of updates do not perform dramatically worse than methods designed to fit a given concept of detail, as shown experimentally in [De Floriani et al.1997].

A general possibility would be to base MT construction only on resolution, which is a concept intrinsic to geometry of each triangle, hence independent of applications. In fact, accuracy, in any of the forms listed above, tends to increase with resolution. However, triangles with the same resolution do not necessarily have the same accuracy. For instance, a higher resolution is necessary in rough areas to achieve the same accuracy in elevation for which a low resolution is sufficient in flat areas (see Figure ).

For applications that are only concerned with terrain shape, we found that an MT-generator designed to optimize elevation accuracy, possibly combined with preservation of line features, works well. VARIANT provides MT-generators of this kind. For applications that need to work also with thematic attributes, it might be better to write new MT-generators which combine also such concepts in selecting updates during construction.

LE PART SEGUENTI NON MI SEMBRA SERVANO - ALCUNE COSE GIA' DETTE It is necessary to point out the difference between the error and the resolution of a triangle. This latter property is intrinsic to a triangle and depends on its size (we assume to measure the size of a triangle t in some conventional way, e.g., the area of t, its perimeter, or the maximum / minimum edge length). Accuracy and resolution are two strictly related, yet different, concepts. Usually, accuracy increases with resolution. However, triangles with the same resolution do not necessarily have the same accuracy. This happens because in rough areas of a terrain a higher resolution is necessary to achieve the same accuracy for which, in flat areas, a low resolution is sufficient (see Figure ). An MT-generator can select TIN updates to be performed based on a greedy techniques that aims at minimizing the error of triangles for a given resolution level. In refinement methods, the data point causing the largest error in the current representation (i.e., the one with the maximum vertical distance from the TIN) is inserted at each step. In simplification methods, the TIN vertex causing the least increase in approximation error is deleted at each step.