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 designing truss structures, a common and complex category of buildings, using non-linear optimization. Truss structures are ubiquitous in the industrialized world, appearing as bridges, towers, roof supports and building exoskeletons, yet are complex enough that modeling them by hand is time consuming and tedious. We represent trusses as a set of rigid bars connected by pin joints, which may change location during optimization. By including the location of the joints as well as the strength of individual beams in our design variables, we can simultaneously optimize the geometry and the mass of structures. We present the details of our technique together with examples illustrating its use, including comparisons with real structures.

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.

Physical simulation of dynamic objects has become commonplace in computer graphics because it produces highly realistic animations. In this paradigm the animator provides few physical parameters such as the objects' initial positions and velocities, and the simulator automatically generates realistic motions. The resulting motion, however, is difficult to control because even a small adjustment of the input parameters can drastically affect the subsequent motion. Furthermore, the animator often wishes to change the end-result of the motion instead of the initial physical parameters.

We introduce a novel algorithm for transforming character anima-tion sequences that preserves essential physical properties of the motion. By using the spacetime constraints dynamics formulation our algorithm maintains realism of the original motion sequence without sacrificing full user control of the editing process. In contrast to most physically based animation techniques that synthesize motion from scratch, we take the approach of motion transformation as the underlying paradigm for generating computer animations. In doing so, we combine the expressive richness of an input animation sequence with the controllability of spacetime op-timization to create a wide range of realistic character animations. The spacetime dynamics formulation also allows editing of intu-itive, high-level motion concepts such as the time and placement of footprints, length and mass of various extremities, number of body joints and gravity. Our algorithm is well suited for the reuse of highly-detailed cap-tured motion animations. In addition, we describe a new methodol-ogy for mapping a motion between characters with drastically dif-ferent numbers of degrees of freedom. We use this method to re-duce the complexity of the spacetime optimization problems. Fur-thermore, our approach provides a paradigm for controlling com-plex dynamic and kinematic systems with simpler ones.

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.

Differential interference contrast (DIC) microscopy is a popular method for studying the three dimensional structure of living cells. Currently, no volume rendering tools exist which support visualisation of 3D DIC data. The authors develop a transformation method which removes the differential appearance of DIC imager, producing data which is suitable for volume rendering, and compare this method to an edge-enhancing approach based on a variance filter.

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.

We describe a simple technique for editing captured or keyframed animation based on warping of the motion parameter curves.The animator interactively defines a set of keyframe-like constraints which are used to derive a smooth deformation that preserves the fine structure of the original motion.Motion clips are combined by overlapping and blending of the parameter curves.We show that whole families of realistic motions can be derived from a single captured motion sequence using only a few keyframes to specify the motion warp.Our technique makes it feasible to create libraries of reusable "clip motion."

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.>

We present an approach to modeling with truly mutable yet completely controllable free-form surfaces of arbitrary topology. Surfaces may be pinned down at points and along curves, cut up and smoothly welded back together, and faired and reshaped in the large. This style of control is formulated as a constrained shape optimization, with minimization of squared principal curvatures yielding graceful shapes that are free of the parameterization worries accompanying many patch-based approaches. Triangulated point sets are used to approximate these smooth variational surfaces, bridging the gap between patch-based and particle-based representations. Automatic refinement, mesh smoothing, and re-triangulation maintain a good computational mesh as the surface shape evolves, and give sample points and surface features much of the freedom to slide around in the surface that oriented particles enjoy. The resulting surface triangulations are constructed and maintained in real time.

We present a new particle-based approach to sampling and controlling implicit surfaces.A simple constraint locks a set of particles onto a surface while the particles and the surface move.We use the constraint to make surfaces follow particles, and to make particles follow surfaces.We implement control points for direct manipulation by specifying particle motions, then solving for surface motion that maintains the constraint.For sampling and rendering, we run the constraint in the other direction, creating floater particles that roam freely over the surface.Local repulsion is used to make floaters spread evenly across the surface.By varying the radius of repulsion adaptively, and fissioning or killing particles based on the local density, we can achieve good sampling distributions very rapidly, and maintain them even in the face of rapid and extreme deformations and changes in surface topology.

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,

In this paper we introduce through-the-lens camera control, a body of techniques that permit a user to manipulate a virtual camera by controlling and constraining features in the image seen through its lens. Rather than solving for camera parameters directly, constrained optimization is used to compute their time derivatives based on desired changes in user-defined controls. This effectively permits new controls to be defined independent of the underlying parameterization. The controls can also serve as constraints, maintaining their values as others are changed. We describe the techniques in general and work through a detailed example of a specific camera model. Our implementation demonstrates a gallery of useful controls and constraints and provides some examples of how these may be used in composing images and animations. Keywords: camera control, constrained optimization, interaction techniques 1 Introduction Camera placement and control play an important role in image compositi...

We present a new approach to interactive modeling of freeform surfaces.Instead of a fixed mesh of control points, the model presented to the user is that of an infinitely malleable surface, with no fixed controls.The user is free to apply control points and curves which are then available as handles for direct manipulation.The complexity of the surface's shape may be increased by adding more control points and curves, without apparent limit.Within the constraints imposed by the controls, the shape of the surface is fully determined by one or more simple criteria, such as smoothness.Our method for solving the resulting constrained variational optimization problems rests on a surface representation scheme allowing nonuniform subdivision of B-spline surfaces.Automatic subdivision is used to ensure that constraints are met, and to enforce error bounds.Efficient numerical solutions are obtained by exploiting linearities in the problem formulation and the representation.

