一种基于固定方向凸包的分层包围盒碰撞检测算法及其应用
本文提出一种基于固定方向凸包的分层包围盒碰撞检测算法,算法主要针对不可穿透的复杂对象之间的连续碰撞进行检测。论文以虚拟数字校园为应用背景,用体积略大的而几何特性简单的外包盒来近似描叙复杂的几何对象,将复杂检测对象通过其各自的包围盒组织成层次结构以逐渐逼近对象。包围盒的组织采用自顶向下的方法,按照一定的规则建立起树形分层包围盒。在对树形分层包围盒进行遍历的过程中,通过包围盒间的快速相交测试来及早排除不可能相交的几何元素对,对包围盒重叠的部分元素进行进一步的测试,以提高碰撞检测的速度。在检测过程中,提出基于时空相关性的遍历跟踪策略,通过跟踪上一时间点活动对象在环境对象树中的遍历过程,确定当前时间点活动对象的遍历路径,从而有效的减少包围盒相交测试的数目,提高算法的效率,同时通过对跟踪表的维护保证碰撞检测的正确性和有效性,降低了算法时间复杂度。论文对遍历包围盒树算法和采用跟踪策略层次包围盒树算法进行了实验对比分析,实验仿真结果表明:在刚体复杂对象的碰撞检测中,相对于遍历包围盒树算法而言,跟踪遍历策略的检测速度效率更高。
碰撞检测 固定方向凸包 分层包围盒 遍历跟踪策略
魏开平 夏天 沈显君
华中师范大学计算机系 湖北省武汉市 430079
国内会议
第二届和谐人机环境联合(第15届全国多媒体技术、第2届全国人机交互、第2届全国普适计算)学术会议
杭州
中文
124-131
2006-10-31（万方平台首次上网日期，不代表论文的发表时间）