Graph Partitioning Algorithms for Rigid Body Simulations
| dc.contributor.author | Liu, Yinchu | en_US |
| dc.contributor.author | Andrews, Sheldon | en_US |
| dc.contributor.editor | Pelechano, Nuria | en_US |
| dc.contributor.editor | Vanderhaeghe, David | en_US |
| dc.date.accessioned | 2022-04-22T08:16:18Z | |
| dc.date.available | 2022-04-22T08:16:18Z | |
| dc.date.issued | 2022 | |
| dc.description.abstract | We propose several graph partitioning algorithms for improving the performance of rigid body simulations. The algorithms operate on the graph formed by rigid bodies (nodes) and constraints (edges), producing non-overlapping and contiguous sub-systems that can be simulated in parallel by a domain decomposition technique. We demonstrate that certain partitioning algorithms reduce the computational time of the solver, and graph refinement techniques that reduce coupling between sub-systems, such as the Kernighan-Lin and Fiduccia-Mattheyses algorithms, give additional performance improvements. | en_US |
| dc.description.sectionheaders | Animation and Simulation | |
| dc.description.seriesinformation | Eurographics 2022 - Short Papers | |
| dc.identifier.doi | 10.2312/egs.20221036 | |
| dc.identifier.isbn | 978-3-03868-169-4 | |
| dc.identifier.issn | 1017-4656 | |
| dc.identifier.pages | 73-76 | |
| dc.identifier.pages | 4 pages | |
| dc.identifier.uri | https://doi.org/10.2312/egs.20221036 | |
| dc.identifier.uri | https://diglib.eg.org:443/handle/10.2312/egs20221036 | |
| dc.publisher | The Eurographics Association | en_US |
| dc.rights | Attribution 4.0 International License | |
| dc.rights.uri | https://creativecommons.org/licenses/by/4.0/ | |
| dc.subject | CCS Concepts: Computing methodologies --> Physical simulation; Mathematics of computing --> Graph algorithms | |
| dc.subject | Computing methodologies | |
| dc.subject | Physical simulation | |
| dc.subject | Mathematics of computing | |
| dc.subject | Graph algorithms | |
| dc.title | Graph Partitioning Algorithms for Rigid Body Simulations | en_US |