{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,27]],"date-time":"2026-01-27T23:52:43Z","timestamp":1769557963296,"version":"3.49.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2026,4,30]]},"abstract":"<jats:p>\n                    This work addresses the challenges of distributing large physics-based simulations often encountered in the visual effects industry. These simulations, based on partial differential equations, model complex phenomena such as free surface liquids, flames, and explosions, and are characterized by domains whose shapes and topologies evolve rapidly. In this context, we propose a novel partitioning algorithm employing\n                    <jats:italic toggle=\"yes\">optimal transport<\/jats:italic>\n                    \u2014which produces a power diagram\u2014and designed to handle a vast variety of simulation domain shapes undergoing rapid changes over time. Our\n                    <jats:italic toggle=\"yes\">Power partitioner<\/jats:italic>\n                    ensures an even distribution of computational tasks, reduces inter-node data exchange, and maintains temporal consistency, all while being intuitive and artist-friendly. To quantify partitioning quality we introduce two metrics, the surface index and the temporal consistency index, which we leverage in a range of comparisons on real-world film production data, showing that our method outperforms the state of the art in a majority of cases.\n                  <\/jats:p>","DOI":"10.1145\/3787521","type":"journal-article","created":{"date-parts":[[2026,1,14]],"date-time":"2026-01-14T20:14:45Z","timestamp":1768421685000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["A practical partitioner for distributed simulations on sparse dynamic domains using optimal transport"],"prefix":"10.1145","volume":"45","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6375-4315","authenticated-orcid":false,"given":"Joel","family":"Wretborn","sequence":"first","affiliation":[{"name":"W\u0113t\u0101 FX","place":["Stockholm, Sweden"]},{"name":"University of Waterloo","place":["Stockholm, Sweden"]}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-7880-5179","authenticated-orcid":false,"given":"Marcus","family":"Schoo","sequence":"additional","affiliation":[{"name":"W\u0113t\u0101 FX","place":["Queenstown, New Zealand"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1126-7419","authenticated-orcid":false,"given":"Noh-Hoon","family":"Lee","sequence":"additional","affiliation":[{"name":"W\u0113t\u0101 FX","place":["Seoul, South Korea"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3830-7772","authenticated-orcid":false,"given":"Christopher","family":"Batty","sequence":"additional","affiliation":[{"name":"University of Waterloo","place":["Waterloo, Canada"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5081-9108","authenticated-orcid":false,"given":"Alexey","family":"Stomakhin","sequence":"additional","affiliation":[{"name":"W\u0113t\u0101 FX","place":["Mililani, United States"]}]}],"member":"320","published-online":{"date-parts":[[2026,1,27]]},"reference":[{"key":"e_1_3_2_2_1","volume-title":"ACM SIGGRAPH 2015 Talks","author":"Bailey Dan","year":"2015","unstructured":"Dan Bailey, Harry Biddle, Nick Avramoussis, and Matthew Warner. 2015. Distributing liquids using OpenVDB. In ACM SIGGRAPH 2015 Talks. ACM, New York, NY, USA."},{"issue":"5","key":"e_1_3_2_3_1","first-page":"570","article-title":"A partitioning strategy for nonuniform problems on multiprocessors","volume":"36","year":"1987","unstructured":"Berger and Bokhari. 1987. A partitioning strategy for nonuniform problems on multiprocessors. IEEE Trans. Comput. C-36, 5 (May1987), 570\u2013580.","journal-title":"IEEE Trans. Comput."},{"key":"e_1_3_2_4_1","volume-title":"ACM SIGGRAPH Talks","author":"Bojsen-Hansen Morten","year":"2021","unstructured":"Morten Bojsen-Hansen, Michael Bang Nielsen, Konstantinos Stamatelos, and Robert Bridson. 2021. Spatially adaptive volume tools in bifrost. In ACM SIGGRAPH Talks."},{"key":"e_1_3_2_5_1","doi-asserted-by":"crossref","unstructured":"Ricard Borrell Guillermo Oyarzun Damien Dosimont and Guillaume Houzeaux. 2020. Parallel SFC-based mesh partitioning and load balancing. arXiv [physics.comp-ph] (July 2020).","DOI":"10.1109\/ScalA49573.2019.00014"},{"key":"e_1_3_2_6_1","volume-title":"Computational Aspects of Dynamic Surfaces","author":"Bridson Robert Edward","year":"2003","unstructured":"Robert Edward Bridson. 2003. Computational Aspects of Dynamic Surfaces. Ph. D. Dissertation. Stanford, CA, USA."},{"key":"e_1_3_2_7_1","volume-title":"Numerical Solution of Partial Differential Equations on Parallel Computers (2006 ed.)","author":"Bruaset Magnus","year":"2005","unstructured":"Magnus Bruaset and Aslak Tveito (Eds.). 2005. Numerical Solution of Partial Differential Equations on Parallel Computers (2006 ed.). Springer, Berlin, Germany."},{"key":"e_1_3_2_8_1","article-title":"Blue noise through optimal transport","author":"Goes Fernando de","year":"2012","unstructured":"Fernando de Goes, Katherine Breeden, Victor Ostromoukhov, and Mathieu Desbrun. 2012. Blue noise through optimal transport. ACM Trans. Graph. 31, 6 (November 2012), 1\u201311.","journal-title":"ACM Trans. Graph."},{"issue":"4","key":"e_1_3_2_9_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2766901","article-title":"Power particles: An incompressible fluid solver based on power diagrams","volume":"34","author":"Goes Fernando de","year":"2015","unstructured":"Fernando de Goes, Corentin Wallez, Jin Huang, Dmitry Pavlov, and Mathieu Desbrun. 2015. Power particles: An incompressible fluid solver based on power diagrams. ACM Trans. Graph. 34, 4 (July2015), 1\u201311.","journal-title":"ACM Trans. Graph."},{"key":"e_1_3_2_10_1","volume-title":"ACM SIGGRAPH 2023 Talks (SIGGRAPH \u201923)","author":"Edholm John","year":"2023","unstructured":"John Edholm, Alexey Stomakhin, Rahul Deshprabhu, David Caeiro Cebrian, Florian Hu, and Caitlin Pope. 2023. Fire and explosions in Avatar: The way of water. In ACM SIGGRAPH 2023 Talks (SIGGRAPH \u201923)."},{"key":"e_1_3_2_11_1","volume-title":"SIGGRAPH 2009: Talks","author":"Flores Lucio","year":"2009","unstructured":"Lucio Flores and David Horsley. 2009. Underground cave sequence for Land of the Lost. In SIGGRAPH 2009: Talks. ACM, New York, NY, USA."},{"issue":"6","key":"e_1_3_2_12_1","first-page":"1","article-title":"A polynomial particle-in-cell method","volume":"36","author":"Fu Chuyuan","year":"2017","unstructured":"Chuyuan Fu, Qi Guo, Theodore Gast, Chenfanfu Jiang, and Joseph Teran. 2017a. A polynomial particle-in-cell method. ACM Trans. Graph. 36, 6 (Nov.2017), 1\u201312.","journal-title":"ACM Trans. Graph."},{"key":"e_1_3_2_13_1","doi-asserted-by":"crossref","unstructured":"Lin Fu Xiangyu Y Hu and Nikolaus A Adams. 2017. A physics-motivated Centroidal Voronoi Particle domain decomposition method. J. Comput. Phys. 335 (April 2017) 718\u2013735.","DOI":"10.1016\/j.jcp.2017.01.051"},{"key":"e_1_3_2_14_1","volume-title":"SIGGRAPH\u201906","author":"Irving Geoffrey","year":"2006","unstructured":"Geoffrey Irving, Eran Guendelman, Frank Losasso, and Ronald Fedkiw. 2006. Efficient simulation of large bodies of water by coupling two and three dimensional techniques. In SIGGRAPH\u201906. ACM Press, New York, New York, USA."},{"key":"e_1_3_2_15_1","volume-title":"Proceedings of the Eighth Annual Conference on Object-Oriented Programming Systems, Languages, and Applications","author":"Kale Laxmikant V.","year":"1993","unstructured":"Laxmikant V. Kale and Sanjeev Krishnan. 1993. CHARM++. In Proceedings of the Eighth Annual Conference on Object-Oriented Programming Systems, Languages, and Applications. ACM, New York, NY, USA."},{"key":"e_1_3_2_16_1","article-title":"METIS Manual: A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices","author":"Karypis George","year":"2013","unstructured":"George Karypis. 2013. METIS Manual: A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices. Retrieved from https:\/\/github.com\/KarypisLab\/METIS\/blob\/master\/manual\/manual.pdfAccessed: 2025-4-13.","journal-title":"https:\/\/github.com\/KarypisLab\/METIS\/blob\/master\/manual\/manual.pdf"},{"issue":"1","key":"e_1_3_2_17_1","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1137\/S1064827595287997","article-title":"A fast and high quality multilevel scheme for partitioning irregular graphs","volume":"20","author":"Karypis George","year":"1998","unstructured":"George Karypis and Vipin Kumar. 1998. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20, 1 (Jan.1998), 359\u2013392.","journal-title":"SIAM J. Sci. Comput."},{"key":"e_1_3_2_18_1","doi-asserted-by":"crossref","unstructured":"R. Koradi M. Billeter and P. G\u00fcntert. 2000. Point-centered domain decomposition for parallel molecular dynamics simulation. Comput. Phys. Commun. 124 2\u20133 (February 2000) 139\u2013147.","DOI":"10.1016\/S0010-4655(99)00436-1"},{"key":"e_1_3_2_19_1","volume-title":"ACM SIGGRAPH 2016 Talks","author":"Lait Jeff","year":"2016","unstructured":"Jeff Lait. 2016. Inside houdini\u2019s distributed solver system. In ACM SIGGRAPH 2016 Talks. ACM, New York, NY, USA."},{"issue":"4","key":"e_1_3_2_20_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3528223.3530058","article-title":"Loki: A unified multiphysics simulation framework for production","volume":"41","author":"Lesser Steve","year":"2022","unstructured":"Steve Lesser, Alexey Stomakhin, Gilles Daviet, Joel Wretborn, John Edholm, Noh-Hoon Lee, Eston Schweickart, Xiao Zhai, Sean Flynn, and Andrew Moffat. 2022. Loki: A unified multiphysics simulation framework for production. ACM Trans. Graph. 41, 4 (July2022), 1\u201320.","journal-title":"ACM Trans. Graph."},{"key":"e_1_3_2_21_1","doi-asserted-by":"crossref","unstructured":"S. Lloyd. 1982. Least squares quantization in PCM. IEEE Trans. Inf. Theory 28 2 (March 1982) 129\u2013137.","DOI":"10.1109\/TIT.1982.1056489"},{"issue":"4","key":"e_1_3_2_22_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3072959.3073671","article-title":"Variance-minimizing transport plans for inter-surface mapping","volume":"36","author":"Mandad Manish","year":"2017","unstructured":"Manish Mandad, David Cohen-Steiner, Leif Kobbelt, Pierre Alliez, and Mathieu Desbrun. 2017. Variance-minimizing transport plans for inter-surface mapping. ACM Trans. Graph. 36, 4 (Aug.2017), 1\u201314.","journal-title":"ACM Trans. Graph."},{"issue":"4","key":"e_1_3_2_23_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2010324.1964932","article-title":"Efficient elasticity for character skinning with contact and collisions","volume":"30","author":"McAdams Aleka","year":"2011","unstructured":"Aleka McAdams, Yongning Zhu, Andrew Selle, Mark Empey, Rasmus Tamstorf, Joseph Teran, and Eftychios Sifakis. 2011. Efficient elasticity for character skinning with contact and collisions. ACM Trans. Graph. 30, 4 (July2011), 1\u201312.","journal-title":"ACM Trans. Graph."},{"issue":"3","key":"e_1_3_2_24_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2487228.2487235","article-title":"VDB: High-resolution sparse volumes with dynamic topology","volume":"32","author":"Museth Ken","year":"2013","unstructured":"Ken Museth. 2013. VDB: High-resolution sparse volumes with dynamic topology. ACM Trans. Graph. 32, 3 (June2013), 1\u201322.","journal-title":"ACM Trans. Graph."},{"key":"e_1_3_2_25_1","volume-title":"Supercomputing","author":"Pearce Olga","year":"2012","unstructured":"Olga Pearce, Todd Gamblin, Bronis R. de Supinski, Martin Schulz, and Nancy M. Amato. 2012. Quantifying the effectiveness of load balance algorithms. In Supercomputing."},{"key":"e_1_3_2_26_1","doi-asserted-by":"crossref","unstructured":"Gabriel Peyr\u00e9 and Marco Cuturi. 2019. Computational optimal transport: With applications to data science. Foundations and Trends\u00ae in Machine Learning 11 5\u20136 (2019) 355\u2013607.","DOI":"10.1561\/2200000073"},{"key":"e_1_3_2_27_1","article-title":"A sparse distributed gigascale resolution material point method","author":"Qiu Yuxing","year":"2022","unstructured":"Yuxing Qiu, Samuel Temple Reeve, Minchen Li, Yin Yang, Stuart R. Slattery, and Chenfanfu Jiang. 2022. A sparse distributed gigascale resolution material point method. ACM Trans. Graph. (November2022).","journal-title":"ACM Trans. Graph."},{"issue":"4","key":"e_1_3_2_28_1","first-page":"1","article-title":"The power particle-in-cell method","volume":"41","author":"Qu Ziyin","year":"2022","unstructured":"Ziyin Qu, Minchen Li, Fernando De Goes, and Chenfanfu Jiang. 2022. The power particle-in-cell method. ACM Trans. Graph. 41, 4 (July2022), 1\u201313.","journal-title":"ACM Trans. Graph."},{"issue":"6","key":"e_1_3_2_29_1","first-page":"1","article-title":"Power plastics: A hybrid Lagrangian\/Eulerian solver for mesoscale inelastic flows","volume":"42","author":"Qu Ziyin","year":"2023","unstructured":"Ziyin Qu, Minchen Li, Yin Yang, Chenfanfu Jiang, and Fernando De Goes. 2023. Power plastics: A hybrid Lagrangian\/Eulerian solver for mesoscale inelastic flows. ACM Trans. Graph. 42, 6 (Dec.2023), 1\u201311.","journal-title":"ACM Trans. Graph."},{"key":"e_1_3_2_30_1","first-page":"491","volume-title":"Sourcebook of Parallel Computing","author":"Schloegel Kirk","year":"2003","unstructured":"Kirk Schloegel, George Karypis, and Vipin Kumar. 2003. Graph partitioning for high-performance scientific simulations. In Sourcebook of Parallel Computing. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 491\u2013541."},{"issue":"6","key":"e_1_3_2_31_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2661229.2661269","article-title":"SPGrid: A sparse paged grid structure applied to adaptive smoke simulation","volume":"33","author":"Setaluri Rajsekhar","year":"2014","unstructured":"Rajsekhar Setaluri, Mridul Aanjaneya, Sean Bauer, and Eftychios Sifakis. 2014. SPGrid: A sparse paged grid structure applied to adaptive smoke simulation. ACM Trans. Graph. 33, 6 (Nov.2014), 1\u201312.","journal-title":"ACM Trans. Graph."},{"issue":"8","key":"e_1_3_2_32_1","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1111\/cgf.13510","article-title":"Distributing and load balancing sparse fluid simulations","volume":"37","author":"Shah C.","year":"2018","unstructured":"C. Shah, D. Hyde, H. Qu, and P. Levis. 2018. Distributing and load balancing sparse fluid simulations. Comput. Graph. Forum 37, 8 (Dec.2018), 35\u201346.","journal-title":"Comput. Graph. Forum"},{"key":"e_1_3_2_33_1","unstructured":"Justin Solomon. 2018. Optimal transport on discrete domains. arXiv [math.OC] (January 2018)."},{"issue":"4","key":"e_1_3_2_34_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2766963","article-title":"Convolutional wasserstein distances","volume":"34","author":"Solomon Justin","year":"2015","unstructured":"Justin Solomon, Fernando de Goes, Gabriel Peyr\u00e9, Marco Cuturi, Adrian Butscher, Andy Nguyen, Tao Du, and Leonidas Guibas. 2015. Convolutional wasserstein distances. ACM Trans. Graph. 34, 4 (July2015), 1\u201311.","journal-title":"ACM Trans. Graph."},{"key":"e_1_3_2_35_1","volume-title":"SIGGRAPH \u201999","author":"Stam Jos","year":"1999","unstructured":"Jos Stam. 1999. Stable fluids. In SIGGRAPH \u201999. ACM."},{"key":"e_1_3_2_36_1","doi-asserted-by":"crossref","unstructured":"Alexey Stomakhin Steve Lesser Joel Wretborn Sean Flynn Johnathan Nixon Nicholas Illingworth Adrien Rollet Kevin Blom and Douglas Mchale. 2023. Pahi: A unified water pipeline and toolset. In Proceedings of the Digital Production Symposium (DigiPro\u201923) Association for Computing Machinery New York NY USA 1\u201313.","DOI":"10.1145\/3603521.3604291"},{"key":"e_1_3_2_37_1","doi-asserted-by":"crossref","unstructured":"Igor Surmin Alexei Bashinov Sergey Bastrakov Evgeny Efimenko Arkady Gonoskov and Iosif Meyerov. 2015. Dynamic load balancing based on rectilinear partitioning in particle-in-cell plasma simulation. Springer.","DOI":"10.1007\/978-3-319-21909-7_12"},{"key":"e_1_3_2_38_1","volume-title":"2016 7th Workshop on Latest Advances in Scalable Algorithms for Large-Scale Systems (ScalA)","author":"Tsuzuki Satori","year":"2016","unstructured":"Satori Tsuzuki and Takayuki Aoki. 2016. Effective dynamic load balance using space-filling curves for large-scale SPH simulations on GPU-rich supercomputers. In 2016 7th Workshop on Latest Advances in Scalable Algorithms for Large-Scale Systems (ScalA). IEEE."},{"issue":"3","key":"e_1_3_2_39_1","doi-asserted-by":"crossref","first-page":"921","DOI":"10.1145\/1073204.1073284","article-title":"Water drops on surfaces","volume":"24","author":"Wang Huamin","year":"2005","unstructured":"Huamin Wang, Peter J. Mucha, and Greg Turk. 2005. Water drops on surfaces. ACM Trans. Graph. 24, 3 (July2005), 921\u2013929.","journal-title":"ACM Trans. Graph."},{"issue":"4","key":"e_1_3_2_40_1","article-title":"A massively parallel and scalable multi-GPU material point method","volume":"39","author":"Wang Xinlei","year":"2020","unstructured":"Xinlei Wang, Yuxing Qiu, Stuart R. Slattery, Yu Fang, Minchen Li, Song-Chun Zhu, Yixin Zhu, Min Tang, Dinesh Manocha, and Chenfanfu Jiang. 2020. A massively parallel and scalable multi-GPU material point method. ACM Trans. Graph. 39, 4 (August2020).","journal-title":"ACM Trans. Graph."},{"key":"e_1_3_2_41_1","doi-asserted-by":"crossref","DOI":"10.1111\/cgf.70033","article-title":"A unified multi-scale method for simulating immersed bubbles","author":"Wretborn Joel","year":"2025","unstructured":"Joel Wretborn, Alexey Stomakhin, and Christopher Batty. 2025. A unified multi-scale method for simulating immersed bubbles. Comput. Graph. Forum (April2025).","journal-title":"Comput. Graph. Forum"},{"issue":"6","key":"e_1_3_2_42_1","doi-asserted-by":"crossref","first-page":"2234","DOI":"10.1109\/TVCG.2018.2886322","article-title":"Fluid simulation with adaptive staggered power particles on GPUs","volume":"26","author":"Zhai Xiao","year":"2020","unstructured":"Xiao Zhai, Fei Hou, Hong Qin, and Aimin Hao. 2020. Fluid simulation with adaptive staggered power particles on GPUs. IEEE Trans. Vis. Comput. Graph. 26, 6 (June2020), 2234\u20132246.","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"issue":"2","key":"e_1_3_2_43_1","first-page":"1","article-title":"An efficient multigrid method for the simulation of high-resolution elastic solids","volume":"29","author":"Zhu Yongning","year":"2010","unstructured":"Yongning Zhu, Eftychios Sifakis, Joseph Teran, and Achi Brandt. 2010. An efficient multigrid method for the simulation of high-resolution elastic solids. ACM Trans. Graph. 29, 2 (March2010), 1\u201318.","journal-title":"ACM Trans. Graph."}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3787521","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,27]],"date-time":"2026-01-27T10:33:49Z","timestamp":1769510029000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3787521"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,27]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,4,30]]}},"alternative-id":["10.1145\/3787521"],"URL":"https:\/\/doi.org\/10.1145\/3787521","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,27]]},"assertion":[{"value":"2025-06-25","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-11-25","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-01-27","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}