3D Conforming Voronoi Mesh Generation by Refinement Algorithm

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.