The Hex-Meshing Game
5 May 2020
Wherein you attempt to transform a quadrangulation into a cube. An activity variously described as non-difficult and amusing, although computer may be somewhat better than humans at it.
Let us cover a sphere with quadrangles. This is what it may look like:
If we start with an even number of quadrangles, then it is always possible to transform it into a cube using the following so-called flipping operations: [1, 2]
Each column represents one operator and its inverse. Any occurrence of a pattern shown above can be replaced with the other pattern that appears in the same column.
For example, if we take the quadrangulation on the left (the rhombic dodecahedron), it takes three steps to transform it into a cube:
Finding a sequence of flips to go from an arbitrary quadrangulation to the cube has an interesting application to hexahedral mesh generation (hexahedra are like cubes, except their faces do not have to form perfect squares). The two patterns used in each flipping operation can be thought of as two parts of a cube (shown in two different colors below):
So instead of thinking of each flip as changing a quadrangulation, we can think of it as attaching a hexahedron to the boundary. When the quadrangulation has been transformed into a cube, that means it has entirely been filled with hexahedra, except for a single cube-shaped hole.
The example shown below is known as Schneiders' pyramid. It has been very difficult to manually find a hexahedral mesh for this (when the problem was first posed, it wasn't even clear that it was possible [3]). This animation shows one possible solution, originally computed by Shang Xiang and Jianfei Liu (刘剑飞), as a sequence of 35 flips [4].
When using flips to construct hexahedral meshes, some sequences have to be excluded because they represent degenerate configurations that cannot be constructed geometrically. A common situation where this happens is when the two hexahedra corresponding to two different flips share multiple quadrangular faces. It is never possible to arrange two such hexahedra so that both of them are valid trilinear hexahedra, let alone convex polyhedra.
These restrictions do not affect the existence of a flipping sequence between two quadrangulations, although a few more steps may be required in order to get around them. You can try to construct hexahedral meshes with different quadrangulations as their boundaries by interacting with the mesh shown below. Only flip sequences that correspond to valid hexahedral meshes are allowed. Different colors on are used to represent different hexahedra and help identify illegal moves.
If you've tried your hand at a few of the random examples, it should be very apparent that finding the right sequence of moves is deceptively hard. Even with a computer trying all possible sequences, the solutions are often prohibitively long (for reference, Jean-Christophe Weill tried this sort of brute-force for the pyramid problem and stopped at 11 hexahedra [5]).
The key idea that was used to find the computer-generated solutions featured above is to look at the boundary a few steps before winning [6]. For example, two steps before transforming it into a cube, the boundary has to be one of only three different possibilities:
If we store all quadrangulations that can be filled with a small number of hexahedra (say, 9 or 10, as this easily fits within the memory of a modern computer), then we only have to exhaustively search for a much shorter sequence that transforms our initial quadrangulation into any quadrangulation that we already know how to fill.
References
- . 1999. Hexahedral mesh generation by successive dual cycle elimination, Eng. Comput. (Lond.) 15, 3, 269–279.
- . 2002. Flipping Cubical Meshes, Eng. Comput. (Lond.) 18, 3, 173–187.
- . 1995. Open problem.
- . 2018. A 36-element solution to Schneiders’ pyramid hex-meshing problem and a parity-changing template for hex-mesh revision, arXiv preprint arXiv:1807.09415.
- . 2015. A tentative to break the pyramid’s code.
- . 2019. Finding Hexahedrization for Small Quadrangulations of the Sphere, ACM Trans. Graph. 38, 4, 53:1–53:13.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.