Medial hex-meshing: high-quality all-hexahedral mesh generation based on medial mesh
Authors: 
Sheng Zhang, Gang Xu, Haiyan Wu, Renshu Gu, Long Qi, Yufei PangAuthors Info & Claims
Pages 2537 - 2557
Abstract
Automatic high-quality all-hexahedral mesh generation is still a challenging problem in engineering applications. In this paper, based on the manifold curve/surface-mixed medial axis representation, we propose a new high-quality all-hex mesh generation method. Given an input watertight model, we first compute the corresponding medial mesh via the medial axis transform simplification method. Then, we build the all-hexahedral layer on the surface skeleton of the medial mesh via cross-field-guided quad-meshing and extrusion, and construct the hex-mesh elements for the curve skeleton of the medial mesh via sweeping approach. Based on the topological and geometrical information of the medial mesh, the initial hexahedral mesh can be obtained. Furthermore, with the iterative volumetric subdivision fitting approach, the hexahedral mesh is fitted to the input model. Finally, padding refinement and mesh optimization method are used to improve the element quality. In order to enhance the robustness and applicability of the proposed method, an interactive framework is also presented to handle non-manifold medial mesh. To show the efficiency of the proposed method, we have extensively tested our method on a lot of models. Compared with existing hexahedral mesh generation methods, our method can generate all-hex meshes with simpler singular structure, better element quality, and smaller element numbers. The code and data will be made available online to foster future research in this field.
References
[1]
Shepherd JF and Johnson CR Hexahedral mesh generation constraints Eng Comput 2008 24 3 195-213
[2]
Zhang Y, Hughes TJ, and Bajaj CL An automatic 3d mesh generation method for domains with multiple materials Comput Methods Appl Mech Eng 2010 199 5–8 405-415
[3]
Zhang Y, Wang W, and Hughes TJ Solid t-spline construction from boundary representations for genus-zero geometry Comput Methods Appl Mech Eng 2012 249 185-197
[4]
Wang W, Zhang Y, Liu L, and Hughes TJ Trivariate solid t-spline construction from boundary triangulations with arbitrary genus topology Comput Aided Des 2013 45 2 351-360
[5]
Zhang Y, Wang W, and Hughes TJ Conformal solid t-spline construction from boundary t-spline representations Comput Mech 2013 51 1051-1059
[6]
Lai Y, Zhang YJ, Liu L, Wei X, Fang E, and Lua J Integrating cad with abaqus: a practical isogeometric analysis software platform for industrial applications Comput Math Appl 2017 74 7 1648-1660
[7]
Li TS, McKeag RM, and Armstrong CG Hexahedral meshing using midpoint subdivision and integer programming Comput Methods Appl Mech Eng 1995 124 1 171-193
[8]
Zhang Y, Bajaj C, and Sohn B-S 3d finite element meshing from imaging data Comput Methods Appl Mech Eng 2005 194 48–49 5083-5106
[9]
Zhang Y and Bajaj C Adaptive and quality quadrilateral/hexahedral meshing from volumetric data Comput Methods Appl Mech Eng 2006 195 9–12 942-960
[10]
Maréchal L (2009) Advances in octree-based all-hexahedral mesh generation: handling sharp features. In: Clark BW (ed) Proceedings of the 18th international meshing roundtable. Springer, Berlin, pp 65–84
[11]
Qian J and Zhang Y Automatic unstructured all-hexahedral mesh generation from b-reps for non-manifold cad assemblies Eng Comput 2012 28 345-359
[12]
Zhang Y, Liang X, and Xu G A robust 2-refinement algorithm in octree or rhombic dodecahedral tree based all-hexahedral mesh generation Comput Methods Appl Mech Eng 2013 256 88-100
[13]
Zhang Y (2013) In: Zhang YJ (ed) Challenges and advances in image-based geometric modeling and Mesh generation. Springer, Dordrecht, pp 1–10.
[14]
Lin H, Jin S, Liao H, and Jian Q Quality guaranteed all-hex mesh generation by a constrained volume iterative fitting algorithm Comput Aided Des 2015 67 107-117
[15]
Zhang YJ Geometric modeling and mesh generation from scanned images 2016 Boca Raton CRC Press
[16]
Gao X, Shen H, Panozzo D (2019) Feature preserving octree-based hexahedral meshing. Computer graphics forum, vol 38. Wiley Online Library, pp 135–149
[17]
Pitzalis L, Livesu M, Cherchi G, Gobbetti E, and Scateni R Generalized adaptive refinement for grid-based hexahedral meshing ACM Trans Graph (TOG) 2021 40 6 1-13
[18]
Livesu M, Pitzalis L, and Cherchi G Optimal dual schemes for adaptive grid based hexmeshing ACM Trans Graph (TOG) 2021 41 2 1-14
[19]
Shih BY, Sakurai H (1996) Automated hexahedral mesh generation by swept volume decomposition and recomposition. In: Proceeding of the 5th International Meshing Roundtable, pp 273–280
[20]
Wu H and Gao S Automatic swept volume decomposition based on sweep directions extraction for hexahedral meshing Procedia Eng 2014 82 136-148
[21]
Gregson J, Sheffer A, Zhang E (2011) All-hex mesh generation via volumetric polycube deformation. Computer graphics forum, vol 30. Wiley Online Library, pp 1407–1416
[22]
Livesu M, Vining N, Sheffer A, Gregson J, and Scateni R Polycut: monotone graph-cuts for polycube base-complex construction ACM Trans Graph (TOG) 2013 32 6 1-12
[23]
Huang J, Jiang T, Shi Z, Tong Y, Bao H, and Desbrun M l1-based construction of polycube maps from complex shapes ACM Trans Graph (TOG) 2014 33 3 1-11
[24]
Fu X-M, Bai C-Y, Liu Y (2016) Efficient volumetric polycube-map construction. Computer graphics forum, vol 35. Wiley Online Library, pp 97–106
[25]
Hu K and Zhang YJ Centroidal voronoi tessellation based polycube construction for adaptive all-hexahedral mesh generation Comput Methods Appl Mech Eng 2016 305 405-421
[26]
Hu K, Zhang YJ, and Liao T Surface segmentation for polycube construction based on generalized centroidal voronoi tessellation Comput Methods Appl Mech Eng 2017 316 280-296
[27]
Li L, Zhang P, Smirnov D, Abulnaga SM, and Solomon J Interactive all-hex meshing via cuboid decomposition ACM Trans Graph (TOG) 2021 40 6 1-17
[28]
Yu Y, Liu JG, Zhang YJ (2022) HexDom: polycube-based hexahedral dominant mesh generation. The edited volume of mesh generation and adaptation: cutting-edge techniques, SEMA-SIMAI Springer Series
[29]
Yu Y, Wei X, Li A, Liu JG, He J, Zhang YJ (2022) HexGen and Hex2Spline: Polycube-Based Hexahedral Mesh Generation and Spline Modeling for Isogeometric Analysis Applications in LS-DYNA. Springer INdAM Serie: proceedings of INdAM Workshop “Geometric Challenges in Isogeometric Analysis”
[30]
Pietroni N, Campen M, Sheffer A, Cherchi G, Bommes D, Gao X, Scateni R, Ledoux F, Remacle J, and Livesu M Hex-mesh generation and processing: a survey ACM Trans Graph 2022 42 2 1-44
[31]
Guo H-X, Liu X, Yan D-M, and Liu Y Cut-enhanced polycube-maps for feature-aware all-hex meshing ACM Trans Graph (TOG) 2020 39 4 106-1
[32]
Liu L, Zhang Y, Liu Y, and Wang W Feature-preserving t-mesh construction using skeleton-based polycubes Comput Aided Des 2015 58 162-172
[33]
Huang J, Tong Y, Wei H, and Bao H Boundary aligned smooth 3d cross-frame field ACM Trans Graph (TOG) 2011 30 6 1-8
[34]
Li Y, Liu Y, Xu W, Wang W, and Guo B All-hex meshing using singularity-restricted field ACM Trans Graph (TOG) 2012 31 6 1-11
[35]
Jiang T, Huang J, Wang Y, Tong Y, and Bao H Frame field singularity correction for automatic hexahedralization IEEE Trans Vis Comput Graph 2013 20 8 1189-1199
[36]
Liu H, Zhang P, Chien E, Solomon J, and Bommes D Singularity-constrained octahedral fields for hexahedral meshing ACM Trans Graph 2018 37 4 93-1
[37]
Sheffer A, Etzion M, Rappoport A, and Bercovier M Hexahedral mesh generation using the embedded voronoi graph Eng Comput 1999 15 3 248-262
[38]
Livesu M, Muntoni A, Puppo E, Scateni R (2016) Skeleton-driven adaptive hexahedral meshing of tubular shapes. In: Computer graphics forum, vol 35. Wiley Online Library, pp 237–246
[39]
Lin H, Liao H, Deng C (2012) Filling triangular mesh model with all-hex mesh by volume subdivision fitting. State Key Lab of CAD & CG, Zhejiang University Report No: TR ZJUCAD 2, 2012
[40]
Blacker T (2000) Meeting the challenge for automated conformal hexahedral meshing. In: 9th international meshing roundtable. Citeseer, pp 11–20
[41]
Sun F, Choi Y-K, Yu Y, Wang W (2013) Medial meshes for volume approximation. arXiv:1308.3917
[42]
Sun F, Choi Y-K, Yu Y, and Wang W Medial meshes-a compact and accurate representation of medial axis transform IEEE Trans Vis Comput Graph 2015 22 3 1278-1290
[43]
Usai F, Livesu M, Puppo E, Tarini M, and Scateni R Extraction of the quad layout of a triangle mesh guided by its curve skeleton ACM Trans Graph (TOG) 2015 35 1 1-13
[44]
Blum H (1967) A transformation for extracting new descriptors of shape. In: Wathen-Dunn W (ed) Proc. models for the perception of speech and visual form. MIT Press, Cambridge, MA, pp 362–380. http://pageperso.lif.univ-mrs.fr/~edouard.thiel/rech/1967-blum.pdf
[45]
Lin C, Liu L, Li C, Kobbelt L, Wang B, Xin S, Wang W (2020) Seg-mat: 3d shape segmentation using medial axis transform. IEEE Trans Vis Comput Graph 28(6):2430–2444
[46]
Yang Y, Ren Z, Li H, Zhou C, Wang X, Hua G (2021) Learning dynamics via graph neural networks for human pose estimation and tracking. In: Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp 8074–8084
[47]
Lan L, Yang Y, Kaufman D, Yao J, Li M, Jiang C (2021) Medial ipc: accelerated incremental potential contact with medial elastics. ACM Trans Graph 40(4):1–16
[48]
Tagliasacchi A, Alhashim I, Olson M, Zhang H (2012) Mean curvature skeletons. Computer Graphics Forum. Oxford, UK: Blackwell Publishing Ltd, 31(5):1735–1744
[49]
Huang H, Wu S, Cohen-Or D, Gong M, Zhang H, Li G, and Chen B L1-medial skeleton of point cloud ACM Trans Graph 2013 32 4 65-1
[50]
Xu Z, Zhou Y, Kalogerakis E, Singh K (2019) Predicting animation skeletons for 3d articulated models via volumetric nets. In: 2019 international conference on 3D vision (3DV). IEEE, pp 298–307
[51]
Cheng J, Zheng X, Chen S, Liu G, Xin S, Lu L, Zhou Y, and Tu C Skeletonization via dual of shape segmentation Comput Aided Geom Des 2020 80
[52]
Amenta N, Choi S, Kolluri RK (2001) The power crust. In: Proceedings of the sixth ACM symposium on solid modeling and applications, pp 249–266
[53]
Sud A, Foskey M, Manocha D (2005) Homotopy-preserving medial axis simplification. In: Proceedings of the 2005 ACM symposium on solid and physical modeling, pp 39–50
[54]
Chazal F and Lieutier A The “-medial axis” Graph Models 2005 67 4 304-331
[55]
Miklos B, Giesen J, Pauly M (2010) Discrete scale axis representations for 3d geometry. In: ACM SIGGRAPH 2010 papers, pp 1–10
[56]
Li P, Wang B, Sun F, Guo X, Zhang C, and Wang W Q-mat: computing medial axis transform by quadratic error minimization ACM Trans Graph (TOG) 2015 35 1 1-16
[57]
Garland M, Heckbert PS (1997) Surface simplification using quadric error metrics. In: Proceedings of the 24th annual conference on computer graphics and interactive techniques, pp 209–216
[58]
Pan Y, Wang B, Guo X, Zeng H, Ma Y, and Wang W Q-mat+: an error-controllable and feature-sensitive simplification algorithm for medial axis transform Comput Aided Geom Des 2019 71 16-29
[59]
Dou Z, Lin C, Xu R, Yang L, Xin S, Komura T, Wang W (2022) Coverage axis: inner point selection for 3d shape skeletonization. Computer Graphics Forum 41(2):419–432.
[60]
Nieser M, Reitebuch U, Polthier K (2011) Cubecover–parameterization of 3d volumes. Computer graphics forum, vol 30. Wiley Online Library, pp 1397–1406
[61]
Livesu M, Pietroni N, Puppo E, Sheffer A, and Cignoni P Loopycuts: practical feature-preserving block decomposition for strongly hex-dominant meshing ACM Trans Graph (TOG) 2020 39 4 121-1
[62]
Jiang T, Huang J, Wang Y, Tong Y, and Bao H Frame field singularity correction for automatic hexahedralization IEEE Trans Vis Comput Graph 2014 20 8 1189-1199
[63]
Ray N, Sokolov D, and Lévy B Practical 3d frame field generation ACM Trans Graph (TOG) 2016 35 6 1-9
[64]
Price MA, Armstrong CG, and Sabin M Hexahedral mesh generation by medial surface subdivision: Part i. Solids with convex edges Int J Numer Methods Eng 1995 38 19 3335-3359
[65]
Price MA and Armstrong CG Hexahedral mesh generation by medial surface subdivision: Part ii. Solids with flat and concave edges Int J Numer Methods Eng 1997 40 1 111-136
[66]
Quadros WR Laytracks3d: a new approach for meshing general solids using medial axis transform Comput Aided Des 2016 72 102-117
[67]
Taghavi R (2020) Automatic 2D abstraction and hexahedral meshing by sorting a Delaunay mesh
[68]
Papadimitrakis D, Armstrong CG, Robinson TT, Le Moigne A, Shahpar S (2020) Building direction fields on the medial object to generate 3d domain decompositions for hexahedral meshing. In Proceedings of 28th International Meshing Roundtable.
[69]
Zhang Y, Bazilevs Y, Goswami S, Bajaj CL, and Hughes TJ Patient-specific vascular nurbs modeling for isogeometric analysis of blood flow Comput Methods Appl Mech Eng 2007 196 29–30 2943-2959
[70]
Viville P, Kraemer P, Bechmann D (2021) Hexahedral mesh generation for tubular shapes using skeletons and connection surfaces. In: 16th international joint conference on computer vision, imaging and computer graphics theory and applications, En ligne, France. . https://hal.science/hal-03268100
[71]
Livesu M, Sheffer A, Vining N, and Tarini M Practical hex-mesh optimization via edge-cone rectification ACM Trans Graph 2015
[72]
Pietroni N, Nuvoli S, Alderighi T, Cignoni P, Tarini M, et al. Reliable feature-line driven quad-remeshing ACM Trans Graph 2021 40 4 1-17
[73]
Catmull E and Clark J Recursively generated b-spline surfaces on arbitrary topological meshes Comput Aided Des 1978 10 6 350-355
[74]
Zhang Y, Bajaj C, and Xu G Surface smoothing and quality improvement of quadrilateral/hexahedral meshes with geometric flow Commun Numer Methods Eng 2009 25 1 1-18
[75]
Qian J, Zhang Y, Wang W, Lewis AC, Qidwai MS, and Geltmacher AB Quality improvement of non-manifold hexahedral meshes for critical feature determination of microstructure materials Int J Numer Methods Eng 2010 82 11 1406-1423
[76]
Hu K, Zhang YJ, and Xu G Cvt-based 3d image segmentation and quality improvement of tetrahedral/hexahedral meshes using anisotropic giaquinta-hildebrandt operator Comput Methods Biomech Biomed Eng Imaging Vis 2018 6 3 331-342
[77]
Cherchi G, Alliez P, Scateni R, Lyon M, Bommes D (2019) Selective padding for polycube-based hexahedral meshing. In: Computer graphics forum, vol 38. Wiley Online Library, pp 580–591
[78]
Bracci M, Tarini M, Pietroni N, Livesu M, and Cignoni P Hexalab.net: an online viewer for hexahedral meshes Comput Aided Des 2019 110 24-36
[79]
Sharp N et al (2019) Polyscope. www.polyscope.run
[80]
Hughes TJR, Cottrell JA, and Bazilevs Y Isogeometric analysis: cad, finite elements, nurbs, exact geometry and mesh refinement Comput Methods Appl Mech Eng 2005 194 39 4135-4195
[81]
Zoccheddu F, Gobbetti E, Livesu M, Pietroni N, Cherchi G (2023) Hexbox: interactive box modeling of hexahedral meshes. Comput Graph Forum 42(5): e14899
[82]
Reberol M, Verhetsel K, Henrotte F, Bommes D, and Remacle J-F Robust topological construction of all-hexahedral boundary layer meshes ACM Trans Math Softw 2023 49 1 1-32
[83]
Beaufort P-A, Reberol M, Kalmykov D, Liu H, Ledoux F, Bommes D (2022) Hex me if you can. Computer graphics forum, vol 41. Wiley Online Library, pp 125–134
[84]
Wang N, Wang B, Wang W, and Guo X Computing medial axis transform with feature preservation via restricted power diagram ACM Trans Graph (TOG) 2022 41 6 1-18
Index Terms
- Medial hex-meshing: high-quality all-hexahedral mesh generation based on medial mesh
Index terms have been assigned to the content through auto-classification.
Recommendations
Volume subdivision based hexahedral finite element meshing of domains with interior 2-manifold boundaries
AFRIGRAPH '06: Proceedings of the 4th international conference on Computer graphics, virtual reality, visualisation and interaction in AfricaWe present a subdivision based algorithm for multi-resolution Hexahedral meshing. The input is a bounding rectilinear domain with a set of embedded 2-manifold boundaries of arbitrary genus and topology. The algorithm first constructs a simplified Voronoi ...
A constructive approach to constrained hexahedral mesh generation
Mitchell proved that a necessary and sufficient condition for the existence of a topological hexahedral mesh constrained to a quadrilateral mesh on the sphere is that the constraining quadrilateral mesh contains an even number of elements. Mitchell's ...
Quality guaranteed all-hex mesh generation by a constrained volume iterative fitting algorithm
The hexahedral mesh (hex mesh) is usually preferred to the tetrahedral mesh (tet mesh) in finite element methods for numerical simulation. In finite element analysis, a valid hex mesh requires that the scaled Jacobian value at each mesh vertex is larger ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© The Author(s), under exclusive licence to Springer-Verlag London Ltd., part of Springer Nature 2024. Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 10 January 2024
Accepted: 03 November 2023
Received: 06 July 2023
Author Tags
Qualifiers
- Research-article
Funding Sources
- Graduate Scientific Research Foundation of Hangzhou Dianzi University
- the National Natural Science Foundation of China (No.U22A2033, 62202130, U1909210)
- the National Key R &D Program of China under Grant No.2020YFB1709402, the Zhejiang Provincial Science and Technology Program in China under Grant 2021C01108
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 23 Feb 2025