Surface reconstruction by computing restricted Voronoi cells in parallel. (September 2017)

• Record Type: Journal Article
• Authors: Boltcheva, Dobrina; Lévy, Bruno
• Is Part Of: Computer aided design. Volume 90(2017)
• Page Start: 123
• Page End: 134
• Publication Date: 2017-09
• Subjects: Surface reconstruction -- Point cloud -- Restricted Voronoi diagram; 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.2017.05.011
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: We present a method for reconstructing a 3D surface triangulation from an input point set. The main component of the method is an algorithm that computes the restricted Voronoi diagram. In our specific case, it corresponds to the intersection between the 3D Voronoi diagram of the input points and a set of disks centered at the points and orthogonal to the estimated normal directions. The method does not require coherent normal orientations (just directions). Our algorithm is based on a property of the restricted Voronoi cells that leads to an embarrassingly parallel implementation. We experimented our algorithm with scanned point sets with up to 100 million vertices that were processed within few minutes on a standard computer. The complete implementation is provided. Highlights: Simple and scalable surface reconstruction algorithm from 3D point sets. The algorithm requires only estimated normal directions (no need of consistent normal orientation). It processes 100 million points within few minutes on a standard computer. The complete implementation is provided. Graphical abstract: