Neighborhood Data Structures, Manifold Properties, and Processing of Point Set Surfaces
Martin Skrodzki · 2019
The thesis covers three topics all centered in the context of point set processing. In the following, we will shortly present each topic with its motivation, explain the performed research, and highlight the contributions. In case the presented results have been published prior to the publication of this thesis, the corresponding reference is given. The first topic concerns notions of neighborhood and corresponding data structures. Many researchers have recognized the importance of high-quality neighborhood relations. For example, the authors Lange and Polthier in their CAGD article from 2005 report that the results of their anisotropic smoothing algorithm heavily depend on the neighborhood structure imposed on the point set. Despite their advantages in storage space and easy acquisition, the missing neighborhood relation is a significant downside to point set representations. The purpose of this first part is to discuss neighborhood concepts as well as a data structure for fast single-core and fast parallelized computation respectively. The second main topic of this thesis deals with manifold structures for point set surfaces. From a significant amount of real-world objects, while 3D-scanning them, only the surface is acquired for further processing in CAD or other applications. When the surface of the underlying real-world geometry has the structure of a manifold, it can be expected that this structure is reflected by any point set acquired from the geometry. Even when the faces of the geometry are smooth manifold patches, there is no theory available in the setting of point sets to reflect their manifold properties. Third and finally, algorithms have to work efficiently and robustly on the point set. While meshed geometries provide an intuitive and natural weighting by the areas of the faces, point sets can at most work with distances between the points. This introduces a new level of difficulty to be overcome by any point set processing algorithm. This final chapter introduces a novel weighting scheme to counteract non-uniformity in point sets, a feature detection algorithm with mathematical guarantees, and an iterative denoising scheme for point sets.