刚体破碎实时模拟算法中的模型预处理

倪雪飞　张雄祥

【摘 要】由于Voronoi网格和真实世界中刚体碎片的样子非常接近， Voronoi网格的不规则性正好可以用来模拟可破碎物体碎片，提高系统真实性。因此我们采用3D Voronoi网格对可破碎物体进行预处理，得到物体所有碎片，并且用网状结构将碎片重新组合在一起成为一个整体，这就是可破碎物体建模过程。

【关键词】网格；Voronoi图；对偶图

1 三维Voronoi图算法

Voronoi图又叫泰森多边形。要使用Voronoi网格对物体进行分割，首先需要建立一个三维Voronoi图，然后将可破碎模型放入Voronoi网格中，将物体分割成若干碎片。

三维Voronoi图是对一大堆三维空间点在空间上的划分。划分后每个点都在一个Voronoi区域内，该区域是一个多面体的不规则形状。划分后每个点到包围该点的Voronoi区域的距离最近，并且各个区域之间没有重叠且没有缝隙。所有区域连在一起就构成够了整个Voronoi图。

目前生成Voronoi图的方法很多，主要包括两类：直接构造法和间接构造法。直接构造法，就是使用增量法直接构造3D Voronoi图。间接构造法就是先计算三维点集的Delaunay 三角剖分，得到四面体网格，然后根据Delaunay 三角剖分是Voronoi图的对偶图这一关系，快速从Delaunay 三角剖分图得到Voronoi图，如图1左图所示，黑色虚线表示Delaunay 三角剖分图，蓝色部分为Voronoi图。由于直接构造3D Voronoi图比较麻烦，且目前成熟的算法不多。而目前对Delaunay 三角剖分图的构造方法很多，所以本文采用逐点插入法构造三维Delaunay网格，然后运用其对偶关系生成Voronoi网格。

三维空间中Delaunay准则为：在三维空间中的一堆顶点组成一系列四面体网格，如果所有四面体的外接球只包含组成四面体的几个顶点，则这样的四面体才能称为Delaunay四面体，所有四面体组成的网格叫做Delaunay网格。Delaunay 三角剖分过程如下：

设N（n）为空间中的n个不同的坐标点x1，x2，…，xn。E（i）表示以点集前i个节点x1，x2，…，xi构成的四面体。从网格E（i）出发，每次加入一个新的节点xi+1。利用Delaunay准则可以构造出新的四面体网格E（i+1），这个过程主要进行以下操作：

（1）找出E（i）中所有外接球包含插入点xi+1的四面体，这些四面体集合称为IE（i），并且更新集合E（i），令E（i）=E（i）-IE（i）；

（2）找出中所有只为一个四面体所有的面，形成集合BF（i）；

（3）遍历集合BF（i）中每个三角形面，让每个面与顶点xi+1生成一个新的四面体网格，并将网格添加到集合NE（i）中，更新E（i），令E（i）=E（i+1）=E（i）+NE（i），当所有顶点经过上述步骤都加入到集合E（i）后，整个集合E就是Delaunay三角剖分网格。这时只需要计算Delaunay网格中每个四面体的外接球球心，然后将外接球心与该球心所在的四面体共面的四个四面体的球心连接在一起，就得到了Voronoi网格，该过程如图1右图所示，细线表示Voronoi网格图，粗线表示四面体。

2 基于三维Voronoi图分割模型

经过上述步骤三维Voronoi网格就生成了，接下来就用Voronoi网格将可破碎模型分割成若干碎片，每个碎片就是通过模型和Voronoi网格单元之间做交集运算得到。用Voronoi网格单元分割可破碎物体的整个过程，Voronoi网格单元和物体模型的交集就是物体碎片。

由于所有Voronoi网格单元都是凸包[1]，所以可以用下面方法得到Voronoi网格单元和物体的相交部分。遍历Voronoi网格的每个面，并计算该面所在的空间平面使其可以覆盖整个物体模型，该平面把物体模型分为两部分标记为F+和F-，F+表示位于Voronoi网格单元内部部分，F-表示位于Voronoi网格单元外部部分。当Voronoi网格的每个平面遍历完成后，模型每次被标记为F+部分就是Voronoi网格单元和物体的交集，即为碎片。

3 结束语

如果被分割[2]的物体只有表面网格，即模型里面是空的，模型被分割后会产生空洞。这就需要使用插值的方法将空洞填补成平面，这样就得到了完整的碎片模型。

【参考文献】

[1]Jose. Voronoi Shattering[OL]. http：//www.joesfer.com/？p=60.2009.

[2]陈魁.应用概率统计[M].北京：清华大学出版社，2000.

[责任编辑：邓丽丽]