三维图形系统中要处理大量环境物体和运动物体,碰撞检测(Collision DetectionCD)用来检测运动物体之间或运动物体与环境物体之间是否有碰撞,从而能决定运动物体的下一步动向,以提高系统的真实感和用户的沉浸感,这在计算机图形学相关研究和应用中占有重要地位。 本文1研究了已有的一些碰撞检测算法,分析了其中典型算法:如四维空间交集测试,八叉树空间分割,BVH(bounding volumes hierarchies层次包围盒),分析各自优劣及适用条件。2针对BVH算法中选择单一的包围盒(Bounding Volume BV)所导致的性能保持的问题,即如何在简单性和紧密型之间取得折衷,本文提出了一种复合式的BVH算法,充分利用了三种BV的特点,按层次选择不同的BV,实验表明该算法能有效提高检测性能,增强算法稳健性,同时该算法具有BV层次范围可调节性的特点:进一步加入了IAABB(Intersection Axis-Aligned Bounding Boxes)方法,实验表明能减少需要检测的可能碰撞的面对(pairs of surfaces)和多边形对(pairs ofpolygons),从而在一定程度上提高检测性能。3最后把复合BVH算法应用于一个具体的三维图形处理系统即野战三维态势系统中,针对态势系统中碰撞的特点,做了碰撞检测的预处理和后处理。