Deficient cloth-to-cloth collision response is the most serious shortcoming of most cloth simulation systems. Past approaches to cloth-cloth collision have used history to decide whether nearby cloth regions have interpenetrated. The biggest pitfall of history-based methods is that an error anywhere along the way can give rise to persistent tangles. This is a particularly serious issue for production character animation, because characters' bodies routinely self-intersect, for instance in the bend of an elbow or knee, or where the arm or hand rests against the body. Cloth that becomes pinched in these regions is often forced into jagged self-intersections that defeat history-based methods, leaving a tangled mess when the body parts separate. This paper describes a history-free cloth collision response algorithm based on global intersection analysis of cloth meshes at each simulation step. The algorithm resolves tangles that arise during pinching as soon as the surrounding geometry permits, and also resolves tangled initial conditions. The ability to untangle cloth after pinching is not sufficient, because standard cloth-solid collision algorithms handle pinches so poorly that they often give rise to visible flutters and other simulation artifacts during the pinch. As a companion to the global intersection analysis method, we present a cloth-solid collision algorithm called collision flypapering, that eliminates these artifacts. The two algorithms presented have been used together extensively and successfully in a production animation environment.

We present a method for the rapid and controllable simulation of the shattering of brittle objects under impact.An object to be broken is represented as a set of point masses connected by distance-preserving linear constraints.This use of constraints, rather than stiff springs, gains us a significant advantage in speed while still retaining fine control over the fracturing behavior.The forces exerted by these constraints during impact are computed using Lagrange multipliers.These constraint forces are then used to determine when and where the object will break, and to calculate the velocities of the newly created fragments.We present the details of our technique together with examples illustrating its use.

Describes how a physical simulation can be integrated with our Responsive Workbench system to support complex assembly tasks involving multiple hands and users. Our system uses the CORIOLIS physical simulation package extended to meet the real-time requirements for our highly interactive virtual environment. We develop a new set of interface tools that exploit the natural properties of physical simulation (i.e. the superposition of forces). Our tools are based on sets of springs connecting the user's hand to a virtual object. Visualizing these springs provides "visual force feedback" of the applied forces and facilitates the prediction of the objects' behavior. Our force-based interaction concept allows multiple hands and users to manipulate a single object without the need for locking the object.

A high performance six degree-of-freedom magnetic levitation haptic interface device has been integrated with a physically-based dynamic rigid-body simulation to enable realistic user interaction in real time with a 3-D dynamic virtual environment. The user grasps the levitated handle of the device to manipulate a virtual tool in the simulated environment and feels its force and motion response as it contacts and interacts with other objects in the simulation. The physical simulation and the magnetic levitation controller execute independently on separate processors. The position and orientation of the virtual tool in the simulation and the levitated handle of the maglev device are exchanged at each update of the simulation. The position and orientation data from each system act as impedance control setpoints for the other, with position error and velocity feedback on each system acting as virtual coupling between the two systems. The setpoints from the simulation are interpolated by the controller at the faster device control rate so that the user feels smooth sliding contacts without chattering due to the slower updates of the simulation. The simple feedback coupling between the two systems enables the overall stiffness and stability of the combined system to be tuned easily and provides realistic haptic user interaction. Sample task simulation environments have been programmed to demonstrate the effectiveness of the haptic interaction system.

The bottle-neck in most cloth simulation systems is that time steps must be small to avoid numerical instability.This paper describes a cloth simulation system that can stably take large time steps.The simulation system couples a new technique for enforcing constraints on individual cloth particles with an implicit integration method.The simulator models cloth as a triangular mesh, with internal cloth forces derived using a simple continuum formulation that supports modeling operations such as local anisotropic stretch or compression; a unified treatment of damping forces is included as well.The implicit integration method generates a large, unbanded sparse linear system at each time step which is solved using a modified conjugate gradient method that simultaneously enforces particles' constraints.The constraints are always maintained exactly, independent of the number of conjugate gradient iterations, which is typically small.The resulting simulation system is significantly faster than previous accounts of cloth simulation systems in the literature.

