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.
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
of triangles with another set Ti
of triangles at a higher resolution, which match the boundary
of the hole left when removing
.
Such update is described by the pair
Ci≡(
, 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).
![]() |
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.
![]() |