Important: Brevity disclaimer.
The task of pointcloud triangulation is about producing triangulated representation of some surface that is represented at the input as a set of 3-dimensional points.
Typically these pointclouds are produced by different kinds of scanners when performing reverse engineering or quality assurance tasks, though there are also other important problems which require pointcloud triangulation algorithm to solve them.
It should be noted that the task in some sense is similar to “recognition” tasks, as algorithm tries to “guess” the shape having only limited information about it (in fact, some pointcloud triangulation algorithms are indeed based on the idea of trying to recognize some common shapes). Thus, it’s highly unlikely that “universal” algorithm can be designed which is able to perform “guessing” 100% correctly in all cases. Nonetheless, there are some fundamental approaches that are able to reconstruct shapes correctly in many practical cases, some of them - even with theoretical guarantees (placing some serious restrictions on the input, though, which are typically not possible to satisfy in practice).
Therefore, typically the single algorithm for pointcloud triangulation is not enough: there should be several of them, each with its own set of tradeoffs, applicable to some specific input types or areas of usage. During the work at Materialise I’ve done two different algorithms for pointcloud retriangulation.
Also the important thing when working with pointcloud triangulation is that not only triangulation algorithm itself is important, but pre/post processing steps are also, in other words - complete workflow should be designed to make reconstruction process really useable on practice. This was also the task I’ve solved when working on this topic.
Golf Club sample