Surface Reconstruction - Triangulating Scattered Points

by Géza Kós

Triangulating surfaces from unorganised sets of sampling points is an important problem in the reverse engineering of geometric shapes. At the Geometric Modelling Laboratory of SZTAKI, a new, efficient triangulation algorithm has been developed.

Reverse engineering of geometric shapes is the process of converting a large number of measured data points into a concise and consistent computer representation. In this sense, it is the inverse of the traditional CAD/CAM procedures, which create physical objects from CAD models.

Triangulating scattered point-sets is a very important problem of reverse engineering. Given a set of unorganised points that lie approximately on the boundary surface of a three-dimensional object, and without a priori information on the topology, our goal is to reconstruct the surface by building a triangular mesh using the given points as vertices.

The resulting polyhedron can be the input of further procedures like surface fitting, or can be visualised with various textures. (For example, in computer-animated films the characters are often created as clay models first, then the 3D scanned and triangulated models are used for visualisation.)

All algorithms aiming to solve this problem must overcome several difficulties. The first one is related to the size and quality of the input. Modern 3D scanners make it possible to acquire several (ten) millions of sample points on the object's surface. For current applications, a triangulation algorithm must be prepared to efficiently handle such huge data sets. Furthermore, the point density is often very uneven due to curvature variations, undesirable outlying elements may occur, and scanning techniques affect sampling distribution. The input also contains noise (measurement errors).

Another problem is related to the topology of the surface. The measured object can be of arbitrary topology, and its surface may have positive Genus. It is also typical that the point-set represents not a complete volumetric object, but only certain surface portions of the boundary, and only these parts need to be reconstructed. In such cases, the surface has holes and/or open boundaries.

The main algorithmic difficulty is related to the dimension. Due to Voronoi's and Delaunay's works, creating tessellation in the space of any dimension is very easy if the tiles have the same dimension as the space. The triangulation problem is slightly different, since the algorithm must create a two-dimensional object in a three-dimensional space. This leads to more complicated topological situations.

Previous algorithms have used many interesting ideas. Some basic algorithms work by projecting the points to a carrier surface and creating triangulation in the parametric domain of the carrier surface. These methods are somewhat limited for disconnected surface portions and objects with positive Genus. Other approaches start from various subsets of the 3D Delaunay tessellation of the sampling points and try to select a proper subset of the faces. Another very popular idea is to define implicit surfaces containing the given sampling points and extract these surfaces.

Figure 1: Surface to reconstruct.	Figure 2: Input point-set.	Figure 3: Filtered points.

Figure 4: Triangulation on the filtered points.	Figure 5: Decimated triangulation.

The new algorithm developed in SZTAKI offers a different approach to solving the problem. Our algorithm considers the surface as a metric, 2D manifold. Using the position of the sampling points, distances and angles within the manifold are estimated and the relative Delaunay triangulation of the sampling points is computed. The triangulation is built locally around each data point and these local triangulations are merged to give a consistent mesh representation of the surface.

The algorithm was found to be efficient. The current implementation is capable of processing huge data sets: up to 100,000,000 vertices on a commercial desktop PC, which generates up to 200,000,000 triangles.

Since most applications require smaller data sets, the algorithm has been enhanced with two optional decimation steps which reduce the size and complexity of the data. The first decimation step is the curvature-based pre-filtering of points, which can be executed before generating any triangle. This procedure eliminates many points in the large, smooth areas of the surface and retains the original density in the neighbourhood of highly curved regions and boundary loops. By this step, the number of points can be reduced by 70-90 percent, without significant loss of quality in the final result.

The second decimation step is performed after generating the triangles. This procedure takes advantage of the fact that triangulation makes a better error estimate possible and more vertices can be deleted.

This project started within the framework of an EU-supported COPERNICUS project (RECCAD no. 1068) in 1997, and has also been supported by the Hungarian Ministry of Education, Grant No. OMFB-01989/2002.

Link:
SZTAKI GML web page: http://www.sztaki.hu/gml

Please contact:
Géza Kós, SZTAKI
Tel:+36 1 386 8782
E-mail: kosgeza@sztaki.hu