A 44-Element Mesh of Schneiders' Pyramid

Kilian Verhetsel, Jeanne Pellerin,
Jean-François Remacle

Université catholique de Louvain

Subdividing hex-dominant mesh

  • Subdivide different types of elements into hex
  • What about pyramids? [Schneiders 1996]

Meshing the pyramid

  • Initially: no known solutions [Schneiders 1996]
  • Even number of quads $\Rightarrow$
    there is a solution [Thurston 1993, Mitchell 1996]
  • Best known solutions:
    ad-hoc constructions
      Yamakawa et al., 2002: 118 hex
      Yamakawa et al., 2010: 88 hex

The Hex-Meshing Game

  • Do simple solutions exist?
    • Input: Surface mesh
    • Goal: Find a hex-mesh with this boundary
      • Minimum number of vertices?
      • Minimum number of hexahedra?

Rules of the Game

  • Ignore all geometric concerns
  • Each cube can be twisted as much as we want

Rules of the Game: Intersections

Two distinct cubes can share:

  • Nothing
  • A vertex
  • An edge
  • A quadrangular facet

Rules of the Game: Boundary

  • Boundary facet: in exactly one hex
  • All other facets: in exactly two hex

Playing the Meshing Game

Boundary Hex mesh
V H V
12 2 12
Boundary Hex mesh
V H V
10 > 20 > 38
Boundary Hex mesh
V H V
12 > 17 > 31
Boundary Hex mesh
V H V
22 6 22

Teaching the Meshing Game to a Computer

  • Give each vertex a unique number
  • Mesh can be written as a list of numbers
  • Work only on this list!

$\lbrack 0, 3, 7, 4, \mathbf{\color{red} 1}, \mathbf{\color{red} 2}, \mathbf{\color{red} 6}, \mathbf{\color{red} 5} \rbrack$
$\lbrack \mathbf{\color{red} 1}, \mathbf{\color{red} 5}, 11, 8, \mathbf{\color{red} 2}, \mathbf{\color{red} 6}, 10, 9 \rbrack$

Enumerating Hex-Meshes

Backtracking Search

  • Search space structured as a tree
  • Exponential size
    • Prune branches to reduce search time

Construction Order

Start construction where we have as few options as possible

Symmetry

  • Source of duplicated work
    1. Equivalent solutions found multiple times
    2. Equivalent dead-ends also visited many times

Dealing with Symmetry

  • Broken using:
    1. Comparing current state vs.
      already explored search space [Fahle 2001]
    2. Inequalities and ordering constraints
      (e.g. [Law 2004])

Application: Bounding difficulty to mesh an object

  • No solution with up to 18 vertices
    $\Rightarrow 19 \le V_{\min}$
  • No solution with up to 19 vertices
    $\Rightarrow 20 \le V_{\min}$
  • No solution with up to 20 vertices
    $\Rightarrow 21 \le V_{\min}$
  • No solution with up to 21 vertices
    $\Rightarrow 22 \le V_{\min}$
  • No solution with up to 25 vertices
    $\Rightarrow 26 \le V_{\min}$
  • No solution with up to 30 vertices
    $\Rightarrow 31 \le V_{\min}$
  • No solution with up to 35 vertices
    $\Rightarrow 36 \le V_{\min}$
  • No solution with up to 17 hexahedra
    $\Rightarrow 18 \le H_{\min}$
  • ~ 200 CPU days of work

Back to the pyramid

Best known solution: 88 hex [Yamakawa 2010]

Can we improve this mesh?

Simplifying a Mesh

  • Different number of elements
  • Same boundary before and after
    • Two interchangeable meshes

Simplifying a Mesh

  • Reduce number of elements in a solution
  • Our method: replace submesh
    without changing its boundary
    • Builds on top of our enumeration algorithm

Results: Schneiders' Pyramid

Yamakawa et al., 2010
H = 88, V = 105

Ours
H = 44, V = 62

Xiang et al., 2018
H = 36, V = 51

\[18 \le H_{\min} \le 36\] \[36 \le V_{\min} \le 51\]

Results: Octagonal Spindle

H = 40, V = 52
\[21 \le H_{\min} \le 40\] \[39 \le V_{\min} \le 52\]

Future Directions

  • Other templates for all-hex meshing?
  • Restrictions to subsets of all meshes

Thank you for your attention!

Code and meshes available at
hextreme.eu

This research is supported by the European Research Council
(project HEXTREME, ERC-2015-AdG-694020)