Theory and practice of sampling and reconstruction for manifolds with boundaries.

摘要

Surface sampling and reconstruction are used in modeling objects in graphics and digital archiving of mechanical parts in Computer Aided Design and Manufacturing (CAD/CAM). Sampling involves collecting 3D points from the surface. Using these point samples, a reconstruction process rebuilds a surface that is topologically equivalent and geometrically close to the original surface. Conditions are imposed on sampling to ensure correct reconstruction. For a special case of manifolds, there are theoretically sound algorithms for sampling and reconstruction. The sampling conditions for such algorithms impose a minimum required sampling density (maximum distance between close samples) to ensure correct reconstruction.; In this dissertation, I study the sampling and reconstruction of manifolds with boundaries. For this class of surfaces, I show that the conditions on minimum required sampling density are not sufficient to ensure correct reconstruction if only the point samples are given as input to the reconstruction process. Additional information like the smallest boundary size in a model, though sufficient to ensure correct reconstruction, imposes uniform sampling density throughout the model. In this dissertation, I propose a novel way to use the variation in the sampling density across the surface to encode the presence of a boundary. A sampling condition is proposed based on this approach, and the reconstruction process requires no additional information other than the input set of sample points. The reconstruction algorithm presented in this dissertation for reconstructing manifolds with or without boundaries is shown to be correct, efficient, and easy to implement.