Hacker News new | past | comments | ask | show | jobs | submit login

The Gilbert-Johnson-Keerthi convex shape intersection algorithm.

It can take any two convex sets and tell you if they overlap, while converging on a separating axis or a penetration point, if it exists. All you need is a support function that returns a point in the set that is furthest along a given direction vector. The algorithm works in an arbitrary number of dimensions.

Basically, it operates on a new shape which is the Minkowski difference of the two intersected sets. If the difference-shape contains the origin, then the two shapes overlap. The algorithm iteratively constructs simplexes inside the Minkowski difference, trying to build one that encompasses the origin. This allows it to have essentially constant memory for a given dimension of problem.

It's a very elegant formulation of a very general problem. It's so pleasing that you can intersect cylinders with cones, or oriented cubes with frustums, or polytopes with superellipses all with the exact same single algorithm.

The Wikipedia writeup is terrible, so I may do my own with nice illustrations at some point.




Neat. I googled, and have been reading this writeup: https://www.medien.ifi.lmu.de/lehre/ss10/ps/Ausarbeitung_Bei... —which seems quite nice so far.


Wow. I'm surprised to see this on here. I used to work Johnson, he's is a super nice guy and always made time to have long conversations with me about optimization.

I believe this algorithm is widely used in the video game industry?


Video games and anywhere you need a rigid body collision simulation. So TV & film visual effects is another common use.


Also researchers who need fast approximate physical dynamics. For example the Mujoco simulator or Drake.




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: