“Fast quasi-harmonic weights for geometric data interpolation” by Wang and Solomon

We propose quasi-harmonic weights for interpolating geometric data, which are orders of magnitude faster to compute than state-of-the-art. Currently, interpolation (or, skinning) weights are obtained by solving large-scale constrained optimization problems with explicit constraints to suppress oscillative patterns, yielding smooth weights only after a substantial amount of computation time. As an alternative, our weights are obtained as minima of an unconstrained problem that can be optimized quickly using straightforward numerical techniques. We consider weights that can be obtained as solutions to a parameterized family of second-order elliptic partial differential equations. By leveraging the maximum principle and careful parameterization, we pose weight computation as an inverse problem of recovering optimal anisotropic diffusivity tensors. In addition, we provide a customized ADAM solver that significantly reduces the number of gradient steps; our solver only requires inverting tens of linear systems that share the same sparsity pattern. Overall, our approach achieves orders of magnitude acceleration compared to previous methods, allowing weight computation in near real-time.

1. Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al. 2016. Tensorflow: A system for large-scale machine learning. In 12th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 16). 265–283.Google ScholarDigital Library
2. Marc Alexa. 2002. Linear combination of transformations. In ACM Transactions on Graphics (TOG), Vol. 21. ACM, 380–387.Google ScholarDigital Library
3. Norman I Badler and Mary Ann Morris. 1982. Modelling flexible articulated objects. In Proc. Computer Graphics’ 82, Online Conf. 305–314.Google Scholar
4. Seungbae Bang and Sung-Hee Lee. 2018. Spline Interface for Intuitive Skinning Weight Editing. ACM Transactions on Graphics (TOG) 37, 5 (2018), 174.Google ScholarDigital Library
5. Sumukh Bansal and Aditya Tatu. 2019. Affine interpolation in a lie group framework. ACM Transactions on Graphics (TOG) 38, 4 (2019), 71.Google ScholarDigital Library
6. Ilya Baran and Jovan Popović. 2007. Automatic rigging and animation of 3d characters. In ACM Transactions on graphics (TOG), Vol. 26. ACM, 72.Google Scholar
7. Fred L. Bookstein. 1989. Principal warps: Thin-plate splines and the decomposition of deformations. IEEE Transactions on pattern analysis and machine intelligence 11, 6 (1989), 567–585.Google ScholarDigital Library
8. Mario Botsch and Leif Kobbelt. 2004. An intuitive framework for real-time freeform modeling. ACM Transactions on Graphics (TOG) 23, 3 (2004), 630–634.Google ScholarDigital Library
9. Xiang Chen, Changxi Zheng, and Kun Zhou. 2016. Example-based subspace stress analysis for interactive shape design. IEEE transactions on visualization and computer graphics 23, 10 (2016), 2314–2327.Google Scholar
10. Keenan Crane, Clarisse Weischedel, and Max Wardetzky. 2013. Geodesics in heat: A new approach to computing distance based on heat flow. Transactions on Graphics 32, 5 (2013), 152.Google ScholarDigital Library
11. Timothy A Davis et al. 2015. SuiteSparse: A suite of sparse matrix software. URL http://faculty.cse.tamu.edu/davis/suitesparse.html (2015).Google Scholar
12. Olivier Dionne and Martin de Lasa. 2013. Geodesic voxel binding for production character meshes. In Proceedings of the 12th ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 173–180.Google ScholarDigital Library
13. Jérôme Droniou and Christophe Le Potier. 2011. Construction and convergence study of schemes preserving the elliptic local maximum principle. SIAM J. Numer. Anal. 49, 2 (2011), 459–490.Google ScholarDigital Library
14. Michael S Floater. 2003. Mean value coordinates. Computer aided geometric design 20, 1 (2003), 19–27.Google ScholarDigital Library
15. David Gilbarg and Neil S Trudinger. 2015. Elliptic partial differential equations of second order. springer.Google Scholar
16. Philipp Herholz, Felix Haase, and Marc Alexa. 2017. Diffusion diagrams: Voronoi cells and centroids from diffusion. In Computer Graphics Forum, Vol. 36. Wiley Online Library, 163–175.Google Scholar
17. Michael Hinze and Tran Nhan Tam Quyen. 2016. Matrix coefficient identification in an elliptic equation with the convex energy functional method. Inverse problems 32, 8 (2016), 085007.Google Scholar
18. Kai Hormann and Michael S Floater. 2006. Mean value coordinates for arbitrary planar polygons. ACM Transactions on Graphics (TOG) 25, 4 (2006), 1424–1441.Google ScholarDigital Library
19. Kai Hormann and Natarajan Sukumar. 2008. Maximum entropy coordinates for arbitrary polytopes. In Computer Graphics Forum, Vol. 27. Wiley Online Library, 1513–1520.Google ScholarDigital Library
20. Alec Jacobson, Ilya Baran, Ladislav Kavan, Jovan Popović, and Olga Sorkine. 2012a. Fast automatic skinning transformations. ACM Transactions on Graphics (TOG) 31, 4 (2012), 1–10.Google ScholarDigital Library
21. Alec Jacobson, Ilya Baran, Jovan Popovic, and Olga Sorkine. 2011. Bounded biharmonic weights for real-time deformation. ACM Trans. Graph. 30, 4 (2011), 78–1.Google ScholarDigital Library
22. Alec Jacobson, Zhigang Deng, Ladislav Kavan, and JP Lewis. 2014. Skinning: real-time shape deformation. In ACM SIGGRAPH 2014 Courses. ACM, 24.Google ScholarDigital Library
23. Alec Jacobson, Elif Tosun, Olga Sorkine, and Denis Zorin. 2010. Mixed finite elements for variational surface modeling. In Computer Graphics Forum, Vol. 29. 1565–1574.Google ScholarCross Ref
24. Alec Jacobson, Tino Weinkauf, and Olga Sorkine. 2012b. Smooth shape-aware functions with controlled extrema. In Computer Graphics Forum, Vol. 31. Wiley Online Library, 1577–1586.Google Scholar
25. Doug L James and Christopher D Twigg. 2005. Skinning mesh animations. In ACM Transactions on Graphics (TOG), Vol. 24. ACM, 399–407.Google ScholarDigital Library
26. Pushkar Joshi, Mark Meyer, Tony DeRose, Brian Green, and Tom Sanocki. 2007. Harmonic coordinates for character articulation. ACM Transactions on Graphics (TOG) 26, 3 (2007), 71.Google ScholarDigital Library
27. Tao Ju, Scott Schaefer, and Joe Warren. 2005. Mean value coordinates for closed triangular meshes. ACM Transactions on Graphics (TOG) 24, 3 (2005), 561–566.Google ScholarDigital Library
28. Ladislav Kavan, Steven Collins, Jiří Žára, and Carol O’Sullivan. 2008. Geometric skinning with approximate dual quaternion blending. ACM Transactions on Graphics (TOG) 27, 4 (2008), 105.Google ScholarDigital Library
29. Ladislav Kavan, P-P Sloan, and Carol O’Sullivan. 2010. Fast and efficient skinning of animated meshes. In Computer Graphics Forum, Vol. 29. Wiley Online Library, 327–336.Google Scholar
30. Diederik P Kingma and Jimmy Ba. 2014. Adam:A method for stochastic optimization. arXiv preprint arXiv:1412.6980 (2014).Google Scholar
31. Andreas Kirsch. 2011. An introduction to the mathematical theory of inverse problems. Vol. 120. Springer Science & Business Media.Google Scholar
32. Binh Huy Le and Zhigang Deng. 2012. Smooth skinning decomposition with rigid bones. ACM Transactions on Graphics (TOG) 31, 6 (2012), 199.Google ScholarDigital Library
33. Binh Huy Le and Zhigang Deng. 2014. Robust and accurate skeletal rigging frommesh sequences. ACM Transactions on Graphics (TOG) 33, 4 (2014), 84.Google ScholarDigital Library
34. Binh Huy Le and Jessica K Hodgins. 2016. Real-time skeletal skinning with optimized centers of rotation. ACM Transactions on Graphics (TOG) 35, 4 (2016), 37.Google ScholarDigital Library
35. Binh Huy Le and JP Lewis. 2019. Direct delta mush skinning and variants. ACM Trans. Graph 38, 113 (2019), 1–113.Google ScholarDigital Library
36. Xian-Ying Li and Shi-Min Hu. 2012. Poisson coordinates. IEEE Transactions on visualization and computer graphics 19, 2 (2012), 344–352.Google Scholar
37. Yaron Lipman, David Levin, and Daniel Cohen-Or. 2008. Green coordinates. ACM Transactions on Graphics (TOG) 27, 3 (2008),78.Google ScholarDigital Library
38. Yaron Lipman, Raif M Rustamov, and Thomas A Funkhouser. 2010. Biharmonic distance. Transactions on Graphics 29, 3 (2010), 27.Google ScholarDigital Library
39. Richard Liska and Mikhail Shashkov. 2008. Enforcing the discrete maximum principle for linear finite element solutions of second-order elliptic problems. Commun. Comput. Phys. 3, 4 (2008), 852–877.Google Scholar
40. Lijuan Liu, Youyi Zheng, Di Tang, Yi Yuan, Changjie Fan, and Kun Zhou. 2019. Neuroskinning: Automatic skin binding for production characters with deep graph networks. ACM Transactions on Graphics (TOG) 38, 4 (2019), 114.Google ScholarDigital Library
41. Changna Lu, Weizhang Huang, and Jianxian Qiu. 2014. Maximum principle in linear finite element approximations of anisotropic diffusion-convection-reaction problems. Numer. Math. 127, 3 (2014), 515–537.Google ScholarDigital Library
42. Nadia Magnenat-Thalmann, Richard Laperrire, and Daniel Thalmann. 1988. Joint-dependent local deformations for hand animation and object grasping. In In Proceedings on Graphics interfaceâĂŹ88. Citeseer.Google Scholar
43. Viktoras Makauskas. 2013. ngSkinTools. https://www.ngskintools.comGoogle Scholar
44. Jesús R Nieto and Antonio Susin. 2013. Cage based deformations: a survey. In Deformation models. Springer, 75–99.Google Scholar
45. Gerard R Richter. 1981. An inverse problem for the steady state diffusion equation. SIAM J. Appl. Math. 41, 2 (1981), 210–221.Google ScholarDigital Library
46. Conrad Sanderson. 2010. Armadillo: An open source C++ linear algebra library for fast prototyping and computationally intensive experiments. (2010).Google Scholar
47. Jonathan Richard Shewchuk. 1996. Triangle:Engineering a 2D quality mesh generator and Delaunay triangulator. In Workshop on Applied Computational Geometry. Springer, 203–222.Google ScholarCross Ref
48. Hang Si. 2015. TetGen, a Delaunay-based quality tetrahedral mesh generator. ACM Transactions on Mathematical Software (TOMS) 41, 2 (2015), 1–36.Google ScholarDigital Library
49. Robin Sibson and Vic Barnett. 1981. Interpreting multivariate data. A brief description of natural neighbor interpolation (1981), 21–36.Google Scholar
50. Oded Stein, Eitan Grinspun, Max Wardetzky, and Alec Jacobson. 2018. Natural boundary conditions for smoothing in geometry processing. ACM Transactions on Graphics (TOG) 37, 2 (2018), 23.Google ScholarDigital Library
51. J-M Thiery and Elmar Eisemann. 2018. ARAPLBS: Robust and Efficient Elasticity-Based Optimization of Weights and Skeleton Joints for Linear Blend Skinning with Parametrized Bones. In Computer Graphics Forum, Vol. 37. Wiley Online Library, 32–44.Google Scholar
52. Elif Tosun. 2008. Geometric modeling using high-order derivatives. Ph.D. Dissertation. Citeseer.Google Scholar
53. Kevin Wampler. 2016. Fast and reliable example-based mesh ik for stylized deformations. ACM Transactions on Graphics (TOG) 35, 6 (2016), 235.Google ScholarDigital Library
54. Yu Wang, Alec Jacobson, Jernej Barbič, and Ladislav Kavan. 2015. Linear subspace design for real-time shape deformation. ACM Transactions on Graphics (TOG) 34, 4 (2015), 57.Google ScholarDigital Library
55. Max Wardetzky, Saurabh Mathur, Felix Kälberer, and Eitan Grinspun. 2007. Discrete Laplace operators: no free lunch. In Symposium on Geometry processing. 33–37.Google Scholar
56. Zangyueyang Xian, Xin Tong, and Tiantian Liu. 2019. A scalable galerkin multigrid method for real-time simulation of deformable objects. ACM Transactions on Graphics (TOG) 38, 6 (2019), 162.Google ScholarDigital Library
57. Zhipei Yan and Scott Schaefer. 2019. A Family of Barycentric Coordinates for Co-Dimension 1 Manifolds with Simplicial Facets. In Computer Graphics Forum, Vol. 38. Wiley Online Library, 75–83.Google Scholar
58. Juyong Zhang, Bailin Deng, Zishun Liu, Giuseppe Patanè, Sofien Bouaziz, Kai Hormann, and Ligang Liu. 2014. Local barycentric coordinates. ACM Transactions on Graphics (TOG) 33, 6 (2014), 188.Google ScholarDigital Library
59. Xiaojin Zhu, Zoubin Ghahramani, and John D Lafferty. 2003. Semi-supervised learning using gaussian fields and harmonic functions. In Proceedings of the 20th International conference on Machine learning (ICML-03). 912–919.Google ScholarDigital Library