萬(wàn) 燕， 符亞玲， 姚 礪

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

0 引 言

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

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

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

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

1 研究方法

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

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

1.1 高層剔除

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

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

圖2 簡(jiǎn)單場(chǎng)景二叉BVH 樹Fig.2 Simple example of BVH

1.2 低層剔除

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

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

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

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

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

2 空間線性投影濾波器

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

2.1 符號(hào)說明

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

，，，表示點(diǎn)面對(duì)（） 的運(yùn)動(dòng)點(diǎn)和三角形的3 個(gè)頂點(diǎn)，，，，表示邊邊對(duì)（） 的兩條邊，的4 個(gè)頂點(diǎn)。

、·和*分別表示向量叉乘、點(diǎn)乘以及普通乘法。

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

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

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

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

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

下面分點(diǎn)面對(duì)（VF－pair）和邊邊對(duì)（EE－pair）兩種情況分別說明SLPF 的原理。

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)果與討論

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

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

3.1 確定k 值

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

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

3.2 濾波器實(shí)驗(yàn)

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

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

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

4 結(jié)束語(yǔ)

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

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