THE MULTI-TESSELATION (MT)
What is an MT?
A Multi-Tesselation (MT) provides representations of a spatial object
through simplicial complexes at variable resolution, i.e., complexes which
can be more or less refined according to user-defined requirements.
Here, a spatial object can be any k-manifold subset of the
d-dimensional Euclidean space, for generic k and
d.
In the following, we use the term tile for a simplex, and
tesselation for a simplicial complex.
This notation is motivated by historical reasons: the MT was initially
developed for two-dimensional simplicial complexes and called
Multi-Triangulation.
In the above notation, we can still use the acronym MT for the
dimension-independent case.
A variable resolution means that the resolution (density) of the tiles can
be locally adapted to the needs of the application. For instance:
- A resolution decreasing with the distance from the viewpoint allows
high-quality images at a lower processing cost since the overall number
of tiles is kept low by reducing the density in areas which are far
away from the eye.
- The resolution can be high only in the proximity of some
interesting feature of the object (e.g., a road on a terrain).
The user queries an MT by specifying two conditions, which evaluate a tile
based on its spatial location, geometry, and possibly other attributes:
- A resolution filter, i.e., a condition telling whether or
not the resolution of a tile is acceptable;
- A focus condition, telling whether or not a tile is of
interest for the application.
The MT answers the query by returning a tesselation which represents
the object at the required resolution inside the area of interest.
What does an MT look like?
An MT is a partially ordered set of local update operations which
progressively refine an initial low-resolution tesselation into a final
high-resolution tesselation.
The basic idea is the following:
We start from a sequence of update operations refining a tesselation
(equivalently, we can start from a sequence of update operations coarsening
a tesselation, and reverse the sequence).
Each update operation (in the following simply called an update)
consists of removing a set of tiles and replacing them with another set
of tiles at a higher resolution, covering the same portion of object.
An update B directly depends on a previous one A if
B removes some tile that has been created by A.
The dependency relation is defined as the transitive closure of the relation
of direct dependency, and it is a partial order.
Obviously, an update B cannot be performed if all updates A, such that B
depends on A, have not been performed before. However, mutually independent
updates can be interleaved in any order, and even omitted from the sequence.
Dependency typically occurs between updates performed at nearby spatial
locations. It is possible to omit from the sequence the updates
occurring in areas that are not of interest, thus obtaining tesselations
whose resolution is variable through space.
The Multi-Tesselation captures the relation of dependency (partial order)
between the updates of a sequence, and represents it as a directed acyclic
graph (DAG):
- nodes are update operations;
- arcs are links of direct dependency.
An arc (A,B) exists whenever update B depends on
A, i.e., a non-empty set of tiles introduced by A is
removed by B.
An additional node represents the update that creates the initial coarse
tesselation, and it is called the root of the MT.
The DAG provides all the legal ways to obtain sequences of subsets of the
original set of updates which are consistent with the partial order, i.e.,
which can be performed on the initial tesselation, and give a tesselation
as a result.
How does an MT work?
A consistent set of updates in an MT is a non-empty subset N
of its nodes, such that, for every update A in N,
also all the parents of A are in N
The updates of a consistent set can be performed in any total order which
extends the partial order represented in the DAG, and the result is a
tesselation. By using different consistent sets, tesselations representing
the object at different (possibly variable in space) resolutions can be
obtained.
Given a resolution filter defined by the user, an MT can automatically
provide a tesselation of "minimum cost", sufficient to guarantee that the
user-defined resolution requirements are satisfied.
There are two criteria for interpreting the words "minimum cost":
- Static criterion:
A tesselation generated by the smallest consistent set of nodes
sufficient to satisfy the resolution filter.
A minumim number of nodes in the consistent set implies a minimum number
of tiles in the tesselation.
The algorithm used to determine such a consistent set performs a top-down
traversal of the DAG: it starts from a set containing just the root,
and progressively includes nodes to refine the corresponding tesselation
where the resolution filter is not satisfied.
- Dynamic criterion:
We assume that the extraction engine remembers the consistent set
N of nodes (and its tesselation) resulting from the previous
query.
The answer to the new query is the tesselation corresponding to a
consistent set N' of minimum distance from N
(where the distance is
measured as the number of nodes which must be added to and deleted from
N to obtain N').
This implies a minimum computational cost, if the new query parameters
are close enough to the previous ones.
The algorithm consists in an iterative modification of the current
set of nodes by:
- adding nodes that refine the tesselation where the resolution
filter is not satisfied;
- deleting nodes which are not strictly necessary to satisfy the
resolution filter, thus coarsening the tesselation where possible.
In addition, the user can specify a focus condition in order to
restrict the application of the resolution filter, and possibly, the output
tesselation, to the parts of the object which are of interest for him.
There are two criteria to define the effect of a focus condition:
- Global criterion:
The influence of the resolution filter is restricted to those tiles
which satisfy the focus condition.
It is like applying a "modified" resolution filter equal to
"(NOT focus) OR filter".
The output tesselation has the following property:
- it covers the whole object;
- all tiles that satisfy the focus condition, satisfy the resolution
filter condition as well.
Tiles which do not satisfy the focus condition may be arbitrarily coarse.
- Local criterion:
The output tesselation is restricted to those tiles which satisfy the
focus condition.
The output tesselation is formed by tiles that satisfy both the
focus condition and the resolution filter, possibly covering just a
portion of the object.
The algorithm traverses fewer nodes and arcs in the DAG, since those
not containing active tiles are pruned off.
The global criterion is available in both versions: the static and the
dynamic one. Only the static version of the local criterion is available.
How is an MT built?
An MT can be built through any iterative method for the generation
of tesselations approximating spatial objects.
Such methods modify a tesselation by performing a sequence of updates.
They are of two types:
- Progressive refinement:
Start from a tesselation at low resolution and progressively refine it to
the maximum resolution. Examples of updates, for a triangulation, are:
adding a vertex, expanding a vertex into an edge or a triangle.
- Progressive coarsening:
Start from a tesselation at high resolution and progressively coarsen it
to the minimum resolution. Examples of updates, for a triangulation, are:
removing a vertex, collapsing an edge or a triangle into a vertex.
The construction of an MT through progressive refinement reduces detecting
links of direct dependency between the updates, and arranging the updates
into a DAG based on such links.
The construction of an MT through progressive coarsening is done by
"reversing" the sequence of updates in order to simulate a progressive
refinement.