三维场景漫游中碰撞检测的研究与应用

开篇：润墨网以专业的文秘视角，为您筛选了一篇三维场景漫游中碰撞检测的研究与应用范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要:在虚拟现实环境下,基于包围盒算法是一类重要碰撞检测算法,该文在比较了层次包围盒下的几种常用的包围盒技术,具体阐述了实时性好且较容易程序实现的轴一致包围盒(AABB)的定义、重叠测试和碰撞检测算法,并把该包围盒技术应用到虚拟现实系统的碰撞检测过程中,最终在VC++和OpenGL平台上实现了三维场景漫游过程中物体之间的精确碰撞检测。

关键词:包围盒;碰撞检测;AABB

中图分类号:TP391文献标识码:A 文章编号:1009-3044(2010)11-2706-02

The Research and Application of the Collision Detection Walkthrough in 3D Scene

YIN Xiao-chun, NIE Ming

(Nanjing College of Information Technology, Nanjing 210046, China)

Abstract:The collision detection algorithm based on Bounding Box is an important algorithm for virtual environment. The paper compares several common Bounding Box technologies under Hierarchical Bounding Volumes, illustrates the definition and the overlap test and the collision detection algorithm of AABB, which has well real-time and could be achieved easily, applies the AABB in the collision detection process of virtual reality system, and finally implements the accurate collision detection between objects of virtual scene in VC++ and OpenGL platform.

Key words: bounding Box; collision detection; AABB

碰撞检测间题在虚拟现实、计算机辅助设计与制造(CAD/CAM)、机器人和自动化、计算机图形学等领域中经常遇到的间题。精确的碰撞检测对于提高虚拟仿真系统的拟真度、增强虚拟环境的沉浸感有着至关重要的作用,而虚拟环境自身的复杂性和实时性也对碰撞检测提出了更高的要求[1]。

1 碰撞检测

在现实生活中,两个不可穿透的物体不能拥有一个相同的空间区域,而碰撞检测的任务就是判断在某时刻两个物体是否发生碰撞。通常碰撞检测系统的输入模型是构成几何对象的基本几何元素的集合,碰撞检测就是判断它们的交集是否为空,如不为空,即发生碰撞,还需计算碰撞点(碰撞发生的位置)。碰撞检测涉及到3D空间,几何模型表示、分层数据结构、测试方法等[2],它实质上是通过判断两个物体之间的距离(即距离检测)或重叠与相交(即碰撞检测)情况来实现的。

国内外学者在碰撞检测领域中做了很多有意义的工作,并提出了一些高效的碰撞检测算法,主要可以分为两类,空间分解法(Space Decomposition)和层次包围盒法(Hierarchical Bounding Volumes)。层次包围盒法是利用体积略大而形状简单的包围盒把复杂的几何对象包裹起来,在进行碰撞检测时首先进行包围盒之间的相交测试,计算两个待测对象中心点的距离与它们半径之和的关系,以此来判定两物体是否可能碰撞。如果包围盒相交,再进行几何对象之间精确的碰撞检测。它是一种最简单和最常用的分层数据结构,这种结构表示易于构造和移植,同时它不取决于任何模型的拓扑特性[3-4]。因此,根据实际需要,本文针对层次包围盒方法进行研究,并在全景虚拟校园中应用。

2 层次包围盒分析与比较

包围盒法的基本思想是使用简单的几何体来代替复杂的千奇百怪的几何体,在虚拟场景中对物体的碰撞检测可看作对包围盒进行检测,当包围盒相交时其包围的物体才有可能碰撞;当包围盒不相交时其包围的物体一定不碰撞;这样可以排除大量不可能碰撞的物体,并能够快速地得到碰撞的物体部位,具体层次包围盒类型有包围球、轴一致包围盒、有向包围盒、固定方向凸包包围盒、离散多面体包围盒等[5]。

2.1 包围球

包围球(sphere)是用球形来近似地表示物体或物体的一部分,再判断这些包围球是否相交,它是一种最简单的碰撞检测方法,这样仅需要测试两个球体中心的距离是否小于它们的半径和(表示发生了碰撞)。有时人们为了进一步提高碰撞精度,把将包围球分割成一系列小的球体,检查与各小球体是否发生碰撞。通过不断地分割检查,最终得到满意的近似值。包围球相交测试很简单,但是它的紧密性太差,因此较少使用。

2.2 有向包围盒

有向包围盒(Oriented Bounding Box:简称OBB)是任意方向的多面体,它不仅对位置和大小进行编码,而且对方向进行编码,因此,它具有很高的紧密性,可以根据被包围的物体的形状特点尽可能的紧密的包围物体。并成倍地减少相交测试包围盒的数目和基本几何元素的数目。在碰撞检测过程中,寻找包围盒的方向并确定包围盒的大小是定义和计算OBB的关键问题。

2.3 固定方向凸包包围盒

固定方向凸包包围盒(Fixed Direction Hull:简称FDH)是一种特殊的凸包,是由Kay和Kajiya于1986年在他们的光线跟踪算法中提出来的。FDH是用超过三对的平行平面对来逼近物体,所有物体的包围盒的面的法向量来自固定方向向量集合。FDH继承了凸包紧密性好的优点,具有AABB简单性的特点,但检测的速度相对比较慢。

2.4 离散多面体包围盒

离散多面体包围盒(Discrete Orientation Polytopes:简称K-DOPs)用由k/2对平行平面包围而成的凸多面体来包围对象物体。k为法向量的个数。通过判断k/2个法向量方向上是否有重叠的情况来判定两个包围体是否相交。法向量的个数越多,包围盒包围的物体就越紧密,求交集计算相对就越复杂,需合理地选取k的大小和平行平面对的方向,来保证碰撞检测的简单性和包裹物体的紧密性之间取得较好的折中,保证比较好的碰撞检测速度。

