EPA handles co-planar triangles in simplex wrong

[GoogleCodeExporter]

In the EPA stage of btGjkEpa2.cpp, the logic for dealing with co-planar (or 
nearly co-planar) triangles in the expanding simplex is wrong. This leads to 
all sorts of stability problems with collisions, for example between a softbody 
and a static box.

When there are co-planar triangles, the planes of both triangles have the same 
distance to the origin. The preferred triangle will be the one which contains 
the projection of the origin.

The code attempts to achieve this by calculating how far out the projection of 
the origin is from the triangle (if it is outside the triangle) (this is stored 
in face->p, which is negative when the projection of the origin is outside the 
triangle), and including that in the distance comparison when finding the 
triangle nearest the origin.

There are several problems with it though:
1) The comparison in findbest():
      if((f->p>=maxp)&&(sqd<mind))
   is wrong as it does not take into account when f->p > maxp && sqd == mind, or if sqd is ever so slightly larger than mind (due to floating point vagaries). This can lead to the best triangle (the one which the origin projects into) not being chosen, but instead the triangle with the origin projection outside of it.

2) Triangles with an outside origin projection are not selected as overall best 
if there is a triangle with the origin projecting inside, even if that triangle 
has a much worse distance.

3) Distance to triangle plane and distance to edge along the triangle plane is 
generally not sufficient to correctly determine distance to triangle. There are 
regions where the distance to vertices has to be used.

All that combined means that the correct best triangle may not be chosen, but 
instead of 2nd best, or even worse.
This can manifest itself by making a collision surface appear lumpy. For 
example, the sparse sdf used for softbody collisions can have fictional sharp 
cliffs in it which leads to the softbody collision badly jittering or some 
points going through the collision object.
This may also be the source of a number of the internal edge collision problems.

I have attached a patch for btGjkEpa2.cpp which uses the correct distance to 
triangle calculations to find the best triangle. It greatly improves 
softbody-hardbody collision quality.

Original issue reported on code.google.com by ja...@orcon.net.nz on 12 Mar 2012 at 9:24

Attachments:

• btGjkEpa2.diff

[GoogleCodeExporter]

Attached a simple test program. It uses the sparse SDF to scan a section around 
the centre of the top of a cube. The sparse SDF uses the GJK/EPA code to 
compute distances to the surface, and from that derive normals.
The expected normal is (0,1,0). Current implementation of EPA shows many errors 
with normals being off by up to 90 degrees. Patched code passes with no errors.

Original comment by ja...@orcon.net.nz on 13 Mar 2012 at 12:20

Attachments:

• btGjkEpa2_test.cpp

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

Thanks a lot for the report and test.

The patch breaks the attached BasicDemo. It forces the use of GJK/EPA instead 
of the box-box algorithm. I haven't looked into why yet, perhaps you can check 
it out? (just copy the files over Bullet/Demos/BasicDemo)

Original comment by erwin.coumans on 14 Mar 2012 at 4:40

Attachments:

• BasicDemo_EpaTest.zip

[GoogleCodeExporter]

There is indeed a numeric instability in the patch. This one should work better.

Original comment by ja...@orcon.net.nz on 15 Mar 2012 at 6:26

Attachments:

• btGjkEpa2.diff

[GoogleCodeExporter]

I reviewed your patch and it looks good to go. I do a bit more testing and 
commit it.

Thanks a lot for this!

Original comment by erwin.coumans on 16 Mar 2012 at 1:43

[GoogleCodeExporter]

Fixed in latest trunk: http://code.google.com/p/bullet/source/detail?r=2533

Thanks again,
Erwin

Original comment by erwin.coumans on 16 Mar 2012 at 7:00

• Changed state: Fixed