倪雪飛　張雄祥

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

【關(guān)鍵詞】網(wǎng)格；Voronoi圖；對(duì)偶圖

1 三維Voronoi圖算法

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

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

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

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

設(shè)N（n）為空間中的n個(gè)不同的坐標(biāo)點(diǎn)x1，x2，…，xn。E（i）表示以點(diǎn)集前i個(gè)節(jié)點(diǎn)x1，x2，…，xi構(gòu)成的四面體。從網(wǎng)格E（i）出發(fā)，每次加入一個(gè)新的節(jié)點(diǎn)xi+1。利用Delaunay準(zhǔn)則可以構(gòu)造出新的四面體網(wǎng)格E（i+1），這個(gè)過程主要進(jìn)行以下操作：

（1）找出E（i）中所有外接球包含插入點(diǎn)xi+1的四面體，這些四面體集合稱為IE（i），并且更新集合E（i），令E（i）=E（i）-IE（i）；

（2）找出中所有只為一個(gè)四面體所有的面，形成集合BF（i）；

（3）遍歷集合BF（i）中每個(gè)三角形面，讓每個(gè)面與頂點(diǎn)xi+1生成一個(gè)新的四面體網(wǎng)格，并將網(wǎng)格添加到集合NE（i）中，更新E（i），令E（i）=E（i+1）=E（i）+NE（i），當(dāng)所有頂點(diǎn)經(jīng)過上述步驟都加入到集合E（i）后，整個(gè)集合E就是Delaunay三角剖分網(wǎng)格。這時(shí)只需要計(jì)算Delaunay網(wǎng)格中每個(gè)四面體的外接球球心，然后將外接球心與該球心所在的四面體共面的四個(gè)四面體的球心連接在一起，就得到了Voronoi網(wǎng)格，該過程如圖1右圖所示，細(xì)線表示Voronoi網(wǎng)格圖，粗線表示四面體。

2 基于三維Voronoi圖分割模型

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

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

3 結(jié)束語

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

【參考文獻(xiàn)】

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

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

[責(zé)任編輯：鄧麗麗]