In this paper, we present a fully automatic Delaunay based sculpting algorithm for approximating the shape of a finite set of points S in R2. The algorithm generates a relaxed Gabriel graph (RGG) 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 as body-arm formed by the Delaunay triangles in the void regions. RGG is constructed through an iterative removal of Delaunay triangles subjected to circumcenter (of triangle) and topological regularity constraints in O(nlogn) 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 RGG 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 L2 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. © 2014 Elsevier Ltd.

Ramanathan Muthuganapathy

Department of Engineering Design

geometry

Iterative methods

Topology

Triangulation

DELAU-NAY TRIANGULATIONS

GABRIEL GRAPH

HOLE DETECTION

RELAXED

SHAPE RECONSTRUCTION

Algorithms

IIT Madras is a public technical and research university located in Chennai, Tamil Nadu. Founded in 1959, it is recognised as an Institute of National Importance.

IIT Madras has been ranked as the top engineering institute in India for four years in a row by the National Institutional Ranking Framework of the MHRD

It currently offers undergraduate, postgraduate and research degrees across 16 disciplines in Engineering, Sciences, Humanities and Management. About 596 faculty belonging to science and engineering departments and centres of the Institute are engaged in teaching, research and industrial consultancy.

IIT Madras

CAD Computer Aided Design

We present an incremental Voronoi vertex labelling algorithm for approximating contours, medial axes and dominant points (high curvature points) from 2D point sets. Though there exist many number of algorithms for reconstructing curves, medial axes or dominant points, a unified framework capable of approximating all the three in one place from points is missing in the literature. Our algorithm estimates the normals at each sample point through poles (farthest Voronoi vertices of a sample point) and uses the estimated normals and the corresponding tangents to determine the spatial locations (inner or outer) of the Voronoi vertices with respect to the original curve. The vertex classification helps to construct a piece-wise linear approximation to the object boundary. We provide a theoretical analysis of the algorithm for points non-uniformly (ε-sampling) sampled from simple, closed, concave and smooth curves. The proposed framework has been thoroughly evaluated for its usefulness using various test data. Results indicate that even sparsely and non-uniformly sampled curves with outliers or collection of curves are faithfully reconstructed by the proposed algorithm. © 2018 The Authors Computer Graphics Forum © 2018 The Eurographics Association and John Wiley & Sons Ltd.

Computer Graphics Forum

Incremental Labelling of Voronoi Vertices for Shape Reconstruction

Given a planar point set sampled from a curve, the curve reconstruction problem computes a polygonal approximation of the curve. In this paper, we propose a Delaunay triangulation-based algorithm for curve reconstruction, which removes the longest edge of each triangle to result in a graph. Further, each vertex of the graph is checked for a degree constraint to compute simple closed/open curves. Assuming ϵ-sampling, we provide theoretical guarantee which ensures that a simple closed/open curve is a piecewise linear approximation of the original curve. Input point sets with outliers are handled as part of the algorithm, without pre-processing. We also propose strategies to identify the presence of noise and simplify a noisy point set, identify self-intersections and enhance our algorithm to reconstruct such point sets. Perhaps, this is the first algorithm to identify the presence of noise in a point set. Our algorithm is able to detect closed/open curves, disconnected components, multiple holes and sharp corners. The algorithm is simple to implement, independent of the type of input, non-feature specific and hence it is a generalized one. We have performed extensive comparative studies to demonstrate that our method is comparable or better than other existing methods. Limitations of our approach have also been discussed. © 2018 Elsevier Ltd

Computers and Graphics (Pergamon)

Peeling the longest: A simple generalized curve reconstruction algorithm

Given a planar point set S, outer boundary detection (shape reconstruction) is an extensively studied problem whereas, inner boundary (hole) detection is not a well researched one, probably because detecting the presence of a hole itself is a difficult task. Nevertheless, hole detection has wide applications in areas such as face recognition, model retrieval and pattern recognition. We present a Delaunay triangulation based strategy to detect the presence of holes and an algorithm to reconstruct them. Our algorithm is a unified one which reconstructs holes, both for a boundary sample (points sampled only from the boundary of the object) as well as for a dot pattern (points sampled from the entire object). Our method is a non-parametric one which detects holes irrespective of its shape. Assuming a sampling model, we provide theoretical analysis of the proposed algorithm, which ensures the correctness of the reconstructed holes, for specific structures. We conduct both qualitative and quantitative comparisons with existing methods and demonstrate that our method is better or comparable with them. Experiments with varying point densities and distributions demonstrate that the algorithm is independent of sampling. We also discuss the limitations of the algorithm. © 2017 Elsevier Ltd

