重叠网格装配中的一种改进ADT搜索方法

李鹏; 高振勋; 蒋崇文; 李椿萱

doi:10.13700/j.bh.1001-5965.2016.0425

重叠网格装配中的一种改进ADT搜索方法

doi: 10.13700/j.bh.1001-5965.2016.0425

北京航空航天大学航空科学与工程学院, 北京 100083

基金项目:

航空科学基金 20141251015

详细信息

作者简介:
李鹏, 男, 博士研究生。主要研究方向:计算流体力学

高振勋, 男, 博士, 讲师。主要研究方向:计算流体力学

通讯作者:
高振勋, E-mail:gaozhenxun@buaa.edu.cn

中图分类号: V211.3;TP311.1
计量
- 文章访问数: 931
- HTML全文浏览量: 158
- PDF下载量: 467
- 被引次数: 0
出版历程
- 收稿日期: 2016-05-20
- 录用日期: 2016-08-25
- 网络出版日期: 2017-06-20

Improved ADT searching method in overlapping grid assembly

School of Aeronautic Science and Engineering, Beijing University of Aeronautics and Astronautics, Beijing 100083, China

Funds:

Aeronautical Science Foundation of China 20141251015

More Information

Corresponding author: GAO Zhenxun, E-mail:gaozhenxun@buaa.edu.cn

摘要

摘要:
针对现有交替数字二叉树（ADT）方法的不足，引入辅助笛卡儿网格提出了一种基于散列数据结构的改进搜索方法以缓解可能出现堆栈溢出的问题和提高重叠网格装配的效率。该方法以散列数据结构的方式对网格单元进行存储和搜索，首先以辅助笛卡儿网格对网格单元的存储空间进行初步映像，然后基于ADT搜索树作进一步检索。在ADT搜索方法的基础上，笛卡儿网格的引入进一步缩小了网格单元的搜索范围使得改进方法具有更好的效率。基于单个网格节点，查询深度和搜索耗时的测试显示改进方法相比现有ADT搜索方法能使挖洞的平均效率提高25%以上。此外，挖洞结果和基于网格装配的数值计算验证了改进搜索方法在重叠网格装配中的可靠性。
- 重叠网格 /
- 网格装配 /
- 交替数字二叉树(ADT) /
- 贡献单元 /
- 搜索方法
Abstract:
An improved searching method of alternating digital tree (ADT) is proposed for making up the deficiency of the existing ADT method and improving the efficiency of the overlapping grid assembly. The new method stores and retrieves donor cells based on a hash data structure, in which an auxiliary Cartesian mesh is first applied to map the storage address similar to the table of contents in hash table, and then a node-oriented ADT is used for further retrieval in accordance with the aforementioned storage space. Based on ADT search, the introduction of the Cartesian mesh can further narrow the search scope of donor cell, which makes the present one have better efficiency. Tests of searching depth and time consumption based on several discrete grid nodes indicate that the present method can enhance the average hole-cutting efficiency by more than 25% compared with the existing ADT method. Moreover, the hole-cutting results and numerical computations of typical configurations confirm the reliability of the improved ADT searching method in overlapping grid assembly.
- overlapping grid /
- grid assembly /
- alternating digital tree (ADT) /
- donor cell /
- searching method

HTML全文

图 1 包围单元法和Nirschl矢量判别法

Figure 1. Enclosing element method and Nirschl's vector method

下载: 全尺寸图片幻灯片

图 2 散列表的数据映像存储示意图

Figure 2. Schematic of data mapping storage for hash table

下载: 全尺寸图片幻灯片

图 3 散列表搜索方法示意图

Figure 3. Schematic of hash table searching method

下载: 全尺寸图片幻灯片

图 4 基于网格节点ADT的存储示意图

Figure 4. Schematic of storage for grid node-oriented ADT

下载: 全尺寸图片幻灯片

图 5 搜索单元的构造示意图

Figure 5. Schematic for construction of searching cell

下载: 全尺寸图片幻灯片

图 6 贡献单元的检索过程示意图

Figure 6. Schematic for procedure of retrieving donor cell

下载: 全尺寸图片幻灯片

图 7 多ADT检索的数据存储结构

Figure 7. Data storage structure of multi-ADT retrieval

下载: 全尺寸图片幻灯片

图 8 测试点在原始网格中的位置

Figure 8. Location of testing nodes in primary meshes

下载: 全尺寸图片幻灯片

图 9 洞映射过程的挖洞耗时

Figure 9. Hole-cutting time consumption of hole-map process

下载: 全尺寸图片幻灯片

图 10 30P30N翼型的挖洞结果

Figure 10. Hole-cutting results of 30P30N airfoil

下载: 全尺寸图片幻灯片

图 11 直机翼-带舵导弹模型的挖洞结果

Figure 11. Hole-cutting results of WFS model

下载: 全尺寸图片幻灯片

图 12 30P30N三段翼型的数值计算结果

Figure 12. Numerical computation results of three-element 30P30N airfoil

下载: 全尺寸图片幻灯片

图 13 半圆球的数值计算结果

Figure 13. Numerical computation results of hemisphere

下载: 全尺寸图片幻灯片

图 14 直机翼-带舵导弹模型的数值计算结果

Figure 14. Numerical computation results of WFS model

下载: 全尺寸图片幻灯片

表 1 30P30N翼型的搜索深度测试结果

Table 1. Test results of searching depth for 30P30N airfoil

节点编号	搜索深度/次		搜索耗时/ms		搜索耗时减少比例/%
节点编号	ADT方法	改进ADT方法	ADT方法	改进ADT方法	搜索耗时减少比例/%
N₁	2 884	1 120	0.312 5	0.125 0	60.00
N₂	8 492	4 630	0.937 5	0.625 0	33.33
N₃	14 588	9 499	1.250 0	0.937 5	25.00

下载: 导出CSV

表 2 直机翼-带舵导弹模型的搜索深度测试结果

Table 2. Test results of searching depth for WFS model

节点编号	搜索深度/次		搜索耗时/ms		搜索耗时减少比例/%
节点编号	ADT方法	改进ADT方法	ADT方法	改进ADT方法	搜索耗时减少比例/%
N₁	23 818	19 516	8.125	6.562 5	19.23
N₂	46 971	22 440	15.938	7.187 5	54.90
N₃	89 508	67 443	30.313	22.813 0	24.74

下载: 导出CSV

表 3 30P30N三段翼型的挖洞耗时

Table 3. Hole-cutting time consumption of three-element 30P30N airfoil

l	优化挖洞耗时/s		全部挖洞耗时/s		全部挖洞耗时减少比例/%
l	ADT方法	改进ADT方法	ADT方法	改进ADT方法	全部挖洞耗时减少比例/%
0.01	30.640 6	18.066 4	32.156 3	18.851 6	41.38
0.02	30.625 0	18.105 5	33.871 1	19.785 2	41.59
0.05	30.714 8	18.179 7	37.152 3	21.238 3	42.83
0.10	30.898 4	18.128 9	38.796 9	21.914 1	43.52

下载: 导出CSV

表 4 直机翼-带舵导弹模型的挖洞耗时

Table 4. Hole-cutting time consumption of WFS model

l	优化挖洞耗时/s		全部挖洞耗时/s		全部挖洞耗时减少比例/%
l	ADT方法	改进ADT方法	ADT方法	改进ADT方法	全部挖洞耗时减少比例/%
0.005	220.454	154.092	232.382 2	163.859 4	29.49
0.010	216.739	153.463	250.248 8	182.775 3	26.96
0.015	221.128	152.766	273.539 3	199.316 0	27.13
0.018	219.326	154.508	282.780 9	211.487 7	25.21

下载: 导出CSV

参考文献(28)

[1]	李鹏, 高振勋, 蒋崇文.重叠网格方法的研究进展[J].力学与实践, 2014, 36(5):551-565. doi: 10.6052/1000-0879-14-011 LI P, GAO Z X, JIANG C W.Progress of the overlapping grid techniques[J].Mechanics in Engineering, 2014, 36(5):551-565(in Chinese). doi: 10.6052/1000-0879-14-011
[2]	PREWITT N, BELK D, SHYY W.Parallel computing of overset grids for aerodynamic problems with moving objects[J].Progress of Aerospace Science, 2000, 36(2):117-172. doi: 10.1016/S0376-0421(99)00013-5
[3]	BLANC F.Patch assembly:An automated overlapping grid assembly strategy[J].Journal of Aircraft, 2010, 47(1):110-119. doi: 10.2514/1.44116
[4]	MEAKING R L.A new method for establishing intergrid communication among systems of overset grids:AIAA-1991-1586[R].Reston:AIAA, 1991.
[5]	阎超.计算流体力学方法及应用[M].北京:北京航空航天大学出版社, 2006:200-208. YAN C.Computational fluid dynamics methods and applications[M].Beijing:Beihang University Press, 2006:200-208(in Chinese).
[6]	张来平, 邓小刚, 张涵信.动网格生成技术及非定常计算方法进展综述[J].力学进展, 2010, 40(4):424-447. doi: 10.6052/1000-0992-2010-4-J2009-123 ZHANG L P, DENG X G, ZHANG H X.Reviews of moving grid generation techniques and numerical methods for unsteady flows[J].Advances in Mechanics, 2010, 40(4):424-447(in Chinese). doi: 10.6052/1000-0992-2010-4-J2009-123
[7]	田书玲. 基于非结构网格方法的重叠网格算法研究[D]. 南京: 南京航空航天大学, 2008: 43-74. TIAN S L.Study of overset grids methods based on unstructured grids[D].Nanjing:Nanjing University of Aeronautics and Astronautics, 2008:43-74(in Chinese).
[8]	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, 1991, 31(1):1-17. doi: 10.1002/(ISSN)1097-0207
[9]	BROWN R A.Building a balanced k-d tree in O(kn log n) time[J].Journal of Computer Graphics Techniques, 2015, 4(1):50-68.
[10]	MARSTIN C W, MCCONNAUGHEY H V.Computational problems on composite grids:AIAA-1984-1611[R].Reston:AIAA, 1984.
[11]	BELK D M, MAPLE R C.Automated assembly of structured grids for moving body problems:AIAA-1995-1680[R].Reston:AIAA, 1995.
[12]	袁武, 阎超, 于剑, 等.基于虚网格的格心ADT搜索法[J].北京航空航天大学学报, 2012, 38(10):1375-1379. http://bhxb.buaa.edu.cn/CN/abstract/abstract12427.shtml YUAN W, YAN C, YU J, et al.Cell-center ADT algorithm based on ghost cell[J].Journal of Beijing University of Aeronautics and Astronautics, 2012, 38(10):1375-1379(in Chinese). http://bhxb.buaa.edu.cn/CN/abstract/abstract12427.shtml
[13]	刘鑫, 陆林生.重叠区域找重策略和插值方法的研究[J].计算机应用研究, 2006, 23(7):26-28. http://www.cnki.com.cn/Article/CJFDTOTAL-JSYJ200607006.htm LIU X, LU L S.Research on intersection strategies and interpoiation methods of overset zone[J].Application Research of Computers, 2006, 23(7):26-28(in Chinese). http://www.cnki.com.cn/Article/CJFDTOTAL-JSYJ200607006.htm
[14]	袁武. 新型重叠网格方法研究及其在复杂多体气动问题中的应用[D]. 北京: 北京航空航天大学, 2013: 36-49. YUAN W.Investigations on novel Chimera grid methods and its applications to complex multibody aerodynamic problems[D].Beijing:Beihang University, 2013:36-49(in Chinese).
[15]	GAO Z X, JIANG C W, LEE C H.Improvement and application of a wall function boundary condition for high-speed compressible flows[J].Science China Technological Science, 2013, 56 (10):2501-2515. doi: 10.1007/s11431-013-5349-4
[16]	GAO Z X, LEE C H.Numerical research on mixing characteristics of different injection schemes for supersonic transverse jet[J].Science China Technological Science, 2011, 54(4):883-893. doi: 10.1007/s11431-010-4277-9
[17]	XU J, CAI J S, LIU Q H, et al.Flow simulations by enhanced implicit-hole-cutting method on overset grids[J].Journal of Aircraft, 2014, 51(5):1401-1409. doi: 10.2514/1.C032283
[18]	WANG Z J.A Conservative overlapped (Chimera) grid algorithm for multiple moving body flows[C]//AIAA 34th Aerospace Sciences Meeting and Exhibit.Reston:AIAA, 1996.
[19]	CHIU I T, MEAKIN R L.On automating domain connectivity for overset grids:AIAA-1995-0854[R].Reston:AIAA, 1995.
[20]	WEY T C.Development of a mesh interface generator for overlapped structured grids:AIAA-1994-1924[R].Reston:AIAA, 1994.
[21]	CHO K W, KWON J H.Development of a fully systemized Chimera methodology for steady/unsteady problems[J].Journal of Aircraft, 1999, 36(6):973-980. doi: 10.2514/2.2538
[22]	LEE Y L, BAEDER J D.Implicit hole cutting-A new approach to overset grid connectivity:AIAA-2003-4128[R].Reston:AIAA, 2003.
[23]	MAPLE R C, BELK D M.A new approach to domain decomposition——The beggar code:in numerical grid generation in computational fluid dynamics and related fields[M].Landshut:Pine Ridge Press, 1994:305-314.
[24]	NIRSCHL H, DWYER H A, DENK V.A Chimera grid scheme for the calculation of particle flows:AIAA-1994-0519[R].Reston:AIAA, 1994.
[25]	WADA Y, LIOU M S.An accurate and robust flux splitting scheme for shock and contact discontinuities[J].SIAM Journal of Science Computer, 1997, 18(3):633-657. doi: 10.1137/S1064827595287626
[26]	VAN LEER B.Towards the ultimate conservative difference scheme Ⅴ:A second order sequel to Godunov's method[J].Journal of Computer Physics, 1979, 32(1):101-136. doi: 10.1016/0021-9991(79)90145-1
[27]	YOON S, JAMESON A.Lower-upper symmetric Gauss-Sediel method for the Euler and Navier-Stoker equations[J].AIAA Journal, 1988, 26(9):1025-1026. doi: 10.2514/3.10007
[28]	MENTER F R.Two-equation eddy-viscosity turbulence models for engineering applications[J].AIAA Journal, 1994, 32(8):1598-1605. doi: 10.2514/3.12149