“Generalized fluid carving with fast lattice-guided seam computation” by Flynn, Hart, Morse, Holladay and Egbert
Conference:
Type(s):
Title:
- Generalized fluid carving with fast lattice-guided seam computation
Session/Category Title: Geometry Processing and Simulation
Presenter(s)/Author(s):
Abstract:
In this paper, we introduce a novel method for intelligently resizing a wide range of volumetric data including fluids. Fluid carving, the technique we build upon, only supported particle-based liquid data, and because it was based on image-based techniques, it was constrained to rectangular boundaries. We address these limitations to allow a much more versatile method for volumetric post-processing. By enclosing a region of interest in our lattice structure, users can retarget regions of a volume with non-rectangular boundaries and non-axis-aligned motion. Our approach generalizes to images, videos, liquids, meshes, and even previously unexplored domains such as fire and smoke. We also present a seam computation method that is significantly faster than the previous approach while maintaining the same level of quality, thus making our method more viable for production settings where post-processing workflows are vital.
References:
1. Ryoichi Ando and Christopher Batty. 2020. A Practical Octree Liquid Simulator with Adaptive Surface Resolution. ACM Trans. Graph. 39, 4, Article 32 (July 2020), 17 pages.
2. Ryoichi Ando, Nils Thürey, and Chris Wojtan. 2013. Highly Adaptive Liquid Simulations on Tetrahedral Meshes. ACM Trans. Graph. 32, 4, Article 103 (July 2013), 10 pages.
3. Shai Avidan and Ariel Shamir. 2007. Seam Carving for Content-aware Image Resizing. ACM Trans. Graph. 26, 3, Article 10 (July 2007).
4. Connelly Barnes, Eli Shechtman, Adam Finkelstein, and Dan B Goldman. 2009. Patch-Match: A Randomized Correspondence Algorithm for Structural Image Editing. ACM Transactions on Graphics (Proc. SIGGRAPH) 28, 3 (Aug. 2009).
5. Morten Bojsen-Hansen and Chris Wojtan. 2016. Generalized Non-reflecting Boundaries for Fluid Re-simulation. ACM Trans. Graph. 35, 4, Article 96 (July 2016), 7 pages.
6. Y. Boykov and V. Kolmogorov. 2004. An experimental comparison of min-cut/max- flow algorithms for energy minimization in vision. IEEE Transactions on Pattern Analysis and Machine Intelligence 26, 9 (Sep. 2004), 1124–1137.
7. Robert Bridson. 2008. Fluid Simulation. A. K. Peters, Ltd., Natick, MA, USA.
8. William L. Briggs, Van Emden Henson, and Steve F. McCormick. 2000. A Multigrid Tutorial: Second Edition. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA.
9. Billy Chen and Pradeep Sen. 2008. Video Carving. In Eurographics 2008 – Short Papers, Katerina Mania and Eric Reinhard (Eds.). The Eurographics Association.
10. Nuttapong Chentanez, Bryan E. Feldman, François Labelle, James F. O’Brien, and Jonathan R. Shewchuk. 2007. Liquid Simulation on Lattice-based Tetrahedral Meshes. In Proceedings of the 2007 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (San Diego, California) (SCA ’07). Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 219–228. http://dl.acm.org/citation.cfm?id=1272690.1272720
11. Chen-Kuo Chiang, Shu-Fan Wang, Yi-Ling Chen, and Shang-Hong Lai. 2009. Fast JND-Based Video Carving with GPU Acceleration for Real-Time Video Retargeting. IEEE Trans. Cir. and Sys. for Video Technol. 19, 11 (Nov. 2009), 1588–1597.
12. Donghyeon Cho, Jinsun Park, Tae-Hyun Oh, Yu-Wing Tai, and In So Kweon. 2017. Weakly- and Self-Supervised Learning for Content-Aware Deep Image Retargeting. In 2017 IEEE International Conference on Computer Vision (ICCV). IEEE.
13. Sabine Coquillart. 1990. Extended Free-Form Deformation: A Sculpturing Tool for 3D Geometric Modeling. In Proceedings of the 17th Annual Conference on Computer Graphics and Interactive Techniques (Dallas, TX, USA) (SIGGRAPH ’90). Association for Computing Machinery, New York, NY, USA, 187–196.
14. Dongfeng Han, X. Wu, and M. Sonka. 2009. Optimal multiple surfaces searching for video/image resizing – a graph-theoretic approach. In 2009 IEEE 12th International Conference on Computer Vision. 1026–1033.
15. Raanan Fattal and Dani Lischinski. 2004. Target-driven Smoke Animation. ACM Trans. Graph. 23, 3 (Aug. 2004), 441–448.
16. Ronald Fedkiw, Jos Stam, and Henrik Wann Jensen. 2001. Visual Simulation of Smoke. In Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’01). Association for Computing Machinery, New York, NY, USA, 15–22.
17. Sean Flynn, Parris Egbert, Seth Holladay, and Bryan Morse. 2019. Fluid Carving: Intelligent Resizing for Fluid Simulation Data. ACM Trans. Graph. 38, 6, Article 238 (Nov. 2019), 14 pages.
18. Zahra Forootaninia and Rahul Narain. 2020. Frequency-Domain Smoke Guiding. ACM Trans. Graph. 39, 6, Article 172 (Nov. 2020), 10 pages.
19. Nick Foster and Ronald Fedkiw. 2001. Practical Animation of Liquids. In Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’01). ACM, New York, NY, USA, 23–30.
20. R. Furuta, I. Tsubaki, and T. Yamasaki. 2018. Fast Volume Seam Carving With Multipass Dynamic Programming. IEEE Transactions on Circuits and Systems for Video Technology 28, 5 (2018), 1087–1101.
21. Matthias Grundmann, Vivek Kwatra, Mei Han, and Irfan Essa. 2010. Discontinuous Seam-Carving for Video Retargeting. IEEE CVPR (2010).
22. Mark Harris. 2005. Fast Fluid Dynamics Simulation on the GPU. In ACM SIGGRAPH 2005 Courses (Los Angeles, California) (SIGGRAPH ’05). ACM, New York, NY, USA, Article 220.
23. Hsi-Chin Hsin, Tze-Yun Sung, and Chin-Wei Su. 2014. A Fast Wavelet-Based Seam Carving Algorithm for Image Resizing. Asian Journal of Computer and Information Systems 2, 5 (Oct. 2014). https://ajouronline.com/index.php/AJCIS/article/view/1796
24. Nobukatsu Kajiura, Satoshi Kosugi, Xueting Wang, and Toshihiko Yamasaki. 2020. Self-Play Reinforcement Learning for Fast Image Retargeting. In Proceedings of the 28th ACM International Conference on Multimedia (Seattle, WA, USA) (MM ’20). Association for Computing Machinery, New York, NY, USA, 1755–1763.
25. Byungsoo Kim, Vinicius C. Azevedo, Markus Gross, and Barbara Solenthaler. 2019a. Transport-Based Neural Style Transfer for Smoke Simulations. ACM Trans. Graph. 38, 6, Article 188 (Nov. 2019), 11 pages.
26. 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.
27. Byungsoo Kim, Vinicius C. Azevedo, Nils Thuerey, Theodore Kim, Markus Gross, and Barbara Solenthaler. 2019b. Deep Fluids: A Generative Network for Parameterized Fluid Simulations. Computer Graphics Forum (Proc. Eurographics) 38, 2 (2019).
28. Ikjoon Kim, Jidong Zhai, Yan Li, and Wenguang Chen. 2015. Optimizing seam carving on multi-GPU systems for real-time content-aware image resizing. J. Supercomput. 71, 9 (2015), 3500–3524.
29. Theodore Kim and John Delaney. 2013. Subspace Fluid Re-simulation. ACM Trans. Graph. 32, 4, Article 62 (July 2013), 9 pages.
30. Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C. Lawrence Zitnick. 2014. Microsoft COCO: Common Objects in Context. In Computer Vision – ECCV 2014, David Fleet, Tomas Pajdla, Bernt Schiele, and Tinne Tuytelaars (Eds.). Springer International Publishing, Cham, 740–755.
31. Frank Losasso, Frédéric Gibou, and Ron Fedkiw. 2004. Simulating Water and Smoke with an Octree Data Structure. In ACM SIGGRAPH 2004 Papers (Los Angeles, California) (SIGGRAPH ’04). ACM, New York, NY, USA, 457–462.
32. A. McAdams, E. Sifakis, and J. Teran. 2010. A Parallel Multigrid Poisson Solver for Fluids Simulation on Large Grids. In Proceedings of the 2010 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (Madrid, Spain) (SCA ’10). Eurographics Association, Goslar Germany, Germany, 65–74. http://dl.acm.org/citation.cfm?id=1921427.1921438
33. 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.
34. Ken Museth. 2013. VDB: High-Resolution Sparse Volumes with Dynamic Topology. ACM Trans. Graph. 32, 3, Article 27 (July 2013), 22 pages.
35. Ken Museth, David E. Breen, Ross T. Whitaker, and Alan H. Barr. 2002. Level Set Surface Editing Operators. ACM Trans. Graph. 21, 3 (July 2002), 330–338.
36. Rahul Narain, Jason Sewall, Mark Carlson, and Ming C. Lin. 2008. Fast Animation of Turbulence Using Energy Transport and Procedural Synthesis. In ACM SIGGRAPH Asia 2008 Papers (Singapore) (SIGGRAPH Asia ’08). ACM, New York, NY, USA, Article 166, 8 pages.
37. Andrew Nealen, Takeo Igarashi, Olga Sorkine, and Marc Alexa. 2007. FiberMesh: Designing Freeform Surfaces with 3D Curves. ACM Trans. Graph. 26, 3 (July 2007), 41–es.
38. Duc Quang Nguyen, Ronald Fedkiw, and Henrik Wann Jensen. 2002. Physically Based Modeling and Animation of Fire. ACM Trans. Graph. 21, 3 (July 2002), 721–728.
39. Michael B. Nielsen and Robert Bridson. 2011. Guide Shapes for High Resolution Naturalistic Liquid Simulation. In ACM SIGGRAPH 2011 Papers (Vancouver, British Columbia, Canada) (SIGGRAPH ’11). ACM, New York, NY, USA, Article 83, 8 pages.
40. 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.
41. N. Rasmussen, D. Enright, D. Nguyen, S. Marino, N. Sumner, W. Geiger, S. Hoon, and R. Fedkiw. 2004. Directable Photorealistic Liquids. In Proceedings of the 2004 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (Grenoble, France) (SCA ’04). Eurographics Association, Goslar Germany, Germany, 193–202.
42. Karthik Raveendran, Chris Wojtan, Nils Thuerey, and Greg Turk. 2014. Blending Liquids. ACM Trans. Graph. 33, 4, Article 137 (July 2014), 10 pages.
43. Michael Rubinstein, Ariel Shamir, and Shai Avidan. 2008. Improved Seam Carving for Video Retargeting. ACM Trans. Graph. 27, 3, Article 16 (Aug. 2008), 9 pages.
44. Michael Rubinstein, Ariel Shamir, and Shai Avidan. 2009. Multi-operator Media Retargeting. In ACM SIGGRAPH 2009 Papers (New Orleans, Louisiana) (SIGGRAPH ’09). ACM, New York, NY, USA, Article 23, 11 pages.
45. Syuhei Sato, Yoshinori Dobashi, Theodore Kim, and Tomoyuki Nishita. 2018b. Example-Based Turbulence Style Transfer. ACM Trans. Graph. 37, 4, Article 84 (July 2018), 9 pages.
46. Syuhei Sato, Yoshinori Dobashi, and Tomoyuki Nishita. 2018a. Editing Fluid Animation Using Flow Interpolation. ACM Trans. Graph. 37, 5, Article 173 (Sept. 2018), 12 pages.
47. Arnaud Schoentgen, Pierre Poulin, Emmanuelle Darles, and Philippe Meseure. 2020. Particle-Based Liquid Control Using Animation Templates. Eurographics Association, Goslar, DEU.
48. Thomas W. Sederberg and Scott R. Parry. 1986. Free-Form Deformation of Solid Geometric Models. In Proceedings of the 13th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’86). Association for Computing Machinery, New York, NY, USA, 151–160.
49. Z. K. Senturk and D. Akgun. 2019. Seam Carving Based Image Retargeting: A Survey. In 2019 1st International Informatics and Software Engineering Conference (UBMYK). 1–6.
50. 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.
51. Tamar Rott Shaham, Tali Dekel, and Tomer Michaeli. 2019. SinGAN: Learning a Generative Model From a Single Natural Image. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV).
52. Lin Shi and Yizhou Yu. 2005. Taming Liquids for Rapidly Changing Targets. In Proceedings of the 2005 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (Los Angeles, California) (SCA ’05). ACM, New York, NY, USA, 229–236.
53. Assaf Shocher, Shai Bagon, Phillip Isola, and Michal Irani. 2019. InGAN: Capturing and Retargeting the “DNA” of a Natural Image. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV).
54. Denis Simakov, Yaron Caspi, Eli Shechtman, and Michal Irani. 2008. Summarizing visual data using bidirectional similarity. Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, 1 — 8.
55. Barry F. Smith, Petter E. Bjørstad, and William D. Gropp. 1996. Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations. Cambridge University Press, New York, NY, USA.
56. O. Sorkine, D. Cohen-Or, Y. Lipman, M. Alexa, C. Rössl, and H.-P. Seidel. 2004. Laplacian Surface Editing. In Proceedings of the 2004 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing (Nice, France) (SGP ’04). Association for Computing Machinery, New York, NY, USA, 175–184.
57. Jos Stam. 1999. Stable Fluids. In Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’99). ACM Press/Addison-Wesley Publishing Co., New York, NY, USA, 121–128.
58. Weimin Tan, Bo Yan, Chuming Lin, and Xuejing Niu. 2019. Cycle-IR: Deep Cyclic Image Retargeting. IEEE Transactions on Multimedia PP (12 2019), 1–1.
59. Nils Thuerey. 2016. Interpolations of Smoke and Liquid Simulations. ACM Trans. Graph. 36, 1, Article 3 (Sept. 2016), 16 pages.
60. 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, Aire-la-Ville, Switzerland, Switzerland, 7–12. http://dl.acm.org/citation.cfm?id=1218064.1218066
61. Adrien Treuille, Antoine McNamara, Zoran Popović, and Jos Stam. 2003. Keyframe Control of Smoke Simulations. ACM Trans. Graph. 22, 3 (July 2003), 716–723.
62. B. Wang, H. Xiong, Z. Ren, and C. W. Chen. 2014. Deformable Shape Preserving Video Retargeting With Salient Curve Matching. IEEE Journal on Emerging and Selected Topics in Circuits and Systems 4, 1 (2014), 82–94.
63. Martin Wicke, Matt Stanton, and Adrien Treuille. 2009. Modular Bases for Fluid Dynamics. ACM Trans. Graph. 28, 3, Article 39 (July 2009), 8 pages.
64. Yuwei Xiao, Szeyu Chan, Siqi Wang, Bo Zhu, and Xubo Yang. 2020. An Adaptive Staggered-Tilted Grid for Incompressible Flow Simulation. ACM Trans. Graph. 39, 6, Article 171 (Nov. 2020), 15 pages.
65. Jong-Chul Yoon, Sun-Young Lee, In-Kwon Lee, and Henry Kang. 2014. Optimized image resizing using flow-guided seam carving and an interactive genetic algorithm. Multim. Tools Appl. 71, 3 (2014), 1013–1031.
66. Yizhou Yu, Kun Zhou, Dong Xu, Xiaohan Shi, Hujun Bao, Baining Guo, and Heung-Yeung Shum. 2004. Mesh Editing with Poisson-Based Gradient Field Manipulation. ACM Trans. Graph. 23, 3 (Aug. 2004), 644–651.
67. Ya Zhou, Zhibo Chen, and Weiping Li. 2021. Weakly Supervised Reinforced Multi-Operator Image Retargeting. IEEE Transactions on Circuits and Systems for Video Technology 31, 1 (2021), 126–139.
68. Yongning Zhu and Robert Bridson. 2005. Animating Sand As a Fluid. ACM Trans. Graph. 24, 3 (July 2005), 965–972.
