Collision detection failed for Ellipsoid shapes

Post Reply
closer
Posts: 5
Joined: Tue Nov 19, 2019 1:09 pm

Collision detection failed for Ellipsoid shapes

Post by closer »

I create Ellipsoid shape by btMultiSphereShape. I just use the collision detection without the dynamics. There are 1,900 Ellipsoid in a box. I need to detect the colliders between them. if object A is collide with others around it, I adjust its position and oriention to decrease colliders, do this one by one, loop by loop, untill no colliders is detected. I use btCollisionWorld->contactTest to compute Penetration depth and collision objects. During runing program, the cmd window print some information like this:
btGjkPairDetector maxIter exceeded:1002
sepAxis=(-0.143599,0.031060,0.286383), squaredDistance=0.103600, shapeTypeA=9, shapeTypeB=9

The program finished without no colliders. However, after drawing those ellipsoids in AutoCAD with the bullet Calculation results(worldTransform), A few overlaps is found. Then I try to change the margin of btCollisonShape to 0.1 and 0.2, but this problem still exits. The semimajor axis of ellipsoid is range from 2.5 to 10. If I use btSphereShape or btConvexHullShape to do it, the program goes well, and no overlaps occur in CAD. Any Suggestion?

The code to create ellipsiod shape

Code: Select all

[/size]
class EllipsoidShape : public btMultiSphereShape
{
public:
	EllipsoidShape(const btVector3& radii, btScalar margin = CONVEX_DISTANCE_MARGIN, btVector3&& position = btVector3(0.0, 0.0, 0.0), btScalar radius = 1.0);
};
EllipsoidShape::EllipsoidShape(const btVector3& radii, btScalar margin, btVector3&& position, btScalar radius)
: btMultiSphereShape(&position, &radius, 1), m_volume(4.0 / 3.0 * SIMD_PI * radii.getX() * radii.getY() * radii.getZ())
{
	m_userIndex = ELLIPSOID_SHAPE;
	setLocalScaling(radii);
	setMargin(margin);
	recalcLocalAabb();
}
Function to set transform

Code: Select all

void AggregatePacking::setCollisionObjectTransform(btCollisionObject* colObj, const btVector3& position, const btQuaternion& orientation) const
{
	btTransform tr;
	tr.setOrigin(position);
	tr.setRotation(orientation);
	colObj->setWorldTransform(tr);
	m_collisionWorld->refreshBroadphaseProxy(colObj)
}
User avatar
drleviathan
Posts: 849
Joined: Tue Sep 30, 2014 6:03 pm
Location: San Francisco

Re: Collision detection failed for Ellipsoid shapes

Post by drleviathan »

The GJK algorithm uses a while(true) loop when trying to prove the origin is either inside or outside the Minkowski sum. The loop has exit cases for when poof is determined and a final "max iterations" exit case. Your configuration is looping "forever" and finally hitting max iterations. The relevant code in the loop looks like this:

Code: Select all

                //degeneracy, this is typically due to invalid/uninitialized worldtransforms for a btCollisionObject
                if (m_curIter++ > gGjkMaxIter)
                {
#if defined(DEBUG) || defined(_DEBUG)

                    printf("btGjkPairDetector maxIter exceeded:%i\n", m_curIter);
                    printf("sepAxis=(%f,%f,%f), squaredDistance = %f, shapeTypeA=%i,shapeTypeB=%i\n",
                           m_cachedSeparatingAxis.getX(),
                           m_cachedSeparatingAxis.getY(),
                           m_cachedSeparatingAxis.getZ(),
                           squaredDistance,
                           m_minkowskiA->getShapeType(),
                           m_minkowskiB->getShapeType());

#endif
                    break;
                }
If your object's worldTransform is NOT invalid, then it would mean the GJK algorithm is wandering around on a flat-ish face of the Minkowski sum and fails to prove the origin is inside or out. I'm having trouble imagining how this could happen between two convex shapes that don't have any truly flat faces. The curvature would always be non-zero for an ellipse so we would expect each loop of the GJK algorithm to converge.

I would ask the following questions:

(1) Are you using 32-bit or 64-bit calculations? And if you're using 32-bit: are your objects using large translations in their transforms such that you might run into floating-point error? By "large" I would guess floating point error might creep into these calculations outside of a few tens of thousands of meters from the origin.

(2) When the GJK algorithm fails: what is the overlap according to CAD? We would expect the overlap to be small since otherwise the GJK algorithm is typically very fast at finding the origin. But how small is it? Is it small enough to be acceptable error? What would be acceptable error for you?

