一種快速查找空間網格到壁面單元最短距離的方法
2023-05-24 04:43:56 1
一種快速查找空間網格到壁面單元最短距離的方法
【專利摘要】本發明公開了一種快速查找空間網格到壁面單元最短距離的方法，包括以下步驟：（1）提取待計算的網格的幾何信息；（2）計算與壁面單元相鄰的體單元的壁面距離值，並將與壁面單元相鄰的體單元加入待更新的網格隊列Q中；（3）若隊列Q非空，則根據連續性，更新隊列元素的相鄰體單元的壁面距離信息；（4）若隊列Q為空，則查找結束，輸出所有網格單元的壁面距離數據。
【專利說明】一種快速查找空間網格到壁面單元最短距離的方法
【技術領域】
[0001]本發明涉及一種計算機輔助工程(CAE)、計算流體力學(CFD)及數值仿真軟體技術，具體涉及一種快速查找空間網格與壁面單元之間最短距離的方法。
【背景技術】
[0002]隨著計算機硬體技術和數值分析技術的快速發展，包括計算流體力學(ComputationalFluidDynamics, CFD)軟體在內的計算機輔助工程軟體及數值仿真技術正越來越廣泛地應用於各種工程【技術領域】中，成為重要的產品研發與技術創新平臺。例如，航空飛行器空氣動力學設計、汽車熱舒適性與結構動力學設計、發動機熱力學與動力學設計、船舶水動力學設計等，都離不開大量基於CFD軟體的仿真計算與數值優化工作。
[0003]就CFD數值仿真分析來說，我們通常需要將研究對象所在的連續物理空間以網格的形式，剖分成離散空間。CFD軟體就是以離散的網格系統為基礎進行數值迭代和物理分析的。目前廣泛使用的網格可以分為兩大類:多塊結構化網格(mult1-block structuredmesh)和非結構網格(unstructured mesh)。由於絕大多數工程流體動力學問題都是瑞流問題，因此湍流模型及相關算法一直是CFD軟體的核心技術之一。在湍流模型中，計算離散的空間網格單元(或網格節點)到壁面網格單元的最短距離值(以下簡稱「壁面距離」)是關鍵內容之一。通常壁面網格單元總數是以萬計、十萬計甚至百萬計的。因此，計算空間某網格單元(或網格節點)的最短壁面距離的技術核心是，如何從數以萬計、十萬計甚至百萬計的單元中準確、快速地尋找到某一個的壁面單元，其到指定空間網格的距離是所有壁面單元中最短的。壁面距離的計算速度直接影響到CFD軟體的運行效率和用戶體驗感；壁面距離值的準確性，則直接影響到湍流模型方程的有效性和CFD軟體的準確性(特別是在複雜工程湍流問題的數值模擬計算中)。
[0004]目前在CFD領域中計算壁面距離的方法主要有兩大類:
[0005]一種方案是「遍歷查找」，即:針對每一個空間網格單元(或節點)，都對所有壁面單元進行一次遍歷搜索，計算二者之間的距離值；並將其中的最短距離作為該空間網格節點的壁面距離值。這種方法構造簡單，但當網格規模(如網格單元總數或節點總數)較大時，「遍歷查找」的耗時將非常長。在「遍歷查找」過程中，可以引入一些優化算法(如「最速下降」/梯度法等)，但無法從根本上避免對大量無效壁面單元的搜索和比較。此外，為了縮短壁面距離的計算時間，還可以充分利用並行集群的並行計算策略:根據並行計算的CPU核數，將整套網格分割成多塊，並將計算任務分發至各CPU核(Core);每核CPU僅需計算分發至本核的某(幾)塊網格的壁面距離；在每核CPU內，仍採用「遍歷查找」方式計算本核任務內的網格單元(或節點)與所有壁面單元之間的最短距離值。實測結果標模，採用並行處理策略，可以在一定程度上緩解「遍歷查找」壁面距離時間過長的問題，但仍不是根本之策。
[0006]一種方案是採用局部「遍歷查找」與部分區域賦近似值相結合的方式，定義計算區域內每一個網格單元(或節點)的壁面距離值。根據CFD數值仿真的特點，在遠離固壁面的計算域中，以壁面距離的函數形式存在的湍流源項作用逐步減弱、甚至可以忽略。因此，就遠離固壁面的網格單元(或節點)來說，可以將其壁面距離賦以某個近似值，而不必精確查找；而在其他區域，仍採用上述「遍歷查找」方法，從而兼顧計算時間和計算效率。這一類方法的主要問題在於:如何人為界定所謂的「遠離壁面」的範圍值。若分界面靠近固壁區域，則給分界面以外區域定義不準確的壁面距離值後，將導致湍流源項誤差過大，從而嚴重汙染整個數值計算結果；若分界面非常靠近計算域外邊界(非固壁面)，則「遍歷查找」區與計算域接近，計算量和查找時間與方案一沒有本質區別(同一量級)。
[0007]在現有技術中，「遍歷查找」方法最根本的問題在於因排除大量無效壁面單元而產生的計算時間。以一套空間單元總數為1400萬、壁面單元總數為15萬的網格為例，在
3.4GHz主頻的CPU上計算大約需要20小時(單機單線程);在並行集群上採用32核CPU計算大約需要2小時；採用256核CPU計算大約需要800秒。而局部「遍歷查找」與部分區域賦近似值相結合的方法的缺陷是近似壁面距離值將汙染整個CFD計算結果。精確查找區與近似值區之間的分界面約靠近固壁、所模擬的物理問題(湍流問題)越複雜，則汙染越嚴重，甚至導致整個計算結果完全不可信。
【發明內容】
[0008]發明目的:本發明所要解決的技術問題是針對現有技術的不足，提供一種快速查找空間網格到壁面單元最短距離的方法。
[0009]為了解決上述技術問題，本發明公開了一種快速查找空間網格到壁面單元最短距離的方法，包括以下步驟:
[0010](I)提取待計算的網格的幾何信息；
[0011](2)計算與壁面單元相鄰的體單元的壁面距離值，並將與壁面單元相鄰的體單元加入待更新的網格隊列Q中；
[0012](3)若隊列Q非空，則根據連續性，更新隊列元素的相鄰體單元的壁面距離信息；
[0013](4)若隊列Q為空，則查找結束，輸出所有網格單元的壁面距離數據。
[0014]本發明步驟(I)中，設置兩個列表存放網格的幾何信息:體單元隊列ListV和壁面單元隊列ListW ；
[0015]其中體單元隊列ListV包括:體單元編號，體單元中心坐標，與該體單元相鄰的各體單元編號，對每個體單元，記錄與該體單元最近的壁面距離編號及壁面距離值d ；
[0016]壁面單元隊列ListW包括:壁面單元編號，壁面單元中心坐標，所屬體單元編號。
[0017]本發明步驟(2)中，遍歷壁面單元列表ListW,對遍歷到的壁面單元Ew,計算壁面單元Ew的壁面單元中心與其所屬的體單元Ev的體單元中心的距離d，該距離值就是體單元Ev的壁面距離；將體單元隊列ListV中體單元Ev的對應壁面單元和壁面距離值分別置為壁面單元Ew和壁面距離d ;同時，將體單元Ev加入待更新隊列Q中。
[0018]本發明步驟(3)中，包括以下步驟:
[0019](a)將待更新隊列Q拷貝至新的隊列R，並清空待更新隊列Q ;
[0020](b)遍歷隊列R,對遍歷到的體單元Ev,處理與體單元Ev相鄰的各體單元Εν』，處理方法為步驟(c);
[0021](C)判斷體單元Εν』的體單元中心到與體單元Ev對應的壁面單元Ew的距離d』是否比體單元Εν』的原壁面距離d更小；若更小，則將體單元Εν』對應的壁面單元和壁面距離值分別置為壁面單元Ew和壁面距離d』，並將體單元Εν』加入待更新隊列Q。
[0022] 申請人:發現，構建快速、精確查找計算壁面距離方法的核心問題在於，儘量避免對大量無效壁面單元的搜索和比對。在本申請中，充分利用「連續的物理空間中壁面距離是一個連續函數」這一基本規律，從近壁第一層網格出發，逐層計算並更新相鄰網格單元的壁面距離值，構造出一種快速且精確查找空間網格到壁面單元最短距離的方法，可以將每個空間網格單元所對應的壁面單元搜索量控制在兩位數甚至個位數以內。以上述1400萬量級的網格為例，本方法的搜索量僅為「遍歷查找」方法的萬分之一、甚至更少，採用單核CPU的計算時間也僅為13秒(單機單線程)。而且，網格規模(網格單元/節點總數)越大，本方法的優勢越突出。
【專利附圖】
【附圖說明】
[0023]下面結合附圖和【具體實施方式】對本發明做更進一步的具體說明，本發明的上述和/或其他方面的優點將會變得更加清楚。
[0024]圖1為壁面距離示意圖。
[0025]圖2為本方法的流程圖。
[0026]圖3為從壁面啟動計算示意圖。
[0027]圖4為更新隊列Q的計算流程圖。
[0028]圖5為處理更新隊列中元素的相鄰體單元示意圖。
【具體實施方式】
[0029]本發明利用「連續的物理空間中壁面距離是一個連續函數」這一基本規律，從近壁第一層網格出發，逐層計算並更新，可以快速且精確查找出計算域內所有空間網格的壁面距離值。計算網格單元的壁面距離與計算網格節點的壁面距離算法是完全一致的，因此以下描述將以「網格單元」為例，不再特意強調和區分「網格單元」的壁面距離算法與「網格節點」的壁面距離算法。壁面距離示意圖如圖1所示。
[0030]如圖2所示，本發明包括如下步驟:
[0031](1)提取待計算的網格的幾何信息，包括:各體單元的編號、單元中心坐標、與該體單元相鄰的各體單元編號；壁面單元編號、壁面單元中心坐標及所屬體單元編號。這些信息都是在空間網格原始存在的?目息。
[0032](2)啟動計算:如圖3所示，計算與壁面相鄰的第一層體單元的壁面距離值，並將與壁面相鄰的第一層體單元加入待更新隊列Q中。
[0033](3)若待更新隊列Q非空，則根據連續性，更新與隊列中各元素的相鄰體單元的壁
面距離信息。
[0034](4)若待更新隊列Q為空，則查找結束，輸出所有網格單元的壁面距離數據。步驟Cl)中，設置兩個列表存放網格的幾何信息:體單元隊列ListV和壁面單元隊列ListW ；
[0035]其中體單元隊列ListV包括:體單元編號，體單元中心坐標，與該體單元相鄰的各體單元編號，對每個體單元，記錄與該體單元最近的壁面距離編號及壁面距離值d ；
[0036]壁面單元隊列ListW包括:壁面單元編號，壁面單元中心坐標，所屬體單元編號。
[0037]步驟(2)中，遍歷壁面單元列表ListW,對遍歷到的壁面單元Ew,計算壁面單元Ew的壁面單元中心與其所屬的體單元Ev的體單元中心的距離d，該距離值就是體單元Ev的壁面距離；將體單元隊列ListV中體單元Ev的對應壁面單元和壁面距離值分別置為壁面單元Ew和壁面距離d ;同時，將體單元Ev加入待更新隊列Q中。
[0038]步驟(3)中，包括以下步驟，如圖4所示:
[0039](a)將待更新隊列Q拷貝至新的隊列R，並清空待更新隊列Q ;
[0040](b)遍歷隊列R,對遍歷到的體單元Ev,處理與體單元Ev相鄰的各體單元Εν』，處理方法為步驟(c)，如圖5所示；
[0041](c)判斷體單元Εν』的體單元中心到與體單元Ev對應的壁面單元Ew的距離d』是否比體單元Εν』的原壁面距離d更小；若更小，則將體單元Εν』對應的壁面單元和壁面距離值分別置為壁面單元Ew和壁面距離d』，並將體單元Εν』加入待更新隊列Q。
[0042]本發明具有以下特性:
[0043]1、利用「連續空間中壁面距離是一個連續函數」這一基本的物理規律，通過對已知單元的相鄰單元進行更新和遞歸查找，從而將對壁面單元的搜索量控制在兩位數、甚至個位數以內，可以快速、準確計算出空間網格單元的壁面距離值及其對應的壁面單元編號。
[0044]2、上述「已知單元」的初值由ListW所描述的近壁第一層體單元給定，且近壁第一層網格的壁面距離值及對應壁面單元是精確的。此後，通過遞歸查找的方式對「已知單元」隊列進行更新，可以實現對所有空間網格單元的遍歷和精確計算。
[0045]實施例
[0046]本實施例快速查找空間網格到壁面單元最短距離的方法，包括以下步驟:
[0047](I)根據待計算的網格拓撲結構，提取其基本的幾何信息和拓撲信息。包括:體單元編號、單元中心、與該體單元相鄰的各的體單元編號；壁面單元編號、面中心及所屬體單元編號。這些信息都是在空間網格原始存在的信息。另外，對每個體單元，還記錄對應的壁面單元編號。
[0048](2)啟動計算:計算與壁面相鄰的第一層體單元的壁面距離值，並將第一層體單元加入待更新隊列Q中。
[0049](3)若採用多CPU並行計算模式，則根據各CPU計算的三維網格塊之間的對接關係，更新相鄰網格塊邊界單元的壁面距離信息。
[0050](4)若隊列Q非空，則根據連續性，更新隊列元素的相鄰體單元的壁面距離信息。
[0051](5)若隊列Q為空，則查找結束，輸出所有網格單元的壁面距離數據。
[0052]本實施例第I步中:提取網格幾何信息和拓撲信息。
[0053](a)根據已讀入的網格數據，用戶可以很方便地提取如下信息，並將分別其存放在兩個列表中:
[0054]ListV (體單元數據):體單元編號，單元中心坐標，與該體單元相鄰的體單元編號。另外，用戶還記錄各體網格對應的壁面單元編號及壁面距離值d (初始值為充分大的正值，如 1.0e30)。
[0055]Listff (壁面單元數據):壁面單元編號，面中心坐標，所屬體單元編號。
[0056](b)如前所述，CFD分析所採用的離散網格分為兩種類型:多塊結構化網格和非結構網格。在多塊結構化網格中，各體網格單元的相鄰體網格單元編號是顯而易見的。例如，已知六面體網格單元編號為(I，J，K)，則與其相鄰的6個體單元編號依次為(1-1，J，K)、(1+1，J，K)、(I，J-1，K)、(I，J+1，K)、(I，J，K-1)、(I，J，K+1)。在非結構網格中，體網格單元
與相鄰體網格單元編號通常不是顯式的，而是存儲在一定類型的數據鍊表中。
[0057]本實施例第2步中:從壁面單元開始，啟動計算。
[0058]對列表ListW循環，首先計算壁面網格單元(記為Ew)中心與其所屬的體單元(記為Ev)中心的距離d。該距離值就是當前體單元的壁面距離，將其對應的壁面單元和距離值記錄為Ew和d,並將當前體單元加入待更新隊列Q中。
[0059]本實施例第3步中:多CPU並行計算時，更新網格塊對接邊界單元的計算流程包括:
[0060](a)對當前CPU，初始化更新隊列Q:若Q中含有與三維網格塊對接邊界面相鄰的體單元，則將這些體單元放入對接面更新隊列G中。
[0061](b)並行通訊，交換位於不同CPU上的網格塊邊界單元數據:根據CPU並行通訊機制(如MPI )，將當前CPU (如Cpul)的對接面更新隊列G發送至其相鄰網格塊所在的CPU (如Cpu2);同時接收從Cpu2發送過來的、與Cpul對接的網格塊邊界單元的對接面更新隊列H。G、H分別記錄Cpul與Cpu2對接的網格塊邊界面兩側的邊界單元的壁面距離信息(包括:壁
面距離d及對應的壁面單元編號)，二者編號一一對應。
[0062](C)在當前CPU (如Cpul)，對隊列H循環:取出隊首元素Ev及其對應的壁面單元Ew ;並根據對接關係，找到體單元Ev在當前CPU中的編號。
[0063](d)計算Ev與Ew中心之間的距離，記為d』。
[0064](e)若d，〈d (ListV所記錄的Ev的壁面距離),則分別以Ew、d』替換ListV中Ev所對應的壁面單元及壁面距離。
[0065]Cf)將Ev加入隊列Q中；並將Ev從H隊列中剔除。
[0066](g)重複第(C)至(f)步,直至隊列H被清空。
[0067]本實施例第4步中:根據連續性原則，計算Ev相鄰單元的壁面距離，並更新隊列Q，計算流程如圖4所示。
[0068](a)將隊列Q拷貝至隊列R，並清空Q。
[0069](b)提取R首元素，如體單元Ev ;並從ListV提取與Ev的相鄰體單元集，如{Εν』}。
[0070](c)對所有的相鄰體單元Εν』，如圖5,計算Εν』中心與Ew中心的距離,記為d』。
[0071](d)若d』〈d (ListV中記錄的Εν』的壁面距離)，則分別以Ew、d』替換ListV中Εν』對應的壁面單元及壁面距離，同時將Εν』加入隊列Q中。
[0072](e )對{Εν 』 }循環後，將Ev從隊列R中剔除。
[0073](f)重複第(b)至(e)步，直至隊列R被清空。
[0074]本發明提供了一種快速查找空間網格到壁面單元最短距離的方法，具體實現該技術方案的方法和途徑很多，以上所述僅是本發明的優選實施方式，應當指出，對於本【技術領域】的普通技術人員來說，在不脫離本發明原理的前提下，還可以做出若干改進和潤飾，這些改進和潤飾也應視為本發明的保護範圍。本實施例中未明確的各組成部分均可用現有技術加以實現。
【權利要求】
1.一種快速查找空間網格到壁面單元最短距離的方法，其特徵在於，包括以下步驟: (1)提取待計算的網格的幾何信息； (2)計算與壁面單元相鄰的體單元的壁面距離值，並將與壁面單元相鄰的體單元加入待更新的網格隊列Q中； (3)若隊列Q非空，則根據連續性，更新隊列元素的相鄰體單元的壁面距離信息； (4)若隊列Q為空，則查找結束，輸出所有網格單元的壁面距離數據。
2.根據權利要求1所述的一種快速查找空間網格到壁面單元最短距離的方法，其特徵在於，步驟(I)中，設置兩個列表存放網格的幾何信息:體單元隊列ListV和壁面單元隊列Listff ； 其中體單元隊列ListV包括:體單元編號,體單元中心坐標,與該體單元相鄰的各體單元編號，對每個體單元，記錄與該體單元最近的壁面距離編號及壁面距離值d ； 壁面單元隊列ListW包括:壁面單元編號,壁面單元中心坐標,所屬體單元編號。
3.根據權利要求2所述的一種快速查找空間網格到壁面單元最短距離的方法，其特徵在於，步驟(2)中，遍歷壁面單元列表ListW,對遍歷到的壁面單元Ew,計算壁面單元Ew的壁面單元中心與其所屬的體單元Ev的體單元中心的距離d，該距離值就是體單元Ev的壁面距離；將體單元隊列ListV中體單元Ev的對應壁面單元和壁面距離值分別置為壁面單元Ew和壁面距離d ;同時，將體單元Ev加入待更新隊列Q中。
4.根據權利要求3所述的一種快速查找空間網格到壁面單元最短距離的方法，其特徵在於，步驟(3)中，包括以下步驟: Ca)將待更新隊列Q拷貝至新的隊列R，並清空待更新隊列Q ； (b)遍歷隊列R，對遍歷到的體單元Ev,處理與體單元Ev相鄰的各體單元Εν』,處理方法為步驟(C)； (C)判斷體單元Εν』的體單元中心到與體單元Ev對應的壁面單元Ew的距離d』是否比體單元Εν』的原壁面距離d更小；若更小，則將體單元Εν』對應的壁面單元和壁面距離值分別置為壁面單元Ew和壁面距離d』，並將體單元Εν』加入待更新隊列Q。
【文檔編號】G06F17/50GK103793584SQ201410091194
【公開日】2014年5月14日 申請日期:2014年3月13日 優先權日:2014年3月13日
【發明者】丁可琦, 毛峰, 張日葵 申請人:北京大學工學院南京研究院, 南京北大工道軟體技術有限公司