Improved boundary recovery method for tetrahedral mesh generation

ZENG Yinjia; CHEN Jianjun; FU Kejie

doi:10.7638/kqdlxxb-2022.0192

English Version Journal Login

您当前的位置：

首页 >

文章列表页 >

Improved boundary recovery method for tetrahedral mesh generation

更新时间：2026-05-28

- Improved boundary recovery method for tetrahedral mesh generation
- Vol. 41, Issue 10, Pages: 42-51(2023)
- 作者机构：
  
  浙江大学航空航天学院,杭州,310027
- 作者简介：
- 基金信息：
- DOI：10.7638/kqdlxxb-2022.0192
  CLC： TP301.6
- Published：2023
- 稿件说明：
移动端阅览
曾寅家, 陈建军, 傅珂杰. 四面体网格边界恢复改进算法[J]. 空气动力学学报, 2023, 41(10): 42−51.

ZENG Yinjia, CHEN Jianjun, FU Kejie. Improved boundary recovery method for tetrahedral mesh generation[J]. 2023, 41(10): 42-51.
曾寅家, 陈建军, 傅珂杰. 四面体网格边界恢复改进算法[J]. 空气动力学学报, 2023, 41(10): 42−51. DOI： 10.7638/kqdlxxb-2022.0192

ZENG Yinjia, CHEN Jianjun, FU Kejie. Improved boundary recovery method for tetrahedral mesh generation[J]. 2023, 41(10): 42-51. DOI： 10.7638/kqdlxxb-2022.0192.

摘要

Delaunay三角化是生成四面体网格的主流方法，而通过该方法生成的初始网格无法保留所有边界约束，因此边界恢复是Delaunay四面体网格生成的必要步骤。边界恢复的难点在于确定辅助点（Steiner点）的数量和位置，以及降低Steiner点引发的负面效应。为此，本文提出了一种改进的四面体网格边界恢复方法，旨在提高约束边界恢复成功率，并减少加入的Steiner点数量。该方法总体流程由“两层+两轮”迭代构成，流程充分利用了约束边界恢复方法和体内Steiner点插入方法的优势，降低了边界恢复对边界约束的破坏。方法首先针对递归壳变换算法容易陷入局部最优解的问题，通过引入模拟退火算法加以解决，提出了一种改进的约束边界恢复方法；然后对于方法中的“网格实体—边界实体求交”关键环节，引入或实现了AABB树、几何精确的“线面相交”函数、交点数查询哈希算法三个关键方法加以优化；最后对于拓扑变换无法恢复的边界，实现了体内、边界两种Steiner点插入方法。实验阶段取用了Thingi10k数据集的4000余例面网格样本进行测试，结果表明该方法有效提高了约束边界恢复的成功率，并能普遍性地减少边界恢复引入的Steiner点数量。

Abstract

Delaunay triangulation is a mainly used method for tetrahedral mesh generation

but the initial mesh generated by this method cannot include all boundary constraints

so the boundary recovery is a necessary step for the generation of Delaunay tetrahedral mesh. The difficulty of boundary recovery lies in determining the number and location of auxiliary points (Steiner points) and reducing the negative effects caused by Steiner points. In this study

an improved boundary recovery method for Delaunay tetrahedral mesh generation is proposed

which aims to increase the success rate of constrained recovery and reduce the number of Steiner points added during the boundary recovery. The overall process of this method is composed of a double iteration with two rounds inside

which fully utilizes the advantages of the constrained boundary recovery method and the interior Steiner point insertion method

and reduces the number of broken boundary constraints caused by boundary restoration. This method firstly solves the problem that the recursive shell transformation algorithm tends to fall into the local optimum

by introducing the simulated annealing algorithm

and an improved constrained boundary recovery method is proposed. Then

three key methods

including the AABB tree

the geometrically accurate "line and surface intersection" function

and a hash algorithm for intersection count query

are introduced or proposed to improve the efficiency and robustness of finding the intersection between mesh entities and boundary entities. Finally

for boundaries that cannot be recovered by topological transformation

