摘 要： 在布料仿真中，碰撞檢測與響應(yīng)十分復(fù)雜，很難同時具備真實感和實時性。針對此問題，采用質(zhì)點彈簧模型進(jìn)行建模，基于FDH包圍盒提出一種快速的檢測基本幾何元素間碰撞的方法。通過分析點的位置向量與三角平面的夾角，利用向量內(nèi)積的性質(zhì)來判斷點與三角形的位置關(guān)系，同時進(jìn)行了相應(yīng)的碰撞響應(yīng)處理。實驗結(jié)果表明，采用該方法進(jìn)行碰撞檢測既保證了模擬的真實性，同時又提高了系統(tǒng)的實時性。
關(guān)鍵詞： 布料模擬；質(zhì)點-彈簧模型；FDH包圍盒；碰撞檢測；碰撞響應(yīng)
隨著計算機(jī)圖形學(xué)、虛擬現(xiàn)實和計算機(jī)動畫等技術(shù)的興起和普遍應(yīng)用，用高質(zhì)量的計算機(jī)動畫對極易變形的柔性物體進(jìn)行真實感仿真成為當(dāng)前研究的熱點課題[1]。在布料動態(tài)模擬過程中，碰撞是一個不容回避的問題，如果不能及時地進(jìn)行碰撞檢測并作出相應(yīng)的響應(yīng)處理，就會出現(xiàn)物體之間相互穿透和重疊等不真實現(xiàn)象[2]。碰撞檢測是影響布料模擬速度的重要因素，碰撞問題解決得好壞直接影響到布料仿真的實時性和精確性。
空間中幾何模型間的碰撞檢測算法一般可以分為空間分解法和層次包圍盒法兩大類[3]。后者的應(yīng)用比較廣泛且種類很多，它的基本思想是用體積略大但形狀特性簡單的包圍盒來近似代替幾何模型，并通過構(gòu)造樹狀層次結(jié)構(gòu)逐漸逼近對象的幾何特性。若兩個幾何模型的包圍盒不相交，可認(rèn)為兩物體之間沒有發(fā)生碰撞；否則，需要對兩物體進(jìn)行精確的檢驗。這樣通過包圍盒間的相交測試快速排除了不相交的基本幾何元素，從而減少了相交測試的次數(shù)。較典型的有沿坐標(biāo)軸的包圍盒AABB（Axis Aligned Bounding Box）和球包圍盒Spheres，這兩類包圍盒的相交測試十分簡單，但緊密性相對較差。方向包圍盒OBB（Oriented Bounding Box）是近些年應(yīng)用比較廣泛的包圍盒，它的最大特點是其方向的任意性，這使得它可根據(jù)被包圍對象的特點盡可能緊密地包圍對象，但同時造成相交測試變得復(fù)雜。固定方向凸包FDH（Fixed Direction Hull）[4]是一種特殊的凸包，它既繼承了凸包緊密性好的優(yōu)點，同時也可以看做AABB的擴(kuò)展，具有其簡單性的特點。鑒于其緊密性和簡單性優(yōu)點，本文采用FDH包圍盒方法進(jìn)一步優(yōu)化了布料碰撞檢測的過程。
本文首先建立布料的質(zhì)點-彈簧分析模型，并基于FDH包圍盒的碰撞檢測原理引入向量，優(yōu)化了基本幾何元素間的碰撞檢測。實驗結(jié)果表明，該方法進(jìn)一步提高了布料與模型的碰撞檢測效率，而且大大增強(qiáng)了布料仿真過程的實時性和真實性。
1 布料模型的建立
自1986年WEIL J[5]采用余弦曲線及其幾何變換對懸垂布料進(jìn)行模擬，大量學(xué)者研究了布料建模的方法。目前應(yīng)用較為廣泛的是由PROVOT X[6]提出的質(zhì)點-彈簧模型，他把布料劃分為矩形網(wǎng)格，網(wǎng)格交點稱為質(zhì)點。為了模擬布料拉伸壓縮、沿平面方向剪切和平面外方向彎曲，分別設(shè)置了結(jié)構(gòu)彈簧、剪切彈簧和彎曲彈簧，質(zhì)點之間用這3種彈簧相連，如圖1所示。
一個復(fù)雜的幾何模型是由上萬個基本幾何元素構(gòu)成的，若采用原始的方法對兩個幾何模型中的所有基本幾何元素進(jìn)行兩兩相交測試，時間復(fù)雜度將高達(dá)O（n2）[6]，所以本文通過構(gòu)造幾何模型的包圍盒樹的層次結(jié)構(gòu)來逐漸逼近幾何對象。設(shè)幾何模型的FDH包圍盒為父節(jié)點，采用自上而下的方法構(gòu)造包圍盒樹。
一棵FDH二叉樹的構(gòu)造過程如下：首先，確定分裂軸，在方向集合D中選擇使包圍盒沿此軸線方向最長的一個向量作為分裂軸；然后，確定分裂平面，計算集合中所有基本幾何元素的中心在分裂軸上的投影中值，此值作為分裂軸上分裂點劃分父節(jié)點，這樣父節(jié)點一分為二；接下來，分別以這兩個節(jié)點為基，繼續(xù)分裂直到最小的節(jié)點單元為幾何模型的基本幾何元素。
3 改進(jìn)的FDH樹碰撞檢測算法
進(jìn)行碰撞檢測，首先分別為布料和其周圍幾何對象的三角化模型建立相對應(yīng)的FDH包圍盒二叉樹，然后對兩棵二叉樹進(jìn)行遍歷判交，這樣可先排除對象間一定不相交的部分，從而只對包圍盒相交的部分進(jìn)行基本幾何元素間的精確檢測，并對發(fā)生碰撞的部分進(jìn)行碰撞響應(yīng)處理。本文采用FDH包圍盒，依據(jù)上述思想設(shè)計了基于FDH樹的碰撞檢測算法。對于兩棵FDH二叉樹A和B，若兩棵樹的根節(jié)點包圍盒不相交，那么可以判斷兩棵樹不相交；若存在樹A的根節(jié)點與樹B的內(nèi)部節(jié)點的FDH包圍盒不相交，則停止向下遍歷；若一直遍歷到樹B的葉子節(jié)點，那么繼續(xù)用該葉子節(jié)點遍歷樹A；如果遍歷到樹A的葉子節(jié)點，那么近一步對基本幾何元素進(jìn)行檢測。算法描述如下：
TraverseTree（A，B）
if（root（A）∩root（B）=?椎）
return樹A與樹B不相交
else if（leaf（A）and leaf（B））
對基本幾何元素進(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 包圍盒間的相交檢測
使用包圍盒進(jìn)行碰撞檢測，目的是盡早排除所有不可能相交的基本幾何元素對。包圍盒間的相交測試速度直接影響碰撞檢測的速度。本文首先利用FDH在運動方向上的值排除一部分肯定不發(fā)生碰撞的包圍盒，對于可能發(fā)生碰撞的再利用投影判交的方法作進(jìn)一步檢測。
以平行于XoZ面放置的布料與桌面碰撞為例，當(dāng)布料下落時最先發(fā)生碰撞的一定是布料（0，-1，0）方向和桌面（0，1，0）方向上的包圍盒。因此可以選取布料包圍盒（0，-1，0）方向上的FDH值yc與桌面包圍盒（0，1，0）方向上的FDH值yd，若yc>yd，則布料包圍盒與桌面包圍盒一定不發(fā)生碰撞。若yc≤yd，則觀察兩個包圍盒的投影區(qū)間的相交情況：如果兩向量集合在某個方向上的投影區(qū)間不相交，則兩包圍盒必不相交；若在所有方向上的投影區(qū)間都相交，那么兩包圍盒相交，但并不說明布料與桌面一定發(fā)生碰撞，還要對基本幾何元素作進(jìn)一步檢測。采用這種方法可以在進(jìn)行投影判交之前先排除一部分不可能相交的包圍盒，省略很多不必要的投影比較，當(dāng)幾何模型的點比較多時明顯地提高了檢測效率。
3.2 基本幾何元素的碰撞檢測
通過FDH包圍盒間的相交測試之后，排除了肯定不會發(fā)生碰撞的區(qū)域，但對于包圍盒發(fā)生碰撞的區(qū)域，尚不能確定包圍盒內(nèi)的基本幾何元素之間是否發(fā)生碰撞[10]。此時有必要進(jìn)行基本幾何元素間的碰撞檢測。本文利用質(zhì)點-彈簧模型模擬布料運動并以三角網(wǎng)格作為布料的基本幾何元素，同時對場景中幾何模型也進(jìn)行了三角化分割，這樣基本幾何元素間碰撞轉(zhuǎn)化為三角形間求交問題，此類問題可歸結(jié)為點-三角形碰撞檢測問題。
現(xiàn)有的點-三角形碰撞檢測方法是通過求解一個三元一次方程組或求解多個一元一次方程的方法來確定基本幾何元素之間的距離[11]，從而判斷兩者是否發(fā)生碰撞，計算比較復(fù)雜。本文提出一種新的點-三角形碰撞檢測方法，通過分析點的位置向量與三角平面的夾角來判斷點與三角形的位置關(guān)系，從而得出是否發(fā)生碰撞。
如圖3和圖4所示，假設(shè)?駐ABC、?駐DEF分別為兩模型的基本幾何元素，其中點B是最可能發(fā)生碰撞的點，為碰撞粒子，則問題轉(zhuǎn)化為檢測點B與?駐DEF的碰撞情況。圖3為在第k個時間步長?駐ABC和?駐DEF的相對位置，其中點N為點B在面DEF上的投影。若到了k+1步，點B運動到B′位置，那么判斷點B與?駐DEF是否相交的算法描述如下：
由此，可根據(jù)不同情況獲得碰撞后質(zhì)點的速度，進(jìn)而獲得該時間步長后質(zhì)點的新位置，有效處理碰撞，逼真地模擬布料運動。
5 實驗結(jié)果及分析
本文在奔騰IV 2.8 GHz，1 GB內(nèi)存的PC上，以O(shè)penGL圖形庫為基礎(chǔ)，使用VC++作為開發(fā)環(huán)境進(jìn)行仿真。首先定義布料和碰撞對象的初始位置，然后布料在各種內(nèi)力和外力的共同作用下向下運動，實現(xiàn)了具有不同質(zhì)點個數(shù)的布料與桌子和球體的碰撞檢測和碰撞響應(yīng)實驗。
圖5是布料與桌子的碰撞檢測，可見圖中布料自然下垂，在方形桌子的棱角處十分自然，并產(chǎn)生了真實的褶皺效果。圖6、圖7為各種狀態(tài)下的布料與不同數(shù)量的球體的碰撞檢測，模擬效果自然逼真。
本文基于質(zhì)點，彈簧模型建立FDH包圍盒，實現(xiàn)了布料與幾何模型的碰撞檢測及響應(yīng)。在進(jìn)行基本幾何元素間的碰撞檢時，利用向量內(nèi)積的性質(zhì)判斷點-三角形是否發(fā)生碰撞，從而省去了對點到平面距離等繁復(fù)的運算的求解。實驗結(jié)果表明，采用本文方法模擬布料與幾何模型的碰撞，在產(chǎn)生自然逼真模擬效果的前提下，使得系統(tǒng)實時性有較大的提高。
參考文獻(xiàn)
[1] 沈才樑，李偉，余立豐，等.基于局部自適應(yīng)混合積分的動態(tài)布料模擬快速方法[J].計算機(jī)應(yīng)用研究，2012，29（7）：2740-2742.
[2] 陳昕，徐乃平.真實感布仿真中布與剛體的碰撞檢測及修正[J].軟件學(xué)報，2001，12（12）：1874-1880.
[3] 湯亮，曹衛(wèi)星，朱艷.作物可視化中的碰撞檢測及相應(yīng)研究[J].計算機(jī)科學(xué)，2011，38（10）：263-284.
[4] 魏迎敏，王涌，吳泉源，等.碰撞檢測中的固定方向凸包包圍盒的研究[J].軟件學(xué)報，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ī)幾何及應(yīng)用[M].北京：科學(xué)出版社，2011.
[10] 趙慧青.虛擬服裝設(shè)計中的布料仿真與碰撞檢測算法研究[D].成都：成都理工大學(xué)，2008.
[11] 羅謙.基于三角網(wǎng)格的變形體碰撞檢測算法研究[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é)合一種面-面碰撞 檢測算法的服裝動態(tài)模擬[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，2002，14（11）：1036-1040.