David Doria, “A Point Set Processing Toolkit for VTK“. The VTK Journal, December 2009

 

In the last several years, an increasing number of tools produce 3D points as output. Examples include Light Detection and Ranging (LiDAR) scanners, Structure From Motion (SFM) algorithms, and Multi View Stereo (MVS) algorithms. These unordered point sets (or point “clouds”) are typically provided simply as a list of 3D coordinates. There are many factors in all of these processes that lead to many of the points that are provided being “outliers”. That is, several points do not seem to actually come from the surface that we expect. This will severely corrupt the results of many algorithms on this type of data. To remove outliers, we provide vtkOutlierRemoval. By definition, point sets do not contain any connectivity information. This makes it impossible to apply many algorithms for 3D data processing. At the very least, point normals at each point are required. That is, if there was a surface through the points, what would the normal of the surface be evaluated at the points in the point set? The vtkPointSetNormalEstimation class performs this estimation. The algorithm we use to compute these normals has no concept of “inside” and “outside” of the object, so the orientation of the normals from point to point my not be consistent. As many algorithms rely on this orientation, we must attempt to correct the normals so they are consistently oriented. This is the role of vtkPointSetNormalOrientation. Necessary for the orientation algorithm are two graph algorithm implementations, vtkEuclideanMinimumSpanningTree and vtkRiemannianGraphFilter. An estimate of the curvature of a point set is often a valuable tool. While the exact values of well defined mathematic quantities can be computed on a mesh, since we do not have connectivity information in a point set, an estimate will have to suffice. We provide vtkPointSetCurvatureEstimation to compute a heuristic idea of curvature at each point. This set of classes provides these basic functionalities as well as a basis for further point set and surface processing algorithms for VTK.