Intrinsic computation of voronoi diagrams on surfaces and its application

The Voronoi diagram is a decomposition of a space, determined by distances to a given set of objects. As a fundamental geometric data structure, Voronoi diagrams have been widely applied in various computer graphics and visualization applications. While there is a popular Fortune’s sweep line algorithm, there is no effective technique to parallelize it. Centroidal Voronoi tessellation (CVT) is a special type of Voronoi diagram such that the generating point of each Voronoi cell is also its center of mass. The CVT has broad applications in computer graphics, such as meshing, stippling, sampling, etc. The existing methods for computing CVTs on meshes either require a global parameterization or compute it in the restricted sense (that is, intersecting a 3D CVT with the surface). Therefore, these approaches often fail on models with complicated geometry and/or topology. To get intrinsic CVT on meshes, we need to compute discrete geodesic efficiently. The existing exact discrete geodesic algorithms are relatively slow while the approximate geodesic methods suffer from numerical problems and are sensitive to mesh tessellation. Thus we need an efficient and accurate method to compute discrete geodesics.To tackle these issues, we studied CVT and discrete geodesic problem systematically. We present a sweep circle algorithm for construct Voronoi diagrams in parallel and the Saddle Vertex Graph (SVG) to efficiently compute discrete geodesics on meshes. Combined discrete geodesic with CVT, we present two efficient algorithms for computing intrinsic CVT on meshes. Furthermore, we propose two applications of CVT and discrete geodesics. One is surface reconstruction from point clouds using CVT and the other is anisotropic shape distribution on meshes. Our contributions are listed as follow: We first presents a new algorithm, called sweep circle, for constructing Voronoi diagram. Starting with a degenerate circle centered at an arbitrary location, our algorithm sweeps the circle by increasing its radius across the plane. Our sweep circle algorithm is flexible in allowing multiple circles at arbitrary locations to sweep the domain simultaneously, thus is parallel in nature. We demonstrate the efficacy of our parallel sweep circle algorithm using GPU. Second, we propose the Saddle Vertex Graph (SVG) to efficiently compute discrete geodesics on triangle meshes. The SVG is a sparse undirected graph that encodes complete geodesic distance information which can be solved efficiently using the shortest path algorithm (e.g., Dijkstra algorithm). It does not require any numerical solver, and is numerically stable and insensitive to the mesh resolution and tessellation. The experimental results on real world models demonstrate significant improvement to the existing approximate geodesic methods in terms of both performance and accuracy. Thirdly, we introduce two intrinsic algorithms for computing CVT on triangle meshes. The first algorithm adopts the Lloyd framework, which iteratively moves the generator of each geodesic Voronoi diagram to its mass center. The second algorithm uses the L-BFGS method to accelerate the intrinsic CVT computation. Thanks to the intrinsic nature, our methods work well for models with arbitrary topology and complicated geometry. Finally, we show the surface reconstruction and shape distribution applications. We propose a effective method for surface reconstruction from point clouds via Euclidean distance transformation based Centroidal Voronoi Tessellation(CVT). Taking the voxels which contain the surface samples as the sites, we compute the CVT on the GPU. Our algorithm is fully parallel and memory-efficient, and works well on models with such defects. We also demonstrate an automatic method for computing anisotropic 2D shape distribution on arbitrary 2-manifold meshes. Our method allows the user to specify the direction as well as the density of the distribution. Our method does not require globalparameterizationoftheinput3Dmesh. Instead, it computes local parameterization on the fly using geodesic polar coordinates. Thanks to the SVG for solving geodesic computation problem efficiently, the local parameterization can be computed at little cost.DOCTOR OF PHILOSOPHY (SCE