Reconstrução de superfície a partir de um conjunto não-organizado de pontos

Abstract

Surface reconstruction is the area dedicated to get complex geometric models from a finite set of unorganized points of object surfaces. This area has become increasingly important in Geometric Modeling and other applications such as Computer Graphics, Computer Vision, VirtualReality and Engineering. This Master thesis describes a broad survey of the main reconstruction methods. These methods are divided in four categories: sculpturing methods, implicit function methods, incremental methods and warping methods. Emphasis is given to sculpturing methods, especially to the Crust family algorithms, because they have theoretical guarantees of reconstruction based on the sample density.In 2D, it is demonstrated that the reconstruction guarantees for the beta-Skeleton algorithm are better than for the raw crust algorithm. However, the first one cannot be extended to R3. The three-dimensional versions of the crust and power crust algorithms are presented, together with the main theorems that define their reconstruction guarantees.The obtained results for the 3D raw crust and power crust algorithms are presented. The CGAL (Computational Geometry Algorithms Library) library was used to implement these algorithms. This library provides the main methods in these algorithms, as the traditional and weighted Delaunay triangulations. Moreover, it is able to represent a floating point value with arbitrary precision, wich is necessary for geometric calculations in the triangulations. Through these implementations it is shown that the crust algorithm (2D and 3D versions) is much simpler than power crust, not presenting difficulties in its implementation. Power crust is an algorithm more complex, that involves supplementary calculations such as: weighted Delaunay triangulation, intersecting polar balls and ortocenter calculations. It presents better reconstruction guarantees of that raw crust, however, its output was not satisfactory because numerical difficulties in its implementation have been found.Thus, this work constitutes a base for developing a library to reconstruct objects from sample points, wich can be integrated to the GSM (GOPAC Solid Modeler). With this future integration, the GSM will be able to directly generate object models from three- dimensional points obtained from a 3D scanner.