Not logged in, Join Here! or Log In Below:  
 
News Articles Search    
 

 Home / 3D Theory & Graphics / OBB minimum distance test Account Manager
 
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.
 
shengfu

April 19, 2005, 10:39 AM

In my application, I need to test if the minimum distance between two OBBs is less than a given tolerance(E). OBB overlap can be considered as a special case when E is equal to zero.

Separating axis theorem tells us that if two OBBs are not intersected iif there exists an separating axis among 15 axis. So the projection of two OBBs onto the axis are examined to see if the projection is overlap or not. In my case, instead of checking the overlap, I check if the distance between the two projections are less than the tolerance(E) or not.

It seems a very natural extend of the original theorem, but I don't it's true or not.

Anybody can give me some idea?

Thanks

Sheng Fu
UGS PLM

 
Marmakoide

April 19, 2005, 12:53 PM

That's all true !!! Big coincidence, I've just finish my OBB intersection test routine yesterday... The reference for this method is "OBB Tree : A Hiearchical Structure for Rapid Interference Detection" by S. Gottschalk, M. C. Lin D. Manocha. A working implementation is provided "http://www.geometrictools.com". Find your distance will be very straigth forward from this code.

[PS] Are you Chinese ? I'am searching for some Chinese students or professors in computer science, to ask some questions...

 
shengfu

April 19, 2005, 01:07 PM

I have read that paper and also implemented that algorithm. I can't find the code in http://www.geometrictools.com. Could you send me the URL?

Yes, I am Chinese. What question do you have?

Thanks

Sheng

 
Marmakoide

April 19, 2005, 01:29 PM

Go to
http://www.geometrictools.com/Intersection.html
Then click on this link
Wm3IntrBox3Box3.cpp

For my question, it's not the right place... I will send you a mail

 
olivierr

April 20, 2005, 06:47 PM

you have to be careful because the projections are scaled by the length of the projection axis.

What you can do us calculate the MTD, by multiplying the projection overlap (or separation) by the axis itself and dividing by the square of the axis length. Something like that...

  1.  
  2. bool Intersect(OBB BoxA, OBB BoxB, Vector& MTD)
  3. {
  4. float mindist2 = -1;
  5. MTD = Vector(0, 0, 0);
  6.  
  7. // 15 sep axes.
  8. for(int i = 0; i < 15; i ++)
  9. {
  10.     Vector Axis = GetSepAxis(i, BoxA, BoxB);
  11.  
  12.     float a2 = Axis.Dot(Axis);
  13.  
  14.     if (a2 < 1.0E-7f)
  15.     {
  16.         continue;
  17.     }
  18.  
  19.     float mina, maxa;
  20.     float minb, maxb;
  21.     BoxA.CalculateInterval(Axis, mina, maxa);
  22.     BoxB.CalculateInterval(Axis, minb, maxb);
  23.     float d0 = mina - maxb;
  24.     float d1 = maxa - minb;
  25.    
  26.     if (d0 > 0 || d1 < 0)
  27.     {
  28.          return false; // no overlap
  29.     }
  30.    
  31.     float d = (-d0 < d1)? d0 : d1;
  32.  
  33.     Vector Sep = Axis * (d / a2);
  34.     float s2 = Sep.Dot(Sep);
  35.    
  36.     if (mindist2 < 0 || s2 < mindist2)
  37.     {
  38.         mindist2 = s2;
  39.         MTD = Sep;
  40.     }
  41. }    
  42.  
  43. return true;
  44. }
  45.  


that would be for an intersection, but for a mindist, you have to be careful, I don't thing the SAT can be used in the same way, or only to get an approximation of distance.

 
This thread contains 5 messages.
 
 
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.