2.5 轴一致包围盒

轴一致包围盒(Axis-Aligned Bounding Boxes:简称AABB)是指包含物体且平行于坐标轴的最小六面体,该六面体沿着碰撞体局部坐标系统的轴向(x, y , z)构造,所有的包围盒具有方向一致性、易于确定包围盒相交状况和构建相关层次结构树。在碰撞检测初期,为快速的排除相距较远的物体时,AABB检测效率比较高,它适用于碰撞的物体个数和即将发生碰撞的物体个数远小于存在的物体个数的情况。由于AABB构建简单快速、相交测试的简单性和较好的紧密性,因此得到了广泛的应用。

3 基于AABB的碰撞检测

3.1 模型定义

AABB模型可以采用沿空间坐标轴上的最大最小值、角点或重心点来定义,其每种定义方式如下:

定义1:设沿轴线方向包围盒大小为:xmin,xmax,ymin,ymax,zmin,zmax,则对包围盒内任一点具有:

R={( x, y , z) | xmin≤x< xmax, ymin≤y < ymax, zmin≤z< zmax }

定义2:如果定义O ( x0 , y0 , z0)为包围盒的一个角点坐标,包围盒长度分别为Dx,Dy,Dz,则有:

R={( x, y , z) | x0 ≤x< x0+Dx , y0≤y < y0 + Dy, z0≤z < z0+ Dz, }

定义3:如果定义C ( xc , yc , zc)为包围盒的重心点坐标,包围盒长度分别为Rx , Ry,Rz,则有:

R={( x, y , z) || xc -x |≤Rx, | yc -y |≤Ry, | zc -z |≤Rz }

3.2 AABB间的相交测试

在空间中,AABB检测主要是判断检测物体的位置状态(分离或重叠),即判断物体是否发生重叠。要判断物体是否重叠,只需判断在空间坐标轴上的投影是否重叠。因此可得到以下推论:

推论1:三维场景中两个轴一致包围盒发生碰撞(重叠)的充要条件是他们在空间坐标轴上的投影都重叠。

在三维场景中,大多数情况下物体并没有发生碰撞(重叠)。因此,不需要花太多时间建立层次结构,更不需要检查所有包围盒在空间坐标轴上的投影。在实际应用中通常采用降维的方法来提高检测的效率,满足实时快速检测和动态检测的需要。所谓降维法是指首先将所有包围盒向空间某一坐标轴进行投影;其次,将投影线段进行排序,挑选出发生重叠的包围盒对;再次,进一步检查这些包围盒对在另外两个轴上的投影是否仍然重叠。如果没有重叠,则说明两个物体没发生碰撞,无须进一步检测;如果重叠,包围盒中的物体发生碰撞的可能性较大,则进行下一层的碰撞检测(如图1所示)。这样可以省去在空间其它两个坐标轴上投影线段排序的时间,同时省去了在空间坐标轴的投影线段的比较、查找的时间。

3.3 基于AABB碰撞检测算法

基于AABB树碰撞检测算法思想是是通过建立基于AABB树,并遍历这两棵树,以确定在当前位置下两个碰撞体是否发生碰撞,这是一个双重递归遍历的过程。具体描述如下:

步骤1:构造三维场景中人(或动态对象)和碰撞体的AABB树。

步骤2:在某一时刻,使用人的AABB树的根结点遍历碰撞体的AABB树。如果发现人的AABB树的根结点的包围盒与碰撞体AABB树内部结点的包围盒不相交,则中止遍历;如果能够遍历到碰撞体AABB树的叶节点,再用该碰撞体AABB树的叶节点遍历人的AABB树。如果能到达人的AABB树的叶节点,执行步骤3。

步骤3:检测基本几何元素间是否相交测试。

3.4 算法应用

在算法实现过程中,首先建立AABB树来包围碰撞体,该树是按照由上至下的递归细分方式构建的二叉树。在每一次递归过程中取最小的AABB,沿所选择的剖分面将碰撞体分为正负两半,并将所对应的原始几何元素(如三角面)分别归属正、负两边,递归进行到每一个叶子节点只包容一个原始几何元素为止,其中对于剖分面的选择,可选择垂直AABB的最长轴,且平分该轴的平面。

在南京信息职业技术学院三维场景模拟显示系统的开发过程中,选用3DMAX制作学院所有建筑的3D模型、OpenGL实现一些纹理贴图、Visual C++6.0作为开发工具。在系统实现三维场景漫游过程中,利用上文算法实现碰撞检测,取得良好的效果,整体效果如图2、图3所示。

4 结束语

由于碰撞检测问题由来已久,在不同领域涌现出许多碰撞检测算法,但在实际应用过程中,可以根据实际检测的精确度和系统的实时性等需求进行选择哪种算法进行碰撞检测,也可以选择多种算法综合应用来满足虚拟现实系统的需要,进而实现完整的、实时、更具沉浸感强的虚拟世界。

参考文献:

[1] 彭群生,鲍虎军.计算机真实感图形的算法基础[M].北京:科学出版社,1999.

[2] 高春晓,刘玉树.碰撞检测技术综述[J].计算机工程与应用,2002,38(5):9-11.

[3] 马登武,叶文.基于包围盒的碰撞检测算法综述[J].系统仿真学报,2006,18(4):1058-1061.

[4] 高玉琴,何云峰等.改进的基于AABB包围盒的碰撞检测算法[J].计算机工程与设计,2007,16(28):3815-3817.

[5] 魏迎梅,王勇.碰撞检测中的层次包围盒方法[J],计算机应用,2000,20(8):241-244.