“Variational quadratic shape functions for polygons and polyhedra” by Bunge, Herholz, Sorkine-Hornung, Botsch and Kazhdan

Solving partial differential equations (PDEs) on geometric domains is an important component of computer graphics, geometry processing, and many other fields. Typically, the given discrete mesh is the geometric representation and should not be altered for simulation purposes. Hence, accurately solving PDEs on general meshes is a central goal and has been considered for various differential operators over the last years. While it is known that using higher-order basis functions on simplicial meshes can substantially improve accuracy and convergence, extending these benefits to general surface or volume tessellations in an efficient fashion remains an open problem. Our work proposes variationally optimized piecewise quadratic shape functions for polygons and polyhedra, which generalize quadratic P2 elements, exactly reproduce them on simplices, and inherit their beneficial numerical properties. To mitigate the associated cost of increased computation time, particularly for volumetric meshes, we introduce a custom two-level multigrid solver which significantly improves computational performance.

1. Marc Alexa and Max Wardetzky. 2011. Discrete Laplacians on General Polygonal Meshes. ACM Transactions on Graphics 30, 4 (2011), 102:1–102:10.Google ScholarDigital Library
2. Prusty Aurojyoti, Piska Raghu, Amirtham Rajagopal, and Jn Reddy. 2019. An n-sided polygonal finite element for nonlocal nonlinear analysis of plates and laminates. Internat. J. Numer. Methods Engrg. 120 (2019), 1071–1107.Google ScholarCross Ref
3. Lourenço Beirão da Veiga, Franco Brezzi, Andrea Cangiani, Gianmarco Manzini, Luisa Donatella Marini, and Alessandro Russo. 2013b. Basic principles of Virtual Element Methods. Mathematical Models and Methods in Applied Sciences 23, 1 (2013), 199–214.Google ScholarCross Ref
4. Lourenço Beirão da Veiga, Franco Brezzi, and Luisa Donatella Marini. 2013a. Virtual Elements for Linear Elasticity Problems. SIAM J. Numer. Anal. 51, 2 (2013), 794–812.Google ScholarDigital Library
5. Lourenço Beirão da Veiga, Franco Dassi, and Alessandro Russo. 2017. High-order Virtual Element Method on polyhedral meshes. Computers and Mathematics with Applications 74 (2017), 1110–1122.Google ScholarDigital Library
6. J.E. Bishop. 2014. A displacement-based finite element formulation for general polyhedra using harmonic shape functions. Internat. J. Numer. Methods Engrg. 97 (2014), 1–31.Google ScholarCross Ref
7. Franco Brezzi, Konstantin Lipnikov, and Valeria Simoncini. 2005. A Family of Mimetic Finite Difference Methods on Polygonal and Polyhedral Meshes. Mathematical Models and Methods in Applied Sciences 15, 10 (2005), 1533–1551.Google ScholarCross Ref
8. Astrid Bunge, Mario Botsch, and Marc Alexa. 2021. The Diamond Laplace for Polygonal and Polyhedral Meshes. Computer Graphics Forum 40, 5 (2021), 217–230.Google ScholarCross Ref
9. Astrid Bunge, Philipp Herholz, Misha Kazhdan, and Mario Botsch. 2020. Polygon Laplacian Made Simple. Computer Graphics Forum 39, 2 (2020), 303–313.Google ScholarCross Ref
10. Yanqing Chen, Timothy A. Davis, William W. Hager, and Sivasankaran Rajamanickam. 2008. Algorithm 887: CHOLMOD, Supernodal Sparse Cholesky Factorization and Update/Downdate. ACM Trans. Math. Softw. 35, 3 (2008), 1–14.Google ScholarDigital Library
11. U. Clarenz, U. Diewald, and M. Rumpf. [n.d.]. Anisotropic geometric diffusion in surface processing. In Proceedings Visualization 2000. 397–405.Google Scholar
12. Yves Coudière and Florence Hubert. 2011. A 3D Discrete Duality Finite Volume Method for Nonlinear Elliptic Equations. SIAM J. Sci. Comput. 33, 4 (2011), 1739–1764.Google ScholarDigital Library
13. Keenan Crane, Clarisse Weischedel, and Max Wardetzky. 2013. Geodesics in Heat: A New Approach to Computing Distance Based on Heat Flow. ACM Transactions on Graphics 32, 5 (2013), 152:1–152:11.Google ScholarDigital Library
14. Fernando de Goes, Andrew Butts, and Mathieu Desbrun. 2020. Discrete Differential Operators on Polygonal Meshes. ACM Transactions on Graphics 39, 4 (2020), 110:1–110:14.Google ScholarDigital Library
15. Fernando de Goes, Mathieu Desbrun, Mark Meyer, and Tony DeRose. 2016. Subdivision Exterior Calculus for Geometry Processing. ACM Transactions on Graphics 35, 4 (2016), 133:1–133:11.Google ScholarDigital Library
16. Mathieu Desbrun, Mark Meyer, Peter Schröder, and Alan H. Barr. 1999. Implicit Fairing of Irregular Meshes Using Diffusion and Curvature Flow. In Proceedings of ACM SIGGRAPH. 317–324.Google Scholar
17. Gerhard Dziuk. 1988. Finite Elements for the Beltrami operator on arbitrary surfaces. Springer Berlin Heidelberg, 142–155.Google Scholar
18. Michael S. Floater. 2003. Mean value coordinates. Computer Aided Geometric Design 20, 1 (2003), 19–27.Google ScholarDigital Library
19. Richard Franke. 1979. A critical comparison of some methods for interpolation of scattered data. Technical Report. Naval Postgraduate School.Google Scholar
20. Xifeng Gao, Daniele Panozzo, Wenping Wang, Zhigang Deng, and Guoning Chen. 2017. Robust Structure Simplification for Hex Re-Meshing. ACM Transactions on Graphics 36, 6 (2017), 185:1–185:13.Google ScholarDigital Library
21. Andrew Gillette, Alexander Rand, and Chandrajit Bajaj. 2016. Construction of Scalar and Vector Finite Element Families on Polygonal and Polyhedral Meshes. Computational Methods in Applied Mathematics 16, 4 (2016), 667–683.Google ScholarCross Ref
22. F. Hermeline. 2009. A Finite Volume Method for Approximating 3D Diffusion Operators on General Meshes. J. Comput. Phys. 228, 16 (2009), 5763–5786.Google ScholarDigital Library
23. K. Hormann and N. Sukumar. 2008. Maximum Entropy Coordinates for Arbitrary Polytopes. Computer Graphics Forum 27, 5 (2008), 1513–1520.Google ScholarDigital Library
24. Kai Hormann and N. Sukumar. 2017. Generalized Barycentric Coordinates in Computer Graphics and Computational Mechanics. Taylor & Francis.Google Scholar
25. Pushkar Joshi, Mark Meyer, Tony DeRose, Brian Green, and Tom Sanocki. 2007. Harmonic Coordinates for Character Articulation. ACM Transactions on Graphics 26, 3 (2007), 71-es.Google ScholarDigital Library
26. Tao Ju, Scott Schaefer, and Joe Warren. 2005. Mean Value Coordinates for Closed Triangular Meshes. ACM Transactions on Graphics 24, 3 (2005), 561–566.Google ScholarDigital Library
27. Torsten Langer and Hans-Peter Seidel. 2008. Higher Order Barycentric Coordinates. Computer Graphics Forum 27, 2 (2008).Google Scholar
28. Andreas Longva, Fabian Löschner, Tassilo Kugelstadt, José Antonio Fernández-Fernández, and Jan Bender. 2020. Higher-Order Finite Elements for Embedded Simulation. ACM Transactions on Graphics 39, 6 (2020), 181:1–181:14.Google ScholarDigital Library
29. G. Manzini, A. Russo, and N. Sukumar. 2014. New perspectives on polygonal and polyhedral finite element methods. Mathematical Models and Methods in Applied Sciences 24 (2014), 1665–1699.Google ScholarCross Ref
30. Sebastian Martin, Peter Kaufmann, Mario Botsch, Martin Wicke, and Markus Gross. 2008. Polyhedral Finite Elements Using Harmonic Basis Functions. Computer Graphics Forum 27, 5 (2008), 1521–1529.Google ScholarDigital Library
31. Johannes Mezger, Bernhard Thomaszewski, Simon Pabst, and Wolfgang Straßer. 2008. Interactive Physically-Based Shape Editing. In Proceedings of ACM Symposium on Solid and Physical Modeling. 79–89.Google ScholarDigital Library
32. Ulrich Pinkall and Konrad Polthier. 1993. Computing discrete minimal surfaces and their conjugates. Experim. Math. 2 (1993), 15–36.Google ScholarCross Ref
33. Fabián Prada, Misha Kazhdan, Ming Chuang, and Hugues Hoppe. 2018. GradientDomain Processing within a Texture Atlas. ACM Transactions on Graphics 37, 4 (2018), 154:1–154:14.Google ScholarDigital Library
34. M. Rashid and M. Selimotic. 2006. A three-dimensional finite element method with arbitrary polyhedral elements. Internat. J. Numer. Methods Engrg. 67 (2006), 226 — 252.Google ScholarCross Ref
35. Teseo Schneider, Jérémie Dumas, Xifeng Gao, Mario Botsch, Daniele Panozzo, and Denis Zorin. 2019. Poly-Spline Finite-Element Method. ACM Transactions on Graphics 38, 3 (2019), 19:1–19:16.Google ScholarDigital Library
36. Teseo Schneider, Yixin Hu, Jérémie Dumas, Xifeng Gao, Daniele Panozzo, and Denis Zorin. 2018. Decoupling Simulation Accuracy from Mesh Quality. ACM Transactions on Graphics 37, 6 (2018), 280:1–280:14.Google ScholarDigital Library
37. Teseo Schneider, Yixin Hu, Xifeng Gao, Jeremie Dumas, Denis Zorin, and Daniele Panozzo. 2022. A Large Scale Comparison of Tetrahedral and Hexahedral Elements for Solving Elliptic PDEs with the Finite Element Method. ACM Transactions on Graphics 41, 3 (2022), 23:1–23:14.Google ScholarDigital Library
38. Nicholas Sharp, Yousuf Soliman, and Keenan Crane. 2019. The Vector Heat Method. ACM Transactions on Graphics 38, 3 (2019), 24:1–24:19.Google ScholarDigital Library
39. Dmitry Sokolov, Nicolas Ray, Lionel Untereiner, and Bruno Lévy. 2016. Hexahedral-Dominant Meshing. ACM Transactions on Graphics 35, 5 (2016), 157:1–157:23.Google ScholarDigital Library
40. N. Sukumar. 2004. Construction of polygonal interpolants: A maximum entropy approach. Internat. J. Numer. Methods Engrg. (2004), 2159–2181.Google Scholar
41. Alireza Tabarraei and N. Sukumar. 2006. Application of Polygonal Finite Elements in Linear Elasticity. International Journal of Computational Methods 03 (2006), 503–520.Google ScholarCross Ref
42. Xu-hai Tang, Sheng-chuan Wu, Chao Zheng, and Jian-hai Zhang. 2009. A novel virtual node method for polygonal elements. Applied Mathematics and Mechanics 30, 10 (2009).Google Scholar
43. Eugene L. Wachspress. 1975. A Rational Finite Element Basis. Academic Press.Google Scholar
44. Wenping Wang and Yang Liu. 2010. A Note on Planar Hexagonal Meshes. In Nonlinear Computational Geometry, Ioannis Z. Emiris, Frank Sottile, and Thorsten Theobald (Eds.). Springer New York, 221–233.Google Scholar
45. Martin Wicke, Mario Botsch, and Markus Gross. 2007. A Finite Element Method on Convex Polyhedra. Computer Graphics Forum 26, 3 (2007), 355–364.Google ScholarCross Ref