Jump to content
  • Advertisement
Sign in to follow this  
leoptimus

FreeSolid GJK

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

If you intended to correct an error in the post then please contact us.

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
Advertisement
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!