Last update: August 4, 2004

BACK

References for Computational Geometry by INRIA teams:

• Boissonnat, J.-D. et al. :
  • Smooth Surface Reconstruction via Natural Neighbor Interpolation of Distance Functions, 2000 & 2002.
  • Natural Neighbor Coordinates of Points on a Surface, 2000 & 2001.
  • Geometric structures for three-dimensional shape representation, 1984.
• Boyer, Edmond et al. :
  • Regular and Non-Regular Point Sets: Properties and Reconstruction, 2001.
• Da, Frank et al.:
  • A Greedy Delaunay Based Surface Reconstruction Algorithm, 2002.
  • Shapes Interpolation, PhD of TKF Da, 2002.

BibTeX references

We present an algorithm to reconstruct smooth surfaces of arbitrary topology from unorganized sample points and normals. The method uses natural neighbour interpolation, works in any dimension and allows to deal with non uniform samples. The reconstructed surface is a smooth manifold passing through all the sample points. This surface is implicitly represented as the zero-set of some pseudo-distance function. It can be meshed so as to satisfy a user-defined error bound. Experimental results are presented for surfaces in R³.

KEY-WORDS : COMPUTATIONAL GEOMETRY / VORONOI DIAGRAMS / NATURAL NEIGHBOR INTERPOLATION / SURFACE RECONSTRUCTION

Notes:

• The normal field gives a sign to the distance function.

Natural neighbour coordinates and natural neighbour interpolation have been introduced by Sibson for interpolating multivariate scattered data. In this paper, we consider the case where the data points belong to a smooth surface $\sss $, i.e. a $(d-1)$-manifold of $\R ^d$. We show that the natural neighbour coordinates of a point $X$ belonging to $\sss $ tends to behave as a local system of coordinates on the surface when the density of points increases. Our result does not assume any knowledge about the ordering, connectivity or topology of the data points or of the surface. An important ingredient in our proof is the fact that a subset of the vertices of the Voronoi diagram of the data points converges towards the medial axis of $\sss$ when the sampling density increases.

KEY-WORDS : COMPUTATIONAL GEOMETRY / VORONOI DIAGRAMS / MEDIAL AXIS / NATURAL NEIGHBOUR INTERPOLATION / SURFACE RECONSTRUCTION

Web links:

• ACM portal : http://doi.acm.org/10.1145/357346.357349

Different geometric structures are investigated in the context of discrete surface representations. It is shown that minimal representations (i.e., polyhedra) can be provided by a surface-based method using nearest neighbors structures or by a volume-based method using the Delaunay triangulation. Both approaches are compared with respect to various criteria, such as space requirements, computation time, constraints on the distribution of the points, facilities for further calculations, and agreement with the actual shape of the object.

In this paper, we address the problem of curve and surface reconstruction from sets of points. We introduce regular interpolants, which are polygonal approximations of curves and surfaces satisfying a new regularity condition. This new condition, which is an extension of the popular notion of r-sampling to the practical case of discrete shapes, seems much more realistic than previously proposed conditions based on properties of the underlying continuous shapes. Indeed, contrary to previous sampling criteria, our regularity condition can be checked on the basis of the samples alone and can be turned into a provably correct curve and surface reconstruction algorithm. Our reconstruction methods can also be applied to non-regular and unorganized point sets, revealing a larger part of the inner structure of such point sets than past approaches. Several real-size reconstruction examples validate the new method.

Author Keywords: Surface reconstruction; Sampling condition; Regular interpolants.

NB: Based on Da's thesis.

In this paper, we present a new greedy algorithm for surface reconstruction from unorganized point sets. Starting from a seed facet, a piecewise linear surface is grown by adding Delaunay triangles one by one. The most plausible triangles are added in the first place, in a way that prevents the appearance of topological singularities. The output is thus guaranteed to be a piecewise linear orientable manifold, possibly with boundary. Experiments show that this method is very fast, and achieves topologically correct reconstruction in most cases. Moreover, it can handle surfaces with complex topology, boundaries, and non uniform sampling.

KEY-WORDS : DELAUNAY TRIANGULATION / SURFACE RECONSTRUCTION / ADVANCING FRONT METHOD

Paper in electronic formats: http://www.inria.fr/rrrt/rr-4564.html

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.

KEY-WORDS : 3D RECONSTRUCTION / GEOMETRIC MODELING / POINT CLOUDS / CROSS-SECTIONS / SAMPLE SIMPLIFICATION / MEDICAL IMAGING / REVERSE-ENGINEERING / CAD

Manuscript in French (postscript): http://www.inria.fr/rrrt/tu-0699.html

BACK

Page created & maintained by Frederic Leymarie, 2001-4.
Comments, suggestions, etc., mail to: leymarie@lems.brown.edu