Re: [Algorithms] OBBs

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

Because of the legal use restrictions I did not read the RAPID code, but
reconstructed my own code from the original paper. I was extremely
careful, and had the same problems described here -- certain
orientations of bounding boxes that were clearly intersecting would be
reported as disjoint. I even reconstructed it in a spreadsheet.

I have not gone back to see if I could make it work.

If you used the RAPID source, I believe it works properly.

	Kent


Pierre Terdiman wrote:
> 
> Are you sure about the fact it's invalid ? I would be very interested to
> know if this is true or not. This is weird because I've used Rapid without
> any problem.
> 
> ----- Original Message -----
> From: Kent Quirk <ken...@co...>
> To: <gda...@li...>
> Sent: Friday, July 21, 2000 2:33 PM
> Subject: Re: [Algorithms] OBBs
> 
> > 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/
> > _____________________________|_________________________________________
> >
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDA...@li...
> > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

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