留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

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

李鹏 高振勋 蒋崇文 李椿萱

李鹏, 高振勋, 蒋崇文, 等 . 重叠网格装配中的一种改进ADT搜索方法[J]. 北京航空航天大学学报, 2017, 43(6): 1182-1190. doi: 10.13700/j.bh.1001-5965.2016.0425
引用本文: 李鹏, 高振勋, 蒋崇文, 等 . 重叠网格装配中的一种改进ADT搜索方法[J]. 北京航空航天大学学报, 2017, 43(6): 1182-1190. doi: 10.13700/j.bh.1001-5965.2016.0425
LI Peng, GAO Zhenxun, JIANG Chongwen, et al. Improved ADT searching method in overlapping grid assembly[J]. Journal of Beijing University of Aeronautics and Astronautics, 2017, 43(6): 1182-1190. doi: 10.13700/j.bh.1001-5965.2016.0425(in Chinese)
Citation: LI Peng, GAO Zhenxun, JIANG Chongwen, et al. Improved ADT searching method in overlapping grid assembly[J]. Journal of Beijing University of Aeronautics and Astronautics, 2017, 43(6): 1182-1190. doi: 10.13700/j.bh.1001-5965.2016.0425(in Chinese)

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

doi: 10.13700/j.bh.1001-5965.2016.0425
基金项目: 

航空科学基金 20141251015

详细信息
    作者简介:

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

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

    通讯作者:

    高振勋, E-mail:gaozhenxun@buaa.edu.cn

  • 中图分类号: V211.3;TP311.1

Improved ADT searching method in overlapping grid assembly

Funds: 

Aeronautical Science Foundation of China 20141251015

More Information
  • 摘要:

    针对现有交替数字二叉树(ADT)方法的不足,引入辅助笛卡儿网格提出了一种基于散列数据结构的改进搜索方法以缓解可能出现堆栈溢出的问题和提高重叠网格装配的效率。该方法以散列数据结构的方式对网格单元进行存储和搜索,首先以辅助笛卡儿网格对网格单元的存储空间进行初步映像,然后基于ADT搜索树作进一步检索。在ADT搜索方法的基础上,笛卡儿网格的引入进一步缩小了网格单元的搜索范围使得改进方法具有更好的效率。基于单个网格节点,查询深度和搜索耗时的测试显示改进方法相比现有ADT搜索方法能使挖洞的平均效率提高25%以上。此外,挖洞结果和基于网格装配的数值计算验证了改进搜索方法在重叠网格装配中的可靠性。

     

  • 图 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方法
    N1 2 884 1 120 0.312 5 0.125 0 60.00
    N2 8 492 4 630 0.937 5 0.625 0 33.33
    N3 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方法
    N1 23 818 19 516 8.125 6.562 5 19.23
    N2 46 971 22 440 15.938 7.187 5 54.90
    N3 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 全部挖洞耗时减少比例/%
    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 全部挖洞耗时减少比例/%
    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
  • [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
  • 加载中
图(14) / 表(4)
计量
  • 文章访问数:  414
  • HTML全文浏览量:  0
  • PDF下载量:  448
  • 被引次数: 0
出版历程
  • 收稿日期:  2016-05-20
  • 录用日期:  2016-08-25
  • 刊出日期:  2017-06-20

目录

    /

    返回文章
    返回
    常见问答