Award Abstract # 1464306
CRII: CHS: A Plug-and-Play Deformable Model Based on Extended Domain Decomposition

NSF Org: IIS
Division of Information & Intelligent Systems
Recipient: UNIVERSITY OF NEW MEXICO
Initial Amendment Date: March 10, 2015
Latest Amendment Date: May 6, 2015
Award Number: 1464306
Award Instrument: Standard Grant
Program Manager: Ephraim Glinert
IIS
 Division of Information & Intelligent Systems
CSE
 Directorate for Computer and Information Science and Engineering
Start Date: March 1, 2015
End Date: February 28, 2018 (Estimated)
Total Intended Award Amount: $174,829.00
Total Awarded Amount to Date: $190,829.00
Funds Obligated to Date: FY 2015 = $190,829.00
History of Investigator:
  • Yin Yang (Principal Investigator)
    yin.yang@utah.edu
Recipient Sponsored Research Office: University of New Mexico
1 UNIVERSITY OF NEW MEXICO
ALBUQUERQUE
NM  US  87131-0001
(505)277-4186
Sponsor Congressional District: 01
Primary Place of Performance: University of New Mexico
NM  US  87131-0001
Primary Place of Performance
Congressional District:
01
Unique Entity Identifier (UEI): F6XLTRUQJEN4
Parent UEI:
NSF Program(s): HCC-Human-Centered Computing
Primary Program Source: 01001516DB NSF RESEARCH & RELATED ACTIVIT
Program Reference Code(s): 7367, 7453, 8228, 9150, 9251
Program Element Code(s): 736700
Award Agency Code: 4900
Fund Agency Code: 4900
Assistance Listing Number(s): 47.070

ABSTRACT

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.

PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH

Note:  When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

(Showing: 1 - 10 of 19)
Haiming Zhao, Weiwei Xu, Kun Zhou, Yin Yang, Xiaogang Jin, Hongzhi Wu "Stress Constrained Thickness Optimization for Shell Object Fabrication" Computer Graphics Forum , v.36 , 2017 , p.368-380
Huamin Wang and Yin Yang "Descent Methods for Elastic Body Simulation on the GPU" ACM Transactions on Graphics , v.35 , 2016 , p.212
Kele Xu, Yin Yang, Maureen Stone, Aurore Jaumard-Hakoun, Clemence Leboullenger, Ger-ard Dreyfus, Pierre Roussel, and Bruce Denby "Robust contour tracking in ultrasound tongueimage sequences" Clinical Linguistics and Phonetics , v.30 , 2016 , p.313-327
Kele Xu, Yin Yang, Maureen Stone, Aurore Jaumard-Hakoun, Clemence Leboullenger, Gerard Dreyfus, Pierre Roussel, and Bruce Denby, "Robust contour tracking in ultrasound tongue image sequences" Clinical Linguistics and Phonetics , v.30 , 2016 , p.313-27 10.3109/02699206.2015.1110714
Mingliang Xu, Mingyuan Li, Weiwei Xu, Zhigang Deng, Yin Yang, Kun Zhou "Interactive Mechanism Modeling from Multi-view Images" ACM Transactions on Graphics , v.35 , 2016 , p.236
Ran Luo, Huamin Wang, Weiwei Xu, Kun Zhou and Yin Yang "DeepWarp: DNN-based Nonlinear Deformation" arXiv preprint , 2018
Ran Luo, Lifeng Zhu, Weiwei Xu, Patrick Kelley, Vanessa Svihla, Yin Yang "InteractiveDesign and Simulation of Tubular Supporting Structure" Graphical Models, , v.80 , 2015 , p.16-30
Ran Luo, Lifeng Zhu, Weiwei Xu, Patrick  Kelley, Vanessa  Svihla, Yin Yang "Interactive Design and Simulation of Tubular Supporting Structure" Graphical Models , 2015
Ran Luo, Qiang Fang, Jianguo Wei, Wenhuan Lu, Weiwei Xu, and Yin Yang "Acoustic VR in the mouth: A real-time speech-driven visual tongue system" In Virtual Reality (VR), 2017 IEEE , 2017 , p.112-212
Tianjia Shao, Yin Yang, Yanlin Weng, Qiming Hou, Kun Zhou "H-CNN: Spatial Hashing Based CNN for 3D Shape Analysis" arXiv preprint , 2018
Wang, Huamin and Yang, Yin "Descent Methods for Elastic Body Simulation on the GPU" ACM Trans. Graph. , v.35 , 2016 , p.212:1--21 10.1145/2980179.2980236
(Showing: 1 - 10 of 19)

