三维约束Voronoi剖分  

Conforming Voronoi Tessellation in 3D

作　　者：李吉刚[1] 杨钦[2] 孟宪海[2] 陈其明[1] 张以都[1] 

机构地区：[1]北京航空航天大学机械工程及自动化学院,北京100083 [2]北京航空航天大学计算机学院,北京100083

出　　处：《计算机辅助设计与图形学学报》2005年第10期2143-2151,共9页Journal of Computer-Aided Design & Computer Graphics

摘　　要：分析了约束面(点、线段、凸多边形)在三维Voronoi网格存在的条件,提出一种构造三维约束Voronoi剖分的算法.该算法的基本思想是在限定线的球覆盖基础上,借助限定面的约束Regular三角化生成关于限定面对称分布的生长点.理论上,对任意的分段线性复合形约束,该算法可以生成满足此约束的Voronoi网格.最后,给出了实例验证以说明文中算法的有效性.In this paper, the conditions guaranteeing the existence of constrained facets in conforming Voronoi tessellation （CVT） in 3D are derived. An algorithm is presented to build a Voronoi tessellation conforming to a piecewise linear complex （PLC） in 3D. To build CVT, a set of balls are constructed covering the 0- and 1-dimension faces of PLC, then Voronoi sites aligned alongside 2D faces of PLC are generated by the conforming regular triangulation of 2D faces of PLC. The algorithm has been implemented to validate its efficiency. It is to our knowledge, the first practical algorithm devoted to solving this problem.

关 键 词：VORONOI图 DELAUNAY三角化 约束Voronoi剖分 Voronoi网格 控制体积法 

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