OBB intersection frustration (SAT)

Graphics and GPU Programming Programming

Started by cozzie August 19, 2018 09:22 PM

4 comments, last by cozzie 5 years, 8 months ago

cozzie

5,063

Author

August 19, 2018 09:22 PM

Hi all,

I've been struggling to get my OBB - OBB intersection test working, using the Separating Axis theorem.
After doing 2 different implementations, the 1st one always returns false, and the other implementation always returns true.

Debugging shows valid OBB input passed to the functions (verified by debug drawing the OBB's by the renderer).
Any input on what I might be doing wrong, is really appreciated.


bool CBaseCollision::OBBOBBIntersect(const CR_OBB &pOBB1, const CR_OBB &pOBB2)
{
	static CR_VECTOR3 rPos = pOBB2.Center - pOBB1.Center;
	
	CR_VECTOR3 xAxis1 = pOBB1.XHalfExtent;		xAxis1.Normalize();
	CR_VECTOR3 yAxis1 = pOBB1.YHalfExtent;		yAxis1.Normalize();
	CR_VECTOR3 zAxis1 = pOBB1.ZHalfExtent;		zAxis1.Normalize();
	CR_VECTOR3 xAxis2 = pOBB2.XHalfExtent;		xAxis2.Normalize();
	CR_VECTOR3 yAxis2 = pOBB2.YHalfExtent;		yAxis2.Normalize();
	CR_VECTOR3 zAxis2 = pOBB2.ZHalfExtent;		zAxis2.Normalize();

	if(	SeparatingPlaneExists(rPos, xAxis1, pOBB1, pOBB2) ||
		SeparatingPlaneExists(rPos, yAxis1, pOBB1, pOBB2) ||
		SeparatingPlaneExists(rPos, zAxis1, pOBB1, pOBB2) ||
		SeparatingPlaneExists(rPos, xAxis2, pOBB1, pOBB2) ||
		SeparatingPlaneExists(rPos, yAxis2, pOBB1, pOBB2) ||
		SeparatingPlaneExists(rPos, zAxis2, pOBB1, pOBB2) ||
		
		SeparatingPlaneExists(rPos, CMathHelper::CrossVec3(xAxis1, xAxis2), pOBB1, pOBB2) || 
		SeparatingPlaneExists(rPos, CMathHelper::CrossVec3(xAxis1, yAxis2), pOBB1, pOBB2) ||
		SeparatingPlaneExists(rPos, CMathHelper::CrossVec3(xAxis1, zAxis2), pOBB1, pOBB2) || 
		SeparatingPlaneExists(rPos, CMathHelper::CrossVec3(yAxis1, xAxis2), pOBB1, pOBB2) ||
		SeparatingPlaneExists(rPos, CMathHelper::CrossVec3(yAxis1, yAxis2), pOBB1, pOBB2) || 
		SeparatingPlaneExists(rPos, CMathHelper::CrossVec3(yAxis1, zAxis2), pOBB1, pOBB2) ||
		SeparatingPlaneExists(rPos, CMathHelper::CrossVec3(zAxis1, xAxis2), pOBB1, pOBB2) || 
		SeparatingPlaneExists(rPos, CMathHelper::CrossVec3(zAxis1, yAxis2), pOBB1, pOBB2) ||
		SeparatingPlaneExists(rPos, CMathHelper::CrossVec3(zAxis1, zAxis2), pOBB1, pOBB2)) return false;
	
	return true;
}

bool CBaseCollision::SeparatingPlaneExists(const CR_VECTOR3 &pPos, const CR_VECTOR3 &pAxis, const CR_OBB &pObb1, const CR_OBB &pObb2)
{
	float baseDist = fabs(CMathHelper::DotProductVec3(pPos, pAxis));

	float compDist = fabs(CMathHelper::DotProductVec3(pObb1.XHalfExtent, pAxis)) +
					 fabs(CMathHelper::DotProductVec3(pObb1.YHalfExtent, pAxis)) +
					 fabs(CMathHelper::DotProductVec3(pObb1.ZHalfExtent, pAxis)) +
					 fabs(CMathHelper::DotProductVec3(pObb2.XHalfExtent, pAxis)) +
					 fabs(CMathHelper::DotProductVec3(pObb2.YHalfExtent, pAxis)) +
					 fabs(CMathHelper::DotProductVec3(pObb2.ZHalfExtent, pAxis));
	
	return(baseDist > compDist);
}

Implementation 2, based on the Realtime collision book implementation:


bool CBaseCollision::OBBOBBIntersect(const CR_OBB &pOBB1, const CR_OBB &pOBB2)
{
	float ra, rb;
	CR_VECTOR3 u_obb1[3];
	CR_VECTOR3 u_obb2[3];

	u_obb1[0] = pOBB1.XHalfExtent;		u_obb1[0].Normalize();
	u_obb1[1] = pOBB1.YHalfExtent;		u_obb1[1].Normalize();
	u_obb1[2] = pOBB1.ZHalfExtent;		u_obb1[2].Normalize();

	u_obb2[0] = pOBB2.XHalfExtent;		u_obb2[0].Normalize();
	u_obb2[1] = pOBB2.YHalfExtent;		u_obb2[1].Normalize();
	u_obb2[2] = pOBB2.ZHalfExtent;		u_obb2[2].Normalize();

	float e_obb1[3] = { pOBB1.Extents.x, pOBB1.Extents.y, pOBB1.Extents.z };
	float e_obb2[3] = { pOBB2.Extents.x, pOBB2.Extents.y, pOBB2.Extents.z };

	// compute rotation matrix expressing OBB2 in OBB1's coordinate frame
	float tR[3][3];
	for(int i=0;i<3;++i)
	{
		for(int j=0;j<3;++j)
		{
			tR[i][j] = CMathHelper::DotProductVec3(u_obb1[i], u_obb2[j]);
		}
	}
	
	// compute translation vector t
	CR_VECTOR3 orgt = pOBB2.Center - pOBB1.Center;
	float t[3];

	// bring translation into 1's coordinate space
	t[0] = CMathHelper::DotProductVec3(orgt, u_obb1[0]);
	t[1] = CMathHelper::DotProductVec3(orgt, u_obb1[2]);
	t[2] = CMathHelper::DotProductVec3(orgt, u_obb1[2]);
	
	// compute common subexpressions. Add epsilon, to prevent cross product being 0 for parallel vectors
	float tAbsR[3][3];
	for(int i=0;i<3;++i)
	{
		for(int j=0;j<3;++j)
		{
			tAbsR[i][j] = abs(tR[i][j]) + 0.0002f;
		}
	}

	// test axes L = A0 / A1 / A2
	for(int i=0;i<3;++i)
	{
		ra = e_obb1[i];
		rb = e_obb2[0] * tAbsR[i][0] + e_obb2[1] * tAbsR[i][1] + e_obb2[2] * tAbsR[i][2];
		if(fabs(t[i]) > ra + rb) return false;
	}

	// test axes L = B0 / B1 / B2
	for(int i=0;i<3;++i)
	{
		ra = e_obb1[0] * tAbsR[0][i] + e_obb1[1] * tAbsR[1][i] + e_obb1[2] * tAbsR[2][i];
		rb = e_obb2[i];
		if(fabs(t[0] * tR[0][1] + t[1] * tR[1][i] + t[2] * tR[2][i]) > ra + rb) return false;
	}

	// Test axis L = A0 x B0
	ra = e_obb1[1] * tAbsR[2][0] + e_obb1[2] * tAbsR[1][0];
	rb = e_obb2[1] * tAbsR[0][2] + e_obb2[2] * tAbsR[0][1];
	if(fabs(t[2] * tR[1][0] - t[1] * tR[2][0]) > ra + rb) return false;

	// Test axis L = A0 x B1
	ra = e_obb1[1] * tAbsR[2][1] + e_obb1[2] * tAbsR[1][1];
	rb = e_obb2[0] * tAbsR[0][2] + e_obb2[2] * tAbsR[0][0];
	if(fabs(t[2] * tR[1][1] - t[1] * tR[2][1]) > ra + rb) return false;

	// Test axis L = A0 x B2
	ra = e_obb1[1] * tAbsR[2][2] + e_obb1[2] * tAbsR[1][2];
	rb = e_obb2[0] * tAbsR[0][1] + e_obb2[1] * tAbsR[0][0];
	if(fabs(t[2] * tR[1][2] - t[1] * tR[2][2]) > ra + rb) return false;

	// Test axis L = A1 x B0
	ra = e_obb1[0] * tAbsR[2][0] + e_obb1[2] * tAbsR[0][0];
	rb = e_obb2[1] * tAbsR[1][2] + e_obb2[2] * tAbsR[1][1];
	if(fabs(t[0] * tR[2][0] - t[2] * tR[0][0]) > ra + rb) return false;

	// Test axis L = A1 x B1
	ra = e_obb1[0] * tAbsR[2][1] + e_obb1[2] * tAbsR[0][1];
	rb = e_obb2[0] * tAbsR[1][2] + e_obb2[2] * tAbsR[1][0];
	if(fabs(t[0] * tR[2][1] - t[2] * tR[0][1]) > ra + rb) return false;

	// Test axis L = A1 x B2
	ra = e_obb1[0] * tAbsR[2][2] + e_obb1[2] * tAbsR[0][2];
	rb = e_obb2[0] * tAbsR[1][1] + e_obb2[1] * tAbsR[1][0];
	if(fabs(t[0] * tR[2][2] - t[2] * tR[0][2]) > ra + rb) return false;

	// Test axis L = A2 x B0
	ra = e_obb1[0] * tAbsR[1][0] + e_obb1[1] * tAbsR[0][0];
	rb = e_obb2[1] * tAbsR[2][2] + e_obb2[2] * tAbsR[2][1];
	if(fabs(t[1] * tR[0][0] - t[0] * tR[1][0]) > ra + rb) return false;

	// Test axis L = A2 x B1
	ra = e_obb1[0] * tAbsR[1][1] + e_obb1[1] * tAbsR[0][1];
	rb = e_obb2[0] * tAbsR[2][2] + e_obb2[2] * tAbsR[2][0];
	if(fabs(t[1] * tR[0][1] - t[0] * tR[1][1]) > ra + rb) return false;

	// Test axis L = A2 x B2
	ra = e_obb1[0] * tAbsR[1][2] + e_obb1[1] * tAbsR[0][2];
	rb = e_obb2[0] * tAbsR[2][1] + e_obb2[1] * tAbsR[2][0];
	if(fabs(t[1] * tR[0][2] - t[0] * tR[1][2]) > ra + rb) return false;

	return true;
}

Crealysm game & engine development: http://www.crealysm.com

Looking for a passionate, disciplined and structured producer? PM me

Zakwayda

2,389

August 20, 2018 01:42 AM

What's the length of the *HalfExtent vectors? 'Half extent' makes it sound like the length is half the box extent (which would be a quarter of the length along the respective axis), which doesn't sound right. Is the length of those vectors just the extent?

Although it's probably not the source of the problem, it shouldn't be necessary to normalize the box axes as you're doing, I don't think (I'm looking at the first test here).

Keep in mind that the cross-product axes can end up being arbitrarily short, which may cause numerical issues. This is accounted for in the second implementation, but not in the first.

If you haven't gotten the first implementation working yet, I'd try the following. Call the function with the same box for both arguments, so that the two boxes are coincident. If you get the correct result (true), that will show that the test doesn't actually fail in all cases, in which case you can try to narrow down the cases that do fail. Irrespective of that, once you find a case that fails (returns false when it should return true), use the debugger or logging to determine which axis is triggering the failure and what the relevant values are at that point. That should get you closer to identifying the problem.

Randy Gaul

2,835

August 20, 2018 02:09 AM

I'm a bit surprised copy + pasting Ericson's code doesn't work. Next step should probably be to debug render sub-expressions and start verifying lines you know to be correct, and take note of which ones you don't know to be correct.

cozzie

5,063

Author

August 20, 2018 06:44 AM

Thanks both, I'll try to debug and see what's returned for which axis I check.
My test case are 2 cubes with are besides each other (0, -3, 0 and 0, -3 and - 1.5), which are rotating in the same direction, meaning all axis's are parallel. This might be the reason why implementation 1 doesn't work (no epsilon correction for 0 cross product). I'll try this one first, since it's a quick fix/ test. Or the other way around, disable rotation for one of the two cubes, so I don't have the potential 'parallel' issue'.

@Randy Gaul true, but there's always a risk of copy/ pasting and making it 'fit' to my codebase.

Crealysm game & engine development: http://www.crealysm.com

Looking for a passionate, disciplined and structured producer? PM me

cozzie

5,063

Author

August 20, 2018 05:05 PM

Short update: managed to get the version as in Realtime collision, working. The issue was that the extents in my OBB werent half, multiplying by 0.5 solved that implementation.

In my testcase I also made one of the 2 cubes static, to check if the other implementation suffers from 0 cross product issues, but still doesn’t work. Now figuring out what else could be the cause. Any thoughts appreciated.

Other implementation also solved, static POS..... was only initialized once within the collision detection function.

Crealysm game & engine development: http://www.crealysm.com

Looking for a passionate, disciplined and structured producer? PM me

OBB intersection frustration (SAT)

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

OBB intersection frustration (SAT)

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines