Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 22 Aug 2013
Offline Last Active Apr 19 2015 11:46 PM

#5159938 Sequential Impulse Solver and Sliding Contacts

Posted by on 11 June 2014 - 10:01 PM



For collision detection my engine implements a mix between GJK and the Xenocollide algorithm with Minkowski Portal Refinement (MPR) to get contact points. You can find the algorithm described in detail in Game Programming Gems 7 section 2.5. A simple 2D example is given on the authors website. Other special-case detection I follow Real-Time Collision Detection by Ericson modifying to my specific needs.


For resolution I used a mixture of the following resources to understand the equations of motion and implement a sequential impulse solver:

  • Game Physics Engine Development by Ian Millington-- while a good resource for general physics engine development, I do not recommend following this approach if you want a stable system for stacking more than 3 or 4 boxes high. The latest edition has an addendum for 2D physics if that is your interest.
  • Game Physics by David H. Eberly -- This book is very thorough and gives lots of details on the math for resolution. At an implementation level this book tends to be more focused on block solvers and simultaneous resolution.


Finally, I followed Box2D lite for ordering the integration / detection / resolution pipeline as well as for how to resolve via impulses only (with no direct position corrections), and how to best do warm-starting.


All this said, the two features that added the most to the stability were:


   1) Warm starting on normal and tangential impulses

   2) Impulses for penetration correction

   3) Adjusting the coefficient of restitution (bouncy objects don't lend well to stacking). Box2D lite effectively sets this to 0 along the normal if you look in the code.


Hope this helps!

#5088483 GJK Simplex Caching and Circles

Posted by on 23 August 2013 - 02:30 PM


I guess if you're not planning on supporting curves or any sort of user-defined paths, then you can go ahead and store vertices for simplexes. But for any sort of curves and paths, you can't.

I think this really is the heart of the question. Can you? I suppose not, at least not with-out special casing GJK, or representing them as a high-res polygon. Which in my mind kind of eliminates the beauty of GJK to begin with right, as long as the shape has a support function, you can plug it in GJK.

#5088350 GJK Simplex Caching and Circles

Posted by on 23 August 2013 - 06:15 AM

Thanks CullDeVu for the quick response.


I'm not sure I follow you on the redundancy check? When I start up GJK, my first step is to find the closest point to the current simplex whether it was cached or from a previous iteration; so I'm not sure I see the overhead there.


I agree with you that there are likely more non-collisions than there are collisions which warrants focusing optimizations towards the majority. However, caching the support vertices from the previous frame not only helps speed up collision cases but non collisions as well under the assumption that relative orientation and positions between a pair of objects tend not to change drastically between single frames regardless of collision status. Additionally, GJK doesn't run until after my broadphase completes which would reduce the number of cached simplices quite a bit.


It seems I've seen some implementations where they've found some way of making circles appear to have vertices (where say v[0] somehow corresponds to the support vertex). But I think you're right with only caching the previous the point for circles. I'll look into that more.