剛體破碎實時模擬算法中的模型預處理

倪雪飛　張雄祥

【摘 要】由于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.

[責任編輯：鄧麗麗]