S M T W T F S
1
2345678
9101112131415
16171819202122
232425 26 272829
30

# Visualising 3D Minkowski Sums

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.
Dec 24 2012 02:28 PM
Wow!!! Very nice work! How long did it take you to program this?
Dec 24 2012 02:48 PM
<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.
Dec 24 2012 04:00 PM
Well good work none the less!
Dec 24 2012 05:34 PM
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...

Note: GameDev.net moderates comments.