Current linear-time simulation methods for articulated figures are based exclusively on reduced-coordinate formulations.This paper describes a general, non-iterative linear-time simulation method based instead on Lagrange multipliers.Lagrange multiplier methods are important for computer graphics applications because they bypass the difficult (and often intractable) problem of parameterizing a system's degrees of freedom.Given a loop-free set of n equality constraints acting between pairs of bodies, the method takes O(n) time to compute the system's dynamics.The method does not rely on matrix bandwidth, so no assumptions about the constraints' topology are needed.Bodies need not be rigid, constraints can be of various dimensions, and unlike reduced-coordinate approaches, nonholonomic (e.g.velocity-dependent) constraints are allowed.An additional set of k one-dimensional constraints which induce loops and/or handle inequalities can be accommodated with cost O(kn).This makes it practical to simulate complicated, closedloop articulated figures with joint-limits and contact at interactive rates.A complete description of a sample implementation is provided in pseudocode.

In this paper, we include Coulomb friction at contacts between bodies and give a characterization of the entire set of stable orientations of an assembly under uniform gravity. Our characterization is based on the concept of potential stability, which describes a necessary but not sufficient condition for the stability of an assembly. Orientations that are computed as being unstable, however, are guaranteed to fall apart. Our characterization reveals that the set of stable orientations maps out a convex region on the unit-sphere of directions and corresponds to a spherical analog of a planar polygon-the region is bounded by a sequence of vertices joined by great arcs. Linear programming techniques are used to automatically find this set of vertices, yielding a description of the range of stable orientations for any assembly. For frictionless assemblies, our characterization of stable orientations is exact. For assemblies with friction, some conservative approximations associated with the use of a linearized Coulomb law are made.

Physically-based modeling has been used in the past to support a variety of interactive modeling tasks including free-form surface design, mechanism design, constrained drawing, and interactive camera control.In these systems, the user interacts with the model by exerting virtual forces, to which the system responds subject to the active constraints.In the past, this kind of interaction has been applicable only to models that are governed by continuous parameters.In this paper we present an extension to mixed continuous/discrete models, emphasizing constrained layout problems that arise in architecture and other domains.When the object being dragged is blocked from further motion by geometric constraints, a local discrete search is triggered, during which transformations such as swapping of adjacent objects may be performed.The result of the search is a "nearby" state in which the target object has been moved in the indicated direction and in which all constraints are satisfied.The transition to this state is portrayed using simple but effective animated visual effects.Following the transition, continuous dragging is resumed.The resulting seamless transitions between discrete and continuous manipulation allow the user to easily explore the mixed design space just by dragging objects.We demonstrate the method in application to architectural floor plan design, circuit board layout, art analysis, and page layout.

The stability of an assemblage of contacting rigid bodies without friction is investigated. A method is presented for finding an orientation of the assembly so that the assembly remains motionless under gravity. If no stable orientation exists for an assembly, the method finds the "least" unstable orientation. The metric used to measure stability is based on the second time-rate of change of the gravitational potential energy, and the desired orientation for an assembly is expressed in terms of an optimization problem involving changes in potential energy. The problem of finding stable or maximally-stable orientations is formulated as a constrained maximin problem. The maximin problem is shown to be a variant of standard zero-sum matrix games, and can be solved using linear programming. The method is the first general method for automatically determining stable orientations. Example assemblies are presented.>

A model for the dynamic simulation of flexible bodies subject to nonpenetration constraints is presented. Flexible bodies are described in terms of global deformations of a rest shape. The dynamical behavior of these bodies that most closely matches the behavior of ideal continuum bodies is derived, and subsumes the results of earlier Lagrangian dynamics-based models. The dynamics derived for the flexible-body model allows the unification of previous work on flexible body simulation and previous work on nonpenetrating rigid body simulation. The nonpenetration constraints for a system of bodies that contact at multiple points are maintained by analytically calculated contact forces. Frictional effects are also included. An implementation for first- and second-order polynomially deformable bodies is described. The simulation of second-order or higher deformations currently involves a polyhedral boundary approximation for collision detection purposes.>

