Problem 27: Hexahedral Meshing

Statement

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]

Origin

Uncertain. Scott Mitchell in [Mit96]?

Status/Conjectures

Partially closed, Fall 2006.

Partial and Related Results

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.

Related Open Problems

See [BE01] for extension of the flipping operation described in Problem 28 to quadrilateral and hexahedral meshes.

Appearances

[MO01]

Categories

meshing

Entry Revision History

J. O'Rourke, 2 Aug. 2001; 18 Feb. 2002 (thanks to D. Eppstein); J. O'Rourke, 24 Oct. 2006.

Bibliography

BEA+99

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.

BE01

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.

CS06

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.

Epp96

David Eppstein.
Linear complexity hexahedral mesh generation.
In Proc. 12th Annu. ACM Sympos. Comput. Geom., pages 58-67, 1996.

Mit96

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.

MO01

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.