李晓东， 屈崑， 蔡晋生

西北工业大学 航空学院， 西安 710072

分层嵌套重叠网格自适应树结构动态组装方法

李晓东， 屈崑*， 蔡晋生

西北工业大学 航空学院， 西安 710072

采用重叠网格可以有效地进行复杂流动的大规模数值模拟，特别是包含运动部件(如旋翼、投弹)的动态模拟。本文将树结构的自适应直角网格用于重叠网格组装过程中的切割和贡献单元的搜索，大大加快重叠网格的组装速度。通过二叉树自适应直角网格对物体外形进行离散，实现切割过程的快速定位；采用八叉树自适应直角网格对流场区域进行离散，高效地搜索贡献单元。使用基于壁面距离准则的重叠区域最小化方法和分层嵌套重叠策略，能提高重叠网格组装的效率和质量。对于具有运动部件的动态重叠网格问题，采用多个二/八叉树减少组装过程中信息更新的冗余计算，从而大幅度减少重叠网格组装的时间消耗。实际算例的重叠网格组装结果说明本文发展的重叠网格组装方法具有很高的计算效率,可以满足运动边界复杂流动问题的动态计算要求。

嵌套重叠网格； 二叉树； 八叉树； 自适应直角网格； 动态网格； 非定常流动； 计算流体力学

随着复杂流动问题研究的进一步发展，数值模拟对网格生成效率和质量提出了更高的要求，高质量网格是影响CFD计算的关键因素[1]。目前，许多图形界面化的商业软件采用多块对接技术能处理复杂几何形状的网格生成问题，但对复杂外形生成统一的结构化贴体网格仍是一项艰巨的工作。

采用重叠网格技术[2]，将流动区域分成若干相互重叠的子区域，对各不同区域可单独生成拓扑较简单的结构化网格。因此，重叠网格技术有效地降低了复杂外形网格的生成难度，大大拓展了结构化网格求解技术的应用范围。同时，由于在处理运动部件方面的优势，重叠网格技术在载荷分离、旋翼等[3-4]领域得到广泛应用。

重叠网格技术的关键在于重叠网格的组装，所谓组装，包含了切割(也被称为挖洞)和贡献单元搜索2个过程。在切割过程中，需要将与固体区域重叠的网格单元(格点计算方式是网格点)以及其他不必参与计算的网格单元标记出来。而在贡献单元搜索过程中，对于每个需要插值的网格单元，需要寻找一个包含它且能提供最佳插值模板的单元作为贡献单元，并计算出相对应的插值系数。然而重叠网格切割和贡献单元搜索都是费时的寻点过程。

国内外学者对重叠网格的组装方法进行了大量的研究。Chiu和Meakin[5]提出采用均匀笛卡儿网格的洞映射(Hole Map)方法提高了挖洞效率，但洞映射方法在识别缝隙处的物面时需要较大的内存。Meakin[6]提出了目标X射线法进行挖洞，该方法具有较好的鲁棒性。PEGASUS 5[7]将洞映射方法和视线法结合来提高挖洞的效率。Wang等[8]采用ADT树结构实现重叠网格组装的加速。Noack[9]采用二叉树方法的自适应直角网格加速了重叠网格的寻点。此外，为有效减小网格的重叠区域，提出了扩张收缩法[5]、割补法[10]等；同时，SUGGAR++[11]采用网格体积、壁面距离等标准进行了重叠区域最小化。在国内，袁武[12-13]、王文[14-15]、淮洋[16]等改进了洞映射方法和割补法，提高了洞映射法的分辨能力和重叠网格的组装质量。

Lee和Baeder[17]提出了一种重叠网格隐式切割方法，该方法采用统一的切割准则进行网格切割，简化了重叠网格“切割”的概念。Landmann和Montagnac[18]提出采用ADT技术和并行切割的方法加速隐式切割进程。刘秋洪等[19-20]提出了多层嵌套重叠隐式切割方法，将重叠网格组装分为嵌套切割和重叠切割2个过程，简化了贡献单元选择的复杂度。

尽管重叠网格的应用在一定程度上减轻了结构化网格生成的难度，然而对于工程中的复杂形状建立重叠网格仍然不是一项容易的任务。在实际的工程应用中，组装过程需要较多的人工干预，并且重叠网格生成往往需要反复的迭代修改才能完成。尤其对于多体运动这类动边界问题，缓慢的组装速度成为重叠网格在工业中应用的瓶颈。因而研究高效、自动的重叠网格组装方法[21]是提高重叠网格应用能力的关键途径。

