Efficient tetrahedral mesh generation algorithm based on octree refinement

LIU Jinbao; GAO Xiang; ZHANG Xiang; GONG Chunye

doi:10.7638/kqdlxxb-2024.0020

English Version Journal Login

您当前的位置：

首页 >

文章列表页 >

Efficient tetrahedral mesh generation algorithm based on octree refinement

更新时间：2026-05-28

- Efficient tetrahedral mesh generation algorithm based on octree refinement
- Vol. 43, Issue 8, Pages: 50-58(2025)
- 作者机构：
  
  1. 国防科技大学计算机学院,长沙,410073
  2. 国防科技大学高端装备数字化软件湖南省重点实验室,长沙,410073
- 作者简介：
- 基金信息：
- DOI：10.7638/kqdlxxb-2024.0020
  CLC： O241;V211.3
- Published：2025
- 稿件说明：
移动端阅览
刘金宝, 高翔, 张翔, 等. 基于八叉树细化的高效四面体网格生成[J]. 空气动力学学报, 2025, 43(8): 50−58.

LIU Jinbao, GAO Xiang, ZHANG Xiang, et al. Efficient tetrahedral mesh generation algorithm based on octree refinement[J]. 2025, 43(8): 50-58.
刘金宝, 高翔, 张翔, 等. 基于八叉树细化的高效四面体网格生成[J]. 空气动力学学报, 2025, 43(8): 50−58. DOI： 10.7638/kqdlxxb-2024.0020

LIU Jinbao, GAO Xiang, ZHANG Xiang, et al. Efficient tetrahedral mesh generation algorithm based on octree refinement[J]. 2025, 43(8): 50-58. DOI： 10.7638/kqdlxxb-2024.0020.

摘要

非结构化四面体网格在复杂几何建模中具有重要应用价值，但现有方法多数需要先生成表面网格，再基于表面网格生成体网格，在大型复杂模型的高精度仿真中往往会出现三维网格生成出错或规模过大的情况。为了克服现有技术中网格生成效率低、鲁棒性较差、实现过程复杂等缺陷，本文提出了一种基于八叉树细化的非结构化四面体网格生成算法。算法采用改进的根四面体网格形状，在保证网格质量的同时使得初始网格单元形状一致，在表面拟合阶段采用网格形状调整和网格分裂两个步骤的实现方式。测试结果表明，本算法可以忽略部分几何模型缺陷，0.9～1.0高质量区间的网格单元占比明显高于其他方法，百万级网格生成耗时较传统方法减少80%以上。该算法能够高效地生成高质量网格，并克服了传统方法的局限性，为非结构化四面体网格生成领域的研究和应用提供了新的思路和参考。

Abstract

Unstructured tetrahedral meshes hold significant application value in complex geometric modeling

yet most existing methods require prior surface mesh generation before volume mesh construction

often leading to 3D mesh generation failures or excessive scale in high-precision simulations of large complex models. To overcome limitations in current techniques

such as low efficiency

poor robustness

and implementation complexity

this paper proposes an octree-refinement-based unstructured tetrahedral mesh generation algorithm. The algorithm adopted an improved root tetrahedral configuration ensuring shape consistency among initial grid units while maintaining quality. Surface fitting was achieved through two operational phases: mesh shape adjustment and mesh splitting. Test results demonstrated the algorithm's tolerance to certain geometric defects

exhibiting a significantly higher proportion of high-quality elements (0.9–1.0 metric range) than other methods

while reducing mesh generation time by over 80% for million-element meshes compared to conventional methods. This approach provides an efficient high-quality mesh generation solution that overcomes traditional limitations

offering new perspectives for research and applications in unstructured tetrahedral mesh generation.

关键词

Keywords

references

BURKHART T A, ANDREWS D M, DUNNING C E. Finite element modeling mesh quality, energy balance and validation methods: A review with recommendations associated with the modeling of bone tissue[J]. Journal of biomechanics, 2013, 46(9): 1477−1488. doi: 10.1016/j.jbiomech.2013.03.022

