Improved Variational Guiding of Smoke Animations

Smoke animations are hard to art‐direct because simple changes in parameters such as simulation resolution often lead to unpredictable changes in the final result. Previous work has addressed this problem with a guiding approach which couples low‐resolution simulations – that exhibit the desired flow and behaviour – to the final, high‐resolution simulation. This is done in such a way that the desired low frequency features are to some extent preserved in the high‐resolution simulation. However, the steady (i.e. constant) guiding used often leads to a lack of sufficiently high detail, and employing time‐dependent guiding is expensive because the matrix of the resulting set of equations needs to be recomputed at every iteration. We propose an improved mathematical model for Eulerian‐based simulations which is better suited for dynamic, time‐dependent guiding of smoke animations through a novel variational coupling of the low‐ and high‐resolution simulations. Our model results in a matrix that does not require re‐computation when the guiding changes over time, and hence we can employ time‐dependent guiding more efficiently both in terms of storage and computational requirements. We demonstrate that time‐dependent guiding allows for more high frequency detail to develop without losing correspondence to the low resolution simulation. Furthermore, we explore various artistic effects made possible by time‐dependent guiding.     

EACS: Effective Avoidance Combination Strategy

When navigating in crowds, humans are able to move efficiently between people. They look ahead to know which path would reduce the complexity of their interactions with others. Current navigation systems for virtual agents consider long‐term planning to find a path in the static environment and short‐term reactions to avoid collisions with close obstacles. Recently some mid‐term considerations have been added to avoid high density areas. However, there is no mid‐term planning among static and dynamic obstacles that would enable the agent to look ahead and avoid difficult paths or find easy ones as humans do. In this paper, we present a system for such mid‐term planning. This system is added to the navigation process between pathfinding and local avoidance to improve the navigation of virtual agents. We show the capacities of such a system using several case studies. Finally we use an energy criterion to compare trajectories computed with and without the mid‐term planning.     

Reusable Visualizations and Animations for Surgery Planning

For surgical planning, the exploration of 3D visualizations and 2D slice views is essential. However, the generation of visualizations which support the specific treatment decisions is very tedious. Therefore, the reuse of once designed visualizations for similar cases can strongly accelerate the process of surgical planning. We present a new technique that enables the easy reuse of both medical visualization types: 3D scenes and 2D slice views. We introduce the keystates as a concept to describe the state of a visualization in a general manner. They can be easily applied to new datasets to create similar visualizations. Keystates can be shared between surgeons of one specialization to reproduce and document the planning process for collaborative work. Furthermore, animations can support the surgeon on individual exploration and are also useful in collaborative environments, where complex issues must be presented in a short time. Therefore, we provide a framework, where animations can be visually designed by surgeons during their exploration process without any programming or authoring skills. We discuss several transitions between different visualizations and present an application from clinical routine.     

Synthesis of Responsive Motion Using a Dynamic Model

Synthesizing the movements of a responsive virtual character in the event of unexpected perturbations has proven a difficult challenge. To solve this problem, we devise a fully automatic method that learns a nonlinear probabilistic model of dynamic responses from very few perturbed walking sequences. This model is able to synthesize responses and recovery motions under new perturbations different from those in the training examples. When perturbations occur, we propose a physics‐based method that initiates motion transitions to the most probable response example based on the dynamic states of the character. Our algorithm can be applied to any motion sequences without the need for preprocessing such as segmentation or alignment. The results show that three perturbed motion clips can sufficiently generate a variety of realistic responses, and 14 clips can create a responsive virtual character that reacts realistically to external forces in different directions applied on different body parts at different moments in time.     

Implicit Contact Handling for Deformable Objects

We present an algorithm for robust and efficient contact handling of deformable objects. By being aware of the internal dynamics of the colliding objects, our algorithm provides smooth rolling and sliding, stable stacking, robust impact handling, and seamless coupling of heterogeneous objects, all in a unified manner. We achieve dynamicsawareness through a constrained dynamics formulation with implicit complementarity constraints, and we present two major contributions that enable an efficient solution of the constrained dynamics problem: a time stepping algorithm that robustly ensures non-penetration and progressively refines the formulation of constrained dynamics, and a new solver for large mixed linear complementarity problems, based on iterative constraint anticipation. We show the application of our algorithm in challenging scenarios such as multi-layered cloth moving at high velocities, or colliding deformable solids simulated with large time steps.     

