title: 3D collision detection : convex hull vs convex hull , need Position and Normal
body: <p>I want to know an approximate 3D position <strong>and</strong> 3D normal of collision site between two 3D convex hulls (<code>A</code> vs <code>B</code>).      </p>
  
  <p>The CPU in parenthesis shows relative CPU-time needed in my finished program.</p>
  
  <h2><strong>Part 1</strong>: Early-out (CPU 1%)</h2>
  
  <p>In the first step, I use a very cheap algorithm - <a href="https://en.wikipedia.org/wiki/Hyperplane_separation_theorem" rel="nofollow noreferrer">separation axis theorem</a>.<br>
  For example,  I use <a href="https://www.gamasutra.com/view/feature/131598/advanced_collision_detection_.php?page=3" rel="nofollow noreferrer">15 axis</a> for 2 cubes.  (In real cases, the shapes are more complex.)<br>
  If there is at least 1 axis that can separate, <code>return "no-collide"</code>.<br>
  Otherwise, do the next part.   </p>
  
  <h2><strong>Part 2</strong>: Vertex vs Volume (CPU 10%)</h2>
  
  <ul>
  <li>Check every vertices of <code>A</code> - whether it is inside <code>B</code>.      </li>
  <li>Check every vertices of <code>B</code> - whether it is inside <code>A</code>.     </li>
  </ul>
  
  <p><a href="https://i.stack.imgur.com/KiiFV.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/KiiFV.png" alt="enter image description here"></a></p>
  
  <h2><strong>Part 3</strong>:  Edge vs Edge (CPU >20%)</h2>
  
  <p>There is a strange case e.g. <a href="https://gamedev.stackexchange.com/questions/75437/collision-detection-3d-rectangles-using-sat">https://gamedev.stackexchange.com/questions/75437/collision-detection-3d-rectangles-using-sat</a> .  I stole the image from there:-</p>
  
  <p><a href="https://i.stack.imgur.com/z0pDg.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/z0pDg.png" alt="enter image description here"></a></p>
  
  <p>Thus, I also need <strong>edge</strong> vs <strong>edge</strong>.</p>
  
  <ul>
  <li>For every pair of A &amp; B edges (12 * 12 = 144 pairs), find a nearest point in  edge of <code>A</code> against the edge of <code>B</code>.  Check whether the vertex is inside <code>B</code>.    </li>
  <li>(vice versa) For every pair of B &amp; A edges, check whether such vertex is inside <code>A</code>.      </li>
  </ul>
  
  <p>Wow, that is a lot of computation.<br>
  However, it is not over yet.      </p>
  
  <h2>Problem</h2>
  
  <ol>
  <li><p>The reported collision position is not so accurate (left:current , right:wish)  :- </p>
  
  <p><a href="https://i.stack.imgur.com/D74nK.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/D74nK.png" alt="enter image description here"></a></p>
  
  <p>To solve it, I thought about generating a new convex shape = <code>A intersect B</code>.<br>
  There are some C++ free libraries out there (e.g. <a href="https://www.openmesh.org/license/" rel="nofollow noreferrer">OpenMesh</a>), but I think it is too CPU-expensive.<br>
  Note that I don't need it to be precisely correct.</p></li>
  <li><p>It also sometimes reports wrong normal (left:current , right:wish)  :-</p>
  
  <p><a href="https://i.stack.imgur.com/p7ZBo.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/p7ZBo.png" alt="enter image description here"></a></p>
  
  <p>^ This problem might be solved by adding <strong>edge</strong> (of A) vs <strong>face</strong> (of B) check, but that would make the whole collision detection even more expensive.</p></li>
  </ol>
  
  <h2>Question</h2>
  
  <p>It looks like common algorithms in the internet (from which I copy) recognizes only micro feature.<br>
  IMHO, the vertex-volume/edge-edge algorithm focus on topology rather that the fact that both shapes are <em>solid</em> volumes.        </p>
  
  <p>What is the algorithm that is more accurate (1st priority) and perhaps cheaper?<br>
  My approach might be wrong at the foundation level.      </p>
  
  <p>To speed things up, I already did some pruning e.g. select only pair of edge A &amp; B that is close together.       </p>
  
  <p><strong>References :-</strong></p>
  
  <ul>
  <li><p><a href="https://stackoverflow.com/questions/14629983/algorithms-for-collision-detection-between-arbitrarily-sized-convex-polygons?rq=1">Algorithms for Collision Detection between Arbitrarily sized Convex Polygons</a>  checks only whether collision occurs.</p></li>
  <li><p><a href="https://pybullet.org/Bullet/BulletFull/btBoxBoxDetector_8cpp_source.html" rel="nofollow noreferrer">https://pybullet.org/Bullet/BulletFull/btBoxBoxDetector_8cpp_source.html</a>  :  inspiring full code of box vs box collision detection in Bullet Physics library - it is hard to understand.</p></li>
  <li><p><a href="https://math.stackexchange.com/questions/397413/determine-direction-of-minimum-overlap-of-convex-polygons">https://math.stackexchange.com/questions/397413/determine-direction-of-minimum-overlap-of-convex-polygons</a>  Unanswered Math question that is very similar to this.</p></li>
  </ul>
  
  <h2>Edit (10 days later)</h2>
  
  <p>Now, I can find all intersecting convex point (the convex is depicted as a pink triangle/rectangle) :-
  <a href="https://i.stack.imgur.com/OZ5HQ.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/OZ5HQ.png" alt="enter image description here"></a></p>
  
  <p>Here is how I find the normal.</p>
  
  <p>For-each separating axis (all=15 axis), I <strong>project</strong> the pink convex on to the axis.<br>
  The axis that yields the shortest <strong>projection</strong> distance (pink arrow) should be the direction of normal.</p>
  
  <p>My above assumption is often correct (e.g. left), but sometimes wrong (e.g. right).<br>
  How to improve it CPU-cheaply?</p>