TY - JOUR
T1 - Efficiently Hex-Meshing Things with Topology
AU - Erickson, Jeff
N1 - Funding Information:
Portions of this work were done while the author was visiting IST Austria. Work on this paper was also partially supported by the National Science Foundation under Grant CCF 09-15519. A preliminary version of this paper was presented at the 29th Annual Symposium on Computational Geometry []. See http://www.cs.uiuc.edu/~jeffe/pubs/hexmesh.html for the most recent version of this paper.
Publisher Copyright:
© 2014, Springer Science+Business Media New York.
PY - 2014/9/1
Y1 - 2014/9/1
N2 - A topological quadrilateral mesh Q of a connected surface in (Formula Prseented.) can be extended to a topological hexahedral mesh of the interior domain (Formula Prseented.) if and only if Q has an even number of quadrilaterals and no odd cycle in Q bounds a surface inside (Formula Prseented.). Moreover, if such a mesh exists, the required number of hexahedra is within a constant factor of the minimum number of tetrahedra in a triangulation of (Formula Prseented.) that respects Q. Finally, if Q is given as a polyhedron in (Formula Prseented.) with quadrilateral facets, a topological hexahedral mesh of the polyhedron can be constructed in polynomial time if such a mesh exists. All our results extend to domains with disconnected boundaries. Our results naturally generalize results of Thurston, Mitchell, and Eppstein for genus-zero and bipartite meshes, for which the odd-cycle criterion is trivial.
AB - A topological quadrilateral mesh Q of a connected surface in (Formula Prseented.) can be extended to a topological hexahedral mesh of the interior domain (Formula Prseented.) if and only if Q has an even number of quadrilaterals and no odd cycle in Q bounds a surface inside (Formula Prseented.). Moreover, if such a mesh exists, the required number of hexahedra is within a constant factor of the minimum number of tetrahedra in a triangulation of (Formula Prseented.) that respects Q. Finally, if Q is given as a polyhedron in (Formula Prseented.) with quadrilateral facets, a topological hexahedral mesh of the polyhedron can be constructed in polynomial time if such a mesh exists. All our results extend to domains with disconnected boundaries. Our results naturally generalize results of Thurston, Mitchell, and Eppstein for genus-zero and bipartite meshes, for which the odd-cycle criterion is trivial.
KW - Computational topology
KW - Cube complexes
KW - Homology
KW - Mesh generation
UR - http://www.scopus.com/inward/record.url?scp=84930731341&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84930731341&partnerID=8YFLogxK
U2 - 10.1007/s00454-014-9624-3
DO - 10.1007/s00454-014-9624-3
M3 - Article
AN - SCOPUS:84930731341
SN - 0179-5376
VL - 52
SP - 427
EP - 449
JO - Discrete and Computational Geometry
JF - Discrete and Computational Geometry
IS - 3
ER -