Parallel Constraint Graph Partitioning and Coloring for Realtime Soft-Body Cutting
Loading...
Date
2025
Journal Title
Journal ISSN
Volume Title
Publisher
The Eurographics Association
Abstract
Real-time simulation of cutting is essential in fields requiring accurate interactions with digital assets, such as virtual manufacturing or surgical training. While Extended Position-Based Dynamics (XPBD) methods are valued for their numerical stability, their reliance on the Gauss-Seidel method leads to two critical limitations when facing high degrees of freedom: the residual stagnation that hinders convergence within limited temporal budget, and a fundamentally sequential nature that limits parallelization, thereby impeding real-time performance. Traditional parallelization approaches often rely on precomputed topological data that becomes outdated during mesh evolution, resulting in suboptimal performance in cutting applications. To address this limitation, this paper introduces a GPU-accelerated algorithm featuring an efficient constraint clustering preprocessing step to accelerate initial solver scheduling, combined with a novel graph coloring technique using GPU-optimized Shortcuts principles for parallel constraint resolution. Experiments show our combination of upfront clustering and dynamic graph re-coloring outperforms existing parallel XPBD implementations, empowering efficient solvers in virtual surgery, product design, and similar scenarios involving continuous geometry updates.
Description
CCS Concepts: Computing methodologies → Computer Graphics
@inproceedings{10.2312:pg.20251267,
booktitle = {Pacific Graphics Conference Papers, Posters, and Demos},
editor = {Christie, Marc and Han, Ping-Hsuan and Lin, Shih-Syun and Pietroni, Nico and Schneider, Teseo and Tsai, Hsin-Ruey and Wang, Yu-Shuen and Zhang, Eugene},
title = {{Parallel Constraint Graph Partitioning and Coloring for Realtime Soft-Body Cutting}},
author = {Yu, Peng and Wang, Ruiqi and Li, Chunlei and Li, Yuxuan and Zhai, Xiao and He, Yuanbo and Wu, Hongyu and Hao, Aimin and Gao, Yang},
year = {2025},
publisher = {The Eurographics Association},
ISBN = {978-3-03868-295-0},
DOI = {10.2312/pg.20251267}
}