(3) When the GJK algorithm fails: are there any consistent aspects of the failure? That is, does it happen randomly over the elliptical shapes, or is it always near certain max/min of the shapes or always for particular scalings? Does it only happen between one big and one small ellipse, or only between big ellipses?

Edit to fix typos.
User avatar
Erwin Coumans
Site Admin
Posts: 4221
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: Collision detection failed for Ellipsoid shapes

Post by Erwin Coumans »

drleviathan makes good points.

Aside from that, you could provide a full working small example (single c++ file, no dependencies other than Bullet) and file an issue here:
https://github.com/bulletphysics/bullet3
it accepts zip file attachments, or just add the code inline.
closer
Posts: 5
Joined: Tue Nov 19, 2019 1:09 pm

Re: Collision detection failed for Ellipsoid shapes

Post by closer »

ellipsoid.zip
(82.42 KiB) Downloaded 578 times
Thanks for the help of drleviathan and Erwin Coumans. I find two wrongly detected objects in part of my calculations. I use the two objects to do collision test in a single cpp file which can be found in attachments. The result of world->contactPairTest is below:
btGjkPairDetector maxIter exceeded:1002
sepAxis=(-0.232991,0.022933,0.050351), squaredDistance = 0.057346, shapeTypeA=9,
shapeTypeB=9
0----1 0.141177
The maxIter still exceeded the limit and a positive distance(0.141177) is gotten. How could this situation happens?
For drleviathan's questions:
I use 32-bit calculations, but the ellipsoids are limited in a box with minAabb(-50, -50, -50) and maxAabb(50, 50, 50). I guess no large translations happen. The overlap according to CAD is very small. I attached two pictures to show that.
Is this case normal? Do have any methods to avoid this? Look forward to any reply.
steven
Posts: 83
Joined: Mon Nov 05, 2018 8:16 am
Location: China

Re: Collision detection failed for Ellipsoid shapes

Post by steven »

adding this shape->setMargin(0) can avoid this issue but i still can't understand what caused this issue.
i have some questions when review this code below in line 76 of btMultiSphereShape.cpp.
temp = (*pos) * m_localScaling + vec * m_localScaling * (*rad) - vec * getMargin();
1. why the origin pos also have to multiply by the m_localScaling? i think only the rad need this.
2. why it have to subtract the vec*getMargin? this function is localGetSupportingVertexWithoutMargin that means no need the Margin.

thanks.
closer
Posts: 5
Joined: Tue Nov 19, 2019 1:09 pm

Re: Collision detection failed for Ellipsoid shapes

Post by closer »

steven wrote: Mon Nov 25, 2019 2:38 am adding this shape->setMargin(0) can avoid this issue but i still can't understand what caused this issue.
i have some questions when review this code below in line 76 of btMultiSphereShape.cpp.
temp = (*pos) * m_localScaling + vec * m_localScaling * (*rad) - vec * getMargin();
1. why the origin pos also have to multiply by the m_localScaling? i think only the rad need this.
2. why it have to subtract the vec*getMargin? this function is localGetSupportingVertexWithoutMargin that means no need the Margin.

thanks.

Thanks to steven. I think, for an object A with affine transformation T(x) = Mx+O, and B = MA + O. Then a support mapping for B=T(A), is SB(v) = MSA(v *M)) + O. So I think the support point code for scaling and translation is like this:

Code: Select all

temp[i] = (*pos) + m_localScaling * (vec * m_localScaling).normlized() * (*rad) - vec * getMargin();
I create a subclass and rewrite
localGetSupportingVertexWithoutMargin
and
batchedUnitVectorGetSupportingVertexWithoutMargin
. Then the problem seems to solved, no maxIter exceeded and a negative distance is detected(-0.10573). However, I still find overlap in CAD. The same as previous, some overlaps are really big. I don't know what does the positive distance mean? In my program I recognize colliders by negative distances, should I consider the positive distances as collision events
steven
Posts: 83
Joined: Mon Nov 05, 2018 8:16 am
Location: China

Re: Collision detection failed for Ellipsoid shapes

Post by steven »

temp = (*pos) + m_localScaling * (vec * m_localScaling).normlized() * (*rad) - vec * getMargin();

feel it should be like this: temp = (*pos) + m_localScaling * (vec / m_localScaling).normalized() * (*rad) - vec * getMargin();
i will check if the points on the ellipsoid can be expressed by this function later.

negative distance means a collision event.

thanks
closer
Posts: 5
Joined: Tue Nov 19, 2019 1:09 pm

Re: Collision detection failed for Ellipsoid shapes

Post by closer »

I have to give up in the use of btMultiSphereShape, I will use polyhedrons to fit ellipsoild to do collision dectection. Look forword the update of bullet, I guess the relative codes could have some mistakes.
Post Reply