the interior and boundary Steiner points are inserted. The proposed method is tested on more than 4

000 surface mesh samples of the Thingi10k dataset

which shows that the success rate of constrained boundary recovery is effectively improved

and meanwhile the number of Steiner points introduced by the boundary recovery is generally reduced.

关键词

Keywords

references

DELAUNAY B. Sur la sphère vide. A la mémoire de Georges Voronoï[J ] . Bulletin de l'Académie des Sciences de l'URSS. Classe des sciences mathématiques et na. 1934, (6): 793-800. https://www.mathnet.ru/links/8a4745807f1f9ec0bcb81167b2a8a7ce/im4937.pdf

SCHÖNHARDT E. Über Die zerlegung von dreieckspolyedern in tetraeder[J]. Mathematische Annalen, 1928, 98(1): 309-312. DOI: 10.1007/BF01451597

CHAZELLE B. Convex partitions of polyhedra: a lower bound and worst-case optimal algorithm[J]. SIAM Journal on Computing, 1984, 13(3): 488-507. DOI: 10.1137/0213031

RUPPERT J, SEIDEL R. On the difficulty of triangulating three-dimensional Nonconvex Polyhedra[J]. Discrete Computational Geometry, 1992, 7(3): 227-253. DOI: 10.1007/BF02187840

CHEN J J, ZHENG J J, ZHENG Y, et al. Improved boundary constrained tetrahedral mesh generation by shell transformation[J]. Applied Mathematical Modelling, 2017, 51: 764-790. DOI: 10.1016/j.apm.2017.07.011

ZHOU Q, JACOBSON A. Thingi10k: A dataset of 10, 000 3d-printing models[J]. arXiv preprint arXiv: 1605.04797, 2016.

RADON J. Mengen konvexer Körper, Die einen gemeinsamen punkt enthalten[J]. Mathematische Annalen, 1921, 83(1): 113-115. DOI: 10.1007/BF01464231

JOE B. Construction of three-dimensional improved-quality triangulations using local transformations[J]. SIAM Journal on Scientific Computing, 1995, 16(6): 1292-1307. DOI: 10.1137/0916075

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

LIU J F, CHEN B, CHEN Y Q. Boundary recovery after 3D Delaunay tetrahedralization without adding extra nodes[J]. International Journal for Numerical Methods in Engineering, 2007, 72(6): 744-756. DOI: 10.1002/nme.2044

CHEN J J, ZHAO D W, HUANG Z G, et al. Three-dimensional constrained boundary recovery with an enhanced Steiner point suppression procedure[J]. Computers Structures, 2011, 89(5-6): 455-466. DOI: 10.1016/j.compstruc.2010.11.016

MAROT C, VERHETSEL K, REMACLE J F. Reviving the search for optimal tetrahedralizations[C ] //28th International Meshing Roundtable, 2020. https://internationalmeshingroundtable.com/assets/papers/2019/22-Marot.pdf doi: 10.5281/ZENODO.3653420

郑建靖. 面向并行计算流体动力学模拟的非结构动网格生成的若干问题研究[D]. 杭州: 浙江大学, 2016.

GEORGE P L, HECHT F, SALTEL E. Automatic mesh generator with specified boundary[J]. Computer Methods in Applied Mechanics and Engineering, 1991, 92(3): 269-288. DOI: 10.1016/0045-7825(91)90017-z

LIU A W, BAIDA M. How far flipping can go towards 3D conforming/constrained triangulation[C]//9th International Meshing Roundtable Conference, 2000.

SHEWCHUK J. Constrained delaunay tetrahedralizations and provably good boundary recovery[C ] // International Meshing Roundtable Conference, 2002. https://people.eecs.berkeley.edu/~jrs/papers/cdtbasic.pdf

WEATHERILL N P, HASSAN O. Efficient three-dimensional Delaunay triangulation with automatic point creation and imposed boundary constraints[J]. International Journal for Numerical Methods in Engineering, 1994, 37(12): 2005-2039. DOI: 10.1002/nme.1620371203