PROJECT OUTCOMES REPORT

Disclaimer

This Project Outcomes Report for the General Public is displayed verbatim as submitted by the Principal Investigator (PI) for this award. Any opinions, findings, and conclusions or recommendations expressed in this Report are those of the PI and do not necessarily reflect the views of the National Science Foundation; NSF has not approved or endorsed its content.

This project pivots on the transformative concept of divide-and-conquer deformable model. Unlike most state-of-the-art techniques that simulate the deformable object entirely, the proposal investigates innovative algorithms that break the simulation into independent computational modules. The final result is obtained by incrementally assembling local computations, instead of using a “one-stop” solver. The proposal seeks theoretical solutions to two general questions: “how to smartly divide” and “how to effectively conquer” in the context of the deformable simulation.

 

The dividing part, as its name implies, seeks for a novel mechanism that is able to partition the original simulation task into multiple sub-tasks, which share the similar structure of the original problem. We found two solutions to attack this technical challenge. The first one is relatively more straightforward. As the domain of deformable simulation is typically discretized by a set of interconnected small elements, which is referred to as a finite element mesh, we can subdivide the original input mesh into sub meshes and perform the simulation at each sub mesh in parallel. Because the size of local dynamics system at each sub mesh is smaller than the original one. Simulation becomes much less expensive and its parallelization on multi-core CPU or GPU is straightforward. However, the partition of the domain could significantly influence the convergence of the global system. In this project, we found that Voronoi diagram provides an elegant solution to this problem because it tends to maximize the volume of each Voronoi cell while minimizing the interface. Another more interesting observation was, the domain can also be defined spectrally as a fragment over the entire spectrum of the dynamic system. In other words, a domain is responsible for a band of the nonlinear vibrational behavior of the deformable body or a set of deformation behaviors. This finding significantly advances the current deformable simulation state-of-the-art. Because we can now explicitly customize the simulation with desired animation effects.

 

Unfortunately, existing method to understand the spectrum of a dynamic system heavily depends on modal analysis. This requires solving large-scale spare eigen value problem and it is difficult to be generalized to handle nonlinear cases (i.e. when the shape of the soft object deviates away from its rest shape). In this project, we also develop a novel spectral analysis and we call this method inertia analysis. We try to understand the dynamic behavior of a deformable simulation from a physics point of view. The final equilibrium of the system is achieved by balancing internal and external forces. However, in order to generate the necessary internal force, the deformable body must be deformed, which yields displacement. Clearly, in real cases acceleration will be triggered to push a static rest shape into a certain deformed one. This acceleration, if seen from a local non-inertia frame, brings the system secondary deformations. Such analysis continues until the acceleration is so small that can be completely ignored. This elegant physical procedure can be formulated in a set of surprisingly simply equations, which can be easily solved by existing numerical libraries and extended for nonlinear cases.

 

The conquer part, meaning how to combine the local solutions into a global one, is another important aspect of this project. We design new blending algorithm to facilitate this purpose. We found that this conquer problem is essentially NP-hard as it can be formulated as a QCQP optimization problem. However, we find its theoretical optimal solution because it only evokes low-rank equality constraints.  And the solution can be obtained by solving a local nonlinear equilibrium problem.

 

The investigated novel plug-and-play simulation is particularly suitable for large-scale, precision-demanding CAD system. This is because during the users frequently edit and adapt the local geometry of a certain CAD design, for instance, changing the shape of the handle of a teapot, while the other parts of the 3D models remain unchanged. With existing simulation packages, high-resolution models need lengthy and expensive simulation every time the geometry is updated. However, with our new algorithmic methodology, we are able to significantly accelerate the simulation module in the simulation-in-the-loop CAD procedure. We have demonstrated the capability of such system in various computer-aided design and fabrication applications.

 

This project yields profound impacts on many areas other than computer graphics. For instance, the developed algorithms have been successfully applied to model CAV-enabled transportation system, to simulate complex nonlinear dynamics of human tissue and to detect the roadway pavement defects with the help of inexpensive depth sensor. The inspiring and encouraging results obtained from this project also successful help the PI to receive another relevant NSF grant so that the team can continue on this fascinating fundamental computer graphics problem. 

 


Last Modified: 05/13/2018
Modified by: Yin Yang

Please report errors in award information by writing to: awardsearch@nsf.gov.

Print this page

Back to Top of page