Hexahedral mesh generation algorithm based on domain decomposition

doi:10.11996/JG.j.2095-302X.2026030589

Abstract

Abstract:

To address automatic generation of structured hexahedral meshes, an automatic hexahedral mesh generation algorithm based on model-domain segmentation was proposed. This method constructed an attribute-adjacency graph from geometric attribute of the model to extract domain features and generate partitioning surfaces, thereby decomposing a model domain into multiple simpler subdomains. The subdomains were then automatically classified and matched based on their features, and predefined subdomain mesh templates were applied to generate subdomain meshes. Finally, the subdomain meshes were merged to obtain an all-hexahedral mesh for the entire model. By combining feature-driven domain segmentation with template-based mesh generation, the proposed method reduced manual intervention while ensuring both topological consistency and geometric feature preservation, thereby improving the stability and repeatability of mesh generation. In the template-generation stage, feature-preserving parameterized mapping was combined with topology-constrained sweeping to generate the hexahedral meshes, forming an automated pipeline from domain segmentation to template generation and mesh merging. The method was applied to meshing typical mechanical models, providing a reference for digital simulation and analysis.

Key words: finite element analysis, attributed adjacency graph, domain decomposition, hexahedral mesh

CLC Number:

TP391.7

ZHANG Tianrui, WANG Aizeng, NING Tao, ZHANG Fengquan. Hexahedral mesh generation algorithm based on domain decomposition[J]. Journal of Graphics, 2026, 47(3): 589-597.

Figures/Tables 18

Fig. 1 3D model (where Fi denotes a model face)

Fig. 2 AAG of the 3D model

Table 1 Attribute information

属性	属性值
边类型	1 直线 0 弧线
边的凹凸性	1 凸边 0 光顺边 -1 凹边
边的闭合性	0 闭合 1 开放
面类型	平面柱面环面 …
面的凹凸性	1 凸面 0 平面 -1 凹面

Fig. 3 Schematic of subdomain structures ((a) Mappable; (b)-(d) Non-mappable)

Fig. 4 Closed-loop splitting ring for direct generation of the partitioning surface

Fig. 5 Open-loop partitioning surface closed by constructing virtual edges

Fig. 6 Adding partitioning surfaces to the AAG

Fig. 7 3D model and its partitioning surface; the bold loop indicates the boundary of the partitioning surface

Fig. 8 Model domain decomposition ((a) Initial domain; (b) Partitioned subdomains)

Table 2 Partial attribute encoding information

维度	特征	编码数值
1	平面	1
1	圆柱面	2
1	圆锥面	3
1	椭球面	4
1	自由曲面	5
2	凸面	1
2	凹面	2
2	光顺面	3
3	闭合面	1
3	开放面	2

Table 3 Representation of typical subgraphs

模板	几何表示	属性图	编码
矩形毛坯+圆形通孔
矩形毛坯+方形通孔
圆柱(实心)
圆柱(空心)
矩形毛坯+圆柱凸台
矩形毛坯+四棱柱凸台

Fig. 9 Flowchart of the algorithm

Fig. 10 Mapping method

Fig. 11 Mapping process of the hexahedral mesh ((a) Parametric-domain mesh; (b) Physical-domain mesh)

Fig. 12 Result of hexahedral-dominant meshing in a preprocessing software ((a) Bearing cover model; (b) Mesh of bearing cover; (c) Bearing pedestal model; (d) Mesh of bearing pedestal)

Fig. 13 Mesh generation for the bearing pedestal model ((a) Original model; (b) The algorithm result; (c) Mesh cross-section)

Fig. 14 Mesh generation for the rectangular elbow model ((a) Original model; (b) The algorithm result; (c) Mesh cross-section)

Fig. 15 Mesh generation for the bearing cover model ((a) Original model; (b) The algorithm result; (c) Mesh cross-section)

References 24

[1]	关振群, 宋超, 顾元宪, 等. 有限元网格生成方法研究的新进展[J]. 计算机辅助设计与图形学学报, 2003, 15(1): 1-14.
	GUAN Z Q, SONG C, GU Y X, et al. Recent advances of research on finite element mesh generation methods[J]. Journal of Computer-Aided Design & Computer Graphics, 2003, 15(1): 1-14(in Chinese).
[2]	刘秀萍. 三维六面体网格划分技术研究与实现[D]. 沈阳: 东北大学, 2010.
	LIU X P. Research on the three-dimensional hexahedral meshing technique and its implementation[D]. Shenyang: Northeastern University, 2010(in Chinese).
[3]	王瑞, 高曙明, 吴海燕. 六面体网格生成和优化研究进展[J]. 计算机辅助设计与图形学学报, 2020, 32(5): 693-708.
	WANG R, GAO S M, WU H Y. Progress in hexahedral mesh generation and optimization[J]. Journal of Computer-Aided Design & Computer Graphics, 2020, 32(5): 693-708(in Chinese).
