面向有限元分析的三角网格布尔运算方法

doi:10.16182/j.issn1004731x.joss.20-0957

摘要/Abstract

摘要：

为加速有限元分析流程，提出了一种面向有限元分析的自适应三角网格模型布尔运算方法。将ADT（alternating digital tree）数据结构应用于三角面片的判交计算，提升了布尔运算中三角面片的判交效率；借鉴结合球填充算法和插点/去点算法的网格重生成方法来重剖分局部区域，保证了算法的效率和生成网格的质量；通过改进的八叉树背景网格来记录和光滑尺寸场，生成了自适应的网格；通过尺寸场合理地控制重剖分区域，使算法效率和生成网格的质量得以很好地平衡。实验结果表明，所提方法可以高效地生成满足有限元分析需求的网格。

关键词: 布尔运算, 自适应, 三角网格, 有限元, ADT

Abstract:

To shorten the cycle of finite element analysis (FEA), an adaptive triangular mesh Boolean operation method for finite element analysis is proposed. The ADT (alternating digital tree) data structure is applied to the intersection calculation of triangular meshes, which improves the efficiency of the intersection calculation of Boolean operations. A sphere packing algorithm and a node addition/deletion algorithm are used to remesh some remeshing regions, which ensures the efficiency of the method and the high-quality of remeshed meshes. An improved octree background grid is used to record and smooth the size field, which can generate size-adaptive meshes. The size field is used to reasonably control remeshing regions, which ensures the efficiency and mesh quality of the method. Results show that the proposed method can efficiently generate meshes that meet the needs of FEA.

Key words: Boolean operation, adaptive, triangular mesh, finite element, ADT(alternating digital tree)

中图分类号:

TP391.9

郭宇飞, 赵康, 海永清. 面向有限元分析的三角网格布尔运算方法[J]. 系统仿真学报, 2022, 34(5): 1003-1014.

Yufei Guo, Kang Zhao, Yongqing Hai. Triangular Mesh Boolean Operation Method for Finite Element Analysis[J]. Journal of System Simulation, 2022, 34(5): 1003-1014.

图/表 17

图1

图2

图3

图4

图5

图6

图7

图8

图9

表1

图10

表2

图11

图12

图13

图14

表3

参考文献 57

[1]	Stark J. Product Lifecycle Management: Paradigm for 21st Century Product Realization[M]. Berlin: Springer-Verlag, 2004.
[2]	Tichkiewitch S, Brissaud D. Methods and Tools for Co-operative and Integrated Design[M]. Netherlands: Springer, 2004.
[3]	Lou R, Pernot J P, Mikchevitch A, et al. Merging Enriched Finite Element Triangle Meshes for Fast Prototyping of Alternate Solutions in the Context of Industrial Maintenance[J]. Computer-Aided Design (S0010-4485), 2010, 42(8): 670-681.
[4]	Karamete B K, Dey S, Mestreau E L, et al. An Algorithm for Discrete Booleans with Applications to Finite Element Modeling of Complex Systems[J]. Finite Elements in Analysis and Design (S0168-874X), 2013, 68(6): 10-27.
[5]	Basaran C. Solving Large-scale Problems in Mechanics: the Development and Application of Computational Solution Methods[J]. International Journal for Numerical and Analytical Methods in Geomechanics (S0363-9061), 1994, 18(2): 139-140.
[6]	The Cgal Project. CGAL User and Reference Manual[K/OL]. (2019-03-29) [2020-11-08]. .
[7]	Douze M, Franco J S, Raffin B. QuickCSG: Fast Arbitrary Boolean Combinations of N Solids[DB/OL]. (2017-06-05) [2020-10-04]. .
[8]	CARVE: an Efficient and Robust Library for Boolean Operations on Polyhedral[DB/OL]. [2020-11-08]. .
[9]	BERNSTEIN G. Cork Boolean Library[DBOL]. [2020-11-08]. .
[10]	Cebral J R, Camelli F E, Löhner R. A Feature-Preserving Volumetric Technique to Merge Surface Triangulations[J]. International Journal for Numerical Methods in Engineering (S0029-5981), 2002, 55(2): 177-190.
[11]	Pavić D, Campen M, Kobbelt L. Hybrid Booleans. Computer Graphics Forum (S0167-7055), 2010, 29(1): 75-87.
[12]	Wang C C. Approximate Boolean Operations on Large Polyhedral Solids with Partial Mesh Reconstruction[J]. IEEE Transactions on Visualization & Computer Graphics (S1077-2626), 2011, 17(6): 836-849.
[13]	Museth K, Breen D. Level Set Surface Editing Operators[J]. ACM Transactions on Graphics (TOG) (S0730-0301), 2002, 21(3): 330-338.
[14]	Lo S H, Wang W X. A Fast Robust Algorithm for the Intersection of Triangulated Surfaces[J]. Engineering with Computers (S0177-0667), 2004, 20(1): 11-21.
[15]	Elsheikh A H, Elsheikh M. A Reliable Triangular Mesh Intersection Algorithm and its Application in Geological Modelling[J]. Engineering with Computers (S0177-0667), 2012, 30(1): 143-157.
[16]	Guo K B, Zhang L C, Wang C J, et al. Boolean Operations of STL Models based on Loop Detection[J]. The International Journal of Advanced Manufacturing Technology (S0268-3768), 2006, 33(5/6): 627-633.
[17]	Jiang X, Peng Q, Cheng X, et al. Efficient Booleans Algorithms for Triangulated Meshes of Geometric Modeling[J]. Computer-Aided Design and Applications (S1686-4360), 2016, 13(4): 419-430.
[18]	Feito F R, Ogayar C J, Segura R J, et al. Fast and Accurate Evaluation of Regularized BOOLEAN Operations on Triangulated Solids[J]. Computer-Aided Design (S0010-4485), 2013, 45(3): 705-716.
[19]	Lo S H. Automatic Merging of Tetrahedral Meshes[J]. International Journal for Numerical Methods in Engineering (S0029-5981), 2013, 93(11): 1191-1215.
[20]	Lo S H, Wang W X. Finite Element Mesh Generation Over Intersecting Curved Surfaces by Tracing of Neighbours[J]. Finite Elements in Analysis and Design (S0168-874X), 2005, 41(4): 351-370.
[21]	Zou Y, Ding G, He Y. Fast Intersection Algorithm between Spatial Triangle Pairs[J]. Journal of Southwest Jiaotong University (S0258-2724), 2011, 46(6): 984-988.
[22]	Möller, Tomas. A Fast Triangle-Triangle Intersection Test[J]. Journal of Graphics Tools(S2165-3488), 1997, 2(2): 25-30.
[23]	Guigue P, Devillers O. Fast and Robust Triangle-Triangle Overlap Test Using Orientation Predicates[J]. Journal of Graphics Tools (S2165-3488), 2003, 8(1): 25-32.
[24]	Tropp O, Tal A, Shimshoni I. A Fast Triangle to Triangle Intersection Test for Collision Detection[J]. Computer Animation & Virtual Worlds (S1546-4261), 2006, 17(5): 527-535.
[25]	Campen M, Kobbelt L. Exact and Robust (Self-) Intersections for Polygonal Meshes[J]. Computer Graphics Forum (S0167-7055), 2010, 29(2): 397-406.
[26]	Klosowski J T, Held M, Joseph S B, et al. Efficient Collision Detection Using Bounding Volume Hierarchies of K-DOPs[J]. IEEE Transactions on Visualization and Computer Graphics (S1077-2626), 1998, 4(1): 21-36.
[27]	Chang J W, Kim M S. Efficient Triangle–Triangle Intersection Test for OBB-Based Collision Detection[J]. Computers & Graphics (S0167-7055), 2009, 33(3): 235-240.
[28]	Bergen G V D. Efficient Collision Detection of Complex Deformable Models Using AABB Trees[J]. Journal of Graphics Tools (S2165-3488), 1997, 2(4): 1-13.
[29]	Munjiza A, Andrews K R F. NBS Contact Detection Algorithm for Bodies of Similar Size[J]. International Journal for Numerical Methods in Engineering (S0029-5981), 1998, 43(1): 131-149.
[30]	Gu X, Gortler S J, Hoppe H. Geometry Images[J]. Acm Transactions on Graphics (S0730-0301), 2002, 21(3): 355-361.
[31]	Surazhsky V, Alliez P, Gotsman C. Isotropic Remeshing of Surfaces: a Local Parameterization Approach[C]//12th International Meshing Roundtable. Santa Fe, New Mexico, USA: Sandia National Laboratory, 2003: 215-224.
[32]	Lai Y K, Jin M, Xie X, et al. Metric-Driven RoSy Field Design and Remeshing[J]. IEEE Transactions on Visualization & Computer Graphics (S1077-2626), 2010, 16(1): 95-108.
[33]	黄劲, 张沐阳, 裴文杰, 等. 可控的高度规整三角网格生成算法[J]. 中国科学：信息科学, 2011, 54(6): 1172-1183.
	Huang Jin, Zhang Muyang, Pei Wenjie, et al. Controllable Highly Regular Triangulation[J]. Science China: Information Sciences, 2011, 54(6): 1172-1183.
