Contents of Point-to-Point Visibility

Two points p₁ and p₂ lying on or above terrain are mutually visibile if terrain profile along the interior of segment p₁p₂ lies below p₁p₂.

FAREI SOLO PER I PUNTI In a visibility query, some query object is given, and the aim is determining the portions of such object visible from a given viewpoint V. A visibility query related to a point Q simply requires to determine whether Q is visible from V or not. A non-point query object must be partitioned into maximal connected portions, each of which is either entirely visible or entirely invisible from V. Visibility queries are solved by reducing them to intersection queries in order to find the TIN triangles that cast shadows on the given object. In the following, we describe the visibility queries implemented in the MT-visibility module of VARIANT.

**Figure:** Points $\hat{{p_1}}$ and $\hat{{p_2}}$ are not mutually visible since the straight-line segment connecting them intersects the TIN.
$\begin{figure}\centerline{\psfig{file=pointvis.eps,width=5cm} }\end{figure}$

A point-to-point visibility query on a TIN can be solved by reducing it to an intersection query: we search for all the triangles which intersect segment p₁p₂ (in three-dimensional space). The two points are mutually visible if the result of the query is empty (see Figure $[*]$ ).

**Figure:** Result of 500 point visibility queries with pairs of points generated randomly. The horizontal axis reports the number of triangles blocking visibility (i.e., intersecting the straight-line segment which joins the two points in IR³ and, thus, reported by the query); the vertical axis reports the number of triangles visited by the local algorithm. Note that the ratio of the two quantities is about constant.
$\begin{figure}\centerline{\psfig{file=graficoVis.ps,width=6cm}} \vspace*{3mm}\end{figure}$

An MT can be used as a spatial index in point-to-point queries, in order to extract just the triangles which, for their spatial location, are relevant for the solution. In this case, the algorithm for local query is used, by setting segment p₁p₂ as region of interest. As in the case of contour lines, in order to ensure that no intersection is lost, we must test the intersection of an MT triangle t with segment p₁p₂ by considering t ``fattened'' vertically for a thickness equal to its approximation error.

Queries can be made either at full resolution (in this case, spatial indexing is the only role played by the MT), or according to a LOD threshold corresponding to a given uniform elevation error $\varepsilon$ . In the latter case, the answer is subject to a given uncertainty, which can be measured in order to produce a fuzzy model of visibility [CITARE LAVORO DI FISHER]. To this aim, we use a vertical wall through segment p₁p₂ as region of interest. In this way, the answer to the local query is a polyline l representing terrain profile along the projection of that segment, with an elevation accuracy $\varepsilon$ . This means that the true terrain profile may lie in a band of thickness 2 $\varepsilon$ obtained by shifting the extracted profile by an offset $\varepsilon$ above and below along the vertical axis (see Figure $[*]$ ).

Let l_u and l_l be the upper and lower boundaries of such a band. If all points of lie above l_u the two points are certainly visible: we say that p₁p₂ have a visibility value 1. If some point of p₁p₂ lies below l_l they are certainly not visible: in this case their visibility value is 0. Otherwise, we assign to the segment a visibility value between 0 and 1, computed as follows: we take the point of l_l that has the smallest vertical distance from p₁p₂, let d be such a distance. Then the visibility value for p₁p₂ is given by ${\frac{{d}}{{2\varepsilon}}}$ .

[ENRICO: QUESTO MODO DI MISURARE L'INCERTEZZA L'HO INVENTATO. CONFRONTARE CON IL LAVORO DI FISHER].

[ENRICO: TOGLIEREI LA PARTE SEGUENTE E FIGURA. L'ALGORITMO LOCALE RESTITUISCE I TRIANGOLI CHE INTERSECANO IL TRIANGOLO ED E' IMMEDIATO ESTRARRE LE CATENE DI INTERSEZIONE (TIPO CONTOUR LINES) MA DOPO BISOGNA RISOLVERE UN PROBLEM DI VISIBILITA' 2D. MI SEMBRA CHE SENZA SPIEGARE QUELLO LA COSA RISULTI INCOMPLETA E OSCURA. INOLTRE NON MI E' CHIARO COME ESTENDERE IL MECCANISMO DELL'INCERTEZZA AL CASO DEI SEGMENTI].

MT-clients performing other types of visibility queries can be defined by extending the basic ideas described above. For instance, a point-to-segment visibility query consists of finding the portion of a given segment s which is visible from a viewpoint v. Since only portions of the terrain that lie between v and s may block the view of s from v, a visibility query can be answered by performing TON extraction with the algorithm for local query, with a region of interest equal to the triangle defined by the given point v and segment s (see Figure $[*]$ ).

**Figure:** Computing the visibility of segment p₁p₂ from v reduces to a local query using triangle vp₁p₂ as a region of interest.
$\begin{figure}\centerline{\psfig{file=segvis.eps,width=5cm} }\end{figure}$