# Finding Hexahedrizations for Small Quadrangulations of the Sphere

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

Université catholique de Louvain

# Hex-Meshing and Geometry

• Usual challenges in hex-meshing:
Find a mesh with elements of good
1. Shape
2. Size
3. Orientation

(Mesh from Livesu 2015)

# Hex-Meshing, Starting from the Boundary

• Starting from the surface seems appealing…
• Problem: Find a hex-mesh
Schneiders 1995
• Existence of a solution:
not obvious
• Smallest known solution:
36 hex Xiang 2018

# The Meshing Game

Given a quad mesh $Q$, how many hexahedra
do we need to fill the interior?

1

40?!

2

36?!

# Rule Ⅰ: Connectivity Only

• Geometric properties don't matter
• Only concerned with topology

# Rule Ⅱ: Intersections

Two distinct cubes can share:

• Nothing
• A vertex
• An edge

# Rule Ⅲ: Interior & Boundary Faces

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

# Is it even possible?

Yes if:

Thurston 1993, Mitchell 1995
2. No interior surface bounded by
odd number of edges Erickson 2014

# Proving the Existence of a Solution

• Subdivide a tet-mesh into hex

Erickson 2014

# Erickson's construction

• The mesh is almost complete…
• Only issue: boundary was refined

Erickson 2014

# Finishing the Construction:Buffer Cells

• Each buffer cell must have even number of quads
• Need two variants

Erickson 2014

# Meshing the Buffer Cells

It is an amusing exercise to fill out these cases by hand Eppstein 1999
It is not difficult to construct explicit hex meshes for these subdivided cubes by hand Erickson 2014

First explicit solution:
76 881 hex Carbonera 2010, Weill 2016

# Meshing the Buffer Cells, Practically

• $\le 40$ hex, but too hard for humans to find

# Searching for Hex-Meshes

• Goal: Transform input into a cube
• Boundary always remains a sphere
Müller-Hanneman 1999, Xiang 2018
• Equivalence between boundary transformation and hex insertion

# Challenge Ⅰ: Symmetry

Different sequences of flips can result into the same mesh!

# Dealing with Symmetry

• Based on tree-shape of the search space
• Write down hex-meshes at
root of finished subtrees (blue nodes)
• Check if they're subset of current mesh (red nodes)

# Challenge Ⅱ: A Needle in a Haystack

• With only a few flips, we can create many meshes.
• We only care about one: the cube.

# Right Before a Solution…

• The end of the search is always the same

# Remembering Small Meshes Helps

1. Precompute all meshes with up to $n$ hexahedra (right to left)
2. Compare them with unmeshed region
• Skips the last $n$ levels of the search tree
 # flips 1 2 3 4 5 6 7 8 9 10 # boundaries 2 5 17 74 489 4,192 42,676 476,520 5,632,488 69,043,690

• Found small hex-meshes for all
 # quads 6 8 10 12 14 16 18 20 # meshes 1 1 3 11 58 451 4,461 49,957

# Topological Hex-Meshing in Practice

• Always possible with $78~n$ hexahedra!
• Previous upper bound: $5396~n$
• Makes the construction of Erickson completely explicit

# Thank You!

Code and Data: hextreme.eu

This research is supported by the European Research Council