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

　一個(gè)復(fù)雜的幾何模型是由上萬(wàn)個(gè)基本幾何元素構(gòu)成的,，若采用原始的方法對(duì)兩個(gè)幾何模型中的所有基本幾何元素進(jìn)行兩兩相交測(cè)試,，時(shí)間復(fù)雜度將高達(dá)O（n2）[6]，所以本文通過(guò)構(gòu)造幾何模型的包圍盒樹(shù)的層次結(jié)構(gòu)來(lái)逐漸逼近幾何對(duì)象,。設(shè)幾何模型的FDH包圍盒為父節(jié)點(diǎn),，采用自上而下的方法構(gòu)造包圍盒樹(shù)。
　一棵FDH二叉樹(shù)的構(gòu)造過(guò)程如下：首先,，確定分裂軸,，在方向集合D中選擇使包圍盒沿此軸線(xiàn)方向最長(zhǎng)的一個(gè)向量作為分裂軸；然后,，確定分裂平面,，計(jì)算集合中所有基本幾何元素的中心在分裂軸上的投影中值，此值作為分裂軸上分裂點(diǎn)劃分父節(jié)點(diǎn),，這樣父節(jié)點(diǎn)一分為二,；接下來(lái)，分別以這兩個(gè)節(jié)點(diǎn)為基,，繼續(xù)分裂直到最小的節(jié)點(diǎn)單元為幾何模型的基本幾何元素,。
3 改進(jìn)的FDH樹(shù)碰撞檢測(cè)算法
　進(jìn)行碰撞檢測(cè)，首先分別為布料和其周?chē)鷰缀螌?duì)象的三角化模型建立相對(duì)應(yīng)的FDH包圍盒二叉樹(shù)，然后對(duì)兩棵二叉樹(shù)進(jìn)行遍歷判交,，這樣可先排除對(duì)象間一定不相交的部分,，從而只對(duì)包圍盒相交的部分進(jìn)行基本幾何元素間的精確檢測(cè)，并對(duì)發(fā)生碰撞的部分進(jìn)行碰撞響應(yīng)處理,。本文采用FDH包圍盒,，依據(jù)上述思想設(shè)計(jì)了基于FDH樹(shù)的碰撞檢測(cè)算法。對(duì)于兩棵FDH二叉樹(shù)A和B,，若兩棵樹(shù)的根節(jié)點(diǎn)包圍盒不相交,，那么可以判斷兩棵樹(shù)不相交；若存在樹(shù)A的根節(jié)點(diǎn)與樹(shù)B的內(nèi)部節(jié)點(diǎn)的FDH包圍盒不相交,，則停止向下遍歷,；若一直遍歷到樹(shù)B的葉子節(jié)點(diǎn)，那么繼續(xù)用該葉子節(jié)點(diǎn)遍歷樹(shù)A,；如果遍歷到樹(shù)A的葉子節(jié)點(diǎn),，那么近一步對(duì)基本幾何元素進(jìn)行檢測(cè)。算法描述如下：
TraverseTree（A,，B）
if（root（A）∩root（B）=?椎）
   return樹(shù)A與樹(shù)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,，則觀(guān)察兩個(gè)包圍盒的投影區(qū)間的相交情況：如果兩向量集合在某個(gè)方向上的投影區(qū)間不相交,，則兩包圍盒必不相交,；若在所有方向上的投影區(qū)間都相交,，那么兩包圍盒相交,，但并不說(shuō)明布料與桌面一定發(fā)生碰撞，還要對(duì)基本幾何元素作進(jìn)一步檢測(cè),。采用這種方法可以在進(jìn)行投影判交之前先排除一部分不可能相交的包圍盒,，省略很多不必要的投影比較，當(dāng)幾何模型的點(diǎn)比較多時(shí)明顯地提高了檢測(cè)效率,。
3.2 基本幾何元素的碰撞檢測(cè)
　通過(guò)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)化為三角形間求交問(wèn)題，此類(lèi)問(wèn)題可歸結(jié)為點(diǎn)-三角形碰撞檢測(cè)問(wèn)題,。
　現(xiàn)有的點(diǎn)-三角形碰撞檢測(cè)方法是通過(guò)求解一個(gè)三元一次方程組或求解多個(gè)一元一次方程的方法來(lái)確定基本幾何元素之間的距離[11],，從而判斷兩者是否發(fā)生碰撞，計(jì)算比較復(fù)雜,。本文提出一種新的點(diǎn)-三角形碰撞檢測(cè)方法,，通過(guò)分析點(diǎn)的位置向量與三角平面的夾角來(lái)判斷點(diǎn)與三角形的位置關(guān)系，從而得出是否發(fā)生碰撞,。
如圖3和圖4所示,，假設(shè)?駐ABC、?駐DEF分別為兩模型的基本幾何元素,，其中點(diǎn)B是最可能發(fā)生碰撞的點(diǎn),，為碰撞粒子，則問(wèn)題轉(zhuǎn)化為檢測(cè)點(diǎn)B與?駐DEF的碰撞情況,。圖3為在第k個(gè)時(shí)間步長(zhǎng)?駐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ǎng)后質(zhì)點(diǎn)的新位置,，有效處理碰撞，逼真地模擬布料運(yùn)動(dòng),。
5 實(shí)驗(yàn)結(jié)果及分析
　本文在奔騰IV 2.8 GHz,，1 GB內(nèi)存的PC上，以O(shè)penGL圖形庫(kù)為基礎(chǔ)，使用VC++作為開(kāi)發(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è),，可見(jiàn)圖中布料自然下垂，在方形桌子的棱角處十分自然,，并產(chǎn)生了真實(shí)的褶皺效果,。圖6、圖7為各種狀態(tài)下的布料與不同數(shù)量的球體的碰撞檢測(cè),，模擬效果自然逼真,。

　本文基于質(zhì)點(diǎn)，彈簧模型建立FDH包圍盒,，實(shí)現(xiàn)了布料與幾何模型的碰撞檢測(cè)及響應(yīng),。在進(jìn)行基本幾何元素間的碰撞檢時(shí)，利用向量?jī)?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è)，王文平,，屠長(zhǎng)河,，等.計(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.