# FreeSolid GJK

This topic is 4604 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Does FreeSolid support single float precision? I'd have problems with FreeSolid 2.0, because the approximation loop for find the closest simplex points never stops! due rounding precision isues. Honestly, I don't understand GJK algorithm very well. The loop exit condition is one of the trickiest part of the algorithm, because it does somehow of absolute and relative error checking that it isn't clear to me. This is the trouble part of solid:
void closest_points(const Convex& a, const Convex& b,
const Transform& a2w, const Transform& b2w,
Point& pa, Point& pb) {
static Vector zero(0, 0, 0);

Vector v = a2w(a.support(zero)) - b2w(b.support(zero));
Scalar dist = v.length();

Vector w;

bits = 0;
all_bits = 0;
Scalar mu = 0;

#ifdef STATISTICS
num_iterations = 0;
#endif

while (bits < 15 && dist > abs_error) {
last = 0;
last_bit = 1;
while (bits & last_bit) { ++last; last_bit <<= 1; }
p[last] = a.support((-v) * a2w.getBasis());
q[last] = b.support(v * b2w.getBasis());
w = a2w(p[last]) - b2w(q[last]);
set_max(mu, dot(v, w) / dist);
if (dist - mu <= dist * rel_error) break;
if (degenerate(w)) {
#ifdef STATISTICS
++num_irregularities;
#endif
break;
}
y[last] = w;
all_bits = bits|last_bit;
#ifdef STATISTICS
++num_iterations;
if (num_iterations > 1000) catch_me();
#endif
if (!closest(v)) {
#ifdef STATISTICS
++num_irregularities;
#endif
break;
}
dist = v.length();
}
compute_points(bits, pa, pb);
}


I remind that I forces FreeSolid to use single float precision. So, Is FreeSolid 2.0 robust? It's logical that it takes 15 iterations for find the closest points of two spheres? Have you ever have a good experience with FreeSolid 2.0? Please tell me if you know another GJK collision package. Thanks. Att: A desperate game programmer.

##### Share on other sites
Well for GJK, the number 15 is significant because it's the number of possible "voronoi regions" for a tetrahedron ("3-simplex"). Basically, GJK goes around selecting tetrahedra made of points on your spheres, such that the tetrahedron converges very quickly to where some point on it to the origin represents the closest point between the two spheres.

Now, I can envision, with 2 small spheres (or spheres far from the origin) if your epsilon value is smaller than than the support function can produce, your loop might go infinite.

The code you present just looks like a precalculation for the real Voronoi computation, like "only test these certain regions" though I don't look very close. Is there an epsilon you can increase? You don't list enough to say for certain "this is unstable".