Hole detection in a planar point set: An empty disk approach

Given a planar point set sampled from an object boundary, the process of approximating the original shape is called curve reconstruction. In this paper, a novel non-parametric curve reconstruction algorithm based on Delaunay triangulation has been proposed and it has been theoretically proved that the proposed method reconstructs the original curve under ε-sampling. Starting from an initial Delaunay seed edge, the algorithm proceeds by finding an appropriate neighbouring point and adding an edge between them. Experimental results show that the proposed algorithm is capable of reconstructing curves with different features like sharp corners, outliers, multiple objects, objects with holes, etc. The proposed method also works for open curves. Based on a study by a few users, the paper also discusses an application of the proposed algorithm for reconstructing hand drawn skip stroke sketches, which will be useful in various sketch based interfaces. © 2016 The Author(s) Computer Graphics Forum © 2016 The Eurographics Association and John Wiley & Sons Ltd. Published by John Wiley & Sons Ltd.

Crawl through Neighbors: A Simple Curve Reconstruction Algorithm

Given a planar point set sampled from an object boundary, the process of approximating the original shape is called curve reconstruction. In this paper, a novel non-parametric curve reconstruction algorithm based on Delaunay triangulation has been proposed and it has been theoretically proved that the proposed method reconstructs the original curve under e-sampling. Starting from an initial Delaunay seed edge, the algorithm proceeds by finding an appropriate neighbouring point and adding an edge between them. Experimental results show that the proposed algorithm is capable of reconstructing curves with different features like sharp corners, outliers, multiple objects, objects with holes, etc. The proposed method also works for open curves. Based on a study by a few users, the paper also discusses an application of the proposed algorithm for reconstructing hand drawn skip stroke sketches, which will be useful in various sketch based interfaces. © 2016 The Eurographics Association and John Wiley & Sons Ltd.

Eurographics Symposium on Geometry Processing

Crawl through neighbors: A simple curve reconstruction algorithm

Given a finite set of points S ⊆ R2, we define a proximity graph called as shape-hull graph (SHG(S)) that contains all Gabriel edges and a few non-Gabriel edges of Delaunay triangulation of S. For any S, SHG(S) is topologically regular with its boundary (referred to as shape-hull (SH)) homeomorphic to a simple closed curve. We introduce the concept of divergent concavity for simple, closed, planar curves based on the alignment of curves in concave portions and discuss various measures to characterize curves having divergent concavity. Under sufficiently dense sampling, we prove that SH(S), where S is sampled from a divergent concave curve ΣD, represents a piece-wise linear approximation of ΣD. We extend this result to provide a sculpting algorithm for closed surface reconstruction from a set of raw samples. The surface is constructed through a repeated elimination of Delaunay tetrahedra subjected to circumcenter and topological constraints. Theoretically, we justify our algorithm by establishing a topological guarantee on the 3D shape-hull with the help of topological rules. We demonstrate the effectiveness of our approach with experimental results on models with sharp features and sparsely distributed point clouds. Compared to existing sculpting approaches for surface reconstruction that require either a parameter tuning or several stages, our approach is simple, non-parametric, single stage and reconstructs topologically correct piece-wise linear approximation for divergent concave surfaces. © 2014 Elsevier Ltd. All rights reserved.

Reconstruction of water-tight surfaces through Delaunay sculpting

ACM SIGGRAPH 2016 Courses on - SIGGRAPH '16

CGAL

Computer-Aided Design

Puzzhull: Cavity and protrusion hierarchy to fit conformal polygons

Delaunay Mesh Generation Chapman & Hall/CRC Computer & Information Science Series

Two-dimensional Delaunay triangulations

Proceedings of the 27th annual ACM symposium on Computational geometry - SoCG '11

Boundary of a non-uniform point cloud for reconstruction

A non-parametric approach to shape reconstruction from planar point sets through Delaunay filtering

Journal	Data powered by TypesetCAD Computer Aided Design
Publisher	Data powered by TypesetElsevier Ltd
ISSN	00104485
Open Access	No