(1. 南京邮电大学数字媒体研究中心, 南京 210003; 2. 南京邮电大学计算机学院, 南宁 210003; 3. 南京邮电大学软件学院, 南京 210003) 摘要: 碰撞检测对于 3D 游戏的开发来说是不可或缺的。 目前，主流游戏引擎通常会退回到基于分层包围体的碰撞检测~gofithms。 它使用更简单的边界 - vohune 来模拟场景中的复杂对象。 本文对四种基于体积的边界碰撞检测算法进行了理论分析。 最后3D植物，进行了实验来测试我们不同的基于体积的边界算法的性能。 结果表明，如果对限制体积进行压缩，算法将会更加准确，但时间也会缩短。 因此，遮挡检测算法应根据具体的游戏开发进行调整，以达到更好的效果。 关键词：碰撞检测； 游戏开发； 包围体积； O 引言 人们对真实性和场景真实性的期望越来越高，这都对碰撞检测提出了更高的要求。 碰撞检测是计算机游戏中需要解决的问题之一，对算法提出了更高的要求。 。
其核心任务是检测游戏场景中两个或多个物体是否相互接触或进入。 目前，三维几何模型的分类越来越复杂，画面效果也越来越逼真。 同时，人们对实时交互也很感兴趣。 下面首先从时间和空间的角度对碰撞检测算法进行划分： 收稿日期：2009-O9-10； 修订日期：2009-12-04 （1）根据时域可分为离散和连续碰撞检测基金项目：国家自然科学基金60773041）； 国家863高科技算法[1j． 技术研究发展计划基金（2007AAo1Z404、20o7AA0lz478）； 江苏省高新技术离散碰撞检测算法指各离散时间点技术研究计划基金（1332006001）； 南京市高新技术项目（2o07软资本127）； 现代通信国家重点实验室基金（9140C1105040805）； 江苏大学高校碰撞检测，其优势在于检测速度，但可能错过检测技术创新项目基金（CX08B-085Z、CX08B-086Z）； 南京邮电大学青年 发生碰撞或物体相互进入的情况； 基金的连续碰撞检测算法（N，r20603O，NY206034）是指在连续的时间间隔内进行碰撞检测。 作者简介：林巧敏(1979)，男，福建泉州人，讲师，博士生，研究的准确性有保证，但计算开销太大，在速度上容易延迟。 研究方向是计算机软件技术、数字媒体技术以及基于通信网络的多媒体，从而产生实时性能。 非常满意。
传感器网络等； 王如川，教授，博士生导师，研究方向为多媒体传感（2）基于空间域可分为基于物体空间和基于图像的传感器网络、云计算等·40·计算机技术与发展第20卷碰撞检测算法E2]。 包围体，混合层包围体[。 等待。 在实际的游戏开发过程中，基于物体空间的碰撞检测算法还可以进一步划分。 最常用的是前四种包围体类型，如图1所示。为了使用通用表示模型的碰撞检测算法和空间结构的碰撞检测算法，空间结构的碰撞检测算法为分为空间分解法（spacedecomposition）和层次包围体树法（hierarchical包围体树）。 这两种方法都是通过最小化对象对或基本几何元素的数量来实现精确相交，从而提高算法的效率。 不同的是，空间分割方法（如BSP树3）是通过整个场景的分层分割技术来实现的，而分层包围体树方法是通过为场景中的每个对象构建合理的分层包围体树来实现。 2 游戏中常用的碰撞检测算法。 早期 3D 游戏中的大多数碰撞检测都基于网格或 (c) 0BB 定向包围体 (d) k-dop 包围体 BSP 树。 基于网格的系统实现简单，但不够精确。 图 1 游戏中常用的包围体类型用于严格的 3D 碰撞检测。
基于BSP树2.1 Sphere的碰撞检测曾经非常流行，算法已经基本成熟定型。 然而，其固有的缺点是球体被定义为包含物体的最小球体，而球体的点使其不适合当今的游戏。 BSP树需要很长的预球体中心，并且可以使用物体顶点坐标的最大值和最小值的一半来处理。 它不适合在加载时进行计算。 BSP 部门经常产生原始测定结果。 假设物体顶点的最小和最大坐标为（ , ，多边形数量的三到四倍，考虑到不需要保存法线和颜色 Zrr~n），（一，Yrr~x ，一），则球体中心c的坐标为：颜色、UV等信息也需要近一倍的资源容量。 在一个游戏中，有1(X 0 = - 1 n + z), 0 (l。容量从3o0M增加到6o0M相信是大多数人无法接受的。{(1+)目前的3D游戏引擎大多采用基于分层包围体的包围球半径：碰撞检测算法。包围体技术[,5]由Clark1_Chi- (呲一)+(Ⅲ_y)+(z御一lampn'于1976年提出。基本思想是使用用简单的几何形状（即包围体）来包围动画场景中的复杂几何对象，通过构造树状的包围球，定义为：R= {(z, Y,)I(z—z0). + ( —y0)+ (z— 层次结构可以超越 越来越接近真实的物体。
在检测两个物体的碰撞时，首先检查两个物体的周围物体是否相交。 如果不相交，Z0)diA, maxordiA, min>diB, max)④ 将凸包所有顶点移动到三个轴上（d0,d,ret1.1_rll(DISIOINT)：·42·计算机技术与发展Volume 20 retum (OVERLAP);} 移动物体。在相同的场景和物体运动路径下，对于上面的k-BOP来说，它是四种算法中最紧凑最好的，但是它的算法每个都经过了七次测试四种算法，结果的平均时间（见第3节性能测试）和空间复杂度也是最高记录的，然后通过修改程序参数，增加场景中运动物体的数量，所以不能简单考虑（最终通过三角形面片的数量来计算），并且对上述每个基于分层包围体树的碰撞检测算法进行了七次测试，所以总共进行了十次测试，最终的测试结果是通过递归遍历层次树来检测对象之间的碰撞而获得的。 一般来说，如图2和图3所示。算法的性能受两个因素的影响： 影响方面：一是周围物体包围周围物体的松紧程度；二是周围物体的松紧程度。 第二，周围物体之间的交叉检测速度。 周围物体包围周围物体的紧密程度影响层次树中的节点数量。 节点数越少，遍历检测的节点数就越少。 如果介质周围有30ol，则人体检测的数量会更少。 OBB和kI)OP可以更紧密地包围物体，但构建它们的成本太高。 对于物体变形的场景，往往无法实时更新图层。 1 棵树。
AABB 和边界球没有足够紧密地包围物体，但它们的层次树更新很快，可以用于变形物体的碰撞检测。 在包围体相交检测的速度方面，AABB和包围球有明显的优势，而OBB和k-2 DOP~lt]需要更多的时间。 然而，无论选择哪种包围体，分层包围体的二叉树的递归遍历算法都是相同的，如下面的伪代码所示： 三角形面片数量（数量） x 104 // 输入：两个对象 a 和 b 的分层包围体二叉树 BVTa，图 2 平均碰撞检测时间 BVTb。 输出：true表示相交，false表示不相交 Ix~olDetect—recursive(BVTa, I b) {if (检测到周围两个物体BVTa和BVTb不相交) }//返回两个物体不碰撞的结果； } if (B ra, B I1) 都是叶子节点) {/aitf 准确检测 BVTa 和 BWI'b 包围的多边形面是否相交，并返回准确相交检测的结果； } elseif (BⅥ a 为叶子节点，为非叶子节点) {V Detet——递归(BVTa,B I1)的左子节点); Detect—re—cursive（B的右子节点，工厂I，B，工厂I1））； }elseif( BVTa 为非叶子节点，BVTb 为叶子节点) else{//BVTa，BV'Po 均为非叶子节点 Detect-recursive（BVTa，sail 的左子节点）； detet-re-cursive（BVTa，B rb 的右子节点）； Detet-recursive（B，植ra的左子节点，B，门rb）； Detect-re,cursive(BVTa的右子节点,B,,rI1));}从图2可以看出：平均碰撞检测时间随着三角形的增加而增加} patch 碰撞检测算法的数量（即移动的数量）对象）随着增加而增加。 同时，边界体积更严格的碰撞检测算法3算法性能测试需要更长的时间。
图3中算法测试的实验软件环境是Visual Studio 2005，它显示了不同测试中的碰撞次数。 从4条不同的曲线可以看出，底层图形API使用OpenGL，硬件环境为ACER。 很明显，周围体积越紧，算法检测到的碰撞次数TM4330-161G25Mn（Intel Celeron双核T1600处理器次数越少，反过来证明周围体的严密性越差，碰撞检测与集成X4500显卡）。 实验的测试指标是平均碰撞检测精度较低，即误判较多。 测量测试时间和平均检测碰撞次数，测试目标为刚性（续第46页）·46·计算机技术与发展第20卷吉林大学，2000年。 [3]李庆庆，张艳平。 基于模糊边缘检测算法的车牌定位[J]. 计算机技术与发展，2006，16(12)：8-12。 [4]廖锦洲，宣国荣． 车辆牌照自动分割[J]. 微型计算机应用，1999（7）：32-34。 [5] Fara~iF，RezaieAH，ZiaratbanM。 基于形态学的车牌定位[J](1): 57-6o. [6] 张宇，马思亮，韩晓，等。 车牌识别中的图像提取与分割算法[． 长春：吉林大学，2006：406-410。 [7] 牛鑫，沉兰荪． 基于特征的车辆牌照定位算法[J]. 交通与计算机，2000（1）：31-33。 [8] 范勇，蒋欣荣，尤智胜游戏引擎碰撞检测原理，等.汽车车牌快速定位算法[J]. 图3 识别结果图 光学工程，2001(2)：56-59。 [9]陈涛，杨晨辉，清都。 基于投影与固有特征相结合的车牌6结束字分割方法[J]. 计算机技术与发展, 2009, 19(5): 45—可见本文采用的水平边缘增强和形状47。 学习扩展与投影相结合的车牌定位分割及改进汽车牌照特征的分割[J]. IEEE，MultimediaSignal基于线性特征的改进识别算法，复杂度低，可以满足Prooessing，2008(10)：399-402。 满足实时性要求； 并且该算法对复杂背景不敏感。 [11] 王锡雷. 基于粗糙集理论的车牌汉字特征提取[J]. 计算具有较好的鲁棒性。
机械技术与发展，2007，17(6)：26-28。 [12]阿卜杜拉，SheikhSH，KhairuddinO，eta1。 Lk~nseplate 参考文献：基于支持向量机的识别[J]． ICEEI，电子一[1]韩永强，李世祥。 汽车牌照子图像定位算法[J]. 微电子工程与信息学，2009（1）：78-82。 脑应用，1999（3）：l4-16。 【l3】黄山． 车牌识别技术研究与实现[D]. 成都：四川大学，[2]郭所志． 基于灰度图像的机动车车牌定位与识别[D]. 长春：2005。（上接42页）(1)：91-102。 4 结论[4]BaraffD． Solidrindt~ es 交互仿真[J]． IEEE 计算机图形学和应用，1995，15(3)：63-75。 以上对电脑游戏中常用的几种底座进行了介绍和分析[5]Kar~mtVV。 动力学仿真的测量技术 对于分层包围体的碰撞检测算法，需要指出的是：准确度是完全碰撞检测[J]. Cnoaputer&Graphics, 1993, 17(4): 满足要求是关键，因为真实的游戏体验才是对游戏379-385的考验。
好坏最重要的标准，当然，在这个前提下，周围的物体不是[6] LinM，ManochaD，CohenJ，eta1。 碰撞检测：算法——越紧越好，因为周围物体越紧，碰撞检测时间就越长 算法与应用[J]. 机器人算法当游戏场景中有大量运动物体时运动引脚会较大，这是由于andManipulation, 1996, 6(1): 129-142。 碰撞检测带来的延迟可能是用户无法接受的。 因此，7[J PalmerLJ，GrinnsdaleRL。 动画视觉检测在3D游戏开发中，需要权衡使用球体树的准确性和效率[J]. 计算机图形学论坛，1995，14(2)：105-116。 矛盾。 [83 GottmhalkS像素游戏素材，LinM，ManochaD。 0EBTree：AHierarchicalStructureforRapidInterferenceDetection[C]／／Pmceedings 参考：0fsIGG H. New Orleans, 1A: [s. RT。 ]，1996：171-18o。 [1] 范兆伟. 实时碰撞检测技术研究[D]. 杭州：浙江大学图书[9] JimeHnezP游戏引擎碰撞检测原理，Thoma~F，T0rraSC． 3D 碰撞检测：A 厅，2003。调查[J]． 计算机与图形，2001，25：269-285。 [2] 王志强，洪家珍，杨辉。 碰撞检测研究综述[J]. 软件科学[1O]MooreM, Wilhdrus J. c0Ilision 检测和报纸响应，1999, 10(5): 545-551。 计算机动画[J]． ACM 计算机图形学，1988 年，22 [3] ArS。 查泽勒 B. 自定义BSP碰撞树[J]. （4）：289-298。 计算几何〜，理论与应用，2000年，15
