0
\$\begingroup\$

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.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – DMGregory ♦
    Commented Sep 1, 2017 at 17:03
  • \$\begingroup\$ 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? \$\endgroup\$
    – KOF
    Commented Sep 1, 2017 at 17:38
  • \$\begingroup\$ Why would it need to be different from combining multiple contact forces/impulses/torques on a single convex collider? \$\endgroup\$
    – DMGregory ♦
    Commented Sep 1, 2017 at 17:55
  • \$\begingroup\$ 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?) \$\endgroup\$
    – KOF
    Commented Sep 1, 2017 at 18:06
  • \$\begingroup\$ 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? \$\endgroup\$
    – DMGregory ♦
    Commented Sep 1, 2017 at 18:54

1 Answer 1

Reset to default
3
\$\begingroup\$

There are almost no algorithms to detect collision with a concave object, because there's no reason to have one. Every concave object can be approximated with convex object. See the following image for an example:

enter image description here

There are algorithms to convert a set of points defining a concave polygon to multiply convex ones. A very easy, but inefficient one would be to simply triangulate the object. You could improve the triangulation version by merging the triangles if the produced polygon stays convex, but this is a hill-climbing-esque algorithm, so it won't always produce the best possible combination.

\$\endgroup\$
3
  • \$\begingroup\$ thanks for the replay, Bálint. So how do calculate the contact forces on such decomposed system of convex objects? I really want to know the details on the data structure to store the child convex objects, and the accumulated forces acting on each child convex objects. This is not covered in any related books. \$\endgroup\$
    – KOF
    Commented Sep 1, 2017 at 17:45
  • \$\begingroup\$ "There is no reason to have one" – that's definitely not true, and you just created a simple such algorithm here, for a reason. Besides, you may want a more efficient algorithm than the one you just presented, as I guess it may not always be that efficient. \$\endgroup\$
    – HelloGoodbye
    Commented Jan 23 at 20:23
  • \$\begingroup\$ @HelloGoodbye Splitting objects up into convex shapes is a cost you only incur once (assuming your geometry isn't dynamic) and it's at worst equal to triangulating the objects, which is O(nlogn), but it's closer to linear. You can build a kd or BVH tree out of them to make finding the collision pairs logarithmic. The maximum number of triangles in a shape is equal to the number of faces, so you can express it in terms of faces: O(logn). GJK is linear on top of this, so worst case is O(N). I have my doubts you can do better than that. \$\endgroup\$
    – Bálint
    Commented Feb 28 at 15:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .