Surface Sampling On Two-Manifold Triangular Meshes And Its Applications

Benefited from 3D data acquisition techniques, the usage of 3D models has been spreadamong a number of fields ranging from cinematography to scientific visualization andmanufacturing. 3D models are usually represented by triangle meshes. The quality oftriangle meshes has a great in?uence on the efficiency and stability of algorithms. Themeshes constructed from point cloud from 3D scanners or produced by other geometricmodeling algorithms (such as boolean operations) though capture the detail of objects,their quality is far from satisfaction. Therefore, it is well worth studying how to resampleand remesh triangle meshes so as to meet different application requirements.We study the problem of surface sampling based on the mature 2D sampling al-gorithms: On one side, we apply 2D sampling algorithm on global parametrization toachieve surface sampling, but solve some of the restrictions of existing algorithms. Thisalgorithm is efficient and suitable for simple meshes; On the other side, we extend the fastPoisson-disk algorithm onto two-manifolds to generate isotropic samplings on more com-plex models. With several runs of relaxation, our approach can produce precise isotropicsamplings efficiently. Then we apply the Poisson-Disk sampling algorithms into high-quality remeshing. In addition, we further explore its applications in other fields. Themain contributions can be summarized as follows:(a) With the 2D importance sampling algorithm, we develop a surface samplingand remeshing algorithm based on global parametrization. The algorithm searches acut path with the guidance of geometric stretch. The model is cut into a disk-like surfaceand then parameterized into a circular domain. Compared with other global parametriza-tion algorithms, it not only reduces the distortion introduced by the parametrization butalso avoids the stitching of multiple charts. Importance sampling is employed to generateblue-noise sampling in accordance with the density control map in the parameter domain.The samples are triangulated and mapped back to 3D space to generate isotropic sampleson the mesh surface, thus improving the quality of original triangle mesh.(b) We propose a uniform Poisson-Disk sampling algorithm performed directlyon mesh surfaces. By adopting geodesic distance as the distance metric, we success-fully generalize the 2D fast Poisson-disk sampling algorithm to 3D mesh surfaces. Toaccurately and continuously represent the boundary of expellant disk and the availableboundary, we introduce a method of extracting geodesic isolines on 2-manifolds based on the fast MMP algorithm. The isolines are exact and represented by a set of conic arcs.Our algorithm can generate isotropic samplings even for complex models, as illustratedby the experiments. We also analyze the relationship between sampling density and theradius of expellant disk.(c) We extend the uniform Poisson-Disk sampling to adaptive Poisson-Disk sam-pling. To realize adaptive sampling on mesh surface, We define the radius of the expellantdisk on arbitrary point on the mesh according to the sampling density, and discover theformula of the available boundary in non-uniform density cases. The formula shows thatthe available boundary is composed of conic arcs. According to the formula, we bringout a method to extract the available boundary on manifolds, thus achieving adaptivesampling in accordance with density.(d) We show how to apply our sampling algorithm on high-quality remeshing.After the connectivity of the initial samples is constructed by mutual tessellation, we canfurther optimize the location of the samples by relaxation. Due to the isotropy of initialsamples, only several runs of Lloyd relaxation can further improve the isotropy of pointdistribution into a precise one, which not only makes the algorithm efficient and improvethe quality of new mesh. Experiments show that our algorithm can generate better triangleshape than other remeshing algorithms.(e) The 3D Poisson-disk sampling algorithm is further extended to generatesmooth progressive multi-level samplings. With a level of sampling fixed, new samplescan be inserted onto the surface by gradually increasing the sampling density or reducingthe radius of expellant disks. The refined level of sampling is still isotropic, moreover, thesamples in the coarser level are guaranteed to be present in the refiner level, which can beused to smoothly interpolate between different levels of detail.Other than surface remeshing, isotropic sampling is useful in many other applica-tions. We explore the applications of 3D Poisson-disk sampling in the fields of objectdistribution and texture mapping. Since the samples are centered in the expellant disks,objects can be uniformly distributed on the surface and they will not overlap with eachother. As for texture mapping, the isotropic sampling on 3D models provides a naturaltexture basic function on mesh surface, thus producing satisfactory results of uniformtexture mapping.