Second-order Stencil Descent for Interior-point Hyperelasticity
Second-order Stencil Descent for Interior-point Hyperelasticity
复制标题
DOI：
10.1145/3592104
复制
发表时间：
2023-07
期刊：
影响因子：
--
通讯作者：
L. Lan;Minchen Li;Chenfanfu Jiang;Huamin Wang;Yin Yang
中科院分区：
文献类型：
--
作者：
L. Lan;Minchen Li;Chenfanfu Jiang;Huamin Wang;Yin Yang
在本文中，我们提出了一种用于有限元超弹性模拟的GPU算法。我们表明，已知对稳健的碰撞解决有效的内点法，可以与非牛顿过程相结合，并在GPU上大幅加速。牛顿法已被广泛应用于内点法族，它在每一步都完全求解一个线性系统。之后，与碰撞/接触约束相关的有效集被更新。不幸的是，使用非牛顿优化（如梯度下降或交替方向乘子法）来模拟这一过程并不能带来预期的加速效果。这是因为内点法中使用的障碍函数需要在每次迭代时更新，以严格将搜索限制在可行区域内。相关的成本（例如，每次迭代的连续碰撞检测）很快就会超过GPU带来的好处，因此需要一种新的并行模式。我们的算法受区域分解法的启发，旨在尽可能将与内点相关的计算转移到局部区域。我们通过将每个区域（即模板）限制为单个单元来最小化其大小，以便充分利用现代GPU的能力。模板级别的结果通过一种新颖的混合扫描方案集成到全局更新中。我们的算法是局部二阶的，具有更好的收敛性。它使模拟加速比其CPU对应算法快两个数量级。我们在具有复杂和详细碰撞几何形状的各种模拟场景中展示了我们算法的可扩展性、稳健性、效率和质量。
In this paper, we present a GPU algorithm for finite element hyperelastic simulation. We show that the interior-point method, known to be effective for robust collision resolution, can be coupled with non-Newton procedures and be massively sped up on the GPU. Newton's method has been widely chosen for the interior-point family, which fully solves a linear system at each step. After that, the active set associated with collision/contact constraints is updated. Mimicking this routine using a non-Newton optimization (like gradient descent or ADMM) unfortunately does not deliver expected accelerations. This is because the barrier functions employed in an interior-point method need to be updated at every iteration to strictly confine the search to the feasible region. The associated cost (e.g., per-iteration CCD) quickly overweights the benefit brought by the GPU, and a new parallelism modality is needed. Our algorithm is inspired by the domain decomposition method and designed to move interior-point-related computations to local domains as much as possible. We minimize the size of each domain (i.e., a stencil) by restricting it to a single element, so as to fully exploit the capacity of modern GPUs. The stencil-level results are integrated into a global update using a novel hybrid sweep scheme. Our algorithm is locally second-order offering better convergence. It enables simulation acceleration of up to two orders over its CPU counterpart. We demonstrate the scalability, robustness, efficiency, and quality of our algorithm in a variety of simulation scenarios with complex and detailed collision geometries.