How convexhulls work?

A place to discuss everything related to Newton Dynamics.

Moderators: Sascha Willems, walaber

How convexhulls work?

Postby AntonSynytsia » Thu Jul 31, 2014 1:03 am

I really like the concept of convex hulls, but yet I don't understand why there are no such things as dynamic concave hulls (other than compounds) in physics engines.

As far as I know convex hulls are created from the most outer points in an array of given vertices, but I don't understand why they are so special when it comes to collision detection. Is it because there is an easy way to determine collision intersections? If so, then what method is used? A similar question would be, how to determine whether a point is inside convexhull?

As well, I would to know which method is Newton using to calculate convexulls, a QuickHull?

Just want to explore the secrets of Newton :twisted:
AntonSynytsia
 
Posts: 193
Joined: Sat Dec 28, 2013 6:36 pm

Re: How convexhulls work?

Postby Julio Jerez » Thu Jul 31, 2014 6:17 am

The convex hull are special for collision detection because of a mathematical theorem called the Minkowski sum of two set of points. you can look that up in Wikipedia.
it just happen that the Minkowski sum of a set of points that happen to be form a convex hull is also another convex hull.

the collision detection is converted from a problem of calculation interstation between to shapes to the problem of calculations the closest distance from a convex hull to the origin.
if the origin is outside the hull the shapes do no intersect, If the origin is inside or touches the shape they the intersect.
here he where another algorithm called JGK is use to calculation the closest point form a convex hull to the origin iteratively. This algorithm does no need to build the complete convex Hull of the two input set of vertices,
instead is build them incrementally as it need them.

No Newton does not use quickhull to build convex hulls, newton use my own algorithm which has being extracted as a stand alone algorithm by some nvidea people
juliohull is much faster that quickull, more robust and much cleaner implementation. and it si a truly N dimension convex hull generator. I use also for making 4 dimensional convex hulls
http://code.google.com/p/juliohull/
Julio Jerez
Moderator
Moderator
 
Posts: 12426
Joined: Sun Sep 14, 2003 2:18 pm
Location: Los Angeles

Re: How convexhulls work?

Postby AntonSynytsia » Thu Jul 31, 2014 7:22 am

Wow, Juleo!
And I wondered why convex-hulls were so fast.
I starred repo for the future reference.

Thanks, for some important knowledge
AntonSynytsia
 
Posts: 193
Joined: Sat Dec 28, 2013 6:36 pm


Return to General Discussion

Who is online

Users browsing this forum: No registered users and 0 guests

cron