“Poly-Spline Finite Element Method” by Schneider, Dumas, Gao, Botsch, Panozzo, et al. …

  • ©Teseo Schneider, Jérémie Dumas, Xifeng Gao, Mario Botsch, Daniele Panozzo, and Denis Zorin




    Poly-Spline Finite Element Method

Session/Category Title: Deformation and FEM



    We introduce an integrated meshing and finite-element method pipeline enabling solution of partial differential equations in the volume enclosed by a boundary representation. We construct a hybrid hexahedral-dominant mesh, which contains a small number of star-shaped polyhedra, and build a set of high-order bases on its elements, combining triquadratic B-splines, triquadratic hexahedra, and harmonic elements. We demonstrate that our approach converges cubically under refinement, while requiring around 50% of the degrees of freedom than a similarly dense hexahedral mesh composed of triquadratic hexahedra. We validate our approach solving Poisson’s equation on a large collection of models, which are automatically processed by our algorithm, only requiring the user to provide boundary conditions on their surface.


    1. Martin Aigner, Christoph Heinrich, Bert Jüttler, Elisabeth Pilgerstorfer, Bernd Simeon, and Vuong. 2009. Swept Volume Parameterization for Isogeometric Analysis.
    2. Douglas Arnold, Daniele Boffi, and Richard Falk. 2002. Approximation by quadrilateral finite elements. Math. Comput. (2002).
    3. Yuri Bazilevs, L. Beirao da Veiga, J Austin Cottrell, Thomas J. R. Hughes, and Giancarlo Sangalli. 2006. Isogeometric analysis: Approximation, stability and error estimates for h-refined meshes. Math. Meth. Appl. Sci. (2006).
    4. L. Beirão Da Veiga, F. Brezzi, A. Cangiani, G. Manzini, L. D. Marini, and A. Russo. 2013. Basic principles of virtual element methods. Math. Meth. Appl. Sci. (2013).
    5. Steven E. Benzley, Ernest Perry, Karl Merkley, Brett Clark, and Greg Sjaardema. 1995. A comparison of all hexagonal and all tetrahedral finite element meshes for elastic and elasto-plastic analysis. In Proceedings of the 4th International Meshing Roundtable.
    6. J. E. Bishop. 2014. A displacement-based finite element formulation for general polyhedra using harmonic shape functions. Int. J. Numer. Methods Eng. (2014).
    7. Dietrich Braess. 2007. Finite Elements: Theory, Fast Solvers, and Applications in Solid Mechanics.
    8. R. T. Q. Chen, Y. Rubanova, J. Bettencourt, and D. Duvenaud. 2018. Neural ordinary differential equations. Advances in Neural Information Processing Systems 31, S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (Eds.). Curran Associates, Inc., 6571–6583. http://papers.nips.cc/paper/7892-neural-ordinary-differential-equations.pdf.
    9. A. O. Cifuentes and A. Kalbag. 1992. A performance study of tetrahedral and hexahedral elements in 3-D finite element structural analysis. Finite Elements in Analysis and Design (1992).
    10. J. Austin Cottrell, Thomas J. R. Hughes, and Yuri Bazilevs. 2009. Isogeometric Analysis: Toward Integration of CAD and FEA.
    11. L. Beirão da Veiga, A. Buffa, D. Cho, and G. Sangalli. 2011. Isogeometric analysis using T-splines on two-patch geometries. Comput. Meth. Appl. Mech. Eng. (2011).
    12. Blanca Ayuso de Dios, Konstantin Lipnikov, and Gianmarco Manzini. 2016. The nonconforming virtual element method. ESAIM: Mathematical Modelling and Numerical Analysis (2016).
    13. Luke Engvall and John A. Evans. 2017. Isogeometric unstructured tetrahedral and mixed-element Bernstein-Bezier discretizations. Comput. Meth. Appl. Mech. Eng. (2017).
    14. Xianzhong Fang, Weiwei Xu, Hujun Bao, and Jin Huang. 2016. All-hex meshing using closed-form induced polycube. ACM Trans. Graph. (2016).
    15. Michael S. Floater, Géza Kós, and Martin Reimers. 2005. Mean value coordinates in 3D. Comput. Aided Geom. Des. 22, 7 (2005), 623–631.
    16. Richard Franke. 1979. A Critical Comparison of Some Methods for Interpolation of Scattered Data.
    17. Xiaoming Fu, Chongyang Bai, and Yang Liu. 2016. Efficient volumetric PolyCube-map construction. Comput. Graph. Forum (2016).
    18. Xifeng Gao, Wenzel Jakob, Marco Tarini, and Daniele Panozzo. 2017a. Robust hex-dominant mesh generation using field-guided polyhedral agglomeration. ACM Trans. Graph. 36, 4 (2017), 1–13.
    19. Xifeng Gao, Daniele Panozzo, Wenping Wang, Zhigang Deng, and Guoning Chen. 2017b. Robust structure simplification for hex re-meshing. ACM Trans. Graph. 36, 6 (2017), 1–13.
    20. James Gregson, Alla Sheffer, and Eugene Zhang. 2011. All-hex mesh generation via volumetric PolyCube deformation. Comput. Graph. Forum (2011).
    21. Kai Hormann and Natarajan Sukumar. 2008. Maximum entropy coordinates for arbitrary polytopes. Comput. Graph. Forum 27, 5 (2008), 1513–1520.
    22. Jin Huang, Tengfei Jiang, Zeyun Shi, Yiying Tong, Hujun Bao, and Mathieu Desbrun. 2014. L1-based construction of polycube maps from complex shapes. ACM Trans. Graph. (2014).
    23. Jin Huang, Yiying Tong, Hongyu Wei, and Hujun Bao. 2011. Boundary aligned smooth 3D cross-frame field. ACM Trans. Graph. (2011).
    24. Thomas J. R. Hughes, John A. Cottrell, and Yuri Bazilevs. 2005. Isogeometric analysis: CAD, finite elements, NURBS, exact geometry and mesh refinement. Comput. Meth. Appl. Mech. Eng. (2005).
    25. Thomas J. R. Hughes. 2000. The Finite Element Method. Linear Static and Dynamic Finite Element Analysis.
    26. Yasushi Ito, Alan M. Shih, and Bharat K. Soni. 2009. Octree-based reasonable-quality hexahedral mesh generation using a new set of refinement templates. Int. J. Numer. Methods Eng. (2009).
    27. Tengfei Jiang, Jin Huang, Yiying Tong Yuanzhen Wang, and Hujun Bao. 2014. Frame field singularity correction for automatic hexahedralization. IEEE Trans. Vis. Comput. Graph. (2014).
    28. Pushkar Joshi, Mark Meyer, Tony DeRose, Brian Green, and Tom Sanocki. 2007. Harmonic coordinates for character articulation. ACM Trans. Graph. 26, 3 (2007), 71.
    29. Tao Ju, Scott Schaefer, and Joe Warren. 2005. Mean value coordinates for closed triangular meshes. ACM Trans. Graph. 24, 3 (2005), 561.
    30. Ilya Kostrikov, Zhongshi Jiang, Daniele Panozzo, Denis Zorin, and Joan Bruna. 2018. Surface networks. In Proceedings f the IEEE Conference on Computer Vision and Pattern Recognition (CVF’18). IEEE, 2540–2548.
    31. Na Lei, Xiaopeng Zheng, Jian Jiang, Yu-Yao Lin, and David Xianfeng Gu. 2017. Quadrilateral and hexahedral mesh generation based on surface foliation theory. Comput. Meth. Appl. Mech. Eng. (2017).
    32. Bo Li, Xin Li, Kexiang Wang, and Hong Qin. 2013. Surface mesh to volumetric spline conversion with generalized polycubes. IEEE Trans. Vis. Comput. Graph. (2013).
    33. Yufei Li, Yang Liu, Weiwei Xu, Wenping Wang, and Baining Guo. 2012. All-hex meshing using singularity-restricted field. ACM Trans. Graph. (2012).
    34. Konstantin Lipnikov, Gianmarco Manzini, and Mikhail Shashkov. 2014. Mimetic finite difference method. J. Comput. Phys. (2014).
    35. Marco Livesu, Nicholas Vining, Alla Sheffer, James Gregson, and Riccardo Scateni. 2013. PolyCut: Monotone graph-cuts for PolyCube base-complex construction. ACM Trans. Graph. (2013).
    36. Gianmarco Manzini, Alessandro Russo, and N. Sukumar. 2014. New perspectives on polygonal and polyhedral finite element methods. Math. Meth. Appl. Sci. (2014).
    37. Loïc Maréchal. 2009. Advances in octree-based all-hexahedral mesh generation: Handling sharp features. In Proceedings of the 18th International Meshing Roundtable. Springer, 65–84. https://link.springer.com/chapter/10.1007/978-3-642-04319-25
    38. Sebastian Martin. 2011. Flexible, unified and directable methods for simulating deformable objects. (2011). Ph.D. dissertation, ETH Zurich.
    39. Sebastian Martin, Peter Kaufmann, Mario Botsch, Martin Wicke, and Markus Gross. 2008. Polyhedral finite elements using harmonic basis functions. In Proceedings of the Symposium on Geometry Processing.
    40. Tobias Martin and Elaine Cohen. 2010. Volumetric parameterization of complex objects by respecting multiple materials. Comput. Graph. (2010).
    41. Matthias Nieser, Ulrich Reitebuch, and Konrad Polthier. 2011. CubeCover – Parameterization of 3D volumes. Comput. Graph. Forum (2011).
    42. Steven J. Owen and Sunil Saigal. 2000. H-Morph: An indirect approach to advancing front hex meshing. Int. J. Numer. Methods Eng. (2000).
    43. Julian Panetta, Qingnan Zhou, Luigi Malomo, Nico Pietroni, Paolo Cignoni, and Denis Zorin. 2015. Elastic textures for additive fabrication. ACM Trans. Graph. (2015).
    44. Cosmin G. Petra, Olaf Schenk, and Mihai Anitescu. 2014a. Real-time stochastic optimization of complex energy systems on high-performance computers. IEEE Computing in Science 8 Engineering (2014).
    45. Cosmin G. Petra, Olaf Schenk, Miles Lubin, and Klaus Gärtner. 2014b. An augmented incomplete factorization approach for computing the Schur complement in stochastic optimization. SIAM J. Sci. Comput. 36, 2 (2014), C139–C162.
    46. Thomas W. Sederberg, David L. Cardon, G. Thomas Finnigan, Nicholas S. North, Jianmin Zheng, and Tom Lyche. 2004. T-spline simplification and local refinement. ACM Trans. Graph. (2004).
    47. Jason F. Shepherd and Chris R. Johnson. 2008. Hexahedral mesh generation constraints. Eng. Comput. (2008).
    48. Jonathan Richard Shewchuk. 1996. Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator.
    49. Hang Si. 2015. TetGen, a delaunay-based quality tetrahedral mesh generator. ACM Trans. Math. Softw. (2015).
    50. Dmitry Sokolov, Nicolas Ray, Lionel Untereiner, and Bruno Lévy. 2016. Hexahedral-dominant meshing. ACM Trans. Graph. (2016).
    51. Matthew L. Staten, Steven J. Owen, and Ted D. Blacker. 2005. Unconstrained Paving 8 Plastering: A New Idea for All Hexahedral Mesh Generation.
    52. Marco Tarini, Kai Hormann, Paolo Cignoni, and Claudio Montani. 2004. PolyCube-maps. ACM Trans. Graph. (2004).
    53. Deepesh Toshniwal, Hendrik Speleers, René R. Hiemstra, and Thomas J. R. Hughes. 2017. Multi-degree smooth polar splines: A framework for geometric modeling and isogeometric analysis. Comput. Meth. Appl. Mech. Eng. (2017).
    54. Xiaodong Wei, Yongjie Jessica Zhang, Deepesh Toshniwal, Hendrik Speleers, Xin Li, Carla Manni, John A. Evans, and Thomas J. R. Hughes. 2018. Blended B-spline construction on unstructured quadrilateral and hexahedral meshes with optimal convergence rates in isogeometric analysis. Comput. Meth. Appl. Mech. Eng. (2018).
    55. Soji Yamakawa and Kenji Shimada. 2003. Fully-automated hex-dominant mesh generation with directionality control via packing rectangular solid cells. Int. J. Numer. Methods Eng. (2003).
    56. Y. J. Zhang, X. Liang, and Guoliang Xu. 2013. A robust 2-refinement algorithm in octree or rhombic dodecahedral tree based all-hexahedral mesh generation. Comput. Meth. Appl. Mech. Eng. (2013).

ACM Digital Library Publication:

Overview Page: