• entries
  • comments
  • views

Visualising 3D Minkowski Sums

Sign in to follow this  


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.
Sign in to follow this  


Recommended Comments

<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.

Share this comment

Link to comment
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...

Share this comment

Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now