Contents of Query Operations

Query Operations

Basic queries on a terrain model include evaluating terrain characteristics at a given point or inside a given region; extracting terrain profile along a given path (e.g., a river or road); windowing and buffering; extracting portions of terrain with a given elevation, or slope, or having a given thematic attribute; etc. Multiresolution queries use resolution and/or accuracy as a further parameter in computation. This means that, besides specifying the subject of our query, we can also specify the desired resolution and/or accuracy of the result, which can be possibly variable over the domain. In the following, we will refer generically to the desired resolution and accuracy as Level of Detail (LOD).

In general, a multiresolution query is specified by two parameters:

A focus condition, which defines the portion of terrain relevant to the query, hereafter called the Region of Interest (ROI). A focus condition is a Boolean function defined on the triangles of an MT and assigning the value TRUE to a triangle if and only if it belongs to the ROI. This may depend on a number of parameters, which can be used to implement a specific condition, such as: spatial location, elevation, slope, field value (such as temperature, rainfall, etc.), attributes (such as soil type, land use, etc.) A triangle that satisfies a focus condition is called active.
A LOD threshold, which defines the level of detail of the TIN to be extracted. A LOD threshold is a Boolean function defined on the tiles of an MT and assigning the value TRUE to a triangle if and only if its level of detail of is considered sufficient. This may depend on the position of the triangle in space, on its geometric properties (size, shape), on its accuracy-related attributes (e.g., error made by approximating either elevation, or another field of interest), etc. A triangle that satisfies the resolution filter is called feasible.

The MT-manager provides just a general-purpose operation for multiresolution queries, called TIN extraction, which performs selective refinement on an MT, on the basis of given focus condition and LOD threshold. TIN extraction returns a TIN describing (a portion of) terrain according to user-defined criteria. The MT-manager supports two types of TIN extraction:

A global query, which extracts a TIN representing the whole terrain at a certain resolution. The LOD threshold is the main parameter of the query, and the result is a TIN made of triangles that are feasible with respect to the given threshold. A focus condition may be used optionally as a filter, in order to bound the application of LOD threshold only to active triangles, while triangles outside the region of interest are considered feasible at an arbitrarily coarse resolution.
A local query, which extracts a TIN restricted to the Region of Interest (ROI), still at variable resolution. Both the focus condition and the LOD threshold are taken as parameters of the query, and the result is a TIN made of triangles that are both active and feasible, i.e., that cover only the desired ROI at the desired LOD. In this case, the MT is used not only as a mechanism to manage resolution, but also as a spatial indexing scheme.
[ENRICO: QUI C'E' UN COMMENTO DI LEILA CHE NON CAPISCO]

A few examples of TIN extraction from global queries with different threshold functions are depicted in Figure $[*]$ : in (a), triangles inside the square box are required to be at the highest possible resolution, while triangles outside it can be arbitrarily coarse; in (b), triangles outside the wedge (view frustum) can be arbitrarily coarse, while the resolution of triangles inside the wedge is highest at its apex (view point), and decreasing with distance from it; in (c), resolution is highest for triangles intersecting a given polyline, while it is arbitrarily coarse elsewhere.

[C'E' UNA RIDONDANZA TRA TESTO E DIDASCALIA. FORSE TOGLIERE LA DESCRIZIONE DAL TESTO.]

**Figure:** Three TINs extracted with three different LOD thresholds. (a) The triangulation has the highest possible resolution inside a rectangular window, and the lowest possible resolution outside it. (b) Resolution inside a wedge (view frustum) is decreasing with the distance from its apex, while it is arbitrarily low outside it. (c) Resolution is high only in the proximity of a polyline.
$\begin{figure}\centerline{\small \begin{tabular}{ccccc} \psfig{file=boxG-2.ps,w... ...m} \\ (a) && (b) && (c) \\ \end{tabular}} FARE ANCHE VISIONE 3D\end{figure}$

[FORSE SAREBBE BENE AVERE ANCHE ESEMPI DI QUERY LOCALE. NON BISOGNEREBBE ESSERE TROPPO RIPETITIVI. FORSE TENERE SOLO POLYLINE E WEDGE PER LA GLOBALE, FARE WINDOW E QUALCOS'ALTRO (BUFFERING CON DISTANZA DA UN PUNTO?) PER LA LOCALE. VEDERE ESEMPI DISPONIBILI DA TESI PAOLA]

Global queries are intended for applications that compute global information (e.g., computation of visibility maps on a terrain). Local queries are the basis for applications that run geometric queries on a mesh (e.g., evaluation of a field value or an attribute at a point, or along a trajectory). Query mechanisms provided by the kernel are generic with respect to the parameters that describe the level of detail and the region of interest. Many different query operations can be defined on top of TIN extraction by varying its parameters. The implementation of mechanisms for answering specific queries is therefore left to modules of the outer layer (see Sections $[*]$ and $[*]$ ).

Algorithms that implement TIN extraction reduce to traversing the DAG that describes an MT, in order to find a closed subset of updates which provides a TIN having the required properties. The MT-manager includes the following three algorithms, which are described in detail in [De Floriani et al.1998,Magillo1999]:

A static algorithm for global queries. This algorithm answers each new query independently of the previous ones, and is suitable for single queries.
A dynamic algorithm for global queries. This algorithm answers a new query by updating the solution of a previous query; it is suitable for repeated queries, when the result of a new query slightly differs from the result of the previous one.
A local algorithm, suitable for local queries.

[LEILA: AGGIUNGERE QUALCOSA DI PIU' SUGLI ALGORITMI, DALLA VERSIONE VECCHIA]

[ENRICO: NELLA VERSIONE VECHIA NON C'E' MOLTO PIU' DI QUESTO, SPIEGARE I MECCANISMI DI ATTRAVERSAMENTO DEL DAG RISULTA OSCURO. LASCEREI COSI']

[ENRICO: FORSE CI STAREBBE UN COMMENTO SUL FATTO CHE E' POSSIBILE UTILIZZARE UN ALGORITMO GLOBALE E POI FILTRARE IL RISULTATO ATTRAVERSO UNA FOCUS CONDITION E CHE QUESTO PUO' ESSERE CONVENIENTE PER SFRUTTARE I VANTAGGI COMPUTAZIONALI DELL'ALGORITMO DINAMICO PER QUERY CHE PUR ESSENDO DI NATURA LOCALE DIFFERISCE DI POCO DA UNA PRECEDENTE (ES: VISUALIZZAZIONE, OPERAZIONI DI PAN SU UNA WINDOW)]

TOLTO PERCHE' SUPERFLUO Variants of these algorithms are also described in [Magillo1999], in which the condition on the output TIN of being formed by feasible triangles is relaxed, while a given bound on its number of triangles is imposed. In this case, each algorithm returns the TIN within the given bound that is as close as possible to the given error threshold function.

The TIN resulting from a query is returned either just as a list of triangles (each defined by its three vertices), or in a more complete format including also triangle-to-triangle adjacency relations. In the latter case, adjacency information is reconstructed on-the-fly during extraction. The first format is sufficient for simple applications such as visualization. The latter format is useful for applications performing TIN analysis.

SUPERFLUO