Interactive Data-Driven Physical Simulation Research
Doug L. James
The Robotics Institute & Computer Science Dept.
School of Computer Science
Carnegie Mellon University
This page documents our research on
data-driven simulation of physical models. One of our goals is to
allow people to simulate and interact with realistic physically based
deformable environments at force-feedback and animation frame rates
while using only minimal computing resources. A recurring research
has been to exploit precomputation (and/or measurement) and efficient
data-driven representations for low-cost runtime simulation.
L. James and Christopher
D. Twigg, Skinning
Mesh Animations, ACM
Transactions on Graphics (ACM SIGGRAPH 2005), 2005.
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.
||Jernej Barbič and Doug
L. James, Real-Time Subspace Integration of St.Venant-Kirchhoff
Deformable Models, ACM
Transactions on Graphics (ACM SIGGRAPH 2005), 2005.
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 sketch. 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.
||Doug L. James and Dinesh K. Pai, BD-Tree:
Output-Sensitive Collision Detection for Reduced Deformable Models,
Transactions on Graphics (ACM SIGGRAPH 2004),
23(3), 2004. [BiBTeX]
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
models represent complex deformations as linear superpositions of
arbitrary displacement fields, and are used in a variety of
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 of 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.
(12,201 chairs; 218,568,714 triangles; level 8 collision
(avi [DivX], 512x384, 66MB, FULL 1m10s clip)
- VIDEO (avi [DivX],
512x384, 4.4MB, MINI 5sec CLIP)
L. James, Jernej Barbic,
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
||Doug L. James
and Kayvon Fatahalian,Precomputing
Interactive Dynamic Deformable Scenes, ACM
Transactions on Graphics (ACM SIGGRAPH 2003), 22(3),
879-887, 2003. [BiBTeX]
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
- Related CMU technical report
(contains additional images and appendices):
||D. James and K.
Fatahalian, Precomputing Interactive Dynamic Deformable Scenes, tech.
report TR-03-33, Robotics Institute, Carnegie Mellon University,
||Paul G. Kry, Doug L. James and Dinesh K. Pai, EigenSkin:
Real Time Large Deformation Character Skinning in Hardware, ACM SIGGRAPH Symposium on Computer
Animation, pp. 153-160, 2002.
We present a technique which allows subtle nonlinear quasi-static
deformations of articulated characters to be compactly approximated by
data-dependent eigenbases which are optimized for real time rendering
commodity graphics hardware. The method extends the common
Skeletal-Subspace Deformation (SSD) technique to provide efficient
approximations of the complex deformation behaviours exhibited in
simulated, measured, and artist-drawn characters. Instead of storing
displacements for key poses (which may be numerous), we precompute
principal components of the deformation influences for individual
kinematic joints, and so construct error-optimal eigenbases describing
each joint's deformation subspace. Pose-dependent deformations are then
expressed in terms of these reduced eigenbases, allowing precomputed
coefficients of the eigenbasis to be interpolated at run time. Vertex
program hardware can then efficiently render nonlinear skin
using a small number of eigendisplacements stored in graphics
hardware. We refer to the final resulting character skinning
construct as the model's EigenSkin. Animation results are presented for
a very large nonlinear finite element model of a human hand rendered in
real time at minimal cost to the main CPU.
||Doug L. James and Dinesh K. Pai, DyRT:
Dynamic Response Textures for Real Time Deformation Simulation with
Graphics Hardware, ACM Transactions on Graphics
(ACM SIGGRAPH 2002), 21(3), pp. 582-585, 2002.
In this paper we describe how to simulate geometrically complex,
interactive, physically-based, volumetric, dynamic deformation models
with negligible main CPU costs. This is achieved using a Dynamic
Response Texture, or DyRT, that can be mapped onto any
conventional animation as an optional rendering stage using commodity
graphics hardware. The DyRT simulation process employs precomputed
vibration models excited by rigid body motions. We present several
examples, with an emphasis on bone-based character animation for
- PAPER (pdf, 2.2MB)
||Full length DyRT video
jumping (avi [mpg4], 700K)
simulation (mpg, 3MB)
||Doug L. James and Dinesh K. Pai,
Time Simulation of Multizone Elastokinematic Models, 2002 IEEE
Intl. Conference on Robotics and Automation, Washington DC, May
We introduce precomputed multizone elastokinematic models for
interactive simulation of multibody kinematic systems which include
elastostatic deformations. This enables an efficient form of domain
decomposition, suitable for interactive simulation of stiff flexible
structures for real time applications such as interactive assembly. One
advantage of multizone models is that each zone can have small strains,
and hence be modeled with linear elasticity, while the entire
multizone/multibody system admits large nonlinear relative strains.
permits fast capacitance matrix algorithms and precomputed Green's
functions to be used for efficient real time simulation. Examples are
given for a human finger modeled as a kinematic chain with a compliant
- PAPER (pdf, 0.8MB)
contact (avi [mpg4], 2.5MB)
|Elastokinematic contact (avi-DivX,
||Doug L. James and Dinesh K. Pai,
Green's Function Methods for Interactive Simulation of Large-scale
Elastostatic Objects, ACM Transactions on Graphics, 22(1), pp. 47-82, 2003.
We present a framework for low-latency interactive simulation of linear
elastostatic models, and other systems arising from linear elliptic
partial differential equations, which makes it feasible to
simulate large-scale physical models. The deformation of the models is
described using precomputed Green's functions (GFs), and runtime
boundary value problems (BVPs) are solved using existing Capacitance
Matrix Algorithms (CMAs). Multiresolution techniques are introduced to
control the amount of information input and output from the solver thus
making it practical to simulate and store very large models. A key
component is the efficient compressed representation of the precomputed
GFs using second-generation wavelets on surfaces. This aids in reducing
the large memory requirement of storing the dense GF matrix, and the
fast inverse wavelet transform allows for fast summation methods to be
used at runtime for response synthesis. Resulting GF compression
are directly related to interactive simulation speedup, and examples
provided with hundredfold improvements at modest error levels. We also
introduce a multiresolution constraint satisfaction technique
as an hierarchical CMA, so named because of its use of hierarchical GFs
describing the response due to hierarchical basis constraints. This
direct solution approach is suitable for hard real time simulation
it provides a mechanism for gracefully degrading to coarser resolution
constraint approximations. The GFs' multiresolution displacement fields
also allow for runtime adaptive multiresolution rendering.
- PAPER: Preprint (pdf, 9.4MB) or final
ACM Digital Library link.
- VIDEOS: Real time
feedback simulations (using Java-based ARTDEFO simulator with Phantom
||Rabbit: Full L=4
wavelet GF model (mpg, 4.7MB)
hierarchical GF model (mpg, 5.6MB)
||Both: (Hires avi-DivX, 4.9MB)
||Doug L. James, Multiresolution Green's
Function Methods for Interactive Simulation of Large-scale Elastostatic
Objects and other Physical Systems in Equilibrium, Ph.D. Thesis,
Institute of Applied Mathematics, UBC, 2001.
thesis presents a framework for low-latency interactive simulation of
linear elastostatic models and other systems associated with linear
elliptic partial differential equations. This approach makes it
to interactively simulate large-scale physical models.
Linearity is exploited by formulating the boundary value problem (BVP)
solution in terms of Green’s functions (GFs) which may be precomputed
provide speed and cheap lookup operations. Runtime BVPs are solved
a collection of Capacitance Matrix Algorithms (CMAs) based on the
Sherman-Morrison-Woodbury formula. Temporal coherence is exploited by
caching and reusing, as well as sequentially updating, previous
capacitance matrix inverses.
Multiresolution enhancements make it practical to simulate and store
very large models. Efficient compressed representations of precomputed
GFs are obtained using second-generation wavelets defined on surfaces.
Fast inverse wavelet transforms allow fast summation methods to be used
to accelerate runtime BVP solution. Wavelet GF compression factors are
directly related to interactive simulation speedup, and examples are
provided with hundredfold improvements at modest error levels.
Furthermore, hierarchical constraints are defined using hierarchical
basis functions, and related hierarchical GFs are then used to
an hierarchical CMA. This direct solution approach is suitable for hard
real time simulation since it provides a mechanism for gracefully
degrading to coarser resolution approximations, and the wavelet
representations allow for runtime adaptive multiresolution rendering.
GF CMAs are well-suited to interactive haptic applications since GFs
allow random access to solution components and the capacitance matrix
the contact compliance used for high-fidelity force feedback rendering.
Examples are provided for distributed and point-like interactions.
Precomputed multizone kinematic GF models are also considered, with
examples provided for character animation in computer graphics.
Finally, we briefly discuss the generation of multiresolution GF models
using either numerical precomputation methods or reality-based robotic
THESIS (pdf, 18MB)
Exam programme (pdf,
Pai, Kees van den Doel,
Doug L. James, Jochen Lang,John E. Lloyd, Joshua L. Richmond,
Som H. Yau, Scanning Physical Interaction Behavior of 3D
Objects, Proceedings of ACM SIGGRAPH 2001, pp. 87-96, 2001.
We describe a system for constructing computer models of several
aspects of physical interaction behavior, by scanning the response of
real objects. The behaviors we can successfully scan and model include
deformation response, contact textures for interaction with
force-feedback, and contact sounds. The system we describe uses a
automated robotic facility that can scan behavior models of whole
objects. We provide a comprehensive view of the modeling process,
including selection of model structure, measurement, estimation, and
rendering at interactive rates. The results are demonstrated with two
examples: a soft stuffed toy which has significant deformation
and a hard clay pot which has significant contact textures and
sounds. The results described here make it possible to quickly
construct physical interaction models of objects for applications in
games, animation, and e-commerce.
Defo Demo Events:
Green's function descriptions of linear elastostatic models are
inherently well suited to reality-based modeling. Using the UBC Active
Measurement Facility (ACME) we have
robotically automated the acquisition of real deformable models by
directly measuring quantities related to Green's functions (see Jochen Lang's Ph.D.
thesis). Once reconstructed, the models may be interactived with using
fast Green's function simulation techniques. For this team project, I
also worked on the reconstruction of textured multiresolution meshes
from range data, and subsequent rendering of deformations using
displaced subdivision surfaces.
- Precarn-IRIS Annual Conference on
Intelligent Systems, Ottawa, June 4-5, 2001. (best demo)
- IEEE Intl. Conference on
Computer Vision, Vancouver, July 9-12, 2001.
||Doug L. James and Dinesh K. Pai, Pressure
Masks for Point-like Contact with Elastic Models, In Proceedings
of the Fifth Phantom User Group Workshop, J.K. Salisbury and M.A.
Srinivasan (Eds), 2000.
In this paper, we introduce pressure masks for supporting the
convenient abstraction of localized scale-specific point-like contact
with a discrete elastic object. While these masks may be defined for
elastic model, special attention is given to the case of point-like
contact with precomputed linear elastostatic models for purposes of
haptic force feedback.
PAPER (pdf, 400K)
||Doug L. James and Dinesh K. Pai, A Unified
Treatment of Elastostatic Contact Simulation for Real Time Haptics,
The Electronic Journal of Haptics Research (www.haptics-e.org), Vol. 2,
Number 1, September 27, 2001.
We describe real-time, physically-based simulation algorithms for
haptic interaction with elastic objects. Simulation of contact with
elastic objects has been a challenge, due to the complexity of
physically accurate simulation and the difficulty of constructing
approximations suitable for real time interaction. We show that this
challenge can be effectively solved for many applications. In
global deformation of linear elastostatic objects can be efficiently
solved with low run-time computational costs, using precomputed Green's
functions and fast low-rank updates based on Capacitance Matrix
Algorithms. The capacitance matrices constitute exact force
response models, allowing contact forces to be computed much faster
global deformation behavior. Vertex pressure masks are introduced to
support the convenient abstraction of localized scale-specific
point-like contact with an elastic and/or rigid surface approximated by
a polyhedral mesh. Finally, we present several examples using the
CyberGlove and PHANToM haptic interfaces.
- PAPER (pdf, 1.6MB)
(avi: 160x120 [3MB] or 320x240 [10MB])
||Early PHANToM demos
||Funky bicycle banana
seat (whoa?!) (mpg, 2.5MB)
||Doug L. James and Dinesh
K. Pai, ARTDEFO: Accurate Real Time
Deformable Objects, Proceedings of ACM
pp. 65-72, 1999.
We present an algorithm for fast, physically accurate simulation of
deformable objects suitable for real time animation and virtual
environment interaction. We describe the boundary integral equation
formulation of static linear elasticity as well as the related Boundary
Element Method (BEM) discretization technique. In addition, we show how
to exploit the coherence of typical interactions to achieve low
the boundary formulation lends itself well to a fast update method when
a few boundary conditions change. The algorithms are described in
with examples from ArtDefo, our implementation.
PAPER (pdf, 1.2MB)
VIDEO (avi, 6MB)
ARTDEFO Picture Gallery!
material is based upon work supported by the National Science
Foundation under Grant No. 0347740.
Any opinions, findings,
conclusions or recommendations expressed in this material are those of
the author(s) and do not necessarily reflect the views of the National