摘  要： 在布料仿真中，碰撞檢測(cè)與響應(yīng)十分復(fù)雜，很難同時(shí)具備真實(shí)感和實(shí)時(shí)性。針對(duì)此問題，采用質(zhì)點(diǎn)彈簧模型進(jìn)行建模，基于FDH包圍盒提出一種快速的檢測(cè)基本幾何元素間碰撞的方法。通過分析點(diǎn)的位置向量與三角平面的夾角，利用向量內(nèi)積的性質(zhì)來判斷點(diǎn)與三角形的位置關(guān)系，同時(shí)進(jìn)行了相應(yīng)的碰撞響應(yīng)處理。實(shí)驗(yàn)結(jié)果表明，采用該方法進(jìn)行碰撞檢測(cè)既保證了模擬的真實(shí)性，同時(shí)又提高了系統(tǒng)的實(shí)時(shí)性。
關(guān)鍵詞： 布料模擬；質(zhì)點(diǎn)-彈簧模型；FDH包圍盒；碰撞檢測(cè)；碰撞響應(yīng)

　隨著計(jì)算機(jī)圖形學(xué)、虛擬現(xiàn)實(shí)和計(jì)算機(jī)動(dòng)畫等技術(shù)的興起和普遍應(yīng)用，用高質(zhì)量的計(jì)算機(jī)動(dòng)畫對(duì)極易變形的柔性物體進(jìn)行真實(shí)感仿真成為當(dāng)前研究的熱點(diǎn)課題[1]。在布料動(dòng)態(tài)模擬過程中，碰撞是一個(gè)不容回避的問題，如果不能及時(shí)地進(jìn)行碰撞檢測(cè)并作出相應(yīng)的響應(yīng)處理，就會(huì)出現(xiàn)物體之間相互穿透和重疊等不真實(shí)現(xiàn)象[2]。碰撞檢測(cè)是影響布料模擬速度的重要因素，碰撞問題解決得好壞直接影響到布料仿真的實(shí)時(shí)性和精確性。
　空間中幾何模型間的碰撞檢測(cè)算法一般可以分為空間分解法和層次包圍盒法兩大類[3]。后者的應(yīng)用比較廣泛且種類很多，它的基本思想是用體積略大但形狀特性簡單的包圍盒來近似代替幾何模型，并通過構(gòu)造樹狀層次結(jié)構(gòu)逐漸逼近對(duì)象的幾何特性。若兩個(gè)幾何模型的包圍盒不相交，可認(rèn)為兩物體之間沒有發(fā)生碰撞；否則，需要對(duì)兩物體進(jìn)行精確的檢驗(yàn)。這樣通過包圍盒間的相交測(cè)試快速排除了不相交的基本幾何元素，從而減少了相交測(cè)試的次數(shù)。較典型的有沿坐標(biāo)軸的包圍盒AABB（Axis Aligned Bounding Box）和球包圍盒Spheres，這兩類包圍盒的相交測(cè)試十分簡單，但緊密性相對(duì)較差。方向包圍盒OBB（Oriented Bounding Box）是近些年應(yīng)用比較廣泛的包圍盒，它的最大特點(diǎn)是其方向的任意性，這使得它可根據(jù)被包圍對(duì)象的特點(diǎn)盡可能緊密地包圍對(duì)象，但同時(shí)造成相交測(cè)試變得復(fù)雜。固定方向凸包FDH（Fixed Direction Hull）[4]是一種特殊的凸包，它既繼承了凸包緊密性好的優(yōu)點(diǎn)，同時(shí)也可以看做AABB的擴(kuò)展，具有其簡單性的特點(diǎn)。鑒于其緊密性和簡單性優(yōu)點(diǎn)，本文采用FDH包圍盒方法進(jìn)一步優(yōu)化了布料碰撞檢測(cè)的過程。
　本文首先建立布料的質(zhì)點(diǎn)-彈簧分析模型，并基于FDH包圍盒的碰撞檢測(cè)原理引入向量，優(yōu)化了基本幾何元素間的碰撞檢測(cè)。實(shí)驗(yàn)結(jié)果表明，該方法進(jìn)一步提高了布料與模型的碰撞檢測(cè)效率，而且大大增強(qiáng)了布料仿真過程的實(shí)時(shí)性和真實(shí)性。
1 布料模型的建立
　自1986年WEIL J[5]采用余弦曲線及其幾何變換對(duì)懸垂布料進(jìn)行模擬，大量學(xué)者研究了布料建模的方法。目前應(yīng)用較為廣泛的是由PROVOT X[6]提出的質(zhì)點(diǎn)-彈簧模型，他把布料劃分為矩形網(wǎng)格，網(wǎng)格交點(diǎn)稱為質(zhì)點(diǎn)。為了模擬布料拉伸壓縮、沿平面方向剪切和平面外方向彎曲，分別設(shè)置了結(jié)構(gòu)彈簧、剪切彈簧和彎曲彈簧，質(zhì)點(diǎn)之間用這3種彈簧相連，如圖1所示。

