Real‐time Animation of Sand‐Water Interaction

Recent advances in physically‐based simulations have made it possible to generate realistic animations. However, in the case of solid‐fluid coupling, wetting effects have rarely been noticed despite their visual importance especially in interactions between fluids and granular materials. This paper presents a simple particle‐based method to model the physical mechanism of wetness propagating through granular materials; Fluid particles are absorbed in the spaces between the granular particles and these wetted granular particles then stick together due to liquid bridges that are caused by surface tension and which will subsequently disappear when over‐wetting occurs. Our method can handle these phenomena by introducing a wetness value for each granular particle and by integrating those aspects of behavior that are dependent on wetness into the simulation framework. Using this method, a GPU‐based simulator can achieve highly dynamic animations that include wetting effects in real time.     

Mixing Fluids and Granular Materials

Fluid animations in computer graphics show interactions with various kinds of objects. However, fluid flowing through a granular material such as sand is still not possible within current frameworks. In this paper, we present the simulation of fine granular materials interacting with fluids. We propose a unified Smoothed Particle Hydrodynamics framework for the simulation of both fluid and granular material. The granular volume is simulated as a continuous material sampled by particles. By incorporating previous work on porous flow in this simulation framework we are able to fully couple fluid and sand. Fluid can now percolate between sand grains and influence the physical properties of the sand volume. Our method demonstrates various new effects such as dry soil transforming into mud pools by rain or rigid sand structures being eroded by waves.     

Real‐time Rendering of Heterogeneous Translucent Objects with Arbitrary Shapes

We present a real‐time algorithm for rendering translucent objects of arbitrary shapes. We approximate the scattering of light inside the objects using the diffusion equation, which we solve on‐the‐fly using the GPU. Our algorithm is general enough to handle arbitrary geometry, heterogeneous materials, deformable objects and modifications of lighting, all in real‐time. In a pre‐processing step, we discretize the object into a regular 4‐connected structure (QuadGraph). Due to its regular connectivity, this structure is easily packed into a texture and stored on the GPU. At runtime, we use the QuadGraph stored on the GPU to solve the diffusion equation, in real‐time, taking into account the varying input conditions: Incoming light, object material and geometry. We handle deformable objects, provided the deformation does not change the topological structure of the objects.     

Determining interference between pairs of solids defined constructively in computer animation

This paper presents theory and implementation of a method for detecting interference between a pair of solid objects. Often at times, when performing simulations, two solids may unwittingly interpenetrate each other. The two components of the system presented in this paper are: (1) a surface representation method to model solid objects; and (2) a method for detecting interference. Body representation of a solid in this system is based upon enveloping each solid with surfaces (called positive entities). Most computer aided design (CAD) systems use solid modeling techniques to represent solid objects. Since most solid models use Boolean operations to model complex objects, a method is presented to envelop complex objects with parametric surfaces. A method for tracing intersection curves between two surfaces is also presented. Discontinuities on surfaces are defined as negative entitics in order to extend the method to complex solids. Determining interference is based upon a numerical algorithm for computing points of intersection between boundary curves and parametrized entities. The existence of segments of these curves inside the boundary of positive and negative entities is established by computing the circulation of a function around the boundary curve. Interference between two solids is then detected. No limitations are imposed on the convexity or simplicity of the boundary curves treated.     

ProcDef: Local‐to‐global Deformation for Skeleton‐free Character Animation

Animations of characters with flexible bodies such as jellyfish, snails, and, hearts are difficult to design using traditional skeleton‐based approaches. A standard approach is keyframing, but adjusting the shape of the flexible body for each key frame is tedious. In addition, the character cannot dynamically adjust its motion to respond to the environment or user input. This paper introduces a new procedural deformation framework (ProcDef) for designing and driving animations of such flexible objects. Our approach is to synthesize global motions procedurally by integrating local deformations. ProcDef provides an efficient design scheme for local deformation patterns; the user can control the orientation and magnitude of local deformations as well as the propagation of deformation signals by specifying line charts and volumetric fields. We also present a fast and robust deformation algorithm based on shape‐matching dynamics and show some example animations to illustrate the feasibility of our framework.     

Visualization of CFD results in immersive virtual environments

An object-oriented event-driven immersive virtual environment (VE) is described for the visualization of computational fluid dynamics (CFD) results. The VE incorporates the following types of primitive software objects: interface objects, support objects, geometric entities, and finite elements. The fluid domain is discretized using either a multi-block structured grid or an unstructured finite element mesh. The VE allows natural ‘fly-through’ visualization of the model, the CFD grid, and the model's surroundings. In order to help visualize the flow and its effects on the model, the VE incorporates the following objects: stream objects (lines, surface-restricted lines, ribbons, and volumes); colored surfaces; elevation surfaces; surface arrows; global and local iso-surfaces; vortex cores; and separation/attachment surfaces and lines. Most of these objects can be used for dynamically probing the flow. Particles and arrow animations can be displayed on top of stream objects. Primitive response quantities as well as derived quantities can be used. A recursive tree search algorithm is used for real-time point and value search in the CFD grid.     

Direct extraction of surface meshes from implicitly represented heterogeneous volumes

This paper describes a novel algorithm to extract surface meshes directly from implicitly represented heterogeneous models made of different constituent materials. Our approach can directly convert implicitly represented heterogeneous objects into a surface model separating homogeneous material regions, where every homogeneous region in a heterogeneous structure is enclosed by a set of two-manifold surface meshes. Unlike other discretization techniques of implicitly represented heterogeneous objects, the intermediate surfaces between two constituent materials can be directly extracted by our algorithm. Therefore, it is more convenient to adopt the surface meshes from our approach in the boundary element method (BEM) or as a starting model to generate volumetric meshes preserving intermediate surfaces for the finite element method (FEM). The algorithm consists of three major steps: firstly, a set of assembled two-manifold surface patches coarsely approximating the interfaces between homogeneous regions are extracted and segmented; secondly, signed distance fields are constructed such that each field expresses the Euclidean distance from points to the surface of one homogeneous material region; and finally, coarse patches generated in the first step are dynamically optimized to give adaptive and high-quality surface meshes. The manifold topology is preserved on each surface patch.     

Direct rendering of Boolean combinations of self-trimmed surfaces

We explore different semantics for the solid defined by a self-crossing surface (immersed sub-manifold). Specifically, we introduce rules for the interior/exterior classification of the connected components of the complement of a self-crossing surface produced through a continuous deformation process of an initial embedded manifold. We propose efficient GPU algorithms for rendering the boundary of the regularized union of the interior components, which is a subset of the initial surface and is called the trimmed boundary or simply the trim. This classification and rendering process is accomplished in real time through a rasterization process without computing any self-intersection curve, and hence is suited to support animations of self-crossing surfaces. The solid bounded by the trim can be combined with other solids and with half-spaces using Boolean operations and hence may be capped (trimmed by a half-space) or used as a primitive in direct CSG rendering. Being able to render the trim in real time makes it possible to adapt the tessellation of the trim in real time by using view-dependent levels-of-detail or adaptive subdivision.     

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.     

Sketching 3D Animations

We are interested in providing animators with a general-purpose tool allowing them to create animations using straight-ahead actions as well as pose-to-pose techniques. Our approach seeks to bring the expressiveness of real-time motion capture systems into a general-purpose multi-track system running on a graphics workstation. We emphasize the use of high-bandwidth interaction with 3D objects together with specific data reduction techniques for the automatic construction of editable representations of interactively sketched continuous parameter evolution. In this paper, we concentrate on providing a solution to the problem of applying data reduction techniques in an animation context. The requirements that must be fulfilled by the data reduction algorithm are analyzed. From the Lyche and Mørken knot removal strategy, we derive an incremental algorithm that computes a B-spline approximation to the original curve by considering only a small piece of the total curve at any time. This algorithm allows the processing of the user's captured motion in parallel with its specification, and guarantees constant latency time and memory needs for input motions composed of any number of samples. After showing the results obtained by applying our incremental algorithm to 3D animation paths, we describe an integrated environment to visually construct 3D animations, where all interaction is done directly in three dimensions. By recording the effects of user's manipulations and taking into account the temporal aspect of the interaction, straight-ahead animations can be defined. Our algorithm is automatically applied to continuous parameter evolution in order to obtain editable representations. The paper concludes with a presentation offuture work.     

Particle‐based simulation of bubbles in water–solid interaction

In this paper, a particle‐based multiphase method for creating realistic animations of bubbles in water–solid interaction is presented. To generate bubbles from gas dissolved in the water on the fly, we propose an approximate model for the creation of bubbles, which takes into account the influence of gas concentration in the water, the solid material, and water–solid velocity difference. As the air particle on the bubble surface is treated as a virtual nucleation site, the bubble absorbs air from surrounding water and grows. The density and pressure forces of air bubbles are computed separately using smoothed particle hydrodynamics; then, the two‐way coupling of bubbles with water and solid is solved by a new drag force, so the generated bubbles’ flow on the surface of solid and the deformation in the rising process can be simulated. Additionally, touching bubbles merge together under the cohesion forces weighted by the smoothing kernel and velocity difference. The experimental results show that this method is capable of simulating bubbles in water–solid interaction under different physical conditions. Copyright © 2012 John Wiley & Sons, Ltd.     

Brain peeling: viewing the inside of a laminar three-dimensional solid

We describe a 3D surface-tracking algorithm that is used to detect the interior laminar surfaces of a solid shell. Each of these surfaces is called a peel. Successive peels may be generated, thus representing the solid shell by its tangential layers. This algorithm is based on voxel surface-tracking methods and solves the problems associated with transforming a surface-tracking algorithm into a brain peeler. We also discuss the properties of the voxel surfaces produced by this algorithm. Using the connectivity properties of these objects, we are able to convert voxel representations into polyhedral representations without human interaction. We illustrate this work with a high-resolution reconstruction of a monkey visual cortex. Additional application domains of this work are in areas in which there is a natural laminar structure to a 3D solid, such as in geophysics (earth strata).Supported by System Development Foundation, AFOSR 85-0341, and the Nathan S. Kline Psychiatric Research Center     

Handling multiple materials for exposure of digital forgeries using 2-D lighting environments

The distribution of incident light is an important physics-based cue for exposing image manipulations. If an image has been composed from multiple sources, it is likely that the illumination environments of the spliced objects differ. Johnson and Farid introduced a proof-of-principle algorithm for a forensic comparison of lighting environments. However, this baseline approach suffers from relatively strict assumptions that limit its practical applicability. In this work, we address one of the biggest limitations, namely the need to compute a lighting environment from patches of homogeneous material. To compute a lighting environment from multiple-color surfaces, we propose a method that we call “intrinsic contour estimation” (ICE). ICE is able to integrate reflectances from multiple materials into one lighting environment, as long as surfaces of different materials share at least two similar normal vectors. We validate the proposed method in a controlled ground-truth experiment on two datasets, with light from three different directions. These experiments show that using ICE can improve the median estimation error by almost 50 %, and the mean error by almost 30 %.     

Collision response for deformable models based on hertz's contact theory

This paper presents an animation technique of collision response for deformable models defined as a spring-mass-damper system. Our approach is to calculate impulsive forces to prevent penetration of colliding objects by means of Hertz's contact theory. With this theory, contact duration and deformation in collision are obtained according to physical properties such as mass and elasticity. Animators, therefore, can represent the differences between materials such as rubber and steel in the sequence of collision animations with a few intuitive physical parameters. We also describe a deformation mapping technique which reduces the computational time of dynamic analysis and realizes the effect of global deformation.     

Volume-preserving free-form solids

