Collision algorithm for area check

[AndreaCatania]

@erwincoumans in godot engine we are using the gjk/epa algorithm to detect area overlaps.

That algorithm is really slow/non-optimal for such use. What is the optimal algorithm that bullet provides, or one that you can advice to use, for areas overlap detection? Is the SAT already available in bullet?

Thanks!

[erwincoumans]

(1) What is the exact shape of the area? If it is an axis aligned bounding box, you can use the broadphase checks. Otherwise, it depends on the shape.

(2) What information do you want? Just an array of objects that overlap, or more (depth, normal, contact positions etc)?

[AndreaCatania]

I need to support all the convex shapes, and I would just need an array of bodies that overlaps. I was thinking about SAT algorithm.

[erwincoumans]

Yes, Bullet has the SAT implementation, but it needs to be organized to get what you need.

For the convex shapes, you need to call initializePolyhedralFeatures, so SAT can be used.
To try out SAT, you can set dispatchInfo.m_enableSAT = true.

The code is here:
https://github.com/bulletphysics/bullet3/blob/master/src/BulletCollision/CollisionDispatch/btConvexConvexAlgorithm.cpp#L489

You probably only need
foundSepAxis = btPolyhedralContactClipping::findSeparatingAxis

It would probably be better to implement a dedicated area check using this:
gather all objects that have AABB overlap (using a broadphase query)
for those potential colliders, use this SAT check.

In that case, don't m_enableSAT (since GJK/EPA is likely better quality/faster for regular physics) but just use your newly written area check using SAT.

[AndreaCatania]

Perfect, thanks for these info, I'll integrate it and let you know.

[AndreaCatania]

The function foundSepAxis = btPolyhedralContactClipping::findSeparatingAxis is really good for what I've to do, though it uses btConvexPolyhedron and not regular shapes.

I'm interested to know why such chose. It's much optimal the curren algorithm compared to the (eventual one) that uses primitive shapes?

I'm asking because this function forces me to also maintain a list of polyhedron, which is not so nice.