龙源期刊网 http://www.qikan.com.cn
虚拟景区中层次碰撞检测方法的研究
作者：支剑锋,韩长红,张超
来源：《电脑知识与技术》2011年第07期
摘要：针对虚拟景区场景大、对象多的特点，提出了一种层次碰撞检测方法。首先运用空间剖分法过滤掉远处不可能碰撞的对象，然后再通过构建碰撞检测空间，剔除掉待测运动对象附近暂时不可能碰撞的对象，最后再运用S-AABB层次包围盒法根据每个对象的具体精度要求进行精确碰撞检测。该碰撞检测方法在满足实际精度要求的前提下，降低了碰撞检测次数和复杂度，提高了实时性，是一种针对虚拟场景高效快速的碰撞检测方法。 关键词：碰撞检测；虚拟场景；S-AABB层次包围盒；空间剖分
中图分类号：TP333文献标识码：A 文章编号：1009-3044(2011)07-1675-05 Research on Hierarchical Collision Detection Algorithms in Virtual Scenic Spot ZHI Jian-feng, HAN Chang-hong, ZHANG Chao
(College of Computer Science and Technology, Xi'an University of Science and Technology, Xi'an 710054, China)
Abstract: Due to the big scene and massive objects of the virtual scenic spot, this thesis present a method of hierarchical collision detection. The method firstly use the spatial partition to filter the far-away objects.Then,by constructing the space of collision detection, filter the vicinal object that will not have a collision with the moving object. And at last, using the method of S-AABB hierarchical bounding-box for accurate collision detection according to the requested precision level. The method used in this thesis meet the demand of precision, reduces the number of the collision detection and the complexity, improve the real-time feature effectively. And it's a rapid collision detection method of virtual scene.
Key words: collision detection; virtual scene; S-AABB hierarchical bounding-box; space partition
在虚拟景区漫游系统中，为了保证虚拟环境的真实性，用户不仅要能从视觉上如实看到虚拟环境中的虚拟物体以及它们的表现，而且能身临其境的与它们进行各种交互，这首先要求虚拟环境中的固体物体是不可穿透的，避免诸如人穿墙而过等不真实情况的发生，这就需要虚拟现实系统能够及时检测出这些碰撞，产生相应的碰撞反应。简单地说， 碰撞检测就是检测虚拟场景中不同对象之间是否发生了碰撞。从几何上讲，碰撞检测表现为两个多面体的求交测试问题。碰撞检测问题基于现实生活中一个普遍存在的事实：两个不可穿透的对象不可能共享相同的空间区域[1]。精确的碰撞检测对提高虚拟环境的真实性、增加虚拟环境的沉浸性有十分重要的作用。
龙源期刊网 http://www.qikan.com.cn
1 碰撞检测综述
目前，常用的碰撞检测算法是包围盒法和空间剖分法等。本文就是根据虚拟景区的实际情况，将层次包围盒法和空间剖分法相结合，提出了层次碰撞检测的方法。 1.1 层次包围盒法
层次包围盒方法的基本思想是用一个简单的几何形体将虚拟场景中复杂的几何物体包围住， 之后通过构造树状层次结构越来越逼近真实的物体。当对两个物体进行碰撞检测时，首先检查两个物体最外层的包围盒是否相交，若不相交，则说明两个物体未碰撞，否则再进一步对两个物体作检测。常见的包围盒有包围球(Sphere)、轴对齐包围盒(AABB)、方向包围盒(OBB)、离散有向多面体(K-DOP)等[2]。包围盒的二维示意图如图1所示。 (a)包围球 (b)AABB 包围盒 (c)OBB 包围盒(d)K-DOP包围盒 图1 包围盒的二维示意图 1.1.1 包围球(Sphere)
一个物体的包围球(Sphere)被定义为包含该对象的最小球体，如图1（a）所示。包围球可表示为[3]：
R={(X,Y,Z)|(X-Cx)2+(Y-Cy)2+(Z-Cz)2
其中(X,Y,Z)是球的中心坐标，r是球的半径。包围球的球心可以用物体顶点坐标的最大值和最小值的一半来确定。设物体顶点坐标最大值和最小值分别为：（xmax,ymax,zmax）和（xmin,ymin,zmin），则球心C坐标为： （2）
包围球半径为： （3）
包围球间的相交测试相对比较简单。对于两个包围球（C1，r1）和（C2，r2），如果球心距离小于两球半径之和，即| C1- C2|≤r1+ r2，则两包围球相交。为节省计算, 避免开根号, 则比较球心距离的平方与半径和的平方。故包围球之间的相交测试需要4次加减运算、4次乘除运算和1次比较运算。
1.1.2 轴对齐包围盒(AABB)
龙源期刊网 http://www.qikan.com.cn
一个给定对象的AABB(Axis Aligned Bounding Box)被定义为包含该对象且边平行于坐标轴的最小的正六面体，如图1 (b)所示。AABB可表示为R={(x，y，z)|lx≤x≤hx，ly≤y≤hy，lz≤z≤hz}值。其中，lx，hx，ly，hy，lz，hz分别是该AABB在x，y，z坐标轴上投影的最小和最大坐标值。
给定对象的AABB的计算很简单．只需分别计算对象中各个元素的顶点的X坐标、y坐标和Z坐标的最大值和最小值即可。AABB间的相交测试采用区间测试的方法。AABB包围盒分别在三根分离轴上投影之后，在每个坐标轴上采用区间测试，可以确定两个AABB包围盒是否相交。区间测试在每根轴上最多进行两次，每一对包围盒最多进行6次比较运算。 1.1.3 方向包围盒(OBB)
一个物体的OBB(Oriented Bounding Box) 被定义为包含该对象且相对于坐标轴方向任意的最小正六面体。如图1（c）所示。OBB的最大特点是其方向的任意性， 这使得它的紧密性更好。但OBB的构造比较复杂，假设虚拟实体由n个三角面片构成且第i个三角面片的顶点为pi，qi和ri (i为标号)，则生成对象OBB的具体步骤如下：
Step1：求出所有n个三角面片的数学期望。
Step2：求出协方差矩阵,1≤j,k≤3,其中，Ai=pi-μ,Bi=qi-μ,Ci=ri-μ,它们均是R3中的一个向量，p，q，r均为三维向量，Mjk为3×3的协方差矩阵中的元素；
Step3：求出协方差矩阵M的特征向量，确定OBB包围盒局部坐标的三个轴向。由于协方差矩阵M是对称矩阵。其三个特征向量相互正交。将这三个特征向量单位化后。设定它们为OBB包围盒的局部坐标的三个轴向(d0,d1,d2)；
Step4：将对象凸壳的所有顶点分别向三个轴向(d0,d1,d2)投影。在三个轴向上的最大和最小投影距离差定为OBB包围盒的大小；
ｕ0 = max(Project(ｄ0,ｖi))；ｕ1 = max(Project(ｄ1,ｖi))； ｕ2 = max(Project(ｄ2,ｖi))；ｗ0 = min(Project(ｄ0,ｖi))； ｗ1 = min(Project(ｄ1,ｖi))；ｗ2 = min(Project(ｄ2,ｖi))； Step5：计算OBB包围盒的中心[4]：
OBB间的相交测试基于分离轴理论[5]。若两个OBB在1条轴线上的投影不重叠，则这条轴称为分离轴。若1对 OBB间存在1条分离轴，则可以判定这两个OBB不相交。因此， 1对