A Point-based Method for Animating Incompressible Flow

FunShing Sin, Adam W. Bargteil, and Jessica K. Hodgins

Abstract

In this paper, we present a point-based method for animating incompressible flow. The advection term is handled by moving the sample points through the flow in a Lagrangian fashion. However, unlike most previous approaches, the pressure term is handled by performing a projection onto a divergence-free field. To perform the pressure projection, we compute a Voronoi diagram with the sample points as input. Borrowing from Finite Volume Methods, we then invoke the divergence theorem and ensure that each Voronoi cell is divergence free. To handle complex boundary conditions, Voronoi cells are clipped against obstacle boundaries and free surfaces. The method is stable, flexible and combines many of the desirable features of point-based and grid-based methods. We demonstrate our approach on several examples of splashing and streaming liquid and swirling smoke.

Citation

FunShing Sin, Adam W. Bargteil, and Jessica K. Hodgins. A point-based method for animating incompressible flow. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation, Aug 2009. [BiBTeX]

Links

• Project page

Estimating Natural Illumination from a Single Outdoor Image

Jean-François Lalonde, Alexei A. Efros, and Srinivasa G. Narasimhan

Abstract

Given a single outdoor image, we present a method for estimating the likely illumination conditions of the scene. In particular, we compute the probability distribution over the sun position and visibility. The method relies on a combination of weak cues that can be extracted from different portions of the image: the sky, the vertical surfaces, and the ground. While no single cue can reliably estimate illumination by itself, each one can reinforce the others to yield a more robust estimate. This is combined with a data-driven prior computed over a dataset of 6 million Internet photos. We present quantitative results on a webcam dataset with annotated sun positions, as well as qualitative results on consumer- grade photographs downloaded from Internet. Based on the estimated illumination, we show how to realistically insert synthetic 3-D objects into the scene.

Citation

Jean-François Lalonde, Alexei A. Efros, and Srinivasa G. Narasimhan. Estimating natural illumination from a single outdoor image. In IEEE International Conference on Computer Vision, 2009. [BiBTeX]

Links

• Project page

Leveraging the Talent of Hand Animators to Create Three-Dimensional Animation

Eakta Jain, Yaser Sheikh, and Jessica K. Hodgins

Abstract

The skills required to create compelling three-dimensional animation using computer software are quite different from those required to create compelling hand animation with pencil and paper. The three-dimensional medium has several advantages over the traditional medium- it is easy to relight the scene, render it from different viewpoints, and add physical simulations. In this work, we propose a method to leverage the talent of traditionally trained hand animators to create three-dimensional animation, while allowing them to work in the medium that is familiar to them. The input to our algorithm is a set of hand-animated frames. Our key insight is to use motion capture data as a source of domain knowledge and 'lift' the two-dimensional animation to three dimensions, while maintaining the unique style of the input animation. A motion capture clip is projected to two dimensions, the limbs are aligned with the hand-drawn frames, and then the motion is reconstructed into three dimensions. We demonstrate our algorithm on a variety of hand animated motion sequences on different characters, including ballet, a stylized sneaky walk, and a sequence of jumping jacks.

Citation

Eakta Jain, Yaser Sheikh, and Jessica K. Hodgins. Leveraging the talent of hand animators to create three-dimensional animation. In Proc. ACM SIGGRAPH/Eurographics Symposium on Computer Animation, August 2009. [BiBTeX]

Links

• Project page

Local Layering

James McCann and Nancy S. Pollard

Abstract

In a conventional 2d painting or compositing program, graphical objects are stacked in a user-specified global order, as if each were printed on an image-sized sheet of transparent film. In this work we show how to relax this restriction so that users can make stacking decisions on a per-overlap basis, as if the layers were pictures cut from a magazine. This allows for complex and visually exciting overlapping patterns, without painstaking layer-splitting, depth-value painting, region coloring, or mask-drawing. Instead, users are presented with a layers dialog which acts locally. Behind the scenes, we divide the image into overlap regions and track the ordering of layers in each region. We formalize this structure as a graph of stacking lists, define the set of orderings where layers do not interpenetrate as consistent, and prove that our local stacking operators are both correct and sufficient to reach any consistent stacking. We also provide a method for updating the local stacking when objects change shape or position due to user editing -- this scheme prevents layer updates from producing undesired intersections. Our method extends trivially to both animation compositing and local visibility adjustment in depth-peeled 3d scenes; the latter of which allows for the creation of impossible figures which can be viewed and manipulated in real-time.

Citation

James McCann and Nancy S. Pollard. Local layering. ACM Transactions on Graphics (SIGGRAPH 2008), 28(3), August 2009. [BiBTeX]

Links

• Project page

Modular Bases for Fluid Dynamics

Martin Wicke, Matt Stanton, and Adrien Treuille

Abstract

We present a new approach to fluid simulation that balances the speed of model reduction with the flexibility of grid-based methods. We construct a set of composable reduced models, or tiles, which capture spatially localized fluid behavior. We then precompute coupling terms so that these models can be rearranged at runtime. To enforce consistency between tiles, we introduce constraint reduction. This technique modifies a reduced model so that a given set of linear constraints can be fulfilled. Because dynamics and constraints can be solved entirely in the reduced space, our method is extremely fast and scales to large domains.

Citation

Martin Wicke, Matt Stanton, and Adrien Treuille. Modular bases for fluid dynamics. ACM Transactions on Graphics (SIGGRAPH 2009), 28(3), August 2009. [BiBTeX]

Links

• Project page

Simulating Balance Recovery Responses to Trips Based on Biomechanical Principles

Takaaki Shiratori, Brooke Coley, Rakié Cham, and Jessica K. Hodgins

Abstract

To realize the full potential of human simulations in interactive environments, we need controllers that have the ability to respond appropriately to unexpected events. In this paper, we create controllers for the trip recovery responses that occur during walking. Two strategies have been identified in human responses to tripping: impact from an obstacle during early swing leads to an elevating strategy, in which the swing leg is lifted over the obstacle and impact during late swing leads to a lowering strategy, in which a swing leg is positioned immediately in front of the obstacle and then the other leg is swung forward and positioned in front of the body to allow recovery from the fall. We design controllers for both strategies based on the available biomechanical literature and data captured from human subjects in the laboratory. We evaluate our controllers by comparing simulated results and actual responses obtained from a motion capture system.

Citation

Takaaki Shiratori, Brooke Coley, Rakié Cham, and Jessica K. Hodgins. Simulating balance recovery responses to trips based on biomechanical principles. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation, Aug 2009. [BiBTeX]

Links

• Project page

Modeling Spatial and Temporal Variation in Motion Data

Manfred Lau, Ziv Bar-Joseph, and James Kuffner

Abstract

We present a novel method to model and synthesize variation in motion data. Given a few examples of a particular type of motion as input, we learn a generative model that is able to synthesize a family of spatial and temporal variants that are statistically similar to the input examples. The new variants retain the features of the original examples, but are not exact copies of them. We learn a Dynamic Bayesian Network model from the input examples that enables us to capture properties of conditional independence in the data, and model it using a multivariate probability distribution. We present results for a variety of human motion, and 2D handwritten characters. We perform a user study to show that our new variants are less repetitive than typical game and crowd simulation approaches of re-playing a small number of existing motion clips. Our technique can synthesize new variants efficiently and has a small memory requirement.

Citation

Manfred Lau, Ziv Bar-Joseph, and James Kuffner. Modeling spatial and temporal variation in motion data. ACM Transactions on Graphics (SIGGRAPH Asia 2009), 28(5), 2009. [BiBTeX]

Links

• Project page

Webcam Clip Art: Appearance and Illuminant Transfer from Time-lapse Sequences

Jean-François Lalonde, Alexei A. Efros, and Srinivasa G. Narasimhan

Abstract

Webcams placed all over the world observe and record the visual appearance of a variety of outdoor scenes over long periods of time. The recorded time-lapse image sequences cover a wide range of illumination and weather conditions -- a vast untapped resource for creating visual realism. In this work, we propose to use a large repository of webcams as a 'clip art' library from which users may transfer scene appearance (objects, scene backdrops, outdoor illumination) into their own time-lapse sequences or even single photographs. The goal is to combine the recent ideas from data-driven appearance transfer techniques with a general and theoretically-grounded physically-based illumination model. To accomplish this, the paper presents three main research contributions: 1) a new, high-quality outdoor webcam database of over 1300 sequences containing over 1.2 million images, calibrated radiometrically and geometrically; 2) a novel approach for matching illuminations across different scenes based on the estimation of the properties of natural illuminants (sun, sky, weather and clouds), the camera geometry, and illumination-dependent scene features; 3) a new algorithm for generating physically plausible high dynamic range environment maps for each frame in a webcam sequence.

Citation

Jean-François Lalonde, Alexei A. Efros, and Srinivasa G. Narasimhan. Webcam clip art: Appearance and illuminant transfer from time-lapse sequences. ACM Transactions on Graphics (SIGGRAPH Asia 2009), 28(5), 2009. [BiBTeX]

Links

• Project page

Accelerometer-based User Interfaces for the Control of a Physically Simulated Character

Takaaki Shiratori and Jessica K. Hodgins

Abstract

In late 2006, Nintendo released a new game controller, the Wiimote, which included a three-axis accelerometer. Since then, a large variety of novel applications for these controllers have been developed by both independent and commercial developers. We add to this growing library with three performance interfaces that allow the user to control the motion of a dynamically simulated, animated character through the motion of his or her arms, wrists, or legs. For comparison, we also implement a traditional joystick/button interface. We assess these interfaces by having users test them on a set of tracks containing turns and pits. Two of the interfaces (legs and wrists) were judged to be more immersive and were better liked than the joystick/button interface by our subjects. All three of the Wiimote interfaces provided better control than the joystick interface based on an analysis of the failures seen during the user study.

Citation

Takaaki Shiratori and Jessica K. Hodgins. Accelerometer-based user interfaces for the control of a physically simulated character. ACM Transactions on Graphics (SIGGRAPH Asia 2008), 27(5), December 2008. [BiBTeX]

Links

• Project page

Backward Steps in Rigid Body Simulation

Christopher D. Twigg and Doug L. James

Abstract

Physically based simulation of rigid body dynamics is commonly done by time-stepping systems forward in time. In this paper, we propose methods to allow time-stepping rigid body systems backward in time. Unfortunately, reverse-time integration of rigid bodies involving frictional contact is mathematically ill-posed, and can lack unique solutions. We instead propose time-reversed rigid body integrators that can sample possible solutions when unique ones do not exist. We also discuss challenges related to dissipation-related energy gain, sensitivity to initial conditions, stacking, constraints and articulation, rolling, sliding, skidding, bouncing, high angular velocities, rapid velocity growth from micro-collisions, and other problems encountered when going against the usual flow of time.

Citation

Christopher D. Twigg and Doug L. James. Backward steps in rigid body simulation. ACM Transactions on Graphics (SIGGRAPH 2008), 27(3), August 2008. [BiBTeX]

Links

• Project page

Image-based Shaving

Minh Hoai Nguyen, Jean-François Lalonde, Alexei A. Efros, and Fernando de la Torre

Abstract

Many categories of objects, such as human faces, can be naturally viewed as a composition of several different layers. For example, a bearded face with glasses can be decomposed into three layers: a layer for glasses, a layer for the beard and a layer for other permanent facial features. While modeling such a face with a linear subspace model could be very difficult, layer separation allows for easy modeling and modification of some certain structures while leaving others unchanged. In this paper, we present a method for automatic layer extraction and its applications to face synthesis and editing. Layers are automatically extracted by utilizing the differences between subspaces and modeled separately. We show that our method can be used for tasks such beard removal (virtual shaving), beard synthesis, and beard transfer, among others.

Citation

Minh Hoai Nguyen, Jean-François Lalonde, Alexei A. Efros, and Fernando de la Torre. Image-based shaving. Computer Graphics Forum Journal (Eurographics 2008), 27(2), 2008. [BiBTeX]

Links

• Project page

Laziness is a virtue: Motion stitching using effort minimization

Lei Li, James McCann, Christos Faloutsos, and Nancy Pollard

Abstract

Given two motion-capture sequences that are to be stitched together, how can we assess the goodness of the stitching? The straightforward solution, Euclidean distance, permits counter-intuitive results because it ignores the effort required to actually make the stitch. The main contribution of our work is that we propose an intuitive, first-principles approach, by computing the effort that is needed to do the transition (laziness-effort, or 'L-score'). Our conjecture is that, the smaller the effort, the more natural the transition will seem to humans. Moreover, we propose the elastic L-score which allows for elongated stitching, to make a transition as natural as possible. We present preliminary experiments on both artificial and real motions which show that our L-score approach indeed agrees with human intuition, it chooses good stitching points, and generates natural transition paths.

Citation

Lei Li, James McCann, Christos Faloutsos, and Nancy Pollard. Laziness is a virtue: Motion stitching using effort minimization. In Short Papers Proceedings of EUROGRAPHICS, 2008. [BiBTeX]

Links

• Project page

Preparatory object rotation as a human-inspired grasping strategy

Lillian Y. Chang, Garth J. Zeglin, and Nancy S. Pollard

Abstract

Humans exhibit a rich set of manipulation strategies that may be desirable to mimic in humanoid robots. This study investigates preparatory object rotation as a manipulation strategy for grasping objects from different presented orientations. First, we examine how humans use preparatory rotation as a grasping strategy for lifting heavy objects with handles. We used motion capture to record human manipulation examples of 10 participants grasping objects under different task constraints. When sliding contact of the object on the surface was permitted, participants used preparatory rotation to first adjust the object handle to a desired orientation before grasping to lift the object from the surface. Analysis of the human examples suggests that humans may use preparatory object rotation in order to reuse a particular type of grasp in a specific capture region or to decrease the joint torques required to maintain the lifting pose. Second, we designed a preparatory rotation strategy for an anthropomorphic robot manipulator as a method of extending the capture region of a specific grasp prototype. The strategy was implemented as a sequence of two open-loop actions mimicking the human motion: a preparatory rotation action followed by a grasping action. The grasping action alone can only successfully lift the object from a 45-degree region of initial orientations (4 of 24 tested conditions). Our empirical evaluation of the robot preparatory rotation shows that even using a simple open-loop rotation action enables the reuse of the grasping action for a 360-degree capture region of initial object orientations (24 of 24 tested conditions).

Citation

Lillian Y. Chang, Garth J. Zeglin, and Nancy S. Pollard. Preparatory object rotation as a human-inspired grasping strategy. In IEEE-RAS International Conference on Humanoid Robots (Humanoids 2008), pages 527–534, December 2008. [BiBTeX]

Links

• Project page

Real-Time Gradient-Domain Painting

James McCann and Nancy S. Pollard

Abstract

We present an image editing program which allows artists to paint in the gradient domain with real-time feedback on megapixel-sized images. Along with a pedestrian, though powerful, gradient-painting brush and gradient-clone tool, we introduce an edge brush designed for edge selection and replay. These brushes, coupled with special blending modes, allow users to accomplish global lighting and contrast adjustments using only local image manipulations -- e.g. strengthening a given edge or removing a shadow boundary. Such operations would be tedious in a conventional intensity-based paint program and hard for users to get right in the gradient domain without real-time feedback. The core of our paint program is a simple-to-implement GPU multigrid method which allows integration of megapixel-sized full-color gradient fields at over 20 frames per second on modest hardware. By way of evaluation, we present example images produced with our program and characterize the iteration time and convergence rate of our integration method.

Citation

James McCann and Nancy S. Pollard. Real-time gradient-domain painting. ACM Transactions on Graphics (SIGGRAPH 2008), 27(3), August 2008. [BiBTeX]

Links

• Project page

Six-DoF Haptic Rendering of Contact between Geometrically Complex Reduced Deformable Models

Jernej Barbič and Doug L. James

Abstract

Real-time evaluation of distributed contact forces between rigid or deformable 3D objects is a key ingredient of 6-DoF force-feedback rendering. Unfortunately, at very high temporal rates, there is often insufficient time to resolve contact between geometrically complex objects. We propose a spatially and temporally adaptive approach to approximate distributed contact forces under hard real-time constraints. Our method is CPU-based and supports contact between rigid or reduced deformable models with complex geometry. We propose a contact model that uses a point-based representation for one object and a signed-distance field for the other. This model is related to the Voxmap-PointShell (VPS) method, but gives continuous contact forces and torques, enabling stable rendering of stiff penalty-based distributed contacts. We demonstrate that stable haptic interactions can be achieved by point-sampling offset surfaces to input "polygon soup" geometry using particle repulsion. We introduce a multiresolution nested pointshell construction that permits level-of-detail contact forces and enables graceful degradation of contact in close-proximity scenarios. Parametrically deformed distance fields are proposed for contact between reduced deformable objects. We present several examples of 6-DoF haptic rendering of geometrically complex rigid and deformable objects in distributed contact at real-time kilohertz rates.

Citation

Jernej Barbič and Doug L. James. Six-dof haptic rendering of contact between geometrically complex reduced deformable models. IEEE Transactions on Haptics, 1(1):39–52, 2008. [BiBTeX]

Links

• Project page

What does the sky tell us about the camera?

Jean-François Lalonde, Srinivasa G. Narasimhan, and Alexei A. Efros

Abstract

As the main observed illuminant outdoors, the sky is a rich source of information about the scene. However, it is yet to be fully explored in computer vision because its appearance depends on the sun position, weather conditions, photometric and geometric parameters of the camera, and the location of capture. In this paper, we propose the use of a physically-based sky model to analyze the information available within the visible portion of the sky, observed over time. By fitting this model to an image sequence, we show how to extract camera parameters such as the focal length, and the zenith and azimuth angles. In short, the sky serves as a geometric calibration target. Once the camera parameters are recovered, we show how to use the same model in two applications: 1) segmentation of the sky and cloud layers, and 2) data-driven sky matching across different image sequences based on a novel similarity measure defined on sky parameters. This measure, combined with a rich appearance database, allows us to model a wide range of sky conditions.

Citation

Jean-François Lalonde, Srinivasa G. Narasimhan, and Alexei A. Efros. What does the sky tell us about the camera? In European Conference on Computer Vision, 2008. [BiBTeX]

Links

• Project page

FMDistance: A fast and effective distance function for motion capture data

Kensuke Onuma, Christos Faloutsos, and Jessica K. Hodgins

Abstract

Given several motion capture sequences, of similar (but not identical) length, what is a good distance function? We want to find similar sequences, to spot outliers, to create clusters, and to visualize the (large) set of motion capture sequences at our disposal. We propose a set of new features for motion capture sequences. We experiment with numerous variations (112 feature-sets in total, using variations of weights, logarithms, dimensionality reduction), and we show that the appropriate combination leads to near-perfect classification on a database of 226 actions with twelve different categories, and it enables visualization of the whole database as well as outlier detection.

Citation

Kensuke Onuma, Christos Faloutsos, and Jessica K. Hodgins. FMDistance: A fast and effective distance function for motion capture data. In Short Papers Proceedings of EUROGRAPHICS, 2008. [BiBTeX]

Links

• Paper (PDF, 193KB)

Action Capture with Accelerometers

Ronit Slyper and Jessica Hodgins

Abstract

We create a performance animation system that leverages the power of low-cost accelerometers, readily available motion capture databases, and construction techniques from e-textiles. Our system, built with only off-the-shelf parts, consists of five accelerometers sewn into a comfortable shirt that streams data to a computer. The accelerometer readings are continuously matched against accelerations computed from existing motion capture data, and an avatar is animated with the closest match. We evaluate our system visually and using simultaneous motion and accelerometer capture.

Citation

Ronit Slyper and Jessica Hodgins. Action capture with accelerometers. In 2008 ACM SIGGRAPH / Eurographics Symposium on Computer Animation, July 2008. [BiBTeX]

Links

• Project page

IM2GPS: Estimating geographic information from a single image

James Hays and Alexei A. Efros

Abstract

Estimating geographic information from an image is an excellent, difficult high-level computer vision problem whose time has come. The emergence of vast amounts of geographically-calibrated image data is a great reason for computer vision to start looking globally — on the scale of the entire planet! In this paper, we propose a simple algorithm for estimating a distribution over geographic locations from a single image using a purely data-driven scene matching approach. For this task, we will leverage a dataset of over 6 million GPS-tagged images from the Internet. We represent the estimated image location as a probability distribution over the Earth's surface. We quantitatively evaluate our approach in several geolocation tasks and demonstrate encouraging performance (up to 30 times better than chance). We show that geolocation estimates can provide the basis for numerous other image understanding tasks such as population density estimation, land cover estimation or urban/rural classification.

Citation

James Hays and Alexei A. Efros. Im2gps: Estimating geographic information from a single image. In Proceedings of the IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 2008. [BiBTeX]

Links

• Project page

Method for determining kinematic parameters of the in vivo thumb carpometacarpal joint

Lillian Y. Chang and Nancy S. Pollard

Abstract

The mobility of the thumb carpometacarpal (CMC) joint is critical for functional grasping and manipulation tasks. We present an optimization technique for determining from surface marker measurements a subject-specific kinematic model of the in vivo CMC joint that is suitable for measuring mobility. Our anatomy-based cost metric scores a candidate joint model by the plausibility of the corresponding joint angle values and kinematic parameters rather than only the marker trajectory reconstruction error. The proposed method repeatably determines CMC joint models with anatomically-plausible directions for the two dominant rotational axes and a lesser range of motion (RoM) for the third rotational axis. We formulate a low-dimensional parameterization of the optimization domain by first solving for joint axis orientation variables that then constrain the search for the joint axis location variables. Individual CMC joint models were determined for 24 subjects. The directions of the flexion-extension (FE) axis and adduction-abduction (AA) axis deviated on average by 9 degrees and 22 degrees, respectively, from the mean axis direction. The average RoM for FE, AA, and pronation-supination (PS) joint angles were 76 degrees, 43 degrees, and 23 degrees for active CMC movement. The mean separation distance between the FE and AA axes was 4.6 mm, and the mean skew angle was 87 degrees from the positive flexion axis to the positive abduction axis.

Citation

Lillian Y. Chang and Nancy S. Pollard. Method for determining kinematic parameters of the in vivo thumb carpometacarpal joint. IEEE Transactions on Biomedical Engineering, 55(7):1897–1906, July 2008. [BiBTeX]

Links

• Project page

A Finite Element Method for Animating Large Viscoplastic Flow

Adam W. Bargteil, Chris Wojtan, Jessica K. Hodgins, and Greg Turk

Abstract

We present an extension to Lagrangian finite element methods to allow for large plastic deformations of solid materials. These behaviors are seen in such everyday materials as shampoo, dough, and clay as well as in fantastic gooey and blobby creatures in special effects scenes. To account for plastic deformation, we explicitly update the linear basis functions defined over the finite elements during each simulation step. When these updates cause the basis functions to become ill-conditioned, we remesh the simulation domain to produce a new high-quality finite-element mesh, taking care to preserve the original boundary. We also introduce an enhanced plasticity model that preserves volume and includes creep and work hardening/softening. We demonstrate our approach with simulations of synthetic objects that squish, dent, and flow. To validate our methods, we compare simulation results to videos of real materials.

Citation

Adam W. Bargteil, Chris Wojtan, Jessica K. Hodgins, and Greg Turk. A finite element method for animating large viscoplastic flow. ACM Transactions on Graphics (SIGGRAPH 2007), 26(3), August 2007. [BiBTeX]

Links

• Project page

Constrained least-squares optimization for robust estimation of center of rotation

Lillian Y. Chang and Nancy S. Pollard

Abstract

This paper presents a new direct method for estimating the average center of rotation (CoR). An existing least-squares (LS) solution has been shown by previous works to have reduced accuracy for data with small range of motion (RoM). Alternative methods proposed to improve the CoR estimation use iterative algorithms. However, in this paper we show that with a carefully chosen normalization scheme, constrained least-squares solutions can perform as well as iterative approaches, even for challenging problems with significant noise and small RoM. In particular, enforcing the normalization constraint avoids poor fits near plane singularities that can affect the existing LS method. Our formulation has an exact solution, accounts for multiple markers simultaneously, and does not depend on manually-adjusted parameters. Simulation tests compare the method to four published CoR estimation techniques. The results show that the new approach has the accuracy of the iterative methods as well as the short computation time and repeatability of a least-squares solution. In addition, application of the new method to experimental motion capture data of the thumb carpometacarpal (CMC) joint yielded a more plausible CoR location compared to the previously reported LS solution and required less time than all four alternative techniques.

Citation

Lillian Y. Chang and Nancy S. Pollard. Constrained least-squares optimization for robust estimation of center of rotation. Journal of Biomechanics, 40(6):1392–1400, 2007. [BiBTeX]

Links

• Project page

Constraint-based Motion Optimization Using A Statistical Dynamic Model

Jinxiang Chai and Jessica K. Hodgins

Abstract

We present a technique for generating animation from a variety of user-defined constraints. We pose constraint-based motion synthesis as a maximum a posterior (MAP) problem and develop an optimization framework that generates natural motion satisfying user constraints. The system automatically learns a statistical dynamic model from motion capture data and then enforces it as a motion prior. This motion prior, together with user-defined constraints, comprises a trajectory optimization problem. Solving this problem in the low-dimensional space yields optimal natural motion that achieves the goals specified by the user.
We demonstrate the effectiveness of this approach in two domains: human body animation and facial animation. We show that the system can generate natural-looking animation from key-frame constraints, key-trajectory constraints, and a combination of these two constraints. For example, the user can generate a walking animation from a small set of key frames and foot contact constraints. The user can also specify a small set of key trajectories for the root, hands and feet positions to generate a realistic jumping motion. The system can generate motions for a character whose skeletal model is markedly different from those of the subjects in the database. We also show that the system can use a statistical dynamic model learned from a normal walking sequence to create new motion such as walking on a slope.

Citation

Jinxiang Chai and Jessica K. Hodgins. Constraint-based motion optimization using a statistical dynamic model. ACM Transactions on Graphics (SIGGRAPH 2007), 26(3), August 2007. [BiBTeX]

Links

• Project page

Construction and optimal search of interpolated motion graphs

Alla Safonova and Jessica K. Hodgins

Abstract

Many compelling applications would become feasible if novice users had the ability to synthesize high quality human motion based only on a simple sketch and a few easily specified constraints. We approach this problem by representing the desired motion as an interpolation of two time-scaled paths through a motion graph. The graph is constructed to support interpolation and pruned for efficient search. We use an anytime version of A* search to find a globally optimal solution in this graph that satisfies the user's specification. Our approach retains the natural transitions of motion graphs and the ability to synthesize physically realistic variations provided by interpolation. We demonstrate the power of this approach by synthesizing optimal or near optimal motions that include a variety of behaviors in a single motion.

Citation

Alla Safonova and Jessica K. Hodgins. Construction and optimal search of interpolated motion graphs. ACM Transactions on Graphics (SIGGRAPH 2007), 26(3), August 2007. [BiBTeX]

Links

• Project page

Data driven grasp synthesis using shape matching and task-based pruning

Ying Li, Jiaxin L. Fu, and Nancy S. Pollard

Abstract

Human grasps, especially whole-hand grasps, are difficult to animate because of the high number of degrees of freedom of the hand and the need for the hand to conform naturally to the object surface. Captured human motion data provides us with a rich source of examples of natural grasps. However, for each new object, we are faced with the problem of selecting the best grasp from the database and adapting it to that object. This paper presents a data-driven approach to grasp synthesis. We begin with a database of captured human grasps. To identify candidate grasps for a new object, we introduce a novel shape matching algorithm that matches hand shape to object shape by identifying collections of features having similar relative placements and surface normals. This step returns many grasp candidates, which are clustered and pruned by choosing the grasp best suited for the intended task. For pruning undesirable grasps, we develop an anatomically based grasp quality measure specific to the human hand. Examples of grasp synthesis are shown for a variety of objects not present in the original database. This algorithm should be useful both as an animator tool for posing the hand and for automatic grasp synthesis in virtual environments.

Citation

Ying Li, Jiaxin L. Fu, and Nancy S. Pollard. Data driven grasp synthesis using shape matching and task-based pruning. IEEE Transactions on Visualization and Computer Graphics, 2007. In press. [BiBTeX]

Links

• Project page

Face Poser: Interactive Modeling of 3D Facial Expressions Using Model Priors

Manfred Lau, Jin-Xiang Chai, Ying-Qing Xu, and Heung-Yeung Shum

Abstract

In this paper, we present an intuitive interface for interactively posing 3D facial expressions. The user can create and edit facial expressions by drawing freeform strokes, or by directly dragging facial points in 2D screen space. Designing such an interface for face modeling and editing is challenging because many unnatural facial expressions might be consistent with the ambiguous user input. The system automatically learns a model prior from a prerecorded facial expression database and uses it to remove the ambiguity. We formulate the problem in a maximum a posteriori (MAP) framework by combining the prior with user-defined constraints. Maximizing the posterior allows us to generate an optimal and natural facial expression that satisfies the user-defined constraints. Our system is interactive; it is also simple and easy to use. A first-time user can learn to use the system and start creating a variety of natural face models within minutes. We evaluate the performance of our approach with cross validation tests, and by comparing with alternative techniques.

Citation

Manfred Lau, Jin-Xiang Chai, Ying-Qing Xu, and Heung-Yeung Shum. Face poser: Interactive modeling of 3d facial expressions using model priors. In 2007 ACM SIGGRAPH / Eurographics Symposium on Computer Animation, August 2007. [BiBTeX]

Links

• Project page

Feature Selection for Grasp Recognition from Optical Markers

Lillian Y. Chang, Nancy Pollard, Tom Mitchell, and Eric P. Xing