Some important trends in geometric modeling are the reliance on solid models rather than surface-based models and the enhancement of the expressive power of models, by using free-form objects in addition to the usual geometric primitives and by incorporating physical principles. An additional trend is the emphasis on interactive performance. In this paper, we integrate all of these requirements into a single geometric primitive by endowing the tri-variate tensor-product free-form solid with several important physical properties, including volume and internal deformation energy. Volume preservation is of benefit in several application areas of geometric modeling, including computer animation, industrial design and mechanical engineering. However, previous physics-based methods, which have usually used some form of “energy”, have neglected the issue of volume (or area) preservation. We present a novel method for modeling an object composed of several tensor-product solids while preserving the desired volume of each primitive and ensuring high-order continuity constraints between the primitives. The method utilizes the Uzawa algorithm for non-linear optimization, with objective functions based on deformation energy or least squares. We show how the algorithm can be used in an interactive environment by relaxing exactness requirements while the user interactively manipulates free-form solid primitives. On current workstations, the algorithm runs in real-time for tri-quadratic volumes and close to real-time for tri-cubic volumes     

Animating strings with twisting,tearing and flicking effects

String‐like objects in our daily lives, for example shoelaces, threads, rubber cords, plastic fiber and spaghetti, have a wide variety of materials. Such string‐like objects also exhibit interesting behaviors such as twisting, tearing (by stretching or twisting), and bouncing back when pulled and released. In this paper, we present a method that enables these behaviors and simulates such materials in traditional string simulation methods that explicitly represent a string by particles and segments. Specifically, we offer the following three contributions. First, we introduce a method for handling twisting effects with both uniform and non‐uniform torsional rigidities. Second, we propose a method for estimating the tension acting on inextensible strings in order to reproduce tearing and flicking (bouncing back), whereas the tension for an extensible object can be computed via stretched length. The length of an inextensible object is maintained constant in general, and thus, we need a novel approach. Third, we introduce an optimized grid‐based collision detection for accelerating the computation. We demonstrate that our method can produce visually plausible animations of string‐like objects with various material properties, and it is a fast framework for interactive applications such as games. Copyright © 2012 John Wiley & Sons, Ltd.     

Rethinking the evaluation of algorithm animations as learning aids: an observational study

One important aspect of creating computer programs is having a sound understanding of the underlying algorithms used by programs. Learning about algorithms, just like learning to program, is difficult, however. A number of prior studies have found that using animation to help teach algorithms had less beneficial effects on learning than hoped. Those results surprise many computer science instructors whose intuition leads them to believe that algorithm animations should assist instruction. This article reports on a study in which animation is utilized in more of a “homework” learning scenario rather than a “final exam” scenario. Our focus is on understanding how learners will utilize animation and other instructional materials in trying to understand a new algorithm, and on gaining insight into how animations can fit into successful learning strategies. The study indicates that students use sophisticated combinations of instructional materials in learning scenarios. In particular, the presence of algorithm animations seems to make a complicated algorithm more accessible and less intimidating, thus leading to enhanced student interaction with the materials and facilitating learning.     

Interactive Rendering of Deforming NURBS Surfaces

Non-uniform rational B-splines (NURBS) has been widely accepted as a standard tool for geometry representation and design. Its rich geometric properties allow it to represent both analytic shapes and free-form curves and surfaces precisely. Moreover, a set of tools is available for shape modification or more implicitly, object deformation. Existing NURBS rendering methods include de Boor algorithm, Oslo algorithm, Shantz’s adaptive forward differencing algorithm and Silbermann’s high speed implementation of NURBS. However, these methods consider only speeding up the rendering process of individual frames. Recently, Kumar et al. proposed an incremental method for rendering NURBS surfaces, but it is still limited to static surfaces. In real-time applications such as virtual reality, interactive display is needed. If a virtual environment contains a lot of deforming objects, these methods cannot provide a good solution. In this paper, we propose an efficient method for interactive rendering of deformable objects by maintaining a polygon model of each deforming NURBS surface and adaptively refining the resolution of the polygon model. We also look at how this method may be applied to multi-resolution modelling.