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
    bounded by those 16 quads
    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
  • A quadrangular facet

Rule Ⅲ: Interior & Boundary Faces

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

Is it even possible?

Yes if:

  1. Even number of quads
    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

Meshing Small Quadrangulations

  • 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

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
(project HEXTREME, ERC-2015-AdG-694020)