Minkowski addition and convex hulls.

Started by
9 comments, last by slicer4ever 11 years, 4 months ago

Now that I see what the problem is, I can give you the full answer. Using plane equations for meshes is suboptimal for this types of queries, because you want to exploit the convexity of your mesh. Multiple plane equations don't contain that information explicitly. On the other hand using verts/indcs is useful because you can construct the Dobkin-Kirkpatrick hierarchy (during pre-processing, takes linear time) and traverse only the most relevant parts of your convex mesh which results in a logarithmic time algorithm.
Implementation details can be found in almost any textbook that mentions this hierarchy.


thank you, i'm currently reading over a pdf about Dobkin-Kirkpatric right now to get a better grasp on the subject. I've never had any formal training on computational geometry, so it's not uncommon for me to run into an new approach to a problem that essentially shines a bright light at things i've been trying to do, but didn't know proper terms for them, so usually it ends up getting done haphazardly.

I am coming to the realization that storing only planes provides only enough information for simple query's into the object, I just discovered that the implementation i created for doing minkowski diffrence has faults in the fact that drawing a straight line between two objects can cause missed collisions.
Check out https://www.facebook.com/LiquidGames for some great games made by me on the Playstation Mobile market.

This topic is closed to new replies.

Advertisement