Collision detection is based on the book, RTCD. It detects a collision when there's not. Any thoughts???

bool OBB_OBB_Intersection(OBB* A, OBB* B, float& s)
{
	float ra, rb;
	XMMATRIX R, AbsR;

	// Compute rotation matrix expressing b in a’s coordinate frame
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			R.r[i].m128_f32[j] = XMVector3Dot(A->GetOrientation().r[i], B->GetOrientation().r[i]).m128_f32[0];

	// Compute translation vector t
	XMVECTOR t = (XMLoadFloat3(&B->GetCenter()) - XMLoadFloat3(&A->GetCenter()));
	// Bring translation into a’s coordinate frame
	t = XMVectorSet(XMVector3Dot(t, A->GetOrientation().r[0]).m128_f32[0], XMVector3Dot(t, A->GetOrientation().r[1]).m128_f32[0], XMVector3Dot(t, A->GetOrientation().r[2]).m128_f32[0], 1.0f);

	// Compute common subexpressions. Add in an epsilon term to
	// counteract arithmetic errors when two edges are parallel and
	// their cross product is (near) null
	const float EPSILON = 1.0e-6f;
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			AbsR.r[i].m128_f32[j] = abs(R.r[i].m128_f32[j]) + EPSILON;

	// Test axes L = A0, L = A1, L = A2
	for (int i = 0; i < 3; i++)
	{
		ra = XMLoadFloat3(&A->GetExtents()).m128_f32[i];
		rb = B->GetExtents().x * AbsR.r[i].m128_f32[0] + B->GetExtents().y * AbsR.r[i].m128_f32[1] + B->GetExtents().z * AbsR.r[i].m128_f32[2];
		if (abs(t.m128_f32[i]) > ra + rb) return false;
		s = abs(t.m128_f32[i]) - (ra + rb);
	}

	// Test axes L = B0, L = B1, L = B2
	for (int i = 0; i < 3; i++)
	{
		ra = A->GetExtents().x * AbsR.r[0].m128_f32[i] + A->GetExtents().y * AbsR.r[1].m128_f32[i] + A->GetExtents().z * AbsR.r[2].m128_f32[i];
		rb = XMLoadFloat3(&B->GetExtents()).m128_f32[i];
		if (abs(t.m128_f32[0] * R.r[0].m128_f32[i] + t.m128_f32[1] * R.r[1].m128_f32[i] + t.m128_f32[2] * R.r[2].m128_f32[i]) > ra + rb) return false;
		s = abs(t.m128_f32[0] * R.r[0].m128_f32[i] + t.m128_f32[1] * R.r[1].m128_f32[i] + t.m128_f32[2] * R.r[2].m128_f32[i]) - (ra + rb);
	}

	// Test axis L = A0 x B0
	ra = A->GetExtents().y * AbsR.r[2].m128_f32[0] + A->GetExtents().z * AbsR.r[1].m128_f32[0];
	rb = B->GetExtents().y * AbsR.r[0].m128_f32[2] + B->GetExtents().z * AbsR.r[0].m128_f32[1];
	if (abs(t.m128_f32[2] * R.r[1].m128_f32[0] - t.m128_f32[1] * R.r[2].m128_f32[0]) > ra + rb) return false;
	s = abs(t.m128_f32[2] * R.r[1].m128_f32[0] - t.m128_f32[1] * R.r[2].m128_f32[0]) - (ra + rb);

	// Test axis L = A0 x B1
	ra = A->GetExtents().y * AbsR.r[2].m128_f32[1] + A->GetExtents().z * AbsR.r[1].m128_f32[1];
	rb = B->GetExtents().x * AbsR.r[0].m128_f32[2] + B->GetExtents().z * AbsR.r[0].m128_f32[0];
	if (abs(t.m128_f32[2] * R.r[1].m128_f32[1] - t.m128_f32[1] * R.r[2].m128_f32[1]) > ra + rb) return false;
	s = abs(t.m128_f32[2] * R.r[1].m128_f32[1] - t.m128_f32[1] * R.r[2].m128_f32[1]) - (ra + rb);

	// Test axis L = A0 x B2
	ra = A->GetExtents().y * AbsR.r[2].m128_f32[2] + A->GetExtents().z * AbsR.r[1].m128_f32[2];
	rb = B->GetExtents().x * AbsR.r[0].m128_f32[1] + B->GetExtents().y * AbsR.r[0].m128_f32[0];
	if (abs(t.m128_f32[2] * R.r[1].m128_f32[2] - t.m128_f32[1] * R.r[2].m128_f32[2]) > ra + rb) return false;
	s = abs(t.m128_f32[2] * R.r[1].m128_f32[2] - t.m128_f32[1] * R.r[2].m128_f32[2]) - (ra + rb);

	// Test axis L = A1 x B0
	ra = A->GetExtents().x * AbsR.r[2].m128_f32[0] + A->GetExtents().z * AbsR.r[0].m128_f32[0];
	rb = B->GetExtents().y * AbsR.r[1].m128_f32[2] + B->GetExtents().z * AbsR.r[1].m128_f32[1];
	if (abs(t.m128_f32[0] * R.r[2].m128_f32[0] - t.m128_f32[2] * R.r[0].m128_f32[0]) > ra + rb) return false;
	s = abs(t.m128_f32[0] * R.r[2].m128_f32[0] - t.m128_f32[2] * R.r[0].m128_f32[0]) - (ra + rb);

	// Test axis L = A1 x B1
	ra = A->GetExtents().x * AbsR.r[2].m128_f32[1] + A->GetExtents().z * AbsR.r[0].m128_f32[1];
	rb = B->GetExtents().x * AbsR.r[1].m128_f32[2] + B->GetExtents().z * AbsR.r[1].m128_f32[0];
	if (abs(t.m128_f32[0] * R.r[2].m128_f32[1] - t.m128_f32[2] * R.r[0].m128_f32[1]) > ra + rb) return false;
	s = abs(t.m128_f32[0] * R.r[2].m128_f32[1] - t.m128_f32[2] * R.r[0].m128_f32[1]) - (ra + rb);

	// Test axis L = A1 x B2
	ra = A->GetExtents().x * AbsR.r[2].m128_f32[2] + A->GetExtents().z * AbsR.r[0].m128_f32[2];
	rb = B->GetExtents().x * AbsR.r[1].m128_f32[1] + B->GetExtents().y * AbsR.r[1].m128_f32[0];
	if (abs(t.m128_f32[0] * R.r[2].m128_f32[2] - t.m128_f32[2] * R.r[0].m128_f32[2]) > ra + rb) return false;
	s = abs(t.m128_f32[0] * R.r[2].m128_f32[2] - t.m128_f32[2] * R.r[0].m128_f32[2]) - (ra + rb);

	// Test axis L = A2 x B0
	ra = A->GetExtents().x * AbsR.r[1].m128_f32[0] + A->GetExtents().y * AbsR.r[0].m128_f32[0];
	rb = B->GetExtents().y * AbsR.r[2].m128_f32[2] + B->GetExtents().z * AbsR.r[2].m128_f32[1];
	if (abs(t.m128_f32[1] * R.r[0].m128_f32[0] - t.m128_f32[0] * R.r[1].m128_f32[0]) > ra + rb) return false;
	s = abs(t.m128_f32[1] * R.r[0].m128_f32[0] - t.m128_f32[0] * R.r[1].m128_f32[0]) - (ra + rb);

	// Test axis L = A2 x B1
	ra = A->GetExtents().x * AbsR.r[1].m128_f32[1] + A->GetExtents().y * AbsR.r[0].m128_f32[1];
	rb = B->GetExtents().x * AbsR.r[2].m128_f32[2] + B->GetExtents().z * AbsR.r[2].m128_f32[0];
	if (abs(t.m128_f32[1] * R.r[0].m128_f32[1] - t.m128_f32[0] * R.r[1].m128_f32[1]) > ra + rb) return false;
	s = abs(t.m128_f32[1] * R.r[0].m128_f32[1] - t.m128_f32[0] * R.r[1].m128_f32[1]) - (ra + rb);

	// Test axis L = A2 x B2
	ra = A->GetExtents().x * AbsR.r[1].m128_f32[2] + A->GetExtents().y * AbsR.r[0].m128_f32[2];
	rb = B->GetExtents().x * AbsR.r[2].m128_f32[1] + B->GetExtents().y * AbsR.r[2].m128_f32[0];
	if (abs(t.m128_f32[1] * R.r[0].m128_f32[2] - t.m128_f32[0] * R.r[1].m128_f32[2]) > ra + rb) return false;
	s = abs(t.m128_f32[1] * R.r[0].m128_f32[2] - t.m128_f32[0] * R.r[1].m128_f32[2]) - (ra + rb);
  
  // Since no separating axis is found, the OBBs must be intersecting
	return true;
}


