融合有效約束OBB和PSO的碰撞檢測(cè)算法研究

文聰 徐武 唐文權(quán)

摘? 要： 傳統(tǒng)的碰撞檢測(cè)算法需要在三維空間中處理節(jié)點(diǎn)是否碰撞，由于處理太多節(jié)點(diǎn)會(huì)占用大量時(shí)間，所以實(shí)時(shí)性一直是傳統(tǒng)碰撞檢測(cè)算法難以克服的障礙。針對(duì)上述問題，提出了一種有效約束的方向包圍盒（OBB）和微粒群優(yōu)化（PSO）相結(jié)合的碰撞檢測(cè)算法（OBBSO）。該方法首先利用有效約束的OBB算法將空間轉(zhuǎn)換成線性不等式組的問題，將矩陣降維，從而快速排除不相交的節(jié)點(diǎn);然后在確定發(fā)生碰撞的節(jié)點(diǎn)中加入PSO算法，對(duì)二維離散空間內(nèi)隨機(jī)群快速尋優(yōu)，尋找出現(xiàn)碰撞的節(jié)點(diǎn)，大大增加了碰撞檢測(cè)效率，因此利用了有效約束OBB和PSO算法的優(yōu)勢(shì)。相關(guān)實(shí)驗(yàn)表明此方法對(duì)于處理碰撞檢測(cè)實(shí)時(shí)性問題具有高效性。

關(guān)鍵詞： 有效約束的OBB; 快速尋優(yōu); 線性不等式組; PSO; 矩陣降維; 碰撞檢測(cè)

中圖分類號(hào)： TN911.1?34; TP391.9? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼： A? ? ? ? ? ? ? ? ?文章編號(hào)： 1004?373X（2020）13?0095?04

Research on collision detection algorithm based on fusion

of effective constraint OBB and PSO

WEN Cong， XU Wu， TANG Wenquan

（School of Electrical and Information Engineering， Yunnan Minzu University， Kunming 650500， China）

Abstract： The traditional collision detection algorithm needs to deal with the collision of the nodes in three?dimensional space. It takes a lot of time to process too many nodes， so real?time performance has always been an obstacle that traditional collision detection algorithms cannot overcome. Therefore， a collision detection algorithm OBBSO which combines the effective constraint oriented bounding box（OBB） and the particle swarm optimization （PSO） is proposed. In this method， the effective constraint OBB algorithm is used to transform the space into a set of linear inequalities first， and then the matrix is subjected to dimension reduction， so as to eliminate disjoint nodes quickly. In addition， the PSO algorithm is introduced into the nodes where collisions have occurred， so that the random group in the two?dimensional discrete space can be quickly optimized to find the nodes where collisions have occurred， which greatly increases the collision detection efficiency. Therefore， the advantages of the effective constraint OBB algorithm and the PSO algorithm are utilized. The relevant experiment results show that this method is efficient in dealing with the real?time performance of collision detection.

Keywords： effective constraint OBB; quick optimizing; linear inequalities; PSO; matrix dimensionality reduction; collision detection