基于空間線性投影的連續碰撞檢測算法

萬 燕， 符亞玲， 姚 礪

（東華大學 計算機科學與技術學院， 上海 201620）

0 引 言

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

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

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

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

1 研究方法

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

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

1.1 高層剔除

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

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

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

1.2 低層剔除

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

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

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

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

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

2 空間線性投影濾波器

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

2.1 符號說明

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

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

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

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

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

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

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

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

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

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

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

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

2.3 空間線性投影濾波器計算推導

為將位置關系轉換為能夠用程序計算的公式，下面進行計算推導。

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

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

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

其中，0，0，0，0 表示點，，，在0時刻的坐標，點1，1，1，1 表示點，，，在1 時刻的坐標。

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

其中，0，0，0，0 表示點，，，在0時刻的坐標，點1，1，1，1 表示點，，，在1 時刻的坐標。

3 結果與討論

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

圖5 數據集渲染圖Fig.5 Rendering image of dataset

3.1 確定k 值

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

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

3.2 濾波器實驗

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

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

表2 funnel 上的測試結果Tab.2 Test results on funnel dataset

4 結束語

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

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