Reconstruction and deformation of objects from sampled point clouds

Reconstructing a quality mesh representing an unknown surface from a set of points sampled on that surface is a fundamental problem in geometric modeling, with many applications in science and engineering. In the past decades, many reconstruction methods have been proposed. Among them, Delaunay triangulation and its dual, Voronoi diagram, have been proven to be powerful tools for reconstruction of smooth surface with moderate size of sampling. However, the application of Delaunay triangulation for reconstruction faces two problems: large data sets and samples from piece-wise smooth surfaces with possible noise. In this dissertation, we improve the scalability, versatility and robustness of Delaunay/Voronoi based reconstruction methods.;For a large data set, the entire Delaunay triangulation may not be loaded into memory due to its large number of simplices. We extend a surface reconstruction algorithm suitable for large point sets. This method is an octree-based version of the well-known Cocone reconstruction algorithm. It allows independent processing of small subsets of the total input point set. When the points are sufficiently sampled from a smooth surface, the global guarantee of topological correctness of the original Cocone is preserved, together with its guarantees on geometric accuracy.;The presence of "singularities" such as boundaries, sharp features and non-manifolds makes the reconstruction of piece-wise smooth surfaces a difficult problem. Existence of possible noise makes this problem even harder. We introduce a robust Delaunay/Voronoibased reconstruction pipeline to deal with sampled singular surfaces. Our work first identifies feature points close to singularities by locally building weighted Voronoi diagrams and analyzing their cell shapes. Then, these points are filtered so that the remaining ones can be connected into piecewise linear curves approximating the original features. As a final step, it reconstructs the surface patches containing these feature curves by a method akin to Cocone but with weighted Delaunay triangulation that allows protecting feature curves with balls.;When it comes to entertainment, faithfully reconstructing human body from scanned data is a challenging topic. Input datasets are daunted by incompleteness caused by limited views and noise generated by consumer level scanners such as Kinect. The final topic in this dissertation deals with generating quality meshes from human body scans possibly laden with defects. We introduce a markerless approach to deform a quality human body template mesh from its original pose to a different pose specified by a point cloud. The point cloud may be noisy, incomplete, or even captured from a different person. We first build coarse correspondences between the template mesh and the point cloud through a spectral technique that exploits human body extremities. Based on these correspondences, we define the goal of non-rigid registration using an elastic energy functional and apply a discrete gradient flow to reduce the difference between a coarse control mesh and the point cloud. Deformation of the template mesh can then be obtained from the deformed control mesh using mean value coordinates. Experimental results demonstrate that our approach can robustly handle noise and partial occlusions.