• entries
743
1924
• views
581840

# GJK musings

1391 views

Thought I'd write a post about the GJK implementation that I'm using in my game to deal with collision detection between implict shapes today.

Above is a screenshot from a 2D test bed I wrote when I was originally working out the algorithm in 2D. Its easier to visualise in 2D and you can explicitly sample the Minkowski difference in order to create a shape for drawing it on the screen.

The two blue shapes are compound shapes formed by combining the support functions of two circles each. A support function is just a method that, for a given shape, takes a world space direction vector and returns the point in world space that is furthest along that vector. Given this, you can do an approximate explicit same around the angles of a circle and create a list of points that roughly describe the shape. If you have two support functions and return the greater of the result of the two of them for a particular direction, you get the kind of "shrink wrap" effect that you see in the blue shapes above, which looks like the result of wrapping two circles in polythene and create a convex that is based on both.

This is one of the lovely things about using support functions. You can easily visualise the function for simple primitives, then combine these together in different ways to create a support function for a more complex shape. In 3D, for example, if you can figure out the support function for a disk and a point, you can create a function for a cone. A sphere is trivially just centre + (direction * radius) but two can be combined together to make a capsule and so on.

As I said last post as well, it is trivial to internally convert the direction to local space, so you only need to be able to work out support functions for a primitive in its local space, and you have the facility to have complex convex shapes in world space, formed by shrink wrapping polythene around simpler shapes, or by blowing up one shape by another (e.g. a rounded cube by combining a sphere with a box by adding the support function results of the two together). You can combine as many shapes as you want using these methods so its pretty powerful.

And once you have a shape with a support method, GJK will work on anything. GJK is based on the fact that if you take every point in one shape and subtract it from every point in the other shape, the result contains the origin if the shapes intersect and does not if they don't. This is easy enough to understand - if the result of subtracting any point in shape 1 from any point in shape 2 is (0, 0, 0), then the only possibility is that two of their points at least must be the same.

So the challenge then goes from "do two shapes intersect" to "does the Minkowski difference of two shapes contain the origin". We can't explicitly create the Minkowski difference since it is an infinite set of points, but by playing clever with the two shapes' support functions, we can sample the Minkowski difference in any direction to find its furthest point in any direction and that is sufficient for the algorithm.

You can also see in the image that the vector between the margin and the surface of the Minkowski difference is the same as the minimum translation vector to move the two shapes apart, which becomes useful in collision resolution. It is tricker to find this vector and I can discuss this in more detail in another post.

Anyyway, that was a very brief introduction to GJK from me. If you are interested in the details of how the algorithm actually works, I can't sufficiently recommend Casey's excellent video on the subject, which was my starting point. He takes a subject normally explained with very dense mathematical language and explains it in a way that makes in accessible to programmers without a formal maths education, which is me all over so was really good. I used source references to implement mine too, but I can honestly say I understand exactly what every line in my implementation is doing and that understanding was necessary once I had the basics working to get the weird corner cases working right.

This is the core of my actual use of the GJK in my game:

Vec3 Physics::getSeparationVector(const Body *body, const Vec3 &pos, const Vec3 &vel) const{ bool loop = true; float m = margin(); Gjk gjk; Vec3 result = pos + vel; ex_vector colliders = potentialColliders(body); int it = 0; while(loop && it++ < 5) { loop = false; Matrix transform = translationMatrix(result); for(auto &c: colliders) { if(gjk.intersect(body->shape(), transform, c->shape(), c->transform(), m)) { Vec3 v; if(!gjk.intersect(body->shape(), transform, c->shape(), c->transform(), 0)) { Gjk::Result r = gjk.closestVector(body->shape(), transform, c->shape(), c->transform(), 0); if(r.solved()) { v = normalizeVector(r.vector()) * ((m * 2.0f) - vectorLength(r.vector())); } else { v = gjk.sampledVector(body->shape(), transform, c->shape(), c->transform(), m).vector(); } } else { v = gjk.sampledVector(body->shape(), transform, c->shape(), c->transform(), m).vector(); } result += v; transform = translationMatrix(result); loop = true; } } } return result - (pos + vel);}GJK can return the closest distance of two non-intersecting shapes, but cannot do so once the shapes are intersecting. There is an algorithm called EPA for this, but for now I'm using the approach that Bullet takes which is to shrink the shapes slightly by a margin, then see if the original shapes intersect, but the shrunk shapes don't, in which case we can use the closest distance of the shrunk shapes to work out the minimum translation vector. This works for shallow collisions.

In the (rare) case of deeper penetrations we fall back on using sampled vectors around a unit sphere which gives a slightly inaccurate result, although can be quite accurate on polyhedra since we can prime this vector set with the face normals of the shapes. But we try to avoid pentrations deeper than the margin anyway so this is rarely called and more an escape from an unexpected condition.

The looping is arbitrary. Resolving one collision can lead to penetrating with another shape as we all know too well, so a tradeoff against performance is to run the loop a few times to improve the final settled position. Seems to work pretty well for my needs in its current form, but did require a deeper understanding of the copy-paste approach I could have taken with the GJK for me to get right, so was well worth the time it took to understand.

The next thing I'm getting into is figuring out how to do a ray cast against a shape that I only have represented by support functions since I don't understand this at current but, as I said last time, I really want to get that figured out so my physics is consistently just using support functions to represent shapes since it makes everything else so clean and simple.

There are no comments to display.