Multiple Incident Splines (MISs) algorithm for topological reconstruction of 2D unordered point clouds

Abstract - An automatic 3D model retrieval from freehand conceptual sketches is a key target for both commercial software houses and academic research. Unfortunately, most of the approaches are not suitable for properly translating stylistic sketches into 3D models. In order to carry out this 3D model conversion, the first task to be dealt with is to turn raster data (3D or 2D free-form curves) into vectorial ones. Such a task represents a key issue which has been addressed by a number of authors but still far to be exhaustively worked out. To address this challenge, this work presents a new method that allows to fit 2D unordered point cloud data with Multiple Incident Splines (MISs). At the heart of the proposed approach are two main procedures: the first one is based on Euclidean Minimum Spanning Tree (EMST) and Principal Component Analysis (PCA) for detecting the main local directions of the point cloud and to order its points while preserving original topology; the second is meant to fit ordered point clouds with spline curves providing a robust intersection and vertex detection. The proposed methodology, tested on a number of case studies, proves to preserve the original topology more efficiently than alternative techniques supplied by commercial vectorization software packages.