Manifold-Guaranteed Surface Decomposition And Meshing Based On Extrinsic Distance Queries

As the research objects in the field of digital geometry processing,3D shapes have various forms,such as parametric surfaces,implicit surfaces,point clouds and mesh surfaces.Among them,mesh surfaces are the most popular representations in computer graphics and physical simulation,due to the strong ability of encoding complete shape information and the flexible usage in various applications.Although either of them can encode the real shape,the devised geometry processing algorithms have to seriously depend on the specific representation form.For example,in the past research,various reconstruction algorithms are proposed to transform a point cloud to a polygonal mesh,and various remeshing algorithms are proposed to transform a low-quality mesh surface to a highquality mesh surface.It can be seen that existing algorithms are highly coupled with a specific kind of surface representation,but weak in satisfying some essential properties(e.g.,manifoldness).For example,they are easy to produce non-manifold artifacts in surface decomposition and meshing,greatly limiting their use in geometry processing.The theme of the thesis is to establish a unified approach to handle diverse 3D data,and further use the unified representation to produce high-quality surface decomposition and meshing results with manifoldness guarantee.First,we use the nearest point query technique to bridge various representations so as to surface representations and geometric algorithms can be decoupled,i.e.,some mesh-oriented algorithms can also be used to deal with other types of surface representations.Second,surface decomposition and meshing are central to many geometry processing tasks.Their results have to be conformal to the manifoldness property.However,existing algorithms are easy to produce non-manifold artifacts especially when the give points are sparse and with non-uniform gaps.In this thesis,we propose a system of manifoldness checking rules,as well as two strategies to enforce the manifoldness property.Finally,thin-plate structures,tubular structures or thin gaps are very challenging in many geometry processing tasks such as mesh generation.In this thesis,we capture the change of projection directions in the task of mesh generation,and infer the real geometry/topology in an adaptive style.To summarize,the contributions of this thesis are three-fold.(1)Unified implicit representation based on efficient projection techniques.Point-to-surface projection refers to the behavior of obtaining the nearest point from a point in 3D to a given surface.With the projection being equipped,the underlying signed distance field,as well as the real shape,is completely determined.Therefore,the projection operator can bridge various surface representations.In real applications,an efficient projection operator is highly desired since the number of points often amounts to millions.For implicit surfaces,the projection point can be found by minimizing the distance between the query point and the given surface.For point clouds,the projection point can be found through moving least squares(MLS).For mesh surfaces,the projection point can be retrieved through bounding volume hierarchy(BVH).Although the Proximity Query Package(PQP)solver is the preferred algorithm for querying the nearest point on a mesh surface,it still requires a tremendous computational cost when the number of points is large.Rather than inherit the spirit of BVH,we propose to use mesh vertices as proxies of mesh edges and faces,making the point-to-surface projection problem to be reduced to a kd-tree search problem.Experimental results show that our algorithm is 5-20 times faster than the classical PQP in terms of run-time performance and 2-5 times faster than the FCPW solver(the optimized PQP version based on SIMD instructions).(2)Manifoldness guaranteed Voronoi decomposition on unified implicit representation.Traditional algorithms study the decomposition problem on mesh surfaces.This thesis extends the problem to the above-mentioned unified geometric implicit representation so that more surface representations forms can be supported.At the same time,traditional decomposition algorithms are mainly based on Restricted Voronoi Diagram(RVD)and Geodesic Voronoi Diagram(GVD).The former cannot guarantee a manifold output while the latter is very inefficient.We propose a system of manifoldness checking rules,as well as two strategies for enforcing manifoldness.The first strategy is to adaptively increase the number of sampling points to ensure that the decomposition result is dual to a watertight manifold mesh.The second strategy is to re-partition the invalid regions so that the adjacency structure between regions meets the manifoldness property.(3)High-quality meshing based on unified implicit representation.Taking the unified implicit representation as the input,the task of high-quality meshing is to integrate 3D mesh reconstruction and remeshing,which allows one to directly generate a high-quality triangular mesh from a poor-quality point cloud.The key difficulty of mesh generation lies in how to preserve topology and geometric details while maintaining high-quality triangles.We solve the problem by tiling the whole space with a special tetrahedron.By tracing all the tetrahedra that are passed through by the surface,our algorithm can generate well shaped triangles.Furthermore,we infer the local topological structure and curvature based on the variation of projection directions,which facilitates us to tile the geometrically complicated region with fine-sized tetrahedra.In this way,our algorithm can produce high-quality triangulation results while preserves topology,manifoldness and geometric details,even if the input surface has complex geometric structures such as thin plates,thin tubes and narrow gaps.