Parallel Constraint Graph Partitioning and Coloring for Realtime Soft-Body Cutting

Simple item page
dc.contributor.authorYu, Pengen_US
dc.contributor.authorWang, Ruiqien_US
dc.contributor.authorLi, Chunleien_US
dc.contributor.authorLi, Yuxuanen_US
dc.contributor.authorZhai, Xiaoen_US
dc.contributor.authorHe, Yuanboen_US
dc.contributor.authorWu, Hongyuen_US
dc.contributor.authorHao, Aiminen_US
dc.contributor.authorGao, Yangen_US
dc.contributor.editorChristie, Marcen_US
dc.contributor.editorHan, Ping-Hsuanen_US
dc.contributor.editorLin, Shih-Syunen_US
dc.contributor.editorPietroni, Nicoen_US
dc.contributor.editorSchneider, Teseoen_US
dc.contributor.editorTsai, Hsin-Rueyen_US
dc.contributor.editorWang, Yu-Shuenen_US
dc.contributor.editorZhang, Eugeneen_US
dc.date.accessioned2025-10-07T06:03:03Z
dc.date.available2025-10-07T06:03:03Z
dc.date.issued2025
dc.description.abstractReal-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.en_US
dc.description.sectionheadersPhysical Simulation
dc.description.seriesinformationPacific Graphics Conference Papers, Posters, and Demos
dc.identifier.doi10.2312/pg.20251267
dc.identifier.isbn978-3-03868-295-0
dc.identifier.pages12 pages
dc.identifier.urihttps://doi.org/10.2312/pg.20251267
dc.identifier.urihttps://diglib.eg.org/handle/10.2312/pg20251267
dc.publisherThe Eurographics Associationen_US
dc.rightsAttribution 4.0 International License
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/
dc.subjectCCS Concepts: Computing methodologies → Computer Graphics
dc.subjectComputing methodologies → Computer Graphics
dc.titleParallel Constraint Graph Partitioning and Coloring for Realtime Soft-Body Cuttingen_US
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
pg20251267.pdf
Size:
16.31 MB
Format:
Adobe Portable Document Format
Download
Collections
PG2025 Conference Papers, Posters, and Demos