Physics-Based Animation

We introduce a new and efficient approach for collision detection in point-based animations, based on the fast computation of tight surface bounds. Our approach is able to tightly bound a high-resolution surface with a cost linear in the number of simulation nodes, which is typically small. We extend concepts about bounds of convex sets to the point-based deformation setting, and we introduce an efficient algorithm for finding extrema of these convex sets. We can compute surface bounds orders of magnitude faster and/or tighter than with previous methods.

Efficient Bounds for Point-Based Animations

Particle simulations as well as geometric modeling techniques have demonstrated their ability to process and render points interactively. However, real-time particle-based fluid simulations suffer from poor rendering quality due to low surface particle resolutions. Surfaces appear blobby, surface details are lost, and features like edges are degraded due to smoothing effects. This paper presents a novel point refinement method for irregularly sampled, dynamic points coming from a particle-based fluid simulation. Our interpolation algorithm can handle complex geometries including splashes, and at the same time preserves features like edges. Point collisions are avoided resulting in a nearly uniform sampling facilitating surface reconstruction techniques. No point preprocessing is necessary, and point neighborhoods are dynamically updated reducing computation and memory costs. We show that our algorithm can efficiently detect and refine the surface points of a fluid and we demonstrate the improvement of rendering quality and applicability to real-time simulations.

Efficient Refinement of Dynamic Point Data

Recent efforts to visually capture the phenomena of boiling have proposed monolithic approaches that extend the basic techniques underlying existing fluid solvers. In this work, we show that if we instead treat boiling as a separate computational module to be loosely coupled to an existing solver, a very easy to implement, highly efficient algorithm can be designed that produces excellent visual results, even on coarse (64^3) grids. The algorithm is also highly SIMD-amenable, allowing the boiling computation to be farmed out to a GPU or Playstation 3 Cell processor. Our algorithm takes less than 100 lines of commented, readable C++, and can be integrated into an existing particle level set fluid solver with virtually no modifications. A serial implementation consumes between 3-5% of the overall running time, and a preliminary SIMD implementation shows that a 64^3 simulation runs at 130 FPS, making the computational cost of the module totally negligible.

A Simple Boiling Module

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.

Real-Time Simulation of Thin Shells

Chemical phenomena abound in the real world, and often comprise indispensable elements of visual effects that are routinely created in the film industry. In this paper, we present a hybrid technique for simulating chemically reactive fluids, based on the theory of chemical kinetics. Our method makes synergistic use of both Eulerian grid-based methods and Lagrangian particle methods to simulate real and hypothetical chemical mechanisms effectively and efficiently. We demonstrate that by modeling chemical reactions using a particle system, an established, physically based fluid system can be extended easily to generate a wide range of chemical phenomena, ranging from catalysis and erosion to fire and explosions, with only a small additional cost.

Animation of Chemically Reactive Fluids Using a Hybrid Simulation Method

Hinge-based bending models are widely used in the physically-based animation of cloth, thin plates and shells. We propose a hinge-based model that is simpler to implement, more efficient to compute, and offers a greater number of effective material parameters than existing models. Our formulation builds on two mathematical observations: (a) the bending energy of curved flexible surfaces can be expressed as a cubic polynomial if the surface does not stretch; (b) a general class of anisotropic materials—those that are orthotropic—is captured by appropriate choice of a single stiffness per hinge. Our contribution impacts a general range of surface animation applications, from isotropic cloth and thin plates to orthotropic fracturing thin shells.

Cubic Shells

Bubbles and foam are important fluid phenomena on scales that we encounter in our lives every day. While different techniques to handle these effects were developed in the past years, they require a full 3D fluid solver with free surfaces and surface tension. We present a shallow water based particle model that is coupled with a smoothed particle hydrodynamics simulation to demonstrate that real-time simulations of bubble and foam effects are possible with high frame rates. A shallow water simulation is used to represent the overall water volume. It is coupled to a particle-based bubble simulation with a flow field of spherical vortices. This bubble simulation is interacting with a smoothed particle hydrodynamics simulation including surface tension to handle foam on the fluid surface. The realism and performance of our approach is demonstrated with several test cases that run with high frame rates on a standard PC.

Real-time Simulations of Bubbles and Foam within a Shallow-Water Framework

In this paper, we present a unified framework for reduced space modeling and rendering of dynamic and nonhomogenous participating media, like snow, smoke, dust and fog. The key idea is to represent the 3D spatial variation of the density, velocity and intensity fields of the media using the same analytic basis. In many situations, natural effects such as mist, outdoor smoke and dust are smooth (low frequency) phenomena, and can be compactly represented by a small number of coefficients of a Legendre polynomial basis. We derive analytic expressions for the derivative and integral operators in the Legendre coefficient space, as well as the triple product integrals of Legendre polynomials. These mathematical results allow us to solve both the Navier-Stokes equations for fluid flow and light transport equations for single scattering efficiently in the reduced Legendre space. Since our technique does not depend on volume grid resolution, we can achieve computational speedups as compared to spatial domain methods while having low memory and pre-computation requirements as compared to datadriven approaches. Also, analytic definition of derivatives and integral operators in the Legendre domain avoids the approximation errors inherent in spatial domain finite difference methods. We demonstrate many interesting visual effects resulting from particles immersed in fluids as well as volumetric scattering in non-homogenous and dynamic participating media, such as fog and mist.

Legendre Fluids: A Unified Framework for Analytic Reduced Space Modeling and Rendering of Participating Media

Real-time evaluation of distributed contact forces for rigid or deformable 3D objects is important for providing multi-sensory feedback in emerging real-time applications, such as 6-DoF haptic force-feedback rendering. Unfortunately, at very high temporal rates (1 kHz for haptics), there is often insufficient time to resolve distributed contact between geometrically complex objects.
In this paper, we present a spatially and temporally adaptive sample-based approach to approximate contact forces under hard real-time constraints. The approach is CPU based, and supports contact between a rigid and a reduced deformable model with complex geometry. Penalty-based contact forces are efficiently resolved using a multi-resolution point-based representation for one object, and a signed-distance field for the other. Hard realtime approximation of distributed contact forces uses multi-level progressive point-contact sampling, and exploits temporal coherence, graceful degradation and other optimizations. We present several examples of 6-DoF haptic rendering of geometrically complex rigid and deformable objects in distributed contact at real-time kilohertz rates.

Time-critical distributed contact for 6-DoF haptic rendering of adaptively sampled reduced deformable models

Simulation of deformations and collision detection are two highly intertwined problems that are often treated separately. This is especially true in existing elegant adaptive simulation techniques, where standard collision detection algorithms cannot leverage the adaptively selected degrees of freedom.We propose a seamless integration of multi-grid algorithms and collision detection that identifies boundary conditions while inherently exploiting adaptivity. We realize this integration through multiscale bounding hierarchies, a novel unified hierarchical representation, together with an adaptive multigrid algorithm for irregular meshes and an adaptivity-aware hierarchical collision detection algorithm. Our solution produces detailed deformations with adapted computational cost, but it also enables robust interactive simulation of self-colliding deformable objects with high-resolution surfaces.

Adaptive Deformations with Fast Tight Bounds