馮立穎

摘 要： 碰撞檢測(cè)在圖形學(xué)、仿真、動(dòng)畫(huà)和虛擬現(xiàn)實(shí)等技術(shù)中得到廣泛的研究，這些研究具有十分重要的意義。文章對(duì)二維空間中多邊形等面模型間相交，以及三維空間中多面體等體模型間干涉的角度對(duì)碰撞檢測(cè)技術(shù)的研究和發(fā)展作了較為全面的論述，并對(duì)幾種常用的碰撞檢測(cè)算法進(jìn)行了分析和比較，最后對(duì)碰撞檢測(cè)算法的發(fā)展方向提出了幾點(diǎn)建議。

關(guān)鍵詞： 虛擬現(xiàn)實(shí)； 碰撞檢測(cè)； 層次包圍盒； 干涉

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-8228（2014）08-07-04

A survey on collision detection technology

Feng Liying

（Information Technology Office of YanShan University， Qinhuangdao， Hebei 066004， China）

Abstract： The collision detection problem among objects is widely studied in graphics， simulation， animation and virtual reality technologies. A comprehensive introduction of study and development of the problem is given from the aspects of the intersection between face models in 2D， such as polygon， and the interference between body models in 3D， such as polyhedron. Some collision detection algorithms are briefly analyzed and compared. Some suggestions of development of collision detection algorithms are proposed.

Key words： virtual reality； collision detection； bounding volume hierarchies； interference

0 引言

數(shù)字化、信息化是當(dāng)今國(guó)內(nèi)外高科技發(fā)展的潮流和趨勢(shì)，隨著計(jì)算機(jī)軟硬件技術(shù)的快速發(fā)展，尤其是圖形處理器以及與之相關(guān)的三維游戲，虛擬仿真等技術(shù)的興起，碰撞檢測(cè)技術(shù)再次成為計(jì)算機(jī)仿真領(lǐng)域研究的熱點(diǎn)之一。在虛擬仿真系統(tǒng)中，如果物體間發(fā)生碰撞，系統(tǒng)必須實(shí)時(shí)而準(zhǔn)確地檢測(cè)到這些碰撞并作出相應(yīng)的碰撞響應(yīng)[1]，否則物體間就會(huì)產(chǎn)生穿透現(xiàn)象，影響虛擬場(chǎng)景的真實(shí)性。以前在自動(dòng)裝配規(guī)劃以及路徑規(guī)劃等領(lǐng)域中，為了檢測(cè)場(chǎng)景中的物體之間或零件之間是否發(fā)生碰撞，產(chǎn)生了許多碰撞檢測(cè)算法，而后有關(guān)專家在碰撞檢測(cè)的理論和應(yīng)用方面做了一系列的實(shí)驗(yàn)，并得到了許多有重要價(jià)值的研究結(jié)果。

近二三十年來(lái)，國(guó)內(nèi)外研究人員在碰撞檢測(cè)領(lǐng)域中做了大量有意義的工作，經(jīng)過(guò)細(xì)致的研究和實(shí)驗(yàn)驗(yàn)證之后，得到了許多實(shí)用的碰撞檢測(cè)算法，對(duì)虛擬現(xiàn)實(shí)技術(shù)的快速發(fā)展起到了積極的推動(dòng)作用。本文將從二維平面和三維空間兩個(gè)方面對(duì)碰撞檢測(cè)技術(shù)進(jìn)行較為詳盡的論述。

1 二維空間碰撞檢測(cè)問(wèn)題

二維空間中的碰撞檢測(cè)幾乎是所有碰撞檢測(cè)算法不可回避的問(wèn)題，它是指三角形、多邊形等面模型之間的求交問(wèn)題，是三維空間中精確碰撞檢測(cè)的必經(jīng)階段[2]。近幾十年來(lái)，許多專家學(xué)者對(duì)平面碰撞問(wèn)題進(jìn)行了深入的研究，并取得一些滿意的結(jié)果，提出了許多優(yōu)秀的算法。

