基于著色算法的并行碰撞檢測算法
2009-01-01 00:00:00趙偉譚睿璞楊秋娜丁文保李文輝
計算機應用研究 2009年5期
（1.吉林大學 計算機科學與技術(shù)學院 長春 130012； 2.長春工業(yè)大學 計算機科學與工程學
院 長春 130012; 3.西北工業(yè)大學 軟件與微電子學院 西安 710072)
摘 要：提出了一種基于著色算法的并行碰撞檢測算法，利用AABB包圍盒較好的緊密性和包圍球計算簡單的優(yōu)點以及并行算法中的分治策略構(gòu)建物體的混合包圍體層次(SAABB)；然后采用破對稱技術(shù)中的典型算法——著色算法，將每棵任務(wù)樹編碼，以產(chǎn)生各不相同的類別，并將不同的類別指派到不同的并行機，在并行機上采用多線程技術(shù)執(zhí)行相同的類別的任務(wù)樹的遍歷，來檢測是否有碰撞發(fā)生。實驗結(jié)果表明，與現(xiàn)有的經(jīng)典的ICOLLIDE等算法相比，該算法在效率、精確性方面具有明顯優(yōu)勢，能夠滿足交互式復雜虛擬環(huán)境的實時性和精確性的要求。
關(guān)鍵詞：碰撞檢測； 混合包圍體層次； 并行技術(shù)； 破對稱； 著色算法
中圖分類號：TP301.6文獻標志碼：A
文章編號：1001-3695(2009)05-1695-05
Parallel collision detection algorithm based on coloring algorithm
ZHAO Wei1，2 TAN Ruipu2 YANG Qiuna3 DING Wenbao2 LI Wenhui1
(1.College of Computer Science Technology Jilin University Changchun 130012 China; 2.School of Computer Science Engineering Changchun University of Technology Changchun 130012 China; 3.Software Microelectronics Institute Northwestern Polytechnical University Xi’an 710072 China)
Abstract:This paper presented a new parallel collision detection algorithm based on coloring algorithm. At first incorporated the merits of both AABB bounding box and bounding spheres to construct a hybrid bounding representation of arbitrary nonconvex polyhedra (SAABB) for attaining speed balanced especially the SAABB using divideandconquer technologies which were mostly primary technologies in parallel algorithm. Then applied symmetry breakingkcoloring technology which was also important in parallel algorithm in order to reduce different categories and assign them to different processors; also multithread was used in multiprocessor computer. At last experiments results show that the algorithm is advantageous over other current typical collision detection such as ICOLLIDE regarding efficiency and accuracy so can meets the realtime and accurate requirements in complex interactive virtual environment.
Key words：collision detection; mixed BVH; parallel technology; symmetry breaking; coloring algorithm
0 引言
碰撞檢測在計算機圖形學、虛擬現(xiàn)實、計算機游戲、動畫、計算機輔助設(shè)計、機器人及虛擬制造等領(lǐng)域中均是經(jīng)典而關(guān)鍵的問題[1]，多年來一直受到較多的關(guān)注。目前，大多數(shù)虛擬對象的幾何模型都是由成千上萬個基本幾何元素組成。由于虛擬環(huán)境的幾何復雜性的增加，使得碰撞檢測的計算復雜性大大提高，復雜場景的交互消耗大量的計算機資源，碰撞檢測往往成為虛擬環(huán)境中的一個瓶頸。
近年來研究人員對碰撞檢測進行了廣泛而深入的研究，提出了大量高效的新算法。大體上可分為兩類，即空間分解法和層次包圍盒方法[2]。尤其是層次包圍盒(hierarchical bounding volumes)，已經(jīng)作為公認的比較好的碰撞檢測手段被廣泛應用，包圍盒的基本思想是使用簡單的幾何體來代替復雜的幾何體，先對物體的包圍盒進行粗略檢測，包圍盒相交時其包圍的幾何體才有可能相交，這樣可以排除大量不可能相交的幾何體。主要包圍盒有：沿坐標軸的包圍盒(AABB)、包圍球(sphere)、沿任意方向包圍盒OBB等，每種包圍盒都有其優(yōu)缺點。本文針對包圍盒的特點，提出了一種結(jié)合包圍球和AABB包圍盒優(yōu)點的混合包圍體層次(SAABB)的新算法，加速了碰撞檢測的過程。
隨著并行機的高速發(fā)展，并行技術(shù)給研究者帶來了前所未有的機遇和挑戰(zhàn)。并行碰撞檢測在計算幾何和機器人控制等領(lǐng)域得到了廣泛的應用[3]。文獻[3]提出了同等大小體素構(gòu)成模型的并行處理算法，但對于過于簡單或是結(jié)構(gòu)復雜的模型較難處理。文獻[4]提出了基于凸多面體剖分的并行碰撞檢測算法，但其實驗模型為凸體有一定的局限性。文獻[5]提出了一種基于MPI的并行碰撞檢測算法，雖然算法效率得到了一定的提高，但是物體的八叉樹表示相當費時，算法進程間通信需要花費一定的時間。文獻[6]提出了一種基于流水線的并行碰撞檢測算法，雖然算法效率有很大提高，但任務(wù)進程數(shù) 對算法性能有很大影響，難以找到最佳值。
與以上方法不同，本文提出了一種新的基于著色算法的并行碰撞檢測算法。采用分治策略為每個任意形狀的物體建立混合包圍盒層次(SAABB)；然后并行遍歷包圍盒樹，這樣極大提高碰撞檢測速度，并具有通用性能可以在單處理機和多處理機上運行。
1 理論基礎(chǔ)
1.1 基本碰撞檢測算法
碰撞檢測算法歸根到底都要進行基本集合元素的相交檢測，而基本幾何元素大多由三角形構(gòu)成，因此高效的三角形和三角形相交檢測對于提高碰撞檢測算法的整體效率至關(guān)重要。
文獻[7]提出了矢量判別法和標量判別法兩種三角形和三角形相交檢測算法，并通過實驗證明了矢量判別法比標量判別法快7%。本文以此算法設(shè)計了基本碰撞檢測算法，它主要用于在包圍盒粗判以后精確判別包圍盒中的物體是否相交。
1.2 混合包圍盒層次
在粗略相交檢測階段，本文采用了包圍球和包圍盒樹來加速算法。包圍球具有簡單，且旋轉(zhuǎn)平移后易于更新的特點；缺點是緊密性差，需要檢測相交的包圍盒對數(shù)多，而AABB包圍盒與包圍球相比，它對物體包裹更加緊密，構(gòu)造和相交測試較簡單。因此，筆者利用AABB包圍盒和包圍球各自的優(yōu)點提出了混合包圍體層次(SAABB)，本文采用SAABB混合層次包圍體樹進行粗略階段的相交檢測。
1.3 混合模型中不同類型包圍盒的相交檢測
設(shè)AABB包圍盒內(nèi)點的坐標為（x，y，z)，包圍盒的邊長為H 包圍盒的中心坐標為(Xs，Ys，Zs)，假設(shè)中心點位于坐標原點，則AABB包圍盒的約束方程為
{(x，y，z)｜0＜x，y，z＜H}（1）
同樣，設(shè)包圍球內(nèi)點的坐標為(x，y，z)，包圍球的半徑為Rs，球心坐標為(X0，Y0，Z0)，則包圍球的約束方程為
{(x，y，z)｜(x-X0)2+(y-Y0)2+(z-Z0)2＜R2s}（2）
假設(shè)AABB包圍盒位于坐標原點（0，0，0），令φ=tg-1(Y0/X0)。其中X0不為零，則AABB包圍盒與包圍球之間的距離為
dist=X20+Y20+Z20-(Rs+H)×φ（3）
設(shè)AABB包圍盒與包圍球中心點的連線與Z坐標軸的夾角為θ，則有：當Y0＞0且X0＞0時，θ=φ；當Y0＞0且X0＜0時，θ=π-φ ；當Y0＜0且X0＞0時，θ=-φ；當Y0＜0且X0＜0時，θ=π+φ。因此，僅需比較θ×dist和｜Z0｜即可得到兩包圍盒的相交情況；若θ×dist＜｜Z0｜，則AABB包圍盒與包圍球相交；否則不相交。
1.4 并行技術(shù)
1.4.1 平衡樹[6，8]
對于二叉樹而言，稱一棵包圍盒樹為完全的，當且僅當包圍盒樹中的每一個葉節(jié)點對應于S的一個單元素子集，即只包含一個基本幾何元素時。由以上描述可知，包圍盒樹最多有2n-1個節(jié)點。其中有n個葉節(jié)點且要求兩子包圍盒內(nèi)的多邊形個數(shù)大致相等；一棵完全的包圍盒樹的高度至少為 log 5n，此時稱為樹是平衡的。
1.4.2 分治策略[6，8]
并行程序設(shè)計中最基本的一種技術(shù)即是分治策略。分治策略的特點是將一個問題分為與原來的較大問題有相同形式的子問題，進一步分為較小的問題通常是通過遞歸方法，直到無須再分解為止。接著就完成這些簡單的任務(wù)并將結(jié)果合并，然后按更大的任務(wù)繼續(xù)合并，直到獲得最后的結(jié)果。當每次分割產(chǎn)生兩部分時，遞歸分治模型就會形成一棵二叉樹；分治策略也可應用于將一個任務(wù)在每一步分為M(M＞2)個部分的情況，則稱為M路分治，通常有二叉樹(M=2)和四叉樹(M=4)。
1.4.3 破對稱技術(shù)[9~11]
本文的并行算法是借鑒破對稱技術(shù)中的著色算法的思想而提出的，在此先作簡要的介紹。
破對稱（symmetry breaking），就是打破某些問題的對稱性，該技術(shù)常用在圖論問題和隨機算法的設(shè)計上。著色算法就是采用該技術(shù)的基本思想來實現(xiàn)的。
令G=(V，E)是一有向環(huán)（即每個頂點的入度和出度均為1），且對于任意兩個頂點u，v∈V，必存在一條從u到v的路徑。所謂G的k著色（kcoloring）就是一種映射c，V→{0，1，…，k-1}，使得如果(i，j)∈E，則c(i)≠c(j)。
給有向環(huán)的頂點著色最直接的辦法是從某一頂點開始，給各頂點相同（交替）地著色，但對于回路而言，第三種顏色是需要的，這種簡單的順序著色算法很清楚是最優(yōu)的，但似乎不能導出一個快速并行算法。使用并行的方法著色，主要困難在于問題的明顯對稱性，因為并行地給很多頂點指派一種顏色，就意味著這些頂點是可以與其余頂點區(qū)分開的，但是在圖中所有的頂點均相同。因此，必須引入某種技術(shù)將頂點劃分成若干類，使得每類可以指派相同的顏色。
對于有向環(huán)圖G=(V，E)，令數(shù)組S表示G的弧，使得對于1≤i，j≤n，每當(i，j)∈E時，S(i)=j。可以設(shè)置P(S(i))=i(i≤i≤n)，立即得到頂點的前驅(qū)關(guān)系。
假定開始時，頂點i的顏色c(i)=i，令i的二進制表示為it-1it-2…ik…i1i0，則c(i)k表示c(i)的第k位的二元值，則有下述基本的著色算法：
輸入：尺寸為n的數(shù)組S表示有向環(huán)的弧；初始頂點著色c(i)。
輸出：有向環(huán)頂點著色c′(i)。
begin
fori=1to npardo
(1)令k是c(i)和c(S(i)）的二進制位不同的最低有效位；
(2)c′(i)←2k+c(i)k；
endfor
end
上述算法的正確性已經(jīng)得到證明，若識別k可以在o(1)時間內(nèi)完成。
2 算法描述及實現(xiàn)
2.1 混合包圍體層次的構(gòu)建
對于一個給定的基本幾何元素集，混合包圍體層次的構(gòu)建分為如下四個步驟：
a）采用文獻[12]中的方法來為物體的每個基本元素構(gòu)建小包圍球，稱之為基本球（underlying sphere）。主要有兩個用途：(a)有助于快速劃分包圍體;(b)在進行精確的相交測試前，它可用于預檢測。
b）建立根節(jié)點。就是要建立整個物體的AABB包圍盒、整個物體的包圍球和物體中所有多邊形的基本球。
c）利用與局部坐標軸垂直的平面，將上述包圍體劃分成兩個子包圍體以形成根節(jié)點的兩個子節(jié)點。子節(jié)點具有與根節(jié)點一樣的三個特征，即AABB包圍盒、包圍球和節(jié)點中所有多邊形的基本球。
為使得左、右子包圍體中的多邊形個數(shù)大致相等，保證混合包圍盒體樹的平衡，采用了一個懲罰函數(shù)f(p)定義如下：
f(p)=｜nl-nr｜+λnc（4）
其中：p為分割面；nl、nr、nc分別為左包圍體內(nèi)右包圍體內(nèi)和橫跨基本球的個數(shù)；λ是nc的一個影響系數(shù)。理想的分割面就是在所有軸向上懲罰函數(shù)值最小的分割面：
minmin{f(p)｜px⊥x_axis，px∈[xmin，xmax]}
min{f(p)｜py⊥y_axis，py∈[ymin，ymax]}
min{f(p)｜pz⊥z_axis，pz∈[zmin，zmax]}（5）
d）對c）中得到的兩個子節(jié)點分別遞歸地執(zhí)行上述包圍體的分割過程得到最終的混合包圍盒樹。
對每個節(jié)點采用如上的方法遞歸建立每個物體的包圍盒樹。適當?shù)倪f歸終止條件，用簡單的線性判別函數(shù)：
p(x)=AT*B（6）
其中：A=(a1，a2，a3，…，an)；B=(b1，b2，b3，…，bn)。b1，b2，b3…，bn為遞歸終止的各種因素，常取為：包圍盒樹要求的高度，葉子節(jié)點中要求所含基本幾何元素的最多數(shù)，a1，a2，a3，…，an分別為b1，b2，b3，…，bn對應的加權(quán)值。
圖1是根據(jù)上述算法步驟構(gòu)建的平衡二叉樹，每個節(jié)點中第一行的兩個數(shù)字表示包含在對應節(jié)點中的基本球的數(shù)目（等于相應多邊形個數(shù)）和對應節(jié)點的包圍球的半徑；第二行的三個數(shù)字表示的是對應節(jié)點的AABB包圍盒的寬度、高度、深度。
2.2 基于混合包圍體層次的串行碰撞檢測法
物體A和B的混合包圍體層次構(gòu)建完成，就可以通過遍歷其平衡樹來進行它們之間的碰撞檢測，在此，筆者引入任務(wù)樹的概念[6]。將遍歷兩個物體的平衡包圍盒樹的過程定義成一棵任務(wù)樹的遍歷，簡單的任務(wù)樹表示如圖2所示。
碰撞檢測的過程從本質(zhì)上來說是一個或樹的遍歷過程。一方面，如果碰撞發(fā)生在一些子任務(wù)中，那么物體A和B肯定發(fā)生了碰撞；另一方面，如果所有的子任務(wù)都沒有發(fā)生碰撞，那么物體A和B肯定沒有發(fā)生碰撞，因此一個任務(wù)的結(jié)果（true發(fā)生碰撞或者1沒有發(fā)生碰撞）可以通過將所有子任務(wù)碰撞結(jié)果作邏輯或運算。
利用任務(wù)樹，混合包圍體層次的廣度遍歷過程的算法如下：
輸入: 兩物體A B
輸出: 碰撞檢測的結(jié)果 //true: 相交 1: 不相交
WFSTraversal (RA，RB)
{ 建立A B兩物體的混合包圍體樹RA，RB；
//任務(wù)（RA，RB）作為根任務(wù)
LIVESET<任務(wù)節(jié)點 (RA，RB)
//將任務(wù)節(jié)點放入隊列
for i =1 to LIVESET.size
//循環(huán)執(zhí)行隊列中的所有節(jié)點
{
while (LIVESET!=NULL){ //隊列不為空
(a1，b1)< LIVESET; //從隊列中取出一任務(wù)節(jié)點
SplitNode=true;
//分裂變量為真，表示節(jié)點繼續(xù)劃分子節(jié)點
if((a1，b1)節(jié)點的包圍球不相交)
SplitNide=FALSE;//此任務(wù)節(jié)點不相交，分裂變量設(shè)為假
else //包圍球相交
Flag1=(Sphere2BoxVolumeRatio(a1)>=
RatioThreshold(a1) );
// a1進行包圍盒相交的閾值
Flag2=(Sphere2BoxVolumeRatio(b1)>=
RatioThreshold(b1) );
// b1進行包圍盒相交的閾值
if (Flag1)//a1包圍盒相交
if (Flag2)//b1包圍盒相交
if ( (a1，b1) 任務(wù)節(jié)點的AABB包圍盒不相交)
SplitNode=FALSE;
//此任務(wù)節(jié)點不相交，分裂變量設(shè)為假
endif
else//不再進行b1節(jié)點AABB包圍盒的相交檢測
if ( (a1，b1) 任務(wù)節(jié)點的a1的AABB包圍盒和b1包圍球不相交)
SplitNode=FALSE;
//此任務(wù)節(jié)點不相交，分裂變量設(shè)為假
endif
endif
else if (Flag2){
//應進行b1節(jié)點AABB包圍盒的相交檢測
if ((b1，a1) 任務(wù)節(jié)點的b1的AABB包圍盒和a1包圍球不相交)
SplitNode=FALSE;
//此任務(wù)節(jié)點不相交，分裂變量設(shè)為假
end if
end if // flag2
end if // flag1
end if // (a1，b1) 任務(wù)節(jié)點的b1包圍球和a1包圍球不相交
if (SplitNode=FALSE) //不相交，不再劃分子節(jié)點
else // 相交，繼續(xù)子節(jié)點的劃分
if (a1是葉節(jié)點) //a1 是葉節(jié)點
if ( b1也是葉節(jié)點))//b1是葉節(jié)
CollisionDetectionFundamentalAlgorithm(a1，b1);
// 調(diào)用基本碰撞檢測函數(shù)
if (a1和b1 相交)
return TRUE;// A B發(fā)生碰撞
end if
else //b1不是葉子節(jié)點，則產(chǎn)生b1的兩個子節(jié)點
LIVESET< (a1，b1> left); //a1，b1> left進入隊列
LIVESET< (a1，b1> right); //a1，b1> right進入隊列
end if
else if (b1是葉子節(jié)點))
{ //a1不是葉子節(jié)點，則產(chǎn)生a1的兩個子節(jié)點
LIVESET< (a1> left，b1);
LIVESET< (a1> right，b1);
else // b1，a1都不是葉子節(jié)點，則產(chǎn)生b1，a1的四個子節(jié)點
LIVESET< (a1> left，b1> left);
LIVESET< (a1> left，b1> right);
LIVESET< (a1> right，b1> left);
LIVESET< (a1> right，b1> right);
end if
end if
end if
}endwhile
}end for
return FALSE; // A 和B 不發(fā)生碰撞
}//WFATraversal遍歷結(jié)束
其中任務(wù)樹的節(jié)點采用隊列(LIVESET)存儲。函數(shù)ratioThreshold()返回一個閾值，來決定是否還要進行AABB包圍盒的相交檢測。
2.3 碰撞檢測算法的并行化
并行域一般在算法的循環(huán)部分，本文基本算法隊列中的節(jié)點可以并行執(zhí)行，大大節(jié)省了時間，從整體上提高了算法的效率。并行化基本算法如下：
輸入: 兩物體A B (RA，RB)
輸出: 碰撞檢測的結(jié)果 //TRUE: 相交 FALSE: 不相交
bool Parallel_Collision _detection(所有物體)
{
分別建立每個物體的混合包圍體樹SAABB；
//若有n個物體，則形成n*n棵任務(wù)樹，設(shè)m=n*n；由所有物體的平衡包圍盒樹通過兩兩組合成多棵任務(wù)樹，將每棵任務(wù)樹的遍歷看做一個任務(wù)；
begin
fori=1tompardo
(1) 令k是c(i)和c(S(i))的二進制位不同的最低有效位；
(2) c′(i)←2k+c(i)k；
(3)將任務(wù)i 插入到處理器c′(i)的單鏈表中；
endfor
end
//每個處理器并行處理每棵任務(wù)樹
for each processor i ，in parallel do
begin
{
LIVESET←(a0，b0)；
for ( w=1tom/ j)
{
if (當前任務(wù)節(jié)點的包圍體不相交)取消當前任務(wù);
else if (當前任務(wù)包含有一個葉子節(jié)點)
CollisionDetectionFundamentalAlgorithm()；
//在當前任務(wù)處調(diào)用基本碰撞檢測函數(shù)；
if (結(jié)果為TRUE)取消當前并行執(zhí)行的所有其他任務(wù)；
return TRUE;// 發(fā)現(xiàn)碰撞
end if
else // 當前任務(wù)包含中間節(jié)點
以同樣的方式將當前任務(wù)的所有子節(jié)點放入隊列LIVESET;
end if
end if
主線程等待其他并行的任務(wù)完成
StoreIntersectingTaskNodes();
//存儲相交的任務(wù)節(jié)點信息
}end for
}
end
return FALSE;
}
3 實驗結(jié)果及性能分析
本算法采用C語言在SGIONYX2工作站(有四個R10000處理器)上實現(xiàn)，部分的并行采用多線程共享同一存儲地址來實現(xiàn)，此處理器同一進程中能同時執(zhí)行的線程數(shù)最多為64，取為32，w取6。
實驗環(huán)境設(shè)定了一個簡單的動態(tài)場景，實驗環(huán)境中有31個物體作隨機運動，基本幾何元素數(shù)(三角面片數(shù))多于80 000個。為了說明本算法的優(yōu)越性，進行如下三個實驗。
實驗1 時間復雜性分析
實驗中將本文算法與其他經(jīng)典算法進行了時間復雜性、幀頻及運行1 000步的時間測試。實驗結(jié)果如表1所示。
表1 時間復雜性分析
算法類型算法時間復雜度幀頻/fps運行1 000步的時間/s
BCDAO(n2)3.195 109
ICOLLIDEO(n log n)4.054 231
SPHEREO(n log n)4.053 265
SCDAO(n log n)7.05185
PCDAO(n/w log n)45.456
其中：BCDA(base collision detection algorithm)為基于三角形與三角形相交的基本碰撞檢測算法；ICOLLIDE算法[13]為采用了AABB包圍盒的算法；SPHERE為采用了包圍球的算法; SCDA(serial collision detection algorithm)為采用混合包圍盒的串行碰撞檢測算法；PCDA(parallel collision detection algorithm)為本文提出的基于著色算法的并行碰撞檢測算法。
從結(jié)果可以看出，混合包圍體算法與單獨采用一種包圍體的算法相比，碰撞檢測的效率有了很大的提高。
實驗2 算法并行化分析
為說明并行計算的優(yōu)點，本文將BCDA、ICOLLIDE、包圍球算法(SPHERE)、SCDA采用著色算法并行化 在上述實驗環(huán)境下，實驗結(jié)果如表2所示。
表2 算法并行化分析
算法類型串行、并行算法運行1 000步的時間/s
BCDANP(nonparallel)5 109
P(parallel)1 976
ICOLLIDENP(nonparallel)4 231
P(parallel)1 366
SPHERENP(nonparallel)3 265
P(parallel)1 036
SCDANP(nonparallel)185
P(parallel)56
從結(jié)果可以看出，采用破對稱技術(shù)并行化算法，進一步加快了碰撞檢測過程。
實驗3 性能與效率測試
對并行算法的測試主要是測試加速比和并行效率，可以通過式（7）（8）完成：
S(p)=ts/tp（7）
其中:S(p)表示加速比；ts表示使用單處理器系統(tǒng)執(zhí)行算法的時間；tp表示使用具有p個處理器的多處理機執(zhí)行所需的時間。
E=ts/tp×p=S(p)×1/p（8）
其中：E表示并行效率；p表示處理器的個數(shù)。并行效率可定義為加速比與CPU個數(shù)之間的比值。
在上述實驗條件及環(huán)境下，筆者測試了在不同數(shù)量的處理器下并行算法的加速比和并行效率。實驗得出本文并行算法的加速比S(p)=3.3，并行效率E=0.82。實驗結(jié)果如圖3(a)和(b)所示。
從理論上講，在多處理器下，并行效率可達約80%，加速比可達約5.7。但由實驗結(jié)果可知，并行效率和加速比很難得到這種理想值，主要原因在于實驗環(huán)境，如果實驗環(huán)境簡單，碰撞檢測的計算任務(wù)小，幾個處理器就足夠了，若處理器太多，則難以實現(xiàn)最佳負載平衡同時處理器也得不到充分利用；反之如果實驗環(huán)境復雜，則需要處理器數(shù)增加。因此在一定的實驗環(huán)境下，隨著處理器個數(shù)的增加，算法的加速比在峰值后呈現(xiàn)下降趨勢，并行效率也在下降。對于不是特別復雜的虛擬環(huán)境，采用多處理器2～4個就足夠了。
并行化處理顯著地提高了碰撞檢測算法的速度，能夠滿足交互式虛擬環(huán)境實時性、精確性的要求。
4 結(jié)束語
本文提出了一種基于著色算法的并行化碰撞檢測算法。該算法的特點主要表現(xiàn)在以下三個方面：
a）利用AABB包圍盒和包圍球的優(yōu)點來構(gòu)建混合包圍體層次。在精確碰撞檢測之前，通過球與球、球與包圍盒、包圍盒與包圍盒的相交檢測排除大量不相交的多邊形。
b）算法用分治策略建構(gòu)平衡包圍體樹，保證了并行的各子問題規(guī)模大致相等，從而能夠充分利用多處理機的性能。
c）采用著色算法來設(shè)計算法，縮短了碰撞檢測的時間，適用于對動態(tài)、復雜、交互式的場景進行實時碰撞檢測。
盡管如此，算法仍有一些有待改進的地方。今后的工作將主要集中在：構(gòu)建平衡包圍盒樹時，可以采用M路分治算法充分并行化；包圍盒劃分時線性判別函數(shù)中因素和加權(quán)值的適當選擇；采用并行虛擬機(PVM)技術(shù)，使算法在互聯(lián)網(wǎng)絡(luò)的PC機上實現(xiàn)并行；還可采用新的并行技術(shù)來擴展算法，如MPI、OpenMP等。
參考文獻：
[1]范昭煒，萬華根，高曙明. 基于流的實時碰撞檢測算法[J]. 軟件學報 2004，15(10):1505-1514.
[2]ADELSON S J HODGES L F. Generating exact raytraced animation frames by reprojection[J]. IEEE Compute Graphics and Applications，1995，15(3):43-52.
[3]LAWBR O S KALE′E L V. A voxelbased parallel collision detection algorithm[C]//Proc ofInternational Conference on Supercomputing. New York:ACM Press 2002：285-293.
[4]薛廣濤 李超 尤晉元. 基于凸多面體剖分的并行碰撞檢測算法[J].上海交通大學學報，2004，38(8):1385-1388.
[5]劉曉平 曹力. 基于MPI的并行八叉樹碰撞檢測[J]. 計算機輔助設(shè)計與圖形學學報 2007，19(2):184-187，192.
[6]趙偉 何艷爽. 一種基于并行的碰撞檢測算法[J]. 吉林大學學報：工學版 2008 38(1):152157.
[7]許強呂曉峰馬登武. 三角形和三角形相交測試技術(shù)研究[J]. 計算機仿真 2006 23(8): 76-78，145.
[8]范昭煒 萬根華 高曙明. 基于并行的快速碰撞檢測算法[J].系統(tǒng)仿真學報 2000，12(5):548-552.
[9]陳國良. 并行算法的設(shè)計與分析(修訂版)[M]. 北京: 高等教育出版社 2002.
[10]陳國良. 并行計算——結(jié)構(gòu)#8226;算法#8226;編程(修訂版)[M]. 北京: 高等教育出版社 2003.
[11]WILKINSON B ALLEN M. 并行程序設(shè)計[M]. 2版. 陸鑫達，等譯. 北京: 機械工業(yè)出版社 2005.
[12]RITTER J. An efficient bounding sphere[M].San Diego，CA:Acaemic Press Inc 1990:301-303.
[13]COHEN J LIN M MANOCHA D et al. ICOLLIDE:an interactive and exact collision detection system for largescale environments[C]//Proc ofACM Interactive 3D Graphics Conf. New York:ACM Press 1995:189-196.