Abstract

Although the human hand is a complex biomechanical system, only a small set of features may be necessary for observation learning of functional grasp classes. We explore how to methodically select a minimal set of hand pose features from optical marker data for grasp recognition. Supervised feature selection is used to determine a reduced feature set of surface marker locations on the hand that is appropriate for grasp classification of individual hand poses. Classifiers trained on the reduced feature set of five markers retain at least 92% of the prediction accuracy of classifiers trained on a full feature set of thirty markers. The reduced model also generalizes better to new subjects. The dramatic reduction of the marker set size and the success of a linear classifier from local marker coordinates recommend optical marker techniques as a practical alternative to data glove methods for observation learning of grasping.

Citation

Lillian Y. Chang, Nancy Pollard, Tom Mitchell, and Eric P. Xing. Feature selection for grasp recognition from optical markers. In Proceedings of the 2007 IEEE/RSJ Intl. Conference on Intelligent Robots and Systems (IROS 2007), pages 2944–2950, October 2007. [BiBTeX]

Links

• Project page

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

Mohit Gupta and Srinivasa G. Narasimhan

Abstract

In this paper, we present a unified framework for reduced space modeling and rendering of dynamic and non-homogenous 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 data-driven 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.

Citation

Mohit Gupta and Srinivasa G. Narasimhan. Legendre fluids: A unified framework for analytic reduced space modeling and rendering of participating media. In 2007 ACM SIGGRAPH / Eurographics Symposium on Computer Animation, August 2007. [BiBTeX]

Links

• Project page

Many-Worlds Browsing for Control of Multibody Dynamics

Christopher D. Twigg and Doug L. James

Abstract

Animation techniques for controlling passive simulation are commonly based on an optimization paradigm: the user provides goals a priori, and sophisticated numerical methods minimize a cost function that represents these goals. Unfortunately, for multibody systems with discontinuous contact events these optimization problems can be highly nontrivial to solve, and many-hour offline optimizations, unintuitive parameters, and convergence failures can frustrate end-users and limit usage. On the other hand, users are quite adaptable, and systems which provide interactive feedback via an intuitive interface can leverage the user's own abilities to quickly produce interesting animations. However, the online computation necessary for interactivity limits scene complexity in practice. We introduce Many-Worlds Browsing, a method which circumvents these limits by exploiting the speed of multibody simulators to compute numerous example simulations in parallel (offline and online), and allow the user to browse and modify them interactively. We demonstrate intuitive interfaces through which the user can select among the examples and interactively adjust those parts of the scene that don't match his requirements. We show that using a combination of our techniques, unusual and interesting results can be generated for moderately sized scenes with under an hour of user time. Scalability is demonstrated by sampling much larger scenes using modest offline computations.

Citation

Christopher D. Twigg and Doug L. James. Many-worlds browsing for control of multibody dynamics. ACM Transactions on Graphics (SIGGRAPH 2007), 26(3), August 2007. [BiBTeX]

Links

• Project page

Near-optimal Character Animation with Continuous Control

Adrien Treuille, Yongjoon Lee, and Zoran Popović

Abstract

We present a new model for real-time character animation with multidimensional, interactive control. The underlying motion engine is data-driven, enables rapid transitions, and automatically enforces foot-skate constraints without inverse kinematics. On top of this motion space, our algorithm learns approximately optimal controllers which use a compact basis representation to guide the system through multidimensional state-goal spaces. These controllers enable real-time character animation that fluidly responds to changing user directives and environmental constraints.

Citation

Adrien Treuille, Yongjoon Lee, and Zoran Popović. Near-optimal character animation with continuous control. ACM Transactions on Graphics (SIGGRAPH 2007), 26(3), August 2007. [BiBTeX]

Links

• Project page

Photo Clip Art

Jean-François Lalonde, Derek Hoiem, Alexei A. Efros, Carsten Rother, John Winn, and Antonio Criminisi

Abstract

We present a system for inserting new objects into existing photographs by querying a vast image-based object library, precomputed using a publicly available Internet object database. The central goal is to shield the user from all of the arduous tasks typically involved in image compositing. The user is only asked to do two simple things: 1) pick a 3D location in the scene to place a new object; 2) select an object to insert using a hierarchical menu. We pose the problem of object insertion as a data-driven, 3D-based, context-sensitive object retrieval task. Instead of trying to manipulate the object to change its orientation, color distribution, etc. to fit the new image, we simply retrieve an object of a specified class that has all the required properties (camera pose, lighting, resolution, etc) from our large object library. We present new automatic algorithms for improving object segmentation and blending, estimating true 3D object size and orientation, and estimating scene lighting conditions. We also present an intuitive user interface that makes object insertion fast and simple even for the artistically challenged.

Citation

Jean-François Lalonde, Derek Hoiem, Alexei A. Efros, Carsten Rother, John Winn, and Antonio Criminisi. Photo clip art. ACM Transactions on Graphics (SIGGRAPH 2007), 26(3), August 2007. [BiBTeX]

Links

• Project page

Responsive Characters from Motion Fragments

James McCann and Nancy S. Pollard

Abstract

In game environments, animated character motion must rapidly adapt to changes in player input -- for example, if a directional signal from the player's gamepad is not incorporated into the character's trajectory immediately, the character may blithely run off a ledge. Traditional schemes for data-driven character animation lack the split-second reactivity required for this direct control; while they can be made to work, motion artifacts will result. We describe an on-line character animation controller that assembles a motion stream from short motion fragments, choosing each fragment based on current player input and the previous fragment. By adding a simple model of player behavior we are able to improve an existing reinforcement learning method for precalculating good fragment choices. We demonstrate the efficacy of our model by comparing the animation selected by our new controller to that selected by existing methods and to the optimal selection, given knowledge of the entire path. This comparison is performed over real-world data collected from a game prototype. Finally, we provide results indicating that occasional low-quality transitions between motion segments are crucial to high-quality on-line motion generation; this is an important result for others crafting animation systems for directly-controlled characters, as it argues against the common practice of transition thresholding.

Citation

James McCann and Nancy S. Pollard. Responsive characters from motion fragments. ACM Transactions on Graphics (SIGGRAPH 2007), 26(3), August 2007. [BiBTeX]

Links

• Project page

Robust estimation of dominant axis of rotation

Lillian Y. Chang and Nancy Pollard

Abstract

A simple method is developed for robustly estimating a fixed dominant axis of rotation (AoR) of anatomical joints from surface marker data. Previous approaches which assume a model of circular marker trajectories use plane-fitting to estimate the direction of the AoR. However, when there is limited joint range of motion and rotation due to a second degree of freedom, minimizing only the planar error can give poor estimates of the AoR direction. Optimizing a cost function which includes the error component within a plane, instead of only the component orthogonal to a plane, leads to improved estimates of the AoR direction for joints which exhibit additional rotational motion from a second degree of freedom. Results from synthetic data validation show the ranges of motion where the new method has lower estimation error compared to plane-fitting techniques. Estimates of the flexion-extension AoR from empirical motion capture data of the knee and index finger joints were also more anatomically plausible.

Citation

Lillian Y. Chang and Nancy Pollard. Robust estimation of dominant axis of rotation. Journal of Biomechanics, 40(12):2707–2715, 2007. [BiBTeX]

Links

• Project page

Scene Completion Using Millions of Photographs

James Hays and Alexi Efros

Abstract

What can you do with a million images? In this paper we present a new image completion algorithm powered by a huge database of photographs gathered from the Web. The algorithm patches up holes in images by finding similar image regions in the database that are not only seamless but also semantically valid. Our chief insight is that while the space of images is effectively infinite, the space of semantically differentiable scenes is actually not that large. For many image completion tasks we are able to find similar scenes which contain image fragments that will convincingly complete the image. Our algorithm is entirely data-driven, requiring no annotations or labelling by the user. Unlike existing image completion methods, our algorithm can generate a diverse set of results for each input image and we allow users to select among them. We demonstrate the superiority of our algorithm over existing image completion approaches.

Citation

James Hays and Alexi Efros. Scene completion using millions of photographs. ACM Transactions on Graphics (SIGGRAPH 2007), 26(3), August 2007. [BiBTeX]

Links

• Project page

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

Jernej Barbič and Doug L. James

Abstract

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 real-time 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.

Citation

Jernej Barbič and Doug L. James. Time-critical distributed contact for 6-dof haptic rendering of adaptively sampled reduced deformable models. In 2007 ACM SIGGRAPH / Eurographics Symposium on Computer Animation, August 2007. [BiBTeX]

Links

• Project page

Using Color Compatibility for Assessing Image Realism

Jean-François Lalonde and Alexei A. Efros

Abstract

Why does placing an object from one photograph into another often make the colors of that object suddenly look wrong? One possibility is that humans prefer distributions of colors that are often found in nature; that is, we find pleasing these color combinations that we see often. Another possibility is that humans simply prefer colors to be consistent within an image, regardless of what they are. In this paper, we explore some of these issues by studying the color statistics of a large dataset of natural images, and by looking at differences in color distribution in realistic and unrealistic images. We apply our findings to two problems: 1) classifying composite images into realistic vs. non-realistic, and 2) recoloring image regions for realistic compositing.

Citation

Jean-François Lalonde and Alexei A. Efros. Using color compatibility for assessing image realism. IEEE International Conference on Computer Vision, 2007. [BiBTeX]

Links

• Project page

Anthropomorphism influences perception of computer-animated characters' actions

Thierry Chaminade, Jessica Hodgins, and Mitsuo Kawato

Abstract

Computer-animated characters are common in popular culture and have begun to be used as experimental tools in social cognitive neurosciences. Here we investigated how appearance of these characters' influences perception of their actions. Subjects were presented with different characters animated either with motion data captured from human actors or by interpolating between poses (keyframes) designed by an animator, and were asked to categorize the motion as biological or artificial. The response bias towards 'biological', derived from the Signal Detection Theory, decreases with characters' anthropomorphism, while sensitivity is only affected by the simplest rendering style, point-light displays. fMRI showed that the response bias correlates positively with activity in the mentalizing network including left temporoparietal junction and anterior cingulate cortex, and negatively with regions sustaining motor resonance. The absence of significant effect of the characters on the brain activity suggests individual differences in the neural responses to unfamiliar artificial agents. While computer-animated characters are invaluable tools to investigate the neural bases of social cognition, further research is required to better understand how factors such as anthropomorphism affect their perception, in order to optimize their appearance for entertainment, research or therapeutic purposes.

Citation

Thierry Chaminade, Jessica Hodgins, and Mitsuo Kawato. Anthropomorphism influences perception of computer-animated characters' actions. Social Cognitive and Affective Neuroscience, May 2007. [BiBTeX]

Links

• Project page

Interactive Tensor Field Design and Visualization on Surfaces

Eugene Zhang, James Hays, and Greg Turk

Abstract

Designing tensor fields in the plane and on surfaces is a necessary task in many graphics applications, such as painterly rendering, pen-and-ink sketch of smooth surfaces, and anisotropic remeshing. In this paper, we present an interactive design system that allows a user to create a wide variety of surface tensor fields with control over the number and location of degenerate points. Our system combines basis tensor fields to make an initial tensor field that satisfies a set of userspecifications. However, such a field often contains unwanted degenerate points that cannot always be eliminated due to topological constraints of the underlying surface. To reduce the artifacts caused by these degenerate points, our system allows the user to move a degenerate point or to cancel a pair of degenerate points that have opposite tensor indices.

Citation

Eugene Zhang, James Hays, and Greg Turk. Interactive tensor field design and visualization on surfaces. IEEE Transactions on Visualization and Computer Graphics, 13(1):94–107, January 2007. [BiBTeX]

Links

• Paper (PDF, 3.22MB)

A Texture Synthesis Method for Liquid Animations

Adam W. Bargteil, Funshing Sin, Jonathan E. Michaels, Tolga G. Goktekin, and James F. O'Brien

Abstract

In this paper we present a method for synthesizing textures on animated liquid surfaces generated by a physically based fluid simulation system. Rather than advecting texture coordinates on the surface, we synthesize a new texture for every frame. We synthesize the texture with an optimization procedure which attempts to match the surface texture to an input sample texture. By synthesizing a new texture for every frame, our method is able to overcome the discontinuities and distortions of an advected parameterization. We achieve temporal coherence by initializing the surface texture with color values advected from the surface at the previous frame and including these colors in the energy function used during optimization.

Citation

Adam W. Bargteil, Funshing Sin, Jonathan E. Michaels, Tolga G. Goktekin, and James F. O'Brien. A texture synthesis method for liquid animations. In 2006 ACM SIGGRAPH / Eurographics Symposium on Computer Animation, September 2006. [BiBTeX]

Links

• Project page

Physics-Based Motion Retiming

James McCann, Nancy S. Pollard, and Siddhartha S. Srinivasa

Abstract

By changing only the playback timing of a motion sequence, an animator can achieve a variety of effects that alter our perception of an event. In some scenarios, it may be important to consider physical properties of the motion when retiming (e.g., to preserve physical plausibility). However, existing retiming solutions can be quite time consuming when physical parameters are considered. This paper presents an interactive method for creating optimal motion retimings that takes into account physically based constraints and objective functions. We achieve fast performance through a precomputation phase where constraints are projected into the two-dimensional space of velocities and accelerations along the input motion path. Unlike previous approaches, our precomputation technique allows for rapid computation of plausible contact forces that result from retiming, and it also accommodates changing physical parameters. We demonstrate our approach by creating physically plausible results for changes in motion duration, manipulations of the gravity vector, and modifications of character limb masses.

Citation

James McCann, Nancy S. Pollard, and Siddhartha S. Srinivasa. Physics-based motion retiming. In 2006 ACM SIGGRAPH / Eurographics Symposium on Computer Animation, September 2006. [BiBTeX]

Links

• Paper (PDF, 4.66MB)

Precomputed Search Trees: Planning for Interactive Goal-Driven Animation

Manfred Lau and James J. Kuffner

Abstract

We present a novel approach for interactively synthesizing motions for characters navigating in complex environments. We focus on the runtime efficiency for motion generation, thereby enabling the interactive animation of a large number of characters simultaneously. The key idea is to precompute search trees of motion clips that can be applied to arbitrary environments. Given a navigation goal relative to a current body position, the best available solution paths and motion sequences can be efficiently extracted during runtime through a series of table lookups. For distant start and goal positions, we first use a fast coarse-level planner to generate a rough path of intermediate sub-goals to guide each iteration of the runtime lookup phase. We demonstrate the efficiency of our technique across a range of examples in an interactive application with multiple autonomous characters navigating in dynamic environments. Each character responds in real-time to arbitrary user changes to the environment obstacles or navigation goals. The runtime phase is more than two orders of magnitude faster than existing planning methods or traditional motion synthesis techniques. Our technique is not only useful for autonomous motion generation in games, virtual reality, and interactive simulations, but also for animating massive crowds of characters offline for special effects in movies.