Chin和Wang兩人研究了兩個(gè)多邊形的相交和最小距離問(wèn)題。利用可視邊鏈和凸的頂點(diǎn)相對(duì)于其內(nèi)部點(diǎn)的單調(diào)性，提出了判別凸n邊形和一個(gè)簡(jiǎn)單非凸m邊形的相交問(wèn)題的最優(yōu)算法[3]，并且研究了當(dāng)兩個(gè)多邊形相交時(shí)，一個(gè)多邊形是否被另一個(gè)多邊形完全包含的問(wèn)題，其時(shí)間復(fù)雜度都為O（m+n）。

曲吉林采用平面掃描算法，解決了平面內(nèi)任意簡(jiǎn)單多邊形平移時(shí)碰撞部位的判定問(wèn)題[4]。平面內(nèi)任意兩個(gè)互不相交的簡(jiǎn)單多邊形，若其中一個(gè)多邊形沿某一方向平移時(shí)與另一個(gè)多邊形碰撞，采用平面掃描法，通過(guò)提取多邊形的單調(diào)鏈，給出了求其碰撞部位的算法。與現(xiàn)有的算法相比，降低了時(shí)間復(fù)雜性。

覃中平、張煥國(guó)研究了平面內(nèi)兩個(gè)互不相交的凸多邊形，若其中一個(gè)凸多邊形沿某一方向與另一個(gè)凸多邊形相碰撞，采用折半搜索技術(shù)來(lái)確定凸多邊形相碰撞時(shí)兩者最初相碰撞的頂點(diǎn)和邊[5]，并且提出了時(shí)間復(fù)雜度為O（logm+logn）的優(yōu)秀算法。

汪嘉業(yè)利用單調(diào)折線研究了在一個(gè)多邊形的凸包和另一個(gè)多邊形不相交的條件下，確定兩個(gè)多邊形是否碰撞，并在碰撞時(shí)確定全部碰撞部位的問(wèn)題[6]，提出了時(shí)間復(fù)雜度為O（m+n）的最優(yōu)算法，并且其算法還可推廣到確定包含有圓弧邊的多邊形之間的最初碰撞部位。

申靜波，唐國(guó)維等人提出了基于夾邊邊對(duì)的空間平面凸多邊形快速相交檢測(cè)算法[7]，并將算法的應(yīng)用對(duì)象從三角形擴(kuò)展到任意空間平面凸多邊形，直接進(jìn)行多邊形間求交計(jì)算。該算法在確定所要檢測(cè)的兩個(gè)凸多邊形是否都存在相對(duì)于另一凸多邊形所在平面的夾邊邊對(duì)的基礎(chǔ)上，根據(jù)計(jì)算結(jié)果求取兩組邊對(duì)間對(duì)應(yīng)夾邊的符號(hào)距離，以此判斷兩個(gè)多邊形是否相交。

2 三維空間中碰撞檢測(cè)問(wèn)題

從空間域的角度來(lái)劃分，碰撞檢測(cè)算法大體可分為兩大類：一類是基于圖象空間的碰撞檢測(cè)算法；另一類是基于物體空間的碰撞檢測(cè)算法。這兩類算法的區(qū)別在于，前者是利用物體二維投影的圖象加上深度信息來(lái)進(jìn)行相交分析，后者則是利用物體三維幾何特性進(jìn)行求交計(jì)算。

2.1 基于圖像空間的碰撞檢測(cè)算法

基于圖象空間的碰撞檢測(cè)算法的基本思想是利用圖形硬件將三維幾何對(duì)象投影到二維圖像平面，同時(shí)利用深度緩存進(jìn)行深度測(cè)試，以判斷對(duì)象之間是否發(fā)生碰撞。但是基于圖象空間的碰撞檢測(cè)算法由于其檢測(cè)結(jié)果的不精確性和依賴硬件支持而一直發(fā)展較慢。近十幾年，隨著圖形硬件技術(shù)的飛速發(fā)展，圖形加速卡在性能不斷迅速提高的同時(shí)甚至出現(xiàn)了可編程的功能。在碰撞檢測(cè)的研究中，人們開(kāi)始將三維幾何物體通過(guò)投影繪制到圖像平面上，得到一個(gè)二維的圖像空間，然后分析該空間中保存在各類緩存的信息，進(jìn)而檢測(cè)出物體之間是否發(fā)生干涉[8]。這類算法優(yōu)勢(shì)在于能有效利用圖形硬件加速技術(shù)來(lái)減輕CPU的計(jì)算負(fù)擔(dān)，從而達(dá)到提高算法效率的目的。

