在现实世界中，除非物体遭到破坏，否则不可能出现多个物体同时占有一个空间区域的情形。然而在虚拟场景中，这种违反常识的情况却可能发生，因此需进行碰撞检测以使系统产生适当的响应。从上世纪 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的缺点是返回信息有限，不能得到确切的通过深度测试的像素数目。此外，其查询模式是“挂起和等待”模式，即只有等上一次的查询结果返回，才能进行下一次查询，查询效率低。

　　NVIDIA公司对可见性查询技术作了进一步发展，其OpenGL扩展GL_NV_occlusion_query弥补 了 GL_HP_occlusion_test 的 不 足 。 首 先 ，GL_NV_occlusion_query返回的查询结果是通过深度测试的像素数目。其次，它提供了一次提交多个查询的函数接口，并且CPU在GPU进行查询时不必阻塞，可以并行作别的计算，因此查询效率得以大大提高。

　　2 检测原理

　　论文算法是基于物体的可见性进行碰撞检测。下面首先给出完全可见的定义：定 义 称物体B对物体A完全可见，如果在显示平面上先绘制物体A，再绘制物体B，物体B的所有部分均不被物体A遮挡。通过可见性查询，可以获知物体B相对于物体A的完全可见性[7]。首先绘制物体A;然后启用可见性查询功能，并把深度测试的条件改为大于或等于当前深度值;再绘制物体B。如果可见性查询的返回结果是FALSE或0，就可以确定物体B没有被物体A所遮挡，是完全可见的。这里，需注意可见性查询是基于深度测试的，深度测试条件的设定直接影响查询的结果。根据物体之间的完全可见性，即可判定它们的相交状况，存在如下定理：定 理 凸多面体A和B相交当且仅当A相对于B不是完全可见，并且B对于A也不是完全可见。此定理的结论是明显的。以图1为例加以说明，其中显示平面在左侧，视线方向由左至右。在图1(a)中，尽管物体B对物体A非完全可见，但是物体A对物体B却是完全可见，因此在它们之间存在分离面，两物体不相交。在图1(b)中，情况正好相反，物体A对物体B不是完全可见，而物体B对物体A却完全可见，它们之间同样不相交。在图1(c)中，由于两个物体对另外一个都不是完全可见，故而它们相交。

　　3 算 法

　　根据上节定理，每一对物体至多进行两次绘制和可见性查询，即可判定其相交情况。由于GL_NV_occlusion_query可见性查询具有较高的效率，基于它实现碰撞检测算法。具体算法如下所示：

　　数据结构：

　　ObjectPair链表，算法的输入检测链表，每个元素对应要进行碰撞检测的一对物体。它有3个成员变量，其中两个是指向被检测物体的指针，第3个成员为一个BOOL型变量，用于标记物体对是否相交。

　　PixelCount数组，数组的元素与ObjectPair链表的元素一一对应，用于记录由可见性查询得到的通过深度测试的像素数目。

　　算法描述：

　　Step 1 (第一轮绘制)遍历ObjectPair链表的元素，依次对每一元素所对应的物体对进行Step 2~Step 6的操作;

　　Step 2 根据物体对AABB包围盒的相交信息，设置视景体、视点及视窗参数;

　　Step 3 禁止帧缓存的写入操作;初始化深度缓存;允许深度测试和深度缓存的写入操作，

　　设置深度测试条件为小于等于当前深度值;

　　Step 4 绘制当前物体对的第一个物体;

　　Step 5 禁止深度缓存的写入操作;设置深度测试条件为大于等于当前深度值;

　　Step 6 开始可见性查询;绘制当前物体对的第二个物体;结束可见性查询;

　　Step 7 将各次查询的结果回读入PixelCount数组的相应元素中;

　　Step 8 (第二轮绘制)遍历ObjectPair链表中的元素，依次对每一物体对进行Step 9~Step 13的操作;

　　Step 9 判断与当前物体对相应的PixelCount数组元素的值，如果其值等于零，转Step 8;否则，根据物体对AABB包围盒的相交信息，设置视景体、视点及视窗参数;

　　Step 10 禁止帧缓存的写入操作;初始化深度缓存;允许深度测试和深度缓存的写入操作，设置深度测试条件为小于等于当前深度值;

　　Step 11 绘制当前物体对的第二个物体;

　　Step 12 禁止深度缓存的写入操作;设置深度测试条件为大于等于当前深度值;

　　Step 13 开始可见性查询;绘制当前物体对的第一个物体;结束可见性查询;

　　Step 14 遍历PixelCount数组元素，如果其值为零，将ObjectPair链表中相应元素的相交标志设置为FALSE;如果其值非零，回读第二轮绘制相应可见性查询结果到该元素;再检测其值，如果是零，将ObjectPair链表相应元素的相交标志设置为FALSE，否则，设置为TRUE;

　　Step 15 恢复用于正常显示场景的视景体、视点及视窗参数设置;允许帧缓存的写入操作;允许深度测试和深度缓存的写入操作，设置深度测试条件为小于等于当前深度值，返回。

　　从上述算法可以看出，对于每一对物体，首先判断第一个物体相对于第二个物体的可见性。如果不完全可见，再判断第二个物体相对于第一个物体的可见性。若结果仍为不完全可见，即可确定两物体相交;其它情况两物体不相交。碰撞检测的过程同时也是在图像平面绘制被检测物体的过程。为了不影响场景的正常显示，在碰撞检测中，禁止帧缓存的写入操作，而在检测完毕后再予以恢复。算法中需注意的另外一点是对深度测试条件的设置。在检测过程中，因为要测试一物体对另一物体的完全可见性，深度测试条件设置为大于等于当前深度值。而在其它情况下，深度测试条件设置为小于等于当前深度值。

