基于各向异性四叉树网格的CAD模型快速三角化算法

徐璟潮; 倪浩楠; 刘陶然; 魏祥利; 陈建军

doi:10.7638/kqdlxxb-2024.0061

欢迎来到能源电力期刊网！

English Version 期刊登录

您当前的位置：

首页 >

文章列表页 >

基于各向异性四叉树网格的CAD模型快速三角化算法

研究论文 | 更新时间：2026-05-28

- 基于各向异性四叉树网格的CAD模型快速三角化算法
- Fast tessellation algorithm for CAD models on anisotropic quadtree grids
- 空气动力学学报 2025年43卷第3期页码：1-13
- 作者机构：
  
  浙江大学航空航天学院,杭州,310027
- 作者简介：
  
  徐璟潮（1999—），男，浙江杭州人，硕士研究生，研究方向：网格生成，计算空气动力学，高性能计算. E-mail：2116583183@qq.com
  陈建军*，教授，研究方向：网格生成，计算空气动力学，高性能计算. E-mail：chenjj@zju.edu.cn
- 基金信息：
  
  冲压发动机技术全国重点实验室基金（2022-JCJQ-LB-020-05）;浣江实验室专项项目（KM20220616）
- DOI：10.7638/kqdlxxb-2024.0061
  中图分类号： O242
- 纸质出版：2025
- 稿件说明：
移动端阅览
徐璟潮, 倪浩楠, 刘陶然, 等. 基于各向异性四叉树网格的CAD模型快速三角化算法[J]. 空气动力学学报, 2025, 43(3): 1−13.

XU Jingchao, NI Haonan, LIU Taoran, et al. Fast tessellation algorithm for CAD models on anisotropic quadtree grids[J]. 2025, 43(3): 1-13.
徐璟潮, 倪浩楠, 刘陶然, 等. 基于各向异性四叉树网格的CAD模型快速三角化算法[J]. 空气动力学学报, 2025, 43(3): 1−13. DOI： 10.7638/kqdlxxb-2024.0061

XU Jingchao, NI Haonan, LIU Taoran, et al. Fast tessellation algorithm for CAD models on anisotropic quadtree grids[J]. 2025, 43(3): 1-13. DOI： 10.7638/kqdlxxb-2024.0061.

摘要

计算机辅助设计（computer-aided design

CAD）模型的三角化在工程和科学研究领域中有重要应用，它为模型可视化提供底层数据表征，也可作为计算机辅助工程、计算机辅助制造等CAD下游应用的输入，支持诸如网格生成、数值模拟、快速原型设计等关键领域的研究与应用。本研究提出了一种基于各向异性四叉树背景网格的CAD模型快速三角化算法。该算法通过自底向上构建的算法流程，确保结果的二维流形；在可控容差的曲线离散阶段，通过设计一种基于曲率和曲率一阶导的尺寸函数有效识别特征；而在自适应四叉树快速曲面三角化阶段，通过设计各向异性四叉树，使得三角化的结果满足最小化网格单元的要求。此外，通过后验的混合多阶容差条件实现了与原始CAD输入在不同连续性上的一致性。复杂CAD模型输入下的数值对比实验表明，相比OCC、Gmsh等开源软件以及Ansys等商业软件中同类算法，该算法在几何保形精度、背景网格规模、算法时间效率等方面均体现出不同程度的优势，具有实际工程应用的潜力。

Abstract

Tessellation of computer-aided design (CAD) models plays a crucial role in engineering and scientific domains

offering foundational data for model visualization and serving as input for downstream CAD applications

including computer-aided engineering (CAE) and computer-aided manufacturing (CAM). This research presented a rapid tessellation algorithm for CAD models that employs an anisotropic quadtree background grid. The algorithm

constructed from the ground up

guaranteed the output as two-dimensional manifolds. It featureed a size function reliant on curvature and its first derivative to accurately identify geometric featureed within a controllable tolerance during curve discretization. During the adaptive quadtree phase for swift surface tessellation

it minimized mesh elements

ensuring alignment with the original CAD input through a posteriori hybrid multi-order tolerance criteria. Comparative numerical experiments indicate that this algorithm outperforms existing open-source software

such as OCC and Gmsh

and commercial solutions like Ansys

in geometric accuracy

background grid scale

and computational efficiency

highlighting its potential for practical engineering applications.

关键词

Keywords

references

KLINGNER B M, FELDMAN B E, CHENTANEZ N, et al. Fluid animation with dynamic meshes[J]. ACM Transactions on Graphics (TOG), 2006, 25(3): 820–825.

STAM J. Stable fluids[M]//Seminal Graphics Papers: Pushing the Boundaries, Volume 2. New York, USA: ACM, 2023: 779–786.

DIAZZI L, PANOZZO D, VAXMAN A, et al . Constrained delaunay tetrahedrization: A robust and practical approach[J ] . ACM Transactions on Graphics, 2023 , 42 ( 6 ): 1 − 15 .

GEORGE P L, BOROUCHAKI H. Delaunay triangulation and meshing[M]. 1998.

SHIMADA K . Current issues and tre nds in meshing and geometric processing for computational engineering analyses[J ] . Journal of Computing and Information Science in Engineering, 2011 , 11 ( 2 ): 021008 .

