Small Quadrangulations of the Sphere

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

Université catholique de Louvain

- Usual challenges in hex-meshing:

Find a mesh with elements of good - Shape
- Size
- Orientation

(Mesh from Livesu 2015)

- Starting from the surface seems appealing…
**Problem:**Find a hex-mesh

bounded by those 16 quads

Schneiders 1995- Existence of a solution:

not obvious - Smallest known solution:

36 hex Xiang 2018

Given a quad mesh $Q$, how many hexahedra

do we need to fill the
interior?

1

40?!

2

36?!

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

Two distinct cubes can share:

- Nothing
- A vertex
- An edge
- A quadrangular facet

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

Yes if:

- Even number of quads

Thurston 1993, Mitchell 1995 - No interior surface bounded by

odd number of edges Erickson 2014

- Subdivide a tet-mesh into hex

Erickson 2014

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

Erickson 2014

Buffer Cells

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

Erickson 2014

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

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

**Goal:**Transform input into a cube- Boundary always remains a sphere

Müller-Hanneman 1999, Xiang 2018 - Equivalence between boundary transformation and hex insertion

Different sequences of flips can result into the same mesh!

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

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

- The end of the search is always the same

- Precompute all meshes with up to $n$ hexahedra (right to left)
- 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

quadrangulated spheres with up to 20 quads

# quads | 6 | 8 | 10 | 12 | 14 | 16 | 18 | 20 |

# meshes | 1 | 1 | 3 | 11 | 58 | 451 | 4,461 | 49,957 |

- Always possible with $78~n$ hexahedra!
- Previous upper bound: $5396~n$

- Makes the construction of Erickson completely explicit

Code and Data: hextreme.eu

This research is supported by the European Research Council

(project HEXTREME, ERC-2015-AdG-694020)