Delaunay/Voronoi Dual Representation of Smooth 2-Manifolds
Delaunay triangulation and Voronoi diagram are widely used in computer graphics, computational geometry and other fields. Different from the planar case, Delaunay triangulation of a point set on smooth 2-manifolds does not always exist. In this paper we propose a new sampling requirement combining the maximal curvature, injectivity radius and convexity radius to guarantee the existence of Delaunay triangulation on 2-manifolds. After introducing the primal/dual efficient representation (PDER) structure 24, we develop a generalized PDER which not only represents Delaunay/Voronoi dual simply and efficiently, but also describes the surfaces with boundaries. Taking advantage of several operators for modeling and updating models, we employ generalized PDER to construct and operate Delaunay/Voronoi dual dynamically on smooth 2- manifolds. The generalized PDER is also a powerful tool for dual subdivision schemes. Many examples demonstrate the feasibility of our method and the generalized PDER data structure.
国际会议
2011国际计算机辅助设计与图形学学术会议(CAD/Graphics 2011)
济南
英文
1-8
2011-09-15（万方平台首次上网日期，不代表论文的发表时间）