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
- Shape
- Size
- 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?
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:
- Even number of quads
Thurston 1993, Mitchell 1995
- 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
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
- 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 |
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)