倪雪飛　張雄祥

【摘 要】由于Voronoi網(wǎng)格和真實世界中剛體碎片的樣子非常接近， Voronoi網(wǎng)格的不規(guī)則性正好可以用來模擬可破碎物體碎片，提高系統(tǒng)真實性。因此我們采用3D Voronoi網(wǎng)格對可破碎物體進行預處理，得到物體所有碎片，并且用網(wǎng)狀結(jié)構(gòu)將碎片重新組合在一起成為一個整體，這就是可破碎物體建模過程。

【關鍵詞】網(wǎng)格；Voronoi圖；對偶圖

1 三維Voronoi圖算法

Voronoi圖又叫泰森多邊形。要使用Voronoi網(wǎng)格對物體進行分割，首先需要建立一個三維Voronoi圖，然后將可破碎模型放入Voronoi網(wǎng)格中，將物體分割成若干碎片。

三維Voronoi圖是對一大堆三維空間點在空間上的劃分。劃分后每個點都在一個Voronoi區(qū)域內(nèi)，該區(qū)域是一個多面體的不規(guī)則形狀。劃分后每個點到包圍該點的Voronoi區(qū)域的距離最近，并且各個區(qū)域之間沒有重疊且沒有縫隙。所有區(qū)域連在一起就構(gòu)成夠了整個Voronoi圖。

目前生成Voronoi圖的方法很多，主要包括兩類：直接構(gòu)造法和間接構(gòu)造法。直接構(gòu)造法，就是使用增量法直接構(gòu)造3D Voronoi圖。間接構(gòu)造法就是先計算三維點集的Delaunay 三角剖分，得到四面體網(wǎng)格，然后根據(jù)Delaunay 三角剖分是Voronoi圖的對偶圖這一關系，快速從Delaunay 三角剖分圖得到Voronoi圖，如圖1左圖所示，黑色虛線表示Delaunay 三角剖分圖，藍色部分為Voronoi圖。由于直接構(gòu)造3D Voronoi圖比較麻煩，且目前成熟的算法不多。而目前對Delaunay 三角剖分圖的構(gòu)造方法很多，所以本文采用逐點插入法構(gòu)造三維Delaunay網(wǎng)格，然后運用其對偶關系生成Voronoi網(wǎng)格。

三維空間中Delaunay準則為：在三維空間中的一堆頂點組成一系列四面體網(wǎng)格，如果所有四面體的外接球只包含組成四面體的幾個頂點，則這樣的四面體才能稱為Delaunay四面體，所有四面體組成的網(wǎng)格叫做Delaunay網(wǎng)格。Delaunay 三角剖分過程如下：

設N（n）為空間中的n個不同的坐標點x1，x2，…，xn。E（i）表示以點集前i個節(jié)點x1，x2，…，xi構(gòu)成的四面體。從網(wǎng)格E（i）出發(fā)，每次加入一個新的節(jié)點xi+1。利用Delaunay準則可以構(gòu)造出新的四面體網(wǎng)格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生成一個新的四面體網(wǎng)格，并將網(wǎng)格添加到集合NE（i）中，更新E（i），令E（i）=E（i+1）=E（i）+NE（i），當所有頂點經(jīng)過上述步驟都加入到集合E（i）后，整個集合E就是Delaunay三角剖分網(wǎng)格。這時只需要計算Delaunay網(wǎng)格中每個四面體的外接球球心，然后將外接球心與該球心所在的四面體共面的四個四面體的球心連接在一起，就得到了Voronoi網(wǎng)格，該過程如圖1右圖所示，細線表示Voronoi網(wǎng)格圖，粗線表示四面體。

2 基于三維Voronoi圖分割模型

經(jīng)過上述步驟三維Voronoi網(wǎng)格就生成了，接下來就用Voronoi網(wǎng)格將可破碎模型分割成若干碎片，每個碎片就是通過模型和Voronoi網(wǎng)格單元之間做交集運算得到。用Voronoi網(wǎng)格單元分割可破碎物體的整個過程，Voronoi網(wǎng)格單元和物體模型的交集就是物體碎片。

由于所有Voronoi網(wǎng)格單元都是凸包[1]，所以可以用下面方法得到Voronoi網(wǎng)格單元和物體的相交部分。遍歷Voronoi網(wǎng)格的每個面，并計算該面所在的空間平面使其可以覆蓋整個物體模型，該平面把物體模型分為兩部分標記為F+和F-，F(xiàn)+表示位于Voronoi網(wǎng)格單元內(nèi)部部分，F(xiàn)-表示位于Voronoi網(wǎng)格單元外部部分。當Voronoi網(wǎng)格的每個平面遍歷完成后，模型每次被標記為F+部分就是Voronoi網(wǎng)格單元和物體的交集，即為碎片。

3 結(jié)束語

如果被分割[2]的物體只有表面網(wǎng)格，即模型里面是空的，模型被分割后會產(chǎn)生空洞。這就需要使用插值的方法將空洞填補成平面，這樣就得到了完整的碎片模型。

【參考文獻】

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

[2]陳魁.應用概率統(tǒng)計[M].北京：清華大學出版社，2000.

[責任編輯：鄧麗麗]