分層嵌套重疊網格自適應樹結構動態組裝方法

李曉東， 屈崑， 蔡晉生

西北工業大學 航空學院， 西安 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