The Multi-Triangulation (MT)

General Information

# What is a Multi-Triangulation?

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.

# What does an MT look like?

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.

# How to build an MT

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