Poly-Spline Finite Element Method

Teseo Schneider, Jeremie Dumas, Xifeng Gao, Mario Botsch, Daniele Panozzo, Denis ZorinarXiv 2018 · DOI · arXiv

TL;DR

The Poly-Spline Finite Element Method (FEM) is a hybrid approach that enables "black-box" simulation by combining the efficiency of B-splines with the flexibility of polyhedral elements. By using high-order bases on hexahedral-dominant meshes, the method achieves cubic convergence while requiring approximately 50% fewer degrees of freedom than standard high-order hexahedral methods.

What Problem Does This Paper Address?

In an ideal world, solving a partial differential equation (PDE) would be a "black box": you provide the shape and the physics, and the computer gives you the answer. In reality, the bottleneck is often meshing.

Standard FEM relies heavily on tetrahedral or hexahedral meshes. Tetrahedral meshes are easy to generate automatically but often require massive numbers of elements to be accurate and can suffer from numerical "locking." Hexahedral meshes are much more efficient and accurate, but generating a pure, high-quality hexahedral mesh for a complex, arbitrary shape is an unsolved problem in geometry processing.

The authors address this by embracing hex-dominant meshes—meshes that are mostly composed of regular cubes (hexahedra) but contain a small number of general polyhedra to fill the gaps in complex regions. The challenge is that standard FEM bases don't work across these different element types simultaneously while maintaining high-order accuracy.

Methods

The authors introduce a hybrid pipeline that matches the basis function to the local geometry of the mesh. They divide the mesh into three types of regions, as illustrated in Figure 2:

![Fig.

  1. Complexes involved in our construction. In green we show S (splines), in red Q (standard hexes), and in blue P (polyhedra).](/figures/art_129a5f919ea8499b877093c0bc5a585e)
  2. Spline Regions ($S$): In the regular, interior parts of the mesh, they use triquadratic B-splines. These are incredibly efficient, requiring only one degree of freedom (DoF) per element while providing high-order accuracy.
  3. Hexahedral Transitions ($Q$): For hexahedra that aren't in a perfectly regular grid (e.g., near boundaries or singularities), they switch to standard triquadratic (Q2) elements. These use 27 DoFs per element to maintain flexibility.
  4. Polyhedral Gaps ($P$): To handle the non-hexahedral "filler" elements, they use harmonic coordinates—a type of polyhedral basis function.

A key technical contribution is the use of consistency constraints. Because the polyhedral elements are non-conformal (meaning they don't perfectly "snap" to their neighbors in a $C^0$ continuous way), the authors enforce mathematical constraints during the construction of the basis to ensure the method still converges at a cubic rate. They also use an isoparametric geometric map (Figure 3) to ensure the math performed in the "unit cube" parametric space translates correctly to the complex physical shape.

![Fig.

  1. Illustration of the geometric mapping from parametric space to physical space.](/figures/art_84cad94dae5c4a748ab89a063cb6f8ae)

Datasets

The method was validated on a large, diverse collection of models:

  • 2D Dataset: 205 star-shaped polygonal meshes.
  • 3D Pure Hex Dataset: 165 meshes.
  • 3D Hybrid Dataset: 29 star-shaped polyhedral meshes. The meshes were automatically generated using modern field-aligned meshing algorithms, demonstrating the "black-box" potential of the pipeline. The authors have released this dataset publicly to encourage benchmarking.

Key Insights and Ideas

  • Local Trade-offs: Instead of choosing one element type for the whole mesh, the method makes local trade-offs. You get the speed of splines where the mesh is "boring" and the power of polyhedra where the geometry is "interesting."
  • DoF Efficiency: By using splines for the bulk of the volume, the method drastically reduces the total number of unknowns (DoFs) in the linear system without sacrificing accuracy.
  • Resilience to Bad Geometry: Surprisingly, the authors found that their polyhedral bases are less sensitive to poor element shapes than standard Q2 hexahedral bases. This suggests that switching to "expensive" polyhedral elements might actually be a better strategy for poorly shaped regions than trying to force a standard hex basis to work.
  • Consistency is King: High-order convergence on polyhedra isn't automatic. The "aha moment" here is that enforcing polynomial reproduction through linear constraints is what allows the non-conformal polyhedral parts to keep up with the cubic convergence of the splines.

Key Results

  • Cubic Convergence: The method consistently achieves a convergence rate of ~3.0 (cubic) for both Poisson and linear elasticity problems, matching the theoretical performance of high-order FEM.
  • Memory Savings: On average, Poly-Spline FEM requires 50% fewer DoFs than a standard Q2 hexahedral mesh of similar density.
  • Robustness: In large-scale tests (Table 1), the method solved models that caused standard Q2 solvers to crash due to out-of-memory errors, thanks to its lower DoF count.
  • Visual Validation: Figure 1 shows the breadth of complex models handled by the system, ranging from organic shapes like lions to mechanical parts.

![Fig.

  1. A selection of automatically generated meshes. Colors denote the basis type; the bottom-right shows a Poisson solution on a complex chair model.](/figures/art_6656ce1696a4403cb5def5d11f2661db)

Limitations and Future Work

  • PDE Dependence: The consistency constraints for the polyhedral elements currently need to be derived specifically for each PDE (e.g., different for Poisson vs. Elasticity). The authors suggest using automatic differentiation to make this more general.
  • Preprocessing: The current implementation requires one step of initial mesh refinement to ensure polyhedra don't touch the boundary or each other, which increases the total element count.
  • Geometric Distortion: In extreme cases, the mapping between the spline and Q2 regions can introduce numerical distortion, which might be improved by optimizing the placement of control points.

Summary updated

Abstract

We introduce an integrated meshing and finite element method pipeline enabling black-box 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 basis on its elements, combining triquadratic B-splines, triquadratic hexahedra (27 degrees of freedom), 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.
BibTeX
@misc{schneider2018poly,
  author = {Teseo Schneider and Jeremie Dumas and Xifeng Gao and Mario Botsch and Daniele Panozzo and Denis Zorin},
  title = {{Poly-Spline Finite Element Method}},
  year = {2018},
  eprint = {1804.03245},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1804.03245},
}

Loading related content...

Figure