Shinya和Forgue等[9]提出在繪制凸體的同時(shí)，保存視窗口中每個(gè)象素上物體的最大和最小深度序列，并將它們按大小順序排列，然后檢測(cè)物體在某一象素上的最大深度值是否與其最小深度值相鄰來(lái)判別相交情況。雖然圖形硬件可以支持物體最大/最小深度的計(jì)算，但該方法并不實(shí)用，因?yàn)樗蟠罅康膬?nèi)存來(lái)保存深度序列，而且從圖形硬件中讀取深度值本身就非常費(fèi)時(shí)。

Gress等[10]利用GPU的可編程性，將碰撞檢測(cè)計(jì)算映射到GPU的頂點(diǎn)處理器和片段處理器中，通過(guò)實(shí)施繪制完成碰撞檢測(cè)計(jì)算，再通過(guò)遮擋查詢獲得碰撞檢測(cè)結(jié)果。該算法既保證了碰撞檢測(cè)的準(zhǔn)確性，同時(shí)也充分利用了GPU強(qiáng)大的并行計(jì)算能力。

Govindaraju等[11]利用圖形硬件進(jìn)行初步檢測(cè)階段，迅速剔除大規(guī)模場(chǎng)景中明顯不發(fā)生碰撞的物體；然后利用幾何結(jié)構(gòu)下的快速相交檢測(cè)算法得到精確的碰撞檢測(cè)結(jié)果。該算法在處理虛擬場(chǎng)景中多物體間初期碰撞檢測(cè)方面能取得不錯(cuò)的效果。

Heidelberger等[12]利用面向體表示的方法，提出了一種能夠處理可變形物體的碰撞檢測(cè)算法。該算法首先將兩物體的相交區(qū)域按層次深度分解為層次深度圖（layered depth image）；然后通過(guò)圖形硬件繪制過(guò)程來(lái)判斷兩物體在層次深度圖的每個(gè)像素上是否有相交區(qū)間存在，從而確定物體是否發(fā)生碰撞。此算法不適合大規(guī)模物體間的碰撞檢測(cè)。

2.2 基于物體空間的碰撞檢測(cè)算法

三維空間中碰撞檢測(cè)問(wèn)題與二維空間碰撞檢測(cè)問(wèn)題相比要復(fù)雜得多，目前，基于三維空間的碰撞檢測(cè)算法主要分為三類：距離跟蹤法、空間分解法（或空間剖分法）、層次包圍盒法。

2.2.1 距離跟蹤法

距離跟蹤法是通過(guò)尋找和跟蹤兩個(gè)多面體之間的最近點(diǎn)來(lái)計(jì)算它們之間的距離。當(dāng)距離小于等于零時(shí)，發(fā)生碰撞；否則沒(méi)有發(fā)生碰撞。當(dāng)物體的運(yùn)動(dòng)速度不快，相鄰幀間運(yùn)動(dòng)物體的位移變化很小時(shí)，可以利用幀間的連續(xù)性來(lái)增量式的計(jì)算物體間的距離。

最早出現(xiàn)的跟蹤算法是Lin-Canny算法[13]，它從上次得到的最近特征對(duì)開(kāi)始，沿多面體的表面移動(dòng)，直到找到新的最近特征。顯然，這種算法依賴于相鄰兩次最近特征的距離，即模型的相干性。如果相干性越高，那么算法的效率越高；相反相干性越低，算法效率就越低。

Enhanced GJK算法[14]是在GJK算法上改進(jìn)而成。GJK算法是一個(gè)跟蹤計(jì)算兩凸多面體間的最短距離的算法，與Lin-Canny算法不同的是，GJK不是直接對(duì)兩凸多面體進(jìn)行搜索和跟蹤，而是在他們的明氏距離多面體參數(shù)空間中搜索跟蹤執(zhí)行，它具有線性時(shí)間復(fù)雜度；Enhanced GJK算法將原GJK算法的時(shí)間復(fù)雜度改進(jìn)為近乎常量級(jí)，達(dá)到與Lin-Canny算法的同等水平。Enhanced GJK采用了“爬山法”迭代算法求解，使時(shí)間復(fù)雜度大大降低，基本呈線性，大大減少了運(yùn)算時(shí)間。

2.2.2 空間剖分法

