Doug L. James

Assistant Professor
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 theme has been to exploit precomputation (and/or measurement) and efficient data-driven representations for low-cost runtime simulation.
  

	Doug L. James and Christopher D. Twigg, Skinning Mesh Animations, ACM Transactions on Graphics (ACM SIGGRAPH 2005), 2005. 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. PAPER (pdf, 8MB) VIDEO (avi [DivX], 55MB) Project page
	Jernej Barbič and Doug L. James, Real-Time Subspace Integration of St.Venant-Kirchhoff Deformable Models, ACM Transactions on Graphics (ACM SIGGRAPH 2005), 2005. 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 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. PAPER (pdf, 5MB) VIDEO (avi [DivX], 80MB) Project page
	Doug L. James and Dinesh K. Pai, BD-Tree: Output-Sensitive Collision Detection for Reduced Deformable Models, ACM Transactions on Graphics (ACM SIGGRAPH 2004), 23(3), 2004.  [BiBTeX] 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 arbitrary 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 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.    PAPER (pdf, 5MB) VIDEO (avi [DivX], 108MB) Project page Electronic Theatre animation page. SIGGRAPH talk slides (zip, WARNING: 247MB!  Optimized for 1024x768 resolution.) "Niagara" sequence (12,201 chairs;  218,568,714 triangles;  level 8 collision depth): VIDEO (avi [DivX], 512x384, 66MB, FULL 1m10s clip) VIDEO (avi [DivX], 512x384, 4.4MB, MINI 5sec CLIP)
	Doug 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 2004.  [BiBTeX] PAPER (pdf, 2MB) VIDEO (avi [DivX], 39MB) Project page

Doug L. James and Kayvon Fatahalian,Precomputing Interactive Dynamic Deformable Scenes, ACM Transactions on Graphics (ACM SIGGRAPH 2003), 22(3), pp. 879-887, 2003.  [BiBTeX] 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. PAPER (pdf,10MB) VIDEO (avi-DivX, 14MB) 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, September, 2003. PAPER (pdf, 4.5MB) CMU techreport page

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. ABSTRACT:  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 on 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 deformations 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. PAPER (pdf, 5.7MB) VIDEO (avi [mpg4], 19MB) Check out Paul's EigenSkin page (with shadow puppets!)

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. ABSTRACT:  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 modal vibration models excited by rigid body motions. We present several examples, with an emphasis on bone-based character animation for interactive applications.   PAPER (pdf, 2.2MB) VIDEOS: Full length DyRT video  (mpg, 24MB) Excerpt:  DyRT-Man jumping (avi [mpg4], 700K) Excerpt:  Surgical simulation (mpg, 3MB)

Doug L. James and Dinesh K. Pai, Real Time Simulation of Multizone Elastokinematic Models, 2002 IEEE Intl. Conference on Robotics and Automation, Washington DC, May 2002. ABSTRACT:  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. This 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 elastic covering. PAPER (pdf, 0.8MB) VIDEOS: Finger motion (avi, 4.7MB) Elastokinematic contact (avi [mpg4], 2.5MB)  Elastokinematic contact (avi-DivX, 2.8MB)

Doug L. James and Dinesh K. Pai, Multiresolution Green's Function Methods for Interactive Simulation of Large-scale Elastostatic Objects, ACM Transactions on Graphics, 22(1), pp. 47-82, 2003. ABSTRACT:  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 interactively 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 factors are directly related to interactive simulation speedup, and examples are provided with hundredfold improvements at modest error levels. We also introduce a multiresolution constraint satisfaction technique formulated 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 since 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 force feedback simulations (using Java-based ARTDEFO simulator with Phantom haptic interface): Rabbit: Full L=4 wavelet GF model (mpg, 4.7MB) Dragon: Wavelet 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. ABSTRACT:     This 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 feasible 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 to provide speed and cheap lookup operations. Runtime BVPs are solved using 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 construct 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.    These GF CMAs are well-suited to interactive haptic applications since GFs allow random access to solution components and the capacitance matrix is 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 measurement.   THESIS (pdf, 18MB) Exam programme (pdf, 200K)

Dinesh K. 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.  ABSTRACT:  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 highly 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 behavior, 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.   PAPER (pdf, 1.5MB) VIDEO (mpg, 16MB) Defo Demo Events: 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. COMMENT:  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 textured displaced subdivision surfaces.

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. ABSTRACT:  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 any 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, Haptics-e, The Electronic Journal of Haptics Research (www.haptics-e.org), Vol. 2, Number 1, September 27, 2001. ABSTRACT:  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 useful approximations suitable for real time interaction. We show that this challenge can be effectively solved for many applications. In particular 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 than 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) VIDEOS: CyberGlove-based grasping (avi: 160x120 [3MB] or 320x240 [10MB]) Early PHANToM demos (avi, 9MB) Funky bicycle banana seat (whoa?!) (mpg, 2.5MB)

Doug L. James and Dinesh K. Pai, ARTDEFO: Accurate Real Time Deformable Objects, Proceedings of ACM SIGGRAPH 99, pp. 65-72, 1999. ABSTRACT:  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 latency; the boundary formulation lends itself well to a fast update method when a few boundary conditions change. The algorithms are described in detail with examples from ArtDefo, our implementation.   PAPER (pdf, 1.2MB)  VIDEO (avi, 6MB) ARTDEFO Picture Gallery!

Home