Gjk support function for arbitrary convex mesh

Post Reply
Gumba
Posts: 3
Joined: Thu Jun 10, 2021 4:45 am

Gjk support function for arbitrary convex mesh

Post by Gumba »

Hi,

I'm trying to implement my own version of GJK and wasn't sure on how to implement the support function for an arbitrary convex mesh, the one which takes a direction as input and outputs the farthest vertex in that direction. Digging through Bullet's source, I found the functions btTriangleMeshShape::localGetSupportingVertex and btTriangleMeshShape::processAllTriangles in BulletCollision/CollisionShapes/btTriangleMeshShape.cpp, which I think is where it's done.

Do I understand this correctly that it's just brute forcing through all the vertices of the mesh and calculating the dot product for them (after an AABB test) or are there some further optimizations which I'm missing?
User avatar
drleviathan
Posts: 849
Joined: Tue Sep 30, 2014 6:03 pm
Location: San Francisco

Re: Gjk support function for arbitrary convex mesh

Post by drleviathan »

Yes, as I recall (and it has been a few years since I looked at it) it is brute force against the points. You could imagine writing spatial map lookup logic to optimize search in a large point cloud, however such a strategy would be slower in practice than brute force below some number of points N, due to memory coherence and branching costs. The particular value of N would depend on how clever is the algorithm, however my guess is it would be higher than is typically used by Bullet customers who care deeply about real-time performance. Non-real-time customers will may be content to wait, or throw more CPU resources at it so they don't have to wait too long.

Also, if you're being clever then you would consider the question: How accurate of an answer is necessary? Because approximate algorithms will often be faster.

A few years ago I thought we needed a stand-alone GJK algorithm and decided to write my own instead of figuring out how to bend Bullet's implementation to my will. It was a maze of twisty passages when working out the final bugs but ultimately fun and educational. Unfortunately we never did end up using it. If you would like to have a copy I could probably dig it up for you. I think it lives under an Apache License.

Meanwhile: btTriangleMeshShape is a base class for concave shapes and I wouldn't expect it to support the GJK algorithm. Perhaps you're thinking about btConvexTriangleMeshShape?
Gumba
Posts: 3
Joined: Thu Jun 10, 2021 4:45 am

Re: Gjk support function for arbitrary convex mesh

Post by Gumba »

Ah, that makes sense. I was trying to implement this hill climbing algorithm https://stackoverflow.com/a/2769176 but couldn't think of an efficient data structure to store all neighbouring vertices for every vertex. But I agree, while this would probably have to test less vertices, it would also have much worse branch prediction and cache-friendliness. I guess I also go with this O(n) approach then, if it's even fast enough for such a widely used library like Bullet.

I thought of btTriangleMeshShape, but I didn't realize that those two functions are overriden in the derived types. I think now this is where the actual work is done with (int)scaled.maxDot looping over all vertices:

Code: Select all

btVector3 btConvexHullShape::localGetSupportingVertexWithoutMargin(const btVector3& vec) const
{
	btVector3 supVec(btScalar(0.), btScalar(0.), btScalar(0.));
	btScalar maxDot = btScalar(-BT_LARGE_FLOAT);

	// Here we take advantage of dot(a, b*c) = dot(a*b, c).  Note: This is true mathematically, but not numerically.
	if (0 < m_unscaledPoints.size())
	{
		btVector3 scaled = vec * m_localScaling;
		int index = (int)scaled.maxDot(&m_unscaledPoints[0], m_unscaledPoints.size(), maxDot);  // FIXME: may violate encapsulation of m_unscaledPoints
		return m_unscaledPoints[index] * m_localScaling;
	}

	return supVec;
}
I would very much be interested in your version of GJK, if it's not too much of a hassle to find it. Bullet's version seems very abstracted and somewhat hard to find the relevant parts.

Thank you for your help!
User avatar
drleviathan
Posts: 849
Joined: Tue Sep 30, 2014 6:03 pm
Location: San Francisco

Re: Gjk support function for arbitrary convex mesh

Post by drleviathan »

I was able to dig up the old code. It turns out: we did use it for something after all. I had forgotten.

In any case, I've pulled the relevant files out into a separate github repository so it can become a stand-alone utility. It is incomplete because there is a missing class called Transform whose original code would have dragged unhelpful dependencies so I'm leaving it out for now: its implementation is left as an exercise for the reader. Also, the unit tests have a Qt dependency which I don't want so I'm leaving those in a non-compiling state. Someday I'll get around to cleaning up that repo and wrangle it into a more useful example. In the meantime: perhaps you will find it helpful.

Note, this GJK implementation only returns true or false for convex overlap. It does not compute closest approach between two convex shapes.

https://github.com/AndrewMeadows/gjk.git
Gumba
Posts: 3
Joined: Thu Jun 10, 2021 4:45 am

Re: Gjk support function for arbitrary convex mesh

Post by Gumba »

Thank you a lot!

I will dig into this over the weekend.
Post Reply