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:

The user queries an MT by specifying two conditions, which evaluate a tile based on its spatial location, geometry, and possibly other attributes: 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):

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":

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:

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: 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.