[4]	MITCHELL S A. High fidelity interval assignment[C]// The 6th International Meshing Roundtable. Albuquerque: Sandia National Laboratories, 1997: 33-44.
[5]	KNUPP P M. Next-generation sweep tool: a method for generating all-hex meshes on two-and-one-half dimensional geometries[C]// The 7th International Meshing Roundtable. Albuquerque: Sandia National Laboratories, 1998: 505-513.
[6]	BLACKER T D, MEYERS R J. Seams and wedges in plastering: a 3-D hexahedral mesh generation algorithm[J]. Engineering with Computers, 1993, 9(2): 83-93. DOI URL
[7]	LELAND R W, MELANDER D J, MEYERS R J, et al. The geode algorithm:combining hex/tet plastering, dicing and transition elements for automatic, all-hex mesh generation[C]// The 7th International Meshing Roundtable. Albuquerque: Sandia National Laboratories, 1998: 515-521.
[8]	TAUTGES T J, MITCHELL S A. Whisker weaving: invalid connectivity resolution and primal construction algorithm[C]// The 4th International Meshing Roundtable. Albuquerque: Sandia National Laboratories, 1995: 115-127.
[9]	FOLWELL N T, MITCHELL S A. Reliable whisker weaving via curve contraction[C]// The 7th International Meshing Roundtable. Albuquerque: Sandia National Laboratories, 1998: 365-378.
[10]	王东风, 翟建军, 陈文亮. 基于映射法的六面体网格生成算法[J]. 中国制造业信息化, 2009, 38(5): 25-27, 32.
	WANG D F, ZHAI J J, CHEN W L. The hexahedral mesh generation based on the mapping technique[J]. Machine Design and Manufacturing Engineering, 2009, 38(5): 25-27, 32 (in Chinese).
[11]	汪攀, 张见明, 韩磊, 等. 基于子域分解的全六面体网格生成方法[J]. 中国机械工程, 2018, 29(3): 295-300.
	WANG P, ZHANG J M, HAN L, et al. Hexahedron mesh generation method based on sub-domain decomposition[J]. China Mechanical Engineering, 2018, 29(3): 295-300(in Chinese).
[12]	翟建军, 乔新宇, 丁秋林. 基于扫掠法的六面体网格生成算法及实现[J]. 南京航空航天大学学报, 2007, 39(1): 71-74.
	ZHAI J J, QIAO X Y, DING Q L. Research and implementation of hexahedral mesh generation algorithm based on sweeping[J]. Journal of Nanjing University of Aeronautics & Astronautics, 2007, 39(1): 71-74(in Chinese).
[13]	LAI M W, BENZLEY S, WHITE D. Automated hexahedral mesh generation by generalized multiple source to multiple target sweeping[J]. International Journal for Numerical Methods in Engineering, 2000, 49(1/2): 261-275. DOI URL
[14]	CAI S Y, TAUTGES T J. One-to-one sweeping based on harmonic S-T mappings of facet meshes and their cages[J]. Engineering with Computers, 2015, 31(3): 439-452. DOI URL
[15]	王洪申, 贾苏洋, 黄忠金. 面向重用的三维CAD拉伸模型建模特征序列重建[J]. 计算机辅助设计与图形学学报, 2024, 36(12): 1870-1879.
	WANG H S, JIA S Y, HUANG Z J. Feature sequence reconstrustruction of 3D CAD stretching model for reuse[J]. Journal of Computer-Aided Design & Computer Graphics, 2024, 36(12): 1870-1879(in Chinese).
[16]	闫立山, 刘昊, 马雅丽. 基于增材制造的六面体网格加密生成算法[J]. 机械设计与制造工程, 2025, 54(3): 15-20.
	YAN L S, LIU H, MA Y L. Hexahedral mesh densification generation algorithm based on additive manufacturing[J]. Machine Design and Manufacturing Engineering, 2025, 54(3): 15-20(in Chinese).
[17]	薛睿渊, 张永楠, 张希恒, 等. 不同网格划分方式下阀门有限元分析结果差异性研究[J]. 西华大学学报(自然科学版), 2025, 44(2): 106-112.
	XUE R Y, ZHANG Y N, ZHANG X H, et al. Study on the difference of valve finite element analysis results under different meshing methods[J]. Journal of Xihua University (Natural Science Edition), 2025, 44(2): 106-112.
[18]	周子钧. 基于属性邻接图的箱体类零件特征识别技术研究[D]. 武汉: 华中科技大学, 2022.
	ZHOU Z J. Research on feature recognition of box parts based on attributed adjacency graph[D]. Wuhan: Huazhong University of Science and Technology, 2022(in Chinese).
[19]	马尧, 陶建华, 周学成, 等. 面向模具的特征识别技术研究[J]. 现代制造工程, 2022(6): 43-48.
	MA Y, TAO J H, ZHOU X C, et al. Research on molds feature recognition technology[J]. Modern Manufacturing Engineering, 2022(6): 43-48(in Chinese).
[20]	邓岩, 王波兴. 基于图神经网络的机匣特征自动识别方法[J]. 工具技术, 2023, 57(12): 150-156.
	DENG Y, WANG B X. Method on automatic feature recognition of casing based on graph neural network[J]. Tool Engineering, 2023, 57(12): 150-156(in Chinese).
[21]	CHEN J M, GAO S M, ZHU H. An improved hexahedral mesh matching algorithm[J]. Engineering with Computers, 2016, 32(2): 207-230. DOI URL
[22]	赵卿锋. 基于奇异拓扑结构的六面体网格拼接方法研究[D]. 杭州: 杭州电子科技大学, 2023.
	ZHAO Q F. Research on hexahedral mesh matching based on base complex[D]. Hangzhou: Hangzhou Dianzi University, 2023(in Chinese).
[23]	张洪梅, 赵国群, 程联军. 基于STL文件的变密度三维全六面体网格自动生成方法[J]. 中国机械工程, 2006, 17(19): 1997-2001.
	ZHANG H M, ZHAO G Q, CHENG L J. Automatic density-changed all-hexahedral element mesh generation algorithm based on STL file[J]. China Mechanical Engineering, 2006, 17(19): 1997-2001(in Chinese).
[24]	张硕, 李建中, 高宏, 等. 一种多到一子图同构检测方法[J]. 软件学报, 2010, 21(3): 401-414.
	ZHANG S, LI J Z, GAO H, et al. Approach for efficient subgraph isomorphism testing for multiple graphs[J]. Journal of Software, 2010, 21(3): 401-414(in Chinese). DOI URL