“Unified many-worlds browsing of arbitrary physics-based animations” by Goel and James

Manually tuning physics-based animation parameters to explore a simulation outcome space or achieve desired motion outcomes can be notoriously tedious. This problem has motivated many sophisticated and specialized optimization-based methods for fine-grained (keyframe) control, each of which are typically limited to specific animation phenomena, usually complicated, and, unfortunately, not widely used.In this paper, we propose Unified Many-Worlds Browsing (UMWB), a practical method for sample-level control and exploration of physics-based animations. Our approach supports browsing of large simulation ensembles of arbitrary animation phenomena by using a unified volumetric WORLDPACK representation based on spatiotemporally compressed voxel data associated with geometric occupancy and other low-fidelity animation state. Beyond memory reduction, the WORLDPACK representation also enables unified query support for interactive browsing: it provides fast evaluation of approximate spatiotemporal queries, such as occupancy tests that find ensemble samples (“worlds”) where material is either IN or NOT IN a user-specified spacetime region. WORLDPACKS also support real-time hardware-accelerated voxel rendering by exploiting the spatially hierarchical and temporal RLE raster data structure. Our UMWB implementation supports interactive browsing (and offline refinement) of ensembles containing thousands of simulation samples, and fast spatiotemporal queries and ranking. We show UMWB results using a wide variety of physics-based animation phenomena—not just JELL-O®.

