A Characterization of the
Quadrilateral Meshes
of a Surface
Which Admit a Compatible Hexahedral Mesh
of the Enclosed Volume
|
![[Sandia National Laboratories]](http://www.sandia.gov/images/logo.gif)
|
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.
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.