Hybrid GPU Local Delaunay Triangulation through Points Consolidation

Introduction

Surface reconstruction is an amazing field of research due to the uncertainty nature of the problem: given a set of points from an unknown surface, how to compute a digital representation as similar as possible to such surface. It faces several challenges: incomplete data, inconsistencies, noise, data size, ambiguities, to name a few. It is a vast researching area, and many methods have been already proposed. Unfortunately, surface reconstruction is still an open field since it is too complex and probably impossible to fully recover an unknown surface without previously assuming some kind of information. Almost every single existing method relies on at least one parameter and usually focuses on a subset of problems, so it can better exploit the implicit model’s characteristics in order to obtain a proper reconstruction.

It is then important to first consider the goals of the method studied, the information available and the assumptions done:

• 1.

  The method must be scalable in terms of the size of the data. One of the most common ways to achieve this kind of goal is the “divide and conquer” approach, so memory and computing power requirements can be reduced.

• 2.

  In the last years, graphical hardware accelerated algorithms have become more common and easy to implement in the GPU (Graphics Processing Unit). Then, it is also convenient that the method may be parallelized, much better if it is GPU friendly.

• 3.

  The method should be also as noise tolerant as possible, assuming not high amounts of outliers. This is a compromise decision, since some of the most common sources of points are laser scanners and image segmentation, both of them providing few outliers, although noise can be present due to imprecision of the acquiring device or low resolution. Assuming low noise level helps to increase the fidelity of the reconstruction of high detailed areas, since they will not be confused with sampling error.

• 4.

  Depending on the source, information such as normals may or not be present. The method should be flexible with the input, performing the necessary steps to compute the missing data. In this sense, only points themselves are a must in this work.

As it will be seen later, combining different processing techniques allows us to design a surface reconstruction method that satisfies with all the goals previously listed.

The user should choose a balance between precision and robustness when facing noise tolerance. In this work, we show how mixing a point consolidation phase and a Delaunay triangulation can produce very good results, both robust against sampling errors and accurate in high frequencies recovery. The Delaunay triangulation only requires a set of points to work, so it also fulfills the last goal.

Regarding the scalability of our method, the triangulation phase is scalable in both terms of memory (a divide and conquer method) and execution time (it is a parallel method that has been implemented in the GPU). The point filter has been adapted to be GPU capable, although its scalability is a bit lower than the triangulation due to its global and iterative nature.

In summary, the main objectives of this chapter include:

• •

  Present local triangulation as a reconstruction alternative,

• •

  Propose a fast filtering scheme for improving local triangulation with global parameter,

• •

  Implement both filtering and triangulation in parallel graphic architecture,

• •

  As such GPU algorithms are still very sensitive to even small optimization, implementation details will be given when they give an important advantage.