Previous work by Mattikalli et al. (1993) considered the stability of assemblies of frictionless contacting bodies with uniform gravity. A linear programming-based technique was described that would automatically determine a single stable orientation for an assembly (if such an orientation existed). In this paper, we give an exact characterization of the entire set of stable orientations of any assembly under uniform gravity. Our characterization reveals that the set of stable orientations maps out a convex region on the unit-sphere of directions. The region is bounded by a sequence of vertices adjoined with great arcs. Linear programming techniques are used to automatically find this set of vertices, yielding a precise description of the range of stable orientations for any frictionless assembly.>

A new algorithm for computing contact forces between solid objects with friction is presented. The algorithm allows a mix of contact points with static and dynamic friction. In contrast to previous approaches, the problem of computing contact forces is not transformed into an optimization problem. Because of this, the need for sophisticated optimization software packages is eliminated. For both systems with and without friction, the algorithm has proven to be considerably faster, simple, and more reliable than previous approaches to the problem. In particular, implementation of the algorithm by nonspecialists in numerical programming is quite feasible.

High level assembly plans prescribe the sequence in which parts come together along with their motions. At each stage of assembly, the stability of subassemblies is an important concern. The authors address the problem of the gravitational stability of assemblies of frictionless rigid bodies. Solution methods to the problems of determining if an assembly is stable, and finding a stable orientation for a given for a given assembly are proposed. The solution methods for the two problems compute constrained motions of individual parts that decrease the gravitational potential energy, in order to determine the stability and search for stable orientations. Linear programming is used to obtain numerical solutions. The problem of finding a stable orientation is formulated as a maximin problem. The solution to this problem is the first general method for automatically determining stable orientations. The program to solve the two problems takes as input a geometric model of the assembly and information related to grounding constraints. Preliminary results are presented.

A model for the dynamic simulation of flexible bodies subject to non-penetration constraints is presented.Flexible bodies are described in terms of global deformations of a rest shape.The dynamical behavior of these bodies that most closely matches the behavior of ideal continuum bodies is derived, and subsumes the results of earl ier Lagrangian dynamics-based models.The dynamics derived for the flexible-body model allows the unification of previous work on flexible body simulation and previous work on non-penetrating rigid body simulation.The non-penetration constraints for a system of bodies that contact at multiple points are maintained by analytically calculated contact forces.An implementation for first-and second-order polynomially deformable bodies is described.The simulation of second-order or higher deformations currently involves a polyhedral boundary approximation for collision detection purposes,

Algorithms and computational complexity measures for simulating the motion of contacting bodies with friction are presented. The bodies are restricted to be perfectly rigid bodies that contact at finitely many points. Contact forces between bodies must satisfy the Coulomb model of friction. A traditional principle of mechanics is that contact forces are impulsive if and only if non-impulsive contact forces are insufficient to maintain the non-penetration constraints between bodies. When friction is allowed, it is known that impulsive contact forces can be necessary even in the absence of collisions between bodies. This paper shows that computing contact forces according to this traditional principle is likely to require exponential time. An analysis of this result reveals that the principle for when impulses can occur is too restrictive, and a natural reformulation of the principle is proposed. Using the reformulated principle, an algorithm with expected polynomial time behaviour for computing contact forces is presented.

A formulation for the contact forces between curved surfaces in resting (non-colliding) contact is presented. In contrast to previous formulations, constraints on the allowable tangential movement between contacting surfaces are not required. Surfaces are restricted to be twice-differentiable surfaces without boundary. Only finitely many contact points between surfaces are allowed; however, the surfaces need not be convex. The formulation yields the contact forces between curved surfaces and polyhedra as well. Algorithms for performing collision detection during simulation on bodies composed of both polyhedra and strictly convex curved surfaces are also presented. The collision detection algorithms exploit the geometric coherence between successive time steps of the simulation to achieve efficient running times.

A method for analytically calculating the forces between systems of rigid bodies in resting (non-colliding) contact is presented. The systems of bodies may either be in motion or static equilibrium and adjacent bodies may touch at multiple points. The analytic formulation of the forces between bodies in non-colliding contact can be modified to deal with colliding bodies. Accordingly, an improved method for analytically calculating the forces between systems of rigid bodies in colliding contact is also presented. Both methods can be applied to systems with arbitrary holonomic geometric constraints, such as linked figures. The analytical formulations used treat both holonomic and non-holonomic constraints in a consistent manner.