This article proposes a coherent method of interpolating 3D data obtained for example by stereo, with a polyhedral surface by means of the Delaunay Triangulation. We first give some theoretical properties concerning the approximations of sampled objects we obtain when the sampling rate increases, based on the study of their skeleton using some tools of Mathematical Morphology. Then, we present the algorithms and their complexity analysis which yield both a surface representation of objects and a volume representation of free space which may be useful in Robotics. This goal is achieved by means of a simple visibility criterion. The method is intrinsically discontinuity preserving and can be used for the integration of multiple viewpoints.

A coherent way of interpolating 3-D data obtained by stereo, for example, with a simplicial polyhedral surface is discussed. The method is based on constrained Delaunay triangulation; the polyhedral surface is obtained by using a simple visibility property to mark tetrahedra likely to be empty. The method is intrinsically discontinuity-preserving and yields both a surface representation of objects and a volume representation of free space which may be useful in robotics. Algorithms to implement the method are described and their complexity analyzed in the worst case and average case situations where tools of probabilistic geometry are used.>