由于自适应树结构具有访问速度快、方便数据查询的特点，所以本文采用二叉树自适应直角网格进行切割，采用八叉树自适应直角网格进行贡献单元搜索，采用壁面距离准则实现重叠区域最小化和分层嵌套重叠策略，采用多个二/八叉树处理动态问题。基于以上方法，本文发展了一种适用于动态问题的快速重叠网格组装方法。

1 重叠网格区域切割方法

由于二叉树的数据结构具有高效的寻址能力，因此在二叉树直角网格中给定坐标点能够快速确定包围该点的二叉树叶子节点。同时二叉树的各向异性自适应特点特别适合对几何形状的近似解析。因此将其应用于物体表面的近似解析和重叠网格切割时的寻点操作是非常适合的。

在下文中，对用于切割的二叉树自适应直角网格简称为网格切割二叉树；该直角网格中的每个单元对应着二叉树的一个节点，简称为节点；根据节点之间的关系，有父节点、子节点以及同属一个父节点的2个兄弟节点；二叉树的叶子节点简称为叶子节点。

1.1 网格切割二叉树构造

在切割阶段，首先构造二叉树根节点覆盖原始计算网格区域，此时根节点包含了所有的壁面单元。通过比较节点网格尺度与所包含的壁面单元的包围盒尺度，判断是否要对该节点作二分加密和确定二分方向。这样不断加密，直到每个二叉树叶子节点的尺度不大于其所包含的壁面单元尺度，或者叶子节点的尺度已经达到预先指定的下限，亦或者树的深度达到预设的上限。这样就完成了网格切割二叉树的构造，此时每个叶子节点都维护了一个与其有相交关系的壁面单元列表。遍历每个叶子节点，只要它包含了壁面单元，则该叶子节点被标记为WALL节点。当所有WALL节点被标记后，即可采用淹没填充法分别将固体区域和流场区域的叶子节点标记为SOLID和FLOW。

图1给出了二维三段翼30P30N的网格切割二叉树，其中每个矩形区域代表二叉树的一个叶子节点。图1(a)中给出了计算域内的叶子节点(NODE_IN)和固体内叶子节点(NODE_OUT)；图1(b)给出了壁面叶子节点(NODE_BND)。从图中可以看出在壁面处，网格切割二叉树具有较高的分辨率；而在离开壁面区域之后，会采用较粗的树节点对区域进行离散，体现了网格切割二叉树具有较强的适应能力。

1.2 重叠区域二叉树切割

但是仅对二叉树叶子节点标记FLOW、WALL和SOLID可能造成切割错误。如图2所示，图中给出了物体A的网格(蓝色网格线)及其二叉树的壁面叶子节点(红色矩形)。图中绿色网格线是另一物体的网格，其网格点P位于物体A的壁面叶子节点中，所以点P应该被标记为OUT。由于采用包围盒对固体壁面进行近似解析处理，造成物体A的网格点Q也位于其壁面叶子节点中，但是对点Q进行切割显然是错误的。为了解决这个问题，WALL和SOLID叶子节点还必需记录该节点所属的物体。只有当某一物体的网格点落在属于其他物体的SOLID或者WALL叶子节点中时，才能被切割。

本文采用位域变量BBA(Bytes of Body Association)来处理这种问题。首先对于每个固体壁面边界进行编号i=1,2,…,Nw。对于每个叶子节点，使用一个至少Nw位的BBA来标识它与每个壁面边界的面元是否相交。而每个物体也使用这样一个BBA变量来表示该物体的表面由哪些壁面边界组成。要检查一个叶子节点是否与另一个物体相交，只需要检查两者的BBA位域变量进行按位与操作的结果是否为0即可。如果不为0，说明两者属于同一个物体，不应进行网格切割。

由于二叉树的搜索速度仅与其树深度成正比，所以可以快速地判断网格点与固体区域的关系。根据叶子节点的标记，将位于FLOW叶子节点的网格点标记为IN，而位于WALL和SOLID叶子节点中的网格点标记为OUT。然后进一步完成网格单元的标记，将包含OUT网格点的网格单元标记为OUT，其余的单元标为IN，这样便完成了重叠区域网格切割。

