萬 燕， 符亞玲， 姚 礪

（東華大學(xué) 計算機科學(xué)與技術(shù)學(xué)院， 上海 201620）

0 引 言

隨著計算機仿真的發(fā)展，碰撞檢測作為其中最重要的環(huán)節(jié)之一，也受到了計算機圖形學(xué)研究人員的極大關(guān)注。 近年來，研究人員在碰撞檢測領(lǐng)域提出了各種有效的算法，并開發(fā)了相應(yīng)的軟件包，但是由于復(fù)雜的高精度模型往往包含數(shù)以萬計的三角面，要在短時間內(nèi)檢測碰撞信息是一項極具挑戰(zhàn)性的工作。

目前，大部分實時性較好的碰撞檢測算法都是傳統(tǒng)的離散碰撞檢測算法，只在離散的時間點上對目標(biāo)進(jìn)行碰撞檢測，這類算法可能會造成碰撞缺失，因此形成隧道效應(yīng)，不僅使得場景缺乏真實感，而且會有過大的計算開銷。 有研究者提出一種連續(xù)碰撞算法，在兩個離散時間點之間使用線性插值的方法來描述物體運動軌跡，檢查兩個時間點間是否發(fā)生碰撞，同時計算首次碰撞時間。 碰撞丟失等讓場景產(chǎn)生不真實感的問題在仿真系統(tǒng)中需要盡量避免，因此必須采用連續(xù)碰撞檢測而不是離散碰撞檢測以避免出現(xiàn)假象。

在碰撞檢測中，碰撞目標(biāo)由大量三角基元構(gòu)成，一對三角對的碰撞檢測可轉(zhuǎn)化為9 對點面（） 基本碰撞測試和6 對邊邊（） 基本碰撞測試，這15對基本測試最終轉(zhuǎn)換為求解三階代數(shù)方程的問題。 求解三階代數(shù)方程代價較大，因此對碰撞基元進(jìn)行快速剔除，避免后續(xù)的求解方程是很有必要的，目前普遍采用兩級碰撞算法對三角對進(jìn)行剔除，即高層剔除階段和低層剔除階段，大大減少求解方程的數(shù)量。 經(jīng)過兩層剔除后，再對剩下的相對較少的基本圖元對進(jìn)行精確碰撞檢測。 由于精確碰撞檢測花費時間較多，因此盡量剔除不可能相交的基元，提高整體的碰撞檢測效率。

兩級碰撞檢測算法僅僅規(guī)定了碰撞對需經(jīng)過高層剔除與低層剔除，再執(zhí)行精確碰撞檢測，而兩層剔除各自使用何種算法未作設(shè)定，由研究者自行設(shè)計。目前存在的低層剔除算法要么計算量大或者構(gòu)造難度高，要么剔除率不高，因此，本文提出了空間線性投影濾波器（SLPF），與文獻(xiàn)［6］中的非穿透性過濾器（DNF）相結(jié)合對基本圖元進(jìn)行低層剔除，可以有效提高剔除效率。

1 研究方法

本文采用兩級碰撞檢測算法對三角對進(jìn)行剔除，快速減少大量冗余三角對。 高層剔除選擇包圍盒層次結(jié)構(gòu)（BVH），非穿透性濾波器（DNF）與本文提出的空間線性投影濾波器（SLPF）結(jié)合作為低層剔除方法。 整體算法框架如圖1 所示。

圖1 整體算法框架圖Fig.1 Flow chart of the proposed algorithm

1.1 高層剔除

高層剔除階段主要是對場景中明顯不相交的基元進(jìn)行整體剔除，通常使用包圍盒層次方法（BVH）或者空間分割法。 包圍盒的種類很多，如球形包圍盒、AABB 包圍盒、OBB 包圍盒和kDOPs 包圍盒；空間分割常用的有均勻網(wǎng)格、二維空間分割樹（BSP）和八叉樹（Octree）。

本文的高層剔除選擇包圍盒層次結(jié)構(gòu)（BVH），以包圍盒（BV）作為結(jié)點的樹，根結(jié)點是一個包括所有物體的包圍盒，葉子結(jié)點是最小的包圍盒，通常只包含一個圖元，一個簡單的包圍盒層次結(jié)構(gòu)（二叉BVH 樹）如圖2 所示。 不同的包圍盒，其構(gòu)成的BVH 剔除效果不同，在綜合考慮剔除效果與時間效率后，本文選用k－DOPs 包圍盒。值不同時其剔除效果也不相同，的取值有6、8、12、14、18 和26，理論上值越大剔除效果越好，樹的構(gòu)建和更新所耗費的時間越多，但相交測試的時間越少。 一般情況下，相交測試時間遠(yuǎn)大于構(gòu)建樹的時間，因此選定值為26。 此外，為了進(jìn)一步提升包圍盒剔除效果，本文在傳統(tǒng)BVH 上增加了一層額外包圍盒，使得包圍盒最小包圍的是三角形的點和邊，而不是三角形本身。

