Title: Two approaches for polyhedral reconstruction of 3D objects of arbitrary genus

Authors: Thomas Schreiber, Guido Brunnett, Frank lsselhard

Addresses: University of Kaiserslautern, Computer Science, Postfach 3049, D-67653 Kaiserslautern, Germany. ' University of Kaiserslautern, Computer Science, Postfach 3049, D-67653 Kaiserslautern, Germany. ' University of Kaiserslautern, Computer Science, Postfach 3049, D-67653 Kaiserslautern, Germany

Abstract: This paper addresses the problem of constructing a polyhedral approximation of a 3D object, given by a set of scattered points from the object|s surface. Two solutions of this problem are presented. Both methods use the Delaunay triangulation as an initial neighbourhood graph. The first approach is based on Boissonnat|s strategy to remove tetrahedra from the hull of the graph according to a cost function. Our algorithm extends Boissonnat|s work to objects of arbitrary genus and offers an automatic termination procedure. The second method defines a new approach to approximate the minimal spanning Voronoi tree which was introduced by O|Rourke et al. Here, in the first step, tetrahedra are grouped into polyhedra and in a second step they are classified to belong either to the polyhedral reconstruction or not.

Keywords: Delaunay triangulation; polyhedral approximation; reverse engineering; scattered data approximation; surface reconstruction.

DOI: 10.1504/IJVD.1999.005581

International Journal of Vehicle Design, 1999 Vol.21 No.2/3, pp.292 - 302

Published online: 20 Oct 2004 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article