Contour Lines

Contour maps are probably the most common and natural way to visualize a terrain. A contour corresponding to an elevation value h is the intersection between the terrain surface with the horizontal plane of equation z = h. A contour map is formed by a collection of contours at different elevations, where each line is labeled with its elevation. In the context of a TIN model, aech contour consists of a set of polylines.

[ENRICO: QUI C'E' UN COMMENTO DI LEILA CHE NON CAPISCO]

Without lack of generality, we assume to deal with the extraction of a single contour, at elevation h. Contour lines are computed on a (single-resolution TIN) by selecting the triangles containing the given elevation h, finding one segment for each of such triangles, corresponding to the intersection with plane z = h, and then linking the resulting segments into polylines.

On an MT, we use the DAG structure as a spatial index to select just the relevant triangles for a contour. To this aim, we use a uniform LOD threshold to select the desired accuracy of the map, and a focus condition that considers a triangle active if and only if it intersects the plane z = h.

ENRICO: QUESTA PARTE CAMBIATA - MI SEMBRAVA MEGLIO USARE FOCUS CONDITION We define a threshold function in the following way. Let p≡(x_p, y_p, z_p) be a generic point in space, then:

(p) =

In order to avoid missing some intersection, we artificially assume that a triangle t spans elevation h if plane z = h either intersects t, or it is disjoint from t, but its vertical distance from t is smaller than the elevation error associated with t (see Figure ). The latter situation corresponds to the cases in which t does not contain h, but some triangle refining t may contain it. Intuitively, we can imagine that every triangle t is thickened for an amount equal to its approximation error in order to test the focus condition.

Figure: (a) Triangle t≡abc is considered as intersecting plane z = h since such plane has a distance from t less than the approximation error; (b) triangles refining t actually intersect plane z = h; (c) the MT node refining t.

Each triangle containing the given elevation which is returned by the query algorithm is post-processed in order to compute the segment that represents its contribution to the countour. Contour segments sharing an endpoint are then connected into chains. Note that two segments may have a common endpoint only if they belong to adjacent triangles. In order to efficently find contour segments that need to be connected to each other, the TIN extraction algorithm generates adjacency relations among the triangles of the output mesh.

Given a sequence h₁,…, h_k of elevation values, two approaches can be used to compute the contours for all given elevations:

1. A single query is used to retrieve all the triangles relevant to at least one elevation h_i, by instantiating a suitable focus condition. TOLTI I DETTAGLI INCONSISTENTI COL RESTO in such case, the threshold function requires a zero error at all points p≡(x_p, y_p, z_p) such that z_p∈{h₁,…, h_k}. Then, each triangle is intersected with the appropriate planes in order to generate the contour lines.
2. One individual query is used for each elevation h_i, which is iterated for all values i = 1…k. SCONTATO The contour line at height h_i is computed from the resulting triangle, then the process is repeated for h_i+1, and so on.

Since a representation of the terrain outside the contours is not of interest, in the first approach we prefer to use the algorithm for local query which extracts only triangles that are active for the given isovalues (see Figure (b)). The second approach can be implemented in a similar way by using a different local query for each isovalue. However, if the given elevations are dense enough, the change in the relevant set of triangles when passing from h_i to h_i+1 is small, and an approach based on the dynamic algorithm for global query is more convenient. In this case, the focus condition is used to select triangles on which LOD threshold must be evaluated. The result of a global query for a given isovalue is depicted in Figure (a). Table compares the first approach and the two versions of the second approach outlined above. It shows the number of triangles visited by the TIN extraction algorithms while visiting the DAG as a measure of the cost of the process. The first approach turns out to be the least expensive one. As expected, the version of the second approach using local queries is appropriate when the gap between two consecutive elevations in the sequence is large, and the opposite version using global queries answered through the dynamic algorithm becomes more convenient as the gap gets smaller.

[ENRICO: NELLA PARTE PRECEDENTE CI SONO DIVERSI COMMENTI DI LEILA CHE NON CAPISCO]

Figure: (a) Computation of a single contour from a TIN extracted through a global query; note that triangles tend to be larger outside the region of interest. (b) Computation of a contour map for 10 elevations through a local query; only triangles relevant to the contours are generated.