using Bullet: flying Triangles and SimdTransform's

Genscher · Post by **Genscher** » Tue Sep 12, 2006 6:33 pm

Hello!

We're one step away from switching from SOLID to Bullet.

GJKPairDetector / clostestPoints is working great and very accurate.

Now we try to use SubsimplexConvexCast::calcTimeOfImpact for our CCD.

We have starting position and end position of all triangle vertexes and use TriangleShape's as representation in bullet (all vertex positions of the triangles are global).
How do we use "SimdTransform fromA" and ""SimdTransform toA" (as example, then we know how to use it in general) to represent the position change of our three vertexes per triangle (no rotation)?
The demos doesn't help in that case.

Thank you very much in advance for your help!

Two more things:
1. Great! Bullet's distance calculation is faster than SOLID

2. we would love some option to set the accurancy of the calcTimeOfImpact return value (seems to be set to "epsilon = 0.0001f;").

Greetings so far!

Genscher · Post by **Genscher** » Wed Sep 13, 2006 10:25 am

Ok, my request seems to be to difficult.

Here in plain as example:

I have the positions of 3 vertexes forming a triangle:

v1 = (1,0,1)
v2 = (1,1,0)
v3 = (0,1,1)

Now, in the next step in is

v1 = (4,1,1)
v2 = (-1,3,1)
v3 = (-1,1,6)

How can I calculate the "SimdTransform fromA" and "SimdTranform toA" from that?
I like to start with fromA as identity matrix. But that's not mandatory

Thank you very much in advance!

Erwin Coumans · Post by **Erwin Coumans** » Wed Sep 13, 2006 11:41 pm

Bullet library so far focusses on rigid bodies. Your application seems to be deformable triangles. I've been thinking about supporting deformable triangles, but that is not implemented yet. There is no rigid transform that brings a triangle to its deformed state.

The idea to do time of impact using deformed triangles, is similar to the Conservative Advancement CCD used in http://www.continuousphysics.com/Bullet ... ection.pdf and in http://www.continuousphysics.com/ftp/pu ... e=fast.pdf ), and goes as follows:

First, we need a measure of transformation. We can take the center of the triangle (average of 3 points), and use that as linear transform. Then, we need a conservative estimate for the maximum travel that the deformed vertices can do. This can be done by taking the maximum distance the triangles move, relative to this center. The orientation can stay identity, or appoximated (for example using the triangle normal etc.)

Then, each iteration in the conservative advancement process, a safe upper bound is given and a fraction is calculated how much the triange can 'travel/deform'. We assume constant/linear deformation. After each step, we perform the actual deformation (for this fraction), and repeat the calculations.

This would give time of impact estimation for cloth triangles for example. But it can also apply to deforming tetrahedra, which is useful for deformation/finite element method (FEM) approaches, etc. In the case of tetrahedra, there is some work done, how to estimate a local coordinate frame, given the 4 vertices. That could be useful.

It wouldn't be too hard to implement, it's more a matter of time. My todo list is very long, both at work and for spare time fun-projects...

Thanks,
Erwin

Apart from that, adding selectable tolerance is possible.

Genscher · Post by **Genscher** » Mon Nov 13, 2006 11:08 pm

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: Select all

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;	
	
	GjkPairDetector	convexConvex(&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!

Genscher · Post by **Genscher** » Tue Nov 14, 2006 1:03 pm

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

Erwin Coumans · Post by **Erwin Coumans** » Tue Nov 14, 2006 7:41 pm

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

Genscher wrote: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

Genscher · Post by **Genscher** » Fri Nov 17, 2006 11:06 am

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: Select all


	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;	
	
	GjkPairDetector	convexConvex(&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!

Erwin Coumans · Post by **Erwin Coumans** » Sun Nov 19, 2006 5:53 pm

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: Select all

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

Thanks for the feedback,
Erwin

Genscher · Post by **Genscher** » Mon Nov 20, 2006 3:21 pm

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!

Erwin Coumans · Post by **Erwin Coumans** » Mon Nov 20, 2006 4:35 pm

Genscher wrote: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

Genscher · Post by **Genscher** » Mon Nov 20, 2006 7:27 pm

Good evening!

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

Genscher

Genscher · Post by **Genscher** » Wed Nov 22, 2006 5:36 pm

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: Select all

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!

Erwin Coumans · Post by **Erwin Coumans** » Wed Nov 22, 2006 7:02 pm

Genscher wrote: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

Real-Time Physics Simulation Forum

using Bullet: flying Triangles and SimdTransform's

using Bullet: flying Triangles and SimdTransform's

to put it simple...

New status

Found a paper about it

Re: Found a paper about it

bullet sample

gjk

Re: gjk

great

GJK

Re: GJK