Hexahedral meshes compatible with a quadrilateral surface mesh
Let $P$ be a simply connected polyhedron whose boundary is divided into an even number of quadrilaterals. A hexahedral mesh of $P$ is a decomposition of its interior into hexahedra, cells combinatorially equivalent to a cube, meeting face to face; it is compatible with the surface mesh if its boundary faces are exactly the given quadrilaterals. Here the hexahedra are required to have planar faces.
Mitchell and Eppstein showed that a topological hexahedral mesh, whose cells may have curved boundaries, always exists. Carbonera and Shepherd gave an algorithm extending any such quadrilateral surface mesh to a hexahedral mesh whose cells have straight edges, though their faces need not be planar.
Problem. Let $P$ be any simply connected polyhedron with a quadrilateral mesh of its boundary having an even number of faces. Does the interior of $P$ always admit a hexahedral mesh, with planar faces, that is compatible with the given boundary mesh?
Source: Origin uncertain; perhaps Mitchell (1996); see Bern, Eppstein et al. (1999); Problem 27 of The Open Problems Project (Demaine, Mitchell and O'Rourke).
Imported from topp.openproblem.net.
Classification
- Primary
- MG — Metric Geometry
- Secondary
- CO
- Keywords
- hexahedral mesh, quadrilateral mesh, The Open Problems Project
References
@misc{bern1999,
author = {Bern, Marshall and Eppstein, D. and Agarwal, P. K. and Amenta, N. and Chew, P. and Dey, T. and Dobkin, D. P. and Edelsbrunner, Herbert and Grimm, C. and Guibas, L. J. and Harer, J. and Hass, J. and Hicks, A. and Johnson, C. K. and Lerman, G. and Letscher, D. and Plassmann, P. and Sedgwick, E. and Snoeyink, Jack and Weeks, J. and Yap, C. and Zorin, D.},
title = {Emerging Challenges in Computational Topology},
year = {1999},
note = {Report on an NSF Workshop on Computational Topology, June 11--12, Miami Beach, FL},
}
@incollection{mitchell1996,
author = {Mitchell, Scott A.},
title = {A Characterization of the Quadrilateral Meshes of a Surface which Admit a Compatible Hexahedral Mesh of the Enclosed Volume},
booktitle = {Proc. 13th Sympos. Theoret. Aspects Comput. Sci.},
series = {Lecture Notes Comput. Sci.},
volume = {1046},
publisher = {Springer-Verlag},
year = {1996},
pages = {465--476},
}
@inproceedings{eppstein1996,
author = {Eppstein, David},
title = {Linear Complexity Hexahedral Mesh Generation},
booktitle = {Proc. 12th Annu. ACM Sympos. Comput. Geom.},
year = {1996},
pages = {58--67},
}
@inproceedings{carbonera2006,
author = {Carbonera, Carlos D. and Shepherd, Jason F.},
title = {A Constructive Approach to Constrained Hexahedral Mesh Generation},
booktitle = {Proc. 15th Internat. Meshing Roundtable},
editor = {Pebay, Phillippe P.},
publisher = {Springer},
year = {2006},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-01078, "Hexahedral meshes compatible with a quadrilateral surface mesh", clopen.solutions.