Combinatorial Techniques for Hexahedral Mesh Generation

Kilian Verhetsel

Meshing

Combinatorial techniques for hexahedral mesh generation

• Major tool to represent geometric objects in computer systems
• Split a complicated shape into many simple elements

Different Types of Meshes

Combinatorial Techniques for Hexahedral Mesh Generation

• Some meshes are used to represent the surface of objects
• Also applications in computer graphics, animation, etc.
• Typical element types: triangles, quadrangles

Different Types of Meshes

Combinatorial Techniques for Hexahedral Mesh Generation

• Some meshes are used to represent the entire volume of an object
• Used to solve partial differential equations on those objects
• Typical element types: hexahedra, tetrahedra, prisms, pyramids

A Word on Topology

Combinatorial Techniques for Hexahedral Mesh Generation

A Word on Topology

• Topology: study of properties invariant under continuous transformations: holes, orientation, etc.

A Word on Topology

• Topology: study of properties invariant under continuous transformations: holes, orientation, etc.

A Word on Topology

• Topology: study of properties invariant under continuous transformations: holes, orientation, etc.
• In computational terms: only care about how elements are connected
• Practical representation: A big list of numbers

Why Hexahedra?

• Fewer elements for same resolution

• Alignment to problem-specific axes, better control of resolution
• Fast solvers specific to hexahedral meshes

Hex-Dominant Meshing

• Easy way to get most of the benefits at a much lower cost
• Combining triangles works on surfaces
• Possible with tetrahedra, but more complex
  Pellerin et al. 2018
• Can we do it efficiently?

Hex-Dominant Meshing Seems Harder

• Only one way to split a quad into triangles
• 174 ways to split a hex into tetrahedra!

Computational Complexity: NP-hard problems

• Many natural optimization problem fall into the NP class
• Easy to check answers, hard to find one
• Proving difficulty: Showing how to solve a known difficult problem using our new problem

Difficulty of Hex-Dominant Meshing

• Can encode any NP-Complete problem using
  tet to hex combination
• In particular: boolean satisfiability

3-CNF

• Artificial, but simple NP-complete problem
• Easy to come up with a reduction
• Variables: must be 0 or 1
• Clause: group 3 variables/negations

• Goal: make it so each clause contain a 1

Make Wires out of Meshes

• Each wire is a stack of tetrahedra
• Two ways to combine them into hexahedra: 0 or 1

Branching Wires

• Each wire needs to go to many different places
• Small tet mesh lets us join three wires that carry the same state

Joining wires at clauses

• Each clause can be combined into one hexahedra in three different ways
• An optimal recombination "chooses" which wire needs to carry a 1 signal

Combining Tetrahedra into Hexahedra is Hard

From Hex-Dominant to All-Hexahedral Meshes

Schneiders' Pyramid

• Question: Is it even possible to mesh it with hexahedra?! Schneiders 1995
• Generally: Which boundary meshes are hex-meshable?

Connectivity Requirements for Hex-Meshes

Two distinct hex can share:

• Nothing
• A vertex
• An edge
• A quadrangular facet

Topological Hex-Meshing in Theory

• Topological Ball: Need even number of quadrangles
• Necessary, because hexahedra have an even number of faces

Topological Hex-Meshing in Theory

• Sufficiency independently proven by Thurston (1993) and Mitchell (1996)

Topological Hex-Meshing in Theory

• In General: All loops that bound an interior surface have an even number of edges

Topological Hex-Meshing in Theory

• Direct argument: Construct arrangement of dual manifolds Thurston 1993, Mitchell 1996
• More explicitly: Reduction to a few cases Eppstein 1999, Erickson 2014

Topological Hex-Meshing in Theory

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

How Many Hexahedra do I need?

Hex-Mesh Enumeration

1. Pick a boundary quad $Q$
2. Try every hex containing $Q$

Challenge of General Enumeration

• Non-manifold boundary after hex insertion
• Difficult to maintain topological invariants

Shellable Meshes

• Boundary always remains a sphere
  Müller-Hanneman 1999, Xiang 2018
• Equivalence between boundary transformation and hex insertion

Flips and Hexahedra

Remembering Small Meshes Helps

1. Precompute all meshes with up to $n$ hexahedra
2. Compare them with unmeshed region
   • Skips the last $n$ levels of the search tree
   

Meshing Small Quadrangulations of the Sphere

• Able to find hex-meshes for all boundaries with up to $20$ quadrangles
• Schneider's pyramid: possible with 36 hexahedra
• Always possible with $78~n$ hexahedra!
  • Previous upper bound: $5396~n$
• Makes the construction of Erickson completely explicit

Geometric Hex-Meshing

No geometric hex-mesh known for any of them Bern et al. 2002

Geometric Case-Study: Schneiders' Pyramid

• Small topological solution found using search techniques
• Faces are almost planar

Geometric Realization of the Pyramid

• Very constrained problem
  (planarity and symmetry)
• Most vertices are obtained by
  • Intersecting three faces
  • Projecting onto another face

Hex-Meshes to Come

• Can apply combinatorial searches to block-structured meshes
• Automatic search for connection templates in various meshing methods
• Which domains are geometrically meshable?
  • Reduces to bicuboid

Thank You!