三维限定Voronoi网格剖分细化算法  

3D Conforming Voronoi Mesh Generation by Refinement Algorithm

作　　者：李吉刚[1,2] 杨钦[1,2] 孟宪海[1,2] 蔡强[3] 

机构地区：[1]软件开发环境国家重点实验室,北京100083 [2]北京航空航天大学计算机学院,北京100083 [3]北京工商大学计算机学院,北京100037

出　　处：《计算机辅助设计与图形学学报》2009年第1期72-80,共9页Journal of Computer-Aided Design & Computer Graphics

基　　金：北京市自然科学基金(4062010)

摘　　要：针对分段线性复合形约束条件下的三维限定Voronoi剖分问题,提出一种细化算法.首先证明了分段线性复合形中的元素在最终生成的三维限定Voronoi网格中可表示为Power图结构;受此启发,提出了对限定线段/平面片分别进行一维/二维Power图细化以实现三维限定Voronoi网格生成的细化算法,并且证明了该算法对于任意分段线性复合形收敛.最后通过实例验证了文中算法的有效性.We describe an algorithm which, for any piecewise linear complex （PLC） in 3D, builds a Voronoi tessellation conforming to this PLC. Based on the proven insight that once a face f in PLC is a union of faces of Voronoi diagram in 3D,the subdivision structure on the face f can be seen as a power diagram, we devised a conforming Voronoi tessellation algorithm by maintaining a power diagram refinement for each 1D/2D faces of PLC and a Voronoi tessellation in 3D. The power diagram refinement for each 1D/2D faces of PLC is devoted to driving Voronoi tessellation in 3D and to enforcing boundary conformity,and to improving the quality of the mesh . The algorithm is guaranteed to terminate on any PLC. The algorithm has been implemented, and yields in practice a relatively small number of Voronoi cell due to the fact that it adapts to the local geometry of the PLC.

关 键 词：限定Voronoi网格 DELAUNAY三角化 细化算法 Power图 Regular三角化 

分 类 号：TP391.4[自动化与计算机技术—计算机应用技术]