Sign in to follow this  
leoptimus

FreeSolid GJK

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 this post


Link to post
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".

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this