[ggt-devel] [ ggt-Bugs-1523709 ] intersect function mistake

[SourceForge.net <no...@so...>]

Bugs item #1523709, was opened at 2006-07-17 02:56
Message generated for change (Comment added) made by patrickh
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=437247&aid=1523709&group_id=43735

Please note that this message will contain a full copy of the comment thread,
including the initial issue submission, for this request,
not just the latest update.
Category: GMTL
Group: None
Status: Open
Resolution: None
Priority: 5
Private: No
Submitted By: Neonic (aneonic)
>Assigned to: Patrick Hartling (patrickh)
Summary: intersect function mistake

Initial Comment:
Good time.
my english not so easy, because i am not finished learn...
but i try to help you in development of gmtl library.

i work on collision detection part of RGDE engine,
where as a part of
math we use gmtl. One function, as i found, writed
complexly wrong,
mistake placed right in source point:

   template<class DATA_TYPE>
   bool intersect( const AABox<DATA_TYPE>& box1, const
Vec<DATA_TYPE, 3>& path1,
                   const AABox<DATA_TYPE>& box2, const
Vec<DATA_TYPE, 3>& path2,
                   DATA_TYPE& firstContact, DATA_TYPE&
secondContact )

where is error? look:
in code we step by step do some tests...
1) we test box intesection at start point. whats write
& more simple
then next code.
2) we test... oops, what we test next in loop? it
seems, what we test
those boxes again, but with the little changes. we add
path existance
to test. Yes, we need to test path, but also we need to
test DYNAMIC
box. there dynamic is new box, created by our box,
moved from old to
new position.
so, solution is (if we use truly relative paths and
relative path is
distance between old and new positions)

    /**
    * Tests if the given AABoxes intersect if moved
along the given paths. Using
    * the AABox sweep test, the normalized time of the
first and last points of
    * contact are found.
    *
    * @param box1          the first box to test
    * @param path1         the path the first box
should travel along
    * @param box2          the second box to test
    * @param path2         the path the second box
should travel along
    * @param firstContact  set to the normalized time
of the first point of contact
    * @param secondContact set to the normalized time
of the second point of contact
    *
    * @return  true if the boxes intersect at any time;
false otherwise
    */
   template<class DATA_TYPE>
   bool intersect( const AABox<DATA_TYPE>& aabb1, const
Vec<DATA_TYPE, 3>& path1,
                   const AABox<DATA_TYPE>& aabb2, const
Vec<DATA_TYPE, 3>& path2,
                   DATA_TYPE& firstContact, DATA_TYPE&
secondContact )
   {
      // Algorithm taken from Gamasutra's article,
"Simple Intersection Test for
      // Games" -
http://www.gamasutra.com/features/19991018/Gomez_3.htm
      //
      // This algorithm is solved from the frame of
reference of box1
      //
      // 2006.07.14 rewritten by Breshin "Neonic"
Alexey (ga...@ma...)

      // Get the relative path (in normalized time)
      Vec<DATA_TYPE, 3> path = path2 - path1;

      // The first time of overlap along each axis
      Vec<DATA_TYPE, 3> overlap1(DATA_TYPE(0),
DATA_TYPE(0), DATA_TYPE(0));

      // The second time of overlap along each axis
      Vec<DATA_TYPE, 3> overlap2(DATA_TYPE(1),
DATA_TYPE(1), DATA_TYPE(1));

      // Check if the boxes already overlap
      if (gmtl::intersect(aabb1, aabb2))
      {
         firstContact = secondContact = DATA_TYPE(0);
         return true;
      }

      // calculating extents
      Point<DATA_TYPE, 3> ext1 =
(aabb1.getMax()-aabb1.getMin())*0.5f;
      Point<DATA_TYPE, 3> ext2 =
(aabb2.getMax()-aabb2.getMin())*0.5f;
      // calculating boxes at new positions
      AABox<DATA_TYPE> box1(pos1-ext1, pos1+ext1);
      AABox<DATA_TYPE> box2(pos2-ext2, pos2+ext2);
      // calculating dynamic boxes
      gmtl::extendVolume(box1,aabb1);
      gmtl::extendVolume(box2,aabb2);

      // Find the possible first and last times of
overlap along each axis
      for (int i=0; i<3; ++i)
      {
         if ((box1.getMax()[i] < box2.getMin()[i]) &&
(path[i] < DATA_TYPE(0)))
         {
            overlap1[i] = (box1.getMax()[i] -
box2.getMin()[i]) / path[i];
         }
         else if ((box2.getMax()[i] < box1.getMin()[i])
&& (path[i] > DATA_TYPE(0)))
         {
            overlap1[i] = (box1.getMin()[i] -
box2.getMax()[i]) / path[i];
         }

         if ((box2.getMax()[i] > box1.getMin()[i]) &&
(path[i] < DATA_TYPE(0)))
         {
            overlap2[i] = (box1.getMin()[i] -
box2.getMax()[i]) / path[i];
         }
         else if ((box1.getMax()[i] > box2.getMin()[i])
&& (path[i] > DATA_TYPE(0)))
         {
            overlap2[i] = (box1.getMax()[i] -
box2.getMin()[i]) / path[i];
         }
      }

      // Calculate the first time of overlap
      firstContact = Math::Max(overlap1[0],
overlap1[1], overlap1[2]);

      // Calculate the second time of overlap
      secondContact = Math::Min(overlap2[0],
overlap2[1], overlap2[2]);

      // There could only have been a collision if the
first overlap time
      // occurred before the second overlap time
      return firstContact <= secondContact;
   }

please, send answer with label "re: gmtl" on this address
and if you want to use changes what i have made -
please save in code
mark (history is history for me :-) )
"// 2006.07.14 rewritten by Breshin "Neonic" Alexey
(ga...@ma...)"

and at the last - i not tested this, but it is from a
part of
correctly working test.

thanks.

----------------------------------------------------------------------

>Comment By: Patrick Hartling (patrickh)
Date: 2009-02-13 14:39

Message:
If you could write a test case demonstrating that this change works and
that it does not break any existing test cases, then I will be happy to
commit your change.

----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=437247&aid=1523709&group_id=43735