“Optimal transport-based polar interpolation of directional fields” by Solomon and Vaxman
Conference:
Type:
Title:
- Optimal transport-based polar interpolation of directional fields
Session/Category Title: Transport: Parallel and Optimal
Presenter(s)/Author(s):
Abstract:
We propose an algorithm that interpolates between vector and frame fields on triangulated surfaces, designed to complement field design methods in geometry processing and simulation. Our algorithm is based on a polar construction, leveraging a conservation law from the Hopf-Poincaré theorem to match singular points using ideas from optimal transport; the remaining detail of the field is interpolated using straightforward machinery. Our model is designed with topology in mind, sliding singular points along the surface rather than having them appear and disappear, and it caters to all surface topologies, including boundary and generator loops.
References:
1. Noam Aigerman and Yaron Lipman. 2016. Hyperbolic orbifold Tutte embeddings. ACM Trans. Graph. 35, 6 (2016), 217–1. Google ScholarDigital Library
2. Grégoire Allaire. 2007. Numerical Analysis and Optimization: An Introduction to Mathematical Modelling and Numerical Simulation. Oxford University Press.Google Scholar
3. Alexis Angelidis and Fabrice Neyret. 2005. Simulation of smoke based on vortex filament primitives. In Proc. Symposium on Computer Animation. ACM, 87–96. Google ScholarDigital Library
4. Mirela Ben-Chen, Craig Gotsman, and Guy Bunin. 2008. Conformal flattening by curvature prescription and metric scaling. In Computer Graphics Forum, Vol. 27. Wiley Online Library, 449–458.Google Scholar
5. David Bommes, Henrik Zimmer, and Leif Kobbelt. 2009. Mixed-integer quadrangulation. In ACM Transactions On Graphics (TOG), Vol. 28. ACM, 77. Google ScholarDigital Library
6. Keenan Crane, Fernando De Goes, Mathieu Desbrun, and Peter Schröder. 2013. Digital geometry processing with discrete exterior calculus. In ACM SIGGRAPH 2013 Courses. ACM, 7. Google ScholarDigital Library
7. Keenan Crane, Mathieu Desbrun, and Peter Schröder. 2010. Trivial connections on discrete surfaces. In Computer Graphics Forum, Vol. 29. Wiley Online Library, 1525–1533.Google Scholar
8. Fernando de Goes and Keenan Crane. 2010. Trivial connections on discrete surfaces revisited: A simplified algorithm for simply-connected surfaces. Technical Report.Google Scholar
9. Stefan de Vries. 2016. Modeling sediment transport pathways in the mouth of the Scheldt estuary. Master’s thesis. University of Twente.Google Scholar
10. Olga Diamanti, Amir Vaxman, Daniele Panozzo, and Olga Sorkine-Hornung. 2014. Designing N-PolyVector fields with complex polynomials. In Computer Graphics Forum, Vol. 33. Wiley Online Library, 1–11. Google ScholarDigital Library
11. Nahum Farchi and Mirela Ben-Chen. 2018. Integer-only cross field computation. ACM Transactions on Graphics (TOG) 37, 4 (2018), 91. Google ScholarDigital Library
12. Simon Fiedler. 2018. Flip Subframe Interpolation. https://vimeo.com/251487780Google Scholar
13. Christoph Garth, Xavier Tricoche, and Gerik Scheuermann. 2004. Tracking of vector field singularities in unstructured 3D time-dependent datasets. In Proceedings of the Conference on Visualization. IEEE Computer Society, 329–336. Google ScholarDigital Library
14. Guangfeng Ji and Han-Wei Shen. 2006. Feature tracking using earth mover’s distance and global optimization. In Pacific Graphics, Vol. 2.Google Scholar
15. Felix Kälberer, Matthias Nieser, and Konrad Polthier. 2007. Quadcover: surface parameterization using branched coverings. In Computer Graphics Forum, Vol. 26. Wiley Online Library, 375–384.Google Scholar
16. Ron Kimmel and James A Sethian. 1998. Computing geodesic paths on manifolds. Proceedings of the National Academy of Sciences 95, 15 (1998), 8431–8435.Google ScholarCross Ref
17. Felix Knöppel, Keenan Crane, Ulrich Pinkall, and Peter Schröder. 2013. Globally optimal direction fields. ACM Transactions on Graphics (TOG) 32, 4 (2013), 59. Google ScholarDigital Library
18. Hugo Lavenant, Sebastian Claici, Edward Chien, and Justin Solomon. 2018. Dynamical Optimal Transport on Discrete Surfaces. ACM Transactions on Graphics (TOG) 37, 6 (Dec. 2018), 250:1–250:16. Google ScholarDigital Library
19. Bruno Lévy. 2015. A numerical algorithm for L2 semi-discrete optimal transport in 3D. ESAIM: Mathematical Modelling and Numerical Analysis 49, 6 (2015), 1693–1715.Google ScholarCross Ref
20. Bruno Lévy and Erica L Schwindt. 2018. Notions of optimal transport theory and how to implement them on a computer. Computers & Graphics 72 (2018), 135–148.Google ScholarCross Ref
21. Wan-Chiu Li, Bruno Vallet, Nicolas Ray, and Bruno Levy. 2006. Representing higher-order singularities in vector fields on piecewise linear surfaces. IEEE Transactions on Visualization and Computer Graphics 12, 5 (2006). Google ScholarDigital Library
22. Heng Liu, Paul Zhang, Edward Chien, Justin Solomon, and David Bommes. 2018. Singularity-constrained octahedral fields for hexahedral meshing. ACM Transactions on Graphics (TOG) 37, 4 (2018), 93. Google ScholarDigital Library
23. Quentin Mérigot. 2011. A multiscale approach to optimal transport. In Computer Graphics Forum, Vol. 30. Wiley Online Library, 1583–1592.Google Scholar
24. MOSEK. 2017. The MOSEK optimization toolbox for MATLAB manual (Version 8.1). http://docs.mosek.com/8.1/toolbox/index.htmlGoogle Scholar
25. Jonathan Palacios and Eugene Zhang. 2007. Rotational symmetry field design on surfaces. In ACM Transactions on Graphics (TOG), Vol. 26. ACM, 55:1–55:10. Google ScholarDigital Library
26. Gabriel Peyré, Lénaïc Chizat, François-Xavier Vialard, and Justin Solomon. 2017. Quantum entropic regularization of matrix-valued optimal transport. European Journal of Applied Mathematics (2017), 1–24.Google Scholar
27. Gabriel Peyré, Marco Cuturi, et al. 2019. Computational optimal transport. Foundations and Trends in Machine Learning 11, 5–6 (2019), 355–607.Google ScholarCross Ref
28. Konstantin Poelke and Konrad Polthier. 2016. Boundary-aware Hodge decompositions for piecewise constant vector fields. Computer-Aided Design 78 (2016), 126–136. Google ScholarDigital Library
29. Konrad Polthier and Markus Schmies. 1998. Straightest Geodesics on Polyhedral Surfaces. Springer Berlin Heidelberg, 135–150.Google Scholar
30. Nicolas Ray, Wan Chiu Li, Bruno Lévy, Alla Sheffer, and Pierre Alliez. 2006. Periodic global parameterization. ACM Transactions on Graphics (TOG) 25, 4 (2006), 1460–1485. Google ScholarDigital Library
31. Nicolas Ray, Bruno Vallet, Laurent Alonso, and Bruno Levy. 2009. Geometry-aware direction field processing. ACM Transactions on Graphics (TOG) 29, 1 (2009), 1. Google ScholarDigital Library
32. Nicolas Ray, Bruno Vallet, Wan Chiu Li, and Bruno Lévy. 2008. N-symmetry direction field design. ACM Transactions on Graphics (TOG) 27, 2 (2008), 10. Google ScholarDigital Library
33. Filippo Santambrogio. 2015. Optimal transport for applied mathematicians. Birkäuser, NY (2015), 99–102.Google Scholar
34. Syuhei Sato, Yoshinori Dobashi, and Tomoyuki Nishita. 2018. Editing Fluid Animation Using Flow Interpolation. ACM Transactions on Graphics (TOG) 37, 5 (2018), 173. Google ScholarDigital Library
35. Syuhei Sato, Yoshinori Dobashi, Yonghao Yue, Kei Iwasaki, and Tomoyuki Nishita. 2015. Incompressibility-preserving deformation for fluid flows using vector potentials. The Visual Computer 31, 6–8 (2015), 959–965. Google ScholarDigital Library
36. MHBM Shariff. 1995. A constrained conjugate gradient method and the solution of linear equations. Computers & Mathematics with Applications 30, 11 (1995), 25–37.Google ScholarCross Ref
37. Amit Singer. 2011. Angular synchronization by eigenvectors and semidefinite programming. Applied and Computational Harmonic Analysis 30, 1 (2011), 20.Google ScholarCross Ref
38. Maxime Soler, Melanie Plainchault, Bruno Conche, and Julien Tierny. 2018. Lifted Wasserstein Matcher for Fast and Robust Topology Tracking. Proc. IEEE Symposium on Large Data Analysis and Visualization (2018).Google ScholarCross Ref
39. Yousuf Soliman, Dejan Slepčev, and Keenan Crane. 2018. Optimal cone singularities for conformal flattening. ACM Transactions on Graphics (TOG) 37, 4 (2018), 105. Google ScholarDigital Library
40. Justin Solomon. 2018. Optimal Transport on Discrete Domains. Proceedings of Symposia in Pure Mathematics (2018).Google Scholar
41. Justin Solomon, Fernando De Goes, Gabriel Peyré, Marco Cuturi, Adrian Butscher, Andy Nguyen, Tao Du, and Leonidas Guibas. 2015. Convolutional Wasserstein distances: Efficient optimal transportation on geometric domains. ACM Transactions on Graphics (TOG) 34, 4 (2015), 66. Google ScholarDigital Library
42. Justin Solomon, Raif Rustamov, Leonidas Guibas, and Adrian Butscher. 2014. Earth mover’s distances on discrete surfaces. ACM Transactions on Graphics (TOG) 33, 4 (2014), 67. Google ScholarDigital Library
43. Yiying Tong, Pierre Alliez, David Cohen-Steiner, and Mathieu Desbrun. 2006. Designing quadrangulations with discrete harmonic forms. In Eurographics Symposium on Geometry Processing. 1–10. Google ScholarDigital Library
44. Xavier Tricoche, Gerik Scheuermann, and Hans Hagen. 2000. A topology simplification method for 2D vector fields. In Visualization. IEEE, 359–366. Google ScholarDigital Library
45. Amir Vaxman et al. 2017. Directional: directional field synthesis, design, and processing. https://github.com/avaxman/Directional.Google Scholar
46. Amir Vaxman, Marcel Campen, Olga Diamanti, Daniele Panozzo, David Bommes, Klaus Hildebrandt, and Mirela Ben-Chen. 2016. Directional field synthesis, design, and processing. In Computer Graphics Forum, Vol. 35. Wiley Online Library, 545–572.Google Scholar
47. Cédric Villani. 2003. Topics in optimal transportation. Number 58. American Mathematical Soc.Google Scholar
