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

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

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

　由此，可根據不同情況獲得碰撞后質點的速度，進而獲得該時間步長后質點的新位置，有效處理碰撞，逼真地模擬布料運動。
5 實驗結果及分析
　本文在奔騰IV 2.8 GHz，1 GB內存的PC上，以OpenGL圖形庫為基礎，使用VC++作為開發環境進行仿真。首先定義布料和碰撞對象的初始位置，然后布料在各種內力和外力的共同作用下向下運動，實現了具有不同質點個數的布料與桌子和球體的碰撞檢測和碰撞響應實驗。
　圖5是布料與桌子的碰撞檢測，可見圖中布料自然下垂，在方形桌子的棱角處十分自然，并產生了真實的褶皺效果。圖6、圖7為各種狀態下的布料與不同數量的球體的碰撞檢測，模擬效果自然逼真。

　本文基于質點，彈簧模型建立FDH包圍盒，實現了布料與幾何模型的碰撞檢測及響應。在進行基本幾何元素間的碰撞檢時，利用向量內積的性質判斷點-三角形是否發生碰撞，從而省去了對點到平面距離等繁復的運算的求解。實驗結果表明，采用本文方法模擬布料與幾何模型的碰撞，在產生自然逼真模擬效果的前提下，使得系統實時性有較大的提高。
參考文獻
[1] 沈才樑，李偉，余立豐，等.基于局部自適應混合積分的動態布料模擬快速方法[J].計算機應用研究，2012，29（7）：2740-2742.
[2] 陳昕，徐乃平.真實感布仿真中布與剛體的碰撞檢測及修正[J].軟件學報，2001，12（12）：1874-1880.
[3] 湯亮，曹衛星，朱艷.作物可視化中的碰撞檢測及相應研究[J].計算機科學，2011，38（10）：263-284.
[4] 魏迎敏，王涌，吳泉源，等.碰撞檢測中的固定方向凸包包圍盒的研究[J].軟件學報，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] 金一慶，陳越，王冬梅.數值方法[M].北京：機械工業出版社，2007.
[9] 汪嘉業，王文平，屠長河，等.計算機幾何及應用[M].北京：科學出版社，2011.
[10] 趙慧青.虛擬服裝設計中的布料仿真與碰撞檢測算法研究[D].成都：成都理工大學，2008.
[11] 羅謙.基于三角網格的變形體碰撞檢測算法研究[D].杭州：浙江大學，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] 顧爾丹，許端清，王靖斌，等.結合一種面-面碰撞   檢測算法的服裝動態模擬[J].計算機輔助設計與圖形學學報，2002，14（11）：1036-1040.