基于有效约束的方向包围盒相交测试算法

摘要：

针对目前虚拟环境下碰撞检测问题中的方向包围盒(OBB)相交测试复杂度高的问题,提出一种基于线性不等式组有效约束的快速OBB相交测试算法。首先用线性不等式组描述OBB,并给出了算法矩阵降维过程中的数学理论条件,即有效约束定理；然后用有效约束不等式确定的超平面对应的行化简原系数矩阵,即针对被操作矩阵的第一列元素对矩阵进行初等变换,必要时剔除相关行列,以实现降维；再在静态与动态(旋转和平移)案例中进行测试速度与准确率的对比；最后对算法的准确性及时间复杂度进行简要分析。实验结果表明,该算法的测试速度是传统算法的2~3倍,且具有整体优越性。

关键词：OBB相交测试、分离轴、有效约束、超平面、矩阵降维

所属期刊栏目：28

分类号：TP391.41(计算技术、计算机技术)

资助基金：河南省科技攻关重点项目132102210420

在线出版日期：2016-10-25（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：1757-1766