Research On Surface Reconstruction And Boundary Detection From 3D Scattered Points

For ten odd years the surface reconstruction via large discrete sampling dataset (called "point cloud") has been developed as one of the main research subjects with the wide attention of both theoretical and applied circles. Due to the diversity of the sampling approaches and application backgrounds, there have been developed tens of algorithms of miscellaneous features. The topological correctness of the reconstruction surfaces produced by many of them is in tight connection with whether the original surfaces have boundaries. Therefore it attracts wide attention how to efficiently perform boundary detection to the sampling data. In this thesis we summarize the main approaches for surface reconstruction, study the problem of boundary detection for point clouds, and propose a new algorithm based on regular space subdivision. Our approach detects the sampling points close to the boundary of the original surface by dividing the spacial range where the data points locates into cubes of equal edge-length and making a topological classification for the adjacent relations among the cubes containing the sampling points. The algorithm is performed directly to the point cloud with no need to reconstruct a surface first. It calculates locally with the time complexity O(N log N), where N is the number of the sampling points.The thesis is organized as follows:Chapter One: Surface Reconstruction via Large Discrete Sampling Dataset. In which we summarize the theory and recent developments with regard to the problem of surface reconstruction via point clouds.Chapter Two: Boundary Detection for Discrete Surfaces. In this chapter the problem and recent developments about boundary detection for surfaces in discrete forms is summarized.Chapter Three: A Boundary Detection Algorithm Based on Regular Space Subdivision. In this chapter a new algorithm directly detecting the boundary of the point cloud is proposed, with a proof of its correctness in mathematics.