3D collision detection : convex hull vs convex hull , need Position and Normal

Question

I want to know an approximate 3D position and 3D normal of collision site between two 3D convex hulls (A vs B).

The CPU in parenthesis shows relative CPU-time needed in my finished program.

Part 1: Early-out (CPU 1%)

In the first step, I use a very cheap algorithm - separation axis theorem.
For example, I use 15 axis for 2 cubes. (In real cases, the shapes are more complex.)
If there is at least 1 axis that can separate, return "no-collide".
Otherwise, do the next part.

Part 2: Vertex vs Volume (CPU 10%)

• Check every vertices of A - whether it is inside B.
• Check every vertices of B - whether it is inside A.

Part 3: Edge vs Edge (CPU >20%)

There is a strange case e.g. https://gamedev.stackexchange.com/questions/75437/collision-detection-3d-rectangles-using-sat . I stole the image from there:-

Thus, I also need edge vs edge.

• For every pair of A & B edges (12 * 12 = 144 pairs), find a nearest point in edge of A against the edge of B. Check whether the vertex is inside B.
• (vice versa) For every pair of B & A edges, check whether such vertex is inside A.

Wow, that is a lot of computation.
However, it is not over yet.

Problem

1. The reported collision position is not so accurate (left:current , right:wish) :-

   

   To solve it, I thought about generating a new convex shape = A intersect B.
   There are some C++ free libraries out there (e.g. OpenMesh), but I think it is too CPU-expensive.
   Note that I don't need it to be precisely correct.

2. It also sometimes reports wrong normal (left:current , right:wish) :-

   

   ^ This problem might be solved by adding edge (of A) vs face (of B) check, but that would make the whole collision detection even more expensive.

Question

It looks like common algorithms in the internet (from which I copy) recognizes only micro feature.
IMHO, the vertex-volume/edge-edge algorithm focus on topology rather that the fact that both shapes are solid volumes.

What is the algorithm that is more accurate (1st priority) and perhaps cheaper?
My approach might be wrong at the foundation level.

To speed things up, I already did some pruning e.g. select only pair of edge A & B that is close together.

References :-

• Algorithms for Collision Detection between Arbitrarily sized Convex Polygons checks only whether collision occurs.

• https://pybullet.org/Bullet/BulletFull/btBoxBoxDetector_8cpp_source.html : inspiring full code of box vs box collision detection in Bullet Physics library - it is hard to understand.

• https://math.stackexchange.com/questions/397413/determine-direction-of-minimum-overlap-of-convex-polygons Unanswered Math question that is very similar to this.

Edit (10 days later)

Now, I can find all intersecting convex point (the convex is depicted as a pink triangle/rectangle) :-

Here is how I find the normal.

For-each separating axis (all=15 axis), I project the pink convex on to the axis.
The axis that yields the shortest projection distance (pink arrow) should be the direction of normal.

My above assumption is often correct (e.g. left), but sometimes wrong (e.g. right).
How to improve it CPU-cheaply?

Answer 1

Game engines typically simulate time a series of discrete steps. As a consequence, the collision system can get into difficult (computationally expensive) cases due to interpenetration (your case) or when things are moving fast -tunneling where A is on one side of B at step N and entirely on the other side of B at step N+1. It is even harder if you need to deal with multibody contact or continuous contact or non convex or jointed or soft object. Yikes! we are simulating the whole world.

You want to do "game physics" and use approximations to buy back frame rate... In the end, you can cover a lot of error with a bunch of smoke puffs or light flares. :-)

There is a class of algorithms which explicitly take simulated time into account to help the collision system. There are a lot of ways to implement a "continuous collision detection" system. You can start here, but you should read widely first, before you commit to code. Fortunately, there is a lot of literature on collision. here is a good place to start https://docs.unity3d.com/Manual/ContinuousCollisionDetection.html https://pybullet.org/Bullet/phpBB3/viewtopic.php?t=20

Here is one suggested heuristic that might work in your existing system.... This heuristic technique might work in a game like astroids 3d where objects float in freely in space. That might be good enough for what you need.

Image every object stores its current state vector (position, orientation, velocity, acceleration, rotation... ) and its previous state vector from the previous time step.

Suppose you detected a potential collision between objects A and B at time=current.

For time=previous, assume A and B are not in contact.

Compute the closest points on the surfaces of A and B, respectively at time=prev using the previous state vectors of A and B. (closestA, closestB).

The line segment (closestA,closestB) will have non-zero length at time=previous. You could just use closestB for your position and normal, but it would have some error proportional to the length of the line segment..

So do a binary search in time, and minimize the error, by finding the time when A is arbitrarily close to B . At each pass of your search, cut search time step size in half. 0.5, 0.25, 0.125.. until the length of (closestA, closestB) is below an error threshold or you give up.

That should give you an acceptable approximate solution for the simple cases...

Also, you said you are using the separation axis theorem as your "first check". That actually sounds expensive to me if that is really the "first check"..

The fastest computation is the one you do not do, so fast collision means lots of cheap pretesting and avoiding the expensive cases.

You can consider using spatial techniques like a coarse spatial grid and only check objects which you already know are near each other.

Also, the sphere-sphere test is a very fast pretest to see if the bounding sphere of two convex object are even overlapping.