[34]	Chen Z, Cao J, Wang W. Isotropic Surface Remeshing Using Constrained Centroidal Delaunay Mesh[J]. Computer Graphics Forum (S0167-7055), 2012, 31(7): 2077-2085.
[35]	Yan D M, Lévy B, Liu Y, et al. Isotropic Remeshing with Fast and Exact Computation of Restricted Voronoi Diagram[J]. Computer Graphics Forum (S0167-7055), 2009, 28(5): 1445-1454.
[36]	Bonet J, Peraire J. An Alternating Digital Tree (ADT) Algorithm for 3D Geometric Searching and Intersection Problems[J]. International Journal for Numerical Methods in Engineering (S0029-5981), 1991, 31(1): 1-17.
[37]	G T. Re-Tiling Polygonal Surfaces[C]//19th Annual Conference on Computer Graphics and Interactive Techniques. Chicago: SIGGRAPH, 1992: 55-64.
[38]	郭宇飞, 尚菲菲, 刘剑飞. 基于球填充法的STL模型曲面自适应网格生成方法[J]. 计算机辅助设计与图形学学报, 2018, 30(4): 549-556.
	Guo Yufei, Shang Feifei, Liu Jianfei. Surface Adaptive Mesh Generation for STL Models Based on Ball-Packing Method[J]. Journal of Computer-Aided Design & Computer Graphics, 2018, 30(4): 549-556
