【作者】 魏开平； 夏天； 沈显君；

【Author】 Wei Kai Ping Xia Tian Shen Xian Jun Department of computer science HuaZhong Normal University, Wu Han ,430079, China

【机构】 华中师范大学计算机系；

【摘要】 本文提出一种基于固定方向凸包的分层包围盒碰撞检测算法,算法主要针对不可穿透的复杂对象之间的连续碰撞进行检测。论文以虚拟数字校园为应用背景,用体积略大的而几何特性简单的外包盒来近似描叙复杂的几何对象,将复杂检测对象通过其各自的包围盒组织成层次结构以逐渐逼近对象。包围盒的组织采用自顶向下的方法,按照一定的规则建立起树形分层包围盒。在对树形分层包围盒进行遍历的过程中,通过包围盒间的快速相交测试来及早排除不可能相交的几何元素对,对包围盒重叠的部分元素进行进一步的测试,以提高碰撞检测的速度。在检测过程中,提出基于时空相关性的遍历跟踪策略,通过跟踪上一时间点活动对象在环境对象树中的遍历过程,确定当前时间点活动对象的遍历路径,从而有效的减少包围盒相交测试的数目,提高算法的效率,同时通过对跟踪表的维护保证碰撞检测的正确性和有效性,降低了算法时间复杂度。论文对遍历包围盒树算法和采用跟踪策略层次包围盒树算法进行了实验对比分析,实验仿真结果表明:在刚体复杂对象的碰撞检测中,相对于遍历包围盒树算法而言,跟踪遍历策略的检测速度效率更高。更多还原

【Abstract】 This paper proposes a method for detecting the continuous collisions based on the fixed direction hull hierarchical bounding volume. The algorithm mostly aims at the continuous collisions between objects with complex structures, and what is more, these objects can not be penetrated by other objects. Here, it is necessary to introduce some related information for the fixed direction hull. Fixed direction hull is a special convex hull, and its outward normal of facets comes from a fixed direction set. Fixed direction hull overcomes limitations of other bounding volumes, and takes a proper tradeoff between the tightness and simplicity of hierarchical bounding box. In other words, by applying the fixed direction hull, the method can keep a good balance between the tightness and simplicity. What is more, fixed direction hull has been proved to be an effective way to detecting collisions in complex environment and resolve the problems about intersection tests between bounding volumes, updating bounding volumes after rotation and updating bounding volume hierarchy after deformation. This paper takes the virtual campus roaming as its application background, and the main contribution is selecting an object with a simpler bounding volume that is a little bigger than other objects, to approximately describe the structure of the complex geometry objects, and gradually approach the objective object’s specific characteristics via respectively organizing the hierarchical structure for each detecting objective’s own bounding volume. We take the up-down method to complete this. Firstly, select one solid object with complex geometric structure as the root node of the fixed direction hull; then use the top-down method , recursively divide the fixed direction hull and calculate each division result; and finally build the hierarchical bounding volume tree according to the pre-defined rules to gradually approach the objective object’s geometry model. During the process of traversing the hierarchical bounding volume tree, we take the following method to speed up the collision detection rate. The main idea is: though carrying on a rapid intersection test between the bounding volumes to prune away the primitive pairs which will not intersected as early as possible, that is, only deal with those bounding volumes with intersected primitive pairs. Moreover, for those bounding volumes with overlapped primitive pairs, we suggest to implement more rapid intersection tests to enhance the overall efficiency. We also propose a traversal tracing strategy to make further develop the efficiency of the collision detection method. This tracing strategy is based on the temporal-spatial coherence in the virtual application environment, and its main idea is as follows: through tracing the traverse process in previous time, the required traverse path in current time can be successfully obtained. This is a heuristic strategy and its algorithm should be implemented in a travers更多还原