Research On Surface Reconstruction From Triangular Mesh

With the development of computer applications technology and computer graphics tech-nology, using polygonal meshes with a convincing level of realism to represent3D dig-ital geometry models is now generally acceptable. Due to polygonal meshes’ highly desirable properties for rendering and calculating, processing and representing3D dig-ital models with them are widely applied in the fields of Computer Aided Geometric Design (CAGD), Computer Games, Animation, Movies, Simulation and Computer Sci-entific Visualization. However, using polygonal meshes to efficiently represent digi-tal models faces a series of problems. First, most polygonal meshes generated from other kind of data set often contain holes, gaps, T-junctions, self-intersections, and non-manifold structure which make them unsuitable for many purposes other than rendering; Next, most polygonal meshes often contain a lot of unnecessary details and degenera-tive polygons which affect not only their storage space, but also the stability, com-plexity, and precision of the algorithms worked on the polygonal meshes. Compared with the method which employed polygonal meshes to represent digital models, such problems discussed above have never arisen within the approaches that make use of im-plicit surface models to represent digital models. Therefore, how to effectively process polygonal meshes with implicit surface models is a hotspot and an essential problem of Digital Geometry Processing (DGP). In recent years, the research of using implicit surface model to interpolate or approximate polygonal mesh has obtained fast develop-ment, and achieved a series of significant progress, but many problems are pressing for solution. For example, how to control the approximation precision between the con-structed implicit surface model and the polygonal mesh; how to express the implicit surface model and store it effectively; how to generate an implicit surface model from its corresponding polygonal mesh under a given approximation error; how to fast render the implicit surface.According to the problems mentioned above, the research of this thesis includes:1) Robust and effective polygonal meshes-implicit surface modeling approach;2) Rapid sampling on implicit surfaces via hybrid optimization;3) Surface construction with fewer patches within precision, and following is the specific content:1. Robust and effective polygonal meshes-implicit surface modeling approachwe present a new robust multi-level partition of unity (MPU) method, which con-structs an implicit surface from a triangular mesh via the new error metric between the mesh and the implicit surface. The new error metric employs a weighted function of inner points and vertices of a triangle to fit an implicit surface, which can control the approximation error between the surface and vertices of the triangle. Furthermore, it is applied to the MPU method by utilizing the dual graph of a triangular mesh, and the general quadric implicit surface is used for surface representation. Compared with the MPU method, the new method generates fewer subdivision cells with the same approx-imation error and performs more steadily especially when given triangular mesh with fewer vertices.2. Rapid sampling on implicit surfaces via hybrid optimizationA new method for implicit surfaces sampling is presented. At first, a new objec-tive function of repulsive energy is given for constraining sampling points distributed on the surface uniformly. Based on this new objective function, the distribution of sam-pling points can be solved by a hybrid optimization. The first step is a local optimiza-tion of sampling points through a parameter to control the velocity of a sampling point for avoiding inverse matrices computation of Hessian, so a set of sampling points can cover given implicit surface rapidly. The second step is global optimization of sampling points. L-BFGS method is used in this step. We can have ideal sampling distribution via these two steps. Experimental results show that the new method can sample fast on implicit surfaces, and the points’ distribution is also satisfactory.3. Surface construction with fewer patches within precisionWe present an algorithm to generate an interpolation or approximation model con-sisting of many patches from a triangle mesh, and each patch is a weighted combination of the three surfaces associated with the vertices of a triangle. Moreover, to make the whole surface include fewer patches, mesh simplification is introduced into the process of surface construction. The algorithm takes a triangle mesh and a given error as in- put, and iteratively deletes vertex whose distance to the surface model constructed from the simplified mesh is less than or equal to the given error until convergence. Since the method is based on surface approximation and vertex deletion, it allows us to control the error between the generated model and the original mesh precisely. Furthermore, many experimental results show that the generated models approximate the original models good.