倪雪飛　秦富春

【摘 要】體素化（Voxelization）模型是為了解決描述模型內(nèi)部屬性如材料、密度等信息時(shí)產(chǎn)生的，體素化則是將物體的幾何信息轉(zhuǎn)化成最接近物體的體數(shù)據(jù)（Volume Datas）。體素化后的模型不僅包含模型的表面信息，而且能描述模型內(nèi)部的屬性。體素是由一組三維的立方體格子組成。

【關(guān)鍵詞】體素化；尺度空間理論；距離場(chǎng)

體素化模型根據(jù)各自的特點(diǎn)各有不同，文獻(xiàn)[1]是根據(jù)法向量的函數(shù)作為標(biāo)準(zhǔn)將模型離散的體素模型，文獻(xiàn)[2]根據(jù)尺度空間理論（Scale-space Theory）的反走樣體素模型，文獻(xiàn)[3]是根據(jù)距離場(chǎng)（Distance Fields）和距離變換（Distance Transform）的方法建立體素模型。

1 預(yù)處理過(guò)程

根據(jù)人體、流體在世界空間中的范圍大小，設(shè)定網(wǎng)格模型的范圍。方向與歐氏空間的，軸方向相同，體素空間是離散空間，坐標(biāo)是整數(shù)坐標(biāo)，每一個(gè)坐標(biāo)序列對(duì)應(yīng)模型唯一的體素網(wǎng)格。由于體素化存在精度的問(wèn)題，網(wǎng)格范圍不應(yīng)該大于實(shí)際模型空間范圍，不然一個(gè)模型頂點(diǎn)將對(duì)應(yīng)多個(gè)網(wǎng)格。

在體素空間中存在拓?fù)潢P(guān)系，下面給出定義：

定義1 如果兩個(gè)體素間存在一個(gè)公共頂點(diǎn)或一條公共邊或一個(gè)公共面，則稱兩個(gè)體素是26-鄰接的。

定義2 如果兩個(gè)體素間存在一條公共邊或一個(gè)公共面，則稱兩個(gè)體素是18-鄰接的。

定義3 如果兩個(gè)體素間存在一個(gè)公共面，則稱兩個(gè)體素是6-鄰接的。

這3種鄰接體素模型，約束力關(guān)系可以表示為：6-鄰接<18-鄰接<26-鄰接。

從定義中可以看出，6-鄰接體素模型只能表示體素網(wǎng)格周圍6個(gè)面的鄰接關(guān)系，18-鄰接體素模型可以表示與體素網(wǎng)格12條棱相接的體素網(wǎng)格，而26-鄰接體素模型則可以額外表示體素網(wǎng)格上8個(gè)頂點(diǎn)相接的體素網(wǎng)格。本文采用的是26-鄰接的體素模型，在體素化過(guò)程中提高仿真精度，使仿真更接近真實(shí)物理特性。

2 八叉樹(shù)數(shù)據(jù)結(jié)構(gòu)

一般的八叉樹(shù)僅對(duì)灰節(jié)點(diǎn)（gray）進(jìn)行分解，在本文中，需要對(duì)所有的節(jié)點(diǎn)均進(jìn)行分解操作，這樣才能對(duì)人體與流體的交互信息進(jìn)行判斷。

我們只需要標(biāo)識(shí)體素網(wǎng)格對(duì)應(yīng)模型的實(shí)際屬性，如果是-1則表示落在人體外面，不進(jìn)行交互；如果是0則表示恰好落在人體邊界，進(jìn)行交互處理；由于精度問(wèn)題，上一次探測(cè)失敗的點(diǎn)有可能落在人體里面，表示為1，仍然進(jìn)行交互處理。

3 線性編碼及算法

體素網(wǎng)格的邊界關(guān)系由頂點(diǎn)、邊、面3種關(guān)系組成，在實(shí)際遍歷的方便以及效率的考慮，我們建立一種索引機(jī)制來(lái)對(duì)應(yīng)這種邊界關(guān)系。

線性八叉樹(shù)有很好的編碼方案，如Meagher給出了線性八叉樹(shù)編碼方案。設(shè)定第個(gè)結(jié)點(diǎn)的編碼為公式（1）。

根據(jù)公式（2），可以由八叉樹(shù)的體素化坐標(biāo)得到編碼位的二進(jìn)制組合。再根據(jù)公式（1）求得線性八叉樹(shù)編碼。對(duì)于不同的編碼，按照建立的索引表中的對(duì)應(yīng)關(guān)系找到對(duì)應(yīng)的體素位置。

例如，三角形的體素化，由于三維物體大部分是由三角面片組成的，所以三角形具有代表性。

