Advances in data acquisition tools have led to a dramatic increase in the geometric complexity of 3D data. Efficiently modeling, simulating, and analyzing these scanned large-scale real-world models become a serious challenge, because the numerical integration of high dimensional partial differential equations (over millions of degrees of freedom) is prohibitive for time-critical applications such as surgical simulation, bio-medical imaging, virtual/augmented reality, and physically-based animation. The problem becomes significantly more acute in situations where the rest-shape geometries of the 3D models are frequently altered and there is a need for collision detection/response coupled with high fidelity visualization of heterogeneous material properties and efficient transmission over the network to facilitate collaborative interaction. In this project the PI will address this challenge by developing a research program to create a modularized computational framework for efficient deformable simulation by partitioning the deformable body into small-size domains and re-connecting them back using weakened linkages. Domain-level computations are independent and reusable; thus, the expensive deformable simulation is reframed as a plug-and-play computational assemblage just like playing with LEGO blocks, and orders of magnitude speedup can be obtained. The plug-and-play deformable model that will be the primary project outcome will advance state-of-the-art techniques in physical simulation, animation and visualization, and will also profoundly benefit a broad range of interdisciplinary fields that directly impact people in their daily lives, from the modeling and registration of deformable human organs for surgical simulation, to the analysis of roadway pavement stress, to silent speech recognition.

The PI's approach pivots on the transformative concept of divide-and-conquer deformable model. Unlike most state-of-the-art techniques that simulate a deformable object in its entirely by means of a "one-stop" solver, the PI will develop innovative algorithms that break a simulation into independent computational modules, with the final result being obtained by incrementally assembling the local computations. The PI will seek theoretical solutions to two general questions: "how to smartly divide" and "how to effectively conquer" in the context of deformable simulation. In particular, he will investigates a theoretically grounded domain decomposition and coupling mechanism so that domain-level computation is independent, reusable, modularized and also a good fit with existing parallel computing architectures such as multi-core CPUs or GPUs. The PI will develop a new theory for the real-time spectral deformation processing that divides the simulation not only spatially but also spectrally, based on a power iteration and inertia analysis. He will also explore possible solutions to the problem of optimal domain partitioning, in which the simulation is parameterized geometrically and the most effective partition is obtained by solving a geometry optimization problem similar to the Voronoi diagram. As the test-bed for the aforementioned theoretical and algorithmic advances, the PI will develop a haptic-enabled collaborative digital fabrication system, which will ultimately allow multiple users, from distant sites to smoothly interact to design and craft physically simulated virtual objects, which can then be 3D printed if desired.

CRII: CHS: A Plug-and-Play Deformable Model Based on Extended Domain Decomposition
IIS #1464306
PI: Yin Yang