“A GPU interpolating reconstruction from unorganized points” by Buchart, Borro and Amundarain

We present a GPU method for surface reconstruction from unorganized point clouds without additional information, based on the work of [Gopi et al. 2000]. The main objective of this work is the generation of a GPU interpolating reconstruction method by using local Delaunay triangulations. Existing algorithms accelerated by graphic hardware are approximating approaches, usually based on either marching cubes or marching tetrahedras. Our work most valuable innovation is the GPU adaptation itself; we developed GPU suitable methods to replace those steps which could not to be implemented in graphics hardware. The two most noticeable ones are the O(log(k)) method which identifies Delaunay neighbors (replacing the O(k) backtracking) and the sorting of a great number of small lists in O(log2(k)). Additionally, a divide and conquer approach was adopted to suit video memory constrains; passes are then independent, so multi-GPU parallelization can be performed without changes. Our tests show an 11 times average gain over the CPU version.

1. Gopi, M., Krishnan, S., and Silva, C. T. 2000. Surface reconstruction based on lower dimensional localized delaunay triangulation. Eurographics 19, 3, 467–478.