• entries
743
1924
• views
578703

# Visualising 3D Minkowski Sums

907 views

I've finished the development of the 2D GJK implementation, including both margin-based resolution for shallow penetrations and unit-circle sampling for approximate resolution for deeper checks and the time has come to start to try to implement this in 3D.

Something that was very handy during working out the 2D version of the algorithm was that I could sweep around a circle to generate an approximate set of points on the Minkowski sum and draw it as a polygon, so I could then draw the simplex I was refining.

So the first step for implementing a 3D version has been to create a method that can generate a mesh from a shape given only a support function. It works by sweeping directions around a unit sphere to generate the vertices, then stitching these into triangles, taking advantage of the fact that we know the order the vertices were added and rejecting any degenerate triangles that are formed.

Above is an image of a capsule built by combining two spheres, using the maximum dot of the point with the direction of each in the support function, but the mesh generator can work with any shape that you provide a support function for, so will be ideal for also visualising the Minkowski sum.

It creates a few more triangles than are actually needed so would require some refinement if it was to be used as anything other than a visualisation tool but is fine for these purposes.

Wow!!! Very nice work! How long did it take you to program this?

<blockquote class="ipsBlockquote" data-author="Black-Rook"><p>Wow!!! Very nice work! How long did it take you to program this?</p></blockquote><br />Couple of hours I guess. It isn't that complicated really. More fiddly.

Well good work none the less!

Thanks. Turns out that was the easy bit. Trying to find the simplex on the surface of the Minkowski difference closest to the origin seems a lot harder in 3D than it was in 2D. At least I have something to do for Christmas Day now...