int main()
{
	float sep;
	OBB objA(XMFLOAT3(0,10,10),XMFLOAT3(.5f,.5f,.5f), XMMatrixRotationY(0)), objB(XMFLOAT3(0,11.8f,10.0f),XMFLOAT3(.5f,.5f,.5f), XMMatrixRotationY(0));
	if (OBB_OBB_Intersection(&objA, &objB, sep))
		cout << "intersecting is found; a separation" << sep << endl;
	system("pause");
	return 0;
}

OBB.cpp

OBB.h

5 hours ago, isu diss said:

Any thoughts???

Here are some thoughts (in no particular order).

- I think the book is pretty reliable, so I'd be surprised if there were an error. You might look for errata online though, just to be sure.

- Your input is a configuration that could, I think, be vulnerable to numerical error. This could throw off an implementation that doesn't account for such error, but the implementation you're using does, so it seems unlikely that that's the problem.

- When the SAT for oriented boxes is 'unrolled' (generally for efficiency), it becomes much harder to debug and analyze than it would be in a more intuitive form (in my opinion). The implementation you posted, for example, offers many opportunities for typos, copy-and-paste errors, etc., any one of which could throw off the results. Obviously you could double-check your implementation against the source (tedious as that may be) to try to find such errors.

- I don't know if what you have there is a copy-paste or your own recreation, but if the latter, you could try copy-pasting and just making the minimal changes needed to compile in your environment. If that worked but yours doesn't, that could provide a hint as to where the problem is.

