REPRESENTING STEREO DATA WITH THE DELAUNAY TRIANGULATION

This article proposes a coherent way of interpolating three-dimensional data obtained by stereo, for example, with a simplicial polyhedral surface. The proposed method is based on the use of the 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, works for multiple viewpoints 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. © 1990.