Nonconvex rigid bodies with stacking
Guendelman, E., Bridson, R., & Fedkiw, R. (2003). Nonconvex Rigid Bodies with Stacking. ACM Transactions On Graphics, 22(3). doi:10.1145/882262.882358
Summary
In this paper, Guendelman et al. propose a method for detecting and resolving collisions when dealing with nonconvex rigid bodies, particularly in scenarios when those bodies need to stack. There are three main pieces to their approach: the geometric representation, the time integration method, and a shock propagation method for propagation-based contact resolution.
First, the geometric representation that they use is the typical triangular mesh, plus a signed distance function, which gives the distance to the (closest) surface of the mesh along the normal vector. Distances inside the mesh are negative, and distances outside the mesh are positive. Such a distance function makes it easy to detect collisions because for a given vertex, you can check what the distance is relative to another object. If the distance is negative, then you know that the objects are interpenetrating.
Second, the time integration method that they use has four components:
- Detect and resolve collisions
- Update object velocities
- Detect and resolve contacts
- Update object positions
By performing the steps in this order, this method avoids issues with undesirable behavior when friction is high (and therefore objects shouldn’t move). They give the example of a block on an inclined plane:
Consider a block sitting still on an inclined plane with a large coefficient of restitution, say $\epsilon=1$, and suppose that friction is large enough that the block should sit still. In a standard time stepping scheme, both position and velocity are updated first, followed by collision and contact resolution. During the position and velocity update, the block starts to fall under the effects of gravity. Then in the collision processing stage we detect a low velocity collision between the block and the plane, and since $\epsilon=1$ the block will change direction and bounce upwards at an angle down the incline. Then in the contact resolution stage, the block and the plane are separating so nothing happens. The block will eventually fall back to the inclined plane, and continue bouncing up and down incorrectly sliding down the inclined plane because of the time it spends in the ballistic phase.
They use a propagation method for resolving collisions, in which they predict where the objects will be, temporarily move them there, and then check for collisions and process them. This might result in new collisions, so they repeat the process a number of times (5). The method for resolving contacts is similar, except that they additionally use a contact graph which reflects which objects are resting on which. They separate the graph into levels such that the objects in level $i$ are lower than the objects in level $i+1$, and then process the levels sequentially.
Finally, after several iterations of contact resolution, they use a method called shock propagation. In this method, they process the contacts at level $i$ and then temporarily fix the positions of those objects (zero the velocity and give them infinite mass). Then, when they process the contacts at level $i+1$, those objects cannot affect the objects at level $i$ and so therefore the contact resolution is propagated upward.