| 算法与游戏之OBB碰撞算法 | 您所在的位置：网站首页 › 3d引擎算法 › 算法与游戏之OBB碰撞算法 |
算法与游戏之OBB碰撞算法
|
笔者介绍：姜雪伟，IT公司技术合伙人，IT高级讲师，CSDN社区专家，特邀编辑，畅销书作者，国家专利发明人;已出版书籍：《手把手教你架构3D游戏引擎》电子工业出版社和《Unity3D实战核心技术详解》电子工业出版社等。 包围盒是一个简单的立体几何空间，它里面可包含着复杂形状的物体。给物体添加包围体的目的是快速的进行碰撞检测，如果读者使用过Unity3D引擎，该引擎一共分为以下几种碰撞体：球状碰撞体、立方体碰撞体、胶囊体、Mesh碰撞体等。它们真正的实现原理也是是OBB包围盒。本章主要是告诉读者3D模型的碰撞体算法一般采用的是OBB包围盒算法或者AABB包围盒算法，这两种碰撞算法在3D引擎中经常使用，Cocos2d-x引擎对3D模型的碰撞检测也是采用AABB算法和OBB算法这两种算法，下面介绍OBB碰撞盒算法。 目前广泛应用的是AABB和OBB包围盒，其中AABB包围盒更常见，因为它的生成方法很简单，因它与坐标轴是对齐的。但它也有不足，它不随物体旋转，对于较精确的碰撞检测效果并不是特别好。这时就需要OBB包围盒，因为它始终沿着物体的主方向生成最小的一个矩形包围盒，并且可以随物体旋转，适用于较精确的碰撞检测。OBB算法在坐标轴的表示如下图： 想要标识一个OBB包围盒我们大概会想到，使用8个顶点的集合、6个面的集合、1个顶点和3个彼此正交的边向量，又或者是1个中心点、1个旋转矩阵和3个1/2边长(注：一个旋转矩阵包含了三个旋转轴，若是二维的OBB包围盒则是一个中心点，两个旋转轴，两个1/2边长)。 上述最后一种方法就是最常用的方法，下面来看一段Cocos2d-x 3.x中CCOBB.h中的代码： Vec3 _center; // 中心点 /* 以下三个变量为正交单位向量， 定义了当前OBB包围盒的x,y,z轴 用于计算矢量投影 */ Vec3 _xAxis; // 包围盒x轴方向单位矢量 Vec3 _yAxis; // 包围盒y轴方向单位矢量 Vec3 _zAxis; // 包围盒z轴方向单位矢量 Vec3 _extents; // 3个1/2边长,半长、半宽、半高Cocos2d-x 3.x中，在CCOBB.h中定义了五个成员变量，每一个数据类型都是一个三维向量，包含了3个浮点数。也就是说，表达一个OBB包围盒需要15个float类型的变量，占用60个字节，然而表示一个AABB包围盒仅需要两个顶点，24个字节，从这一点上来说，OBB的内存消耗算很高了。 一种减少开销的方案是：只存储旋转矩阵的两个轴，只是在测试时利用叉积计算第三个轴，这样可以减少CPU操作开销并节省3个浮点数分量，降低20%内存消耗。 在Cocos2d-x 中使用了两种方法去计算OBB，第一种方法是简化的OBB构建算法，由一个AABB包围盒来确定最终OBB包围盒，另外一种方法是通过协方差矩阵来确定一个方向包围盒(实际上无论是AABB包围盒还是OBB包围盒，真正的难点便在于包围盒的构建上)。 在Cocos2d-x中第一种方法用起来更为简单一些，例如： //获取一个Sprite3D对象的aabb包围盒 AABB aabb = _sprite->getAABB(); //创建obb包围盒 OBB _obbt = OBB(aabb);不论立方体如何旋转其碰撞体都会随着转动。说到转动，读者不难想象到利用矩阵可以实现旋转变换，函数如下： OBB::OBB(constVec3* verts, intnum) { if(!verts)return; reset(); Mat4 matTransform = _getOBBOrientation(verts, num); matTransform.transpose(); Vec3 vecMax = matTransform * Vec3(verts[0].x, verts[0].y, verts[0].z); Vec3 vecMin = vecMax; for (int i = 1; i < num; i++) { Vec3 vect = matTransform * Vec3(verts[i].x, verts[i].y, verts[i].z); vecMax.x = vecMax.x> vect.x ? vecMax.x : vect.x; vecMax.y = vecMax.y>vect.y ? vecMax.y : vect.y; vecMax.z = vecMax.z>vect.z ? vecMax.z : vect.z; vecMin.x = vecMin.x< vect.x ? vecMin.x : vect.x; vecMin.y = vecMin.y_extents.z || d < -_extents.z) return false; return true; } //指定OBB包围盒的变量值 void OBB::set(const Vec3& center, const Vec3& xAxis, const Vec3& yAxis, const Vec3& zAxis, const Vec3& extents) { _center = center; _xAxis = xAxis; _yAxis = yAxis; _zAxis = zAxis; _extents = extents; } //复位 void OBB::reset() { memset(this, 0, sizeof(OBB));//将OBB所在内存块置零 } //获取顶点信息 void OBB::getCorners(Vec3* verts) const { verts[0] = _center - _extentX + _extentY + _extentZ; //左上顶点坐标 //z轴正方向的面 verts[1] = _center - _extentX - _extentY + _extentZ; //左下顶点坐标 verts[2] = _center + _extentX - _extentY + _extentZ; //右下顶点坐标 verts[3] = _center + _extentX + _extentY + _extentZ; //右上顶点坐标 //z轴负方向的面 verts[4] = _center + _extentX + _extentY - _extentZ; //右上顶点坐标 verts[5] = _center + _extentX - _extentY - _extentZ; //右下顶点坐标 verts[6] = _center - _extentX - _extentY - _extentZ; //左下顶点坐标 verts[7] = _center - _extentX + _extentY - _extentZ; //左上顶点坐标 } //将点投影到坐标轴 float OBB::projectPoint(const Vec3& point, const Vec3& axis) const { float dot = axis.dot(point);//点积 float ret = dot * point.length(); return ret; } //计算最大最小投影值 void OBB::getInterval(const OBB& box, const Vec3& axis, float &min, float &max) const { Vec3 corners[8]; box.getCorners(corners);//获取包围盒顶点信息 float value; //分别投影八个点，取最大和最小值 min = max = projectPoint(axis, corners[0]); for(int i = 1; i 右下点的矢量 v1 = corners[0] - corners[1];//左下点->左上点的矢量 /* 两个矢量的叉积得到的结果 是垂直于原来两个相乘矢量的矢量 */ Vec3::cross(v0, v1, &faceDirection);//计算v0,v1的叉积结果存储到faceDirection /* 归一化 此处相当于求x,y轴所在平面的法矢量 */ faceDirection.normalize(); break; case 1:// 左/右计算结果为一个与x轴平行的矢量 v0 = corners[5] - corners[2]; v1 = corners[3] - corners[2]; Vec3::cross(v0, v1, &faceDirection); faceDirection.normalize(); break; case 2:// 上/下计算结果为一个与y轴平行的矢量 v0 = corners[1] - corners[2]; v1 = corners[5] - corners[2]; Vec3::cross(v0, v1, &faceDirection); faceDirection.normalize(); break; default: CCASSERT(0, "Invalid index!"); break; } return faceDirection;//返回方向矢量 } //检测两个OBB包围盒是否重合 bool OBB::intersects(const OBB& box) const { float min1, max1, min2, max2; //当前包围盒的三个面方向相当于取包围盒的三个坐标轴为分离轴并计算投影作比较 for (int i = 0; i |
【本文地址】