# 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:
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

## 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$

## 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