Computing a correct representation from a set of sample points is essential in various contexts, such as in applications including, for instance, medical imaging, reverse engineering, virtual reality, or special effects for cinema. The problem, addressed in this thesis, can be described as follows: given S, a set of points sampled on a three dimensional object O, reconstruct a geometric model of the surface bounding O. The contributions are threefold. First, we describe the implementation of a classic solution in Computational Geometry as a part of the CGAL library (http://www.cgal.org/). The packages, Alpha-shapes in 2 and 3D, are now available in the version 2.3 of the CGAL basic library. Second, we present a new approach to reconstruct orientable surfaces from unorganized point sets. The main idea is to extend incrementally a surface by attaching triangles at its current boundary. Our method is very effective and is able to reconstruct a correct surface for very large and challenging data sets. Moreover, the implementation is fast and memory efficient. Third, we describe a new interpolation method for cross-sections. This approach uses the natural neighbors barycentric coordinates. The reconstructed surface is smooth almost everywhere and is defined only with discrete geometric structures like Delaunay triangulation. Futhermore, the reconstruction is very efficient since all the calculations are performed in 2D.
