Sign in to follow this  
FireSoull_

Initialising the simplex set in GJK

Recommended Posts

FireSoull_    122
Hi, I currently looking at the GJK algorithm and how it works, using Christer Ericson's slides for SIGGRAPH 2004 and I am not totally sure how the first step works (which involves initialising the simplex set with up to d+1 points within a convex hull). My main question then is how are you supposed to determine what vertices on a convex hull will be used to create the intitial simplex, can just randomly selecting point(s) work or is there a specific method for constructing a simplex from a convex hull, or is there something I have misunderstood/missed? Thanks.

Share this post


Link to post
Share on other sites
Norbo    545
I generally use a single point for the initial simplex- the difference of the objects' center points. It is possible to start with a full simplex, though if I'm not mistaken, to do that you'd generally be using the final simplex of an earlier run of the algorithm to warm start it.

I have not dealt with warm starting GJK extensively, but I've found that circumstances usually change enough between multiple runs that allowing for warm starting wasn't worth it. Someone else may have more experience here.

Share this post


Link to post
Share on other sites
oliii    2196
I'd do what Norbo says.

Also, you can start off using the relative position between the two convexes as your first potential SAT. That will give you your first point for your simplex.

And yes, you can cache the simplexes between two objects if you want to use time coherence.

Share this post


Link to post
Share on other sites
DonDickieD    2751
Does GJK behave differently (numerically more robust) for different strategies when initializing the simplex? I got better results with using the zero vector as initial search direction instead of using the difference of the centroids. Might be just accidental, but I wonder if anybody made similar observations?


Share this post


Link to post
Share on other sites

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

Sign in to follow this