基于可见性查询的凸体碰撞检测算法

　　在现实世界中，除非物体遭到破坏，否则不可能出现多个物体同时占有一个空间区域的情形。然而在虚拟场景中，这种违反常识的情况却可能发生，因此需进行碰撞检测以使系统产生适当的响应。从上世纪 70 年代以来碰撞检测算法得到了许多研究，其成果广泛应用于计算机图形学、游戏开发、机器人路径规划、CAD/CAM及虚拟制造等领域[1-2]。传统的碰撞检测算法是基于物体空间的，根据物体的三维几何特性计算其相交状况。此类算法通常需维护复杂的数据结构，计算开销很大，因此往往成为影响应用系统实时性的计算瓶颈。图像空间碰撞检测算法是一类新兴的算法，其原理是将三维物体投影绘制到二维的计算机图像平面上，通过分析显存信息判断物之间是否发生相交[3]。此类算法具有实现简单、效率高等优点，并随着图形硬件的快速发展，得到了人们越来越多的重视。目前的图像空间算法或者要求特殊的图形硬件支持，或者在检测中需从显存回读大量数据，因此应用和发展受到限制[4-6]。针对此不足，论文提出一种新的图像空间算法。此算法基于主流图形硬件的可见性查询功能，大大减少了回读数据量，并可一次提交多个物体对的碰撞检测，显著提高了检测的效率。

　　1 可见性查询

　　可见性查询是当前主流显卡支持的一个功能，基于硬件判断几何模型在显示平面上的可见性。根据计算机图形学原理，如果绘制一个物体后深度缓存未发生变化，亦即没有像素通过深度测试，则说明物体不可见;否则，物体就是可见的。然而如果仅作深度测试，必须把深度缓存的信息回读到内存才能获得检测结果。假设测试的像素数目为10000(图像平面100×100的一块区域)，那么就需回读10000字(40000字节)的数据，这将是一个耗时的操作。基于硬件的可见性查询有效地改善了这种情况。不论检测的像素数目是多少，都只需回读1字(4字节)数据就可获知物体的可见性。可见性查询主要应用于隐藏物体的剔除。首先绘制物体的包围盒，然后进行可见性查询。如果返回值为FALSE，那么说明此物体不可见，在绘制场景时可以不作其绘制。惠 普 公 司 的 可 见 性 查 询 扩 展 称 为GL_HP_occlusion_test。当绘制一个几何模型后，GL_HP_occlusion_test根据是否有像素通过深度测试返回一个BOOL值。如果返回值为TRUE，说明物体在场景中没有被完全遮挡，即至少有部分可 见 ; 否 则 ， 说 明 物 体 完 全 不 可 见 。GL_HP_occlusion_test的缺点是返回信息有限，不能得到确切的通过深度测试的像素数目。此外，其查询模式是“挂起和等待”模式，即只有等上一次的查询结果返回，才能进行下一次查询，查询效率低。