Citation

Manfred Lau and James J. Kuffner. Precomputed search trees: Planning for interactive goal-driven animation. In 2006 ACM SIGGRAPH / Eurographics Symposium on Computer Animation, pages 299–308, September 2006. [BiBTeX]

Links

• Project page

Acquiring Scattering Properties of Participating Media by Dilution

Srinivasa Narasimhan, Mohit Gupta, Craig Donner, Ravi Ramamoorthi, Shree K. Nayar, and Henrik Wann Jensen

Abstract

The visual world around us displays a rich set of volumetric effects due to participating media. The appearance of these media is governed by several physical properties such as particle densities, shapes and sizes, which must be input (directly or indirectly) to a rendering algorithm to generate realistic images. While there has been significant progress in developing rendering techniques (for instance, volumetric Monte Carlo methods and analytic approximations), there are very few methods that measure or estimate these properties for media that are of relevance to computer graphics. In this paper, we present a simple device and technique for robustly estimating the properties of a broad class of participating media that can be either (a) diluted in water such as juices, beverages, paints and cleaning supplies, or (b) dissolved in water such as powders and sugar/salt crystals, or (c) suspended in water such as impurities. The key idea is to dilute the concentrations of the media so that single scattering effects dominate and multiple scattering becomes negligible, leading to a simple and robust estimation algorithm. Furthermore, unlike previous approaches that require complicated or separate measurement setups for different types or properties of media, our method and setup can be used to measure media with a complete range of absorption and scattering properties from a single HDR photograph. Once the parameters of the diluted medium are estimated, a volumetric Monte Carlo technique may be used to create renderings of any medium concentration and with multiple scattering. We have measured the scattering parameters of forty commonly found materials, that can be immediately used by the computer graphics community. We can also create realistic images of combinations or mixtures of the original measured materials, thus giving the user a wide flexibility in making realistic images of participating media.

Citation

Srinivasa Narasimhan, Mohit Gupta, Craig Donner, Ravi Ramamoorthi, Shree K. Nayar, and Henrik Wann Jensen. Acquiring scattering properties of participating media by dilution. ACM Transactions on Graphics (SIGGRAPH 2006), 25(3), August 2006. [BiBTeX]

Links

• Project page

Capturing and Animating Skin Deformation in Human Motion

Sang Il Park and Jessica K. Hodgins

Abstract

During dynamic activities, the surface of the human body moves in many subtle but visually significant ways: bending, bulging, jiggling, and stretching. We present a technique for capturing and animating those motions using a commercial motion capture system and approximately 350 markers. Although the number of markers is significantly larger than that used in conventional motion capture, it is only a sparse representation of the true shape of the body. We supplement this sparse sample with a detailed, actor-specific surface model. The motion of the skin can then be computed by segmenting the markers into the motion of a set of rigid parts and a residual deformation (approximated first as a quadratic transformation and then with radial basis functions). We demonstrate the power of this approach by capturing flexing muscles, high frequency motions, and abrupt decelerations on several actors. We compare these results both to conventional motion capture and skinning and to synchronized video of the actors.

Citation

Sang Il Park and Jessica K. Hodgins. Capturing and animating skin deformation in human motion. ACM Transactions on Graphics (SIGGRAPH 2006), 25(3), August 2006. [BiBTeX]

Links

• Project page

Hierarchical Simplification of City Models to Maintain Urban Legibility

Remco Chang, Thomas Butkiewicz, Caroline Ziemkiewicz, Zachary Wartell, Nancy S. Pollard, and William Ribarsky

Abstract

For 3D global visualization systems such as Google Earth, it is important to be able to render city-sized collections of relatively simple building models at fast speeds without losing spatial coherence. Since traditional mesh simplification algorithms are not designed for collections of simple models, we introduce a method of simplification through merging of similar objects. We incorporate the concept of "urban legibility" from architecture and city-planning as a guideline for simplifying city models. Our algorithm can be broken down into five steps. Hierarchical clustering, cluster merging, polyline simplification, and hierarchical texturing are performed during pre-processing, while at runtime, the levels-of-detail (LOD) process selects the appropriate models to render. It is our belief that many applications can benefit from our algorithm. Google Earth (and other 3D geographical information systems) as well as any spatial data visualization applications (including scatter plots) can all use logical, simplified clusters to represent large amounts of spatial information.

Citation

Remco Chang, Thomas Butkiewicz, Caroline Ziemkiewicz, Zachary Wartell, Nancy S. Pollard, and William Ribarsky. Hierarchical simplification of city models to maintain urban legibility. In Proceedings of the SIGGRAPH 2006 Conference on Sketches & Applications. ACM Press, August 2006. [BiBTeX]

Links

• Paper (PDF, 773KB)

Mesh Ensemble Motion Graphs: Data-driven Mesh Animation with Constraints

Doug L. James, Christopher D. Twigg, Andrew Cove, and Robert Y. Wang

Abstract

We describe a technique for using space-time cuts to smoothly transition between stochastic mesh animation clips involving numerous deformable mesh groups while subject to physical constraints. These transitions are used to construct Mesh Ensemble Motion Graphs for interactive data-driven animation of high-dimensional mesh animation datasets, such as those arising from expensive physical simulations of deformable objects blowing in the wind. We formulate the transition computation as an integer programming problem, and introduce a novel randomized algorithm to compute transitions subject to geometric noninterpenetration constraints.

Citation

Doug L. James, Christopher D. Twigg, Andrew Cove, and Robert Y. Wang. Mesh ensemble motion graphs: Data-driven mesh animation with constraints. In Proceedings of the SIGGRAPH 2006 Conference on Sketches & Applications. ACM Press, August 2006. [BiBTeX]

Links

• Project page

Precomputed Acoustic Transfer: Output-sensitive, accurate sound generation for geometrically complex vibration sources

Doug L. James, Jernej Barbič, and Dinesh K. Pai

Abstract

Simulating sounds produced by realistic vibrating objects is challenging because sound radiation involves complex diffraction and interreflection effects that are very perceptible and important. These wave phenomena are well understood, but have been largely ignored in computer graphics due to the high cost and complexity of computing them at audio rates. We describe a new algorithm for real-time synthesis of realistic sound radiation from rigid objects. We start by precomputing the linear vibration modes of an object, and then relate each mode to its sound pressure field, or acoustic transfer function, using standard methods from numerical acoustics. Each transfer function is then approximated to a specified accuracy using low-order multipole sources placed near the object. We provide a low-memory, multilevel, randomized algorithm for optimized source placement that is suitable for complex geometries. At runtime, we can simulate new interaction sounds by quickly summing contributions from each modes equivalent multipole sources. We can efficiently simulate global effects such as interreflection and changes in sound due to listener location. The simulation costs can be dynamically traded-off for sound quality. We present several examples of sound generation from physically based animations.

Citation

Doug L. James, Jernej Barbič, and Dinesh K. Pai. Precomputed acoustic transfer: Output-sensitive, accurate sound generation for geometrically complex vibration sources. ACM Transactions on Graphics (SIGGRAPH 2006), 25(3), August 2006. [BiBTeX]

Links

• Project page

Continuum crowds

Adrien Treuille, Seth Cooper, and Zoran Popović

Abstract

Human crowds are ubiquitous in the real world, making their simulation a necessity for realistic interactive environments. We present a real-time crowd model based on continuum dynamics. In our model, a dynamic potential field simultaneously integrates global navigation with moving obstacles such as other people, efficiently solving for the motion of large crowds without the need for explicit collision avoidance. Simulations created with our system run at interactive rates, demonstrate smooth flow under a variety of conditions, and naturally exhibit emergent phenomena that have been observed in real crowds.

Citation

Adrien Treuille, Seth Cooper, and Zoran Popović. Continuum crowds. ACM Transactions on Graphics (SIGGRAPH 2006), 25(3):1160–1168, July 2006. [BiBTeX]

Links

• Project page

Model reduction for real-time fluids

Adrien Treuille, Andrew Lewis, and Zoran Popović

Abstract

We present a new model reduction approach to fluid simulation, enabling large, real-time, detailed flows with continuous user interaction. Our reduced model can also handle moving obstacles immersed in the flow. We create separate models for the velocity field and for each moving boundary, and show that the coupling forces may be reduced as well. Our results indicate that surprisingly few basis functions are needed to resolve small but visually important features such as spinning vortices.

Citation

Adrien Treuille, Andrew Lewis, and Zoran Popović. Model reduction for real-time fluids. ACM Transactions on Graphics (SIGGRAPH 2006), 25(3):826–834, July 2006. [BiBTeX]

Links

• Project page

Quantitative Evaluation on Near Regular Texture Synthesis

Wen-Chieh Lin, James H. Hays, Chenyu Wu, Vivek Kwatra, and Yanxi Liu

Abstract

Near regular textures are pervasive in man-made and natural world. Their global regularity and local randomness pose new difficulties to the state of the art texture analysis and synthesis algorithms. We carry out a systematic comparison study on the performance of four texture synthesis algorithms on near-regular textures. Our results confirm that faithful near-regular texture synthesis remains a challenging problem for the state of the art general purpose texture synthesis algorithms. In addition, we provide comparison of human perception with computer evaluations on the quality of the texture synthesis results.

Citation