空間剖分法是將整個(gè)虛擬空間劃分成相等體積的小單元格，只對(duì)占據(jù)同一單元格或相鄰單元格的幾何對(duì)象進(jìn)行相交測(cè)試。適用于物體在空間中均勻分布的稀疏環(huán)境。

Ganter和Isarankura發(fā)展了單步檢測(cè)方法，提出了一種空間分割技術(shù)的方法[15]，這種空間分割技術(shù)將包含物體的空間劃分為一個(gè)個(gè)子空間，將所有的測(cè)試限制在兩個(gè)物體的重疊局部區(qū)域來(lái)進(jìn)行，并且在重疊區(qū)域內(nèi)的所有的子空間都按照最小、最大值來(lái)排序，從而進(jìn)一步減少測(cè)試的時(shí)間。

Fuch和Kedem提出二叉空間分割BSP（Binary Space Partition）即空間任何一個(gè)平面，都可以將它所在的空間分割為兩個(gè)互不相交的子空間，空間中其他平面均可劃歸在某一子空間中。同樣，某一子空間中任一平面可以將該空間分為另外兩個(gè)互不相交的子空間。如此遞歸分割，將每次分割平面加入二叉樹(shù)節(jié)點(diǎn)，即可形成一棵描述場(chǎng)景層次結(jié)構(gòu)的BSP樹(shù)。BSP樹(shù)碰撞檢測(cè)算法是在虛擬場(chǎng)景中的兩個(gè)對(duì)象間找出分割平面以判斷兩個(gè)對(duì)象是否相交。若兩個(gè)對(duì)象間存在分割平面，則沒(méi)有發(fā)生碰撞；否者，發(fā)生了碰撞。

2.2.3 層次包圍盒法

層次包圍盒算法是利用體積略大而幾何特性簡(jiǎn)單的包圍盒來(lái)近似地描述相對(duì)復(fù)雜的虛擬對(duì)象，進(jìn)而通過(guò)構(gòu)造樹(shù)狀層次結(jié)構(gòu)可以越來(lái)越逼近對(duì)象的幾何模型，直到幾乎完全獲得對(duì)象的幾何特性，從而只需對(duì)包圍盒重疊的部分進(jìn)行進(jìn)一步的相交測(cè)試。與一個(gè)物體相對(duì)應(yīng)的層次結(jié)構(gòu)的節(jié)點(diǎn)是空間上包圍該物體一部分幾何對(duì)象的幾何近似體（包圍盒）：層次結(jié)構(gòu)的根節(jié)點(diǎn)包圍了整個(gè)物體，每個(gè)父節(jié)點(diǎn)包圍的幾何對(duì)象是它的所有子節(jié)點(diǎn)包圍的幾何對(duì)象之和，節(jié)點(diǎn)從上到下逐漸逼近它包圍的幾何對(duì)象。利用層次包圍盒方法進(jìn)行碰撞檢測(cè)時(shí)，首先測(cè)試幾何對(duì)象的包圍盒是否相交，如果包圍盒不相交，則被包圍的對(duì)象就不相交；只有包圍盒相交時(shí)，才對(duì)其所包裹的幾何對(duì)象做進(jìn)一步相交測(cè)試。

目前，比較典型的包圍盒類型有包圍球（Sphere）、軸向包圍盒AABB（Axis-Aligned Bounding Box）、方向包圍盒OBB（Oriented Bounding Box）以及離散有向多面體k-DOPs（Discrete Orientation Polytopes）等。

包圍球（Sphere）[16]是簡(jiǎn)單性好緊密性差的一類包圍盒，一個(gè)給定對(duì)象的包圍球被定義為包含該對(duì)象的最小的球體。計(jì)算給定對(duì)象的包圍球，首先需分別計(jì)算對(duì)象的基本幾何元素集合中所有元素的頂點(diǎn)的x、y、z坐標(biāo)均值以確定包圍球的球心c，再由球心與三個(gè)最大值坐標(biāo)所確定的點(diǎn)與點(diǎn)之間的距離計(jì)算半徑r。包圍球確定的區(qū)域?yàn)椋篟={（x，y，z）T|（x-cx）2+（y-cy）2+（z-cz）2

軸向包圍盒AABB（axis-aligned bounding box）[17]是最早的一類包圍盒，在碰撞檢測(cè)的研究歷史中使用得最廣，一個(gè)物體的AABB被定義為包含該對(duì)象且邊平行于坐標(biāo)軸的最小正六面體。對(duì)于給定的對(duì)象，它的AABB僅需六個(gè)標(biāo)量描述，即組成物體基本幾何元素的頂點(diǎn)的x坐標(biāo)、y坐標(biāo)以及z坐標(biāo)的最大值和最小值。AABB間的重疊測(cè)試比較簡(jiǎn)單，兩個(gè)AABB重疊當(dāng)且僅當(dāng)它們?cè)谌齻€(gè)坐標(biāo)軸上的投影區(qū)間均重疊，則它們是相交的。

