Fast tessellation algorithm for CAD models on anisotropic quadtree grids

XU Jingchao; NI Haonan; LIU Taoran; WEI Xiangli; CHEN Jianjun

doi:10.7638/kqdlxxb-2024.0061

English Version Journal Login

您当前的位置：

首页 >

文章列表页 >

Fast tessellation algorithm for CAD models on anisotropic quadtree grids

更新时间：2026-05-28

- Fast tessellation algorithm for CAD models on anisotropic quadtree grids
- Vol. 43, Issue 3, Pages: 1-13(2025)
- 作者机构：
  
  浙江大学航空航天学院,杭州,310027
- 作者简介：
- 基金信息：
- DOI：10.7638/kqdlxxb-2024.0061
  CLC： O242
- Published：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 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Efficient tetrahedral mesh generation algorithm based on octree refinement

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

GONG Chunye

ZHANG Xiang

GAO Xiang

LIU Jinbao

FU Kejie

ZENG Yinjia

JIANG Qinxue

TIAN Hao

Related Institution

College of Computer, National University of Defense Technology, Changsha

Laboratory of Digitizing Software for Frontier Equipment, National University of Defense Technology, Changsha

Beijing Aerohydrodynamic Frontier Research Center, Beijing

National Laboratory for Computational Fluid Dynamics, Beijing

CAEP Software Center for High Performance Numerical Simulation, Beijing

AI问答

⁰