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;
}