FU K J, LIAO M J, WANG Y S, et al . MeshAC: A 3D mesh generation and adaptation package for multiscale coupling methods[J ] . Computer Physics Communications, 2025 , 310 : 109523 .

DENG L W, YIN J H, HE Q, et al. Research on mesh generation technology based on delaunay triangulation[C]// Proc of the 2024 Joint International Vacuum Electronics Conference and International Vacuum Electron Sources Conference (IVEC + IVESC), Monterey, CA, USA. IEEE, 2024: 1–2.

GARNER K M, TSOLAKIS C, THOMADAKIS P, et al. Towards distributed semi-speculative adaptive anisotropic parallel mesh generation[C]//Proc of the AIAA Aviation Forum and Ascend 2024, Las Vegas, Nevada. AIAA, 2024: 4505.

YU K X, CHEN J J, FU K J, et al . On the efficiency of the advancing-front surface mesh generation algorithm[J ] . Computer-Aided Design, 2022 , 153 : 103403 .

BÉCHET E, CUILLIERE J C, TROCHU F . Generation of a finite element mesh from stereolithography (STL) files[J ] . Computer-Aided Design, 2002 , 34 ( 1 ): 1 − 17 .

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

LIU Y, LO S H, GUAN Z Q, et al . Boundary recovery for 3D Delaunay triangulation[J ] . Finite Elements in Analysis and Design, 2014 , 84 : 32 − 43 .

MAROT C, PELLERIN J, REMACLE J F . One machine, one minute, three billion tetrahedra[J ] . International Journal for Numerical Methods in Engineering, 2019 , 117 ( 9 ): 967 − 990 .

FREY P J, BOROUCHAKI H . Geometric surface mesh optimization[J ] . Computing and Visualization in Science, 1998 , 1 ( 3 ): 113 − 121 .

VAN HUYSSTEEN D, RIVAROLA F L, ETSE G, et al . Quasi-optimal mesh generation for the virtual element method: A fully adaptive remeshing procedure[J ] . Computer Methods in Applied Mechanics and Engineering, 2025 , 435 : 117630 .

CHEN W, SUN S Q, WANG Y, et al. Robust surface remeshing based on conformal welding[M]//Proc of the 2024 International Meshing Roundtable (IMR). Philadelphia, PA: Society for Industrial and Applied Mathematics, 2024.

WANG D, HASSAN O, MORGAN K, et al . EQSM: An efficient high quality surface grid generation method based on remeshing[J ] . Computer Methods in Applied Mechanics and Engineering, 2006 , 195 ( 41-43 ): 5621 − 5633 .

ALEKSANDAR P, PAUL J . A feature-based proposal for blending freedom surfaces[J ] . Journal of Engineering Design, 2002 , 13 ( 4 ): 341 − 349 .

YERRY M A, SHEPHARD M S . Automatic three-dimensional mesh generation by the modified-octree technique[J ] . International Journal for Numerical Methods in Engineering, 1984 , 20 ( 11 ): 1965 − 1990 .

SHOSTKO A A, LÖHNER R, SANDBERG W C . Surface triangulation over intersecting geometries[J ] . International Journal for Numerical Methods in Engineering, 1999 , 44 ( 9 ): 1359 − 1376 .

AUBRY R, DEY S, MESTREAU E L, et al . A robust conforming NURBS tessellation for industrial applications based on a mesh generation approach[J ] . Computer-Aided Design, 2015 , 63 : 26 − 38 .

TABARRAEI A, SUKUMAR N . Adaptive computations on conforming quadtree meshes[J ] . Finite Elements in Analysis and Design, 2005 , 41 ( 7-8 ): 686 − 702 .

JAILLET F, LOBOS C . Fast Quadtree/Octree adaptive meshing and re-meshing with linear mixed elements[J ] . Engineering with Computers, 2022 , 38 ( 4 ): 3399 − 3416 .

ITO Y . Challenges in unstructured mesh generation for practical and efficient computational fluid dynamics simulations[J ] . Com puters Fluids, 2013 , 85 : 47 − 52 .

SCHÖBERL J . NETGEN an advancing front 2D/3D-mesh generator based on abstract rules[J ] . Computing and Visualization in Science, 1997 , 1 ( 1 ): 41 − 52 .

JACOBSON A, KAVAN L, SORKINE-HORNUNG O . Robust inside-outside segmentation using generalized winding numbers[J ] . ACM Transactions on Graphics, 2013 , 32 ( 4 ): 1 − 12 .

ZHENG Y, CHEN J J. Unstructured mesh generation[M]. Beijing: Science Press, 2016 (in Chinese).

CHEN J J, XIAO Z F, ZHENG Y, et al . Automatic sizing functions for unstructured surface mesh generation[J ] . International Journal for Numerical Methods in Engineering, 2017 , 109 ( 4 ): 577 − 608 .

FU K J, CHEN J J, LI J, et al . Automatic unstructured mesh generation approach for simulation of electronic packaging system[J ] . Engineering with Computers, 2023 , 39 ( 5 ): 3527 − 3559 .

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

基于八叉树细化的高效四面体网格生成

四面体网格边界恢复改进算法

三维复杂外形的双曲型非结构网格生成方法

面向脏几何的曲面网格自动生成算法

面向错位装配体的自动曲面嵌入算法