Thread: [Algorithms] OBBs
Brought to you by:
vexxed72
Menu
▾
▴
gdalgorithms-list
|
From: <Nik...@ao...> - 2000-07-21 02:39:53
|
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.
Thanks,
Nik...@ao...
|
|
From: Kent Q. <ken...@co...> - 2000-07-21 12:35:00
|
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/ _____________________________|_________________________________________ |
|
From: Pierre T. <p.t...@wa...> - 2000-08-04 00:46:00
|
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 |
|
From: Kent Q. <ken...@co...> - 2000-08-06 10:25:31
|
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/ _____________________________|_________________________________________ |
|
From: Pierre T. <p.t...@wa...> - 2000-08-06 16:15:19
|
I'm afraid I don't get it. You told us about the matrix made of absolute values. That one actually is in the RAPID source, in the obb_disjoint function. And you said that taking the absolute values was too optimistic. So, why would it work within the RAPID code, if it doesn't work in theory according to you ? Confusing. ----- Original Message ----- From: Kent Quirk <ken...@co...> To: <gda...@li...> Sent: Sunday, August 06, 2000 7:19 AM Subject: Re: [Algorithms] OBBs > 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/ > _____________________________|_________________________________________ > > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list |
|
From: Kent Q. <ken...@co...> - 2000-08-07 02:46:37
|
I'm sorry. I don't have time right now to go back and dig up work from two years ago. I was trying to be helpful and point out that a) a long time ago, I had problems similar to those described, and b) I vaguely remember someone pointing out that THEY had discovered a problem. I hoped it was helpful. If it's not helpful to you, ignore it. That's all I can tell you right now. Pierre Terdiman wrote: > > I'm afraid I don't get it. > > You told us about the matrix made of absolute values. That one actually is > in the RAPID source, in the obb_disjoint function. And you said that taking > the absolute values was too optimistic. So, why would it work within the > RAPID code, if it doesn't work in theory according to you ? > > Confusing. > > ----- Original Message ----- > From: Kent Quirk <ken...@co...> > To: <gda...@li...> > Sent: Sunday, August 06, 2000 7:19 AM > Subject: Re: [Algorithms] OBBs > > > 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/ > > _____________________________|_________________________________________ > > > > _______________________________________________ > > 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/ _____________________________|_________________________________________ |
×
Want the latest updates on software, tech news, and AI?
Get latest updates about software, tech news, and AI from SourceForge directly in your inbox once a month.
Thanks for helping keep SourceForge clean.
X