融合有效约束OBB和PSO的碰撞检测算法研究
2020-08-07文聪徐武唐文权
文聪 徐武 唐文权
摘 要： 傳统的碰撞检测算法需要在三维空间中处理节点是否碰撞，由于处理太多节点会占用大量时间，所以实时性一直是传统碰撞检测算法难以克服的障碍。针对上述问题，提出了一种有效约束的方向包围盒（OBB）和微粒群优化（PSO）相结合的碰撞检测算法（OBBSO）。该方法首先利用有效约束的OBB算法将空间转换成线性不等式组的问题，将矩阵降维，从而快速排除不相交的节点;然后在确定发生碰撞的节点中加入PSO算法，对二维离散空间内随机群快速寻优，寻找出现碰撞的节点，大大增加了碰撞检测效率，因此利用了有效约束OBB和PSO算法的优势。相关实验表明此方法对于处理碰撞检测实时性问题具有高效性。
关键词： 有效约束的OBB; 快速寻优; 线性不等式组; PSO; 矩阵降维; 碰撞检测
中图分类号： TN911.1?34; TP391.9 文献标识码： A 文章编号： 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
