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.     

Head-eye Animation Corresponding to a Conversation for CG Characters

CG character animations, in which CG characters engage in conversations, are widely used in multimedia contents such as videos and games. In constructing such an animation, we should consider about many factors, such as the content of the utterance and the state of conversation, which necessitates a large amount of time and labor. To deal with this problem, this paper proposes a method, which generates the head-eye movements of the CG characters synchronized with the conversation. In this method, so as to generate a composite head-eye movement, the view line direction is divided into the head, eye and body rotations by sharing motion mechanism dynamically adjusted according to the view line direction. And letting the two modules generating the head and the eye movements share the same conversation state, head and eye movements synchronized with the conversation are generated. Finally, we apply the proposed method to the conversation scenes, and show that natural animation can be produced easily.     

Articulated Object Reconstruction and Markerless Motion Capture from Depth Video

We present an algorithm for acquiring the 3D surface geometry and motion of a dynamic piecewise‐rigid object using a single depth video camera. The algorithm identifies and tracks the rigid components in each frame, while accumulating the geometric information acquired over time, possibly from different viewpoints. The algorithm also reconstructs the dynamic skeleton of the object, thus can be used for markerless motion capture. The acquired model can then be animated to novel poses. We show the results of the algorithm applied to synthetic and real depth video.     

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.     

River Networks for Instant Procedural Planets

Realistic terrain models are required in many applications, especially in computer games. Commonly, procedural models are applied to generate the corresponding models and let users experience a wide variety of new environments. Existing algorithms generate landscapes immediately with view‐dependent resolution and without preprocessing. Unfortunately, landscapes generated by such algorithms lack river networks and therefore appear unnatural. Algorithms that integrate realistic river networks are computationally expensive and cannot be used to generate a locally adaptive high resolution landscape during a fly‐through. In this paper, we propose a novel algorithm to generate realistic river networks. Our procedural algorithm creates complete planets and landscapes with realistic river networks within seconds. It starts with a coarse base geometry of a planet without further preprocessing and user intervention. By exploiting current graphics hardware, the proposed algorithm is able to generate adaptively refined landscape geometry during fly‐throughs.     

Automatic Registration for Articulated Shapes

We present an unsupervised algorithm for aligning a pair of shapes in the presence of significant articulated motion and missing data, while assuming no knowledge of a template, user‐placed markers, segmentation, or the skeletal structure of the shape. We explicitly sample the motion, which gives a priori the set of possible rigid transformations between parts of the shapes. This transforms the problem into a discrete labeling problem, where the goal is to find an optimal assignment of transformations for aligning the shapes. We then apply graph cuts to optimize a novel cost function, which encodes a preference for a consistent motion assignment from both source to target and target to source. We demonstrate the robustness of our method by aligning several synthetic and real‐world datasets.     

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 Hierarchical Segmentation of Articulated Bodies

This paper presents a novel segmentation method to assist the rigging of articulated bodies. The method computes a coarse‐to‐fine hierarchy of segments ordered by the level of detail. The results are invariant to deformations, and numerically robust to noise, irregular tessellations, and topological short‐circuits. The segmentation is based on two key ideas. First, it exploits the multiscale properties of the diffusion distance on surfaces, and then it introduces a new definition of medial structures, composing a bijection between medial structures and segments. Our method computes this bijection through a simple and fast iterative approach, and applies it to triangulated meshes.     

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.     

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.     

Example-Based Rendering of Eye Movements

This paper describes a model for example-based, photo-realistic rendering of eye movements in 3D facial animation. Based on 3D scans of a face with different gaze directions, the model captures the motion of the eyeball along with the deformation of the eyelids and the surrounding skin. These deformations are represented in a 3D morphable model.
Unlike the standard procedure in facial animation, the eyeball is not modeled as a rotating 3D sphere located behind the skin surface. Instead, the visible region of the eyeball is part of a continuous face mesh, and displacements of the iris as well as occlusions by the lids are modeled in a texture mapping approach. The algorithm avoids artifacts that are widely encountered in 3D facial animation, and it presents a new concept of handling occlusions and discontinuities in morphing algorithms.     

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.     

