Jump to content

  • Log In with Google      Sign In   
  • Create Account

Interested in a FREE copy of HTML5 game maker Construct 2?

We'll be giving away three Personal Edition licences in next Tuesday's GDNet Direct email newsletter!

Sign up from the right-hand sidebar on our homepage and read Tuesday's newsletter for details!


We're also offering banner ads on our site from just $5! 1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.






Visualising 3D Minkowski Sums

Posted by Aardvajk, 23 December 2012 · 536 views

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.




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! smile.png
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...

November 2014 »

S M T W T F S
      1
2345678
9101112131415
16171819202122
23 24 2526272829
30      

Recent Entries

Recent Comments

Recent Entries

Recent Comments

PARTNERS