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.
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
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?
Actually to answer my own question… yes.
200 scene objects… test against 1 box.
Intersects() 1ms
SAT = 12ms
First intersects then SAT = 6ms
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.
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));
}
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?
another issue with mxs and trees is trees like recursion and mxs doesn’t
funny thing is that even non-recursive tree building algorithms are only twice as fast
only twice as fast as what exactly ?
Twice as fast as its recursive counterpart. I’m talking about tree building performance only