Simplification of Articulated Meshes

We present a method for simplifying a polygonal character with an associated skeletal deformation such that the simplified character approximates the original shape well when deformed. As input, we require a set of example poses that are representative of the types of deformations the character undergoes and we produce a multi-resolution hierarchy for the simplified character where all simplified vertices also have associated skin weights. We create this hierarchy by minimizing an error metric for a simplified set of vertices and their skin weights, and we show that this quartic error metric can be effectively minimized using alternating quadratic minimization for the vertices and weights separately. To enable efficient GPU accelerated deformations of the simplified character, we also provide a method that guarantees the maximum number of bone weights per simplified vertex is less than a user specified threshold at all levels of the hierarchy.     

Simulating Inextensible Cloth Using Impulses

Computer simulation of cloth is often plagued by springs being over‐stretched. The evaluation of impulses to prevent over‐stretching is explained step‐by‐step. Our impulse approach controls the length of springs by a nonlinear system and then a novel linearization of it into a symmetric positive definite system. The cloth/solid collision handling is integrated into the linearized system seamlessly. Some results based on this method are also presented.     

Geodesic-Controlled Developable Surfaces for Modeling Paper Bending

We present a novel and effective method for modeling a developable surface to simulate paper bending in interactive and animation applications. The method exploits the representation of a developable surface as the envelope of rectifying planes of a curve in 3D, which is therefore necessarily a geodesic on the surface. We manipulate the geodesic to provide intuitive shape control for modeling paper bending. Our method ensures a natural continuous isometric deformation from a piece of bent paper to its flat state without any stretching. Test examples show that the new scheme is fast, accurate, and easy to use, thus providing an effective approach to interactive paper bending. We also show how to handle non-convex piecewise smooth developable surfaces.     

Real-Time Simulation of Thin Shells

This paper proposes a real-time simulation technique for thin shells undergoing large deformation. Shells are thin objects such as leaves and papers that can be abstracted as 2D structures. Development of a satisfactory physical model that runs in real-time but produces visually convincing animation of thin shells has been remaining a challenge in computer graphics. Rather than resorting to shell theory which involves the most complex formulations in continuum mechanics, we adopt the energy functions from the discrete shells proposed by Grinspun et al. [ [GHDS03] ]. For real-time integration of the governing equation, we develop a modal warping technique for shells. This new simulation framework results from making extensions to the original modal warping technique [ [CK05] ] which was developed for the simulation of 3D solids. We report experimental results, which show that the proposed method runs in real-time even for large meshes, and that it can simulate large bending and/or twisting deformations with acceptable realism.     

Fast Parallel Construction of Smooth Surfaces from Meshes with Tri/Quad/Pent Facets

Polyhedral meshes consisting of triangles, quads, and pentagons and polar configurations cover all major sampling and modeling scenarios. We give an algorithm for efficient local, parallel conversion of such meshes to an everywhere smooth surface consisting of low‐degree polynomial pieces. Quadrilateral facets with 4‐valent vertices are ‘regular’ and are mapped to bi‐cubic patches so that adjacent bi‐cubics join C² as for cubic tensor‐product splines. The algorithm can be implemented in the vertex and geometry shaders of the GPU pipeline and does not use the fragment shader. Its implementation in DirectX 10 achieves conversion plus rendering at 659 frames per second with 42.5 million triangles per second on input of a model of 1300 facets of which 60% are not regular.     

An Adaptive Contact Model for the Robust Simulation of Knots

In this paper, we present an adaptive model for dynamically deforming hyper‐elastic rods. In contrast to existing approaches, adaptively introduced control points are not governed by geometric subdivision rules. Instead, their states are determined by employing a non‐linear energy‐minimization approach. Since valid control points are computed instantaneously, post‐stabilization schemes are avoided and the stability of the dynamic simulation is improved. Due to inherently complex contact configurations, the simulation of knot tying using rods is a challenging task. In order to address this problem, we combine our adaptive model with a robust and accurate collision handling method for elastic rods. By employing our scheme, complex knot configurations can be simulated in a physically plausible way.     

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.