[39]	Quadros W R, Vyas V, Brewer M, et al. A Computational Framework for Automating Generation of Sizing Function in Assembly Meshing Via Disconnected Skeletons[J]. Engineering with Computers (S0177-0667), 2010, 26(3): 231-247.
[40]	Kania L, Pirzadeh S. A Geometrically-Derived Background Function for Automated Unstructured Mesh Generation[C]//AIAA Computational Fluid Dynamics Conference. Orlando, FL: AIAA, 2005.
[41]	Chen J, Xiao Z, Zheng Y, et al. Automatic Sizing Functions for Unstructured Surface Mesh Generation[J]. International Journal for Numerical Methods in Engineering (S0029-5981), 2017, 109(4): 577-608.
[42]	Quadros W R, Shimada K, Owen S J. Skeleton-Based Computational Method for the Generation of a 3D Finite Element Mesh Sizing Function[J]. Engineering with Computers (S0177-0667), 2004, 20(3): 249-264.
[43]	Pippa S, Caligiana G. GradH-Correction: Guaranteed Sizing Gradation in Multi-patch Parametric Surface Meshing[J]. International Journal for Numerical Methods in Engineering (S0029-5981), 2005, 62(4): 495-515.
[44]	Borouchaki H, Frey P J. Mesh Gradation Control[J]. International Journal for Numerical Methods in Engineering (S0029-5981), 1999, 43(6): 1143-1165.
[45]	Persson P O. Mesh Size Functions for Implicit Geometries and PDE-Based Gradient Limiting[J]. Engineering with Computers (S0177-0667), 2006, 22(2): 95-109.
[46]	McMorris H, Kallinderis Y. Octree-Advancing Front Method for Generation of Unstructured Surface and Volume Meshes[J]. AIAA Journal (S0001-1452), 2015, 35(6): 976-984.
[47]	Deister F, Tremel U, Hassan O, et al. Fully Automatic and Fast Mesh Size Specification for Unstructured Mesh Generation[J]. Engineering with Computers (S0177-0667), 2004, 20(3): 237-248.
[48]	Liu J F. Automatic Triangulation of N-D Domains[C]//CAD/Graphics'91. Hangzhou: CCF, 1991: 238-241.
[49]	Liu J. Automatic Mesh Generation of 3-D Geometric Models[J]. Acta Mechanica Sinica (S0567-7718), 2003, 19(3): 285-288.
[50]	Kenji S. Physically-Based Mesh Generation: Automated Triangulation of Surfaces and Volumes Via Bubble Packing[M]. Cambridge, MA: Massachusetts Institute of Technology, 1993.
[51]	Shimada K, Gossard D C. Automatic Triangular Mesh Generation of Trimmed Parametric Surfaces for Finite Element Analysis[J]. Computer Aided Geometric Design (S0167-8396), 1998, 15(3): 199-222.
[52]	Shimada K, Yamada A, Itoh T. Anisotropic Triangulation of Parametric Surfaces Via Close Packing of Ellipsoids[J]. International Journal of Computational Geometry & Applications (S0218-1959), 2000, 10(4): 417-440.
[53]	Yamakawa S, Shimada K. Anisotropic Tetrahedral Meshing Via Bubble Packing and Advancing Front[J]. International Journal for Numerical Methods in Engineering (S0029-5981), 2003, 57(13): 1923-1942.
[54]	Cheng S W, Jin J. Edge Flips and Deforming Surface Meshes[C]//ACM Symposium on Computational Geometry. New York, NY: ACM, 2011: 331-340.
[55]	Surazhsky V, Gotsman C. Explicit Surface Remeshing[C]//Eurographics Symposium on Geometry Processing. Aachen. Germany: Eurographics Association, 2003: 1-11.
[56]	Simon F, Jens A, Thomas K, et al. Direct Resampling for Isotropic Surface Remeshing[C]//Vision, Modeling, & Visualization Workshop. Siegen, Germany: DBLP, 2010: 9-16.
[57]	Dunyach M, Vanderhaeghe D, Barthe L, et al. Adaptive Remeshing for Real-Time Mesh Deformation[C]//Eurographics-Short Papers. Girona, Spain: The Eurographics Association, 2013: 29-32.

模型	文献	节点	时间/s	最小角/?(°)	平均最小角/(°)
Fandisk	[55]	5 100	17.000	17.000	49.000
	[35]	3 000	40.000	24.350	51.680
	[56]	4 000	3.000	21.000	53.000
	[57]	4 000	0.250	18.000	49.000
	本文	3 046	0.203	19.400	53.717
Joint	[35]	6 000	66.120	24.950	53.510
	[34]	6 000	3.640	29.890	53.410
	[57]	3 100	0.640	15.000	47.000
	本文	6 391	0.453	28.786	57.134
Horse	[55]	5 600	28.000	9.100	50.000
	[56]	6 000	16.000	30.000	52.000
	[57]	6 000	0.940	28.000	51.000
	本文	5 872	11.235	20.700	50.530

?算例	优化	单元数	最小角/(°)	最大角/(°)	不同内角三角片数
?算例	优化	单元数	最小角/(°)	最大角/(°)	0°~15°	15°~30°	150°~165°	165°~180°
1	优化前	62 363	0.03	178.52	623	306	57	30
1	优化后	65 405	8.82	158.20	2	44	2	0
2	优化前	3 122	0.26	178.00	221	158	24	23
2	优化后	2 704	17.80	121.10	0	12	0	0
3	优化前	31 558	0.02	179.41	13 172	3 691	1 659	3 099
3	优化后	60 942	4.13	134.91	88	431	0	0
4	优化前	48 260	0.15	179.30	5 932	7 418	412	127
4	优化后	47 196	0.30	179.30	5 254	6 992	338	100
5	优化前	2 434	0.01	176.44	343	235	36	11
5	优化后	1 868	0.07	176.44	93	139	10	3

算例	CGAL	本文方法?(未采用ADT)	本文方法?(采用ADT)
1	4.187	260.974	1.267
2	0.631	8.642	0.153
3	4.234	173.342	1.135
4	17.475	473.251	3.703
5	3.975	27.343	0.938	s