OBB包圍盒層次（Oriented Bounding Box）是緊密型好、相交測(cè)試復(fù)雜的一類包圍盒[18]。一個(gè)給定對(duì)象的OBB被定義為包含該對(duì)象且相對(duì)于坐標(biāo)軸方向任意的最小的正六面體。OBB最大特點(diǎn)是它的方向的任意性，這使得它可以根據(jù)被包圍對(duì)象的形狀特點(diǎn)盡可能緊密地包圍對(duì)象，但同時(shí)也使得它的相交測(cè)試變得復(fù)雜。OBB間的相交測(cè)試基于分離軸理論，若兩個(gè)OBB在一條軸線上（不一定是坐標(biāo)軸）上的投影不重疊，則這條軸稱為分離軸，若一對(duì)OBB間存在一條分離軸，則可以判定這兩個(gè)OBB不相交，否則它們是相交的。

離散有向多面體k-DOPs（Discrete Orientation Polytopes）[19]是由紐約州立大學(xué)的James T、Klosowski等人提出的。一個(gè)對(duì)象的k-DOPs被定義為包含該對(duì)象且它的所有面的法向量都來(lái)自一個(gè)固定方向（k個(gè)向量）的集合的凸包，其中的方向向量為共線且方向相反的向量對(duì)。一個(gè)幾何對(duì)象的k-DOPs可以通過(guò)計(jì)算對(duì)象的頂點(diǎn)與固定方向集D中的各個(gè)方向的最大點(diǎn)積得到。D中有k/2對(duì)方向相反的向量對(duì)，k-DOPs在每對(duì)向量上的最大延伸確定了它在該對(duì)向量上的投影區(qū)間，一個(gè)k-DOPs包圍盒完全可由描述它在這些向量對(duì)上的k/2個(gè)投影區(qū)間所確定。因此，k-DOPs包圍盒間的相交測(cè)試可以通過(guò)投影區(qū)間的重疊測(cè)試來(lái)完成，只要兩個(gè)k-DOPs包圍盒在D中某一個(gè)方向?qū)ι系耐队皡^(qū)間不重疊，就可以判定它們是不相交的；否則認(rèn)為它們是相交的。

2.2.4 基于物體空間的碰撞檢測(cè)算法的分析比較

目前，在物體空間的碰撞檢測(cè)的算法中，距離跟蹤法依賴于相鄰兩次最近特征的距離，即模型的相干性。如果相干性越高，那么算法的效率越高；相反，相干性越低，算法效率就越低。這就使得算法具有了不穩(wěn)定性，其健壯性也受到影響。空間剖分法由于只適合于物體在空間均勻分布的稀疏環(huán)境，簡(jiǎn)單地從大量物體中排除不相交的物體。但對(duì)于一般的環(huán)境，很難選擇一個(gè)最優(yōu)的剖分尺寸，若選擇不當(dāng)，會(huì)導(dǎo)致空間耗費(fèi)大，計(jì)算效率降低，因此空間剖分法有一定的局限性，是一種較少用到的方法。與上述兩種算法相比，層次包圍盒法是碰撞檢測(cè)算法中一種被廣泛使用的方法，在對(duì)物體進(jìn)行碰撞檢測(cè)時(shí)，首先進(jìn)行包圍盒間的相交測(cè)試，由于包圍盒間的求交過(guò)程比物體間求交過(guò)程簡(jiǎn)單，所以可以盡早地排除大量不相交的物體，節(jié)省碰撞檢測(cè)的時(shí)間，提高碰撞檢測(cè)的效率。對(duì)研究人員來(lái)說(shuō)，這種方法無(wú)疑是一種較好的選擇。但是，這種方法也有它的缺點(diǎn)，當(dāng)被檢測(cè)的對(duì)象的變得越來(lái)越復(fù)雜時(shí)，構(gòu)建包圍盒樹(shù)會(huì)占用大量存儲(chǔ)空間的同時(shí)，也會(huì)增加參與相交測(cè)試包圍盒的數(shù)量，因此會(huì)耗費(fèi)大量存儲(chǔ)空間和相交測(cè)試的時(shí)間。

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

