<H1>6 Collisions</H1>
        Much has been written about collision detection for cloth; we have nothing substantial to add to the subject of collision detection per se. Cloth/cloth collisions are detected by checking pairs ( p, t) and (e 1 , e 2 ) for intersections, where p and t are a cloth particle and a cloth triangle respectively, and e 1 and e 2 are edges of cloth triangles. Given a previous known legal state of the cloth, we postulate a linear motion for the cloth particles to the current (possibly illegal) state and check for either particle/triangle or edge/edge crossings. To avoid O(n 2 ) comparisons, we use a coherency-based boundingbox approach 
[ 1 ] to cull out the majority of pairs. When collisions between a cloth vertex and triangle, or two cloth edges are detected, we insert a strong damped spring force to push the cloth apart. A dissipative force tangent to the contact is also applied, countering any sliding motion. The force is not, strictly speaking, a frictional force: rather it is proportional to the slip velocity, so it is in actuality a damping force, although it reasonably emulates dynamic friction. Applying static friction forces to cloth contacts is far more difficult, and is a problem we have not solved yet. The forces, and their derivatives with respect to position and velocity, are of course included in equation (15). Our system detects collisions between cloth particles and solid objects by testing each individual cloth particle against the faces of each solid object. A solid object’s faces are grouped in a hierarchical bounding box tree, with the leaves of the tree being individual faces of the solid. The tree is created by a simple recursive splitting along coordinate axes. The maintenance of contacts and the application of friction forces was described in the previous section.
      
      
        <H2>6.1 Constraint Initiation</H2>
        Both cloth/cloth and cloth/solid collisions give rise to the same problem whenever two contacts form. For both types of collisions, our detection algorithm reports an intersection, and then takes action to remedy the situation: either by enforcing a constraint (cloth/solid collisions) or by adding a penalty force (cloth/cloth) collisions. However, since our simulator proceeds in discrete steps, collisions resulting in a reasonably substantial interpenetration depth can occur between one step and the next. Clearly, this situation needs to be remedied. For cloth/cloth collisions, this would not appear to be a problem: the spring forces that are added work to counter the colliding velocities and then push the cloth apart. For cloth/solid collisions, however, the situation is more complicated. If we simply enforce a constraint which causes the colliding cloth particle to have a velocity consistent with the solid object’s velocity, and continue to enforce that constraint, the cloth particle will continue to remain embedded somewhere below the solid object’s surface. This is unacceptable. One solution is to use Baumgarte stabilization [ 18 ]
, which schedules the particle’s acceleration so that the position and velocity error of the particle with respect to the surface decay asymptotically to zero. We experimented with this technique, but found it lacking. In particular, a fast rise to the surface was prone to noise and “jumpiness”; this could be eliminated, but at the cost of decreasing the step size. A slower rise to the surface caused visual artifacts. We tried a simpler solution: when intersections occurred, rather than wait for a scheduled constraint or a penalty force to eliminate the intersection, we simply altered the positions of the cloth particles, effecting an instantaneous (and discontinuous) change in position. While this would be problematic when using a multi-step differential equation solver which expects continuity (such as a RungeKutta method), it should not interfere with a one-step solver such as the backward Euler method. Unfortunately, simply changing particle positions produced disastrous results. The stretch energy term in a cloth system is extremely strong, and altering particle positions arbitrarily introduced excessively large deformation energies in an altered particle’s neighborhood. This resulted in visibly “jumpy” behavior of the cloth in localized regions.
        50
        SIGGRAPH 98, Orlando, July 19–24
        C OMPUTER G RAPHICS Proceedings, Annual Conference Series, 1998
      
      
        <H2>6.2 Position Alteration</H2>
        Despite its initial failure, the ability to make arbitrary small changes in a particle’s position continued to attract our attention. The entire process of implicit integration can be considered to be a filtering process 
[ 7 ], and we postulated that a mechanism for filtering energy changes caused by displacing particles might make position alteration a viable technique. We considered that perhaps some sort of extra implicit step could be used as a filter, but forming and solving an additional linear system at each step seemed too expensive. Happily, we can make use of the filtering effect of implicit integration without any extra work. Consider a particle that has collided with a solid object. The particle’s change in velocity at each step is under our control, using the constraint techniques described in section 5. Meanwhile, the particle’s position at the next step follows from equation (4): x i = h(v 0i + v i ) (recall that v 0i is the particle’s current velocity). The reason that changing positions after a step has been taken doesn’t work is because the particle’s neighbors receive no advance notification of the change in position: they are confronted with the alteration at the beginning of the next step. This presents an obvious solution: we simply modify the top row of equation (4) to
        
          17
          x i = h(v 0i + v i ) + y i
        
        where y i is an arbitrary correction term of our choice, introduced solely to move a particle to a desired location during the backward Euler step. Having modified the top row of equation (4), we must follow this change through: using equation (17) and repeating the derivation of section 3 and the symmetric transform from section 5 yields the modified symmetric system
        
          18
          M − h ∂v ∂f − h 2 ∂x ∂f v = h f 0 + h ∂x ∂f v 0 + ∂x ∂f y .
        
        This modification gives us complete control over both the position and velocity of a constrained particle in just one step, without any extra computational cost. We use this technique to bring particles quickly and stably to the surface of solid objects without creating visual artifacts or limiting the allowable step size. We can also add correction terms to particles involved in cloth/cloth collisions. Without a constraint on those particles’ velocities there is no guarantee that they will go exactly where we want in one step, but the ability to induce sizeable jumps in position without excessively stiff spring forces adds greatly to the stability of the simulation.
      
      
        