Linear Complexity Hexahedral Mesh Generation

12th ACM Symp. Comp. Geom., Philadelphia, ACM, pp.58-67, 1996

MESHING
RESEARCH
CORNER

Department of Information and Computer Science
University of California, Irvine, CA 92717
http://www.ics.uci.edu/~eppstein/
Tech. Report 95-51

Abstract
We show that any simply connected (but not necessarily convex) polyhedron with an even number of quadrilateral sides can be partitioned into 0(n) topological cubes, meeting face to face. The result generalizes to non-simply-connected polyhedra satisfying an additional bipartiteness condition. The same techniques can also be used to reduce the geometric version of the bexabedral mesh generation problem to a finite case analysis amenable to machine solution.