在虛擬環(huán)境中，碰撞問(wèn)題一直是經(jīng)典而關(guān)鍵的問(wèn)題之一，因而得到很多專家學(xué)者的關(guān)注和研究，他們提出了各種各樣的方法來(lái)提高檢測(cè)算法的效率和魯棒性。作者認(rèn)為在以后研究中可以從以下幾個(gè)方面入手。

⑴ 層次包圍盒法是一種被研究人員廣泛使用的算法，利用該方法對(duì)物體間進(jìn)行相交測(cè)試時(shí)，在大多情況下都會(huì)立即產(chǎn)生無(wú)碰撞結(jié)論。因此節(jié)省包圍盒間相交測(cè)試的次數(shù)和相交測(cè)試的時(shí)間是提高檢測(cè)效率的有效途徑，所以研究者可以采用混合的包圍盒方法，即外層采用緊密性差、相交測(cè)試簡(jiǎn)單的包圍盒，如包圍球，而里層采用緊密性好、相交測(cè)試復(fù)雜的包圍盒，如OBB，在解決實(shí)時(shí)碰撞檢測(cè)問(wèn)題時(shí)不失為一個(gè)有效的方法。

⑵ 基于圖像的碰撞檢測(cè)算法屬于較新的一類算法。但曾經(jīng)由于受到圖形硬件發(fā)展的限制，研究進(jìn)展相對(duì)比較緩慢。隨著圖形硬件的發(fā)展才得以重新進(jìn)入研究者的視野，國(guó)外有一批研究者正在進(jìn)行該方面的研究，包含了碰撞檢測(cè)領(lǐng)域，國(guó)內(nèi)在這方面的研究尚屬起步階段，成果較少。CPU與GPU間的負(fù)載平衡問(wèn)題有待進(jìn)一步研究，以提高算法效率。該類算法由于其本身的優(yōu)勢(shì)，特別是隨著圖形硬件的飛速發(fā)展，具有廣闊的研究前景和研究?jī)r(jià)值。

⑶ 利用多核CPU并行計(jì)算的功能來(lái)提高碰撞檢測(cè)的效率。隨著計(jì)算機(jī)硬件的不斷發(fā)展，雙核，四核，甚至多核CPU應(yīng)運(yùn)而生，通過(guò)把多核CPU并行計(jì)算，以及數(shù)據(jù)分塊思想應(yīng)用到碰撞檢測(cè)算法之中，以靜態(tài)和動(dòng)態(tài)任務(wù)分配策略相結(jié)合的方法來(lái)提高算法的并行度，從而達(dá)到提高碰撞檢測(cè)速度的目的。其核心問(wèn)題是如何找出更好的動(dòng)態(tài)任務(wù)分配策略以完全實(shí)現(xiàn)CPU間負(fù)載均衡，這是今后一個(gè)研究方向。

總之，碰撞檢測(cè)技術(shù)仍有許多方面需要進(jìn)一步探討和研究，包括軟體模型、復(fù)雜模型之間的碰撞、框架與框架之間的空間一致性，以及接觸和干涉之間的區(qū)分等問(wèn)題。因此，需要研究者不斷仔細(xì)鉆研，拓寬思路，設(shè)計(jì)出更高效的算法，才能滿足虛擬場(chǎng)景中大量復(fù)雜物體之間碰撞檢測(cè)實(shí)時(shí)性的要求。

參考文獻(xiàn)：

[1] 何雪薇，龔光紅.虛擬人運(yùn)動(dòng)的動(dòng)力學(xué)實(shí)現(xiàn)方法研究[C]. 2003全國(guó)

系統(tǒng)仿真年會(huì)論文集.西安：中國(guó)系統(tǒng)仿真學(xué)，2003：614-619