　一個(gè)復(fù)雜的幾何模型是由上萬個(gè)基本幾何元素構(gòu)成的，若采用原始的方法對(duì)兩個(gè)幾何模型中的所有基本幾何元素進(jìn)行兩兩相交測(cè)試，時(shí)間復(fù)雜度將高達(dá)O（n2）[6]，所以本文通過構(gòu)造幾何模型的包圍盒樹的層次結(jié)構(gòu)來逐漸逼近幾何對(duì)象。設(shè)幾何模型的FDH包圍盒為父節(jié)點(diǎn)，采用自上而下的方法構(gòu)造包圍盒樹。
　一棵FDH二叉樹的構(gòu)造過程如下：首先，確定分裂軸，在方向集合D中選擇使包圍盒沿此軸線方向最長的一個(gè)向量作為分裂軸；然后，確定分裂平面，計(jì)算集合中所有基本幾何元素的中心在分裂軸上的投影中值，此值作為分裂軸上分裂點(diǎn)劃分父節(jié)點(diǎn)，這樣父節(jié)點(diǎn)一分為二；接下來，分別以這兩個(gè)節(jié)點(diǎn)為基，繼續(xù)分裂直到最小的節(jié)點(diǎn)單元為幾何模型的基本幾何元素。
3 改進(jìn)的FDH樹碰撞檢測(cè)算法
　進(jìn)行碰撞檢測(cè)，首先分別為布料和其周圍幾何對(duì)象的三角化模型建立相對(duì)應(yīng)的FDH包圍盒二叉樹，然后對(duì)兩棵二叉樹進(jìn)行遍歷判交，這樣可先排除對(duì)象間一定不相交的部分，從而只對(duì)包圍盒相交的部分進(jìn)行基本幾何元素間的精確檢測(cè)，并對(duì)發(fā)生碰撞的部分進(jìn)行碰撞響應(yīng)處理。本文采用FDH包圍盒，依據(jù)上述思想設(shè)計(jì)了基于FDH樹的碰撞檢測(cè)算法。對(duì)于兩棵FDH二叉樹A和B，若兩棵樹的根節(jié)點(diǎn)包圍盒不相交，那么可以判斷兩棵樹不相交；若存在樹A的根節(jié)點(diǎn)與樹B的內(nèi)部節(jié)點(diǎn)的FDH包圍盒不相交，則停止向下遍歷；若一直遍歷到樹B的葉子節(jié)點(diǎn)，那么繼續(xù)用該葉子節(jié)點(diǎn)遍歷樹A；如果遍歷到樹A的葉子節(jié)點(diǎn)，那么近一步對(duì)基本幾何元素進(jìn)行檢測(cè)。算法描述如下：
TraverseTree（A，B）
if（root（A）∩root（B）=?椎）
   return樹A與樹B不相交
 else if（leaf（A）and leaf（B））
   對(duì)基本幾何元素進(jìn)行精確求交
 else if（leaf（A）and NotLeaf（B））
   for each child Cb
   TraverseTree（Cb，A）
else
   for each child Ca
   TraverseTree（Ca，B）
