\section{The MT-Clients within VARIANT}
\label{sec:clients}

[LE COSE DETTE IN QUESTA INTRO SONO STATE GIA' DETTE IN PRECEDENZA.
PER ORA LASCIO COSI' MA BISOGNEREBBE EVITARE LE RIDONDANZE]

A naive use of MTs from any application handling terrain data consists 
simply of extracting a TIN at a user-defined accuracy, 
and using it as a data set for subsequent processing 
(e.g., visualization, analysis, or simulation). 
In this case, a single TIN extraction is needed, which is performed by using 
a selected focus condition and LOD threshold.
This simple feature is an improvement over the use of a 
terrain model at uniform resolution, since it allows an application to run
on a model whose level of detail is suitable to match its needs, and/or the 
computing power.

However, the true power of VARIANT is exploited by applications that
make direct use of variable resolution features to improve performance.
In the following, we list some examples of MT-clients that are meant to
exploit such features.
%, and are either already available within VARIANT 
%or under implementation.


\subsection{Interactive Terrain Visualization} 
\label{sec:viewer}

Realistic visualization of terrain is very important in flight simulation
and environmental assessment. 
Skewed views of terrain may easily span a huge domain: for instance,
%in good visibility conditions, 
the field of view from an airplane may extend
on a range of several hundreds kilometers. 
If a terrain model at very high resolution were used to visualize such kind of 
views, the number of graphical primitives to be rendered would overwhelm
even the performance of most powerful graphical workstation.  
Moreover, resolution would be unnecessarily high on a large portion of 
terrain, since the size of each graphical primitive far from
viewpoint would become smaller than a pixel.
On the other hand, if a generalized model were used, at a resolution
sufficiently low to be managed by the rendering engine, the visual
quality of terrain close to the viewpoint would be highly degraded.
%, while some portions of terrain far from viewpoint might still be at an 
%unnecessarily high resolution.
Some improvement may be obtained with the latter approach by a clever use of
texture mapping [UNA CITAZIONE, FORSE LAVORO PISANI]. 
However, texture mapping cannot help with the shape degradation of
silhouettes (e.g., ridges) and other important geometric features 
(e.g., cliffs, roads, rivers, etc.).

The performance of a visualization system can be improved enormously if a
representation at variable level of detail is used. 
In fact, this kind of solution is the subject of a number of recent 
proposals in the literature
\cite{CigPupSco97,BerDob95,FlyAway,Hop98,LinAl96,Topovista},
and iit s also adopted in the context of commercial products and videogames.

[MANCANO RIFERIMENTI PER QUESTO. SICURAMENTE CI SONO VISUALIZZATORI COMMERCIALI 
CHE USANO MULTIRISOLUZIONE VARIABILE, MA NON SO QUALI. LE PM SONO STATE 
INCLUSE NELLA VERSIONE PIU' RECENTE DI DIRECTX, LA LIBRERIA GRAFICA DELLA 
MICROSOFT.
NON SO SE LASCIARE L'AFFERMAZIONE SENZA RIFERIMENTI O TAGLIARE LA FRASE.] 

The general idea is to visualize a terrain model whose
resolution is high close to the viewpoint, while it progressively 
decreases with distance from it. 
Note that a different model must be provided at each frame, since the 
viewpoint changes its position continuously.
Therefore, TIN extraction at variable resolution must be performed in
real time.

VARIANT includes a prototype visualization module which permits the 
interactive visualization (i.e., over ten frames per second) of a terrain 
at variable resolution on low cost platforms, such as PCs, already.
This module allows the user to drive its viewpoint through space
to fly over terrain.
\NOTA{COSE GIA' DETTE SOPRA.
In order to obtain an interactive frame rate, it is necessary
to keep the overall number of triangles sent to a rendering device
below a certain bound.
At the same time, the visual appearance of the mesh that
is rendered must not be perceptually dissimilar from the
mesh at the maximum resolution.
%%
The basic idea is using a low accuracy for 
terrain portions which are either
distant or outside the field of view.
}

At each frame rate, we apply the dynamic algorithm
for global queries, and extract a TIN covering the whole 
domain and obeying to a LOD threshold defined in the following way:
\begin{itemize}
\item
  For all points lying outside the
  view frustum, resolution can be arbitrarily coarse, since they
  do not contribute to the visible scene.
\item
  For all points lying inside the view frustum, resolution is 
  maximum at the viewpoint, and decreasing linearly with distance 
  from it.
\NOTE{SOLITA CONFUSIONE TRA ACCURACY E RESOLUTION - MEGLIO SOPRASSEDERE
  this corresponds to the idea that accuracy of triangles
  must be higher near the viewpoint and decrease progressively 
  with distance.
}
\end{itemize}
In this way, the LOD threshold varies at each frame,
since it depends on the position of the viewpoint.
Therefore, the terrain model visualized is adaptively changed at each 
viewpoint position.
At each frame, the dynamic algorithm for TIN extraction starts from 
the model corresponding to the previous frame, increasing detail where 
necessary, and decreasing it where it is unnecessarily high.
Triangles of the extracted TIN lying outside the view frustum are 
culled out prior to rendering. 

\NOTA{VERSIONE VECCHIA CON ALGORITMO LOCALE
The basic idea is that a low accuracy is sufficient for distant
terrain portions, and that triangles outside the field of view
do not need to be generated, since they do not contribute 
to the visible scene.
%
At each frame rate, we apply a local query, where:
\begin{itemize}
\item
  The region of interest $\FCS$ is the view frustum.
\item
  For any poiny $p$, the threshold value $\THR(p)$ 
  is an increasing function of the distance of
  $p$ from the viewpoint;
  this corresponds to the idea that accuracy of triangles
  must be higher near the viewpoint and decrease progressively 
  with distance.
\end{itemize}
The region of interest and the threshold function vary 
at each instant in time, while moving the viewpoint.
The implementation running on a PC can extract nearly 100,000
triangles per second from the terrain models seen in Section 
\ref{sec:histwrite}.
}

Note that we could use alternatively a local algorithm for TIN extraction by
providing the view frustum as a ROI, since this automatically culls triangles
outside the view frustum. 
However, we found that the dynamic approach is faster, due to the computational 
advantage of starting from a TIN that is very similar to that in output.
Figure \ref{sec:volare} shows the portion of TIN extracted at a given frame 
rate, bounded to the view frustum, and a corresponding perspective 
visualization. 
Note how the actual size of triangles increases with distance from the 
viewpoint, while their apparent size on the screen is almost uniform.
 
\begin{figure}
\centerline{
\psfig{file=variab2DL.ps,width=5cm} \hspace{1cm}
\psfig{file=variab.ps,width=5cm}
}           
\centerline{ (a)  \hspace{5cm} (b) }
\caption{\label{fig:volare}
(a) A TIN used for interactive terrain visualization, clipped at the
view frustum, and (b) the corresponding view of terrain.}
\end{figure}



\subsection{Contour Lines}
\label{sub:isoline}

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.
%When a terrain is described by a 
In the context of a TIN model, aech contour consists of a set of 
polylines.
%, each of which is either closed or open.

[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$.

\NOTA{ENRICO: QUESTA PARTE CAMBIATA - MI SEMBRAVA MEGLIO USARE
FOCUS CONDITION  
We define a threshold function $\THR$ in the following way. 
Let $p\equiv (x_p,y_p,z_p)$ be a generic point in space, then:
%
\[ \THR(p) = \left\{
   \begin{array}{ll}
   0                  & \mbox{if $z_p=h$} \\
   +\infty            & \mbox{otherwise}
   \end{array}
\right. \]  
%
Thus, the maximum accuracy is required for triangles that
intersect the given elevation, and any accuracy is accepted for 
other triangles (see Figure \ref{fig:iso} (a)).
}

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 \ref{fig:nonconse}).
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.

\begin{figure}
\centerline{ \psfig{file=nonconse.eps,width=\textwidth} }
\caption{\label{fig:nonconse}
(a) Triangle $t\equiv 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$.}
\end{figure}

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_1,\ldots,h_k$ of elevation values,
two approaches can be used to compute the contours for all given
elevations:
\begin{enumerate}
\item
  A single query is used to retrieve all the triangles
  relevant to at least one elevation $h_i$, 
  by instantiating a suitable focus condition.
\NOTA{TOLTI I DETTAGLI INCONSISTENTI COL RESTO
  in such case, the threshold function requires a zero error
  at all points $p\equiv (x_p,y_p,z_p)$ such that
  $z_p \in \{h_1,\ldots,h_k\}$.
}
  Then, each triangle is intersected with the appropriate planes 
  in order to generate the contour lines.
\item
  One individual query is used for each elevation $h_i$, which
  is iterated for all values $i=1\ldots k$.
\NOTA{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.
}
\end{enumerate}

\begin{table}
%%%\centerline{ 
\begin{tabular}{rrrrrr}
& \multicolumn{2}{c}{Approach 1} &
& \multicolumn{2}{c}{Approach 2} \\
& \multicolumn{2}{c}{(one query)} &
& \multicolumn{2}{c}{(multiple queries)} \\
\hline
$k$ & gap &  local  && dynamic & local   \\
\hline
5   & 200 &   35704 &&  127158 &   41036 \\
10  & 100 &   61244 &&  177613 &   82629 \\
20  &  50 &   89694 &&  211326 &  166616 \\
40  &  25 &  107163 &&  225833 &  334204 \\
45  &  22 &  108522 &&  226259 &  378139 \\
50  &  20 &  110118 &&  227577 &  417037 \\
66  &  15 &  112402 &&  229761 &  555773 \\
100 &  10 &  114432 &&  230901 &  834045 \\
200 &   5 &  115997 &&  232557 & 1667575 \\
\hline
\end{tabular}
%%%%}
\caption{\label{tab:esperiso}
Number of visited triangles in extracting the triangles needed 
for computing a contour map.
Evenly spaced elevations have been used:
$k$ is their number, and the ``gap'' is the height
difference between two consecutive elevations.
For approach 2, the total number of triangles visited in all
queries is shown.}
\end{table}

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 \ref{fig:iso} (b)).
The second approach
can be implemented in a similar way by using a different
local query for each isovalue.
% where the region of interest of an individual query is plane $z=h_i$.
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 
\ref{fig:iso} (a).
Table \ref{tab:esperiso} 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]

\begin{figure}   
\centerline{
\begin{tabular}{ccc}
\psfig{file=isotriG.ps,width=5cm} &&
\psfig{file=isolinG.ps,width=5cm}\\[0.5em]
extracted TIN && contour lines\\[1em]
\multicolumn{3}{c}{\bf (a)}\\[2em]
\psfig{file=isotriL.ps,width=5cm} &&
\psfig{file=isolinL.ps,width=5cm}\\[0.5em]
extracted TIN && contour lines\\[1em]
\multicolumn{3}{c}{\bf (b)}\\
\end{tabular} 
}
}
\caption{\label{fig:iso}
(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.
%The dataset is Mount Marcy.
}
\end{figure}



\subsection{Visibility}
Visibility problems involve either computing visibility properties 
of terrain from a given viewpoint, or computing visibility properties 
of objects located on terrain.
VARIANT includes a module for solving point-to-point visibility
queries, and a module for viewshed computation;
a module for horizon computation is under development.
Such MT-clients are described in the following subsections.

[LEILA: DECIDERE COME METTERE LA QUESTIONE MODULI IMPLEMENTATI E NON]

\subsubsection{Point-to-Point Visibility}
\label{sub:ptvis}

Two points $p_1$ and $p_2$ lying on or above terrain are mutually 
{\em visibile} if terrain profile along the interior of segment $p_1 p_2$ 
lies below $p_1 p_2$.

\NOTA{ FAREI SOLO PER I PUNTI
In a {\em visibility query}, some query object is given,
and the aim is determining the portions of such
object visible from a given viewpoint $V$.
A {\em 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.
}

\begin{figure}
\centerline{\psfig{file=pointvis.eps,width=5cm} }
\caption{\label{fig:pointvis}
Points $\hat{p_1}$ and $\hat{p_2}$ are not mutually visible
since the straight-line segment connecting them intersects the TIN.}
\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_1 p_2$ (in three-dimensional space).
The two points are mutually visible if the result
of the query is empty (see Figure \ref{fig:pointvis}).

\NOTA{
\begin{figure}
\centerline{\psfig{file=graficoVis.ps,width=6cm}}
\vspace*{3mm}
\caption{\label{fig:ptvis:gra}
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
$\real^3$ 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.}
\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_1 p_2$ 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_1 p_2$ 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_1 p_2$ 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 \ref{fig:uncertainty}).

FIGURA DA FARE

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_1 p_2$ have a visibility value 1. 
If some point of $p_1 p_2$ 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_1 p_2$, let $d$ be such a distance.
Then the visibility value for $p_1 p_2$ 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 \ref{fig:segvis}).

\begin{figure}
\centerline{\psfig{file=segvis.eps,width=5cm} }
\caption{\label{fig:segvis}
Computing the visibility of segment $p_1 p_2$ from $v$ reduces 
to a local query using triangle $v p_1 p_2$ as a region of interest.}
\end{figure}

??????????????????

\subsubsection{Viewshed Computation}
\label{sub:viewshed}

Computing the {\em viewshed} of a given viewpoint $v$ on a TIN $T$
consists of determining the portions of each triangle
of $T$ that are visible from $v$.

The problem of viewshed computation has been extensively
studied for TINs, and for general three-dimensional scenes.
Viewsheds can be computed from an MT
by extracting first a TIN at the desired resolution,
and then applying one of the existing viewshed algorithm for TINs
%%%\cite{ReiSen88,KatAl91,PreVit92,OveSha92,BoiDob92,DeB93}
(see \cite{DeFMag94} for a survey).

The most popular viewshed algorithms for TINs traverse the
TIN triangles in front-to-back order with respect to the given
viewpoint and compute the visible and invisible portions
of each triangle directly during such traversal.
They exploit the fact that a triangle $\sigma$
can only be obscured by triangles that precede it in the
front-to-back order;   
thus, when $\sigma$ is traversed, we already have all necessary
information to determine the visibility situations of $\sigma$.

Viewshed computation is an expensive task since the
worst-case space complexity of the viewshed can be as high as
$\Omega(n^2)$ for a TIN with $n$ vertices \cite{ColSha89}.
Thus, we can save time and computation resources by computing it on a
terrain representation at a reduced resolution.
In general, visibility computations are sensitive to elevation
errors near the viewpoint; therefore it is recommended
to ensure a sufficient accuracy near the viewpoint,
and decrease it progressively with distance \cite{FelGri90}.

As in the case of interactive terrain visualization,
we define our threshold function in $\real^2$.
Given a generic point $p\in\real^2$, we denote with $d$
the distance of $p$ from the viewpoint $v$.
Our thershold function increases linearly with $d$
according to the expression $\THR(p) = c_{dist} d$, 
where $c_{dist}$ is a positive constant.

A {\em global query} is performed in order to extract 
a TIN representing the whole terrain according to the
variable-resolution criteria illustrated above.
On such TIN, a viewshed algorithm is then applied.
Since viewshed algorithms need adjacency information 
for the TIN on which they operate, such information
is generated within the extraction algorithm.

The viewshed of a terrain is usually computed for either
a fixed viewpoint, or for a fixed set of viewpoints
(e.g. a set of facilities such as transmission or 
monitoring stations on a terrain).
If the viewshed is computed just once, then the corresponding 
TIN can be extracted by applying a static query algorithm
(which requires less memory).

In some situations, however, it might be useful to compute the
viewshed initially on a rather rough terrain representation, and then
refine it interactively in some interesting areas that are 
determined based on the initial sketch of the distribution of visible
and invisible terrain areas.
In such cases it is necessary to modify the error threshold
function and extract a new TIN.
For instance, if the user decides to refine the viewshed 
in a specific area $A$ of the terrain, then the threshold function
must be redefined in such a way that it gives smaller values 
(i.e., requires a more accurate representation), 
for the view directions intersecting $A$.
Thus, the expression of the threshold function becomes 
$\THR(p) = c_{dist}(\theta) d$,
where now $c_{dist}$ is a function of the angular position $\theta$
of point $p$ with respect to the viewpoint $v$
(see Figure \ref{fig:viewsect}),
and it can be changed interactively by the user.

\begin{figure}
\centerline{\psfig{file=viewsect.eps,width=5cm} }
\caption{\label{fig:viewsect}
If $A$ is an area of interest where the viewshed must be refined,
then factor $c_{ang}(\theta)$ is smaller for 
$\theta_1\leq \theta \leq\theta_2$ than elsewhere.}
\end{figure}

As $c_{dist}$ changes, a new TIN must be extracted and
the corresponding viewshed must be computed.
In such a context, it is interesting to use a dynamic
TIN extraction combined with a dynamic viewshed algorithm.
Dynamic viewshed algorithms maintain the visible portions 
of a set of triangles under on-line insertion and deletion 
of triangles \cite{DeFMagCOSIT95,DobYvi93}.
If we record the changes in the extracted TIN
(i.e., the set of triangles that disappear and the
ones that replace them), we can avoid recomputing the viewshed from
scratch, and instead use a dynamic viewshed 
algorithm to update it by removing the contribution of the 
old triangles and inserting that of the new triangles.

\NOTA{ TOLTO SU SUGGERIMENTO DI ENRICO
A dynamic viewshed algorithm intrinsecally 
exhibits higher time complexity than a static one, and,
in particular, it cannot reach worst-case optimality.
In \cite{DobYvi93,DeFMagCOSIT95}, 
the expected time complexity for updating the viewshed after
the insertion or deletion
of a triangle, when $n$ triangles are present, is $O(n \log n)$.
Now, we compare the cost of updating a viewshed against the
cost of recomputing it, in order to determine the extent to 
which a dynamic approach is convenient.
Let $n_1$ and $n_2$ be the number of triangles in the
previous and in the current TIN, respectively.
Computing the new viewshed
by scratch takes a time equal, in the worst case, to $O((n_2)^2)$,
if the optimal algorithm by Edelesbrunner, Guibas and Sharir
\cite{EdeGuiSha89} is used.
We denote by $k_{old}$ and $k_{new}$, respectively, the number 
of triangles appearing in the new TIN, and not in the old one,
and the number of triangles
appearing in the old TIN, and not in the new one.
(clearly, $k_{old} \leq n_1$ and $k_{new} \leq n_2$).
Updating the viewshed costs $O(k_{old} n_1 \log n_1 )$ for deletions,
and $O(k_{new} n_2 \log n_2)$ for insertions.
We assume that the two TINs ``so close'' to each other
that $n_2$ and $n_2 = \Theta(n)$.
The update of the viewshed is more efficient than its direct recomputation
if $O( (k_{old}+k_{new}) n \log n)$ is less than $O(n^2)$, i.e., if
$k_{old},k_{new} \in O( \frac{n}{\log n} )$.
}

A module for computing viewsheds from TINs extracted
from a Multi-Triangulation is currently under implementation.

\subsubsection{Horizon Computation}
\label{sub:horiz}

Similar approaches as those illustrated in the previous section
can be used to compute other visibility structures
on a terrain, for instance, the {\em horizon}.

The horizon of a terrain \cite{ColSha89}
corresponds to the distal boundary of the visible area
from a viewpoint in all directions.
%%
\NOTA{
More formally, the horizon is the locus of points
$P$, lying on the terrain surface, such that:
\begin{itemize}
\item   
  $P$ is visible from $V$, and
\item   
  for any point $Q$ on the surface, such that
  such that the projections of $P$, $Q$, and $V$ onto the $xy$-plane
  are aligned, with the one of $P$ lying between the other two,
  $Q$ is not visible from $V$.
\end{itemize}
}
On a TIN, the horizon is a chain of portions of
triangle edges, radially sorted around the viewpoint.

\NOTA{
A worst-case size of $\Theta(n \alpha (n))$ has been
proven for the horizon of a TIN with $n$ vertices \cite{EdeGuiSha89}.
Algorithms for computing the horizon of a viewpoint of a TIN
have been proposed in \cite{Ata83,Her89,DeFMag95}.
}

Similar error thresholds as those introduced in Section 
\ref{sub:viewshed} can be used for extracting a TIN from an MT;
existing horizon algorithms are then applied to such TIN.
As in the case of viewsheds, a dynamic approach can be
used to interactively refining an initially sketched the horizon.
Dynamic horizon algorithms can be used for such a purpose.
%%In \cite{DeFMagCOSIT95},
%%the expected time complexity for updating the horizon 
%%is $O(\alpha(n) \log n)$.
\NOTA{
As in Section \ref{sub:viewshed}, we assume that the sizes of
the current and of the previous TIN are both in $\Theta(n)$
and we denote by $k_{old}$ and $k_{new}$ the number of triangle 
removed and inserted, respectively, when passing from the previous
to the current TIN.
The horizon can be either re-computed from scratch,
or dynamically updated.
In the following, we compare these two approaches.
Re-computing the horizon by scratch costs $O(n \log n)$,
if the optimal algorithm by Hershberger \cite{Her89} is used.
The update of the horizon costs
$O( (k_{old}+k_{new}) \alpha(n) \log n)$.
The update process is convenient when
$k_{old}$ and $k_{new} = O( \frac{n}{\alpha(n)} )$
(note that $\alpha$ is very close to be a constant function of $n$).
}

\section{Conclusions and Future Work}
\label{sec:concl}

In this paper we have described VARIANT, a prototype system 
for processing and visualizing terrains at variable resolution based
on a special multiresolution model, called the Multi-Triangulation.
We have briefly presented the MT, we have
illustrated the architecture of the system
and described the various components of the system itself.

We are currently implementing the following modules that
will become part of the system:
\begin{itemize} 
\item
  The method, described in Section \ref{sub:features},
  for integrating a multiresolution representation of line
  features in an MT.
\item
  History writers that operate bottom-up based on edge collapses.
\item
  New compressed data structures for MTs.
\item
  MT-clients for computing horizons 
  and for solving visibility queries involving one- and 
  two-dimensional entities.
\end{itemize}

We have developed a technique for the management of 
Multi-Triangulations in {\em secondary memory}.
This problem is relevant because multiresolution deals with huge 
amounts of data, likely leading to structures too big to fit in memory.
In GISs, often terrain datasets have such a
size that a single-resolution terrain model built from such sets
would be too big to be loaded into memory.
The same problem arises even more likely for an MT, which represents
the terrain at a wide range of resolutions including the maximum one.

\NOTA{ TAGLIATO CORTO
  Data structures and algorithms for the management of MTs on
  secondary storage can be designed for solving two different problems:
\begin{enumerate}
\item
  given a large MT on disk, load just a part of it,
  and then apply query algorithms in main memory to the
  loaded part;
\item
  define and apply query algorithms having a
  direct access to a large MT resident on disk.
\end{enumerate}
For Problem 1, in \cite{Mag99} we have presented a method
based on splitting an MT into parts which are still MTs and which
can be loaded separately, as well as algorithms for
selecting the parts of the split MT which must be loaded
for answering a given local query.
Problem 2 requires methods 
  that allow the efficient retrieval of the disk page 
  containing a part of an MT, when access to that portion is required.
  We are currently studying an indexing technique based on the 
  two spatial coordinates $x$ and $y$ plus a third coordinate
  representing the depth in the DAG.    
\end{itemize}
FINE TAGLIO}

The technique we have developed solves the following problem:
  given a large MT on disk, load just a part of it,
  and then apply query algorithms in main memory to the
  loaded part.
The method is 
based on splitting an MT into parts which are still MTs and which
can be loaded separately. 
Algorithms have been designed for
selecting the parts of the splitted MT which must be loaded
for answering a given local query \cite{Mag99}.

For its modular structure, VARIANT is an extensible system and
allows the addition of further modules as soon as they are developed. 
In the future, we are planning to add
MT-clients performing specific computations such as
%%%%extraction of {\em drainage networks and basins},
computation of {\em optimal paths}.
%%%%, etc.

\NOTA{
Programs that compute drainage, and simulate behavior of water flow can take
advantage of the possibility to use higher accuracy only in the proximity of 
most important flow channels (rivers), and/or of critical regions 
(e.g., regions that might be subject to floods). 
Also in this case, it is possible to improve performance by adopting suitable
threshold functions, increasing with distance from regions of interest.
For instance, if the drainage network related to a given river 
must be extracted, the threshold function can be increasing with 
distance from the river, while the region of interest might 
be limited to the slopes around its valley.
}

Paths can be defined on a terrain
according to various optimality criteria,
e.g., paths of minimum length, paths with minimum variation
in height, with minimum slope along the path,
paths avoiding or preferring certain types of soil
(see \cite{BerKre97,LanMahSac97,Kre94PATH} for various
characterizations of optimal paths).
Multiresolution can help optimization tasks
since it gives the possibility of reasoning on a terrain model at
increasingly high accuracy,
while progressively refining a rough candidate solution.