1）對(duì)于三角形面片的體素化，可以分為點(diǎn)、邊、面的處理。三個(gè)頂點(diǎn)分別為。點(diǎn)的體素坐標(biāo)則表示為：為體素空間的距離大小。根據(jù)公式（1）、公式（2），由體素空間坐標(biāo)求得體素網(wǎng)格的索引編碼，然后由索引編碼可以得到體素位置。

2）在對(duì)點(diǎn)進(jìn)行體素化后，接下來(lái)對(duì)邊進(jìn)行處理。一般位置的邊不垂直和平行坐標(biāo)面，處理這樣的邊時(shí)，相當(dāng)于在邊的一個(gè)頂點(diǎn)發(fā)出射線，指向邊的另一個(gè)頂點(diǎn)，途中經(jīng)過(guò)的所有網(wǎng)格均被標(biāo)記。由于已經(jīng)求得了頂點(diǎn)的體素編碼，可以根據(jù)編碼找到邊的頂點(diǎn)與體素網(wǎng)格相交的方式是點(diǎn)、邊或者是面，然后由得到的相交方式求得相鄰的體素網(wǎng)格，依次遞歸下去。對(duì)于特殊邊的體素處理，只需要將相應(yīng)坐標(biāo)忽略掉即可。如垂直于平面，其體素的分量只需要從第一個(gè)體素網(wǎng)格的開(kāi)始遞增或遞減。這樣就可以得到邊所占據(jù)的所有體素網(wǎng)格的編號(hào)。

3）在處理三角面時(shí)，需要先將三角面投射到具有最大陰影面積的平面上，假設(shè)為平面，投射三角形為。已經(jīng)找到三角形頂點(diǎn)和邊的體素網(wǎng)格和索引，根據(jù)網(wǎng)格坐標(biāo)分量、的范圍來(lái)確定三角面的體素網(wǎng)格。具體做法是先在平面上找到滿足條件的點(diǎn)集坐標(biāo)，然后以點(diǎn)集的點(diǎn)為原點(diǎn)，垂直平面，方向朝向原平面的射線，相交于點(diǎn)，為軸分量，交點(diǎn)為體素網(wǎng)格的坐標(biāo)。最后根據(jù)公式（1）、公式（2），求出八叉樹(shù)編碼，并對(duì)其進(jìn)行標(biāo)記，計(jì)算體素點(diǎn)在人體模型的位置信息。

4 紋理切片

按照上述內(nèi)外體素化算法流程，可以對(duì)人體、流體所在的體素網(wǎng)格進(jìn)行體素化。體素化后的信息是離散的，將數(shù)據(jù)存入三維數(shù)組，便可得到一組有標(biāo)識(shí)位組成的信息。每一組二維數(shù)組對(duì)應(yīng)一層紋理切片。

在計(jì)算出紋理切片信息后，需要遍歷所有層，探測(cè)在每層中流體與固體接觸的邊界位置，從而得到交互信息。而探測(cè)方式則可遍歷二維數(shù)組，根據(jù)相應(yīng)的標(biāo)識(shí)值來(lái)確定的。

當(dāng)遍歷遇到0標(biāo)號(hào)的時(shí)候，標(biāo)記進(jìn)入人體內(nèi)部，當(dāng)再次遇到1的時(shí)候標(biāo)記穿出人體內(nèi)部。依次遞歸下去，即奇數(shù)次為0時(shí)為進(jìn)入邊界，偶數(shù)次為0時(shí)退出邊界。遍歷所有切片，找到需要交互的網(wǎng)格，然后根據(jù)網(wǎng)格信息計(jì)算出在世界坐標(biāo)中的位置。假設(shè)網(wǎng)格坐標(biāo)是c（i，j，k），對(duì)應(yīng)的世界坐標(biāo)有表達(dá)式（3）

5 結(jié)束語(yǔ)

本文采用的是一種基于八叉樹(shù)的方法建立模型對(duì)應(yīng)體素單元的索引，由于我們體素化后的目的是為了判斷與人體模型交互的耦合面，所以不需要建立包含復(fù)雜信息的體素模型。我們采用一種相對(duì)簡(jiǎn)單、快捷的辦法來(lái)建立體素模型。

【參考文獻(xiàn)】

[1]Jian Huang， Roni Yagel， Fillipov V， et al. An accurat method to voxelize polygonal meshes[C]//.In：IEEE Volume Visualization98. Chapel Hill， North Carolina， USA，1998.119～126.

[2]Stijn Oomes， Peter Snoeren， Tjeerd Dijkstra. 3D shape representation： transforming polygons into voxels [C]//. In：Proceedings of the First International Conference on Scale-Space Theory in Computer Vision. Haar Romeny，B.ter，etal.（Ed.），Springer Verlag，1997.349～352.

[3]Kong T Y， Rosenfeld Y A. Digtial topology：introduction and survey[J]. Computer Vision，Graphics and Image Processing，1989，48：357～393.

[責(zé)任編輯：侯天宇]