OBB方向包围盒碰撞检测算法（原理与代码）

淡淡的烟草味﹌ 2022-12-28 04:06 512阅读 0赞

原理：OBB间的相交测试基于分离轴理论（separating axis theory）。若两个OBB在一条轴线上（不一定是坐标轴）上的投影不重叠，则这条轴称为分离轴。若一对OBB间存在一条分离轴，则可以判定这两个OBB不相交。对任何两个不相交的凸三维多面体，其分离轴要么垂直于任何一个多面体的某一个面，要么同时垂直于每个多面体的某一条边。因此，对一对OBB，只需测试15条可能是分离轴的轴（每个OBB的3个面方向再加上每个OBB的3个边方面的两两组合），只要找到一条这样的分离轴，就可以判定这两个OBB是不相交的，如果这15条轴都不能将这两个OBB分离，则它们是相交的。

代码：

FBox，FOrientedBox都是UE4数据结构
    /**@前路漫漫 oriented box intersection */
    bool IntersectOOBB(const FOrientedBox& OB1, const FOrientedBox& OB2)
    {
    	const int32 ObVertNum = 8;
    	FVector OB1Vert[ObVertNum] = { FVector::ZeroVector };
    	OB1.CalcVertices(OB1Vert);
    
    	FVector OB2Vert[ObVertNum] = { FVector::ZeroVector };
    	OB2.CalcVertices(OB2Vert);
    
    	//calculate 1d bound box
    	auto affectMinMaxValue = [](float& min, float& max, float value)
    	{
    		min = std::min(min, value);
    		max = std::max(max, value);
    	};
    
    	//determin whether two obb(box1, box2) exit a separate axis on a given axis(axe)
    	auto isSATFoundedOnAxe = [&affectMinMaxValue, &OB1Vert, &OB2Vert, &ObVertNum](const FOrientedBox& box1, const FOrientedBox& box2, const FVector& axe)->bool
    	{
    		float minBox1 = std::numeric_limits<float>::max(), maxBox1 = std::numeric_limits<float>::min(), minBox2 = std::numeric_limits<float>::max(), maxBox2 = std::numeric_limits<float>::min();
    
    		for (int32 i = 0; i < ObVertNum; i++)
    		{
    			affectMinMaxValue(minBox1, maxBox1, axe | OB1Vert[i]);
    		}
    
    		for (int32 i = 0; i < ObVertNum; i++)
    		{
    			affectMinMaxValue(minBox2, maxBox2, axe | OB2Vert[i]);
    		}
    
    		//try seg1 on seg2 or seg2 on seg1
    		return ((minBox2 <= maxBox1 && minBox2 >= minBox1) ||
    			(maxBox2 <= maxBox1 && maxBox2 >= minBox1)) ||
    			((minBox1 <= maxBox2 && minBox1 >= minBox2) ||
    				(maxBox1 <= maxBox2 && maxBox1 >= minBox2));
    	};
    
    	/*Exclude the majority case of no collision*/
    	FBox Box1AABB(OB1Vert, ObVertNum);
    	FBox Box2AABB(OB2Vert, ObVertNum);
    	if (!Box1AABB.Intersect(Box2AABB))
    		return false;
    
    	/*Use SAT to know if collision existe*/
    	if (!isSATFoundedOnAxe(OB1, OB2, OB1.AxisX)) return false;
    	if (!isSATFoundedOnAxe(OB1, OB2, OB1.AxisY)) return false;
    	if (!isSATFoundedOnAxe(OB1, OB2, OB1.AxisZ)) return false;
    
    	if (!isSATFoundedOnAxe(OB1, OB2, OB2.AxisX)) return false;
    	if (!isSATFoundedOnAxe(OB1, OB2, OB2.AxisY)) return false;
    	if (!isSATFoundedOnAxe(OB1, OB2, OB2.AxisZ)) return false;
    
    	if (!isSATFoundedOnAxe(OB1, OB2, OB1.AxisX ^ OB2.AxisX)) return false;
    	if (!isSATFoundedOnAxe(OB1, OB2, OB1.AxisX ^ OB2.AxisY)) return false;
    	if (!isSATFoundedOnAxe(OB1, OB2, OB1.AxisX ^ OB2.AxisZ)) return false;
    
    	if (!isSATFoundedOnAxe(OB1, OB2, OB1.AxisY ^ OB2.AxisX)) return false;
    	if (!isSATFoundedOnAxe(OB1, OB2, OB1.AxisY ^ OB2.AxisY)) return false;
    	if (!isSATFoundedOnAxe(OB1, OB2, OB1.AxisY ^ OB2.AxisZ)) return false;
    
    	if (!isSATFoundedOnAxe(OB1, OB2, OB1.AxisZ ^ OB2.AxisX)) return false;
    	if (!isSATFoundedOnAxe(OB1, OB2, OB1.AxisZ ^ OB2.AxisY)) return false;
    	if (!isSATFoundedOnAxe(OB1, OB2, OB1.AxisZ ^ OB2.AxisZ)) return false;
    
    	return true;
    }