Triangulation

The result of local reconstructions is a set of 3D contour points. A parametric description of this set of points is required for a global surface representation. Such a description is used to build functions which approximate or model the object surface. This can be either a parametrisation of the surface or first, a triangulation of the rim points. In this section, we briefly discuss such a description and we present our approach.

If a parametrisation of the surface is available then an approximation can be computed using, for example, spline functions [dB 78]. However, without any a priori information on the object surface, it might be difficult to compute such a parametrisation. Another approach consists in triangulating the reconstructed points. The object surface can then be represented as a set of connected polygonal facets. The advantage is that only topological information are required: the neighbours of each vertexof the triangulation.

An optimal triangulation in the 2D case is the Delaunay triangulation which maximises the minimum angle of the resulting mesh. The generalisation to the 3D case leads to the tetrahedrisation of the set of points which is a volume. This method is therefore not well adapted to the case of rim points; indeed rims describe the object surface or only part of it and thus, they do not necessarily define a volume. In addition, the 3D points are organised in contours and hence, the resulting triangulation should conserve this information.

Consequently, our approach consists in constructing a triangular mesh which respect the adjacency of successive rims:

• two 3D points can be connected if and only if they are on two consecutive 3D rims.

Thus, the problem of triangulating the set of rim points is reduced to one of triangulating each pair of consecutive rims in the sequence. This leads to the following condition for a triangular facet:

• A facet is defined by two points on one rim and one point on the next or the previous rim.

This condition is not sufficient to define a unique triangulation of a rim pair and an additional criterion must be used to isolate one set of facets. The triangulation of a rim pair corresponds therefore to the problem of finding a minimum cost path in a directed graph, in which the vertices correspond to the set of all possible connections between the points of the rim pair [Fuc 77]. A solution can be found in n² operations where n is the number of points on a rim.

The additional criteria that can be used are: the sum of facet areas, the sum of edge lengths or the sum of angles. However, experimental results show very little difference between these criteria.