The goal of the project is the development of a surface-based approach to the construction of surfaces from three-dimensional clouds of points, for instance sampled from a three-dimensional shape using a digitizing device like a laser scanner. The basic approach is to connect the points by a graph of which the edges lie on the desired surface. The initial graph is the so-called surface description graph (SDG) which is based on beta-environment graphs. This surface wire frame is successively augmented by inserting triangles to a triangular mesh. The process follows basic constraints that are derived from knowledge on smoothness behaviour of sampled surfaces. By this method variations in the point density as well as sharp and detailed features of the surfaces can be reconstructed reliably. The algorithm has been implemented in C++ (using STL) into the software-system RecEye using the toolkits Tcl/Tk, Tix, OpenInventor, and OpenGL.

Graphical User Interface:

3D shutter glasses (CrystalEyes) are supported as well as a hand gesture control for picking subsets of points during user interaction.

Fully automatic reconstruction:

Reliable surface reconstruction from 3D point (cloud) data: The input point data may be totally unorganized. Strong variations in the point density are no problem and even sharp edges (surface turns) of the object are reconstructed reliably. Furthermore, the input data can be delivered by any arbitrary scanning system (tactile, laser etc.). The input data is solely the point set (first picture). Then, in a first step the surface description graph (SDG) is computed out of this point set. This graph is then filled sucessively with triangles. The next three pictures show two snapshots during this reconstruction process and the final result.

The video below shows a complete reconstruction process in slow motion.

Automatic noise reduction in the point set:

Locally-Restricted Reconstruction and Interactive Shape Design:

If the user is only interested in the reconstrution of a subset of the data site, the reconstruction algorithm can be modified as follows:

Points are sequentially connected by single red edges (first three pictures).

The graph represents a first surface estimation. These edges are *projected *onto the point set and used for the incremental reconstruction algorithm (first picture). The graph has been used for the reconstruction algorithm as wire frame (second picture). In order to reconstruct the part around the nose, two more edges are inserted into the triangular mesh (next two pictures).

After the two edges have been inserted (first picture) the edges of the mesh and the newly added edges are projected onto the point set (second picture). The reconstruction of the blue wire frame (third picture) delivers a first good preview of the area the user is interested in.

In order to further extend the reconstruction area, only one single edge is drawn from the mesh to the nose tip (first picture) and then the mesh is projected onto the point set (second picture). Finally, the reconstruction result delivers the front part of the skull (last picture).

The complete interaction process has been performed in about two minutes.