# Physics Simulation Forum

 All times are UTC

 Page 1 of 1 [ 7 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Johnsons's / Voroni simplex solverPosted: Thu Nov 23, 2006 2:38 am

Joined: Fri Aug 18, 2006 11:50 pm
Posts: 48
Im making progress on my physics engine, but im stuck on which of the two simplex solvers to use. I sort of understand how the voroni solver works from studying bullets code, but im lost on the other one.

Before I go figure out how the other one works, what are your opinions on the speed of each one?
I want to use the fastest one (I assume they are both equally accurate)

Top

 Post subject: Re: Johnsons's / Voroni simplex solverPosted: Thu Nov 23, 2006 3:03 am

Joined: Sun Jun 26, 2005 6:43 pm
Posts: 3825
Location: California, USA
coderchris wrote:
Im making progress on my physics engine, but im stuck on which of the two simplex solvers to use. I sort of understand how the voroni solver works from studying bullets code, but im lost on the other one.

Before I go figure out how the other one works, what are your opinions on the speed of each one?
I want to use the fastest one (I assume they are both equally accurate)

They are not equally accurate., but the speed is very similar.

I added some degeneracy check in the Voronoi Simplex solver, which get's picked up by the GJK mainloop. Degenate cases happen occasionally, when the simplex is almost affine. Then it will try to do a penetration check, and if this gives a 'deeper' result, it will use that. This helps solve some degenerate cases. See Pierre Terdiman's posting about 'reliable' penetration depth, it was actually such case, caused by GJK, not penetration depth. Due to degeneracy, GJK would terminate and report a small positive distance, although it should have gone into penetration depth solving. So that should be fixed using the Voronoi solver.

I plan on optimizing the 'Voronoi' simplex solver: someone contributed a more optimal version, which works better on 'next-gen' platforms.

Hope this helps,
Erwin

PS: I think Gino van den Bergen added a similar degeneracy check in his Johnson solver implementation in Solid 3.5.x, so you could add this too (not sure if I added this already). Also, Gino's Johnson implementation has some higher accuracy mode, which favors the shortest triangle-edges (to calculate a better normal).

Top

 Post subject: Posted: Sat Nov 25, 2006 2:56 am

Joined: Fri Aug 18, 2006 11:50 pm
Posts: 48
Thanks for the help, Its so close to being complete, but im having a bit of a problem, and Im not sure if its because of GJK itself or somthing else. Here is a picture showing the problem

[img=http://img221.imageshack.us/img221/9305/proofje1.th.jpg]

The blue and red shapes are the two object being checked.
The yellow shape is the minkowski difference without margins.
The grayish pink shape is the minkowski difference with margins added.
The purple is the last simplex used in GJK.

The red line *is supposed* to go from the origin to the nearest point on the minkowski difference, and it is not. That is the bug. It works by finding the distance to the last simplex used by GJK, so im guessing since the last simplex does not contain the whole edge of the minkowski difference, it must be a bug with my GJK implementation, or it could be that 'degeneracy' you talked about in your previous post.

Does this look like a bug with my GJK or is this the degeneracy?

Here is my GJK code as well:
Code:
static Vec2[] Collide(Shape s1, Shape s2)
{
Vec2 d = s2.position.Subtract(s1.position);
d.Normalise();

//GJK initialise
Vec2 s = Support(s1,s2,d);
Vec2 simplex[] = new Vec2[3];
byte simpSize = 1;
simplex[0] = new Vec2(s);
d = s.Negate();
Vec2 a;
boolean collide = true;

//4 iterations
for (int i=0;i<numIterations;i++)
{
a = Support(s1, s2, d);
//Potential non - collide
if (collide && Vec2.Dot(a,d) < 0)
collide = false;
simplex[simpSize] = new Vec2(a);
simpSize ++;

//simplex has two points
if (simpSize == 2)
{
Vec2 o = simplex[1].Negate();
Vec2 ab = simplex[0].Subtract(simplex[1]);
if (Vec2.Dot(ab, o) > 0)
{
d = Vec2.Cross( Vec2.Cross(ab, o), ab);
//d.Normalise();
Vec2 temp = new Vec2(simplex[1]);
simplex[1] = new Vec2(simplex[0]);
simplex[0] = temp;
}
else
{
simplex[0] = new Vec2(simplex[1]);
simpSize --;
d = new Vec2(o);
//d.Normalise();
}
}
//simplex has three points
else if (simpSize == 3)
{
Vec2 o = simplex[2].Negate();
Vec2 ab = simplex[1].Subtract(simplex[2]);
Vec2 ac = simplex[0].Subtract(simplex[2]);
float abc = Vec2.Cross(ab, ac);

if (Vec2.Dot(Vec2.Cross(abc, ac), o) > 0)
{
if (Vec2.Dot(ac, o) > 0)
{
simplex[1] = new Vec2(simplex[0]);
simplex[0] = new Vec2(simplex[2]);
simpSize --;
d = Vec2.Cross(abc, ac);
//d.Normalise();
}
else if (Vec2.Dot(ab, o) > 0)
{
simplex[0] = new Vec2(simplex[2]);
simpSize --;
d = Vec2.Cross(abc, ab);
//d.Normalise();
}
else
{
simplex[0] = new Vec2(simplex[2]);
simpSize = 1;
d = new Vec2(o);
//d.Normalise();
}
}
else
{
if (Vec2.Dot(Vec2.Cross(ab, abc), o) > 0)
{
if (Vec2.Dot(ab, o) > 0)
{
simplex[0] = new Vec2(simplex[2]);
simpSize --;
d = Vec2.Cross(ab, abc);
//d.Normalise();
}
else
{
simplex[0] = new Vec2(simplex[2]);
simpSize = 1;
d = new Vec2(o);
//d.Normalise();
}
}
else
{
lastSimplex = simplex;
if (collide)
return simplex;
return null;
}
}
}
}

lastSimplex = simplex;
return null;
}

Top

 Post subject: Posted: Sat Nov 25, 2006 4:53 am

Joined: Sun Jun 26, 2005 6:43 pm
Posts: 3825
Location: California, USA
Please compare with Bullet's implementation, or just port Bullet's code.

Hope that helps,
Erwin

coderchris wrote:
Thanks for the help, Its so close to being complete, but im having a bit of a problem, and Im not sure if its because of GJK itself or somthing else. Here is a picture showing the problem

Top

 Post subject: Posted: Sat Nov 25, 2006 5:20 am

Joined: Fri Aug 18, 2006 11:50 pm
Posts: 48
I guess that means its a degeneracy issue. Ill try to look at bullets code some more but i cant seem to find where you check for this degeneracy

Top

 Post subject: Posted: Sat Nov 25, 2006 5:37 am

Joined: Sun Jun 26, 2005 6:43 pm
Posts: 3825
Location: California, USA
coderchris wrote:
I guess that means its a degeneracy issue. Ill try to look at bullets code some more but i cant seem to find where you check for this degeneracy

Before assuming a rare and unlikely degeneracy, I would first reproduce your setup in Bullet. If you use the Demos/EPAPenDepthDemo, it will tell you which path it took (degeneracy etc).

One degeneracy check in Bullet happens in line 438:
http://www.continuousphysics.com/Bullet ... tml#l00430

Erwin

Top

 Post subject: Posted: Sat Nov 25, 2006 5:39 am

Joined: Fri Aug 18, 2006 11:50 pm
Posts: 48
ah I see, thanks I got it fixed, was a bug with my vononoi solver

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 7 posts ]

 All times are UTC

#### Who is online

Users browsing this forum: Google [Bot] and 11 guests

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

Search for:
 Jump to:  Select a forum ------------------ BULLET PHYSICS LIBRARY USERS    General Bullet Physics Support and Feedback    Release Announcements    Applications, Games, Demos or Movies using Bullet PHYSICS AUTHORING TOOLS, SERIALIZATION AND STANDARDS    Physics authoring tools, serialization, standards and related topics RESEARCH AND DEVELOPMENT IN COLLISION DETECTION & PHYSICS. Don't post Bullet support questions here!    Research and development discussion about Collision Detection and Physics Simulation    Links, Papers, Libraries, Demos, Movies, Comparisons       Non-technical forum and license/patent discussion    Career Opportunities