Jernej Barbič

Real-time Reduced Large-deformation Models and Distributed Contact for Computer Graphics and Haptics Degree Type: Ph.D. in Computer Science
Advisor(s): Doug James
Graduated: August 2007

Abstract:

This thesis presents novel algorithms for deformable dynamics, collision detection and contact resolution between reduced nonlinear 3D deformable objects, for use in interactive computer graphics and haptics. The deformable models investigated are elastic, volumetric, and capable of undergoing large deformations. Each mesh vertex of a general 3D deformable object has three degrees of freedom. Noninteractive computation times result when simulating large-deformation dynamics of such unreduced systems (assuming non-trivial geometry). Reduced deformable objects are obtained by substituting these general degrees of freedom for a much smaller appropriately defined set of reduced degrees of freedom. This dimensionality reduction can enable much faster simulation times, with some loss of simulation accuracy. Many interesting objects can be well approximated by reduced deformations: swaying bridges, plants, tall buildings, mechanical components (hoses, wires), and human tissue (thigh passively deforming after a jump). The reduced deformable degrees of freedom need to be defined carefully so that they support "typical" large deformations. We present an automatic degree-of-freedom selection algorithm, and an algorithm for fast runtime simulation of the resulting reduced nonlinear dynamics for geometrically nonlinear deformable models.

Real-time deformable objects can be used to provide multi-sensory feedback in emerging real-time applications, such as 6-DOF (force and torque) haptic rendering. It is challenging to perform collision detection and compute contact forces and torques between geometrically complex objects at haptic rates. This thesis presents a CPU-based approach to simulate distributed contact between two (rigid or reduced-deformable) objects with complex geometry. Penalty-based contact forces are resolved using a multi-resolution point-based representation for one object, and a signed-distance field for the other. Our algorithm can adapt the contact force accuracy to both the difficulty of the current contact configuration and the speed of the particular computer. Reduced-deformed distance fields are proposed to support contact between reduced deformable objects. We also expose several important algorithmic details essential for stable and robust 6-DOF haptic rendering. Applications of our work include computer animation and games (including game haptics), CAD/CAM (virtual prototyping), and interactive virtual medicine.

Thesis Committee:
Doug L. James (Chair)
Ralph L. Hollis
Nancy S. Pollard
Dinesh K. Pai (University of British Columbia)

Jeannette Wing, Head, Computer Science Department
Randy Bryant, Dean, School of Computer Science

Keywords:
Real-time, deformations, model reduction, finite element method, subspace integration, distributed contact, haptics, distance fields, multi-resolution, interruptible, time-critical, simulation, precomputation, computer graphics