Johnsons's / Voroni simplex solver

[coderchris]

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)

[Erwin Coumans]

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).

[coderchris]

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: 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;
	}

[Erwin Coumans]

Please compare with Bullet's implementation, or just port Bullet's code.

Hope that helps,
Erwin

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

[coderchris]

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

[Erwin Coumans]

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

[coderchris]

ah I see, thanks I got it fixed, was a bug with my vononoi solver