Do 2 BoundingBoxes Intersect


#1

Has anyone got a snippet for testing if 2 bounding boxes intersect?

Intersects() operates on grid-space… so if the objects are rotated you can get false-positives as the bounding box will be world-orientated.


#2

think SAT is your best bet

the c++ example assumes the position is at the center of the box and half size is 0.5 *(len, width,height)

could look something like this in mxs

(

	fn splane d pnorm tm1 hw1 tm2 hw2 =
	(
			abs (dot d pnorm) > abs (dot (tm1[1] * hw1.x) pnorm) + abs (dot (tm1[2] * hw1.y) pnorm) + 
						abs (dot (tm1[3] * hw1.z) pnorm)  + abs (dot (tm2[1] * hw2.x) pnorm) + 
						abs (dot (tm2[2] * hw2.y) pnorm) +  abs (dot (tm2[3] * hw2.z) pnorm);
	)	


	fn test_obb_vs_obb obj1 obj2 =
	(
		tm1 = obj1.transform;
		bbox = nodeGetBoundingBox obj1 tm1;
		hw1 = (bbox[2] - bbox[1]) * 0.5;
		bbox = nodeLocalBoundingBox obj1;
		tm1.translation =  (bbox[1] + bbox[2]) * 0.5; 
		
		tm2 = obj2.transform;
		bbox = nodeGetBoundingBox obj2 tm2;
		hw2 = (bbox[2] - bbox[1]) * 0.5;
		bbox = nodeLocalBoundingBox obj2;
		tm2.translation =  (bbox[1] + bbox[2]) * 0.5; 
		
		d = tm2.translation	- tm1.translation;
		
		not (splane d tm1[1] tm1 hw1 tm2 hw2 or splane d tm1[2] tm1 hw1 tm2 hw2 or splane d tm1[3] tm1 hw1 tm2 hw2 or
		splane d tm2[1] tm1 hw1 tm2 hw2 or splane d tm2[2] tm1 hw1 tm2 hw2 or splane d tm2[3] tm1 hw1 tm2 hw2 or
		splane d  (cross tm1[1] tm2[1]) tm1 hw1 tm2 hw2 or splane d  (cross tm1[1] tm2[2]) tm1 hw1 tm2 hw2 or
		splane d  (cross tm1[1] tm2[3]) tm1 hw1 tm2 hw2 or splane d  (cross tm1[2] tm2[1]) tm1 hw1 tm2 hw2 or
		splane d  (cross tm1[2] tm2[2]) tm1 hw1 tm2 hw2 or splane d  (cross tm1[2] tm2[3]) tm1 hw1 tm2 hw2 or
		splane d  (cross tm1[3] tm2[1]) tm1 hw1 tm2 hw2 or splane d  (cross tm1[3] tm2[2]) tm1 hw1 tm2 hw2 or
		splane d  (cross tm1[3] tm2[3]) tm1 hw1 tm2 hw2);
	)	
	
	test_obb_vs_obb $box01 $box02

)	

don’t think it would hold up to any serious computation stress speed wise but obb vs obb is probably the least trivial of primitive intersections. There’s a slightly more efficient varian t in real time collisions but it seems to have an error in it :confused:


#3

That’s awesome! What do you think would work better on a large scene example?
run intersects() first then this test to confirm? or just the latter?


#4

Actually to answer my own question… yes.

200 scene objects… test against 1 box.
Intersects() 1ms
SAT = 12ms

First intersects then SAT = 6ms


#5

this is the alternate version (in c++) if anyones interested

struct OBB
{
	Matrix3	tm;
    Point3	hsize;

	OBB() : tm(TRUE), hsize(0.0f,0.0f,0.0f) {}
	OBB(TimeValue t, INode* node) : tm(TRUE), hsize(0.0f,0.0f,0.0f) 
	{
		if(!node) return;
		Object* obj = node->GetObjectRef();
		if(!obj) return;

		tm = node->GetNodeTM(t);
		Box3 box;
		obj->GetDeformBBox(t, box);

		hsize = 0.5f * (box.pmax - box.pmin);
		tm.SetTrans((0.5f * (box.pmax + box.pmin)) * tm);
	}
};


#ifndef EPSILON
	#define EPSILON		1e-4f
#endif