Robust and Efficient Wave Simulations on Deforming Meshes

The goal of this paper is to enable the interactive simulation of phenomena such as animated fluid characters. While full 3D fluid solvers achieve this with control algorithms, these 3D simulations are usually too costly for real‐time environments. In order to achieve our goal, we reduce the problem from a three‐ to a two‐dimensional one, and make use of the shallow water equations to simulate surface waves that can be solved very efficiently. In addition to a low runtime cost, stability is likewise crucial for interactive applications. Hence, we make use of an implicit time integration scheme to obtain a robust solver. To ensure a low energy dissipation, we apply an Implicit Newmark time integration scheme. We propose a general formulation of the underlying equations that is tailored towards the use with an Implicit Newmark integrator. Furthermore, we gain efficiency by making use of a direct solver. Due to the generality of our formulation, the fluid simulation can be coupled interactively with arbitrary external forces, such as forces caused by inertia or collisions. We will discuss the properties of our algorithm, and demonstrate its robustness with simulations on strongly deforming meshes.     

Crowds by Example

We present an example-based crowd simulation technique. Most crowd simulation techniques assume that the behavior exhibited by each person in the crowd can be defined by a restricted set of rules. This assumption limits the behavioral complexity of the simulated agents. By learning from real-world examples, our autonomous agents display complex natural behaviors that are often missing in crowd simulations. Examples are created from tracked video segments of real pedestrian crowds. During a simulation, autonomous agents search for examples that closely match the situation that they are facing. Trajectories taken by real people in similar situations, are copied to the simulated agents, resulting in seemingly natural behaviors.     

Deformable Motion: Squeezing into Cluttered Environments

We present an interactive method that allows animated characters to navigate through cluttered environments. Our characters are equipped with a variety of motion skills to clear obstacles, narrow passages, and highly constrained environment features. Our control method incorporates a behavior model into well‐known, standard path planning algorithms. Our behavior model, called deformable motion, consists of a graph of motion capture fragments. The key idea of our approach is to add flexibility on motion fragments such that we can situate them into a cluttered environment via constraint‐based formulation. We demonstrate our deformable motion for realtime interactive navigation and global path planning in highly constrained virtual environments.     

Smart Motion Synthesis

Creating long motion sequences is a time‐consuming task even when motion capture equipment or motion editing tools are used. In this paper, we propose a system for creating a long motion sequence by combining elementary motion clips. The user is asked to first input motions on a timeline. The system then automatically generates a continuous and natural motion. Our system employs four motion synthesis methods: motion transition, motion connection, motion adaptation, and motion composition. Based on the constraints between the feet of the animated character and the ground, and the timing of the input motions, the appropriate method is determined for each pair of overlapped or sequential motions. As the user changes the arrangement of the motion clips, the system interactively changes the output motion. Alternatively, the user can make the system execute an input motion as soon as possible so that it follows the previous motion smoothly. Using our system, users can make use of existing motion clips. Because the entire process is automatic, even novices can easily use our system. A prototype system demonstrates the effectiveness of our approach.     

An Efficient Hybrid Incompressible SPH Solver with Interface Handling for Boundary Conditions

We propose a hybrid smoothed particle hydrodynamics solver for efficientlysimulating incompressible fluids using an interface handling method for boundary conditions in the pressure Poisson equation. We blend particle density computed with one smooth and one spiky kernel to improve the robustness against both fluid–fluid and fluid–solid collisions. To further improve the robustness and efficiency, we present a new interface handling method consisting of two components: free surface handling for Dirichlet boundary conditions and solid boundary handling for Neumann boundary conditions. Our free surface handling appropriately determines particles for Dirichlet boundary conditions using Jacobi‐based pressure prediction while our solid boundary handling introduces a new term to ensure the solvability of the linear system. We demonstrate that our method outperforms the state‐of‐the‐art particle‐based fluid solvers.     

A Fast Simulation Method Using Overlapping Grids for Interactions between Smoke and Rigid Objects

