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.

Improve this question
\$\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 ♦
    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
    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 ♦
    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
    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 ♦
    Sep 1, 2017 at 18:54

1 Answer 1

Reset to default
4
\$\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.

Improve this answer
\$\endgroup\$
1
  • \$\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
    Sep 1, 2017 at 17:45

You must log in to answer this question.

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