Re: [Algorithms] OBBs

[Kent Q. <ken...@co...>]

Nik...@ao... wrote:
> I recently finished writing a collision detection system for my engine (using
> OBBs); however I have been having trouble with the system not always
> detecting collisions.  I tested all of the functions separately to confirm
> their accuracy; yet this brought no avail.  I decided to work backwards to
> find the bug, and I used a function from the RAPID library which tests for
> disjointedness between two boxes.  Here is the description of the function:
> 
> This is a test between two boxes, box A and box B.  It is assumed that
> the coordinate system is aligned and centered on box A.  The 3x3
> matrix B specifies box B's orientation with respect to box A.
> Specifically, the columns of B are the basis vectors (axis vectors) of
> box B.  The center of box B is located at the vector T.  The
> dimensions of box B are given in the array b.  The orientation and
> placement of box A, in this coordinate system, are the identity matrix
> and zero vector, respectively, so they need not be specified.  The
> dimensions of box A are given in array a.
>     obb_disjoint(double B[3][3], double T[3], double a[3], double b[3]);
> 
> I set up a situation in Max using two boxes, in which the collision detection
> failed, and I then entered the box data in by hand.  The result was that
> after putting box 2 in box 1's coordinate system, the matrix B was a 128
> degree rotation around the Z axis (or Max's Y axis).  The location of box 2
> in relation to box 1 was:
>     T[0]= -5.853f;
>     T[1]= -2.173f;
>     T[2]= 3.842f;
> And the dimensions (half-lengths) were:
>     Bd[0]= 2;  Bd[1]= 4; Bd[2]= 4.5;
>     Ad[0]= 4;  Ad[1]= 1; Ad[2]= 7.5;
> If you set this situation up in Max, it is obvious that the two boxes
> intersect (make sure to switch the Y & Z coordinates because of the
> difference in D3D and Max's CS, and multiply the half-lengths by 2 to get the
> actual dimensions).  Yet, RAPID's function reports that the boxes are
> disjoint.  Any help would be appreciated.

I too struggled with this for a long time. 

After I had given up, and gone to another collision system, someone else
reported that RAPID's OBB intersection algorithm (as documented) is too
optimistic in its use of absolute value. There is a matrix in the code
that gets built as the absolute values of another matrix, thereby saving
some steps...but that's an invalid savings.  Sadly, I can't find the
reference. But I hope this points you in the right direction, or perhaps
someone else has a better memory.

	Kent

-- 
-----------------------------------------------------------------------
Kent Quirk                   | CogniToy: Intelligent toys...
Game Designer                |           for intelligent minds.
ken...@co...      | http://www.cognitoy.com/     
_____________________________|_________________________________________