# Looking for collision detection algorithms for broad and narrow phases between non-convex polyhedrons

I have some experiences on particle system simulation (namely DEM - Discrete element method), in which an individual particle with realistic shape (convex and non-convex) is approximated by gluing 3D spheres together (non-overlapping or overlapping), and act like rigid body. The collision detection is performed by the simplest sphere-sphere contact.

Nevertheless, for particle shape representing by polyhedrons, almost all the collision detection algorithms for broad and narrow phases are based on convex polyhedron (e.g. GJK). For non-convex/concave shapes, convex decomposition is required to divide the concave object into many convex components (e.g. V-HACD).

At this point, I really want to know the details on:

1) how to store the concave objects via many convex components into memory (like BSP tree?);

2) collision detection and contact forces calculation between convex-concave, concave-concave objects.

I have searched quite a few relevant books like "Real-time collision detection" and "3D game engine design", etc, unfortunately I haven't find any details on this topic yet. Could some veteran game developers give some advice or insight on how to implement collision between concave objects?

Cheers,

David

Update 1:

Seems the physics engines likes Bullet3 and reactPhysics3D are able to simulate collision of non-convex objects. Can someone give some rough idea on how to do this? before I dig into the source codes, since i have only some academic experiences on molecular dynamics / DEM simulations mainly based on 3D spheres.

• It sounds like you already have solutions applicable to broad & narrow phases: approximating with spheres and V-HACD. Those together reduce the problems to ones with well-known solutions: sphere-sphere (ie. radius checks) and convex-convex polyhedron (eg. GJK). Have you encountered a specific problem or limitation with doing collision detection this way? If so, please describe that issue and users here can try to suggest algorithms specifically to address that issue. This helps focus the question so it has a correct answer rather than an open-ended list of algorithm possibilities. – DMGregory Sep 1 '17 at 17:03
• Well, what i want to know is how to compute the contact forces on concave objects which has been decomposed into many convex objects. We treat the composite convex (child convex) as a whole rigid body (original concave object), calculate the forces on any of the child convex, and do cross production of these forces as a resulting force on the concave objects? – KOF Sep 1 '17 at 17:38
• Why would it need to be different from combining multiple contact forces/impulses/torques on a single convex collider? – DMGregory Sep 1 '17 at 17:55
• DMGregory: you are correct :), I forgot this. The remaining problem is the data structure implementation of such concave object, and the procedure of collision detection from other objects (need loop over every child convex?) – KOF Sep 1 '17 at 18:06
• Again, it's unclear to me why this needs a special solution. Would storing the constituent colliders in a simple array or list and iterating over each in turn not be sufficient? What specific behaviour or issue do you feel you need a specialized data structure to address? – DMGregory Sep 1 '17 at 18:54