Linear Complexity Hexahedral Mesh Generation
arXiv:cs/9809109 · doi:10.1016/S0925-7721(98)00032-7
Abstract
We show that any polyhedron forming a topological ball with an even number of quadrilateral sides can be partitioned into O(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 hexahedral mesh generation problem to a finite case analysis amenable to machine solution.
12 pages, 17 figures. A preliminary version of this paper appeared at the 12th ACM Symp. on Computational Geometry. This is the final version, and will appear in a special issue of Computational Geometry: Theory and Applications for papers from SCG '96