SCA 14: Eurographics/SIGGRAPH Symposium on Computer Animation

Permanent URI for this collection

https://diglib.eg.org/handle/10.2312/7760

Browse

Now showing 1 - 20 of 20

Adaptive Tetrahedral Meshes for Brittle Fracture Simulation
(The Eurographics Association, 2014) Koschier, Dan; Lipponer, Sebastian; Bender, Jan; Vladlen Koltun and Eftychios Sifakis
We present a method for the adaptive simulation of brittle fracture of solid objects based on a novel reversible tetrahedral mesh refinement scheme. The refinement scheme preserves the quality of the input mesh to a large extent, it is solely based on topological operations, and does not alter the boundary, i.e. any geometric feature. Our fracture algorithm successively performs a stress analysis and increases the resolution of the input mesh in regions of high tensile stress. This results in an accurate location of crack origins without the need of a general high resolution mesh which would cause high computational costs throughout the whole simulation. A crack is initiated when the maximum tensile stress exceeds the material strength. The introduced algorithm then proceeds by iteratively recomputing the changed stress state and creating further cracks. Our approach can generate multiple cracks from a single impact, but effectively avoids shattering artifacts. Once the tensile stress decreases, the mesh refinement is reversed to increase the performance of the simulation. We demonstrate that our adaptive method is robust, scalable and computes highly realistic fracture results.
An Adaptive Virtual Node Algorithm with Robust Mesh Cutting
(The Eurographics Association, 2014) Wang, Yuting; Jiang, Chenfanfu; Schroeder, Craig; Teran, Joseph; Vladlen Koltun and Eftychios Sifakis
We present a novel virtual node algorithm (VNA) for changing tetrahedron mesh topology to represent arbitrary cutting triangulated surfaces. Our approach addresses a number of shortcomings in the original VNA of [MBF04]. First, we generalize the VNA so that cuts can pass through tetrahedron mesh vertices and lie on mesh edges and faces. The original algorithm did not make sense for these cases and required often ambiguous perturbation of the cutting surface to avoid them. Second, we develop an adaptive approach to the definition of embedded material used for element duplication. The original algorithm could only handle a limited number of configurations which restricted cut surfaces to have curvature at the scale of the tetrahedron elements. Our adaptive approach allows for cut surfaces with curvatures independent of the embedding tetrahedron mesh resolution. Finally, we present a novel, provably-robust floating point mesh intersection routine that accurately registers triangulated surface cuts against the background tetrahedron mesh without the need for exact arithmetic.
Camera Motion Graphs
(The Eurographics Association, 2014) Sanokho, Cunka Bassirou; Desoche, Clement; Merabti, Billal; Li, Tsai-yen; Christie, Marc; Vladlen Koltun and Eftychios Sifakis
This paper presents Camera Motion Graphs, a technique to easily and efficiently generate cinematographic sequences in real-time dynamic 3D environments. A camera motion graph consists of (i) pieces of original camera trajectories attached to one or multiple targets, (ii) generated continuous transitions between camera trajectories and (iii) transitions representing cuts between camera trajectories. Pieces of original camera trajectories are built by extracting camera motions from real movies using vision-based techniques, or relying on motion capture techniques using a virtual camera system. A transformation is proposed to recompute all the camera trajectories in a normalized representation, making camera paths easily adaptable to new 3D environments through a specific retargeting technique. The camera motion graph is then constructed by sampling all pairs of camera trajectories and evaluating the possibility and quality of continuous or cut transitions. Results illustrate the simplicity of the technique, its adaptability to different 3D environments and its efficiency.
ChaCra: An Interactive Design System for Rapid Character Crafting
(The Eurographics Association, 2014) Megaro, Vittorio; Thomaszewski, Bernhard; Gauge, Damien; Grinspun, Eitan; Coros, Stelian; Gross, Markus; Vladlen Koltun and Eftychios Sifakis
We propose an interactive design system for rapid crafting of planar mechanical characters. Our method combines the simplicity of sketch-based modeling with the ease of defining motion through extreme poses. In order to translate digital designs into fabrication-ready descriptions, our method automatically computes the mechanical structure that makes the characters move as desired. We achieve real-time performance by limiting the mechanical structure between pairs of components to simple building blocks that define, trim, and propagate their motion. By focusing on shape and motion, our system emphasizes the creative aspects of character design while hiding away the intricacies of the underlying mechanical structure. We demonstrate the flexibility of our approach on a set of virtual designs and physical prototypes.
Coupling 3D Eulerian, Heightfield and Particle Methods for Interactive Simulation of Large Scale Liquid Phenomena
(The Eurographics Association, 2014) Chentanez, Nuttapong; Müller, Matthias; Kim, Tae-Yong; Vladlen Koltun and Eftychios Sifakis
We propose a new method to simulate large scale water phenomena by combining particle, 3D grid and height field methods. In contrast to most hybrid approaches that use particles to simulate foam and spray only, we also represent the bulk of water near the surface with both particles and a grid depending on the regions of interest and switch between those two representations during the course of the simulation. For the coupling we leverage the recent idea of tracking the water surface with a density field in grid based methods. Combining particles and a grid simulation then amounts to adding the density field of the particles and the one stored on the grid. For open scenes, we simulate the water outside of the 3D grid domain by solving the Shallow Water Equations on a height field. We propose new methods to couple these two domains such that waves travel naturally across the border. We demonstrate the effectiveness of our approach in various scenarios including a whale breaching simulation, all running in real-time or at interactive rates.
DenseSense: Interactive Crowd Simulation using Density-Dependent Filters
(The Eurographics Association, 2014) Best, Andrew; Narang, Sahil; Curtis, Sean; Manocha, Dinesh; Vladlen Koltun and Eftychios Sifakis
We present a novel algorithm to model density-dependent behaviors in crowd simulation. Our approach aims to generate pedestrian trajectories that correspond to the speed/density relationships that are typically expressed using the Fundamental Diagram. The algorithm's formulation can be easily combined with well-known multi-agent simulation techniques that use social forces or reciprocal velocity obstacles for local navigation. Our approach results in better utilization of free space by the pedestrians and has a small computational overhead. We are able to generate human-like dense crowd behaviors in large indoor and outdoor environments; we validate our results by comparing them with captured crowd trajectories.
Efficient Denting and Bending of Rigid Bodies
(The Eurographics Association, 2014) Patkar, Saket; Aanjaneya, Mridul; Bartle, Aric; Lee, Minjae; Fedkiw, Ronald; Vladlen Koltun and Eftychios Sifakis
We present a novel method for the efficient denting and bending of rigid bodies without the need for expensive finite element simulations. Denting is achieved by deforming the triangulated surface of the target body based on a dent map computed on-the-fly from the projectile body using a Z-buffer algorithm with varying degrees of smoothing. Our method accounts for the angle of impact, is applicable to arbitrary shapes, readily scales to thousands of rigid bodies, is amenable to artist control, and also works well in combination with prescoring algorithms for fracture. Bending is addressed by augmenting a rigid body with an articulated skeleton which is used to drive skinning weights for the bending deformation. The articulated skeleton is simulated to include the effects of both elasticity and plasticity. Furthermore, we allow joints to be added dynamically so that bending can occur in a nonpredetermined way and/or as dictated by the artist. Conversely, we present an articulation condensation method that greatly simplifies large unneeded branches and chains on-the-fly for increased efficiency.
Efficient Unsupervised Temporal Segmentation of Human Motion
(The Eurographics Association, 2014) Vögele, Anna; Krüger, Björn; Klein, Reinhard; Vladlen Koltun and Eftychios Sifakis
This work introduces an efficient method for fully automatic temporal segmentation of human motion sequences and similar time series. The method relies on a neighborhood graph to partition a given data sequence into distinct activities and motion primitives according to self-similar structures given in that input sequence. In particular, the fast detection of repetitions within the discovered activity segments is a crucial problem of any motion processing pipeline directed at motion analysis and synthesis. The same similarity information in the neighborhood graph is further exploited to cluster these primitives into larger entities of semantic significance. The elements subject to this classification are then used as prior for estimating the same target values for entirely unknown streams of data. The technique makes no assumptions about the motion sequences at hand and no user interaction is required for the segmentation or clustering. Tests of our techniques are conducted on the CMU and HDM05 motion capture databases demonstrating the capability of our system handling motion segmentation, clustering, motion synthesis and transfer-of-label problems in practice - the latter being an optional step which relies on the preexistence of a small set of labeled data.
Fast Grid-Based Nonlinear Elasticity for 2D Deformations
(The Eurographics Association, 2014) Setaluri, Rajsekhar; Wang, Yu; Mitchell, Nathan; Kavan, Ladislav; Sifakis, Eftychios; Vladlen Koltun and Eftychios Sifakis
We present a deformation technique that constructs 2D warps by using spline curves to specify the starting and target shapes of selected key contours. We generate a two-dimensional deformation map from these contours by simulating a non-linear elastic membrane deforming in accordance with user-specified constraints. Although we support and demonstrate elastic models inspired by physical membranes, we highlight a custom material model for this specific application, which combines the benefits of harmonic interpolation and area-preserving deformations. Our warps are represented via a standard Cartesian lattice and leverage the regularity of this description to enable efficient computation. Specifically, our method resolves the targeting constraints imposed along arbitrarily shaped contours with sub-grid cell precision, without requiring an explicit remeshing of the warp lattice around the constraint curve. We describe how to obtain a well-conditioned discretization of our membrane model even under elaborate constraints and strict area preservation demands, and present a multigrid solver for the efficient numerical solution of the deformation problem.
Holonomic Collision Avoidance for Virtual Crowds
(The Eurographics Association, 2014) Hughes, Rowan; Ondrej, Jan; Dingliana, John; Vladlen Koltun and Eftychios Sifakis
All approaches to simulating human collision avoidance for virtual crowds make simplifications to the underlying behaviour. One of the prevalent simplifications is to ignore it's holonomic aspect (i.e. sidestepping, walking backwards). This does not, however, capture the full range of how humans avoid collisions. In real world scenarios we can often observe people sidestepping around each other and obstacles in their environment. In this paper we present a new holonomic collision avoidance algorithm for real-time crowd simulation. Our model is elaborated from experimental data, which allowed us to both observe the conditions under which holonomic interactions occur, as well as the strategies walkers use during such interactions to avoid collision. Our model is general enough to be used with other collision avoidance techniques. We validate our approach by reproducing situations from our experiments and we demonstrate several examples in which our method provides more plausible collision avoidance behaviour.
Interactive Design of Modular Tensegrity Characters
(The Eurographics Association, 2014) Gauge, Damien; Coros, Stelian; Mani, Sandro; Thomaszewski, Bernhard; Vladlen Koltun and Eftychios Sifakis
We present a computational design tool for creating physical characters using tensegrities - networks of rigid and elastic elements that are in static equilibrium. Whereas the task of designing general tensegrities is very difficult to automate, we show that a modular design paradigm allows users of our system to intuitively build intricate structures that approximate the shape of complex characters. The underlying concept exploited by our method is that simple tensegrities can be used as building blocks to create increasingly complex figures. To this end, we propose a dedicated optimization scheme in order to compute the lengths of elastic cables such that, when fabricated, the structure assumes the desired shape under gravity while remaining compliant and responsive to user interaction. We demonstrate the flexibility of our system by designing several types of tensegrity characters, one of which we also fabricate.
Ocean Waves Animation using Boundary Integral Equations and Explicit Mesh Tracking
(The Eurographics Association, 2014) Keeler, Todd; Bridson, Robert; Vladlen Koltun and Eftychios Sifakis
We tackle deep water simulation in a scalable way, solving 3D irrotational flow using only variables stored in a mesh of the surface of the water, in time proportional to the rendered mesh. The heart of our method is a novel boundary integral equation formulation that is amenable to explicit mesh tracking with unstructured triangle meshes. Our method complements FFT style waves as it is able to handle solid boundaries. It is less memory intensive than volumetric methods and inherently handles the near-infinite depth of the deep ocean. We demonstrate acceleration techniques using the FMM and GPU computing. The natural Lagrangian motion of our model gives inherent adaptivity to our simulation without the need for direct mesh operations.
Optimization Integrator for Large Time Steps
(The Eurographics Association, 2014) Gast, Theodore F.; Schroeder, Craig; Vladlen Koltun and Eftychios Sifakis
Practical time steps in today's state-of-the-art simulators typically rely on Newton's method to solve large systems of nonlinear equations. In practice, this works well for small time steps but is unreliable at large time steps at or near the frame rate, particularly for difficult or stiff simulations. We show that recasting backward Euler as a minimization problem allows Newton's method to be stabilized by standard optimization techniques with some novel improvements of our own. The resulting solver is capable of solving even the toughest simulations at the 24Hz frame rate and beyond. We show how simple collisions can be incorporated directly into the solver through constrained minimization without sacrificing efficiency. We also present novel penalty collision formulations for self collisions and collisions against scripted bodies designed for the unique demands of this solver.
A Peridynamic Perspective on Spring-Mass Fracture
(The Eurographics Association, 2014) Levine, Joshua A.; Bargteil, Adam W.; Corsi, Christopher; Tessendorf, Jerry; Geist, Robert; Vladlen Koltun and Eftychios Sifakis
The application of spring-mass systems to the animation of brittle fracture is revisited. The motivation arises from the recent popularity of peridynamics in the computational physics community. Peridynamic systems can be regarded as spring-mass systems with two specific properties. First, spring forces are based on a simple strain metric, thereby decoupling spring stiffness from spring length. Second, masses are connected using a distancebased criterion. The relatively large radius of influence typically leads to a few hundred springs for every mass point. Spring-mass systems with these properties are shown to be simple to implement, trivially parallelized, and well-suited to animating brittle fracture.
Position-based Elastic Rods
(The Eurographics Association, 2014) Umetani, Nobuyuki; Schmidt, Ryan; Stam, Jos; Vladlen Koltun and Eftychios Sifakis
We present a novel method to simulate complex bending and twisting of elastic rods. Elastic rods are commonly simulated using force based methods, such as the finite element method. These methods are accurate, but do not directly fit into the more efficient position-based dynamics framework, since the definition of material frames are not entirely based on positions. We introduce ghost points, which are additional points defined on edges, to naturally endow continuous material frames on discretized rods. We achieve robustness by a novel discretization of the Cosserat theory. The method supports coupling with a frame, a triangle, and a rigid body at the rod's end point. Our formulation is highly efficient, capable of simulating hundreds of strands in real-time.
Stable Orthotropic Materials
(The Eurographics Association, 2014) Li, Yijing; Barbic, Jernej; Vladlen Koltun and Eftychios Sifakis
Isotropic Finite Element Method (FEM) deformable object simulations are widely used in computer graphics. Several applications (wood, plants, muscles) require modeling the directional dependence of the material elastic properties in three orthogonal directions. We investigate orthotropic materials, a special class of anisotropic materials where the shear stresses are decoupled from normal stresses. Orthotropic materials generalize transversely isotropic materials, by exhibiting different stiffnesses in three orthogonal directions. Orthotropic materials are, however, parameterized by nine values that are difficult to tune in practice, as poorly adjusted settings easily lead to simulation instabilities. We present a user-friendly approach to setting these parameters that is guaranteed to be stable. Our approach is intuitive as it extends the familiar intuition known from isotropic materials. We demonstrate our technique by augmenting linear corotational FEM implementations with orthotropic materials.
SteerFit: Automated Parameter Fitting for Steering Algorithms
(The Eurographics Association, 2014) Berseth, Glen; Kapadia, Mubbasir; Haworth, Brandon; Faloutsos, Petros; Vladlen Koltun and Eftychios Sifakis
In the context of crowd simulation, there is a diverse set of algorithms that model steering. The performance of steering approaches, both in terms of quality of results and computational efficiency, depends on internal parameters that are manually tuned to satisfy application-specific requirements. This paper investigates the effect that these parameters have on an algorithm's performance. Using three representative steering algorithms and a set of established performance criteria, we perform a number of large scale optimization experiments that optimize an algorithm's parameters for a range of objectives. For example, our method automatically finds optimal parameters to minimize turbulence at bottlenecks, reduce building evacuation times, produce emergent patterns, and increase the computational efficiency of an algorithm. We also propose using the Pareto Optimal front as an efficient way of modelling optimal relationships between multiple objectives, and demonstrate its effectiveness by estimating optimal parameters for interactively defined combinations of the associated objectives. The proposed methodologies are general and can be applied to any steering algorithm using any set of performance criteria.
Steklov-Poincaré Skinning
(The Eurographics Association, 2014) Gao, Ming; Mitchell, Nathan; Sifakis, Eftychios; Vladlen Koltun and Eftychios Sifakis
We introduce a novel and efficient simulation technique for generating physics-based skinning animations of skeleton-driven characters with full support for collision handling. Although physics-based approaches may use a volumetric (e.g. tetrahedral) flesh model, operations such as rendering, collision processing and user manipulation directly involve only the surface of this mesh. Motivated by this fact we define an elastic model of the skin surface which, while directly using only the surface degrees of freedom, exhibits a mechanical response that captures the full volumetric flesh behavior. We achieve this unusual result by combining three fundamental contributions: First, we present a material model which offers a plausible approximation to corotational elasticity at significantly reduced cost, by computing local rotations via procedural skinning rather than deriving them from the mesh deformation; the result is a force model which is affine on vertex positions, with coefficients dependent on the skeletal pose (but not on the deformation). Second, we use this force model to derive a direct mapping between surface vertex positions and resulting equilibrium forces on the same boundary vertices, which is a discrete version of the Steklov-Poincaré operator of the volumetric elastic model. This mapping is conveniently shown to also be affine (with pose-dependent coefficients), but with a dense stiffness matrix which renders direct numerical solution impractical. However, as a third and final step we show how a modified Newton iteration and a skinninginspired preconditioner can solve the boundary problem with a competitive runtime cost. We assess the efficacy of our solution in simulations of high resolution human flesh models, with full external and self-collision processing.
Strain Based Dynamics
(The Eurographics Association, 2014) Müller, Matthias; Chentanez, Nuttapong; Kim, Tae-Yong; Macklin, Miles; Vladlen Koltun and Eftychios Sifakis
We propose a new set of constraints within the Position Based Dynamics (PBD) framework that allow the control of strain in directions that are independent of the edge directions of the simulation mesh. Instead of constraining distances between points, we constrain the entries of the Green - St Venant strain tensor. Varying the stiffness values corresponding to the individual strain coefficients lets us simulate anisotropic behavior. By working with Green's rotation-independent, non-linear strain tensor directly we do not have to perform a polar decomposition of the deformation gradient as in most strain limiting approaches. In addition, we propose a modification of the constraints corresponding to the diagonal entries of the strain tensor such that they can be solved in a single step and a modification of the constraints corresponding to the off-diagonal entries to decouple stretch from shear resistance. By formulating the constraints within the PBD framework, they can be used not only for strain limiting but to perform the actual simulation of the deformable object whereas traditional strain limiting methods have to be paired with a separate simulation method.
View-Dependent Adaptive Cloth Simulation
(The Eurographics Association, 2014) Koh, Woojong; Narain, Rahul; O'Brien, James F.; Vladlen Koltun and Eftychios Sifakis
This paper describes a method for view-dependent cloth simulation using dynamically adaptive mesh refinement and coarsening. Given a prescribed camera motion, the method adjusts the criteria controlling refinement to account for visibility and apparent size in the camera's view. Objectionable dynamic artifacts are avoided by anticipative refinement and smoothed coarsening. This approach preserves the appearance of detailed cloth throughout the animation while avoiding the wasted effort of simulating details that would not be discernible to the viewer. The computational savings realized by this method increase as scene complexity grows, producing a 2x speed-up for a single character and more than 4x for a small group.

Browse

Browsing SCA 14: Eurographics/SIGGRAPH Symposium on Computer Animation by Title

Results Per Page

Sort Options