- The SAT for oriented boxes expressed in unoptimized form may be less efficient, but it's much simpler. If you understand the SAT well enough, you could implement a simple version and see if that works. That might provide some useful information.

- Arguably, any common mathematical operations such as matrix or matrix-vector multiplications shouldn't be implemented in place, but rather should be factored out and tested in isolation. That could reduce the potential problem areas somewhat. (This would apply, at minimum, to computing the local rotation matrix and translation vector.)

- Lastly, I'll offer the fairly obvious suggestion of using the debugger. What you observe might be hard to interpret due to the unrolling, but you might still be able to spot where things are going wrong (in particular, you know which axes should be separating axes, so if you get past one of those conditionals you'll have some idea of where the problem is).

I dont know what obb is i think its object oriented bounding box which aint aabb of the object but it follows its rotation matrix, i have a solution for this, once you calculate all vertices,.side normals.and distances you can test if one overlaps another it doesnt shoot out any collision lines etc.

bool Overlaps(TachoGLModel<T> * with)
{
TachoGLModel<T> * A = this;
TachoGLModel<T> * B = with;
//to overlap there must be at least one side / other face intersection

	for (int i=0; i < FaceLength; i++)
	{
bool overlapsf = false;
		for (int v=0; v < with->header.LENGTH; v++) //for each vertex in obb
		{
		int vside = classifyapointagainstaplane( with->AOS[v].v, FACE_N[i], FACE_DISTANCE[i] );

		if ( ( vside == isBack ) || (vside == isOnPlane) )
		{
		overlapsf = true;
		break;
		}
		
		}
		
		if (!overlapsf) return false;
		
	}

	//whenever we got here we need to test other model

	
	for (int i=0; i < with->FaceLength; i++)
	{

bool overlapsf = false;
		for (int v=0; v < header.LENGTH; v++)
		{
		int vside = classifyapointagainstaplane( AOS[v].v, with->FACE_N[i], with->FACE_DISTANCE[i] );

		if ( ( vside == isBack ) || (vside == isOnPlane) )
		{
		overlapsf = true;
		break;
		}
		
		}
		
		if (!overlapsf) return false;
		
	}

	return true;
}

