Explicit Surface Reconstruction With Manifoldness Guarantee

3D reconstruction is a typical reverse engineering problem.Its task is to recover the potential geometric structure from the scattered point cloud.Existing 3D reconstruction approaches can be divided into implicit reconstruction approaches and explicit reconstruction approaches.The former focuses on inferring the implicit equation of the potential surface,while the latter focuses on fully respecting the given point cloud and generating an interpolation-type mesh surface.Generally speaking,implicit reconstruction is stronger than explicit reconstruction in preserving manifold and smoothness,but weaker than explicit reconstruction in preserving sharp features and geometric details.The two reconstruction methods complement each other and are indispensable.The purpose of this dissertation is to develop an explicit reconstruction approach that can output a watertight and manifold surface.When the quality of the point cloud is high,that is,the given point cloud is free of noise and meets the sampling density defined by the local feature size(LFS),the existing explicit reconstruction algorithms can indeed achieve a desirable result.However,for low-quality point clouds,it is not easy to achieve such a goal.The first reason lies in the data:in practice,the point cloud data may have various defects,such as non-uniform/sparse point distribution,lack of normal vectors,noise,outlier and missing data.When the LFS standard is not satisfied,surface reconstruction becomes an ill-conditioned problem.The second reason lies in the method:the potential surface represented by point cloud may have an extreme shape complexity,including sharp points,sharp edges,thin plates,thin tubes,high genus,etc.However,the existing reconstruction methods cannot be aware of different levels of shape features,from global to local,before the surface is completely reconstructed.Based on careful investigation of existing research progress,we propose a progressive interpolation based surface reconstruction approach based on repeatedly updating a dynamic guiding surface.Throughout the algorithm,some prior knowledge,such as "being of a simple overall shape" and "being an orientable watertight manifold surface",is incrementally utilized to make the guide surface approach the real underlying surface.The contributions of the dissertation include the following aspects:(1)Surface Voronoi diagram with manifoldness guaranteeVoronoi diagram is a partition for plane or space.Restricted Voronoi diagram(RVD)and geodesic Voronoi diagram(GVD)are the generalization of Voronoi diagram on surface.RVD is defined as the intersection of a three-dimensional Voronoi diagram and a surface,and the distance measurement is the linear distance,which is the extrinsic partition of the surface.The distance measurement of GVD is geodesic distance,which is the intrinsic partition of surfaces.In contrast,RVD is more efficient and GVD is more accurate.However,both RVD and GVD cannot generate an manifold triangulaiton.This dissertation focuses on how to ensure that the dual restricted Delaunay triangulation(RDT)of RVD is a manifold,which is of great significance to remeshing,surface reconstruction,surface repair,etc.By observing the geometric structure of RVD,this paper analyzes the causes of non manifold of RDT,summarizes the manifold conditions between RVD and RDT,and proposes a robust algorithm to systematically repair the incorrect regions,so as to strictly ensure that RDT is a manifold.(2)Explicit surface reconstruction with manifoldness guaranteeOn one hand,there is no explicit reconstruction algorithm that can output a high-quality mesh of watertight manifolds for defective point clouds(non-uniform distributed,sparse,lack of normal vectors,noisy,outlier sets,missing data,etc.).On the other hand,the potential shapes encoded by the point cloud may include thin plates,thin tubes,high genus,sharp features,etc.The goal of this dissertation is to produce a high-quality triangular mesh of watertight manifold,while restoring the real geometry as far as possible.In this thesis,we invent two tools,named "filmsticking" and "sculpting",to progressively modify a manifold shape by repeatedly minimizing the difference between the current surface and the point cloud,until the resulting surface sufficiently manifests the real shape.Our algorithm uses the spherical bounding surface of the point cloud as the initial guiding surface,and then alternately performs "filmsticking" and "sculpting".In this process,the main task of filmsticking is to compute RVDs on the guiding surface such that more points can be attracted onto the guiding surface while the main task of sculpting is to modify the geometry and topology of the guiding surface based on the difference between the guiding surface and the point cloud.The whole algorithm terminates until the guiding surface becomes unchanged.The convergence is proved in this thesis and the effectiveness of the proposed algorithm is justified through extensive tests on real and simulated data.(3)Mesh repair technology with manifoldness guaranteeMost of computer graphics algorithms require the input mesh to be a watertight manifold.They cannot deal with a broken mesh with various defects,such as non-manifoldness,gaps,inconsistent face orientations,self-intersection.In this paper,we inherit the spirit of manifold surface reconstruction and develop a mesh repair algorithm with manifoldness guarantee.We first construct a watertight manifold guide surface that is similar to the original mesh by detecting the boundary and internal of the original model,and then extract RDT as output by using the surface Voronoi diagram with manifoldness guarantee.Further,we preserve the geometric features by adding auxiliary points on the edges of the original mesh.The usefulness and effectiveness of the algorithm are demonstrated on the public data set modelnet10.