陈建军. 非结构化网格生成及其并行化的若干问题研究[D]. 杭州: 浙江大学, 2006.

CHEN J J, ZHENG Y. Redesign of a conformal boundary recovery algorithm for 3D Delaunay triangulation[J]. Journal of Zhejiang University-SCIENCE A, 2006, 7(12): 2031-2042. DOI: 10.1631/jzus.2006.A2031

GOERIGK N, SI H. On indecomposable polyhedra and the number of steiner points[J]. Procedia Engineering, 2015, 124: 343-355. DOI: 10.1016/j.proeng.2015.10.144

SI H. On decomposition of embedded prismatoids in R 3 without additional points[R ] //GARANZHA V A, KAMENSKI L, SI H, eds. Numerical Geometry, Grid Generation and Scientific Computing. Lecture Notes in Computational Science and Engineering, 2021, 143: 95-111. doi: 10.1007/978-3-030-76798-3_6

SI H, GOERIGK N. On tetrahedralisations of generalised Chazelle polyhedra with interior Steiner points[J]. Computer-Aided Design, 2018, 103: 61-72. DOI: 10.1016/j.cad.2017.11.005

GEORGE P L, BOROUCHAKI H, SALTEL E. ‘Ultimate’ robustness in meshing an arbitrary polyhedron[J]. International Journal for Numerical Methods in Engineering, 2003, 58(7): 1061-1089. DOI: 10.1002/nme.808

DU Q, WANG D S. Constrained boundary recovery for three dimensional Delaunay triangulations[J]. International Journal for Numerical Methods in Engineering, 2004, 61(9): 1471-1500. DOI: 10.1002/nme.1120

郑耀, 陈建军. 非结构网格生成: 理论、算法和应用[M]. 北京: 科学出版社, 2016.

METROPOLIS N, ROSENBLUTH A, ROSENBLUTH M, et al. Simulated annealing[J]. Journal of Chemical Physics, 1953, 21(161-162): 1087-1092.

AARTS E, KORST J. Simulated annealing and Boltzmann machines: a stochastic approach to combinatorial optimization and neural computing[M]. John Wiley Sons, Inc. , 1989.

BOWYER A. Computing dirichlet tessellations[J]. The computer journal, 1981, 24(2): 162-166.

WATSON D F. Computing the n-dimensional delaunay tessellation with application to voronoi polytopes[J]. The Computer Journal, 1981, 24(2): 167-172. DOI: 10.1093/comjnl/24.2.167

SI H. Three dimensional boundary conforming Delaunay mesh generation[M ] . Technische Universitaet Berlin (Germany), 2008. https://api-depositonce.tu-berlin.de/server/api/core/bitstreams/3157c794-7ad0-4888-ad90-98b778906413/content

INGBER L. Very fast simulated re-annealing[J]. Mathematical and Computer Modelling, 1989, 12(8): 967-973. DOI: 10.1016/0895-7177(89)90202-1

BERGEN G VAN DEN. Efficient collision detection of complex deformable models using AABB trees[J]. Journal of Graphics Tools, 1997, 2(4): 1-13. Doi: 10.1080/10867651.1997.10487480

GUIGUE P, DEVILLERS O. Fast and robust triangle-triangle overlap test using orientation predicates[J]. Journal of Graphics Tools, 2003, 8(1): 25-32. DOI: 10.1080/10867651.2003.10487580

SI H, GÄRTNER K. 3D boundary recovery by constrained Delaunay tetrahedralization[J]. International Journal for Numerical Methods in Engineering, 2011, 85(11): 1341-1364. DOI: 10.1002/nme.3016

RUPPERT J. A delaunay refinement algorithm for quality 2-dimensional mesh generation[J]. Journal of Algorithms, 1995, 18(3): 548-585. DOI: 10.1006/jagm.1995.1021

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Efficient tetrahedral mesh generation algorithm based on octree refinement

Fast tessellation algorithm for CAD models on anisotropic quadtree grids

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

WEI Xiangli

LIU Taoran

NI Haonan

XU Jingchao

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问答

⁰