A Characterization of the Quadrilateral Meshes of a Surface Which Admit a Compatible Hexahedral Mesh of the Enclosed Volume
Abstract
A popular three-dimensional mesh generation scheme is to start with a quadrilateral mesh of the surface of a volume, and then attempt to fill the interior of the volume with hexahedra, so that the hexahedra touch the surface in exactly the given quadrilaterals. Folklore has maintained that there are many quadrilateral meshes for which no such compatible hexahedral mesh exists. In this paper we give an existence proof which contradicts this folklore: A quadrilateral mesh need only satisfy some very weak conditions for there to exist a compatible hexahedral mesh. For a volume that is topologically a ball, any quadrilateral mesh composed of an even number of quadrilaterals admits a compatible hexahedral mesh. We extend this to certain non-ball volumes: there is a construction to reduce to the ball case, and we give a necessary condition as well.
Keywords: Computational Geometry, hexahedral mesh generation, existence.
See also David Eppstein’s result: Linear complexity hexahedral mesh generation
Bill Thurston also wrote a newsgroup article outlining a proof that is similar to my paper: “Hexahedral decomposition of polyhedra, sci.math, 25 Oct 1993.” David Eppstein has a copy of this online.
Citation
Scott A. Mitchell, “A Characterization of the Quadrilateral Meshes of a Surface Which Admit a Compatible Hexahedral Mesh of the Enclosed Volume.” In proc. 13th Annual Symposium on Theoretical Aspects of Computer Science (STACS `96), Lecture Notes in Computer Science 1046, Springer, pages 465-476, 1996.