A non-parametric approach to shape reconstruction from planar point sets through Delaunay filtering. (May 2015)

• Record Type: Journal Article
• Authors: Peethambaran, Jiju; Muthuganapathy, Ramanathan
• Is Part Of: Computer aided design. Volume 62(2015)
• Page Start: 164
• Page End: 175
• Publication Date: 2015-05
• Subjects: Shape reconstruction -- Delaunay triangulation -- Hole detection -- Relaxed Gabriel graph -- α-shape -- χ-shape; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2014.12.002
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: In this paper, we present a fully automatic Delaunay based sculpting algorithm for approximating the shape of a finite set of points S in R 2 . The algorithm generates a relaxed Gabriel graph ( R G G ) that consists of most of the Gabriel edges and a few non-Gabriel edges induced by the Delaunay triangulation. Holes are characterized through a structural pattern called asbody-arm formed by the Delaunay triangles in the void regions. R G G is constructed through an iterative removal of Delaunay triangles subjected to circumcenter (of triangle) and topological regularity constraints in O ( n log n ) time using O ( n ) space. We introduce the notion of directed boundary samples which characterizes the two dimensional objects based on the alignment of their boundaries in the cavities. Theoretically, we justify our algorithm by showing that under given sampling conditions, the boundary of R G G captures the topological properties of objects having directed boundary samples. Unlike many other approaches, our algorithm does not require tuning of any external parameter to approximate the geometric shape of point set and hence human intervention is completely eliminated. Experimental evaluations of the proposed technique are done using L 2 error norm measure, which is the symmetric difference between the boundaries of reconstructed shape and the original shape. We demonstrate the efficacy of our automatic shape reconstruction technique by showing several examples and experiments with varying point set densities and distributions. Highlights: A fully automatic algorithm using the structural properties of Delaunay triangles. External boundary as well as an internal hole detection have been addressed. Demonstrate the efficacy with varying point set densities and distributions. Theoretical guarantee of the algorithm has been presented.