2 贡献单元搜索

当网格单元被分类为IN和OUT之后，需要将IN类的网格单元中的插值单元标记为FRINGE。沿着预先定义的重叠边界和切割确定的洞边界，直接将边界内两层单元(因为采用二阶格式计算)标记为FRINGE，即可确定所有插值单元。

在贡献单元搜索阶段，面对的问题是任意给定物体A中一个插值单元的中心点p，找到另外一个物体上包含点p的网格单元D。本文采用最速下降搜索，但是这种方法要求初始单元需接近单元D。所以本文采取等边八叉树自适应直角网格辅助确定初始单元，以下简称八叉树。

首先构造一个比整个计算网格包围盒稍大的立方体(二维情况下是正方形)作为八叉树的根节点。然后根据其所包含的网格单元尺度不断将节点八分加密，形成新的叶子节点。对于每个叶子节点，记录其所覆盖的网格单元的编号。当叶子节点的尺度小于其覆盖的网格单元尺度，或者节点尺度达到下限，或者包含的网格单元个数达到下限，或者树的深度达到上限，则停止对该节点加密。此时每个叶子节点包含了一组网格单元编号。在这些单元中，对每个网格块只保留一个作为初始单元。但是考虑到如图3所示的情况，一个八叉树节点(用实线矩形表示)跨越了一个薄物体(如翼型后缘)的固体区域。对于这样的节点，它覆盖区域内的所有壁面边界单元都需要被保留作为搜索初始单元。这样就构造了叶子节点的搜索初始单元列表。完成所有叶子节点的处理后，八叉树构造完成。

当八叉树构造完毕后，便可进行包含单元搜索。在给定物体A的网格中，任意插值单元中心点为p，在八叉树中能够快速找到p所在的叶子节点N。选择搜索初始单元列表中所有的初始单元，进行最速下降搜索[22]。通过以上搜索可得到一组非OUT且非FRINGE的包含单元，采用物面距离作为贡献单元的评价标准，在所有的包含单元中选择物面距离最小者做贡献单元。

3 重叠区域最小化方法

前文已经指出，切割边界内两层单元被标记为FRINGE。但是这样做可能导致重叠区域过大，浪费计算资源，而且影响后处理效果。因此需要调整重叠边界以有效地缩小重叠区域。

重叠区域进行最小化的一个准则是被插值单元和贡献单元的壁面距离应该尽量接近。例如在图4中，两个圆柱网格相互重叠，图4(a)为未进行重叠区域最小化时的网格组装情况，具有较大的重叠区域。显然在圆柱网格A的壁面附近，网格A中的贡献单元的壁面距离要比圆柱网格B中作为插值单元的壁面距离值明显偏小；反之，在圆柱网格B的壁面附近，网格B中的贡献单元的壁面距离要比圆柱网格A中的插值单元的壁面距离偏小。但是在两个圆柱的中间位置附近，网格A和网格B的单元各自的壁面距离是接近的。因此两圆柱网格的重叠边界应在此位置附近。

在调整重叠区域时，从洞边界开始在插值区域中做阵面推进，以格心方式进行说明。首先引入一个概念，伪固体(PSOLID)单元，是重叠区域最小化过程中对要进行最小化的单元的一种标记形式，最终被标记的单元在经过重叠区域最小化之后将被设置为OUT。具体来说，如果一个单元的壁面距离比贡献单元的壁面距离大，并且贡献单元插值模版中不包含PSOLID单元，则将这个插值单元标记为PSOLID单元。如果推进到某单元的贡献单元插值模版中包含PSOLID单元的情况，说明在该处两个重叠边界发生接触，不应该继续缩小重叠区域，并且该单元也不能作为插值单元，不进行PSOLID单元标记。此时可以根据所有的PSOLID单元确定出最小重叠区域以及重叠边界，即将与计算单元邻近的两层PSOLID网格单元标记为插值单元，并将剩余的PSOLID单元设置为OUT，即可完成重叠区域最小化。最后可以得到图4(b)的结果。

4 分层嵌套重叠策略

对于复杂外形物体进行重叠网格组装时，多网格重叠的情况会导致贡献单元选择变得复杂。因此本文采用嵌套重叠网格[19,23]的思想，将各部件的网格分为不同的层次，按照网格间的层次关系进行组装，从而简化组装过程，提高贡献单元搜索效率和网格组装质量。