圖2 簡單場景二叉BVH 樹Fig.2 Simple example of BVH

1.2 低層剔除

經(jīng)過高層剔除，仍然有很多冗余三角面片不能被剔除，低層剔除將待檢測圖元對的碰撞檢測轉(zhuǎn)換為點面測試和邊邊測試，每個基本測試又可以分為兩個部分：共面測試和內(nèi)部測試。

以點面測試（測試點面對的碰撞情況）為例，若點和面發(fā)生碰撞，則點在△內(nèi)部，即、、、4 點共面（共面條件）；同時碰撞點在△內(nèi)（內(nèi)部條件），如圖3 所示。 判斷碰撞對是否滿足共面條件稱為共面測試，判斷碰撞對是否滿足內(nèi)部條件的稱為內(nèi)部測試。

圖3 點面對發(fā)生碰撞時的位置關(guān)系Fig.3 Position of VF－pair when they collide

低層剔除使用的有代表三角形、孤集和濾波器等方法。

本文的低層剔除采用兩個濾波器：非穿透性濾波器（DNF）和本文提出的空間線性投影濾波器（SLPF）。 由于碰撞對確定碰撞需要滿足兩個條件：共面條件和內(nèi)部條件。 DNF 可以剔除不滿足共面條件的碰撞對，而本文提出的SLPF 可以剔除部分不滿足內(nèi)部條件的碰撞對，因此綜合使用這兩個濾波器，可以剔除大量不滿足碰撞條件的碰撞對，得到效果較好的低層剔除。 在多個模型上實驗證明，結(jié)合使用DNF 和SLPF 的方法比僅使用DNF 方法剔除數(shù)量更多。

2 空間線性投影濾波器

空間線性投影濾波器（SLPF）是將碰撞對投影到空間中的直線上，根據(jù)直線上投影點的位置關(guān)系，直觀簡單地判斷碰撞對原來的位置關(guān)系，可以剔除大部分不滿足內(nèi)部條件的碰撞對。

2.1 符號說明

、和V分別表示點在0，1，以及任意∈［0，1］的情況。

，，，表示點面對（） 的運動點和三角形的3 個頂點，，，，表示邊邊對（） 的兩條邊，的4 個頂點。

、·和*分別表示向量叉乘、點乘以及普通乘法。

黑斜體表示向量，例如：，，。

2.2 空間線性投影濾波器的理論介紹

SLPF 是將空間中的碰撞對投影到空間中的某條直線上，根據(jù)投影點的位置關(guān)系來剔除不可能發(fā)生碰撞的碰撞對。 在點面碰撞中，若點的投影點始終在三角形3 個頂點的投影點的同一側(cè)，則可剔除；在邊邊碰撞中，若一條邊的兩個頂點的投影點始終在另一條邊的兩個頂點的投影點的同一側(cè)，則可剔除。

在任意時間間隔內(nèi)，對于特定的投影空間，如果兩個變形基元在投影空間中沒有相交，則這兩個基元在其原空間中也不會相交。

假設(shè)在原本的空間中兩個變形基元相交，那么在投影空間中這兩個基元也一定相交，與兩個基元在投影空間不相交矛盾，故假設(shè)不成立，定理1 成立。

下面分點面對（VF－pair）和邊邊對（EE－pair）兩種情況分別說明SLPF 的原理。

（1）點面對：將VF－pair 的4 個點，，，投影到某條直線上，記為，，，。 由定理1 可知，若整個時間間隔內(nèi)沒有相交，那么必定存在一條直線，有始終在、、的左邊（或右邊），則這一對點面一定不發(fā)生碰撞，反之則不一定發(fā)生碰撞。點面對在方向向量為（1，0，0） 即軸上的投影情況，如圖4（a）所示。

（2）邊邊對：將EE－pair 的4 個點，，，投影到某條直線上，記為，，，。 由定理1 可知，若整個時間間隔內(nèi)沒有相交，那么必定存在一條直線，有、始終在、的左邊（或右邊），則這一對邊邊一定不發(fā)生碰撞，反之則不一定發(fā)生碰撞。邊邊對在方向向量為（1，0，0） 即軸上的投影情況，如圖4（b）所示。

圖4 碰撞對在X 軸上投影Fig.4 The projection of VF－pair and EE－pair onto the X－axis

2.3 空間線性投影濾波器計算推導(dǎo)

為將位置關(guān)系轉(zhuǎn)換為能夠用程序計算的公式，下面進(jìn)行計算推導(dǎo)。

記投影向量的單位向量為，以點和為例。 如果的投影點一直在的投影點的右側(cè)，則有線段構(gòu)成的向量在以為單位向量的直線上的投影為與的點乘大于0，即·0一直成立，如果的投影點一直在的投影點的左側(cè)，則·0 一直成立。

在連續(xù)碰撞檢測中，有任意一點V ＝V*（1）*，因此有：

