TY - GEN

T1 - Efficiently hex-meshing things with topology

AU - Erickson, Jeff

PY - 2013

Y1 - 2013

N2 - A topological quadrilateral mesh Q of a connected surface in ℝ3 can be extended to a topological hexahedral mesh of the interior domain Ω if and only if Q has an even number of quadrilaterals and no odd cycle in Q bounds a surface inside Ω. 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 Ω that respects Q. Finally, if Q is given as a polyhedron in ℝ3 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 ℝ3 can be extended to a topological hexahedral mesh of the interior domain Ω if and only if Q has an even number of quadrilaterals and no odd cycle in Q bounds a surface inside Ω. 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 Ω that respects Q. Finally, if Q is given as a polyhedron in ℝ3 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 - Hexahedral mesh generation

KW - Homology

UR - http://www.scopus.com/inward/record.url?scp=84879629690&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84879629690&partnerID=8YFLogxK

U2 - 10.1145/2493132.2462403

DO - 10.1145/2493132.2462403

M3 - Conference contribution

AN - SCOPUS:84879629690

SN - 9781450320313

T3 - Proceedings of the Annual Symposium on Computational Geometry

SP - 37

EP - 45

BT - Proceedings of the 29th Annual Symposium on Computational Geometry, SoCG 2013

PB - Association for Computing Machinery

T2 - 29th Annual Symposium on Computational Geometry, SoCG 2013

Y2 - 17 June 2013 through 20 June 2013

ER -