Summary
A purely topological approach for the generation of hexahedral meshes from quadrilateral surface meshes of genus zero has been proposed by M. Müller-Hannemann: in a first stage, the input surface mesh is reduced to a single hexahedron by successively eliminating loops from the dual graph of the quad mesh; in the second stage, the hexahedral mesh is constructed by extruding a layer of hexahedra for each dual loop from the first stage in reverse elimination order. In this paper, we introduce several techniques to extend the scope of target shapes of the approach and significantly improve the quality of the generated hexahedral meshes. While the original method can only handle “almost convex” objects and requires mesh surgery and remeshing in case of concave geometry, we propose a method to overcome this issue by introducing the notion of concave dual loops. Furthermore, we analyze and improve the heuristic to determine the elimination order for the dual loops such that the inordinate introduction of interior singular edges, i.e. edges of degree other than four in the hexahedral mesh, can be avoided in many cases.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Armstrong, C., Robinson, D., McKeag, R., Li, T., Bridgett, S., Donaghy, R., McGleenan, C., Donaghy, R., Mcgleenan, C.: Medials for meshing and more (1995)
Blacker, T.: The cooper tool. In: 5th IMR, Sandia (1996)
Blacker, T.: Meeting the challenge for automated conformal hexahedral meshing. In: 9th IMR (2000)
Blacker, T.D., Meyers, R.J.: Seams and wedges in plastering: A 3-d hexahedral mesh generation algorithm. Engineering w. Comp. 9 (1993)
Bommes, D., Campen, M., Ebke, H.-C., Alliez, P., Kobbelt, L.: Integer-grid maps for reliable quad meshing. ACM Trans. Graph. 32(4) (July 2013)
Bommes, D., Lévy, B., Pietroni, N., Puppo, E., Silva, C., Tarini, M., Zorin, D.: State of the art in quad meshing. In: Eurographics (2012)
Bommes, D., Zimmer, H., Kobbelt, L.: Mixed-integer quadrangulation. In: ACM SIGGRAPH 2009, New York, USA (2009)
Botsch, M., Steinberg, S., Bischoff, S., Kobbelt, L.: Openmesh - a generic and efficient polygon mesh data structure (2002)
Brewer, M., Diachin, L., Knupp, P., Leurent, T., Melander, D.: The mesquite mesh quality improvement toolkit. In: 12th IMR (2003)
Campen, M., Bommes, D., Kobbelt, L.: Dual loops meshing: quality quad layouts on manifolds. ACM Trans. Graph. 31(4) (2012)
Folwell, N.T., Mitchell, S.A.: Reliable whisker weaving via curve contraction. In: 7th IMR, Sandia (1999)
Frey, P.J., Borouchaki, H., George, P.L.: Delaunay tetrahedralization using an advancing-front approach. In: 5th IMR (1996)
Hohmeyer, M.E., Christopher, W.: Fully-automatic object-based generation of hexahedral meshes. In: 4th IMR (1995)
Huang, J., Tong, Y., Wei, H., Bao, H.: Boundary aligned smooth 3d cross-frame field. In: SIGGRAPH Asia 2011. ACM (2011)
Kälberer, F., Nieser, M., Polthier, K.: Quadcover - surface parameterization using branched coverings. In: CG Forum, vol. 26 (2007)
Knupp, P.: Next-generation sweep tool: A method for generating all-hex meshes on two-and-one-half dimensional geomtries. In: 7th IMR (1998)
Ledoux, F., Weill, J.-C.: An extension of the reliable whisker weaving algorithm. In: 16th IMR, pp. 215–232. Springer (2008)
Li, M., Tong, R.: All-hexahedral mesh generation via inside-out advancing front based on harmonic fields. The Visual Computer (2012)
Li, Y., Liu, Y., Xu, W., Wang, W., Guo, B.: All-hex meshing using singularity-restricted field. ACM Trans. Graph. 31(6) (2012)
Liu, S., Gadh, R.: Automatic hexahedral mesh generation by recursive convex and swept volume decomposition. In: 6th IMR, Sandia (1997)
Miyoshi, K., Blacker, T.: Hexahedral mesh generation using multi-axis cooper algorithm (2000)
Müller-Hannemann, M.: High quality quadrilateral surface meshing without template restrictions: A new approach based on network flow techniques (1998)
Müller-Hannemann, M.: Shelling hexahedral complexes for mesh generation. Journal of Graph Algorithms and Applications 5 (2001)
Murdoch, P., Benzley, S., Blacker, T., Mitchell, S.A.: The spatial twist continuum: A connectivity based method for representing all-hexahedral finite element meshes. Finite Elements in Analysis and Design 28 (1997)
Myles, A., Pietroni, N., Kovacs, D., Zorin, D.: Feature-aligned t-meshes. ACM Trans. Graph. 29 (2010)
Nieser, M., Reitebuch, U., Polthier, K.: Cubecover–parameterization of 3d volumes. In: CG Forum vol. 30 (2011)
Saifullah, A.M., Üngör, A.: A simple algorithm for triconnectivity of a multigraph. In: Proc. of the 15th Australasian Symp. on Computing, CATS 2009. Australian Computer Society, Inc. (2009)
Sheffer, A., Etzion, M., Bercovier, M.: Hexahedral mesh generation using the embedded voronoi graph. In: 7th IMR (1999)
Shepherd, J.F., Johnson, C.R.: Hexahedral mesh generation constraints. Engineering with Computers 24 (2008)
Shewchuk, J.R.: Tetrahedral mesh generation by delaunay refinement. In: Symp. on Computational Geometry, SCG 1998. ACM (1998)
Staten, M., Canann, S.A., Owen, S.: Bmsweep: Locating interior nodes during sweeping (1998)
Struik, D.J.: Lectures on Classical Differential Geometry. Addison-Wesley Publishing Co., Massachusetts (1961)
Tautges, T.J., Blacker, T., Mitchell, S.A.: The whisker weaving algorithm: A connectivity-based method for constructing all-hexahedral finite element meshes (1995)
Tuchinsky, P.M., Clark, B.W.: The hextet hex-dominant automesher: An interim progress report. In: 6th IMR (1997)
White, D., Mingwu, L., Benzley, S.E., Sjaardema, G.D.: Automated hexahedral mesh generation by virtual decomposition. In: 4th IMR, Sandia (1995)
Zhang, M., Huang, J., Liu, X., Bao, H.: A wave-based anisotropic quadrangulation method. In: ACM SIGGRAPH 2010 (2010)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Kremer, M., Bommes, D., Lim, I., Kobbelt, L. (2014). Advanced Automatic Hexahedral Mesh Generation from Surface Quad Meshes. In: Sarrate, J., Staten, M. (eds) Proceedings of the 22nd International Meshing Roundtable. Springer, Cham. https://doi.org/10.1007/978-3-319-02335-9_9
Download citation
DOI: https://doi.org/10.1007/978-3-319-02335-9_9
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-02334-2
Online ISBN: 978-3-319-02335-9
eBook Packages: EngineeringEngineering (R0)