The Multi-Triangulation

The Multi-Triangulation is a multiresolution model for triangle meshes, proposed initially in [Puppo1996] and developed in [De Floriani et al.1997,De Floriani et al.1998,Magillo1999]. In VARIANT, we use an MT to represent TINs at multiple resolutions. Here we just give a brief outline of the model. The interested reader may refer to works cited above for details.

Figure: The plane triangulation underlying a TIN and its embedding in three-dimensional space.
\begin{figure*}\centerline{ \psfig{file=tin.eps,width=5cm} }\end{figure*}

A TIN consists of a plane triangulation where each vertex has an associated elevation value. Vertex elevations define an embedding of the plane triangulation into the three-dimensional space (see Figure [*]). Without loss of generality, we use a planar patch to project each triangle in space. However, smooth surfaces can be also obtained, without modifying the overall framework, by using a curved patch to project each triangle (e.g., computed on the basis of both elevation and surface normal at each vertex [Renka and Cline1984]).

SEMBRA SUPERFLUO, PER ORA TOLTO We are interested in modeling at multiple resolutions the triangulation T underlying a TIN. Thus, in the remainder we identify a TIN with the corresponding plane triangulation T, whenever elevations are not relevant.

The intuitive idea behind a Multi-Triangulation (MT) is the following. Consider a process that starts with a coarse TIN and progressively refines it by performing a sequence of local updates. A popular example of refinement sequence consists of the iterative insertion of vertices, where each new vertex v modifies the TIN by substituting a set of triangles filling a polygon with a fan of triangles incident at v, and triangulating the same polygon [Fowler and Little1979]. RISCRITTA PIU' IN BREVE E CON MENO SIMBOLI Each local update replaces a subset $\overline{{T_i}}$ of triangles with another set Ti of triangles at a higher resolution, which match the boundary of the hole left when removing $\overline{{T_i}}$. Such update is described by the pair Ci≡($\overline{{T_i}}$, Ti). Updates forming an MT are refinement updates, i.e., they insert more triangles than they remove. More in general, a local update replaces a subset of triangles of a TIN with another, more numerous, set of triangles representing the same portions of terrain at a higher resolution. Thus, an update is described by the two subsets of triangles removed and inserted by it, respectively (see Figure [*]a).

Figure: (a) An initial triangulation and a sequence of four updates: updates 1 and 2, as well as updates 3 and 4, are mutually independent, while 3 depends on both 1 and 2, and 4 depends on 2; (b) the corresponding MT: an additional dummy update represents the creation of the initial TIN.
\begin{figure*}\centerline{ \psfig{file=mt_bw.eps,width=11cm} }\end{figure*}

We define the following dependency relation between updates: an update C2 depends on another update C1 if and only if C2 removes some triangles introduced with C1. Intuitively, this means that C2 can be applied only if C1 has been applied before it. The transitive closure of dependency relation defines a partial order, which is represented graphically as a directed acyclic graph (DAG), as depicted in Figure [*]b.

DETTO PIU' IN BREVE A Multi-Triangulation (MT) encodes the relation of dependency between updates in the form of a directed acyclic graph (DAG) where nodes represent updates, and arcs represent dependency links between them. An additional dummy update corresponds to the creation of the initial TIN. A directed arc (C1, C2) represents the fact that update C2 depends on C1. The partial order encoded in an MT is used as a mechamism to select subsets of updates that are closed with respect to the partial order.

This structure is used to obtain different sequences of updates formed by subsets of the initial sequence. A set of updates of an MT that is closed with respect to the partial order, i.e., that contains all parents of each of its nodes, DETTO PIU' IN BREVE for every Ci∈S, all the parents of Ci (i.e., all updates Ci depends on) are in S. Any such closed set of updates provides a TIN representing the terrain at a certain resolution (see Figure [*]). It is possible to perform more updates in some areas and fewer updates elsewhere, depending on the resolution requirements imposed by a given application, thus producing a TIN having a resolution variable through the domain. Such an operation, called selective refinement, is the basis for managing terrain resolution on-line.

Figure: (a) A closed subset of the nodes of the MT of Figure [*], is given by the nodes above the curve (i.e., nodes 0, 1, 2, 4). (b) The TIN resulting from applying such updates.
\begin{figure*}\centerline{ \psfig{file=closed.eps,width=10cm} } \centerline{ {\bf (a) \hspace*{5cm} (b)} }\end{figure*}