1 hour ago, _WeirdCat_ said:

I dont know what obb is i think its object oriented bounding box which aint aabb of the object but it follows its rotation matrix, i have a solution for this, once you calculate all vertices,.side normals.and distances you can test if one overlaps another it doesnt shoot out any collision lines etc.

 

bool Overlaps(TachoGLModel<T> * with)
{
TachoGLModel<T> * A = this;
TachoGLModel<T> * B = with;
//to overlap there must be at least one side / other face intersection

	for (int i=0; i < FaceLength; i++)
	{
bool overlapsf = false;
		for (int v=0; v < with->header.LENGTH; v++) //for each vertex in obb
		{
		int vside = classifyapointagainstaplane( with->AOS[v].v, FACE_N[i], FACE_DISTANCE[i] );

		if ( ( vside == isBack ) || (vside == isOnPlane) )
		{
		overlapsf = true;
		break;
		}
		
		}
		
		if (!overlapsf) return false;
		
	}

	//whenever we got here we need to test other model

	
	for (int i=0; i < with->FaceLength; i++)
	{

bool overlapsf = false;
		for (int v=0; v < header.LENGTH; v++)
		{
		int vside = classifyapointagainstaplane( AOS[v].v, with->FACE_N[i], with->FACE_DISTANCE[i] );

		if ( ( vside == isBack ) || (vside == isOnPlane) )
		{
		overlapsf = true;
		break;
		}
		
		}
		
		if (!overlapsf) return false;
		
	}

	return true;
}

 

I don't think that test is correct. Based on a quick look, it appears to be a partial separating axis test, but it doesn't check cross-product axes.

The non-intersection configurations that the cross-product axis tests detect don't necessarily come up in practice that often, so you could easily test your code with various configurations and have it appear to work. But I think it's not actually correct. To correctly classify all configurations, you need to include all 15 axes (as the OP's code does).

Found one bug 

const float EPSILON = 1.0e-6f;

Seems that you cant compare something that is less than 0.001

I'll try to explain twisted logic behind this, i've studied this few times always with the same result: consider all faces point outside of the shape,

(Test A against B) Through A faces, check whenever all B shape vertices lie in front of this face if yes then theres no intersection at all (return false) if first test passes then you test B against A to see if all of A vertices lie in front of any B face, otherwise it overlaps.

24 minutes ago, _WeirdCat_ said:

Ill try to explain twisted logic behind this, i've studied this few times always with the same result: consider all faces point outside of the shape,

(Test A against B) Through A faces, check whenever all B shape vertices lie in front of this face if yes then theres no intersection at all (return false) if first test passes then you test B against A to see if all of A vertices lie in front of any B face, otherwise it overlaps.

Yeah, I'm familiar with the algorithm (nice diagrams by the way!). And it works more or less as you describe for 2-d.

The problem is that the OP is performing the test in 3-d, and in 3-d you have to test additional axes to cover all possible configurations. So although your test may be correct for 2-d, it doesn't (fully) address the specific problem under discussion.

Its a 3d thing i just made screenshots of one projection, so one can see it, this stays true for 3d too. These shapes are actually 3d objects, however guy has too low EPSILON when comparing floats he should use 0.001 as epsilon

17 minutes ago, _WeirdCat_ said:

Its a 3d thing i just made screenshots of one projection, so one can see it, this stays true for 3d too.

Ok, in that case, the code you posted is incomplete. It'll return the correct results for some configurations, but will return false positives for others. (As I mentioned earlier those other configurations don't necessarily come up often in practice, so such an implementation can appear to work reliably even though it's incomplete.)

It's also worth noting that while your code is a general-purpose solution for arbitrary convex polytopes, the test for oriented boxes can be implemented more efficiently by exploiting the regularity of the shape (the code the OP posted is an example of this).

W went off topic but if you find any case where this test fails let me know, maybe we have different assumptions or the code is bad and i don't know it.

1 hour ago, _WeirdCat_ said:

W went off topic but if you find any case where this test fails let me know, maybe we have different assumptions or the code is bad and i don't know it.

This exact issue is discussed in this thread. It goes into considerable detail, and even provides a nicely illustrated example of a failure case.