基于虚网格的格心ADT搜索法

袁 武 阎 超 于 剑 杜若凡

(北京航空航天大学国家计算流体力学实验室，北京100191)

寻点方法是重叠网格［1－6］的关键技术之一，“寻点”是确定网格点在其他网格中的位置、查找网格贡献单元的统称.由于在重叠网格的生成过程中需要大量地进行“寻点”操作，因而准确与效率是寻点方法的关键.

常见的寻点方法有遍历法、Stencil Walk［7］、反变换(Inverse Map)［8］、ADT(Alternating Digital Tree)搜索［9－10］等.其中，ADT 搜索方法用笛卡儿坐标下的包围盒(min，max)对物体进行特征描述，由包围盒是否相交来判断物体的相交关系.由于包围盒相交关系的判断非常简单，因此，ADT方法效率很高，且特别适合对几何不规则目标进行搜索.

本文提出了一种直接在格心网格下操作、基于虚网格概念的ADT搜索方法，能有效提高寻点方法的效率和可靠性，并通过数值算例对新方法进行了验证.

1 本文方法

1.1 格心ADT搜索

目前，基于格心网格的有限体积法在CFD(Computational Fluid Dynamics)中应用广泛.在格心网格的寻点问题中，由于网格分区的关系，在分区边界上，格心网格单元跨越多个子区，单元顶点位于不同子区内，难以给出格心网格单元的唯一位置标识，格心网格单元在逻辑空间上不封闭，这给ADT树的建立带来不便.一种解决办法［11］是，仍然借用格点网格生成ADT树，然后找到P点的格点贡献单元，以该格点网格为顶点的格心网格必然比较靠近P点，再结合Stencil Walk方法，在附近找到真正的格心贡献单元，但Stencil Walk方法存在局部收敛性要求，若初始位置单元不合理，Stencil walk方法有可能收敛不到合理贡献……