碰撞检测问题在机器人运动规划、计算机图形学等领域中有很长的研究历史。近年来随着虚拟现实、分布交互仿真等技术的兴起，碰撞检测特别是软体碰撞检测开始成为研究的热点。精确的碰撞检测对提高虚拟环境的真实性、增强虚拟环境的沉浸感有着至关重要的作用，而虚拟环境自身的复杂性和实时性又对碰撞检测提出了更高的要求。 本文以织物模拟为应用对象，对基于AABB层次包围盒的碰撞检测算法进行了研究，解决了碰撞检测和自碰撞检测的实时处理问题。在碰撞检测算法的基础上，将织物自碰撞问题通过递归的思想归结为碰撞检测的问题来讨论。同时，分析了基本几何元素间的碰撞检测问题，将所有的几何元素间的碰撞检测问题归结为“点-三角形”碰撞和“边- 边”碰撞，对可变三角形的自碰撞检测分解为6次“点-三角形”碰撞检测和9次“边-边”碰撞检测，在可变形体与刚性物体的碰撞检测中，修改“点-三角形”碰撞检测，并对刚体表面进行向外膨胀，从而消除“边-边”碰撞检测，达到提高算法效率的目的。 此外，本文在充分开发和利用虚拟环境中对象运动的时空相关性的基础上，采用了加速对象间碰撞检测速度的遍历跟踪策略。这是一个启发式的策略，通过跟踪上一时间采样点对包围盒树的遍历过程，确定当前时间采样点的遍历路径，从而有效地减少了遍历过程中包围盒相交测试的次数，提高了算法效率，同时通过对跟踪表的维护，保证了碰撞检测的正确性和有效性。 本课题是以VC++6.0和OpenGL为开发工具，在开发过程中自始至终贯彻了面向对象的编程思想。实验结果表明本文采用AABB层次包围盒碰撞检测算法能很好的在织物模拟中解决实时碰撞问题，从而为解决和处理软体对象的碰撞检测问题提供了一种可靠有效的途径。

Collision detection has been researched in many fields such as robot motion planning and computer graphics for a long time. In recent years, with the rising of virtual reality and distributed interactive simulation, many researches focus on collision detection，especially collision detection with flexible objects. Efficient and Exact collision detection is very important to improve reality and enhance immersion for virtual environment, and the complexity and real-time of virtual environment bring new requirement to collision detection. With the background of cloth simulation in the paper, the collision detection algorithms based on AABB(Axis-Aligned Bounding Boxes) are researched: With this approach, the collision and self-collision detection achieve real-time performance. Based on collision detection algorithm, a method is proposed to transform the self-collision problem into Collision problem by recursion. The collision detection algorithms among the basic geometry elements are discussed in detail, and the collision detection problems are concluded as “point- triangle” collision detection and “triangle - triangle” collision detection. The self-collision detection of changed triangle can be decomposed six times of “point- triangle” collision detection and nine times of “triangle - triangle” collision detection, but in the collision detection of changed object with rigid object, by modifying the “point- triangle” collision detection and expanding the surface of rigid object, the “triangle - triangle” collision detection can be avoided, so it can improve the efficiency of the algorithms. Furthermore, by developing and utilizing temporal-spatial coherence in virtual environment, a traverse tracing strategy is proposed that can speed up collision detection in this paper. This is a heuristic strategy. It can reduce the intersection tests need to be computed between bounding volumes by tracing the traverse process in previous time to gain traverse path in current time. The correctness and validity of collision detection can be guaranteed by maintaining the tracing list. Our subject is developed with VC++6.0 and OpenGL, and object-oriented programming thought is adopted. The test result shows that the hierarchical bounding volumes can solve effectively the detection collision problem in cloth simulation, and further provides an effective and reliable way to deal with the collision happens in soft objectives.