Authors: Kilian Verhetsel, Jeanne Pellerin, Jean-François Remacle
(The meshes above can be rotated by clicking on them and dragging your cursor.)
Suppose you drew a set of n quadrangles on a sphere, covering its entirety. How many cubes do you need to fill the interior of that sphere? This question is surprisingly difficult to answer, even with only a few quadrangles (the case n = 8 is notoriously hard, and of the 3 cases where n = 10, only one is easy to solve).
Our contribution to SIGGRAPH 2019 shows that with n quadrangles on the boundary, 78n combinatorial cubes (or hexahedra) are always enough. This is a significant improvement over the previous upper bound: 5396n (Carbonera and Shepherd, 2010). Our result is based on a proof by Erickson (2014): we computed hexahedral meshes of the two base cases that it uses (shown above).
In most cases, there are significantly smaller solution. The paper gives an algorithm to search for such solutions. This was fast enough to compute hexahedral meshes for all 54,943 quadrangulations of up to 20 quadrangles for which a solution exists. The worst case required only 72 hexahedra.