I created the following setup:
Shape A:
Pyramid shape with height = 2 and width = 1. The origin is located at 0.25 * height.
Shape B:
Triangle shape with vertices (0,1,0), (-1,-1,0) and (1,-1,0)
Both shapes have identity orientations at their source and target positions. This means there is no relative rotation. The first shape is initialized at (0,5.5,0) and moves down to (0,1.5,0). The other shape is initialized at (0,0,0) and moves up to (0,4,0). I should also note that I used btConvexHullShape for both shapes.
Basically the distance between both shapes is 4m and they travel 8m relative to each other. This means the TOI should be 0.5. My code returned the wrong result, so I reproduced the setup in Bullet and I get the same error. So I wonder if something is wrong with the original algorithm? What seems to happen is that directly in the first iteration the origin is found. I tried to visualize the test case, but Bullet's debug functionality is very limited. Anyway, the visualization matches the actual result so you should get the idea.
I created at test case in Bullet which I attach to this message. So you can look for yourself. Maybe it is something simple, like not using the API correctly. I needed to change three files. You might consider keeping the btConvexHull.h file since it was not const correct and I needed to fix this...
Cheers,
-Dirk
Bug in btSubsimplexConvexCast
-
- Posts: 861
- Joined: Sun Jul 03, 2005 4:06 pm
- Location: Kirkland, WA
Bug in btSubsimplexConvexCast
You do not have the required permissions to view the files attached to this post.
-
- Posts: 861
- Joined: Sun Jul 03, 2005 4:06 pm
- Location: Kirkland, WA
Re: Bug in btSubsimplexConvexCast
The funny thing is that if you use a box shape with the same quadratic bottom face and same setup you get the correct result. Just replace (copy/paste) the pyramid setup with the below code if you are interested:
Code: Select all
float ex = 1.0f;
float ey = 0.5f;
float ez = 0.5f;
shapeA->addPoint( btVector3( -ex, -ey, ez ) );
shapeA->addPoint( btVector3( ex, -ey, ez ) );
shapeA->addPoint( btVector3( ex, ey, ez ) );
shapeA->addPoint( btVector3( -ex, ey, ez ) );
shapeA->addPoint( btVector3( -ex, -ey, -ez ) );
shapeA->addPoint( btVector3( ex, -ey, -ez ) );
shapeA->addPoint( btVector3( ex, ey, -ez ) );
shapeA->addPoint( btVector3( -ex, ey, -ez ) );
-
- Site Admin
- Posts: 4221
- Joined: Sun Jun 26, 2005 6:43 pm
- Location: California, USA
Re: Bug in btSubsimplexConvexCast
If you replace the convexCaster by the btGjkConvexCast it works fine (this is the basic convervative advancement, without merging the CA and GJK loop as done in btSubsimplexConvexCast).
And if the convex shape is centered around the origin it works fine too:
I haven't had time to look into the issue with the btSubsimplexConvexCast, but I expect it to be an implementation problem, rather then algorithmic.
Thanks for the report!
Erwin
And if the convex shape is centered around the origin it works fine too:
Code: Select all
btConvexHullShape* shapeA = new btConvexHullShape;
shapeA->addPoint( btVector3( 0.0f, 0.50f * h, 0.0f ) );
shapeA->addPoint( btVector3( -r, -0.5f * h, r ) );
shapeA->addPoint( btVector3( r, -0.5f * h, r ) );
shapeA->addPoint( btVector3( r, -0.5f * h, -r ) );
shapeA->addPoint( btVector3( -r, -0.5f * h, -r ) );
Thanks for the report!
Erwin
-
- Posts: 861
- Joined: Sun Jul 03, 2005 4:06 pm
- Location: Kirkland, WA
Re: Bug in btSubsimplexConvexCast
When I met with Gino he mentioned that he uses a new approach where he doesn't move the Minkowski sum anymore. Do you know how this works?
I know that the "centerer" pyramid works, but this is not a solution to the problem. The algorithm or implementation should work with any convex hull.
W.r.t the other method you mention I think I remember that this approach uses two nested iterative methods (CA and GJK), right? So this is not very tempting from a perfomance perspective.
I look into the problem tomorrow again and let you know if I find a solution.
Cheers,
-Dirk
I know that the "centerer" pyramid works, but this is not a solution to the problem. The algorithm or implementation should work with any convex hull.
W.r.t the other method you mention I think I remember that this approach uses two nested iterative methods (CA and GJK), right? So this is not very tempting from a perfomance perspective.
I look into the problem tomorrow again and let you know if I find a solution.
Cheers,
-Dirk
-
- Site Admin
- Posts: 4221
- Joined: Sun Jun 26, 2005 6:43 pm
- Location: California, USA
Re: Bug in btSubsimplexConvexCast
I wouldn't exaggerate the performance difference, especially when all code and data fits in cache/local store (GJK typically uses less then 5 iterations), but I like to see issue bug fixed.W.r.t the other method you mention I think I remember that this approach uses two nested iterative methods (CA and GJK), right? So this is not very tempting from a perfomance perspective.
If you can help finding out what the issue is, that would be great.
Thanks for the feedback,
Erwin
-
- Site Admin
- Posts: 4221
- Joined: Sun Jun 26, 2005 6:43 pm
- Location: California, USA
Re: Bug in btSubsimplexConvexCast
While writing a book section on conservative advancement, I got back to this issue and found the issue to be in the support mapping for the minkowski sum shape.
Support mapping for Minkowski sum/difference A-B should be Sa(v) - Sb(-v). It wrongly was Sa(v)+Sb(v), note the lack of minus signs.
Identical to using a minkowski sum shape is to directly use two separate support mapping calls, as is generally used in GJK:
It has been fixed in the bullet.googlecode.com repository, available in upcoming Bullet 2.68. In addition, the btSubsimplexConvexCast now returns the hitpoint.
Thanks Dirk for the reproduction case!
Erwin
Support mapping for Minkowski sum/difference A-B should be Sa(v) - Sb(-v). It wrongly was Sa(v)+Sb(v), note the lack of minus signs.
Identical to using a minkowski sum shape is to directly use two separate support mapping calls, as is generally used in GJK:
Code: Select all
supVertexA = interpolatedTransA(m_convexA->localGetSupportingVertex(-v*interpolatedTransA.getBasis()));
supVertexB = interpolatedTransB(m_convexB->localGetSupportingVertex(v*interpolatedTransB.getBasis()));
w = supVertexA-supVertexB;
Thanks Dirk for the reproduction case!
Erwin