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)
Johnsons's / Voroni simplex solver
-
- Site Admin
- Posts: 4221
- Joined: Sun Jun 26, 2005 6:43 pm
- Location: California, USA
Re: Johnsons's / Voroni simplex solver
They are not equally accurate., but the speed is very similar.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)
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).
-
- Posts: 49
- Joined: Fri Aug 18, 2006 11:50 pm
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:
[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: Select all
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;
}
-
- Site Admin
- Posts: 4221
- Joined: Sun Jun 26, 2005 6:43 pm
- Location: California, USA
Please compare with Bullet's implementation, or just port Bullet's code.
Hope that helps,
Erwin
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
-
- Posts: 49
- Joined: Fri Aug 18, 2006 11:50 pm
-
- Site Admin
- Posts: 4221
- Joined: Sun Jun 26, 2005 6:43 pm
- Location: California, USA
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).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
One degeneracy check in Bullet happens in line 438:
http://www.continuousphysics.com/Bullet ... tml#l00430
Erwin
-
- Posts: 49
- Joined: Fri Aug 18, 2006 11:50 pm