Hex Mesh Existence

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.

Paper pdf

STACS slides pdf

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.