Wen-Chieh Lin, James H. Hays, Chenyu Wu, Vivek Kwatra, and Yanxi Liu. Quantitative evaluation on near regular texture synthesis. In Computer Vision and Pattern Recognition Conference (CVPR '06), volume 1, pages 427–434, June 2006. [BiBTeX]

Links

• Paper (PDF, 796KB)

Discovering Texture Regularity as a Higher-Order Correspondence Problem

James H. Hays, Marius Leordeanu, Alexei A. Efros, and Yanxi Liu

Abstract

Understanding texture regularity in real images is a challenging computer vision task. We propose a higher-order feature matching algorithm to discover the lattices of near-regular textures in real images. The underlying lattice of a near-regular texture identifies all of the texels as well as the global topology among the texels. A key contribution of this paper is to formulate lattice-finding as a correspondence problem. The algorithm finds a plausible lattice by iteratively proposing texels and assigning neighbors between the texels. Our matching algorithm seeks assignments that maximize both pair-wise visual similarity and higher-order geometric consistency. We approximate the optimal assignment using a recently developed spectral method. We successfully discover the lattices of a diverse set of unsegmented, real-world textures with significant geometric warping and large appearance variation among texels.

Citation

James H. Hays, Marius Leordeanu, Alexei A. Efros, and Yanxi Liu. Discovering texture regularity as a higher-order correspondence problem. In 9th European Conference on Computer Vision, May 2006. [BiBTeX]

Links

• Paper (PDF, 5.09MB)

Learning Silhouette Features for Control of Human Motion

Liu Ren, Gregory Shakhnarovich, Jessica K. Hodgins, Hanspeter Pfister, and Paul Viola

Abstract

We present a vision-based performance interface for controlling animated human characters. The system combines information about the user's motion contained in silhouettes from several viewpoints with domain knowledge contained in a motion capture database to interactively produce a high quality animation. Such an interactive system will be useful for authoring, teleconferencing, or as a control interface for a character in a game. In our system, the user performs in front of three video cameras; the resulting silhouettes are used to estimate his or her orientation and body configuration based on a set of discriminative local features. Those features are selected by a machine learning algorithm during a preprocessing step. Sequences of motions that approximate the user's actions are extracted from the motion database and scaled in time to match the speed of the user's motion. We use swing dancing, an example of complex human motion, to demonstrate the effectiveness of our approach and compare the results obtained with discriminative local features to those obtained with global features, Hu moments, and to ground truth measurement from a motion capture system.

Citation

Liu Ren, Gregory Shakhnarovich, Jessica K. Hodgins, Hanspeter Pfister, and Paul Viola. Learning silhouette features for control of human motion. ACM Transactions on Graphics, 24(4), October 2005. [BiBTeX]

Links

• Project page

Oral Fixations

James Duesing, Jessica K. Hodgins, Bum Lee, Moshe Mahler, Jay Oberski, Sang Il Park, and David Tinapple

Abstract

Oral Fixations is a single channel video installation that evolves over a seven hour time period. The project is a darkly humorous look at a habit of endless consumption and the resulting accumulation of waste. A narrative gradually emerges from the on-screen action that depicts a large mouthed character who dances while flossing its one protruding tooth. A conveyor belt regularly delivers factory-farm fresh hams that the character delights in taking one large bite from and then tossing aside. Over the duration of the piece the hams begin to pile up in the room until at the end of seven hours the room is filled with the refuse of this gluttony. The viewer is encouraged to revisit the piece periodically throughout the day and see how the discarded hams build an oddly humorous environment of waste around the character.

Citation

James Duesing, Jessica K. Hodgins, Bum Lee, Moshe Mahler, Jay Oberski, Sang Il Park, and David Tinapple. Oral fixations. In SIGGRAPH '05: ACM SIGGRAPH 2005 Electronic Art and Animation Catalog, pages 118–119, New York, NY, USA, 2005. ACM Press. [BiBTeX]

Links

• Project page

A Data-Driven Approach to Quantifying Natural Human Motion

Liu Ren, Alton Patrick, Alexei A. Efros, Jessica K. Hodgins, and James M. Rehg

Abstract

In this paper, we investigate whether it is possible to develop a measure that quantifies the naturalness of human motion (as defined by a large database). Such a measure might prove useful in verifying that a motion editing operation had not destroyed the naturalness of a motion capture clip or that a synthetic motion transition was within the space of those seen in natural human motion. We present an ensemble approach to attack this problem. In our approach, we first hierarchically decompose human motion into its constituent parts (individual joints, limbs, and full body) and build a statistical model of each one using existing machine learning techniques such as mixture of Gaussians (MoG), hidden Markov models (HMM), and switching linear dynamic systems (SLDS). We then combine these models into an ensemble model for classification of the motion as natural or unnatural. We also implement a Naive Bayes (NB) model for a baseline comparison. We test these techniques on motion capture data held out from a database, keyframed motions, edited motions, motions with noise added, and synthetic motion transitions. We present the results as receiver operating characteristic (ROC) curves and compare the results to the judgments made by subjects in a user study.

Citation

Liu Ren, Alton Patrick, Alexei A. Efros, Jessica K. Hodgins, and James M. Rehg. A data-driven approach to quantifying natural human motion. ACM Transactions on Graphics (SIGGRAPH 2005), 24(3), August 2005. [BiBTeX]

Links

• Project page

A Practical Analytic Single Scattering Model for Real Time Rendering

Bo Sun, Ravi Ramamoorthi, Srinivasa Narasimhan, and Shree K. Nayar

Abstract

We consider real-time rendering of scenes in participating media, capturing the effects of light scattering in fog, mist and haze. While a number of sophisticated approaches based on Monte Carlo and finite element simulation have been developed, those methods do not work at interactive rates. The most common real-time methods are essentially simple variants of the OpenGL fog model. While easy to use and specify, that model excludes many important qualitative effects like glows around light sources, the impact of volumetric scattering on the appearance of surfaces such as the diffusing of glossy highlights, and the appearance under complex lighting such as environment maps. In this paper, we present an alternative physically based approach that captures these effects while maintaining real-time performance and the ease-of-use of the OpenGL fog model. Our method is based on an explicit analytic integration of the single scattering light transport equations for an isotropic point light source in a homogeneous participating medium. We can implement the model in modern programmable graphics hardware using a few small numerical lookup tables stored as texture maps. Our model can also be easily adapted to generate the appearances of materials with arbitrary BRDFs, environment map lighting, and precomputed radiance transfer methods, in the presence of participating media. Hence, our techniques can be widely used in real-time rendering applications.

Citation

Bo Sun, Ravi Ramamoorthi, Srinivasa Narasimhan, and Shree K. Nayar. A practical analytic single scattering model for real time rendering. ACM Transactions on Graphics (SIGGRAPH 2005), 24(3), August 2005. [BiBTeX]

Links

• Project page

Analyzing the Physical Correctness of Interpolated Human Motion

Alla Safonova and Jessica K. Hodgins

Abstract

Two human motions can be linearly interpolated to produce a new motion, giving the animator control over the length of a jump, the speed of walking, or the height of a kick. Over the past ten years, this simple technique has been shown to produce surprisingly natural looking results. In this paper, we analyze the motions produced by this technique for physical correctness and suggest small modifications to the standard interpolation technique that in some circumstances will produce significantly more natural looking motion.

Citation

Alla Safonova and Jessica K. Hodgins. Analyzing the physical correctness of interpolated human motion. In 2005 ACM SIGGRAPH / Eurographics Symposium on Computer Animation, August 2005. [BiBTeX]

Links

• Project page

Automatic Photo Pop-up

Derek Hoiem, Alexei A. Efros, and Martial Hebert

Abstract

Our system automatically constructs simple "pop-up" 3D models, like those one would find in a children's book, out of a single outdoor image. The labels each region of an outdoor image as "ground", "vertical", or "sky". Line segments fitted to the ground-vertical boundary in the image and an estimate of the horizon's position provide the necessary information to determine where to "cut" and "fold" in the image. After cutting and folding, the model is popped up, and the image is texture mapped onto the model.

Citation

Derek Hoiem, Alexei A. Efros, and Martial Hebert. Automatic photo pop-up. ACM Transactions on Graphics (SIGGRAPH 2005), 24(3), August 2005. [BiBTeX]

Links

• Project page

Behavior Planning for Character Animation

Manfred Lau and James J. Kuffner

Abstract

This paper explores a behavior planning approach to automatically generate realistic motions for animated characters. Motion clips are abstracted as high-level behaviors and associated with a behavior finite-state machine (FSM) that defines the movement capabilities of a virtual character. During runtime, motion is generated automatically by a planning algorithm that performs a global search of the FSM and computes a sequence of behaviors for the character to reach a user-designated goal position. Our technique can generate interesting animations using a relatively small amount of data, making it attractive for resource-limited game platforms. It also scales efficiently to large motion databases, because the search performance is primarily dependent on the complexity of the behavior FSM rather than on the amount of data. Heuristic cost functions that the planner uses to evaluate candidate motions provide a flexible framework from which an animator can control character preferences for certain types of behavior. We show results of synthesized animations involving up to one hundred human and animal characters planning simultaneously in both static and dynamic environments.

Citation

Manfred Lau and James J. Kuffner. Behavior planning for character animation. In 2005 ACM SIGGRAPH / Eurographics Symposium on Computer Animation, pages 271–280, August 2005. [BiBTeX]

Links

• Project page

Performance Animation from Low-dimensional Control Signals

Jinxiang Chai and Jessica K. Hodgins

Abstract

The ability to accurately reconstruct a user's motion in real time would allow the intuitive control of characters in computer games, the control of avatars for virtual reality or electronically mediated communication, and the rapid prototyping of character animations. This project introduces an approach to performance animation that employs video cameras and a small set of retro-reflective markers to create a low-cost, easy-to-use system that might someday be practical for home use. The low-dimensional control signals from the user's performance are supplemented by a database of pre-recorded human motion. At run time, the system automatically learns a series of local models from a set of motion capture examples that are a close match to the marker locations captured by the cameras. These local models are then used to reconstruct the motion of the user as a full-body animation. We demonstrate the power and flexibility of this approach by having users control six behaviors in real time without significant latency: walking, running, hopping, jumping, boxing, and Kendo (Japanese sword art). The reconstructed motion is based on a single large human motion database. Our experiments indicate that this approach scales well with the size and heterogeneity of the database and is robust to variations in kinematics between users. The resulting animation also captures the individual style of the user's motion through spatial-temporal interpolation of the data. Finally, we assess the quality of the reconstructed motion by comparing against ground truth data simultaneously captured with a full marker set in a commercial motion capture system.

Citation

Jinxiang Chai and Jessica K. Hodgins. Performance animation from low-dimensional control signals. ACM Transactions on Graphics (SIGGRAPH 2005), 24(3), August 2005. [BiBTeX]

Links

• Project page

Physically Based Grasping Control from Example

Nancy S. Pollard and Victor B. Zordan

Abstract

Animated human characters in everyday scenarios must interact with the environment using their hands. Captured human motion can provide a database of realistic examples. However, examples involving contact are difficult to edit and retarget; realism can suffer when a grasp does not appear secure or when an apparent impact does not disturb the hand or the object. Physically based simulations can preserve plausibility through simulating interaction forces. However, such physical models must be driven by a controller, and creating effective controllers for new motion tasks remains a challenge. In this project, we present a controller for physically based grasping that draws from motion capture data. Our controller explicitly includes passive and active components to uphold compliant yet controllable motion, and it adds compensation for movement of the arm and for gravity to make the behavior of passive and active components less dependent on the dynamics of arm motion. Given a set of motion capture grasp examples, our system solves for all but a small set of parameters for this controller automatically. We demonstrate results for tasks including grasping and two-hand interaction and show that a controller derived from a single motion capture example can be used to form grasps of different object geometries.

Citation

Nancy S. Pollard and Victor B. Zordan. Physically based grasping control from example. In 2005 ACM SIGGRAPH / Eurographics Symposium on Computer Animation, August 2005. [BiBTeX]

Links

• Project page

Real-Time Subspace Integration for St. Venant-Kirchhoff Deformable Models

Jernej Barbič and Doug L. James

Abstract

In this paper, we present an approach for fast subspace integration of reduced-coordinate nonlinear deformable models that is suitable for interactive applications in computer graphics and haptics. Our approach exploits dimensional model reduction to build reduced-coordinate deformable models for objects with complex geometry. We exploit the fact that model reduction on large deformation models with linear materials (as commonly used in graphics) result in internal force models that are simply cubic polynomials in reduced coordinates. Coefficients of these polynomials can be precomputed, for efficient runtime evaluation. This allows simulation of nonlinear dynamics using fast implicit Newmark subspace integrators, with subspace integration costs independent of geometric complexity. We present two useful approaches for generating low-dimensional subspace bases: modal derivatives and an interactive sketching technique. Mass-scaled principal component analysis (mass-PCA) is suggested for dimensionality reduction. Finally, several examples are given from computer animation to illustrate high performance, including force-feedback haptic rendering of a complicated object undergoing large deformations.

Citation

Jernej Barbič and Doug L. James. Real-time subspace integration for St. Venant-Kirchhoff deformable models. ACM Transactions on Graphics (SIGGRAPH 2005), 24(3):982–990, August 2005. [BiBTeX]

Links

• Project page

Skinning Mesh Animations

Doug L. James and Christopher D. Twigg

Abstract

We extend approaches for skinning characters to the general setting of skinning deformable mesh animations. We provide an automatic algorithm for generating progressive skinning approximations, that is particularly efficient for pseudo-articulated motions. Our contributions include the use of nonparametric mean shift clustering of high-dimensional mesh rotation sequences to automatically identify statistically relevant bones, and robust least squares methods to determine bone transformations, bone-vertex influence sets, and vertex weight values. We use a low-rank data reduction model defined in the undeformed mesh configuration to provide progressive convergence with a fixed number of bones. We show that the resulting skinned animations enable efficient hardware rendering, rest pose editing, and deformable collision detection. Finally, we present numerous examples where skins were automatically generated using a single set of parameter values.

Citation

Doug L. James and Christopher D. Twigg. Skinning mesh animations. ACM Transactions on Graphics (SIGGRAPH 2005), 24(3), August 2005. [BiBTeX]

Links

• Project page

Vortex Fluid for Gaseous Phenomena

Sang Il Park and Myoung Jun Kim

Abstract

In this paper, we present a method for visual simulation of gaseous phenomena based on the vortex method. Using a localized vortex flow as a basic building block, the whole flow field is described. As a result, we generate more dynamic swirling fluid flows while achieving computational efficiency by concentrating only on the localized vorticity region during the simulation. Based on the lagrangian framework, we consider various boundary conditions. By exploiting the panel method, we satisfy the no-through boundary condition in a Lagrangian way. A simple and effective way of handling the no-slip boundary condition is also presented. In treating the no-slip boundary condition, we allow a user to assign the roughness of the boundary surface, which further improves visual realism.

Citation

Sang Il Park and Myoung Jun Kim. Vortex fluid for gaseous phenomena. In 2005 ACM SIGGRAPH / Eurographics Symposium on Computer Animation, August 2005. [BiBTeX]

Links

• Project page

Hardware-Accelerated Adaptive EWA Volume Splatting

Wei Chen, Liu Ren, Matthias Zwicker, and Hanspeter Pfister

Abstract

we present a hardware-accelerated adaptive EWA(elliptical weighted average) volume splatting algorithm. EWA splatting combines a Gaussian reconstruction kernel with a low-pass image filter for high image quality without aliasing artifacts or excessive blurring. We introduce a novel adaptive filtering scheme to reduce the computational cost of EWA splatting. We show how this algorithm can be efficiently implemented on modern graphics processing units (GPUs). Our implementation includes interactive classification and fast lighting. To accelerate the rendering we store splat geometry and 3D volume data locally in GPU memory. We present results for several rectilinear volume datasets that demonstrate the high image quality and interactive rendering speed of our method.

Citation

Wei Chen, Liu Ren, Matthias Zwicker, and Hanspeter Pfister. Hardware-accelerated adaptive EWA volume splatting. In Proceedings of IEEE Visualization 2004, October 2004. [BiBTeX]

Links

• Project page

Autonomous Behaviors for Interactive Vehicle Animations

Jared Go, Thuc Vu, and James J. Kuffner

Abstract

We present a method for synthesizing animations of autonomous space, water, and land-based vehicles in games or other interactive simulations. Controlling the motion of such vehicles to achieve a desirable behavior is difficult due to the constraints imposed by the system dynamics. We combine real-time path planning and a simplified physics model to automatically compute control actions to drive a vehicle from an input state to desirable output states based on a behavior cost function. Both offline trajectory preprocessing and online search are used to build an animation framework suitable for interactive vehicle simulations. We demonstrate synthesized animations of spacecraft performing a variety of autonomous behaviors, including Seek, Pursue, Avoid, Avoid Collision, and Flee. We also explore several enhancements to the basic planning algorithm and examine the resulting tradeoffs in runtime performance and quality of the generated motion.

Citation

Jared Go, Thuc Vu, and James J. Kuffner. Autonomous behaviors for interactive vehicle animations. In 2004 ACM SIGGRAPH / Eurographics Symposium on Computer Animation, August 2004. [BiBTeX]

Links

• Project page

Evaluating Motion Graphs for Character Navigation

Paul S. A. Reitsma and Nancy S. Pollard

Abstract

Realistic and directable humanlike characters are an ongoing goal in animation. Motion graph data structures hold much promise for achieving this goal. However, the quality of the results obtained from a motion graph may not be easy to predict from the input motion segments. This paper introduces the idea of assessing a data structure such as a motion graph for its utility in a particular application. We focus on navigation tasks and define metrics for evaluating expected path quality and coverage for a given environment. One key to evaluating a motion graph for navigation tasks is to first embed it into the environment in a way that captures all possible paths that might result from playing back the motion graph within that environment. This paper describes an algorithm for accomplishing this embedding that preserves the flexibility of the original motion graph. We use the metrics defined in this paper to compare motion datasets and to highlight areas where these datasets could be improved.

Citation

Paul S. A. Reitsma and Nancy S. Pollard. Evaluating motion graphs for character navigation. In 2004 ACM SIGGRAPH / Eurographics Symposium on Computer Animation, August 2004. [BiBTeX]

Links

• Project page

Flow-based Video Synthesis and Editing

Kiran S. Bhat, Steven M. Seitz, Jessica K. Hodgins, and Pradeep K. Khosla

Abstract

This paper presents a novel algorithm for synthesizing and editing video of natural phenomena that exhibit continuous flow patterns. The algorithm analyzes the motion of textured particles in the input video along user-specified flow lines, and synthesizes seamless video of arbitrary length by enforcing temporal continuity along a second set of user-specified flow lines. The algorithm is simple to implement and use. We used this technique to edit video of waterfalls, rivers, flames, and smoke.

Citation

Kiran S. Bhat, Steven M. Seitz, Jessica K. Hodgins, and Pradeep K. Khosla. Flow-based video synthesis and editing. ACM Transactions on Graphics (SIGGRAPH 2004), 23(3), August 2004. [BiBTeX]

Links

• Project page

Fluid Control Using the Adjoint Method

Antoine McNamara, Adrien Treuille, Zoran Popović, and Jos Stam

Abstract

We describe a novel method for controlling physics-based fluid simulations through gradient-based nonlinear optimization. Using a technique known as the adjoint method, derivatives can be computed efficiently, even for large 3D simulations with millions of control parameters. In addition, we introduce the first method for the full control of free-surface liquids. We show how to compute adjoint derivatives through each step of the simulation, including the fast marching algorithm, and describe a new set of control parameters specifically designed for liquids.

Citation

Antoine McNamara, Adrien Treuille, Zoran Popović, and Jos Stam. Fluid control using the adjoint method. ACM Transactions on Graphics (SIGGRAPH 2004), 23(3), August 2004. [BiBTeX]

Links

• Project page

Learning Silhouette Features for Control of Human Motion

Liu Ren, Gregory Shakhnarovich, Jessica K. Hodgins, Hanspeter Pfister, and Paul Viola

Abstract

We present a vision-based performance interface for controlling animated human characters. The system combines information about the user's motion contained in silhouettes from several viewpoints with domain knowledge contained in a motion capture database to interactively produce a high quality animation. Such an interactive system will be useful for authoring, teleconferencing, or as a control interface for a character in a game. In our system, the user performs in front of three video cameras; the resulting silhouettes are used to estimate his or her orientation and body configuration based on a set of discriminative local features. Those features are selected by a machine learning algorithm during a preprocessing step. Sequences of motions that approximate the user's actions are extracted from the motion database and scaled in time to match the speed of the user's motion. We use swing dancing, an example of complex human motion, to demonstrate the effectiveness of our approach and compare the results obtained with discriminative local features to those obtained with global features, Hu moments, and to ground truth measurement from a motion capture system.

Citation

Liu Ren, Gregory Shakhnarovich, Jessica K. Hodgins, Hanspeter Pfister, and Paul Viola. Learning silhouette features for control of human motion. In Proceedings of the SIGGRAPH 2004 Conference on Sketches & Applications. ACM Press, August 2004. [BiBTeX]

Links

• Project page

Markerless Human Motion Transfer

German Cheung, Simon Baker, Jessica K. Hodgins, and Takeo Kanade

Citation

German Cheung, Simon Baker, Jessica K. Hodgins, and Takeo Kanade. Markerless human motion transfer. In Proceedings of the SIGGRAPH 2004 Conference on Sketches & Applications. ACM Press, August 2004. [BiBTeX]

Near-Regular Texture Analysis and Manipulation

Yanxi Liu, Wen-Chieh Lin, and James Hays

Abstract

A near-regular texture deviates geometrically and photometrically from a regular congruent tiling. Although near-regular textures are ubiquitous in the man-made and natural world, they present computational challenges for state of the art texture analysis and synthesis algorithms. Using regular tiling as our anchor point, and with user-assisted lattice extraction, we can explicitly model the deformation of a near-regular texture with respect to geometry, lighting and color. We treat a deformation field both as a function that acts on a texture and as a texture that is acted upon, and develop a multimodal framework where each deformation field is subject to analysis, synthesis and manipulation. Using this formalization, we are able to construct simple parametric models to faithfully synthesize the appearance of a near-regular texture and purposefully control its regularity.

Citation

Yanxi Liu, Wen-Chieh Lin, and James Hays. Near-regular texture analysis and manipulation. ACM Transactions on Graphics (SIGGRAPH 2004), 23(3), August 2004. [BiBTeX]

Links

• Project page

Squashing Cubes: Automating Deformable Model Construction for Graphics

Doug L. James, Jernej Barbič, and Christopher D. Twigg

Abstract

The vast majority of geometric meshes used in computer graphics are optimized for rendering, and not deformable object simulation. Despite tools for volume (or surface) (re)meshing of geometric models to support physical simulation, in practice, the construction of physically based deformable models from arbitrary graphical models remains a tedious process for animators. Squashing Cubes automates the construction of physically based deformable objects from arbitrary geometric models. During preprocess, the geometric model (typically a surface mesh) is voxelized into tiny elastic cubes, i.e., the (squashing cubes model). Second, a generic deformable object simulator is used to deform the squashing cubes model. Finally, the resulting deformations are interpolated back onto the original model, thus producing the final animation.

Citation

Doug L. James, Jernej Barbič, and Christopher D. Twigg. Squashing cubes: Automating deformable model construction for graphics. In Proceedings of the SIGGRAPH 2004 Conference on Sketches & Applications. ACM Press, August 2004. [BiBTeX]

Links

• Project page

Synthesizing Animations of Human Manipulation Tasks

Katsu Yamane, James J. Kuffner, and Jessica K. Hodgins

Abstract

Even such simple tasks as placing a box on a shelf are difficult to animate, because the animator must carefully position the character to satisfy geometric and balance constraints while creating motion to perform the task with a natural-looking style. In this paper, we explore an approach for animating characters manipulating objects that combines the power of path planning with the domain knowledge inherent in data-driven, constraint-based inverse kinematics. A path planner is used to find a motion for the object such that the corresponding poses of the character satisfy geometric, kinematic, and posture constraints. The inverse kinematics computation of the character's pose resolves redundancy by biasing the solution toward natural-looking poses extracted from a database of captured motions. Having this database greatly helps to increase the quality of the output motion. The computed path is converted to a motion trajectory using a model of the velocity profile. We demonstrate the effectiveness of the algorithm by generating animations across a wide range of scenarios that cover variations in the geometric, kinematic, and dynamic models of the character, the manipulated object, and obstacles in the scene.

Citation

Katsu Yamane, James J. Kuffner, and Jessica K. Hodgins. Synthesizing animations of human manipulation tasks. ACM Transactions on Graphics (SIGGRAPH 2004), 23(3), August 2004. [BiBTeX]

Links

• Project page

Synthesizing Physically Realistic Human Motion in Low-Dimensional, Behavior-Specific Spaces

Alla Safonova, Jessica K. Hodgins, and Nancy S. Pollard

Abstract

Optimization is an appealing way to compute the motion of an animated character because it allows the user to specify the desired motion in a sparse, intuitive way. The difficulty of solving this problem for complex characters such as humans is due in part to the high dimensionality of the search space. The dimensionality is an artifact of the problem representation because most dynamic human behaviors are intrinsically low dimensional with, for example, legs and arms operating in a coordinated way. We describe a method that exploits this observation to create an optimization problem that is easier to solve. Our method utilizes an existing motion capture database to find a low-dimensional space that captures the properties of the desired behavior. We show that when the optimization problem is solved within this low-dimensional subspace, a sparse sketch can be used as an initial guess and full physics constraints can be enabled. We demonstrate the power of our approach with examples of forward, vertical, and turning jumps; with running and walking; and with several acrobatic flips.

Citation

Alla Safonova, Jessica K. Hodgins, and Nancy S. Pollard. Synthesizing physically realistic human motion in low-dimensional, behavior-specific spaces. ACM Transactions on Graphics (SIGGRAPH 2004), 23(3), August 2004. [BiBTeX]

Links

• Project page

Team Teaching Animation Art and Technology

James Duesing and Jessica K. Hodgins

Abstract

In this paper we report on an interdisciplinary course, "Animation Art and Technology," which we have taught for the past two years at Carnegie Mellon University. Faculty and teaching assistants from computer science and art teach the class as a team and the students are an interdisciplinary mix. This class is a project-based course in which teams of students produce 4-5 animations. Most of the animations have a substantive technical component and the students are challenged to consider innovation with content to be equal with the technical. In this paper, we describe the structure of the class and assess the elements that have worked well and those that require improvement.

Citation

James Duesing and Jessica K. Hodgins. Team teaching animation art and technology. In Educators Program from the 31st Annual Conference on Computer Graphics and Interactive Techniques. ACM Press, August 2004. [BiBTeX]

Links

• Paper (PDF, 3.14MB)

BD-Tree: Output-Sensitive Collision Detection for Reduced Deformable Models

Doug L. James and Dinesh K. Pai

Abstract

We introduce the Bounded Deformation Tree, or BD-Tree, which can perform collision detection with reduced deformable models at costs comparable to collision detection with rigid objects. Reduced deformable models represent complex deformations as linear superpositions of arbitary displacement fields, and are used in a variety of applications of interactive computer graphics. The BD-Tree is a bounding sphere hierarchy for output-sensitive collision detection with such models. Its bounding spheres can be updated after deformation in any order, and at a cost independent of the geometric complexity of the model; in fact the cost can be as low as one multiplication and addition per tested sphere, and at most linear in the number reduced deformation coordinates. We show that the BD-Tree is also extremely simple to implement, and performs well in practice for a variety of real-time and complex off-line deformable simulation examples.

Citation

Doug L. James and Dinesh K. Pai. BD-Tree: Output-sensitive collision detection for reduced deformable models. ACM Transactions on Graphics (SIGGRAPH 2004), 23(3), August 2004. [BiBTeX]

Links

• Project page

Modeling Physical Variability for Synthetic MOUT Agents

Gita Sukthankar, Michael Mandel, Katia Sycara, and Jessica K. Hodgins

Abstract

Generating behavioral variability is an important prerequisite in the development of synthetic MOUT (Military Operations in Urban Terrain) agents for military simulations. Agents that lack variability are predictable and ineffective as opponents and teammates for human trainees. Along with cognitive differences, physical differences contribute towards behavioral variability. In this paper, we describe a novel method for modeling physical variability in MOUT soldiers using motion capture data acquired from human subjects. Motion capture data is commonly used to create animated characters since it retains the nuances of the original human movement. We build a cost model over the space of agent actions by creating and stochastically sampling motion graphs constructed from human data. Our results demonstrate how different cost models can induce variable behavior that remains consistent with military doctrine.

Citation

Gita Sukthankar, Michael Mandel, Katia Sycara, and Jessica K. Hodgins. Modeling physical variability for synthetic mout agents. In Proceedings of 2004 Conference on Behavior Representation in Modeling and Simulation, May 2004. [BiBTeX]

Links

Segmenting Motion Capture Data into Distinct Behaviors

Jernej Barbič, Alla Safonova, Jia-Yu Pan, Christos Faloutsos, Jessica K. Hodgins, and Nancy S. Pollard

Abstract

Much of the motion capture data used in animations, commercials, and video games is carefully segmented into distinct motions either at the time of capture or by hand after the capture session. As we move toward collecting more and longer motion sequences, however, automatic segmentation techniques will become important for processing the results in a reasonable time frame. We have found that straightforward, easy to implement segmentation techniques can be very effective for segmenting motion sequences into distinct behaviors. In this paper, we present three approaches for automatic segmentation. The first two approaches are online, meaning that the algorithm traverses the motion from beginning to end, creating the segmentation as it proceeds. The first assigns a cut when the intrinsic dimensionality of a local model of the motion suddenly increases. The second places a cut when the distribution of poses is observed to change. The third approach is a batch process and segments the sequence where consecutive frames belong to different elements of a Gaussian mixture model. We assess these three methods on fourteen motion sequences and compare the performance of the automatic methods to that of transitions selected manually.

Citation

Jernej Barbič, Alla Safonova, Jia-Yu Pan, Christos Faloutsos, Jessica K. Hodgins, and Nancy S. Pollard. Segmenting Motion Capture Data into Distinct Behaviors. In Proceedings of Graphics Interface 2004, pages 185–194, May 2004. [BiBTeX]

Links

• Project page

Example-Based Stereo with General BRDFs

Adrien Treuille, Aaron Hertzmann, and Steve Seitz

Abstract

This paper presents an algorithm for voxel-based reconstruction of objects with general reflectance properties from multiple calibrated views. It is assumed that one or more reference objects with known geometry are imaged under the same lighting and camera conditions as the object being reconstructed. The unknown object is reconstructed using a radiance basis inferred from the reference objects. Each view may have arbitrary, unknown distant lighting. If the lighting is calibrated, our model also takes into account shadows that the object casts upon itself. To our knowledge, this is the first stereo method to handle general, unknown, spatially-varying BRDFs under possibly varying, distant lighting, and shadows. We demonstrate our algorithm by recovering geometry and surface normals for objects with both uniform and spatially-varying BRDFs. The normals reveal fine-scale surface detail, allowing much richer renderings than the voxel geometry alone.

Citation

Adrien Treuille, Aaron Hertzmann, and Steve Seitz. Example-based stereo with general brdfs. In 8th European Conference on Computer Vision (ECCV 2002), May 2004. [BiBTeX]

Links

• Project page

Efficient Synthesis of Physically Valid Human Motion

Anthony C. Fang and Nancy S. Pollard

Abstract

Optimization is a promising way to generate new animations from a minimal amount of input data. Physically based optimization techniques, however, are difficult to scale to complex animated characters, in part because evaluating and differentiating physical quantities becomes prohibitively slow. Traditional approaches often require optimizing or constraining parameters involving joint torques; obtaining first derivatives for these parameters is generally an O(D²) process, where D is the number of degrees of freedom of the character. In this paper, we describe a set of objective functions and constraints that lead to linear time analytical first derivatives. The surprising finding is that this set includes constraints on physical validity, such as ground contact constraints. Considering only constraints and objective functions that lead to linear time first derivatives results in fast per-iteration computation times and an optimization problem that appears to scale well to more complex characters. We show that qualities such as squash-and-stretch that are expected from physically based optimization result from our approach. Our animation system is particularly useful for synthesizing highly dynamic motions, and we show examples of swinging and leaping motions for characters having from 7 to 22 degrees of freedom.

Citation

Anthony C. Fang and Nancy S. Pollard. Efficient synthesis of physically valid human motion. ACM Transactions on Graphics (SIGGRAPH 2003), 22(3):417–426, July 2003. [BiBTeX]

Links

• Project page

Estimating Cloth Simulation Parameters from Video

Kiran S. Bhat, Christopher D. Twigg, Jessica K. Hodgins, Pradeep K. Khosla, Zoran Popović, and Steven M. Seitz

Abstract

Cloth simulations are notoriously difficult to tune due to the many parameters that must be adjusted to achieve the look of a particular fabric. In this paper, we present an algorithm for estimating the parameters of a cloth simulation from video data of real fabric. A perceptually motivated metric based on matching between folds is used to compare video of real cloth with simulation. This metric compares two video sequences of cloth and returns a number that measures the differences in their folds. Simulated annealing is used to minimize the frame by frame error between the metric for a given simulation and the real-world footage. To estimate all the cloth parameters, we identify simple static and dynamic calibration experiments that use small swatches of the fabric. To demonstrate the power of this approach, we use our algorithm to find the parameters for four different fabrics. We show the match between the video footage and simulated motion on the calibration experiments, on new video sequences for the swatches, and on a simulation of a full skirt.

Citation

Kiran S. Bhat, Christopher D. Twigg, Jessica K. Hodgins, Pradeep K. Khosla, Zoran Popović, and Steven M. Seitz. Estimating cloth simulation parameters from video. In 2003 ACM SIGGRAPH / Eurographics Symposium on Computer Animation, pages 37–51, July 2003. [BiBTeX]

Links

• Project page

Keyframe Control of Smoke Simulations

Adrien Treuille, Antoine McNamara, Zoran Popović, and Jos Stam

Abstract

We describe a method for controlling smoke simulations through user-specified keyframes. To achieve the desired behavior, a continuous quasi-Newton optimization solves for appropriate "wind" forces to be applied to the underlying velocity field throughout the simulation. The cornerstone of our approach is a method to efficiently compute exact derivatives through the steps of a fluid simulation. We formulate an objective function corresponding to how well a simulation matches the user's keyframes, and use the derivatives to solve for force parameters that minimize this function. For animations with several keyframes, we present a novel multiple-shooting approach. By splitting large problems into smaller overlapping subproblems, we greatly speed up the optimization process while avoiding certain local minima.

Citation

Adrien Treuille, Antoine McNamara, Zoran Popović, and Jos Stam. Keyframe control of smoke simulations. ACM Transactions on Graphics (SIGGRAPH 2003), 22(3):716–723, July 2003. [BiBTeX]

Links

• Project page

Perceptual Metrics for Character Animation: Sensitivity to Errors in Ballistic Motion

Paul S. A. Reitsma and Nancy S. Pollard

Abstract

Motion capture data and techniques for blending, editing, and sequencing that data can produce rich, realistic character animation; however, the output of these motion processing techniques sometimes appears unnatural. For example, the motion may violate physical laws or reflect unreasonable forces from the character or the environment. While problems such as these can be fixed, doing so is not yet feasible in real time environments. We are interested in developing ways to estimate perceived error in animated human motion so that the output quality of motion processing techniques can be better controlled to meet user goals. This paper presents results of a study of user sensitivity to errors in animated human motion. Errors were systematically added to human jumping motion, and the ability of subjects to detect these errors was measured. We found that users were able to detect motion with errors, and noted some interesting trends: errors in horizontal velocity were easier to detect than errors in vertical velocity, and added accelerations were easier to detect than added decelerations. On the basis of our results, we propose a perceptually based metric for measuring errors in ballistic human motion.

Citation

Paul S. A. Reitsma and Nancy S. Pollard. Perceptual metrics for character animation: Sensitivity to errors in ballistic motion. ACM Transactions on Graphics (SIGGRAPH 2003), 22(3):537–542, July 2003. [BiBTeX]

Links

• Project page

Precomputing Interactive Dynamic Deformable Scenes

Doug L. James and Kayvon Fatahalian

Abstract

We present an approach for precomputing data-driven models of interactive physically based deformable scenes. The method permits real-time hardware synthesis of nonlinear deformation dynamics, including self-contact and global illumination effects, and supports real-time user interaction. We use data-driven tabulation of the system's deterministic state space dynamics, and model reduction to build efficient low-rank parameterizations of the deformed shapes. To support runtime interaction, we also tabulate impulse response functions for a palette of external excitations. Although our approach simulates particular systems under very particular interaction conditions, it has several advantages. First, parameterizing all possible scene deformations enables us to precompute novel reduced coparameterizations of global scene illumination for low-frequency lighting conditions. Second, because the deformation dynamics are precomputed and parameterized as a whole, collisions are resolved within the scene during precomputation so that runtime self-collision handling is implicit. Optionally, the data-driven models can be synthesized on programmable graphics hardware, leaving only the low-dimensional state space dynamics and appearance data models to be computed by the main CPU.

Citation

Doug L. James and Kayvon Fatahalian. Precomputing interactive dynamic deformable scenes. ACM Transactions on Graphics (SIGGRAPH 2003), 22(3):879–887, July 2003. [BiBTeX]

Links

• Paper (PDF, 10.5MB)
• Video (AVI, 13.8MB)

Vision-based Control of 3D Facial Animation

Jinxiang Chai, Jing Xiao, and Jessica K. Hodgins

Abstract

Controlling and animating the facial expression of a computer-generated 3D character is a difficult problem because the face has many degrees of freedom while most available input devices have few. In this paper, we show that a rich set of lifelike facial actions can be created from a preprocessed motion capture database and that a user can control these actions by acting out the desired motions in front of a video camera. We develop a real-time facial tracking system to extract a small set of animation control parameters from video. Because of the nature of video data, these parameters may be noisy, low-resolution, and contain errors. The system uses the knowledge embedded in motion capture data to translate these low-quality 2D animation control signals into high-quality 3D facial expressions. To adapt the synthesized motion to a new character model, we introduce an efficient expression retargeting technique whose run-time computation is constant independent of the complexity of the character model. We demonstrate the power of this approach through two users who control and animate a wide range of 3D facial expressions of different avatars.

Citation

Jinxiang Chai, Jing Xiao, and Jessica K. Hodgins. Vision-based control of 3d facial animation. In 2003 ACM SIGGRAPH / Eurographics Symposium on Computer Animation, jul 2003. [BiBTeX]

Links

• Project page

Object Space EWA Surface Splatting: A Hardware Accelerated Approach to High Quality Point Rendering

Liu Ren, Hanspeter Pfister, and Matthias Zwicker

Abstract

Elliptical weighted average (EWA) surface splatting is a technique for high quality rendering of point-sampled 3D objects. EWA surface splatting renders water-tight surfaces of complex point models with high quality, anisotropic texture filtering. In this paper we introduce a new multi-pass approach to perform EWA surface splatting on modern PC graphics hardware, called object space EWA splatting. We derive an object space formulation of the EWA filter, which is amenable for acceleration by conventional triangle-based graphics hardware. We describe how to implement the object space EWA filter using a two pass rendering algorithm. In the first rendering pass, visibility splatting is performed by shifting opaque surfel polygons backward along the viewing rays, while in the second rendering pass view-dependent EWA prefiltering is performed by deforming texture mapped surfel polygons. We use texture mapping and alpha blending to facilitate the splatting process. We implement our algorithm using programmable vertex and pixel shaders, fully exploiting the capabilities of today's graphics processing units (GPUs).

Citation

Liu Ren, Hanspeter Pfister, and Matthias Zwicker. Object space EWA surface splatting: A hardware accelerated approach to high quality point rendering. In Computer Graphics Forum (Eurographics 2002), volume 21, September 2002. [BiBTeX]

Links

• Project page

Creating Models of Truss Structures with Optimization

Jeffrey Smith, Jessica K. Hodgins, Irving Oppenheim, and Andrew Witkin

Abstract

We present a method for designing truss structures, a common and complex category of buildings, using non-linear optimization. Truss structures are ubiquitous in the industrialized world, appearing as bridges, towers, roof supports and building exoskeletons, yet are complex enough that modeling them by hand is time consuming and tedious. We represent trusses as a set of rigid bars connected by pin joints, which may change location during optimization. By including the location of the joints as well as the strength of individual beams in our design variables, we can simultaneously optimize the geometry and the mass of structures. We present the details of our technique together with examples illustrating its use, including comparisons with real structures.

Citation

Jeffrey Smith, Jessica K. Hodgins, Irving Oppenheim, and Andrew Witkin. Creating models of truss structures with optimization. ACM Transactions on Graphics (SIGGRAPH 2002), 21(3):295–301, July 2002. [BiBTeX]

Graphical Modeling and Animation of Ductile Fracture

James F. O'Brien, Adam W. Bargteil, and Jessica K. Hodgins

Abstract

In this paper, we describe a method for realistically animating ductile fracture in common solid materials such as plastics and metals. The effects that characterize ductile fracture occur due to interaction between plastic yielding and the fracture process. By modeling this interaction, our ductile fracture method can generate realistic motion for a much wider range of materials than could be realized with a purely brittle model. This method directly extends our prior work on brittle fracture [O'Brien and Hodgins, SIGGRAPH 99]. We show that adapting that method to ductile as well as brittle materials requires only a simple to implement modification that is computationally inexpensive. This paper describes this modification and presents results demonstrating some of the effects that may be realized with it.

Citation

James F. O'Brien, Adam W. Bargteil, and Jessica K. Hodgins. Graphical modeling and animation of ductile fracture. ACM Transactions on Graphics (SIGGRAPH 2002), 21(3):291–294, July 2002. [BiBTeX]

Links

• Project page

Interactive Control of Avatars Animated With Human Motion Data

Jehee Lee, Jinxiang Chai, Paul S. A. Reitsma, Jessica K. Hodgins, and Nancy S. Pollard

Abstract

Real-time control of three-dimensional avatars is an important problem in the context of computer games and virtual environments. Avatar animation and control is difficult, however, because a large repertoire of avatar behaviors must be made available, and the user must be able to select from this set of behaviors, possibly with a low-dimensional input device. One appealing approach to obtaining a rich set of avatar behaviors is to collect an extended, unlabeled sequence of motion data appropriate to the application. In this paper, we show that such a motion database can be preprocessed for flexibility in behavior and efficient search and exploited for real-time avatar control. Flexibility is created by identifying plausible transitions between motion segments, and efficient search through the resulting graph structure is obtained through clustering. Three interface techniques are demonstrated for controlling avatar motion using this data structure: the user selects from a set of available choices, sketches a path through an environment, or acts out a desired motion in front of a video camera. We demonstrate the flexibility of the approach through four different applications and compare the avatar motion to directly recorded human motion.

Citation

Jehee Lee, Jinxiang Chai, Paul S. A. Reitsma, Jessica K. Hodgins, and Nancy S. Pollard. Interactive control of avatars animated with human motion data. ACM Transactions on Graphics (SIGGRAPH 2002), 21(3):491–500, July 2002. [BiBTeX]

Links

• Project page

Motion Capture-Driven Simulations that Hit and React

Victor B. Zordan and Jessica K. Hodgins

Abstract

Controllable, reactive human motion is essential in many video games and training environments. Characters in these applications often perform tasks based on modified motion data, but response to unpredicted events is also important in order to maintain realism. We approach the problem of motion synthesis for interactive, humanlike characters by combining dynamic simulation and human motion capture data. Our control systems use trajectory tracking to follow motion capture data and a balance controller to keep the character upright while modifying sequences from a small motion library to accomplish specified tasks, such as throwing punches or swinging a racket. The system reacts to forces computed from a physical collision model by changing stiffness and damping terms. The freestanding, simulated humans respond automatically to impacts and smoothly return to tracking. We compare the resulting motion with video and recorded human data.

Citation

Victor B. Zordan and Jessica K. Hodgins. Motion capture-driven simulations that hit and react. In Proceedings of the 2002 ACM SIGGRAPH / Eurographics Symposium on Computer animation, pages 89–96. ACM Press, 2002. [BiBTeX]

Simulation Level of Detail for Multiagent Control

David C. Brogan and Jessica K. Hodgins

Abstract

Many classes of applications require multiagent navigation control algorithms to specify the movements and actions of heterogeneous groups containing thousands of characters. The scale and complexity of these interacting character groups require navigation control algorithms that are both generalizable and specifically tuned to particular character platforms. We propose a technique called simulation level of detail (LOD) that provides a simulation-based interface between navigation control algorithms and the specific mobile characters on which they operate. A simulation LOD efficiently models a character's ability to move given its dynamic state and provides this simplified version of the character to navigation controllers for use in run-time search algorithms that compute locomotion actions. We develop our simulation LOD algorithms on groups of physically simulated human and alien bicyclists and demonstrate reusable controllers that provide improvements in path following and herding tasks.

Citation

David C. Brogan and Jessica K. Hodgins. Simulation level of detail for multiagent control. In Proceedings of the First International Joint Conference on Autonomous Agents and Multiagent Systems, pages 199–206. ACM Press, 2002. [BiBTeX]

Computing the Physical Parameters of Rigid-Body Motion from Video

Kiran S. Bhat, Steven M. Seitz, Jovan Popović, and P. K. Khosla

Abstract

This paper presents an optimization framework for estimating the motion and underlying physical parameters of a rigid body in free flight from video. The algorithm takes a video clip of a tumbling rigid body of known shape and generates a physical simulation of the object observed in the video clip. This solution is found by optimizing the simulation parameters to best match the motion observed in the video sequence. These simulation parameters include initial positions and velocities, environment parameters like gravity direction and parameters of the camera. A global objective function computes the sum squared difference between the silhouette of the object in simulation and the silhouette obtained from video at each frame. Applications include creating interesting rigid body animations, tracking complex rigid body motions in video and estimating camera parameters from video.

Citation

Kiran S. Bhat, Steven M. Seitz, Jovan Popović, and P. K. Khosla. Computing the physical parameters of rigid-body motion from video. In 7th European Conference on Computer Vision (ECCV 2002) (Part I), pages 551–565, May 2002. [BiBTeX]

Links

• Project page

Fast and Controllable Simulation of the Shattering of Brittle Objects

Jeffrey Smith, Andrew Witkin, and David Baraff

Abstract

We present a method for the rapid and controllable simulation of the shattering of brittle objects under impact. An object is represented as a set of point masses connected by distance-preserving linear constraints. This use of constraints, rather than stiff springs, gains us a significant advantage in speed while still retaining fine control over the fracturing behavior. The forces exerted by these constraints during impact are computed using Lagrange multipliers. These constraint forces are then used to determine when and where the object will break, and to calculate the velocities of the newly created fragments. We present the details of our technique together with examples illustrating its use.

Citation

Jeffrey Smith, Andrew Witkin, and David Baraff. Fast and controllable simulation of the shattering of brittle objects. Computer Graphics Forum, 20(2):81–91, 2001. [BiBTeX]

Animating Athletic Motion Planning By Example

Ronald Metoyer and Jessica K. Hodgins

Citation

Ronald Metoyer and Jessica K. Hodgins. Animating athletic motion planning by example. In Graphics Interface, pages 61–68, 2000. [BiBTeX]

Links

Automatic Joint Parameter Estimation from Magnetic Motion Capture Data

James F. O'Brien, Robert Bodenheimer, Gabriel Brostow, and Jessica K. Hodgins

Citation

James F. O'Brien, Robert Bodenheimer, Gabriel Brostow, and Jessica K. Hodgins. Automatic joint parameter estimation from magnetic motion capture data. In Graphics Interface, pages 53–60, 2000. [BiBTeX]

Links

• Project page

Combining Active and Passive Simulations for Secondary Motion

James F. O'Brien, Victor B. Zordan, and Jessica K. Hodgins

Abstract

Objects that move in response to the actions of a main character often make an important contribution to the visual richness of an animated scene. We use the term "secondary motion" to refer to passive motions generated in response to the movements of characters and other objects or environmental forces. Secondary motions aren't normally the mail focus of an animated scene, yet their absence can distract or disturb the viewer, destroying the illusion of reality created by the scene. We describe how to generate secondary motion by coupling physically based simulations of passive objects to actively controlled characters.

Citation

James F. O'Brien, Victor B. Zordan, and Jessica K. Hodgins. Combining active and passive simulations for secondary motion. IEEE Computer Graphics & Applications, 20(4):86–96, August 2000. [BiBTeX]

Links

Animating Explosions

Gary D. Yngve, James F. O'Brien, and Jessica K. Hodgins

Abstract

In this paper, we introduce techniques for animating explosions and their effects. The primary effect of an explosion is a disturbance that causes a shock wave to propagate through the surrounding medium. The disturbance determines the behavior of nearly all other secondary effects seen in explosion. We simulate the propagation of an explosion through the surrounding air using a computational fluid dynamics model based on the equations for compressible, viscous flow. To model the numerically stable formation of shocks along blast wave fronts, we employ an integration method that can handle steep pressure gradients without introducing inappropriate damping. The system includes two-way coupling between solid objects and surrounding fluid. Using this technique, we can generate a variety of effects including shaped explosive charges, a projectile propelled from a chamber by an explosion, and objects damaged by a blast. With appropriate rendering techniques, our explosion model can be used to create such visual effects as fireballs, dust clouds, and the refraction of light caused by a blast wave.

Citation

Gary D. Yngve, James F. O'Brien, and Jessica K. Hodgins. Animating explosions. In Proceedings of ACM SIGGRAPH 2000, pages 29–36, July 2000. [BiBTeX]

Links

• Project page

Animating Fracture

James F. O'Brien and Jessica K. Hodgins

Citation

James F. O'Brien and Jessica K. Hodgins. Animating fracture. Communications of the ACM, 43(7):68–75, 2000. [BiBTeX]

Links

• Project page

Interactive Manipulation of Rigid Body Simulations

Jovan Popović, Steven M. Seitz, Michael Erdmann, Zoran Popović, and Andrew Witkin

Abstract

Physical simulation of dynamic objects has become commonplace in computer graphics because it produces highly realistic animations. In this paradigm the animator provides few physical parameters such as the objects' initial positions and velocities, and the simulator automatically generates realistic motions. The resulting motion, however, is difficult to control because even a small adjustment of the input parameters can drastically affect the subsequent motion. Furthermore, the animator often wishes to change the end-result of the motion instead of the initial physical parameters. We describe a novel interactive technique for intuitive manipulation of rigid multi-body simulations. Using our system, the animator can select bodies at any time and simply drag them to desired locations. In response, the system computes the required physical parameters and simulates the resulting motion. Surface characteristics such as normals and elasticity coefficients can also be automatically adjusted to provide a greater range of feasible motions, if the animator so desires. Because the entire simulation editing process runs at interactive speeds, the animator can rapidly design complex physical animations that would be difficult to achieve with existing rigid body simulators.

Citation

Jovan Popović, Steven M. Seitz, Michael Erdmann, Zoran Popović, and Andrew Witkin. Interactive manipulation of rigid body simulations. In Proceedings of SIGGRAPH 2000, pages 209–218, July 2000. [BiBTeX]

Links

• Project page

Tangible Interaction + Graphical Interpretation: a New Approach to 3D Modeling

David Anderson, James L. Frankel, Joe Marks, Aseem Agarwala, Paul Beardsley, Jessica K. Hodgins, Darren Leigh, Kathy Ryall, Eddie Sullivan, and Jonathan S. Yedidia

Abstract

Construction toys are a superb medium for geometric models. We argue that such toys, suitably instrumented or sensed, could be the inspiration for a new generation of easy-to-use, tangible modeling systems.especially if the tangible modeling is combined with graphical-interpretation techniques for enhancing nascent models automatically. The three key technologies needed to realize this idea are embedded computation, vision-based acquisition, and graphical interpretation. We sample these technologies in the context of two novel modeling systems: physical building blocks that self-describe, interpret, and decorate the structures into which they are assembled; and a system for scanning, interpreting, and animating clay figures.

Citation

David Anderson, James L. Frankel, Joe Marks, Aseem Agarwala, Paul Beardsley, Jessica K. Hodgins, Darren Leigh, Kathy Ryall, Eddie Sullivan, and Jonathan S. Yedidia. Tangible interaction + graphical interpretation: a new approach to 3d modeling. In Proceedings of ACM SIGGRAPH 2000, pages 393–402, July 2000. [BiBTeX]

The Effects of Noise on the Perception of Animated Human Running

Bobby Bodenheimer, Anna V. Shleyfman, and Jessica K. Hodgins

Citation

Bobby Bodenheimer, Anna V. Shleyfman, and Jessica K. Hodgins. The effects of noise on the perception of animated human running. In Computer Animation and Simulation '99, September 1999. [BiBTeX]

Links

Tracking and Modifying Upper-Body Human Motion Data with Dynamic Simulation

Victor B. Zordan and Jessica K. Hodgins

Citation

Victor B. Zordan and Jessica K. Hodgins. Tracking and modifying upper-body human motion data with dynamic simulation. In Computer Animation and Simulation '99, September 1999. [BiBTeX]

Links

Graphical Modeling and Animation of Brittle Fracture

James F. O'Brien and Jessica K. Hodgins

Abstract

In this paper, we augment existing techniques for simulating flexible objects to include models for crack initiation and propagation in three-dimensional volumes. By analyzing the stress tensors computed over a finite element model, the simulation determines where cracks should initiate and in what directions they should propagate. We demonstrate our results with animations of breaking bowls, cracking walls, and objects that fracture when they collide. By varying the shape of the objects, the material properties, and the initial conditions of the simulations, we can create strikingly different effects ranging from a wall that shatters when it is hit by a wrecking ball to a bowl that breaks in two when it is dropped on edge.

Citation

James F. O'Brien and Jessica K. Hodgins. Graphical modeling and animation of brittle fracture. In Proceedings of SIGGRAPH 99, pages 137–146, August 1999. [BiBTeX]

Links

• Project page

Fast Synthetic Vision, Memory, and Learning Models for Virtual Humans

James J. Kuffner and Jean-Claude Latombe

Abstract

The paper presents a simple and efficient method of modeling synthetic vision, memory, and learning for autonomous animated characters in real time virtual environments. The model is efficient in terms of both storage requirements and update times, and can be flexibly combined with a variety of higher level reasoning modules or complex memory rules. The design is inspired by research in motion planning, control, and sensing for autonomous mobile robots. We apply this framework to the problem of quickly synthesizing from navigation goals the collision-free motions for animated human figures in changing virtual environments. We combine a low level path planner, a path following controller and cyclic motion capture data to generate the underlying animation. Graphics rendering hardware is used to simulate the visual perception of a character, providing a feedback loop to the overall navigation strategy. The synthetic vision and memory update rules can handle dynamic environments where objects appear, disappear, or move around unpredictably. The resulting model is suitable for a variety of real time applications involving autonomous animated characters.

Citation

James J. Kuffner and Jean-Claude Latombe. Fast synthetic vision, memory, and learning models for virtual humans. In Proceedings of Computer Animation 1999, pages 118–127, May 1999. [BiBTeX]

Animating Sand, Mud, and Snow

Robert Sumner, James F. O'Brien, and Jessica K. Hodgins

Citation

Robert Sumner, James F. O'Brien, and Jessica K. Hodgins. Animating sand, mud, and snow. Computer Graphics Forum, 18(1):17–26, March 1999. [BiBTeX]

Links

Two methods for display of high contrast images

Jack Tumblin, Jessica K. Hodgins, and Brian K. Guenter

Abstract

High contrast images are common in night scenes and other scenes that include dark shadows and bright light sources. These scenes are difficult to display because their contrasts greatly exceed the range of most display devices for images. As a result, the image constrasts are compressed or truncated, obscuring subtle textures and details. Humans view and understand high contrast scenes easily, "adapting" their visual response to avoid compression or truncation with no apparent loss of detail. By imitating some of these visual adaptation processes, we developed methods for the improved display of high-contrast images. The first builds a display image from several layers of lighting and surface properties. Only the lighting layers are compressed, drastically reducing contrast while preserving much of the image detail. This method is practical only for synthetic images where the layers can be retained from the rendering process. The second method interactively adjusts the displayed image to preserve local contrasts in a small "foveal" neighborhood. Unlike the first method, this technique is usable on any image and includes a new tone reproduction operator. Both methods use a sigmoid function for contrast compression. This function has no effect when applied to small signals but compresses large signals to fit within an asymptotic limit. We demonstrate the effectiveness of these approaches by comparing processed and unprocessed images.

Citation

Jack Tumblin, Jessica K. Hodgins, and Brian K. Guenter. Two methods for display of high contrast images. ACM Transactions on Graphics, 18(1):56–94, January 1999. [BiBTeX]

Links

• Project page

Dynamically Simulated Characters in Virtual Environments

David C. Brogan, Ronald A. Metoyer, and Jessica K. Hodgins

Citation

David C. Brogan, Ronald A. Metoyer, and Jessica K. Hodgins. Dynamically simulated characters in virtual environments. IEEE Computer Graphics & Applications, 18(5):58–69, September 1998. [BiBTeX]

Links

• Project page

Large Steps in Cloth Simulation

David Baraff and Andrew P. Witkin

Abstract

The bottle-neck in most cloth simulation systems is that time steps must be small to avoid numerical instability. This paper describes a cloth simulation system that can stably take large time steps. The simulation systemcouples a new technique for enforcing constraints on individual cloth particles with an implicit integration method. The simulator models cloth as a triangular mesh, with internal cloth forces derived using a simple continuum formulation that supports modeling operations such as local anisotropic stretch or compression; a unified treatment of damping forces is included as well. The implicit integration method generates a large, unbanded sparse linear system at each time step which is solved using a modified conjugate gradient method that simultaneously enforces particles' constraints. The constraints are always maintained exactly, independent of the number of conjugate gradient iterations, which is typically small. The resulting simulation system is significantly faster than previous accounts of cloth simulation systems in the literature.

Citation

David Baraff and Andrew P. Witkin. Large steps in cloth simulation. In Proceedings of SIGGRAPH 98, Computer Graphics Proceedings, Annual Conference Series, pages 43–54, July 1998. [BiBTeX]

Links

• Paper (PDF, 249KB)

Adapting Simulated Behaviors For New Characters

Jessica K. Hodgins and Nancy S. Pollard

Abstract

This paper describes an algorithm for automatically adapting existing simulated behaviors to new characters. Animating a new character is difficult because a control system tuned for one character will not, in general,work on a characterwith different limb lengths, masses, or moments of inertia. The algorithm presented here adapts the control system to a new character in two stages. First, the control system parameters are scaled based on the sizes, masses, and moments of inertia of the new and the original characters. Then a subset of the parameters is fine-tuned using a search process based on simulated annealing. To demonstrate the effectiveness of this approach, we animate the running motion of a woman, child, and imaginary character bymodifying the control systemfor a man. We also animate the bicycling motion of a second imaginary character by modifying the control system for a man. We evaluate the results of this approach by comparing the motion of the simulated human runnerswith video of an actual child andwith data for men,women, and children in the literature. In addition to adapting a control system for a new model, this approach can also be used to adapt the control system in an on-line fashion to produce a physically realistic metamorphosis from the original to the new model while the morphing character is performing the behavior. We demonstrate this on-line adaptation with a morph from a man to a woman over a period of twenty seconds.

Citation

Jessica K. Hodgins and Nancy S. Pollard. Adapting simulated behaviors for new characters. In Proceedings of SIGGRAPH 97, pages 153–162, August 1997. [BiBTeX]

Transitions Between Dynamically Simulated Motions: Leaping, Tumbling, Landing, and Balancing

Wayne L. Wooten and Jessica K. Hodgins

Citation

Wayne L. Wooten and Jessica K. Hodgins. Transitions between dynamically simulated motions: Leaping, tumbling, landing, and balancing. In ACM SIGGRAPH 97 Visual Proceedings: The art and interdisciplinary programs of SIGGRAPH '97, page 217. ACM Press, 1997. [BiBTeX]

Linear-Time Dynamics using Lagrange Multipliers

David Baraff

Abstract

Current linear-time simulation methods for articulated figures are based exclusively on reduced-coordinate formulations. This paper describes a general, non-iterative linear-time simulation method based instead on Lagrange multipliers. Lagrange multiplier methods are important for computer graphics applications because they bypass the difficult (and often intractable) problem of parameterizing a system's degrees of freedom. Given a loop-free set of n equality constraints acting between pairs of bodies, the method takes O(n) time to compute the system's dynamics. The method does not rely on matrix bandwidth, so no assumptions about the constraints' topology are needed. Bodies need not be rigid, constraints can be of various dimensions, and unlike reduced-coordinate approaches, nonholonomic (for example, velocity-dependent) constraints are allowed. An additional set of k one-dimensional constraints which induce loops and/or handle inequalities can be accommodated with cost O(kn). This makes it practical to simulate complicated, closed-loop articulated figures with joint-limits and contact at interactive rates. A complete description of a sample implementation is provided in pseudocode.

Citation

David Baraff. Linear-time dynamics using lagrange multipliers. In Proceedings of SIGGRAPH 96, Computer Graphics Proceedings, Annual Conference Series, pages 137–146, August 1996. [BiBTeX]

Links

• Paper (PDF, 158KB)

Atlanta in Motion

Jessica K. Hodgins

Citation

Jessica K. Hodgins. Atlanta in motion. In ACM SIGGRAPH 96 Visual Proceedings: The art and interdisciplinary programs of SIGGRAPH '96, page 163. ACM Press, 1996. [BiBTeX]

Animating Human Athletics

Jessica K. Hodgins, Wayne L. Wooten, David C. Brogan, and James F. O'Brien

Abstract

This paper describes algorithms for the animation of men and women performing three dynamic athletic behaviors: running, bicycling, and vaulting. We animate these behaviors using control algorithms that cause a physically realistic model to perform the desired maneuver. For example, control algorithms allow the simulated humans to maintain balance while moving their arms, to run or bicycle at a variety of speeds, and to perform a handspring vault. Algorithms for group behaviors allow a number of simulated bicyclists to ride as a group while avoiding simple patterns of obstacles. We add secondary motion to the animations with springmass simulations of clothing driven by the rigid-body motion of the simulated human. For each simulation, we compare the computed motion to that of humans performing similar maneuvers both qualitatively through the comparison of real and simulated video images and quantitatively through the comparison of simulated and biomechanical data.

Citation

Jessica K. Hodgins, Wayne L. Wooten, David C. Brogan, and James F. O'Brien. Animating human athletics. In Proceedings of SIGGRAPH 95, pages 71–78, August 1995. [BiBTeX]

Links

• Project page

Planning Motions with Intentions

Yoshihito Koga, Koichi Kondo, James J. Kuffner, and Jean-Claude Latombe

Abstract

We apply manipulation planning to computer animation. A new path planner is presented that automatically computes the collision-free trajectories for several cooperating arms to manipulate a movable object between two configurations. This implemented planner is capable of dealing with complicated tasks where regrasping is involved. In addition, we present a new inverse kinematics algorithm for the human arms. This algorithm is utilized by the planner for the generation of realistic human arm motions as they manipulate objects. We view our system as a tool for facilitating the production of animation.

Citation

Yoshihito Koga, Koichi Kondo, James J. Kuffner, and Jean-Claude Latombe. Planning motions with intentions. In Proceedings of SIGGRAPH 94, pages 395–408, July 1994. [BiBTeX]

Links

• Paper (PDF, 392KB)

Animation of Dynamic Legged Locomotion

Marc H. Raibert and Jessica K. Hodgins

Abstract

This paper is about the use of control algorithms to animate dynamic legged locomotion. Control could free the animator from specifying the details of joint and limb motion while producing both physically realistic and natural looking results. We implemented computer animations of a biped robot, a quadruped robot, and a kangaroo. Each creature was modeled as a linked set of rigid bodies with compliant actuators at its joints. Control algorithms regulated the running speed, organized use of the legs, and maintained balance. All motions were generated by numerically integrating equations of motion derived from the physical models. The resulting behavior included running at various speeds, traveling with several gaits (run, trot, bound, gallop, and hop), jumping, and traversing simple paths. Whereas the use of control permitted a variety of physically realistic animated behavior to be generated with limited human intervention, the process of designing the control algorithms was not automated: the algorithms were "tweaked" and adjusted for each new creature.

Citation

Marc H. Raibert and Jessica K. Hodgins. Animation of dynamic legged locomotion. In Computer Graphics (Proceedings of SIGGRAPH 91), volume 25, pages 349–358, July 1991. [BiBTeX]