A novel solution to the 2-D tracking problem is presented. This solution has two major components: a deformation model that constrains the interpretation of motion, and a set of energy-based match criteria that specify image features to be used in tracking. The separation of the motion model from the match features is an advantage of this approach over previous tracking systems. An implementation of these ideas has been shown to exhibit fast and flexible operation over a wide class of image motions. Experimental results are given for two real-world image sequences.>

We present a method for texture synthesisbased on the simulation of a process of local nonlinear interaction, called reaction-diffusion, which has been proposed as a model of biological pattern formation. We extend traditional reaction-diffusion systems by allowing anisotropic and spatially non-uniform diffusion, as well as multiple competing directions of diffusion. We adapt reaction-diffusion systems to the needs of computer graphics by presenting a method to synthesize patterns which compensate for the effects of non-uniform surface parameterization. Finally, we develop efficient algorithms for simulating reactiondiffusion systems and display a collection of resulting textures using standard texture- and displacement-mapping techniques. 1 Introduction Texture mapping techniques have become so highly developed and so widely used that textureless images tend to appear barren, unrealistic, and boring. To date, though, techniques for synthesizing natural textures have advanced far les...

Our goal is to use physical simulation as an interactive medium for building and manipulating a wide range of models. A key to achieving this goal is the ability to create complex physical models dynamically by snapping simple pieces together, integrating the process of model creation into the ongoing simulation. We present a mathematical and computational formulation for constrained dynamics that makes this possible, allowing encapsulated objects, constraints, and forces to be combined dynamically and simulated efficiently. The formulation handles arbitrary objects, including nonrigid bodies. We describe an implementation for interactive dynamics, and discuss applications to mechanism construction, geometric modeling, interactive optimization data fitting, and animation.

We describe a fast method for creating physically based animation of non-rigid objects. Rapid simulation of non- rigid behavior is based on global deformations. Con- straints are used to connect non-rigid pieces to each other, forming complex models. Constraints also provide mo- tion control, allowing model points to be moved accurately along specified trajectories. The use of deformations that are linear in the state of the system causes the constraint matrices to be constant. Pre-inverting these matrices there- fore yields an enormous benefit in performance, allowing reasonably complex models to be manipulated at interac- tive speed.

Spacetime constraints are a new method for creating character animation. The animator specifies what the character has to do, for instance, "jump from here to there, clearing a hurdle in between;" how the motion should be performed, for instance "don't waste energy," or "come down hard enough to splatter whatever you land on;" the character's physical structure---the geometry, mass, connectivity, etc. of the parts; and the physical resources' available to the character to accomplish the motion, for instance the character's muscles, a floor to push off from, etc. The requirements contained in this description, together with Newton's laws, comprise a problem of constrained optimization. The solution to this problem is a physically valid motion satisfying the "what" constraints and optimizing the "how" criteria. We present as examples a Luxo lamp performing a variety of coordinated motions. These realistic motions conform to such principles of traditional animation as anticipation, squash-and-stretch, follow-through, and timing.

A simple but general approach to imposing and solving geometric constraints on parameterized models is introduced, applicable to animation as well as model construction. Constraints are expressed as energy functions, and the energy gradient followed through the model's parameter space. Intuitively, energy constraints behave like forces that pull and parametrically deform the parts of the model into place. A wide variety of geometric constraints are amenable to this formulation, and may be used to influence arbitrary model parameters. A catalogue of basic constraints is presented, and results are shown. Keywords --- Constraints, Modeling, Animation 1 Introduction A widely-used approach to modeling is to combine geometric primitives---such as cylinders, blocks, and bicubic patches---with a variety of operators---such as translations, rotations, booleans, and deformations--- to form a model hierarchy. The task of constructing a model within this framework has two parts: building the hie...

Scale-space filtering constructs hierarchic symbolic signal descriptions by transforming the signal into a continuum of versions of the original signal convolved with a kernal containing a scale or bandwidth parameter. It is shown that the Gaussian probability density function is the only kernel in a broad class for which first-order maxima and minima, respectively, increase and decrease when the bandwidth of the filter is increased. The consequences of this result are explored when the signal¿or its image by a linear differential operator¿is analyzed in terms of zero-crossing contours of the transform in scale-space.

The extrema in a signal and its first few derivatives provide a useful general purpose qualitative description for many kinds of signals. A fundamental problem in computing such descriptions is scale: a derivative must be taken over some neighborhood, but there is seldom a principled basis for choosing its size. Scale-space filtering is a method that describes signals qualitatively, managing the ambiguity of scale in an organized and natural way. The signal is first expanded by convolution with gaussian masks over a continuum of sizes. This "scale-space" image is then collapsed, using its qualitative structure, into a tree providing a concise but complete qualitative description covering all scales of observation. The description is further refined by applying a stability criterion, to identify events that persist of large changes in scale.