Next: Problem 28: Flip Graph Connectivity in 3D
Previous: Problem 26: Surface Reconstruction
Can the interior of every simply connected polyhedron whose surface is meshed by an even number of quadrilaterals be partitioned into a hexahedral mesh compatible with the surface meshing? [BEA+99]
Uncertain. Scott Mitchell in [Mit96]?
Partially closed, Fall 2006.
It was known that a topological hexahedral mesh exists [Mit96], [Epp96], with, in general, curved boundaries, but despite the availability of software that extends quadrilateral surface meshes to hexahedral volume meshes, it is not known if a “geometric” hexahedral mesh can be achieved, with all cells having planar faces.
A new result [CS06] settles the practical aspects of the problem, but leaves one question unresolved. This paper provides an explicit algorithm that extends a quadrilateral surface mesh to a hexahedral mesh, where all the hexahedra have straight segment edges. In a sense, these hexahedra are intermediate between the topological and geometric meshes mentioned above. The faces are not necessarily planar, but this is not a crucial aspect in applications, such a fluid dynamics simulations.
The question of whether a hexahedral mesh with planar faces exists remains open.
See [BE01] for extension of the flipping operation described in Problem 28 to quadrilateral and hexahedral meshes.
meshing
J. O’Rourke, 2 Aug. 2001; 18 Feb. 2002 (thanks to D. Eppstein); J. O’Rourke, 24 Oct. 2006.
Marshall Bern, D. Eppstein, P. K. Agarwal, N. Amenta, P. Chew, T. Dey, D. P. Dobkin, Herbert Edelsbrunner, C. Grimm, L. J. Guibas, J. Harer, J. Hass, A. Hicks, C. K. Johnson, G. Lerman, D. Letscher, P. Plassmann, E. Sedgwick, Jack Snoeyink, J. Weeks, C. Yap, and D. Zorin. Emerging challenges in computational topology, 1999. Report on an NSF Workshop Computational Topology, June 11-12, Miami Beach, FL.
Marshall Wayne Bern and David Eppstein. Flipping cubical meshes. In Proc. 10th Int. Meshing Roundtable, pages 19–29, October 2001. ACM Computing Research Repository, cs.CG/0108020.
Carlos D. Carbonera and Jason F. Shepherd. A constructive approach to constrained hexahedral mesh generation. In Phillippe P. Pebay, editor, Proc. 15th Internat. Meshing Roundtable. Springer, 2006.
David Eppstein. Linear complexity hexahedral mesh generation. In Proc. 12th Annu. ACM Sympos. Comput. Geom., pages 58–67, 1996.
Scott A. Mitchell. A characterization of the quadrilateral meshes of a surface which admit a compatible hexahedral mesh of the enclosed volume. In Proc. 13th Sympos. Theoret. Aspects Comput. Sci., volume 1046 of Lecture Notes Comput. Sci., pages 465–476. Springer-Verlag, 1996.
J. S. B. Mitchell and Joseph O’Rourke. Computational geometry column 42. Internat. J. Comput. Geom. Appl., 11(5):573–582, 2001. Also in SIGACT News 32(3):63-72 (2001), Issue 120.