**The Multi-Triangulation (MT)**

*General Information*

A Multi-Triangulation (MT) is a tool which provides representations of a surface through triangle meshes at variable resolution, i.e., meshes which can be more or less refined according to user-defined requirements. The user queries an MT by specifying two parameters:

- a condition telling when the resolution of a triangle is acceptable (based on the spatial location, geometry, and approximation error of the triangle), and
- a condition telling when a triangle lies in the area of interest for the application (based on the spatial location of the triangle).

The MT answers the query by returning a triangle mesh which represents the surface with the required accuracy inside the focus area.

A large number of relevant spatial operations can be performed at variable resolution on a surface by querying an MT built for such a surface. Examples of such queries are:

- Windowing: a triangle lies in the focus area if and only if it is at least partially contained inside an axis-parallel box;
- Region interference: same as above, but with a window of arbitrary shape;
- Line interference: a triangle lies in the focus area if and only if it intersects a given line;
- View volume clipping: a triangle lies in the focus area if and only if it is at least partially contained into a given view frustum;
- etc.

A variable resolution means that the resolution (density) of the triangle mesh 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 triangles is kept low by reducing the density in areas which are far away from the eye;
- the resolution can be set as high only in the proximity of some special feature (e.g., a detail of interest of an object).

An example

In the following example we can see a triangle mesh by two different
viewpoints. The mesh is extracted considering a conical region with
resolution decreasing with distance from the vertex of the cone.

An MT is made of a collection of elementary triangle meshes, each
representing a portion of the surface at a certain resolution. Many
alternative representations of the same piece of surface exist in an
MT. A mesh representing the whole surface at variable resolution can be
obtained by assembling the elementary triangle meshes. The triangle
meshes forming an MT are arranged in a directed acyclic graph, which
provides all the ways in which they can be combined to provide
consistent surface descriptions.

The construction of an MT is based on iterative methods for the generation of triangle meshes representing a surface. Such methods are of two kinds:

- progressive refinement: an initial coarse mesh is progressively refined through a sequence of updates (examples of updates are adding vertices, expanding a vertex into an edge or a triangle);
- progressive coarsening: a mesh at full resolution is pregressively coarsened through a sequence of updates (examples of updates are removing a vertex, collapsing an edge or a triangle into a vertex)

*Back to previous page*