其中，0、0 表示點、在0 時刻的坐標(biāo)，點1、1 表示點、在1 時刻的坐標(biāo)，∈［0，1］。因此，在VF － pair 中只要滿足式（1） 中1，2，3，4，5，6 同號，那么此時間間隔內(nèi)不發(fā)生碰撞。

其中，0，0，0，0 表示點，，，在0時刻的坐標(biāo)，點1，1，1，1 表示點，，，在1 時刻的坐標(biāo)。

在EE － pair 中只要滿足式（2） 中1，2，3，4，5，6，7，8 同號，那么此時間間隔內(nèi)不發(fā)生碰撞。

其中，0，0，0，0 表示點，，，在0時刻的坐標(biāo)，點1，1，1，1 表示點，，，在1 時刻的坐標(biāo)。

3 結(jié)果與討論

本文實驗環(huán)境為Intel Core i7－8565U CPU＠1.80 GHz 2.00 GHz，編譯環(huán)境為VS2017，代碼編寫采用C＋＋，測試數(shù)據(jù)為funnel 和cloth＿ball 數(shù)據(jù)模型，數(shù)據(jù)來自北卡羅來納大學(xué)教堂山分校（University of North Carolina at Chapel Hill，UNC）。funnel：9 450 個點，18 484 個三角面；cloth＿ball：46 598個點，92 230個三角面，渲染圖如圖5 所示。

圖5 數(shù)據(jù)集渲染圖Fig.5 Rendering image of dataset

3.1 確定k 值

對比不同包圍盒的優(yōu)劣，本文最終選擇kDOPs包圍盒。 為了確定適合的值，本文對為6、8、14、18、26 分別進(jìn)行測試，對比不同值在funnel 和cloth＿ball 數(shù)據(jù)上一幀的剔除數(shù)量與時間，結(jié)果如圖6所示。在funnel 上，為26 時無論是邊邊對還是點面對的剔除率都是最高的，且花費時間最短；在cloth＿ball上，為26 時無論是點面對還是邊邊對的剔除率都是最高的，時間稍稍長于為14 和18 時。 綜合考慮花費時間與剔除數(shù)量后，本文采用26－DOPs。

圖6 k 值測試結(jié)果Fig.6 Results of the k－value test

3.2 濾波器實驗

空間線性投影濾波器（SLPF）對基本測試中不滿足內(nèi)部條件的碰撞對進(jìn)行快速剔除，為提高剔除率，又增加一個非穿透性濾波器（DNF）來進(jìn)行非共面剔除。 分別在cloth＿ball 和funnel 上進(jìn)行實驗，經(jīng)過26－DOPs 剔除后，對比僅使用SLPF、僅使用DNF以及使用SLPF＋DNF 進(jìn)行剔除的效果，結(jié)果見表1和表2，其中時間為每幀時間。 可以看出，僅使用SLPF 比僅使用DNF 的剔除數(shù)量更多，使用SLPF＋DNF 的剔除數(shù)量最多。 由于SLPF＋DNF 路徑是在SLPF 為真的情況下再進(jìn)入DNF 判定，增加了計算，所以時間花費比只經(jīng)過一層濾波器稍多。 而對于SLPF 或者DNF，不同的碰撞位置需要計算的不等式數(shù)量不同，而具體哪個濾波器需要計算的不等式數(shù)量更多無從判定，因此有時SLPF 花費的時間多，有時DNF 花費的時間多。

表1 cloth＿ball 上的測試結(jié)果Tab.1 Test results on cloth＿ball dataset

表2 funnel 上的測試結(jié)果Tab.2 Test results on funnel dataset

4 結(jié)束語

本文對連續(xù)碰撞檢測算法進(jìn)行研究，采用兩級碰撞檢測算法作為框架。 高層剔除階段在分析各種包圍盒優(yōu)劣后，決定選擇k－DOPs 作為包圍盒層次結(jié)構(gòu)的包圍盒，經(jīng)過實驗確定值為26。 由于一對碰撞對需要滿足共面條件和內(nèi)部條件才能確定是發(fā)生碰撞，而已經(jīng)存在的DNF 只能剔除不滿足共面條件的碰撞對，于是在低層剔除階段，提出一個可以剔除不滿足內(nèi)部條件的碰撞對的空間線性投影濾波器（SLPF），結(jié)合使用非穿透性濾波器（DNF），可以顯著提高剔除效率。 最后，在兩個數(shù)據(jù)集上進(jìn)行實驗，驗證了這一理論。 實驗結(jié)果表明，僅使用SLPF 比僅使用DNF 的剔除數(shù)量更多，使用SLPF＋DNF 的剔除數(shù)量最多。

本文算法在剔除數(shù)量上具有一定優(yōu)勢，但是在時間花費上并不占據(jù)絕對優(yōu)勢，還有改進(jìn)的空間，比如：簡化計算步驟。 除此之外，本文算法是基于CPU 實現(xiàn)的，后續(xù)可以考慮基于GPU 的并行策略來進(jìn)一步減少使用時間。