end if
3.1 包圍盒間的相交檢測(cè)
　使用包圍盒進(jìn)行碰撞檢測(cè)，目的是盡早排除所有不可能相交的基本幾何元素對(duì)。包圍盒間的相交測(cè)試速度直接影響碰撞檢測(cè)的速度。本文首先利用FDH在運(yùn)動(dòng)方向上的值排除一部分肯定不發(fā)生碰撞的包圍盒，對(duì)于可能發(fā)生碰撞的再利用投影判交的方法作進(jìn)一步檢測(cè)。
　以平行于XoZ面放置的布料與桌面碰撞為例，當(dāng)布料下落時(shí)最先發(fā)生碰撞的一定是布料（0，-1，0）方向和桌面（0，1，0）方向上的包圍盒。因此可以選取布料包圍盒（0，-1，0）方向上的FDH值yc與桌面包圍盒（0，1，0）方向上的FDH值yd，若yc>yd，則布料包圍盒與桌面包圍盒一定不發(fā)生碰撞。若yc≤yd，則觀察兩個(gè)包圍盒的投影區(qū)間的相交情況：如果兩向量集合在某個(gè)方向上的投影區(qū)間不相交，則兩包圍盒必不相交；若在所有方向上的投影區(qū)間都相交，那么兩包圍盒相交，但并不說明布料與桌面一定發(fā)生碰撞，還要對(duì)基本幾何元素作進(jìn)一步檢測(cè)。采用這種方法可以在進(jìn)行投影判交之前先排除一部分不可能相交的包圍盒，省略很多不必要的投影比較，當(dāng)幾何模型的點(diǎn)比較多時(shí)明顯地提高了檢測(cè)效率。
3.2 基本幾何元素的碰撞檢測(cè)
　通過FDH包圍盒間的相交測(cè)試之后，排除了肯定不會(huì)發(fā)生碰撞的區(qū)域，但對(duì)于包圍盒發(fā)生碰撞的區(qū)域，尚不能確定包圍盒內(nèi)的基本幾何元素之間是否發(fā)生碰撞[10]。此時(shí)有必要進(jìn)行基本幾何元素間的碰撞檢測(cè)。本文利用質(zhì)點(diǎn)-彈簧模型模擬布料運(yùn)動(dòng)并以三角網(wǎng)格作為布料的基本幾何元素，同時(shí)對(duì)場(chǎng)景中幾何模型也進(jìn)行了三角化分割，這樣基本幾何元素間碰撞轉(zhuǎn)化為三角形間求交問題，此類問題可歸結(jié)為點(diǎn)-三角形碰撞檢測(cè)問題。
　現(xiàn)有的點(diǎn)-三角形碰撞檢測(cè)方法是通過求解一個(gè)三元一次方程組或求解多個(gè)一元一次方程的方法來確定基本幾何元素之間的距離[11]，從而判斷兩者是否發(fā)生碰撞，計(jì)算比較復(fù)雜。本文提出一種新的點(diǎn)-三角形碰撞檢測(cè)方法，通過分析點(diǎn)的位置向量與三角平面的夾角來判斷點(diǎn)與三角形的位置關(guān)系，從而得出是否發(fā)生碰撞。
如圖3和圖4所示，假設(shè)?駐ABC、?駐DEF分別為兩模型的基本幾何元素，其中點(diǎn)B是最可能發(fā)生碰撞的點(diǎn)，為碰撞粒子，則問題轉(zhuǎn)化為檢測(cè)點(diǎn)B與?駐DEF的碰撞情況。圖3為在第k個(gè)時(shí)間步長?駐ABC和?駐DEF的相對(duì)位置，其中點(diǎn)N為點(diǎn)B在面DEF上的投影。若到了k+1步，點(diǎn)B運(yùn)動(dòng)到B′位置，那么判斷點(diǎn)B與?駐DEF是否相交的算法描述如下：

