虚拟场景中基于包围盒的碰撞检测方法的研究与应用
- 格式：pdf
- 大小：252.44 KB
- 文档页数：5
http://www.paper.edu.cn
- 1 - 虚拟场景中基于包围盒的碰撞检测方法的研究与应用
李红霞
河海大学计算机及信息工程学院，南京（210098）
E-mail：lihongxia2005@hhu.edu.cn
摘 要：将一种改进算法应用于台球的碰撞检测算法。利用虚拟环境中发生碰撞的帧与帧之
间的关联性，对已发生的碰撞进行缓冲，以便下一次的碰撞检测可以利用已检测的上一次的
碰撞的信息，加快了碰撞检测的速度，同时利用预测式方法扩展了这种算法。实验结果证明，
本算法可以有效地解决碰撞检测的计算复杂性问题和改进虚拟环境中碰撞检测的性能，使动
画效果更加逼真。
关键词：计算机动画，台球，碰撞检测，虚拟环境
1. 引言
虚拟现实（Virtual Reality, 简称VR），又译为临境，灵境等。虚拟现实是对虚拟想象或
真实三维世界的模拟。当对某个特定环境真实再现后，用户通过接受和响应模拟环境给予的
各种感官刺激，从而达到身临其境的感觉[1]
。虚拟现实可被看成一个高级的人机界面，人们
可以通过视听触等信息通道来感受设计者的意图。
虚拟现实的特点包括：“身临其境”的沉浸感；友好亲切的人机交互性；激动人心的刺激
性。参与者在虚拟环境中的活动或经历主要有两种形式：一种是主观参与者与参与者是整个
经历的中心，一切围绕参与者进行。另一种是客观参与者，参与者可以在虚拟环境中看到自
己与其他物体的交互。
VR技术的主要目标之一是允许用户以尽可能自然的方式与虚拟世界直接交互。VR中
动态物体与静态物体之间或动态物体之间的交互基础是碰撞检测[2]
。
碰撞检测在机器人路径规划、计算机动画、虚拟环境仿真等领域都起着至关重要的作用。
而提高虚拟环境的沉浸感、增强虚拟环境的真实性对碰撞检测的准确性、实时性提出了更高
的要求。
2. 碰撞检测概述
碰撞检测（Collision Detection）就是检测虚拟场景中不同对象之间是否发生了碰撞。从
几何上讲，碰撞检测表现为两个多面体的求交问题；在虚拟现实系统中，主要是如何解决碰
撞检测的实时性和精确性的矛盾。准确的碰撞检测对于增强虚拟场景的真实感和沉浸感起着
至关重要的作用。而碰撞问题包括碰撞检测和碰撞响应两部分。碰撞检测的目标是发现碰撞
并报告；碰撞响应是在碰撞发生后，根据碰撞点和其它参数促使发生碰撞的对象做出正确的
动作，以反应真实的动态效果。碰撞响应涉及到力学反馈、运动物理学等领域的知识。
碰撞检测问题基于现实生活中一个普遍存在的事实：两个不可穿透的对象不可能共享相
同的区域。碰撞检测的基本任务是确定两个或多个物体彼此之间是否发生接触或穿透。即确
定在某一时刻两个几何模型是否发生干涉，如发生碰撞，则需确定碰撞点[3]
。
碰撞检测是一个复杂又费时的过程，按过程可以分为三个部分，碰撞检测、碰撞分析与
决断、碰撞信息反馈。碰撞检测主要是检测是否两个物体之间发生碰撞，这个过程有许多方
法实现，但对于一个大的集成系统来说，仅仅做出判断是不够的，获取到碰撞发生的时间和
位置以及发生碰撞物体的几何元素。碰撞检测信息反馈主要为集成系统提供相应的说明和对
物体的状态作出改变，以便为更高层任务的完成提供参考依据。 http://www.paper.edu.cn
- 2 - 随着计算机软硬件和网络技术的快速发展，虚拟场景中的物体模型越来越复杂。一个虚
拟环境通常包含若干个静止的环境对象和运动着的活动对象，每一个虚拟对象的几何模型都
是由成千上万个基本几何元素组成的，虚拟环境的几何复杂度使得碰撞检测的计算复杂度大
大提高。同时，其真实性、实时性和交互性等方面的要求越来越高，参与者不仅要能从视觉
上如实地看到虚拟环境中的虚拟对象以及它们的表现，而且能身临其境地与它们发生各种交
互，因此碰撞检测往往成为虚拟环境中的一个瓶颈。
3. 基于包围盒的碰撞检测算法
碰撞检测技术中所用的包围盒有两个属性：简单性和紧密性。简单性是指包围盒间进行
相交测试时需要的计算量。紧密性要求包围盒尽可能的贴近被包围的对象，这一属性直接关
系到需要进行相交测试的包围盒的数目，紧密性越好，参与相交测试的包围盒数目就越少。
层次包围盒是利用体积略大而形状简单的包围盒把复杂的集合对象包裹起来，进行碰撞
检测首先进行包围盒之间的相交测试；如果包围盒相交，再进行几何对象之间精确的碰撞检
测。它是目前应用最为广泛的一种碰撞检测算法。
碰撞检测领域中研究最多的包围盒主要有[4]
：包围球（sphere）、轴一致包围盒（AABB
Axis-Aligned Bounding Boxes）、有向包围盒（OBB Oriented Bounding Box）、固定方向凸包
包围盒（FDH Fixed Direction Hull）等。
(a) 包围球 (b)AABB包围盒 (c) OBB包围盒 (d) 6-dop包围盒
图1 包围盒二维示意图
4. 对OBB的碰撞检测的改进算法的应用
在虚拟环境中通常在帧和帧之间都会有很强的关联性，因为虚拟环境从一帧过渡到另一
帧时间不会急剧变化。这意味着虚拟环境中物体从一帧变化到另一帧时是相对静止。因此当
有一次碰撞在两个虚拟物体之间发生时，很有可能会有一次新的碰撞在这两个物体之间发生
[5]
。假设新的碰撞总是会在接近上一次碰撞的多边形处发生，在需要测试碰撞发生与否时可
以首先测试上一次发生碰撞的地方，同时按照下面图2的流程，应该把上一次发生碰撞的相
关信息缓冲下来，以供本次测试使用，见图3。
图2 下一帧与上一帧的关系 http://www.paper.edu.cn
- 3 -
图3 当前帧的碰撞检测结果
此方法在具体实现时，需要在原有的表示每个物体的数据结构里添加Cache字段，里面
存放每个物体上次发生碰撞信息。每当需检测该物体的碰撞情况时，系统先检测该物体的
Cache字段中的存放的该物体的碰撞情况，如发生碰撞，则Cache中的物体此时仍然发生碰
撞，可直接返回给系统；如未发生碰撞，则Cache中的物体此时未发生碰撞，此时，需要重
新检测该物体的方向包围盒，若新的碰撞发生，则将发生碰撞的物体的信息返回给系统，同
时用此结果覆盖掉Cache中原来的信息，即将Cache中的内容刷新；若没有新的碰撞发生，
则将未发生碰撞的结果返回。
这种方法可以很好地提高碰撞检测的速度，此时Cache的入口数目的选择比较重要。若
其入口只有一个，就可能会发生误判的错误。例如当碰撞涉及到多于两个物体时，其中的一
个Cache中的物体的碰撞信息在没有发挥任何作用时就会被另一个物体的碰撞信息刷新，这
样就会漏掉一次发生的碰撞。具体情况如图4所示。可以看到，在这种情况下，第一步A
和B的Cache字段中分别存放A和B的碰撞情况，第二步B的Cache字段中的内容被B和
C的碰撞情况覆盖掉了，第三步再检查A和B的碰撞情况时，它们在Cache中的内容已经
被刷新了，这样系统会得出A和B没有发生碰撞的错误结论。
图4 物体A，B和C同时碰撞的情况
若让Cache能存储多次碰撞的碰撞点信息，即让Cache拥有多个入口值，就可以解决上
述同时发生碰撞的漏判问题。此时通过测试Cache中所有的物体，系统可以检测出所有发生
的碰撞。当一个碰撞在数目较少的物体之间反复发生时，这种发法也可起到好的效果，因为
此时系统仅需要判断缓存中的数据即可得到结论，发生碰撞的相关信息一定可以从缓存中读
出。
若采用多个Cache入口，就会涉及到Cache的替换策略。替换策略可以采用最近最少使
用法（LRU），即当Cache已满需要替换时，挑选Cache中没有使用过的时间最长的项替换
掉。因此，Cache字段除了物体的碰撞点的几何信息之外还需要维护以下变量。
Collided：标识物体是否发生碰撞的逻辑变量。初始值为0，若被访问过就置为1。 http://www.paper.edu.cn
- 4 - Used：标识次Cache是否被访问过。初始值为0，若被访问过就置为1。
Time_id：时间标识。有系统设定时间间隔单位。每过一个时间单位，Time_id值加1。
为此，系统还需设置一个全局计数器，每触发一次计数器，便刷新一次Time_id的值。
当刚发生的一次碰撞涉及到Cache中的项时，需要将缓存中每一项的Collided，Used
和Time_id更新。
然而Cache入口数量也不能取得太大。因为系统需要测试所有的已存放在Cache中的信
息才能判断是否发生碰撞。若是Cache的入口数量太大，会消耗大量时间去查找其中的项，
则系统的效能将大大降低。Cache入口较多将会显著降低系统的效率。
算法框架
在一个交互适时的虚拟现实系统里，在每个时间点进行如下的循环：
Begin
for all time steps
render next picture
read input
simulation specific calculations
collision detection
collision response
End
本文所采用的算法框架如图5所示：
图5 算法框架
5. 实验结果
对于小球的碰撞运动采用改进算法，分别进行测试，碰撞检测的时间t，实验结果如图6。 http://www.paper.edu.cn
- 5 -
图6 实验结果
从实验结果可以看出，采用已改进的碰撞检测算法较之采用未改进的碰撞检测算法有大
约10%~15%的性能上的改进，并且当球的数量越多时，算法改进的效率也越高。
参考文献
[1] 汪成为，高文，王行仁，灵境（虚拟现实）技术的理论/实现及应用。北京：清华大学出版社，1996：
1-3
[2] 王祎 虚拟现实中基于组件的碰撞检测技术研究[学位论文]，吉林大学2005年4月
[3] 丁志磊 基于OBB包围盒的快速碰撞检测 [学位论文] 兰州理工大学 2006年4月
[4] 郭海儒 基于OBB包围盒树的实时碰撞检测算法[学位论文]，太原理工大学2004年5月
[5] 章勤，黄琨，李光明 一种基于OBB的碰撞检测算法的改进，华中科技大学学报（自然科学版）Vol.31
No.1 Jan.2003
Research on Collision Detection in Virtual Reality Based on
Object-Oriented Bounding Boxes tree
Li Hongxia
College of Computer and Information Engineering，Hohai University，Nanjing，（210098）
Abstract
In allusion to the collision detection algorithm of spheres, apply an ameliorated algorithm. Utilized the
relevance of the collision between the frame and the frame in virtual environment, do a cushion for the
collision which have happened, next collision can gradually use the last collision information which
