CHS: Small: Towards Next-Generation Large-Scale Nonlinear Deformable Simulation

利用数字计算机精确地模拟在外部相互作用下变形的软物体是广泛的科学和工程领域中的基本问题。 例如，如果不能提供真实的力-位移响应，虚拟手术培训几乎没有效果，并为用户提供误导性的体验。 在过去的十年中，可变形模型的仿真自由度（DOF）的数量从数百增加到数十万甚至数百万。 已经变得越来越强大的计算硬件对这一发展做出了重大贡献，但不幸的是，在未来计算机模拟不太可能继续从增加的处理器频率中显着受益。 事实上，在过去的几年里，芯片行业已经将重点从更快的处理器时钟转移到多核架构上。 另一方面，随着先进采集设备/技术的广泛采用，计算机可以处理的数据的复杂性和规模呈指数级增长，并且大规模几何形状在现代3D数据处理中变得无处不在。 这个数据爆炸的新时代对可变形仿真提出了前所未有的挑战。 现有的方法通常使用一站式求解器来计算系统的所有未知自由度，但由于底层的高维数值积分，这是计算密集型的。 即使使用最先进的硬件，对于大规模场景，可变形模拟仍然需要数小时，数天甚至数周。 显然，传统的仿真方法不能很好地适应分布式计算资源分配，并且随着越来越大的数据集变得越来越麻烦。 这就要求为大规模几何复杂和非线性可变形模型重新设计算法框架和专用数值程序，以支持下一代图形应用程序。 受这些重大挑战的激励，本项目系统地研究了一系列理论进步、计算技术和数值实现，这些进展将大规模非线性可变形模型的前沿推向“后摩尔定律”。“具体而言，研究的学术价值将包括以下几个方面： 本计画将设计一个以区域分解为基础的平行变形模拟器。 通过削弱域间的联系，域级计算变得独立和可并行。 耦合机制将被推广和丰富，使非协调和重叠的区域分解成为可能。 这包括在指定的硬件配置下对域细分进行深入优化。 仿真的可重用性将通过一种称为蜂窝域的新技术得到进一步提高。 该项目将加深目前对大规模模型简化的理解，并在并行计算的背景下重新打造这一有用的工具。 特别是，如何利用幂迭代来获得谱分析将被探索。 此外，基于几何的简化直接决定了减少的自由度，即使在施加的极端约束下也具有更鲁棒的模拟。 一个论证充分的计算理论是不太可行的，除非封装在一套精心设计的实现。 相应地，该项目还将设计定制的数值程序与建议的算法技术配对，整个模拟框架将通过利用独特的数据模式，数值行为和问题结构在系统级，求解器级和子求解器级进行微调域分解可变形模型。 作为一个实验平台，该项目将开发一个新的实时人类舌头运动可视化系统。 超过8%的美国儿童患有沟通或吞咽障碍。 基于新的变形求解器，将开发一个超声成像驱动的实时人类舌头可视化系统，以帮助医生和语言治疗师更好地了解这种疾病背后的病理机制，并计划更有效的特定主题的医疗/物理治疗。

Using a digital computer to accurately simulate soft objects that deform under external interactions is a fundamental problem in a wide range of scientific and engineering fields. For example, without being able to deliver a faithful force-displacement response, virtual surgical training is hardly effective and provides users with misleading experiences. In the past decade, the number of simulation degrees of freedom (DOFs) for deformable models has increased from hundreds to hundreds-of-thousands and even millions. Computing hardware that has become more and more powerful has contributed significantly to this development, but unfortunately it is unlikely that in the future computer simulation will continue to benefit dramatically from increased processor frequency. Indeed, in the last few years the chip industry has already moved the emphasis from a faster processor clock to multi-core architectures. On the other hand, with the widespread adoption of advanced acquisition devices/techniques, the complexity and scale of the data that can be handled by computers have grown exponentially, and large-scale geometries are becoming ubiquitous in modern 3D data processing. This new era of data explosion imposes unprecedented challenges on deformable simulation. Existing methods typically use one-stop solvers that calculate all the unknown DOFs of a system, but that is computationally intensive due to the underlying high-dimensional numerical integration. Even with state-of-the-art hardware, deformable simulation can still take hours, days, or even weeks for massive scenarios. Clearly, conventional simulation methodologies fail to well accommodate distributed computing resource allocation, and become more and more cumbersome with bigger and bigger datasets. This calls for rebranded algorithmic frameworks and dedicated numerical procedures for large-scale geometrically-complex and nonlinear deformable models that empower next-generation graphics applications. Motivated by these grand challenges, this project systematically investigates a collection of theoretical advancements, computational techniques, and numerical implementations that push the frontier of large-scale nonlinear deformable models to "post Moore's law." Specifically, the intellectual merit of the research will comprise the following aspects:o The project will devise a theoretically grounded domain decomposition based parallel deformable simulator. By weakening inter-domain linkages, the domain-level computations become independent and parallelizable. The coupling mechanism will be generalized and enriched so that non-conforming and overlapping domain decompositions are made possible. This includes an in-depth optimization of the domain tessellation under specified hardware configurations. Simulation reusability will be further enhanced through a novel technique called cellular domains.o The project will deepen the current understanding of large-scale model reduction and re-forge this useful tool in the context of parallel computing. In particular, how to utilize power iteration to obtain the spectral analysis will be explored. Furthermore, geometry-based reduction directly dictates reduced DOFs and has a more robust simulation even under imposed extreme constraints.o A well-argued computational theory is less practicable unless encapsulated by a set of carefully engineered implementations. Accordingly, the project will also design customized numerical procedures paired with proposed algorithmic techniques, and the entire simulation framework will be fine-tuned at the system level, solver level, and sub-solver level by leveraging unique data patterns, numerical behaviors, and problem structures of domain decomposed deformable models.o As a testbed platform, the project will develop a novel real-time human tongue motion visualization system. Over 8% of U.S. children have a communication or swallowing disorder. Built upon the new deformation solver, an ultrasound-imaging-driven real-time human tongue visualization system will be developed to assist doctors and speech therapists to better understand the pathological mechanism behind this disease and plan more effective subject-specific medical/physical treatments.