Hi,

I've been struggling and reading and reading more about OBB-OBB intersection tests using the SAT theory.

Now, suddenly I thought of another solution.

- I can find if a point is inside a OBB (see the function below)

-- besides some basic math it requires 1 vector-matrix multiplication

- what if I take OBB A as a base, and pass the 8 points of OBB B to a the function that checks if a point is inside an OBB

-- if it is, I can quit early and I have intersection

-- if the 8 points are not inside, there's no intersection

For a full SAT test, I understood that I need at least 15 dot products and some more basic math.

The answer what would be quicker, would ofcourse only be answered with facts, by profiling.

But in general, would you think this approach sounds reasonable?

(accepting that I'm not able to pickup the SAT term theory fully and I don't want to copy/paste another solution)

Any input is appreciated.

bool PointInOBB(const OBB &pOBB, const XMFLOAT4X4 &pMatTransform, const XMFLOAT3 &pPoint)
{
	XMMATRIX xmTransform = XMLoadFloat4x4(&pMatTransform);
	XMMATRIX xmInverse = XMMatrixInverse(NULL, xmTransform);

	XMVECTOR point = XMLoadFloat3(&pPoint);
	XMFLOAT3 transformedPoint;
	XMVECTOR tempTransformed = XMVector3TransformCoord(point, xmInverse);
	
	XMStoreFloat3(&transformedPoint, tempTransformed);

	if( fabs(transformedPoint.x) < pOBB.Extents.x * 0.5f &&
		fabs(transformedPoint.y) < pOBB.Extents.y * 0.5f &&
		fabs(transformedPoint.z) < pOBB.Extents.z * 0.5f) return true;

	return false;
}

Use points alone is not sufficient to determine whether an object is in another. Consider this case in 2D:

A A

B B

A A

B B

None of the points in B is in A but the 2 objects are in fact colliding.

Thanks for the quick response, I fully understand what you mean. Didn't think of that.

Have to think of another solution now then..

I don't want to be mean or anything, but maybe save you some time. Intersecting two OBBs is a difficult mathematical topic. You need to see if any volume of A intersects any volume of B. This is why you cannot just test points, edges, or faces alone. The surface itself isn't enough, as overlapping volume is what defines an intersection.

In terms of efficiency brute force axis checking is likely to be the fastest method available, or if there's any other faster method it's only a marginal difference with a likely large leap in complexity along with some restrictive assumptions.

If you really want to learn the math involved in the brute force axis checking you can try this article: http://www.randygaul.net/2014/05/22/deriving-obb-to-obb-intersection-sat/

bool OBB3D::Overlap(OBB3D& other)
{
	
	D3DXMATRIX OtherMatrixInv = other.TransformMatrix;
	D3DXMatrixInverse(&OtherMatrixInv , 0 , &OtherMatrixInv);
	D3DXMATRIX FinalTransform = this->TransformMatrix*OtherMatrixInv;

	D3DXVECTOR3 OtherTransformedEdges[8];

	for(int i = 0 ; i < 8 ; ++i)
	{
		D3DXVec3TransformCoord(&OtherTransformedEdges[i] , &other.Edge[i] , &FinalTransform);
	}

	float	maxX = OtherTransformedEdges[0].x, minX = OtherTransformedEdges[0].x ,
			maxY = OtherTransformedEdges[0].y, minY = OtherTransformedEdges[0].y , 
			maxZ = OtherTransformedEdges[0].z, minZ = OtherTransformedEdges[0].z ;

	for(int i = 0 ; i < 8 ; ++i)
	{
		if(maxX < OtherTransformedEdges[i].x)maxX = OtherTransformedEdges[i].x;
		if(minX > OtherTransformedEdges[i].x)minX = OtherTransformedEdges[i].x;

		if(maxY < OtherTransformedEdges[i].y)maxY = OtherTransformedEdges[i].y;
		if(minY > OtherTransformedEdges[i].y)minY = OtherTransformedEdges[i].y;

		if(maxZ < OtherTransformedEdges[i].z)maxZ = OtherTransformedEdges[i].z;
		if(minZ > OtherTransformedEdges[i].z)minZ = OtherTransformedEdges[i].z;
	}

	if(	LineOverLap1D(maxX,minX,this->sx_/2,-this->sx_/2) && 
		LineOverLap1D(maxY,minY,this->sy_/2,-this->sy_/2) && 
		LineOverLap1D(maxZ,minZ,this->sz_/2,-this->sz_/2))
		return true;
	

	return false;
}

bool OBB3DCollide(OBB3D& b1 , OBB3D& b2)
{
	bool c1 = b1.Overlap(b2) , c2 = false;
	if(c1){ c2 = b2.Overlap(b1); }
	return c1 && c2;
}

This is code that i wrote ~7 years ago ( I no longer use it) but I think it works. Basically the code OBB3DCollide is the final function.
The idea is to make one of the boxes AABB (by adding the inverse transform to the other). After that you project all the edges from the OBB on the X, Y, Z axes and check if they overlap with the AABB. Do the same thing with the other box. If all the edges overlap with the AABB you have a collison.

Edge[N] is just all the lines that form that BBOX.

The name of the algorithm was "axis shadowing" (I guess?).

EDIT:

http://www.gamasutra.com/view/feature/131790/simple_intersection_tests_for_games.php?page=5

Coz, don't run from SAT. Stare it down and take it one step at time until you defeat it.

Try starting out with a pair of oriented squares.

1) Get the axes to test on by determining the normals of the faces.
2) Iterate through the axes and project the vertices of both shapes onto each axis, then look for overlap.
3) If you can find any axis that has no overlap then collision is false.
4) If all axes overlap then collision is true.

If you can get it in 2D then you should be able to extend it.

http://www.metanetsoftware.com/technique/diagrams/A2_aabb-tri_sepaxis.swf

(Interactive SAT demo from Metanet software.)

Here is the version of OBB-OBB intersection from MathGeoLib:

https://github.com/juj/MathGeoLib/blob/master/src/Geometry/OBB.cpp#L2445

The scalar C++ code follows Christer Ericson's book Real-Time Collision Detection, p. 101-106. The SIMDified version is of my own devising. If someone has a faster version, I'd be interested to know.