4.1 分层嵌套策略

图5给出了重叠网格的分层嵌套策略图。在划分网格时将较密的第n层网格嵌套在较粗的n-1 层网格内部，将n-1层中被第n层覆盖的网格区域进行切割。而当同层的网格出现相互切割时，需要根据单元壁面距离选择距离较小者做计算单元。采用这种分层嵌套策略，可以按照部件的从属关系进行分层嵌套或同层重叠，降低对复杂外形网格的生成难度，简化不同层之间贡献单元的搜索，可生成高质量的结构化贴体重叠网格。

重叠网格分层嵌套策略中采用了簇和层2个物理概念。簇(Cluster)是包含一个部件或物体的所有网格块，由一个或者多个具有对接(Match)边界的网格块组成，不同的网格簇之间可相互重叠(Overlap)。图6中的两个圆柱网格簇分别由4个网格块(Block)组成，两个网格簇之间相互重叠。层(Layer)由一个或几个相互重叠的网格簇组成，不同的网格层之间可以相互嵌套(Embed)，图7为2个背景网格层和一个NACA4412翼型网格层之间的相互嵌套关系。

4.2 分层嵌套重叠策略的统一实现

本文提出采用基于壁面距离的切割准则将不同层间的嵌套切割和同层间的重叠切割2个过程统一于一个重叠网格切割过程，从而将嵌套重叠的概念用于重叠网格的切割中。整个过程遵循的基本原则是在网格发生重叠或嵌套时，将壁面距离小的网格单元用作计算单元，而壁面距离大的网格单元被切割。

具体来说，根据网格簇的概念对带有物面的网格直接进行壁面距离的计算；对于没有壁面的背景网格，给定一个固定的壁面距离值。当存在多个背景网格时，根据背景网格位于的层数给定背景网格壁面距离值，较大的壁面距离值表示较低的网格层。这样通过壁面距离大小的比较就可以快速地将被高层网格区域覆盖的低层网格设置为OUT，实现分层嵌套切割的效果。同时由于采用壁面距离实现了同层重叠区域的最小化，因而实现了重叠切割。因此，通过采用壁面距离准则，可以将同层的重叠切割和不同层的嵌套切割统一地在一个切割过程中实现，简化了重叠网格的切割过程。

5 运动部件的处理

在这里只考虑刚体运动的情况。每次物体位置和姿态变化后，都需要重新进行切割和搜索贡献单元，还需要最小化重叠区域。尽管基于树结构的切割与搜索速度很快，但是如果每次重新生成用于切割和贡献单元搜索的二叉树和八叉树，必然导致效率不佳。因此，根据运动规律的不同将所有物体分为若干动态组，而所有静态物体被纳入唯一的静态组。各组分别构造独立的二叉树和八叉树。当物体运动时，并不对物体的网格以及二/八叉树的坐标进行变换，即各个动态分组仍然用各自原有的局部坐标系，但要记录下各动态组6个自由度的位移。在更新切割信息时，要重复将被切割的坐标点变换到切割物体所在的局部坐标内。对于同一组内的切割，由于相对位置不变，只需进行一次切割，后续不再改变。

对于贡献单元的搜索，也采取上述方式处理。这样二叉树和八叉树不必重新构造，节省了大量的计算时间。

6 分层嵌套重叠网格静/动态组装算例

依据以上提出的重叠网格组装方法开发了一套重叠网格组装程序，采用二维三段翼30P30N算例[24]和ADEC三维投弹算例[25]分别验证该方法的静态和动态网格组装能力。

6.1 二维三段翼30P30N算例

本文采用二维三段翼30P30N来验证重叠网格静态组装的可靠性。依据其几何外形的结构关系，划分各部件不同层次的流场区域网格，采用由6个簇组成的4个网格层进行重叠网格组装。第4层(最高层)为翼型网格，其中包含三段翼前缘缝翼、主翼和后缘襟翼3个网格簇，对每个网格簇分别生成正交的结构化网格；其余3层均为直角背景网格，第3层为翼型附近流场的网格，第2层为保证背景网格之间良好过度而采用的一层网格，第1层为包含远场边界的背景网格。

