基于虛網(wǎng)格的格心ADT搜索法

袁 武 閻 超 于 劍 杜若凡

(北京航空航天大學國家計算流體力學實驗室，北京100191)

尋點方法是重疊網(wǎng)格［1－6］的關鍵技術之一，“尋點”是確定網(wǎng)格點在其他網(wǎng)格中的位置、查找網(wǎng)格貢獻單元的統(tǒng)稱.由于在重疊網(wǎng)格的生成過程中需要大量地進行“尋點”操作，因而準確與效率是尋點方法的關鍵.

常見的尋點方法有遍歷法、Stencil Walk［7］、反變換(Inverse Map)［8］、ADT(Alternating Digital Tree)搜索［9－10］等.其中，ADT 搜索方法用笛卡兒坐標下的包圍盒(min，max)對物體進行特征描述，由包圍盒是否相交來判斷物體的相交關系.由于包圍盒相交關系的判斷非常簡單，因此，ADT方法效率很高，且特別適合對幾何不規(guī)則目標進行搜索.

本文提出了一種直接在格心網(wǎng)格下操作、基于虛網(wǎng)格概念的ADT搜索方法，能有效提高尋點方法的效率和可靠性，并通過數(shù)值算例對新方法進行了驗證.

1 本文方法

1.1 格心ADT搜索

目前，基于格心網(wǎng)格的有限體積法在CFD(Computational Fluid Dynamics)中應用廣泛.在格心網(wǎng)格的尋點問題中，由于網(wǎng)格分區(qū)的關系，在分區(qū)邊界上，格心網(wǎng)格單元跨越多個子區(qū)，單元頂點位于不同子區(qū)內(nèi)，難以給出格心網(wǎng)格單元的唯一位置標識，格心網(wǎng)格單元在邏輯空間上不封閉，這給ADT樹的建立帶來不便.一種解決辦法［11］是，仍然借用格點網(wǎng)格生成ADT樹，然后找到P點的格點貢獻單元，以該格點網(wǎng)格為頂點的格心網(wǎng)格必然比較靠近P點，再結合Stencil Walk方法，在附近找到真正的格心貢獻單元，但Stencil Walk方法存在局部收斂性要求，若初始位置單元不合理，Stencil walk方法有可能收斂不到合理貢獻……