Recently, many techniques using computational fluid dynamics have been proposed for the simulation of natural phenomena such as smoke and fire. Traditionally, a single grid is used for computing the motion of fluids. When an object interacts with a fluid, the resolution of the grid must be sufficiently high because the shape of the object is represented by a shape sampled at the grid points. This increases the number of grid points that are required, and hence the computational cost is increased. To address this problem, we propose a method using multiple grids that overlap with each other. In addition to a large single grid (a global grid) that covers the whole of the simulation space, separate grids (local grids) are generated that surround each object. The resolution of a local grid is higher than that of the global grid. The local grids move according to the motion of the objects. Therefore, the process of resampling the shape of the object is unnecessary when the object moves. To accelerate the computation, appropriate resolutions are adaptively‐determined for the local grids according to their distance from the viewpoint. Furthermore, since we use regular (orthogonal) lattices for the grids, the method is suitable for GPU implementation. This realizes the real‐time simulation of interactions between objects and smoke.     

GPU-based Fast Ray Casting for a Large Number of Metaballs

Metaballs are implicit surfaces widely used to model curved objects, represented by the isosurface of a density field defined by a set of points. Recently, the results of particle‐based simulations have been often visualized using a large number of metaballs, however, such visualizations have high rendering costs. In this paper we propose a fast technique for rendering metaballs on the GPU. Instead of using polygonization, the isosurface is directly evaluated in a per‐pixel manner. For such evaluation, all metaballs contributing to the isosurface need to be extracted along each viewing ray, on the limited memory of GPUs. We handle this by keeping a list of metaballs contributing to the isosurface and efficiently update it. Our method neither requires expensive precomputation nor acceleration data structures often used in existing ray tracing techniques. With several optimizations, we can display a large number of moving metaballs quickly.     

Textured Liquids based on the Marker Level Set

In this work we propose a new Eulerian method for handling the dynamics of a liquid and its surface attributes (for example its color). Our approach is based on a new method for interface advection that we term the Marker Level Set (MLS). The MLS method uses surface markers and a level set for tracking the surface of the liquid, yielding more efficient and accurate results than popular methods like the Particle Level Set method (PLS). Another novelty is that the surface markers allow the MLS to handle non-diffusively surface texture advection, a rare capability in the realm of Eulerian simulation of liquids. We present several simulations of the dynamical evolution of liquids and their surface textures.     

Simulation of Human Motion Data using Short-Horizon Model-Predictive Control

Many data‐driven animation techniques are capable of producing high quality motions of human characters. Few techniques, however, are capable of generating motions that are consistent with physically simulated environments. Physically simulated characters, in contrast, are automatically consistent with the environment, but their motions are often unnatural because they are difficult to control. We present a model‐predictive controller that yields natural motions by guiding simulated humans toward real motion data. During simulation, the predictive component of the controller solves a quadratic program to compute the forces for a short window of time into the future. These forces are then applied by a low‐gain proportional‐derivative component, which makes minor adjustments until the next planning cycle. The controller is fast enough for interactive systems such as games and training simulations. It requires no precomputation and little manual tuning. The controller is resilient to mismatches between the character dynamics and the input motion, which allows it to track motion capture data even where the real dynamics are not known precisely. The same principled formulation can generate natural walks, runs, and jumps in a number of different physically simulated surroundings.     

Alleviating the Modifiable Areal Unit Problem within Probe‐Based Geospatial Analyses

We present a probe‐based interface for the exploration of the results of a geospatial simulation of urban growth. Because our interface allows the user great freedom in how they choose to define regions‐of‐interest to examine and compare, the classic geospatial analytic issue known as the modifiable areal unit problem (MAUP) quickly arises. The user may delineate regions with unseen differences that can affect the fairness of the comparisons made between them. To alleviate this problem, our interface first alerts the user if it detects any potential unfairness between regions when they are selected for comparison. It then presents the dimensions with potential problematic outliers to the user for evaluation. Finally, it provides a number of semi‐automated tools to assist the user in correcting their regions' boundaries to minimize the inequalities they feel could significantly impact their comparisons.     

The PAG Crowd: A Graph Based Approach for Efficient Data‐Driven Crowd Simulation