在三段翼30P30N中，缝翼与主翼以及主翼与襟翼之间的复杂流动是整个数值模拟的关键，因此对这个区域的网格进行了加密。网格组装结果如图8所示，其中图8(a)为三层背景网格的嵌套切割结果，图8(b)为前缘缝翼、主翼和后缘襟翼网格重叠切割结果。图9和图10分别给出了前缘缝翼、后缘襟翼与主翼缝隙处重叠网格的切割结果。重叠组装后的网格中无网格孤岛，说明了本文发展的重叠网格静态组装算法可靠。

6.2 ADEC三维投弹算例

为了进一步验证本文算法对动态重叠网格的组装能力，选取ADEC三维投弹算例进行验证。为了便于检查动态网格组装结果，本文并没有进行CFD计算，而是通过python脚本向组装程序发送位移数据。考虑到投弹过程主要发生在竖直方向上，因此以导弹竖直下落过程来测试重叠网格的动态组装。图11给出了机翼-挂架和导弹的物面网格。该算例中机翼的网格量约为365万，导弹的网格量约为241万。图12给出了该算例的网格切割二叉树的壁面叶子节点，从图中可以看出采用网格切割二叉树能有效地分辨出算例中挂架和导弹间的狭小缝隙。

该算例在一台E5-2660处理器，内存64 G，主频为2.60 GHz的工作站上运行，并采用单线程方式组装网格。每步更新切割和贡献单元搜索，只输出组装信息文件，以节省磁盘操作时间。

图13给出了初始时刻投弹模型网格组装结果，图中蓝色网格表示导弹的计算网格单元，红色网格是机翼的计算网格单元。图13(a)是xOy视图上位于挂架中心处的一个切面，从图中可以看出对两者之间缝隙处的网格进行了良好的组装；图13(b)给出了yOz方向上机翼和导弹之间缝隙处网格组装的详细结果，从图中可以看出两者之间的缝隙处有足够多的网格单元，可以保证插值的精度，能有效地计算缝隙中的复杂流动。

图14为运动过程中4个不同时刻的网格组装结果，图中给出的是yOz和xOy方向上的切面, dt表示时间步长。从下落过程的组装结果可以看出，在初始时刻机翼和导弹相距较近，两者的网格经过重叠最小化之后缝隙处距离壁面较近的网格都会被切割；随着导弹远离挂架之后，导弹附近的网格都会被保留，这样组装的网格可以保证导弹周围流场的精确计算。

按照是否进行重叠区域最小化操作分别进行时间统计，如表1所示。整个网格组装过程总共30个时间步，在不进行重叠最小化操作时，总共耗时437 s，平均每步用时约14.6 s；进行重叠区域最小化操作的总共耗时为1 168 s，平均每步用时约39 s。其中，由于在初始时间步上会对网格数据进行初始化和计算网格单元的壁面距离，所以初始时刻网格组装的用时相对较多，当导弹离开挂架一定的距离后，每步网格组装时间会显著下降。

Table 1 Time consumption of assembling overset grids for moving bodies

TypeofassemblingmethodTimeconsumption/sTotalAverageThefirststepWithoutoverlappingminimization43714.621.6Withoverlappingminimization116839108

另一方面，虽然采用重叠区域最小化会一定程度增加网格组装的时间，但提高了网格的组装质量。从网格量、时间消耗和网格组装质量上来看，两种方式的动态重叠网格组装效率均可以满足运动物体非定常计算的要求。

7 结 论

本文采用二/八树结构的自适应直角网格方法，发展了一种动态重叠网格快速组装方法，该方法只需要初始的组装网格和网格边界条件，无需人工干预便可自动实现网格组装。

1) 通过采用二/八树结构的自适应直角网格方法，提高了切割的效率并节约内存空间，实现了高效搜索和定位贡献单元。提出的重叠区域最小化方法显著减小了网格重叠区域，提高了网格组装质量，有利于提高流动计算的效率。

2) 采用壁面距离准则的分层嵌套重叠切割策略，在一个过程中同时实现重叠切割和嵌套切割功能，简化了贡献单元的搜索，提高了复杂外形网格切割效率和网格组装质量。

3) 对不同运动部件分别采用随部件一起运动的独立的二/八叉树结构，能够有效地降低计算冗余，加快动态重叠网格的组装速度。

4) 算例说明本文提出的重叠网格组装方法快速高效，提升了网格组装效率，可解决带有运动边界的非定常流动数值模拟过程中的动网格生成问题。

