This post is somewhat a description of what I’ve been doing recently. This week I’ve been searching for cloth simulation papers to get a bit out of rigid body dynamics since it is a well solved problem as discussed by the community. Last week I ended up finishing an implementation of contact point clustering using k-means. My experiments have shown that the optimization described in the excelent GPG4 article is available just to show how things got started. However, it can generate good results even if implemented naively, still leaving open doors for more optimization, such as the use of hysteresis to avoid jittering and the like. The video below was one of the first tests that showed some acceptable, still not plausable though, results.

We basically cluster contact points by the normals using k-means and reproject them on an average plane built from the contact points of a cluster. I call this the cluster plane. As opposed to maximizing contact point distance as was told in the GPG4 article, we build an approximate convex hull using the contact points for each cluster. I call this the cluster polygon. I used an algorithm similar to the convex pair contact point reduction. There can be a maximum of three manifolds. Roughly speaking, the optimization improved the simulation performance by an order of magnitude. For collisions between spheres and (potential) triangles I implemented and can recommend the holistic algorithm described in this paper simply because is direct and easy enough to implement in a week. Ideally my plan is to disregard the algorithm when a solution to the problem of collision between the other shapes and the internal edges of the potential triangles is implemented, leaving all mesh contacts generated by a single code path.

There can be as many clusters as necessary to make the simulation stable but I limit the number to three because there are three important cases to consider which makes a larger number of clusters unnecessary, and this optimization must worth the computational effort. One cluster if the shape is colliding with a plane, two if collinding with a wedge, and three with a corner. Remember that the only reason the normals are clustered is to reduce the number of contact points that are sent to the contact solver. So this is an optimization. Ideally you should make it an option using a macro/boolean. (I really need to add this to Bounce later.)

I also recommend associating a contact normal to a contact point, not to a manifold, which makes unnecessary project the penetration along the normal. So clearly the hull vs hull contact reduction is just a special case of cluster reduction.

Hi Irlan. Why there can be a maximum of three manifolds?

There can be as many clusters as necessary to make the simulation stable but I limit the number to three because there are three important cases to consider which makes a larger number of clusters unnecessary, and this optimization must worth the computational effort. One cluster if the shape is colliding with a plane, two if collinding with a wedge, and three with a corner. Remember that the only reason the normals are clustered is to reduce the number of contact points that are sent to the contact solver. So this is an optimization. Ideally you should make it an option using a macro/boolean. (I really need to add this to Bounce later.)

I also recommend associating a contact normal to a contact point, not to a manifold, which makes unnecessary project the penetration along the normal. So clearly the hull vs hull contact reduction is just a special case of cluster reduction.