Real-Time Physics Simulation Forum

Re: GJK

2006-11-22T19:02:46+00:00

Ok, i adapted my code to use the new Bullet which you integrated in Blender.

First of all: Thank you for the great upgrade!

But the problem stays, the GJK returns exactly the same value as before.
The only difference is, that the new bullet feels faster than before (but i switched from cygwin to mingw so i don't know if it's Bullet)

Is there another distance function i could use in bullet?
Greetings so far!

This testcase works fine with Bullet, its not wrong!

Please see this picture, the red line connects the triangles perfectly (ignore the additional white line, that's the minkowski simplex)

I will add the testcase in the Bullet Demos/CollisionDemo demo, so you can see for yourself (see CHECK_GENSHER_TRIANGLE_CASE define in Bullet 2.35)

You can do cloth triangles versus all Bullet shapes: this includes implicit box, sphere, cylinder, convex polyhedron etc. Bullet works best if one of the convex has 'volume', so triangle verus convex primitive is ideal. Usually on game characters, the cloth is colliding with cylinders or other volumetric shapes.

In general, I can recommend using a larger collisionMargin, not just 0.001. This gives the cloth collision some 'thickness'.

Thanks,
Erwin

Statistics: Posted by Erwin Coumans — Wed Nov 22, 2006 7:02 pm

GJK

2006-11-22T17:36:31+00:00

Ok, i adapted my code to use the new Bullet which you integrated in Blender.

First of all: Thank you for the great upgrade!

But the problem stays, the GJK returns exactly the same value as before.
The only difference is, that the new bullet feels faster than before (but i switched from cygwin to mingw so i don't know if it's Bullet)

Code:

float p1[3], p2[3], p3[3], q1[3],q2[3], q3[3];p1[0] = -3.9242966175; p1[1] = -0.5582823175; p1[2] = 2.0101921558;p2[0] = -3.6731941700;p2[1] = -0.5604774356;p2[2] = 2.00301921558;p3[0] = -3.6698703766;p3[1] = -0.3097069263;p3[2] = 2.0073683262;btTriangleShape trishapeA(btVector3(p1[0], p1[1], p1[2]), btVector3(p2[0], p2[1], p2[2]), btVector3(p3[0], p3[1], p3[2]));trishapeA.setMargin(0.001f);q1[0] = -2.6317186356; q1[1] = -1.0000005960; q1[2] = 1.9999998808;q2[0] = -2.6317174435;q2[1] = 0.9999994636;q2[2] = 1.9999998808;q3[0] = -4.6317176819;q3[1] = 1.0f;q3[2] = 1.9999998808;btTriangleShape trishapeB(btVector3(q1[0], q1[1], q1[2]), btVector3(q2[0], q2[1], q2[2]), btVector3(q3[0], q3[1], q3[2]));trishapeB.setMargin(0.001f);btVoronoiSimplexSolver sGjkSimplexSolver;btGjkPairDetector convexConvex(&trishapeA ,&trishapeB,&sGjkSimplexSolver,0);btPointCollector gjkOutput;btGjkPairDetector::ClosestPointInput input;btTransform tr;tr.setIdentity();input.m_transformA = tr;input.m_transformB = tr;convexConvex.getClosestPoints(input, gjkOutput, 0);if (gjkOutput.m_hasResult){VECCOPY(pa, gjkOutput.m_pointInWorld);VECCOPY(pb, gjkOutput.m_pointInWorld);VECADDFAC(pb, pb, gjkOutput.m_normalOnBInWorld, gjkOutput.m_distance); printf("bullet: %10.10f\n", gjkOutput.m_distance); // = 0.24 => that's absolutely wrong! return gjkOutput.m_distance;}

Is there another distance function i could use in bullet?

Greetings so far!

Statistics: Posted by Genscher — Wed Nov 22, 2006 5:36 pm

great

2006-11-20T19:27:57+00:00

Good evening!

That's great news! I can hardly wait until bullet 2.33 is compiled with blender!

Genscher

Statistics: Posted by Genscher — Mon Nov 20, 2006 7:27 pm

Re: gjk

2006-11-20T16:35:17+00:00

I can't use any other bullet version since i use the blender bullet version.

The Bullet version in Blender will be upgraded to Bullet 2.33 this week. The refactored Bullet is already checked into cvs in Blender/extern/bullet2

But as i know, there wasn't changed anything in the gjk algorithm.

It is likely an implementation issue, not algorithmic. The implementation has improved.

Thanks for your testcase, I will try it out,
Erwin

Statistics: Posted by Erwin Coumans — Mon Nov 20, 2006 4:35 pm

gjk

2006-11-20T15:21:15+00:00

Hello!

thank you for your answer.

As the code shows, it's not a penetration depth problem, it's a distance problem (I verified the problem with penetration AND without penetration and I already wrote).
That's why i don't pass any penetration depth solver to it.

Just use the values i provided for two triangles and you can veirfy the problem.
I can't use any other bullet version since i use the blender bullet version.
But as i know, there wasn't changed anything in the gjk algorithm.

Greetings so far!

Statistics: Posted by Genscher — Mon Nov 20, 2006 3:21 pm

using Bullet: flying Triangles and SimdTransform's

2006-11-19T17:53:13+00:00

Is it distance or penetration depth problem?

Several improvements have been made on Bullet GJK (distance) and EPA (penetration) recently. There is a good chance that this is not an algorithmic problem but just some implementation bugs. I noticed your GjkPairDetector doesn't have 'bt' prefix, so you might be using a very outdated Bullet version?

Can you verify your case with this latest Bullet version 2.33? I will add the solving of your problem on my todo list.

Also, you are passing a 0 pointer for the penetration depth solver, that will not work properly. Please pass a btGjkEpaPenetrationDepthSolver object, instead of 0 in

Code:

GjkPairDetector   convexConvex(&trishapeA ,&trishapeB,&sGjkSimplexSolver,0);

Thanks for the feedback,
Erwin

Statistics: Posted by Erwin Coumans — Sun Nov 19, 2006 5:53 pm

bullet sample

2006-11-17T11:06:55+00:00

ok, here we go, in have a valid example where bullet computes the distance really wrong (but SOLID does the same, so i don't blame bullet):

Code:

p1[0] = -3.9242966175; p1[1] = -0.5582823175; p1[2] = 2.0101921558;p2[0] = -3.6731941700;p2[1] = -0.5604774356;p2[2] = 1.9995596409;p3[0] = -3.6698703766;p3[1] = -0.3097069263;p3[2] = 2.0073683262;TriangleShape trishapeA(SimdVector3(p1[0], p1[1], p1[2]), SimdVector3(p2[0], p2[1], p2[2]), SimdVector3(p3[0], p3[1], p3[2]));trishapeA.SetMargin(0.001f);q1[0] = -2.6317186356; q1[1] = -1.0000005960; q1[2] = 1.9999998808;q2[0] = -2.6317174435;q2[1] = 0.9999994636;q2[2] = 1.9999998808;q3[0] = -4.6317176819;q3[1] = 1.0f;q3[2] = 1.9999998808;TriangleShape trishapeB(SimdVector3(q1[0], q1[1], q1[2]), SimdVector3(q2[0], q2[1], q2[2]), SimdVector3(q3[0], q3[1], q3[2]));trishapeB.SetMargin(0.001f);VoronoiSimplexSolver sGjkSimplexSolver;GjkPairDetectorconvexConvex(&trishapeA ,&trishapeB,&sGjkSimplexSolver,0);PointCollector gjkOutput;GjkPairDetector::ClosestPointInput input;SimdTransform tr;tr.setIdentity();input.m_transformA = tr;input.m_transformB = tr;convexConvex.GetClosestPoints(input, gjkOutput, 0);if (gjkOutput.m_hasResult){VECCOPY(pa, gjkOutput.m_pointInWorld);VECCOPY(pb, gjkOutput.m_pointInWorld);VECADDFAC(pb, pb, gjkOutput.m_normalOnBInWorld, gjkOutput.m_distance);printf("bullet: %10.10f\n", gjkOutput.m_distance); // = 0.24 => that's absolutely wrong! return gjkOutput.m_distance;}

Bullet also returns a big wrong values arround 0.24 - 0.27 when this two triangle do not intersect.
You can verify the non-interpenetrating test, if you set p2[2] = 2.00301921558;
so the distance should be arround 0.003 - 0.004.
But bullet returns 0.244 as distance for the non-interpenetrating test!

I hope I could clearify my problem.

Greetings!

Statistics: Posted by Genscher — Fri Nov 17, 2006 11:06 am

Re: Found a paper about it

2006-11-14T19:41:45+00:00

Can you provide a BulletDemo that can reproduce the failing case with big/small triangle? I am always welcoming feedback and suggestions for improvement. There is some current work going on into improving GJK + EPA (penetration case). I prefer getting the single precision floating point version as accurate as possible, but a double precision version might improve things too. Also, what value are you using for collision margin? Setting it to zero is not supported.

I'm familiar with the paper you refer to.It is an interesting approach, I hope to implement at some stage. Are you planning to work on this?

Thanks,
Erwin

Hello!

I found a paper which describes a solution of the problem which I have.
It seems that the "normal" GJK algorithm suffer some limitation when having "difficult" settings like in my case (big triangle against smal triangle and only a little distance).

http://citeseer.ist.psu.edu/cache/paper ... j00new.pdf

Greetings so far

Statistics: Posted by Erwin Coumans — Tue Nov 14, 2006 7:41 pm

Found a paper about it

2006-11-14T13:03:45+00:00

Hello!

I found a paper which describes a solution of the problem which I have.
It seems that the "normal" GJK algorithm suffer some limitation when having "difficult" settings like in my case (big triangle against smal triangle and only a little distance).

http://citeseer.ist.psu.edu/cache/paper ... j00new.pdf

Greetings so far

Statistics: Posted by Genscher — Tue Nov 14, 2006 1:03 pm

New status

2006-11-13T23:08:56+00:00

Hello!

First of all, thank you Erwin for your great work in the bullet physics library!

I made a workarround for the ccd thing and it seems to work fine (at least for simple setups).

The weird thing was, that i missed some collisions in the "near"-mode.
I checked the distance like this:

Code:

TriangleShape trishapeA(SimdVector3(p1[0], p1[1], p1[2]), SimdVector3(p2[0], p2[1], p2[2]), SimdVector3(p3[0], p3[1], p3[2]));trishapeA.SetMargin(0.0f);TriangleShape trishapeB(SimdVector3(q1[0], q1[1], q1[2]), SimdVector3(q2[0], q2[1], q2[2]), SimdVector3(q3[0], q3[1], q3[2]));trishapeB.SetMargin(0.0f);VoronoiSimplexSolver sGjkSimplexSolver;GjkPairDetectorconvexConvex(&trishapeA ,&trishapeB,&sGjkSimplexSolver,0);PointCollector gjkOutput;GjkPairDetector::ClosestPointInput input;SimdTransform tr;tr.setIdentity();input.m_transformA = tr;input.m_transformB = tr;convexConvex.GetClosestPoints(input, gjkOutput, 0);

Under some configuration it results in bad/wrong distance results.
My impression is, that it is not bullets false but maybe a design limitation of GJK because i tested this distance problem also with SOLID (using double precission) and it gave me arorund the same results as bullet.

I was testing the distance between two triangle where the first triangle is arround 1/10 - 1/20 of the size of the second triangle.
I subdivided the second triangle (after figuring that I did everything right) and the problem was gone! Bullet was working fine!

So my question is: How can i get reliable distance results even when the size of the two triangles differ very much?

Greetings and good work!

Statistics: Posted by Genscher — Mon Nov 13, 2006 11:08 pm