GPU Local Triangulation: an Interpolating Surface Reconstruction Algorithm

Abstract

A GPU capable method for surface reconstruction from unorganized point clouds without additional information, called GLT (GPU Local Triangulation), is presented. The main objective of this research is the generation of a GPU interpolating reconstruction based on local Delaunay triangulations, inspired by a pre-existing reconstruction algorithm. Current graphics hardware accelerated algorithms are approximating approaches, where the final triangulation is usually performed through either marching cubes or marching tetrahedras. GPU-compatible methods and data structures to perform normal estimation and the local triangulation have been developed, plus a variation of the Bitonic Merge Sort algorithm to work with multi-lists. Our method shows an average gain of one order of magnitude over previous research.