　由此，可根據(jù)不同情況獲得碰撞后質(zhì)點(diǎn)的速度，進(jìn)而獲得該時(shí)間步長后質(zhì)點(diǎn)的新位置，有效處理碰撞，逼真地模擬布料運(yùn)動(dòng)。
5 實(shí)驗(yàn)結(jié)果及分析
　本文在奔騰IV 2.8 GHz，1 GB內(nèi)存的PC上，以O(shè)penGL圖形庫為基礎(chǔ)，使用VC++作為開發(fā)環(huán)境進(jìn)行仿真。首先定義布料和碰撞對(duì)象的初始位置，然后布料在各種內(nèi)力和外力的共同作用下向下運(yùn)動(dòng)，實(shí)現(xiàn)了具有不同質(zhì)點(diǎn)個(gè)數(shù)的布料與桌子和球體的碰撞檢測(cè)和碰撞響應(yīng)實(shí)驗(yàn)。
　圖5是布料與桌子的碰撞檢測(cè)，可見圖中布料自然下垂，在方形桌子的棱角處十分自然，并產(chǎn)生了真實(shí)的褶皺效果。圖6、圖7為各種狀態(tài)下的布料與不同數(shù)量的球體的碰撞檢測(cè)，模擬效果自然逼真。

　本文基于質(zhì)點(diǎn)，彈簧模型建立FDH包圍盒，實(shí)現(xiàn)了布料與幾何模型的碰撞檢測(cè)及響應(yīng)。在進(jìn)行基本幾何元素間的碰撞檢時(shí)，利用向量內(nèi)積的性質(zhì)判斷點(diǎn)-三角形是否發(fā)生碰撞，從而省去了對(duì)點(diǎn)到平面距離等繁復(fù)的運(yùn)算的求解。實(shí)驗(yàn)結(jié)果表明，采用本文方法模擬布料與幾何模型的碰撞，在產(chǎn)生自然逼真模擬效果的前提下，使得系統(tǒng)實(shí)時(shí)性有較大的提高。
參考文獻(xiàn)
[1] 沈才樑，李偉，余立豐，等.基于局部自適應(yīng)混合積分的動(dòng)態(tài)布料模擬快速方法[J].計(jì)算機(jī)應(yīng)用研究，2012，29（7）：2740-2742.
[2] 陳昕，徐乃平.真實(shí)感布仿真中布與剛體的碰撞檢測(cè)及修正[J].軟件學(xué)報(bào)，2001，12（12）：1874-1880.
[3] 湯亮，曹衛(wèi)星，朱艷.作物可視化中的碰撞檢測(cè)及相應(yīng)研究[J].計(jì)算機(jī)科學(xué)，2011，38（10）：263-284.
[4] 魏迎敏，王涌，吳泉源，等.碰撞檢測(cè)中的固定方向凸包包圍盒的研究[J].軟件學(xué)報(bào)，2001，12（7）：1056-1062.
[5] WEIL J. The synthesis of cloth objects[J]. ACM SIGGRAPH Computer Graphics， 1986，20（4）：49-54.
[6] PROVOT X. Deformation constraints in a mass-spring model to describe rigid cloth behavior[J]. Proceedings of Graphics Interface，1995：147-154.
[7] LING L， DAMODARAN M， GAY K L. A model for animating cloth motion in air flow[C].  TENCON′94. IEEE Region 10′s Ninth Annual  International Conference， 1994：118-122.
[8] 金一慶，陳越，王冬梅.數(shù)值方法[M].北京：機(jī)械工業(yè)出版社，2007.
[9] 汪嘉業(yè)，王文平，屠長河，等.計(jì)算機(jī)幾何及應(yīng)用[M].北京：科學(xué)出版社，2011.
[10] 趙慧青.虛擬服裝設(shè)計(jì)中的布料仿真與碰撞檢測(cè)算法研究[D].成都：成都理工大學(xué)，2008.
[11] 羅謙.基于三角網(wǎng)格的變形體碰撞檢測(cè)算法研究[D].杭州：浙江大學(xué)，2006.
[12] BRIDSOU R， FEDKIW R， ANDERSON J. Robust treatment of collisions，contact and friction for cloth animation[A]. Computer Graphics Proceedings， Annual Conference Series， ACM SIGGRAPH， SanAntonio，Texas，2002：594-603.
[13] 顧爾丹，許端清，王靖斌，等.結(jié)合一種面-面碰撞   檢測(cè)算法的服裝動(dòng)態(tài)模擬[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2002，14（11）：1036-1040.