[1] LEVY D W, LAFLIN K R, TINOCO E N, et al. Summary of data from the fifth computational fluid dynamics drag prediction workshop[J]. Journal of Aircraft， 2014, 51(4): 1194-1213.

[2] BENEK J A, STEGER J L, DOUGHERTY F C. A flexible grid embedding technique with application to the Euler equations：AIAA-1983-1944[R]. Reston: AIAA, 1983.

[3] NOACK R W, SLOTNICK J P. A summary of the 2004 overset symposium on composite grids and solution technology：AIAA-2005-0921[R]. Reston: AIAA, 2005.

[4] CHAN W M. Overset grid technology development at NASA Ames Research Center[J]. Computers & Fluids， 2009, 38(3): 496-503.

[5] CHIU I T, MEAKIN R L. On automating domain connectivity for overset grids：AIAA-1995-0854[R]. Reston: AIAA, 1995.

[6] MEAKIN R L. Object X-rays for cutting holes in composite overset structured grids：AIAA-2001-2537[R]. Reston: AIAA, 2001.

[7] ROGERS S E, SUHS N E, DIETZ W E. PEGASUS 5: An automated preprocessor for overset-grid computational fluid dynamics[J]. AIAA Journal， 2003, 41(6): 1037-1045.

[8] WANG Z J, PARTHASARATHY V, HARIHARAN N. A fully automated Chimera methodology for multiple moving body problems：AIAA-1998-0217[R]. Reston: AIAA, 1998.

[9] NOACK R W. SUGGAR: A general capability for moving body overset grid assembly：AIAA-2005-5117[R]. Reston: AIAA, 2005.

[10] CHO K W, KWON J H, LEE S. Development of a fully systemized chimera methodology for steady/unsteady problems[J]. Journal of Aircraft， 1999, 36(6): 973-980.

[11] NOACK R W, BOGER D A, KUNZ R F, et al. Suggar++: An improved general overset grid assembly capability：AIAA-2009-3992[R]. Reston: AIAA, 2009.

[12] 袁武， 阎超， 席柯. 洞映射方法的研究和改进[J]. 北京航空航天大学学报, 2012, 38(4): 563-568. YUAN W， YAN C， XI K. Investigation and enhancement of hole mapping method[J]. Journal of Beijing University of Aeronautics and Astronautics, 2012, 38(4): 563-568 (in Chinese).

[13] 袁武， 阎超， 杨威. 割补法的改进和应用[J]. 空气动力学学报, 2013, 31(6): 704-709. YUAN W， YAN C， YANG W. Enhancement and application of cut-paste algorithm[J]. Acta Aerodynamica Sinica, 2013, 31(6): 704-709 (in Chinese).

[14] 王文， 阎超， 袁武， 等. 新型重叠网格洞面优化方法及其应用[J]. 航空学报, 2016, 27(3): 826-835. WANG W， YAN C， YUAN W， et al. A new kind of overlap optimization algorithm and its applica-tions[J]. Acta Aeronautica et Astronautica Sinica, 2016, 27(3): 826-835 (in Chinese).

[15] 王文， 阎超， 袁武， 等. 鲁棒的结构网格自动化重叠方法[J]. 航空学报, 2016， 37(10): 2980-2991. WANG W， YAN C， YUAN W， et al. A robust and automatic structured overlapping grid approach[J]. Acta Aeronautica et Astronautica Sinica, 2016， 37(10): 2980-2991 (in Chinese).

[16] 淮洋， 郝海兵， 姚冰， 等. 一种改进型洞映射法[J]. 航空计算技术, 2015, 45(2): 31-34. HUAI Y， HAO H B， YAO B， et al. An improved method of hole-map[J]. Aeronautical Computing Technique, 2015, 45(2): 31-34 (in Chinese).

[17] LEE Y, BAEDER J D. Implicit hole cutting-A new approach to overset grid connectivity: AIAA-2003-4128[R]. Reston: AIAA, 2003.

[18] LANDMANN B, MONTAGNAC M. A highly automated parallel Chimera method for overset grids based on the implicit hole cutting technique[J]. International Journal for Numerical Methods in Fluids, 2011, 66(6): 778-804.

