摘要
针对目前虚拟环境下碰撞检测问题中的方向包围盒（OBB）相交测试复杂度高的问题,提出一种基于线性不等式组有效约束的快速OBB相交测试算法.首先用线性不等式组描述OBB,并给出了算法矩阵降维过程中的数学理论条件,即有效约束定理;然后用有效约束不等式确定的超平面对应的行化简原系数矩阵,即针对被操作矩阵的第一列元素对矩阵进行初等变换,必要时剔除相关行列,以实现降维;再在静态与动态（旋转和平移）案例中进行测试速度与准确率的对比;最后对算法的准确性及时间复杂度进行简要分析.实验结果表明,该算法的测试速度是传统算法的2~3倍,且具有整体优越性.
To solve the high complexity problem of OBB intersect test during collision detection process in virtual environments, this paper proposes a fast oriented bounding box（OBB） intersect test algorithm which is based on linear inequalities effective constraints. First, we describe OBB by linear inequalities, and give the associated mathematical theory conditions in of matrix dimensionality reduction, i.e. effective constraint theorem. Second, we simplify the original coefficient matrix via utilizing the corresponding row of the hyperplane which corresponds to effective constraint inequality, namely achieved matrix dimension reduction by excluding related rows and columns when necessary by operating the first column of the matrix elements using elementary transformation. We also make the comparisons about the performance and accuracy in static case and dynamic case. Finally, the accuracy and time complexity of the algorithm is briefly analyzed. The experimental results show that the performance of the algorithm is faster than traditional algorithm in 2~3 times, and the method has the overall superiority.
出处
《计算机辅助设计与图形学学报》
EI
CSCD
北大核心
2016年第10期1757-1766,共10页
Journal of Computer-Aided Design & Computer Graphics
基金
河南省科技攻关重点项目(132102210420)
关键词
OBB相交测试
分离轴
有效约束
超平面
矩阵降维
OBB intersect test
separation axis
effective constraint
hyperplane
matrix dimension reduction
