与一个平截体做相交检测可以说游戏检测必不可少的东西了,早期的包围检测可以剔除一些不需要渲染的物体,减轻GPU负担,极大的优化性能.一般的,我喜欢在View Space(相机空间) 来做检测,而不是World Space(世界空间)或者Locla Space(物体的局部空间),也不知道别的引擎是怎么干的,不过这不是重点,出于性能考虑,以下代码使用_m128类型来进行数学运算,当成4个float数来使用.为了使用方便,定义一些辅助存储结构(来自DirectXMath)
struct XMFLOAT4 struct XMFLOAT3 struct XMFLOAT2 另外重载一些大于小于运算符,这里就不写出来了
{ { { 注意,min,max返回的是各个分量的,+-*/同理
float x,y,z,w; float x,yz; float x,y example:
}; }; }; max( {1,2,3} ,{0,7,2} ) => {0,2,2} endexample
首先介绍第一种包围体,axis-aligned bounding box(AABB),这是一种非常简单的 包围体,容易计算,直观,但是包围的不够紧密,AABB可以有两个点来描述,一个是物体xyz的最小值组成的,一个是最大值组成的,下图是一个2D的AABB(降低维度讲解更为清晰)
有的数据结构并不直接存储Vmin和Vman,而是存放中间点c和距离中心xyz最大范围e,C,E通过Vmin和Vmax计算十分简单
出于性能考虑,数据结构应该是16byte对齐的,(题外话,VC下使用declspec(align(16)),当然C++11新增了alignas(expression),蛋疼的是,g++4.9已经完全支持c++14的时候,visual studio ctp3还只部分支持c++14特性,值得庆幸的是alignas在vc2014CTP3就得到了支持,是很有必要升级编译器的,另外可能得撸个def.h这样的头文件做些workaround,提供宏来进行对齐,我的库是一个lalignas),
Struct lalignas(16) Box
{
XMFLOAT3 mCenter;
XMFLOAT3 mExtents;
};
接下来我们要实现一个函数,用于从对象各个点创建AABB由于各个对象所使用的顶点结构是不可能一致的,于是得提供一些额外参数用于指出point,于是函数声明以及定义应该是这样<另外一些对容器的重载这里就不写出来了>
template<typename T> Box ComputeBoundingAxisAlignedBoxFromPoints(const T* vertices, std::size_t size,std::uint16_t stride,std::uint16_t offset) { //首先构造两个最小点和最大点 lconstexpr auto Infinity = std:: numeric_limits<float>::max(); XMFLOAT3 vMin {+Infinity,+Infinity,+Infinity}; XMFLOAT3 vMax {-Infinity,-Infinity,-Infinity}; auto pBuffer = (leo::byte *) vertices;//sizeof(leo::byte) == 1 for(std::size_t i = 0; i != size;++i) { vMin =std::min(vMin,*std::reintpret_cast<XMFLAOT3*>(pBuffer+stride*i+offset)); vMax=std::max(vMin,*std::reintpret_cast<XMFLAOT3*>(pBuffer+stride*i+offset)); } return {(vMin+vMax)/2,(vMax-vMin)/2}; } |
但是AABB的包围(如下图)太不紧密了,于是有了OBB