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

3D Conforming Voronoi Mesh Generation by Refinement Algorithm

针对分段线性复合形约束条件下的三维限定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.