　　4 实 验

　　作者采用C++及OpenGL对算法进行了实现。算法分两个阶段，第一个阶段为粗判断，采用扫掠和裁剪算法快速排除未发生碰撞的物体对[8];第二个阶段为精判断，采用上节算法精确检测物体间的相交情况。从原理上，论文算法基于当前计算机主流图形硬件提供的可见性查询功能进行碰撞检测，不仅克服了传统物体空间算法的缺点，也避免了其它一些图像空间算法需从显存回读大量数据的不足，因此检测效率得到有效提高。为验证论文算法的性能，在微机上对算法进行了实验。实验所用微机配置为CPU PIV2.93GHz，内存512M，显卡NVIDIA Geforce FX7300, 显存128M。

　　为了能够得出对算法性能的客观评价，首先需建立一个适当的实验场景。作者建立的场景是一个正方体容器(6个壁面在实验中不作绘制)。实验物体包括圆锥体、圆柱体、正方体和球体4种类型，它们在容器中作平移和旋转两种运动。物体的平移速度和角速度在实验开始时随机确定，平移速度的绝对值不大于物体尺寸的6%，角速度不大于10o/帧。因为实验目的是测试算法性能，因此对物体发生碰撞时的响应作了简化处理。在物体碰到壁面，或物体之间发生碰撞时，速度的绝对值保持不变，仅将速度方向作相应改变，使其不发生刺穿而能够继续运动。发生碰撞的物体用红色进行绘制。图2是实验的一个场景图，它由100个物体组成，三角面片的总数为44300个，而场景的密度为5%。

　　作者首先做了物体数目变化对碰撞检测时间影响的实验，其中用于实验的物体的平均三角面片数目为 443 个。实验记录每一帧场景(即动画的一步)用于碰撞检测的 CPU 时间，而不计场景绘制等操作所花费时间。为了减少随机因素的影响，采用连续 1200 帧场景的平均碰撞检测时间作为实验结果。作者在同样实验条件下使用RECODE 算法[5]进行碰撞检测作为对照，绘制得到如图 3 所示的直方图。从图 3 可见，在物体数目较少时(20 和 40)，两个算法的碰撞检测时间都小于 1ms，没有直方图绘出。随着物体数目的增加，论文算法的优势逐渐明显，其碰撞检测时间比 RECODE 算法减少 20%以上。作者还就三角面片数目对碰撞检测时间的影响进行了实验。在这个实验中，物体数目固定为 100 个，而通过调整不同物体的比例来改变三角面片的数目(不同种类物体的三角面片数目有较大的差别)。根据实验结果，绘制得到如图 4所示的直方图。从图 4 也可看出，论文算法在碰撞检测效率上比 RECODE 算法有较大提升。

　5 结 论

　　随着图形硬件技术的不断发展，图像空间的碰撞检测算法得到了研究者们越来越多的重视。论文提出一种基于可见性查询的碰撞检测算法。与同类算法相比较，此算法大大减少了从显存回读的数据量，并且充分利用硬件可一次提交多个查询操作的特性，使检测效率得以显著提高。论文算法虽是针对凸体而作，也可用于凹体的情况。对于非凸物体，在碰撞检测前要对其作预处理[9-10]，将其分解为凸体后再应用论文算法。

　　参 考 文 献

　　[1] Lin M C, Gottschalk S. Collision detection betweengeometric models: a survey[C]//The Proceedings ofIMA Conference on Mathematics of Surfaces, 1998:第 4 期 徐建国等：基于可见性查询的凸体碰撞检测算法 ·111·37-56.

　　[2] Jiménez P, Thomas F, Torras C. Collision detection: asurvey [J]. Computers and Graphics, 2001, 25(2):269-285.

　　[3] Zeiller M. Collision detection for objects modeled bycsg[C]//Visualization and Intelligent Design inEngineering and Architecture, 1993: 165-180.

　　[4] MyszKowski K, et al. Fast collision detection betweencomputer solids using rasterizing graphics hardware [J].The Visual Computer, 1995, 11(9): 497-511.

　　[5] Baciu G, Wong W S-K, Sun H. RECODE: aNImage-based collision detection algorithm [J]. Journalof Visualization and Computer Animation, 1999, 10(4):181-192.

　　[6] 范昭炜, 万华根, 高曙明. 基于图像的快速碰撞检测算法[J]. 计算机辅助设计与图形学学报, 2002,

　　14(9): 805-809.

　　[7] Govindaraju N K, Redon S, Lin M C, et al. CULLIDE:interactive collision detection between complexmodels in large environments using graphicshardware[C]//Proceedings of the ACMSIGGRAPH/Eurographics Workshop on Graphics

　　Hardware, Saarbrucken, 2003: 25-32.

　　[8] Cohen J D, Lin M C, Manocha D, et al. I-COLLIDE:an interactive and exact collision detection system for

　　large-scale environments[C]//Proceedings of ACMInteractive 3D Graphics Conference, Monterey, CA,USA, 1995: 189-196.

　　[9] Chazelle B, Dobkin D P, Shouraboura N, et al.Strategies for polyhedral surface decomposition: anexperimental study[C]//Proceedings of ACMSymposium on Computational Geometry, Vancouver,Canada, 1995: 297-305.

　　[10] Ehmann S, Lin M. Accurate and fast proximityqueries between polyhedra using convex surfacedecomposition[C]// Proceedings of the EurographicsConference, 2001: 500-510.

上一篇 : 暂无             下一篇 : 烤地瓜机 烤地瓜机烤地瓜的原理