0

I am trying to implement a GJK algorithm which is supposed to return the distance between two convex shapes, in the futur i plan on using this for continuous collision detection. In the calculations i am using floats to speed up the calculation time and use less memory. I know that float numbers are not very precise for example i often get 1...10-6 instead of 0 and that isn't too supprising. However GJK as a finishing condition which is something like [value <= error] and if i choose a value error below 0.01 GJK never ends. Mathematicly i am supposed to get 0 so this would mean that i have accumulated float errors up to 0.01 is this possible? It's true that the calculation i do are pretty big, i do matrix inversions and multiplications and than i calculate determinants and divide them. In the code bellow i show the two functions that do most of the calculations. If this is a precison problem how could i fix this? Although i don't really need more than 0.1 in precision i still think that this is a bit odd. I will also add that this algorithm prints values that seem correct and detects collision correctly so this mainly why i think it is a precision problem even though i have my doubts.

//this code calls the calculations, as you can see there are some Matrix calculations here.
void ConvexShape::getDistance(const Matrix4x4& t1, const ConvexShape& shape, const Matrix4x4& t2)
        {
          Matrix4x4 rt1 = t1;
          rt1.get(0,3) = 0.0;
          rt1.get(1,3) = 0.0;
          rt1.get(2,3) = 0.0;

          Matrix4x4 rt2 = t2;
          rt2.get(0,3) = 0.0;
          rt2.get(1,3) = 0.0;
          rt2.get(2,3) = 0.0;

          Matrix4x4 invRT1 = rt1.invert();
          Matrix4x4 invRT2 = rt2.invert();

          Vector3 v = t1*support(invRT1*Vector3(1,0,0)) - t2*shape.support(invRT2*Vector3(-1,0,0));
          Simplex simplex;
          SupportVertex w(t1*support(invRT1*(-v)), t2*shape.support(invRT2*(v)));
          while(v.dot(v) - v.dot(w.getMdPosition()) > 0.01)
          {
            simplex.addPoint(w);
            v = simplex.getNearZero().getMdPosition();
            w = SupportVertex(t1*support(invRT1*(-v)), t2*shape.support(invRT2*(v)));
          }
          std::cout << "DISTANCE = " << v.getLength() << std::endl;
        }
//this a piece of code that calculated the barycentric coordonated of a thetrahedron it is often used.
void Simplex::getBarycentricCoordonates(const Vector3& OA, const Vector3& OB, const Vector3& OC, const Vector3& OD, float* u, float* v, float* w, float* k)
        {
          Vector3 AB = OB - OA;
          Vector3 AC = OC - OA;
          Vector3 AD = OD - OA;
          Vector3 AO = -OA;

          float ABAB = AB.dot(AB);
          float ACAC = AC.dot(AC);
          float ADAD = AD.dot(AD);

          float ABAC = AB.dot(AC);
          float ABAD = AB.dot(AD);

          float ACAD = AC.dot(AD);

          float AOAB = AO.dot(AB);
          float AOAC = AO.dot(AC);
          float AOAD = AO.dot(AD);

          float detA  = - ABAB*(ACAC*ADAD - ACAD*ACAD)
                        + ABAC*(ABAC*ADAD - ACAD*ABAD)
                        - ABAD*(ABAC*ACAD - ACAC*ABAD);

          float detAv = - AOAB*(ACAC*ADAD - ACAD*ACAD)
                        + AOAC*(ABAC*ADAD - ACAD*ABAD)
                        - AOAD*(ABAC*ACAD - ACAC*ABAD);

          float detAw = - ABAB*(AOAC*ADAD - AOAD*ACAD)
                        + ABAC*(AOAB*ADAD - AOAD*ABAD)
                        - ABAD*(AOAB*ACAD - AOAC*ABAD);

          float detAk = - ABAB*(ACAC*AOAD - ACAD*AOAC)
                        + ABAC*(ABAC*AOAD - ACAD*AOAB)
                        - ABAD*(ABAC*AOAC - ACAC*AOAB);

          float denom = 1.0/detA;

          *v = detAv*denom;
          *w = detAw*denom;
          *k = detAk*denom;
          *u = 1.0 - *v - *w - *k;
        }
  • 1
    Might be a precision issue. `float` is the lowest precision floating point representation available in C++. Change to `double` and see if your results improve. – lurker Aug 06 '19 at 00:25
  • Possible duplicate of [Is floating point math broken?](https://stackoverflow.com/questions/588004/is-floating-point-math-broken) –  Aug 06 '19 at 00:26
  • You know, this may not be a dupe, now that I look at it more closely. Probably related, though. –  Aug 06 '19 at 00:28
  • Thanks for your coments, i did try replacing the floats by doubles in certain areas but i wasn't able to change it everywhere because of the codes design and to be honest i am not sure that it had a bg impact, but again i only changed it in the calculateBarycenterCoordonates() function. And my question is not really why the float is not very precise but rather is my result due to the float non precision? – Le Grand Spectacle Aug 06 '19 at 01:08
  • I didn't suggesting changing `float` to `double` to determine why `double` is more precise. It won't answer that. It's more precise because it's a lot more bits. I suggested changing `float` to `double` as an experiment that would give you a clue as to whether your result is due to a precision issue. But since you can't change all of them, that experiment is questionable. Outside of that, you might want to walk through your code carefully to check your math. You could also use a debugger and examine data at intermediate points to determine if those results make sense. – lurker Aug 06 '19 at 01:14

0 Answers0