
NSF Org: |
IIS Division of Information & Intelligent Systems |
Recipient: |
|
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: |
|
History of Investigator: |
|
Recipient Sponsored Research Office: |
1 UNIVERSITY OF NEW MEXICO ALBUQUERQUE NM US 87131-0001 (505)277-4186 |
Sponsor Congressional District: |
|
Primary Place of Performance: |
NM US 87131-0001 |
Primary Place of
Performance Congressional District: |
|
Unique Entity Identifier (UEI): |
|
Parent UEI: |
|
NSF Program(s): | HCC-Human-Centered Computing |
Primary Program Source: |
|
Program Reference Code(s): |
|
Program Element Code(s): |
|
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.
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.