[2] 王志強(qiáng)，洪嘉振，楊輝.碰撞檢測(cè)問(wèn)題研究綜述[J].軟件學(xué)報(bào)，1999.10

（5）：545-551

[3] F.Chin， C.A.Wang. Optimal Algorithms for the Intersection and

the Minimum Distance Problems between Planar Polygons. IEEE Transactions on Computers，1993.C-32（12）：1203-1207

[4] 曲吉林.確定任意簡(jiǎn)單多邊形平移時(shí)碰撞部位的掃描算法[J].計(jì)算機(jī)

學(xué)報(bào)，2000.23（7）：692-1698

[5] 覃中平，張煥國(guó).確定凸多邊形平移時(shí)最初碰撞部位的最優(yōu)算法[J].

計(jì)算機(jī)學(xué)報(bào)，1992.15（3）：171-177

[6] 汪嘉業(yè).平面上簡(jiǎn)單多邊形平移時(shí)確定碰撞部位的最優(yōu)算法[J].計(jì)算

機(jī)學(xué)報(bào)，1992.15（8）：582-588

[7] 申靜波，唐國(guó)維，李井輝.基于夾邊邊對(duì)的凸多邊形間快速相交檢測(cè)

算法[J].計(jì)算機(jī)工程與科學(xué)，2007.29（12）：93-94

[8] N.K. Govindaraju， M.C. Lin， D. Manocha. Fast and reliable

collision culling using graphics hardware[J].IEEE Transactions on Visuallization and Computer Graphics，2006.12（2）：143-154

[9] M. Shinya， M. Forgue. Interference Detection through Rasteriza-

tion. Journal of Visua-lization and Computer Animation，1997.2（8）：131-134

[10] A. Gress， G. Zachmann. Object-space interference detection on

programmable graphics hardware[C]. SIAM Conference on Geometric Design and Computing Washington. DC： Nashboro Press，2006：13-17

[11] GOVINDARAJU N K， LINM C， MANOCHA D.Quick-

CULLIDE： fast inter-and intra-object collision culling using graphics hardware[C] //Proc of IEEE Virtual Reality，2005：59-66

[12] HEIDELBERGER B， TESCHNER M， GROSS M.Volumetric

collision detection for derformable objects， TR395[R].Zurich， Switzerland： Computer Science Department ETH，2003.

[13] M. C. Lin， J. F. Canny. A Fast Algorithm for Incremental

Distance Calculation. In Proceedings of the IEEE International Conference on Robotics and Automation， Sacramento， CA，1991：1008-1014

[14] V. Gino， B. Den. A Fast and Robust GJK Implementation for

Collision Detection of Convex Objects. http：//www.win.tue.nl/cs/tt/gino/solid/index.html，1999.8（4）：11-17

[15] M. A. Ganter， B. P. Isarankura. Dynamic Collision Detection

Using Space Partitioning. Journal of Mechanical Design， Transactions of the ASME，1993.115（1）：150-155

[16] I. J. Palmer， R. L. Grimsdale. Collision Detection for Animation

Using Sphere-Trees. Computer Graphics Forum，1995.14（2）：105-116

[17] 馬登武，葉文，李瑛.基于包圍盒的碰撞檢測(cè)算法綜述[J].系統(tǒng)仿真學(xué)

報(bào)，2006.18（4）：1058-1061

[18] S. Gottschalk， M. C. Lin， D. Manocha. OBB-Tree： A

Hierarchical Structure for Rapid Interference Detection. In Proc. the ACM of SIGGRAPH'96，1996：171-180

[19] J. T. Klosowski， M. Held， J. S. B. Mitchell， et al. Efficient

Collision Detection Using Bounding Volume Hierarchies of k-DOPs. IEEE Transactions on Visualization and Computer Graphics，1998.4（1）：21-36

[20] YU Chun-yan， YE Dong-yi， WU Ming-hui， et al. A new

horizonal collision detection scheme for avatar with avatar in collaborative virtual environment[C] //Proc of the 4th International Conference on Machine Learning and Cybernetics，2005：4961-4966

[21] 鄒益勝，丁國(guó)富，許明恒.實(shí)時(shí)碰撞檢測(cè)算法綜述[J].計(jì)算機(jī)應(yīng)用研

究，2008.5（1）：8-11