Input Size Independent Efficient Quality Meshing of the Interior of 2D Point Cloud Data

Abstract This paper describes a framework to generate an unstructured Delaunay mesh of a two-dimensional domain whose boundary is specified by a point cloud data (PCD). The assumption is that the PCD is sampled from a smooth 1-manifold without a boundary definition and is significantly dense (at least ∊ -sampled where ∊ 1 ). Presently meshing of such a domain requires two explicit steps, namely the extraction of model definition from the PCD and the use of model definition to guide the unstructured mesh generation. For a densely sampled PCD, the curve reconstruction process is dependent on the size of input PCD and can become a time-consuming overhead. We propose an optimized technique that bypasses the explicit step of curve reconstruction by implicit access to the model information from a well-sampled PCD. A mesh thus generated will be optimal, as the fineness of the mesh is not dictated by the sampling of PCD, but only the geometric complexity of the underlying curve. The implementation and experiments of the proposed framework show significant improvement in expense over the traditional methodology. The main contribution of this paper is the circumvention of the explicit time-consuming step of boundary computation which is a function of the PCD sampling size and a direct generation of a mesh whose complexity is dictated by the geometry of the domain.