1. Mridul Aanjaneya, Ming Gao, Haixiang Liu, Christopher Batty, and Eftychios Sifakis. 2017. Power Diagrams and Sparse Paged Grids for High Resolution Adaptive Liquids. ACM Trans. Graph. 36, 4, Article 140 (July 2017), 12 pages. Google ScholarDigital Library
2. Okan Arikan. 2006. Compression of Motion Capture Databases. In ACM SIGGRAPH 2006 Papers. 890–897.Google Scholar
3. Jernej Barbič and Jovan Popović. 2008. Real-Time Control of Physically Based Simulations Using Gentle Forces. ACM Trans. Graph. 27, 5, Article 163 (dec 2008), 10 pages. Google ScholarDigital Library
4. Ronen Barzel, John R Hughes, and Daniel N Wood. 1996. Plausible motion simulation for computer graphics animation. In Computer Animation and Simulation’96. Springer, 183–197.Google Scholar
5. Miklós Bergou, Saurabh Mathur, Max Wardetzky, and Eitan Grinspun. 2007. TRACKS: Toward Directable Thin Shells. ACM Trans. Graph. 26, 3 (jul 2007), 50–es. Google ScholarDigital Library
6. Stefan Bruckner and Torsten Möller. 2010. Result-Driven Exploration of Simulation Parameter Spaces for Visual Effects Design. IEEE Transactions on Visualization and Computer Graphics 16, 6 (2010), 1468–1476. Google ScholarDigital Library
7. Stephen Chenney and D. A. Forsyth. 2000. Sampling Plausible Solutions to Multi-Body Constraint Problems. In Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’00). ACM Press/Addison-Wesley Publishing Co., USA, 219–228. Google ScholarDigital Library
8. Albert Chern, Felix Knöppel, Ulrich Pinkall, Peter Schröder, and Steffen Weißmann. 2016. Schrödinger’s smoke. ACM Transactions on Graphics (TOG) 35, 4 (2016), 1–13.Google ScholarDigital Library
9. Michael F. Cohen. 1992. Interactive Spacetime Control for Animation. In Proceedings of the 19th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’92). Association for Computing Machinery, New York, NY, USA, 293–302. Google ScholarDigital Library
10. Brian Curless and Marc Levoy. 1996. A Volumetric Method for Building Complex Models from Range Images. In Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’96). Association for Computing Machinery, New York, NY, USA, 303–312. Google ScholarDigital Library
11. Shen Ding-tao, Cui Can, and Wang Jie-chen. 2008. Implementation and Application of Intersection Operation Based on Run-Length Encoding. In 2008 International Conference on Computer Science and Software Engineering, Vol. 4. 602–606. Google ScholarDigital Library
12. Raanan Fattal and Dani Lischinski. 2004. Target-driven Smoke Animation. In ACM SIGGRAPH 2004 Papers. 441–448.Google Scholar
13. N. Foster and D. Metaxas. 1997. Controlling Fluid Animation. In Proceedings Computer Graphics International. 178–188. Google ScholarCross Ref
14. Jie Guo, Mengtian Li, Zijing Zong, Yuntao Liu, Jingwu He, Yanwen Guo, and Ling-Qi Yan. 2021. Volumetric Appearance Stylization with Stylizing Kernel Prediction Network. ACM Trans. Graph. 40, 4, Article 162 (July 2021), 15 pages. Google ScholarDigital Library
15. Paul S. Heckbert. 1987. Ray Tracing Jell-O® Brand Gelatin. SIGGRAPH Comput. Graph. 21, 4 (aug 1987), 73–74. Google ScholarDigital Library
16. Ben Houston, Michael B. Nielsen, Christopher Batty, Ola Nilsson, and Ken Museth. 2006. Hierarchical RLE Level Set: A Compact and Versatile Deformable Surface Representation. ACM Trans. Graph. 25, 1 (Jan. 2006), 151–175. Google ScholarDigital Library
17. Ben Houston, Mark Wiebe, and Chris Batty. 2004. RLE Sparse Level Sets. In ACM SIGGRAPH 2004 Sketches. 137.Google Scholar
18. Yuanming Hu, Jiafeng Liu, Xuanda Yang, Mingkuan Xu, Ye Kuang, Weiwei Xu, Qiang Dai, William T. Freeman, and Frédo Durand. 2021. QuanTaichi: A Compiler for Quantized Simulations. ACM Trans. Graph. 40, 4, Article 182 (jul 2021), 16 pages. Google ScholarDigital Library
19. Timothy Jeruzalski, John Kanji, Alec Jacobson, and David I.W. Levin. 2018. Collision-Aware and Online Compression of Rigid Body Simulations via Integrated Error Minimization. Computer Graphics Forum (Proc. SCA) (2018).Google Scholar
20. Aaron Demby Jones, Pradeep Sen, and Theodore Kim. 2016. Compressing Fluid Sub-spaces. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 77–84.Google Scholar
21. Byungsoo Kim, Vinicius C. Azevedo, Markus Gross, and Barbara Solenthaler. 2019. Transport-Based Neural Style Transfer for Smoke Simulations. ACM Transactions on Graphics (TOG) 38, 6 (2019), 188.Google ScholarDigital Library
22. Byungsoo Kim, Vinicius C. Azevedo, Markus Gross, and Barbara Solenthaler. 2020. Lagrangian Neural Style Transfer for Fluids. ACM Transactions on Graphics 39, 4, Article 52 (2020), 10 pages. Google ScholarDigital Library
23. Yuki Koyama, Issei Sato, and Masataka Goto. 2020. Sequential Gallery for Interactive Visual Design Optimization. ACM Trans. Graph. 39, 4, Article 88 (July 2020), 12 pages. Google ScholarDigital Library
24. Samuli Laine and Tero Karras. 2010. Efficient Sparse Voxel Octrees. In Proceedings of the 2010 ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games (Washington, D.C.) (I3D ’10). Association for Computing Machinery, New York, NY, USA, 55–63. Google ScholarDigital Library
25. Timothy R. Langlois and Doug L. James. 2014. Inverse-Foley Animation: Synchronizing rigid-body motions to sound. ACM Transactions on Graphics (Proceedings of SIGGRAPH 2014) 33, 4 (Aug. 2014). Google ScholarDigital Library
26. John Lasseter. 1987. Principles of Traditional Animation Applied to 3D Computer Animation. In Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’87). Association for Computing Machinery, New York, NY, USA, 35–44. Google ScholarDigital Library
27. Jerome Edward Lengyel. 1999. Compression of Time-dependent Geometry. In Proceedings of the 1999 symposium on Interactive 3D graphics. 89–95.Google ScholarDigital Library
28. Pingchuan Ma, Yunsheng Tian, Zherong Pan, Bo Ren, and Dinesh Manocha. 2018. Fluid Directed Rigid Body Control Using Deep Reinforcement Learning. ACM Trans. Graph. 37, 4, Article 96 (July 2018), 11 pages. Google ScholarDigital Library
29. J. Marks, B. Andalman, P. A. Beardsley, W. Freeman, S. Gibson, J. Hodgins, T. Kang, B. Mirtich, H. Pfister, W. Ruml, K. Ryall, J. Seims, and S. Shieber. 1997. Design Galleries: A General Approach to Setting Parameters for Computer Graphics and Animation. In Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’97). ACM Press/Addison-Wesley Publishing Co., USA, 389–400. Google ScholarDigital Library
30. Antoine McNamara, Adrien Treuille, Zoran Popović, and Jos Stam. 2004. Fluid Control Using the Adjoint Method. ACM Trans. Graph. 23, 3 (Aug. 2004), 449–456. Google ScholarDigital Library
31. Ken Museth. 2011. DB+Grid: A Novel Dynamic Blocked Grid for Sparse High-Resolution Volumes and Level Sets. In ACM SIGGRAPH 2011 Talks (Vancouver, British Columbia, Canada) (SIGGRAPH ’11). Association for Computing Machinery, New York, NY, USA, Article 51, 1 pages. Google ScholarDigital Library
32. Ken Museth. 2013. VDB: High-Resolution Sparse Volumes with Dynamic Topology. ACM Trans. Graph. 32, 3, Article 27 (July 2013), 22 pages. Google ScholarDigital Library
33. Ken Museth. 2021. NanoVDB: A GPU-Friendly and Portable VDB Data Structure For Real-Time Rendering And Simulation. In ACM SIGGRAPH 2021 Talks (Virtual Event, USA) (SIGGRAPH ’21). Association for Computing Machinery, New York, NY, USA, Article 1, 2 pages. Google ScholarDigital Library
34. Jelani Jelani Osei Nelson. 2011. Sketching and streaming high-dimensional vectors. Ph.D. Dissertation. Massachusetts Institute of Technology.Google Scholar
35. Michael B. Nielsen and Ken Museth. 2006. Dynamic Tubular Grid: An Efficient Data Structure and Algorithms for High Resolution Level Sets. J. Sci. Comput. 26, 3 (March 2006), 261–299. Google ScholarDigital Library
36. Michael B. Nielsen, Konstantinos Stamatelos, Morten Bojsen-Hansen, Duncan Brinsmead, Yannick Pomerleau, Marcus Nordenstam, and Robert Bridson. 2018. A Collocated Spatially Adaptive Approach to Smoke Simulation in Bifrost. In ACM SIGGRAPH 2018 Talks (Vancouver, British Columbia, Canada) (SIGGRAPH ’18). Association for Computing Machinery, New York, NY, USA, Article 77, 2 pages. Google ScholarDigital Library
37. Carol O’Sullivan, John Dingliana, Thanh Giang, and Mary K. Kaiser. 2003. Evaluating the Visual Fidelity of Physically Based Animations. ACM Trans. Graph. 22, 3 (jul 2003), 527–536. Google ScholarDigital Library
38. Masafumi Oyamada, Jianquan Liu, Shinji Ito, Kazuyo Narita, Takuya Araki, and Hiroyuki Kitagawa. 2018. Compressed Vector Set: A Fast and Space-Efficient Data Mining Framework. Journal of Information Processing 26 (2018), 416–426.Google ScholarCross Ref
39. Zherong Pan, Jin Huang, Yiying Tong, Changxi Zheng, and Hujun Bao. 2013. Interactive Localized Liquid Motion Editing. ACM Trans. Graph. 32, 6, Article 184 (nov 2013), 10 pages. Google ScholarDigital Library
40. Jovan Popović, Steven M Seitz, and Michael Erdmann. 2003. Motion sketching for control of rigid-body simulations. ACM Transactions on Graphics (TOG) 22, 4 (2003), 1034–1054.Google ScholarDigital Library
41. Jovan Popović, Steven M. Seitz, Michael Erdmann, Zoran Popović, and Andrew Witkin. 2000. Interactive Manipulation of Rigid Body Simulations. In Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’00). ACM Press/Addison-Wesley Publishing Co., USA, 209–217. Google ScholarDigital Library
42. Hanan Samet. 2006. Foundations of multidimensional and metric data structures. Morgan Kaufmann.Google Scholar
43. Syuhei Sato, Yoshinori Dobashi, and Theodore Kim. 2021. Stream-Guided Smoke Simulations. ACM Trans. Graph. 40, 4, Article 161 (July 2021), 7 pages. Google ScholarDigital Library
44. Mirko Sattler, Ralf Sarlette, and Reinhard Klein. 2005. Simple and Efficient Compression of Animation Sequences. In Proceedings of the 2005 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (Los Angeles, California) (SCA ’05). Association for Computing Machinery, New York, NY, USA, 209–217. Google ScholarDigital Library
45. Khalid Sayood. 2017. Introduction to Data Compression. Morgan Kaufmann.Google Scholar
46. Arnaud Schoentgen, Pierre Poulin, Emmanuelle Darles, and Philippe Meseure. 2020. Particle-Based Liquid Control Using Animation Templates. Eurographics Association, Goslar, DEU. Google ScholarDigital Library
47. 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, Article 205 (Nov. 2014), 12 pages. Google ScholarDigital Library
48. Lin Shi and Yizhou Yu. 2005. Controllable Smoke Animation with Guiding Objects. ACM Transactions on Graphics 24 (01 2005). Google ScholarDigital Library
49. Evan Shimizu, Matthew Fisher, S. Paris, J. McCann, and K. Fatahalian. 2020. Design Adjectives: A Framework for Interactive Model-Guided Exploration of Parameterized Design Spaces. Proceedings of the 33rd Annual ACM Symposium on User Interface Software and Technology (2020).Google ScholarDigital Library
50. SideFX. 2021. Houdini Engine. http://www.sidefx.com.Google Scholar
51. Jerry O. Talton, Daniel Gibson, Lingfeng Yang, Pat Hanrahan, and Vladlen Koltun. 2009. Exploratory Modeling with Collaborative Design Spaces. ACM Trans. Graph. 28, 5 (Dec. 2009), 1–10. Google ScholarDigital Library
52. Diane Tang, J Thomas Ngo, and Joe Marks. 1995. N-body Spacetime Constraints. The Journal of Visualization and Computer Animation 6, 3 (1995), 143–154.Google ScholarCross Ref
53. N. Thürey, R. Keiser, M. Pauly, and U. Rüde. 2006. Detail-Preserving Fluid Control. In Proceedings of the 2006 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (Vienna, Austria) (SCA ’06). Eurographics Association, Goslar, DEU, 7–12.Google Scholar
54. Adrien Treuille, Antoine McNamara, Zoran Popović, and Jos Stam. 2003. Keyframe Control of Smoke Simulations. ACM Trans. Graph. 22, 3 (jul 2003), 716–723. Google ScholarDigital Library
55. Christopher D. Twigg and Doug L. James. 2007. Many-Worlds Browsing for Control of Multibody Dynamics. ACM Trans. Graph. 26, 3 (July 2007), 14–es. Google ScholarDigital Library
56. Andrew Witkin and Michael Kass. 1988. Spacetime Constraints. In Proceedings of the 15th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’88). Association for Computing Machinery, New York, NY, USA, 159–168. Google ScholarDigital Library
57. Chris Wojtan, Peter J Mucha, and Greg Turk. 2006. Keyframe control of complex particle systems using the adjoint method. In Proceedings of the 2006 ACM SIGGRAPH/Eurographics symposium on Computer animation. 15–23.Google ScholarDigital Library
58. Guowei Yan, Zhili Chen, Jimei Yang, and Huamin Wang. 2020. Interactive Liquid Splash Modeling by User Sketches. ACM Trans. Graph. 39, 6, Article 165 (Nov. 2020), 13 pages. Google ScholarDigital Library
59. Thomas Y Yeh, Glenn Reinman, Sanjay J Patel, and Petros Faloutsos. 2009. Fool me twice: Exploring and exploiting error tolerance in physics-based animation. ACM Transactions on Graphics (TOG) 29, 1 (2009), 1–11.Google ScholarDigital Library