THOMPSON J F, WEATHERILL N P. Structured and unstructured grid generation[J]. High-Performance Computing in Biomedical Research, 2020: 63-111.

FUJITA K, KATSUSHIMA K, ICHIMURA T, et al. Octree-based multiple-material parallel unstructured mesh generation method for seismic response analysis of soil-structure systems[J]. Procedia Computer Science, 2016, 80: 1624−1634. doi: 10.1016/j.procs.2016.05.496

SHEWCHUK J R. Tetrahedral mesh generation by Delaunay refinement[C]//14th Annual Symposium on Computational Geometry - SCG '98, Minneapolis, Minnesota, USA. ACM, 1998: 86−95. doi: 10.1145/276884.276894

LUO Q B. Automatic delaunay mesh generation method and physically-based mesh optimization method on two-dimensional regions[J]. Engineering with Computers, 2022, 38(Suppl 2): 1021−1031. doi: 10.1007/s00366-020-01262-x

PIRZADEH S. Unstructured viscous grid generation by the advancing-layers method[J]. AIAA Journal, 1994, 32(8): 1735−1737. doi: 10.2514/3.12167

WU H T. Research on AFT of unstructured surface mesh based on ANN[C]//2022 19th International Computer Conference on Wavelet Active Media Technology and Information Processing (ICCWAMTIP), Chengdu, China. IEEE, 2022: 1−5. doi: 10.1109/ICCWAMTIP56608.2022.10016609

JUNG Y H, LEE K. Tetrahedron-based octree encoding for automatic mesh generation[J]. Computer-Aided Design, 1993, 25(3): 141−153. doi: 10.1016/0010-4485(93)90039-Q

HE X, WANG L G, et al. Octree based method for 3D mesh generation of geological bodies[J]. Metal Mine, 2008(11): 66-70 (in Chinese). doi: 10.3321/j.issn:1001-1250.2008.11.020

LIANG X, ZHANG Y. An octree-based dual contouring method for triangular and tetrahedral mesh generation with guaranteed angle range[J]. Engineering with Computers, 2014, 30(2): 211−222. doi: 10.1007/s00366-013-0328-8

GEUZAINE C, REMACLE J F. Gmsh: A 3-D finite element mesh generator with built-in pre- and post-processing facilities[J]. International Journal for Numerical Methods in Engineering, 2009, 79(11): 1309−1331. doi: 10.1002/nme.2579

SI H. TetGen, a Delaunay-based quality tetrahedral mesh generator[J]. ACM Transactions on Mathematical Software, 2015, 41(2): 1-36. doi: 10.1145/2629697

LI H F, WU J C, LIU J B, et al. Finite element mesh generation and decision criteria of mesh quality[J]. China Mechanical Engineering, 2012, 23(3): 10 (in Chinese). doi: 10.3969/j.issn.1004-132X.2012.03.026

AKENINE-MÖLLER T. Fast 3D triangle-box overlap testing[C]//ACM Siggraph 2005 courses. 2005: 8-es. doi: 10.1145/1198555.1198747

KATSUSHIMA K, FUJITA K, ICHIMURA T, et al. Development of octree-based high-quality mesh generation method for biomedical simulation[C]//Computational Science–ICCS, 2018. doi: 10.1007/978-3-319-93701-4_27

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Fast tessellation algorithm for CAD models on anisotropic quadtree grids

Improved boundary recovery method for tetrahedral mesh generation

Hyperbolic unstructured grid generation method of three-dimensional complex configuration

Auto-generation algorithm of surface meshes on dirty geometries

Automatic surface imprinting for misaligned assembly CAD models

Related Author

CHEN Jianjun

WEI Xiangli

LIU Taoran

NI Haonan

XU Jingchao

FU Kejie

ZENG Yinjia

JIANG Qinxue

Related Institution

School of Aeronautics and Astronautics, Zhejiang University, Hangzhou

Beijing Aerohydrodynamic Frontier Research Center, Beijing

National Laboratory for Computational Fluid Dynamics, Beijing

CAEP Software Center for High Performance Numerical Simulation, Beijing

School of Aerospace, Tsinghua University

AI问答

⁰