[19] 刘秋洪， 屈崑， 蔡晋生， 等. 嵌套重叠网格的构造策略及其隐式切割[J]. 中国科学: 物理学 力学 天文学, 2013, 42(2): 186-198. LIU Q H， QU K， CAI J S， et al. An automated Chimera method based on a hierarchical overset grid strategy and the implicit hole cutting technique[J]. SCIENTIA SINICA Physica, Mechanica & Astronomica, 2013, 42(2): 186-198 (in Chinese).

[20] 徐嘉， 刘秋洪， 蔡晋生， 等. 基于隐式嵌套重叠网格技术的阻力预测[J]. 航空学报, 2013, 34(2): 208-217. XU J， LIU Q H， CAI J S， et al. Drag prediciton based on overset grids with implict hole cutting technique[J]. Acta Aeronautica et Astronautica Sinica, 2013, 34(2): 208-217 (in Chinese).

[21] DRUYOR JR C T, JONES W T, KARMAN JR S L. A survey of overset domain assembly methods: AIAA-2015-0910[R]. Reston: AIAA, 2015.

[22] DIETZ W E, JACOCKS J L, FOX J H. Application of domain decomposition to the analysis of complex aerodynamic configurations[C]//3rd International Symposium on Domain Decomposition Methods for Partial Differential Equations. Houston, Texas: SIAM, 1989: 428-450.

[23] CAI J, TSAI H M, LIU F. A parallel viscous flow solver on multi-block overset grids[J]. Computers & Fluids, 2006, 35(10): 1290-1301.

[24] CHIN V D, PETERS D W, SPAID F W, et al. Flowfield measurements about a multi-element airfoil at high Reynolds numbers: AIAA-1993-3137[R]. Reston: AIAA, 1993.

[25] HEIM E R. CFD wing/pylon/finned store mutual interference wind tunnel experiment:ADB152669[R]. Arnold: Arnold Engineering Development Center, 1991.

(责任编辑：李明敏)

＊Corresponding author. E-mail: kunqu@nwpu.edu.cn

A dynamic assembling method based on adaptive tree structure for hierarchical overset grids

LI Xiaodong, QU Kun*, CAI Jinsheng

SchoolofAeronautics,NorthwesternPolytechnicalUniversity,Xi’an710072,China

The overset or chimera grid is an effective method for large-scale numerical simulation of aerodynamic problems with complex geometry, especially those with bodies in relative motion (such as the rotorcraft, store/aircraft separation). The method of adaptive cartesian grids based on the tree structure is applied to perform fast hole cutting and donor searching in the overset grid assembly process. In this technique, the geometry is represented by adaptive cartesian grids of binary trees, and this can achieve quick locating in the hole cutting. Adaptive cartesian grids of octrees are used to decompose the flow field, making the donor searching efficient. By means of a minimal overlapping-domain approach and a hierarchical strategy for overset grids, which both employ the rule of wall distance, the efficiency and quality of overset grid assembly are improved. For dynamic problems of moving bodies, multiple binary trees and octrees are applied to decrease the redundant work of updating data in procedures of overset grid assembly, substantially reducing the time consumption. The test cases demonstrate that the technique in this paper is computationally efficient and can be successfully employed to problems of multiple moving bodies.

overset grid; binary trees; octrees; adaptive cartesian grid; dynamic grid; unsteady flow; computational fluid dynamics

2016-03-21； Revised：2016-04-12； Accepted：2016-04-27； Published online：2016-05-04 14:16

URL：www.cnki.net/kcms/detail/11.1929.V.20160504.1416.010.html

National Basic Research Program of China

http://hkxb.buaa.edu.cn hkxb@buaa.edu.cn

10.7527/S1000-6893.2016.0135

2016-03-21； 退修日期：2016-04-12； 录用日期：2016-04-27； 网络出版时间：2016-05-04 14:16

www.cnki.net/kcms/detail/11.1929.V.20160504.1416.010.html

国家“973”计划

＊通讯作者.E-mail: kunqu@nwpu.edu.cn

李晓东， 屈崑， 蔡晋生． 分层嵌套重叠网格自适应树结构动态组装方法[J]． 航空学报, 2017, 38(3): 120243. LI X D, QU K, CAI J S. A dynamic assembling method based on adaptive tree structure for hierarchical overset grids[J]. Acta Aeronautica et Astronautica Sinica, 2017, 38(3): 120243.

V211.3

A

1000-6893(2017)03-120243-10