static int OBBvsOBB(OBB &a, OBB &b)
{
	float ra, rb, R[3][3], AbsR[3][3];

	for(int i = 0; i < 3; ++i)
		for(int j = 0; j < 3; ++j)
			R[i][j] = DotProd(a.tm[i], b.tm[j]);

	Point3 d = b.tm[3] - a.tm[3];
	Point3 t = Point3(DotProd(d, a.tm[0]), DotProd(d, a.tm[1]), DotProd(d, a.tm[2]));

	for(int i = 0; i < 3; ++i)
		for(int j = 0; j < 3; ++j)
			AbsR[i][j] = fabs(R[i][j]) + EPSILON;

	for(int i = 0; i < 3; ++i) 
	{
		ra = a.hsize[i];
		rb = b.hsize[0] * AbsR[i][0] + b.hsize[1] * AbsR[i][1] + b.hsize[2] * AbsR[i][2];
		if(fabs(t[i]) > ra + rb) return 0;
	}

	for(int i = 0; i < 3; ++i) 
	{
		ra = a.hsize[0] * AbsR[0][i] + a.hsize[1] * AbsR[1][i] + a.hsize[2] * AbsR[2][i];
		rb = b.hsize[i];
		if(fabs(t[0] * R[0][i] + t[1] * R[1][i] + t[2] * R[2][i]) > ra + rb) return 0;
	}

	ra = a.hsize[1] * AbsR[2][0] + a.hsize[2] * AbsR[1][0];
	rb = b.hsize[1] * AbsR[0][2] + b.hsize[2] * AbsR[0][1];
	if(fabs(t[2] * R[1][0] - t[1] * R[2][0]) > ra + rb) return 0;

	ra = a.hsize[1] * AbsR[2][1] + a.hsize[2] * AbsR[1][1];
	rb = b.hsize[0] * AbsR[0][2] + b.hsize[2] * AbsR[0][0];
	if(fabs(t[2] * R[1][1] - t[1] * R[2][1]) > ra + rb) return 0;

	ra = a.hsize[1] * AbsR[2][2] + a.hsize[2] * AbsR[1][2];
	rb = b.hsize[0] * AbsR[0][1] + b.hsize[1] * AbsR[0][0];
	if(fabs(t[2] * R[1][2] - t[1] * R[2][2]) > ra + rb)  return 0;

	ra = a.hsize[0] * AbsR[2][0] + a.hsize[2] * AbsR[0][0];
	rb = b.hsize[1] * AbsR[1][2] + b.hsize[2] * AbsR[1][1];
	if(fabs(t[0] * R[2][0] - t[2] * R[0][0]) > ra + rb)  return 0;

	ra = a.hsize[0] * AbsR[2][1] + a.hsize[2] * AbsR[0][1];
	rb = b.hsize[0] * AbsR[1][2] + b.hsize[2] * AbsR[1][0];
	if(fabs(t[0] * R[2][1] - t[2] * R[0][1]) > ra + rb) return 0;

	ra = a.hsize[0] * AbsR[2][2] + a.hsize[2] * AbsR[0][2];
	rb = b.hsize[0] * AbsR[1][1] + b.hsize[1] * AbsR[1][0];
	if(fabs(t[0] * R[2][2] - t[2] * R[0][2]) > ra + rb) return 0;

	ra = a.hsize[0] * AbsR[1][0] + a.hsize[1] * AbsR[0][0];
	rb = b.hsize[1] * AbsR[2][2] + b.hsize[2] * AbsR[2][1];
	if(fabs(t[1] * R[0][0] - t[0] * R[1][0]) > ra + rb) return 0;

	ra = a.hsize[0] * AbsR[1][1] + a.hsize[1] * AbsR[0][1];
	rb = b.hsize[0] * AbsR[2][2] + b.hsize[2] * AbsR[2][0];
	if(fabs(t[1] * R[0][1] - t[0] * R[1][1]) > ra + rb) return 0;

	ra = a.hsize[0] * AbsR[1][2] + a.hsize[1] * AbsR[0][2];
	rb = b.hsize[0] * AbsR[2][1] + b.hsize[1] * AbsR[2][0];
	if(fabs(t[1] * R[0][2] - t[0] * R[1][2]) > ra + rb)  return 0;

	return 1;
}

//**************************************************************************************************

def_visible_primitive(OBB_vs_OBB , "OBB_vs_OBB");

Value* OBB_vs_OBB_cf(Value** arg_list, int count)
{
	enum args { knode1, knode2, knum_args };

	check_arg_count(OBB_vs_OBB, knum_args, count);

	TimeValue t = MAXScript_time();
	OBB obb1(t, arg_list[knode1]->to_node()), obb2(t, arg_list[knode2]->to_node());

	return bool_result(OBBvsOBB(obb1, obb2));
}

#6

if you need to check intersection with a lot of boxes (or some against all), you have to use some “tree” algorithms.
R-Tree works good for me.


#7

I once made a maxscript kdtree for a nearest neighbor search, but it was terribly slow to build a tree from points (queries were fast enough) so it wasn’t practical at all. Uniform grid is the only acceleration structure I had no trouble with in maxscript. Does anyone has positive experience with these trees in mxs?


#8

another issue with mxs and trees is trees like recursion and mxs doesn’t :wink:


#9

funny thing is that even non-recursive tree building algorithms are only twice as fast


#10

only twice as fast as what exactly ?


#11

Twice as fast as its recursive counterpart. I’m talking about tree building performance only


#12

not even close i’m afraid…

Untitled-1

and the kdtree is also finding the median during the build… also the qkdtree seems to have a clean up issue :confused:


#13

Thanks for testing it!
Should have mentioned that I only borrowed the build algorithm idea and did my tests in mxs version of kdtree. And this non-recursive approach performs a little better but still not good enough. I posted my code in another thread


#14

the “likes recursion” wasn’t really a reference to performance but the way it (trees) lends its self to the coding