We present a data‐driven method for the real‐time synthesis of believable steering behaviours for virtual crowds. The proposed method interlinks the input examples into a structure we call the perception‐action graph (PAG) which can be used at run‐time to efficiently synthesize believable virtual crowds. A virtual character's state is encoded using a temporal representation, the Temporal Perception Pattern (TPP). The graph nodes store groups of similar TPPs whereas edges connecting the nodes store actions (trajectories) that were partially responsible for the transformation between the TPPs. The proposed method is being tested on various scenarios using different input data and compared against a nearest neighbours approach which is commonly employed in other data‐driven crowd simulation systems. The results show up to an order of magnitude speed‐up with similar or better simulation quality.     

Modal Locomotion: Animating Virtual Characters with Natural Vibrations

We present a general method to intuitively create a wide range of locomotion controllers for 3D legged characters. The key of our approach is the assumption that efficient locomotion can exploit the natural vibration modes of the body, where these modes are related to morphological parameters such as the shape, size, mass, and joint stiffness. The vibration modes are computed for a mechanical model of any 3D character with rigid bones, elastic joints, and additional constraints as desired. A small number of vibration modes can be selected with respect to their relevance to locomotion patterns and combined into a compact controller driven by very few parameters. We show that these controllers can be used in dynamic simulations of simple creatures, and for kinematic animations of more complex creatures of a variety of shapes and sizes.     

A Local/Global Approach to Mesh Parameterization

We present a novel approach to parameterize a mesh with disk topology to the plane in a shape‐preserving manner. Our key contribution is a local/global algorithm, which combines a local mapping of each 3D triangle to the plane, using transformations taken from a restricted set, with a global “stitch” operation of all triangles, involving a sparse linear system. The local transformations can be taken from a variety of families, e.g. similarities or rotations, generating different types of parameterizations. In the first case, the parameterization tries to force each 2D triangle to be an as‐similar‐as‐possible version of its 3D counterpart. This is shown to yield results identical to those of the LSCM algorithm. In the second case, the parameterization tries to force each 2D triangle to be an as‐rigid‐as‐possible version of its 3D counterpart. This approach preserves shape as much as possible. It is simple, effective, and fast, due to pre‐factoring of the linear system involved in the global phase. Experimental results show that our approach provides almost isometric parameterizations and obtains more shape‐preserving results than other state‐of‐the‐art approaches. We present also a more general “hybrid” parameterization model which provides a continuous spectrum of possibilities, controlled by a single parameter. The two cases described above lie at the two ends of the spectrum. We generalize our local/global algorithm to compute these parameterizations. The local phase may also be accelerated by parallelizing the independent computations per triangle.     

Soft Articulated Characters with Fast Contact Handling

Fast contact handling of soft articulated characters is a computationally challenging problem, in part due to complex interplay between skeletal and surface deformation. We present a fast, novel algorithm based on a layered representation for articulated bodies that enables physically-plausible simulation of animated characters with a high-resolution deformable skin in real time. Our algorithm gracefully captures the dynamic skeleton-skin interplay through a novel formulation of elastic deformation in the pose space of the skinned surface. The algorithm also overcomes the computational challenges by robustly decoupling skeleton and skin computations using careful approximations of Schur complements, and efficiently performing collision queries by exploiting the layered representation. With this approach, we can simultaneously handle large contact areas, produce rich surface deformations, and capture the collision response of a character/s skeleton.     

Simulation of Tearing Cloth with Frayed Edges

Woven cloth can commonly be seen in daily life and also in animation. Unless prevented in some way, woven cloth usually frays at the edges. However, in computer graphics, woven cloth is typically modeled as a continuum sheet, which is not suitable for representing frays. This paper proposes a model that allows yarn movement and slippage during cloth tearing. Drawing upon techniques from textile and mechanical engineering fields, we model cloth as woven yarn crossings where each yarn can be independently torn when the strain limit is reached. To make the model practical for graphics applications, we simulate only tearing part of cloth with a yarn‐level model using a simple constrained mass‐spring system for computational efficiency. We designed conditions for switching from a standard continuum sheet model to our yarn‐level model, so that frays can be initiated and propagated along the torn lines. Results show that our method can achieve plausible tearing cloth animation with frayed edges.