一種快速查找多塊結構化網格對接關係的方法
2023-04-25 02:54:56
一種快速查找多塊結構化網格對接關係的方法
【專利摘要】本發明公開了一種快速查找多塊結構化網格對接關係的方法，包括以下步驟：（1）針對計算機幾何模型劃分的兩塊以上結構網格的每個網格塊，提取所有六個邊界面網格的幾何特徵，生成待查找關係邊界面網格對的隊列；（2）在待查找對接關係的兩個不同邊界面網格中，查找並生成搜索種子；（3）以步驟（2）得到的搜索種子為起點，在搜索種子所在的兩個邊界面網格內各自進行連續擴張，找出兩個對應邊界面網格內最大的單連通對接區域；（4）保存已查找出的對接區域信息，更新待查找關係邊界面網格對的隊列；（5）重複第（2）至（4）步，直至待查找關係邊界面網格對的隊列為空；（6）輸出所有三維網格模型網格塊的邊界面網格對接區域信息。
【專利說明】一種快速查找多塊結構化網格對接關係的方法
【技術領域】
[0001]本發明涉及一種計算機輔助工程(CAE)、計算流體力學(CFD)、計算結構力學(CSD)及數值仿真軟體技術，具體涉及基於網格節點信息的網格拓撲重構技術，是一種快速查找多塊結構化網格對接關係的方法。
【背景技術】
[0002]隨著計算機硬體技術和數值分析技術的快速發展，以計算流體力學(Computational Fluid Dynamics, CFD)軟體、計算結構力學(Computational StructureDynami cs, CSD )軟體為代表的計算機輔助工程軟體及數值仿真技術正越來越廣泛地應用於各種工程【技術領域】中，成為重要的產品研發與技術創新平臺。例如，航空飛行器的空氣動力學與結構力學設計、汽車熱舒適性與結構動力學設計、發動機熱力學與動力學設計、船舶水動力學設計等，都離不開大量基於CFD/CSD軟體的仿真計算與數值優化工作。
[0003]以CFD分析為例，我們通常需要將研究對象所在的連續物理空間以網格的形式，剖分成離散空間。CR)軟體就是以離散的網格系統為基礎進行數值迭代和物理分析的。目前廣泛使用的網格可以分為兩大類:多塊結構化網格(mult1-block structured mesh)和非結構網格(unstructured mesh)。其中，多塊結構化網格由於數據結構簡單、數值迭代收斂速度快、計算結果光滑等優勢而備受CFD工程師的青睞。
[0004]在多塊結構化網格中，每個網格塊(block)的節點信息都是各自獨立排序的；兩個相鄰網格塊之間通過公共分界面(網格塊的邊界面之一)進行對接，並傳遞彼此之間的數據信息，但兩個網格塊對該分界面都有各自獨立的排序、編號和存儲(圖1，G、H:網格塊(block) ;g、h:相互對接的網格節點)。因此，CFD軟體在進行數值計算之前，首先應根據已讀入的多塊結構化網格的節點信息，重新建立相鄰網格塊之間的對接關係，也即重構網格拓撲。
[0005]目前針對多塊結構化網格的拓撲重構技術主要有兩大類:
[0006]一種方案是「暴力算法」(brute-force)，即針對每個網格塊邊界面上的任意一點g，對其他網格塊邊界面上的所有節點進行遍歷搜索，在誤差範圍內得到與點g位置完全重合的另一點h，也即h及其所在的網格塊就是點g的對接點及對接網格塊(圖1)。這種方法構造簡單、可靠性高，但搜索時間非常長。通過對網格塊邊界面的節點數據進行預處理，如採用k-d樹(k-維樹)數據結構來存儲和管理網格塊的節點數據，可以大幅減少查詢次數。但即便如此，「暴力算法」的搜索時間仍比較長，且算法實現非常複雜。
[0007]另一種方案是「分治法」(divide and conquer),即人為地將網格塊的邊界面劃分成一系列更小的子面，將兩個相鄰網格塊的邊界面對接問題轉化為一系列子面的對接面，並且整個計算過程可以遞歸地進行下去。其具體實施過程包括如下步驟:(I)計算網格塊邊界面的幾何特徵，包括邊界面中心C和包絡半徑r (三維空間中為球半徑)，如圖3所示；
(2)從待查找隊列中取出兩個邊界面，如G、H，計算其面中心距離d，判斷d是否大於其包絡半徑之和(rl+r2);(3)若d> (rl+r2)，則表明G、H不可能相交，此時應更換其中一個邊界面(如H)，再重複比較；(4)若G與所有其他邊界面均不相交，則表明G為計算域的物理邊界，可以從查找隊列中剔除；(5)若d〈(rl+r2)，則對G、H進行細分，如分別切割成m和η個子面，即G={G1,G2,...，Gm}、H={H1，H2，...，Hn} ; (6)依次計算各子面的幾何特徵(圖3)，並類似第(2)步，判斷任意兩個子面間的相交特性；(7)若G上某個子面Gi與H面上所有子面均不相交，則將Gi從當前隊列中剔除；(8)若Gi與H面上的某個子面Hj相交，則可以參照第(5)步對二者繼續細分，直至每個子面的點數小於一定值後不再細分，而改對兩個子面直接逐點循環判斷是否存在節點重合及對接範圍。相對於第一種方案來說，「分治法」可以利用子面之間的位置關係排除一部分遍歷搜索量，但在CFD分析中，由於網格節點大都集中在分析對象表面的附近區域，因此即使在子面的包絡半徑範圍內，仍然存在大量與該子面並無對接關係的子面。因此「分治法」的計算量仍十分可觀。
[0008]隨著相關硬體技術的發展，當前的計算機輔助設計對數值仿真結果的精細化程度要求已經越來越高，這導致數值計算所採用的網格量(網格節點總數)也越來越大，通常都在千萬量級以上。對於多塊結構化網格來說，當網格塊數和節點總數較大時，採用「分治法」查找網格對接關係的時間過長，基於遍歷搜索的「暴力算法」的運行時間更是無法接受。例如,針對一個由347塊網格塊(block)拼接而成的計算網格，其網格節點總數約為1450萬個、邊界面上的節點數約為200萬個，此時採用分治法在3.4GHz主頻的CPU上計算，大約需要50分鐘才能獲得所有網格塊邊界面之間的對接關係，查找效率非常低。
【發明內容】
[0009]發明目的:本發明所要解決的技術問題是針對現有技術的不足，提供一種快速查找多塊結構化網格對接關係的方法。
[0010]為了解決上述技術問題，本發明公開了一種快速查找多塊結構化網格對接關係的方法，包括以下步驟:
[0011](I)針對計算機幾何模型劃分的兩塊以上結構網絡三維網格模型的每個網格塊，提取每個網格塊中所有六個邊界面網格的幾何特徵，生成待查找關係邊界面網格對的隊列；
[0012](2)在待查找對接關係的兩個不同邊界面網格中，查找並生成搜索種子，搜索種子是一對分別位於所述兩個不同邊界面網格上的完全重合的網格節點；網格節點是指結構網格內網格線的交點；結構網格的網格節點在邊界面網格內可以通過兩個下標值唯一確定；
[0013](3)以步驟(2)得到的搜索種子為起點，在搜索種子所在的兩個邊界面網格內各自進行連續擴張，找出兩個對應邊界面網格內最大的單連通對接區域；
[0014](4)保存已查找出的對接區域信息，更新待查找關係邊界面網格對的隊列；
[0015](5)重複第(2)至(4)步，直至待查找關係邊界面網格對的隊列為空；
[0016](6)輸出所有三維網格模型網格塊的邊界面網格對接區域信息。
[0017]步驟(I)中，提取邊界面幾何特徵包括以下步驟:
[0018](Ia)提取邊界面網格中心p、包絡半徑r、邊界面網格角點eg及該邊界面網格角點eg的對角點eg』;邊界面網格中心P坐標為該邊界面網格上所有節點坐標的算術平均，包絡半徑r指邊界面內其他網格節點到邊界面網格中心P的最大距離；其中邊界面網格的角點指的是邊界面網格的邊界線相交處的網格節點，邊界面網格角點的對角點指的是索引的兩個下標值與該邊界面網格角點索引的兩個下標值均相差I的網格節點，每個邊界面網格的角點均對應唯—個對角點；
[0019](Ib)按順時針方向生成邊界面網格角點Cg及其對應對角點eg』的列表；
[0020](Ic)提取所有邊界面網格的幾何特徵後，將未確定對接關係的邊界面網格放入待查找關係邊界面網格對的隊列中。
[0021]在待查找關係邊界面網格對的隊列中，查找並生成從兩個相異邊界面網格上各取一個網格節點組成的搜索種子，包括以下步驟:
[0022](2a)從待查找關係邊界面網格對的隊列中取出隊首兩個邊界面網格，分別記為邊界面網格G和邊界面網格H，計算兩者邊界面網格中心的距離d ;若邊界面中心距離小於兩者包絡半徑之和，則執行第(2d)至(2h)步，否則，執行第(2b )至(2c )步；
[0023](2b)標記邊界面網格G和邊界面網格H不相交；
[0024](2c)若邊界面網格G與待查找關係邊界面對的隊列中其他所有邊界面網格均不相交，則將面網格G標記為計算域的物理邊界；
[0025](2d)針對邊界面網格G的角點和對角點組合，在邊界面網格H中查找是否存在一組邊界面角點和對角點組合，使得邊界面網格G的角點與邊界面網格H的角點重合，並且邊界面網格G角點對應的對角點與邊界面網格H的角點對應的對角點也重合；所述兩個網格節點重合指的是兩個網格節點小於預設的容許誤差，預設的容許誤差取值為全部三維網格模型區域中最小網格節點間距的一半；
[0026](2e)若存在,則將面網格G上的該邊界面網格角點和邊界面網格H上與所述邊界面網格G的角點重合的點作為搜索種子；
[0027](2f)若不存在，則記錄邊界面網格G的角點和邊界面網格H的角點中距離最近的一對角點，以這對角點為初值，在邊界面網格G和邊界面網格H面內搜索兩個角點所在的連通區域之間的最小距離值d』 ；
[0028](2g)若最小距離值d』大於容許誤差，則邊界面網格G和邊界面網格H不相交，更換邊界面網格H，返回步驟(2a)
[0029](2h)若最小距離值d』小於容許誤差，則達到最小距離值d』的邊界面網格G和邊界面網格H上的網格節點對就是所需的搜索種子。
[0030]步驟(3)中以步驟(2h)得到的搜索種子為起點，進行連續擴張，查找出邊界面網格G和邊界面網格H內與兩個搜索種子連通的最大對接區域，包括以下步驟:
[0031](3a)將邊界面網格G中所有網格節點標記為未訪問狀態；
[0032](3b)將搜索種子，即邊界面網格G中網格節點g以及邊界面網格H中與之重合的網格節點h形成的網格節點對g〈_>h放入查找隊列Q中；
[0033](3c)若查找隊列Q為空集，表明連續擴張已完成，輸出面網格G和面網格H面內對接區域的網格節點標號；步驟3結束；
[0034](3d)若查找隊列Q非空，取出隊首元素q，q為網格節點對，由邊界面網格G中網格節點g以及邊界面網格H中的網格節點h形成，標記邊界面網格G中網格節點g為已訪問；
[0035](3e)測試步驟(3d)邊界面網格H中的網格節點h以及網格節點h的相鄰網格節點中，是否存在與步驟(3d)中的邊界面網格G的網格節點g重合的網格節點h』 ；[0036](3f)若步驟(3e)中邊界面網格H存在網格節點h』與邊界面網格G中網格節點g重合，遍歷邊界面網格G中所有與網格節點g相鄰且未訪問過的網格節點g』，將形成的所有網格節點對g』 h』加入查找隊列Q中；
[0037](3g)返回步驟(3c)。
[0038]有益效果:本發明可以大幅提高搜索效率，快速查找出多塊結構化網格的對接關係；並且，本發明構造的搜索方法計算流程簡單，容易實現。以一個1450萬節點、由347塊網格塊拼接而成的計算網格為例，其邊界面的節點總數約為200萬個，在3.4GHz主頻的CPU上查找網格塊對接關係:採用「暴力算法」進行搜索需要6小時；採用「分治法」進行搜索需要52分鐘；而採用本發明給出的快速搜索方法僅需I分21秒，用戶體驗非常好。
【專利附圖】
【附圖說明】
[0039]下面結合附圖和【具體實施方式】對本發明做更進一步的具體說明，本發明的上述和/或其他方面的優點將會變得更加清楚。
[0040]圖1為多塊結構化網格對接示意圖。
[0041]圖2為「分治法」對網格塊邊界面進行預處理:劃分子面，計算其中心及包絡半徑示意圖。
[0042]圖3為本發明流程圖。
[0043]圖4為網格邊界面的角點g及其所在網格單元的對角點g』示意圖。
[0044]圖5為本發明中生成「搜索種子」的流程圖。
[0045]圖6為本發明計算G、H邊界面之間最小間距的流程圖。
[0046]圖7為本發明中邊界面內連續擴張的計算流程圖。
【具體實施方式】
[0047]如圖3所示，本發明包括如下步驟:
[0048](I)針對所有網格塊的所有邊界面，提取其幾何特徵，包括面中心、包絡半徑、面角點及其對角點。
[0049](2)在帶查找對接關係的邊界面隊列中，首先查找並生成搜索種子。搜索種子是一對分別位於兩個不同邊界面網格(如G、H)上的重合的網格節點(如g、h)。
[0050](3)以上述種子為起點，在其所在的邊界面內進行連續擴張，可以找出兩個對應邊界面網格(如G、H)內最大的單連通對接區域。
[0051](4)保存已查找出的對接信息，更新待查邊界面網格隊列。
[0052](5)重複第(2)至(4)步，直至待查邊界面網格隊列為空。
[0053](6)輸出所有網格塊的邊界面對接信息，結束。
[0054]步驟(I)中:提取網格塊邊界面網格的幾何特徵。
[0055](Ia)如圖4所示，p為邊界面網格中心，r為包絡半徑，在多塊結構化網格中，網格塊每個邊界面網格包含4個角點(如g等)及其所在網格單元的對角點(如g』)。邊界面網格中心可以是其幾何中心，也可以在面內任取一個節點作為其中心，包絡半徑r指邊界面網格內其他網格節點到邊界面網格中心P的最大距離。
[0056](Ib)得到邊界面幾何特徵後，按順時針方向存儲4個角點及其對角點的列表。[0057](Ic)提取所有邊界面的幾何特徵後，將未確定對接關係的邊界面放入待查找關係邊界面對的隊列中，以執行下一步操作。
[0058]本發明在充分分析並提取網格塊邊界面一般特徵的基礎上，構造出一種快速查找多塊結構化網格對接關係的方法。針對上述347塊網格，採用本發明方法查找出該網格對接關係的時間僅為「分治法」的1/40。圖2為「分治法」對網格塊邊界面進行預處理:劃分子面，計算其中心及包絡半徑示意圖。
[0059]步驟(2)中:生成搜索種子，具體計算流程如圖5所示。
[0060](2a)從待查找關係邊界面對的隊列中取出隊首兩個面網格，分別記為G和H。計算二者面中心的距離d。若面中心距離小於二者包絡半徑之和(rl+r2，可以乘以某個大於I的安全係數後再作比較)，則執行第(d)至(h)步；否則，執行第(b)至(c)步。
[0061](2b)若d>rl+r2，表明G、H不相交。此時，可更換H，並重複第(a)步操作。
[0062](2c)若G與邊界面隊列中其他所有邊界面均不相交，則將G標記為計算域的物理邊界，並將其從待查隊列中剔除。
[0063](2d)針對G的4個角點-對角點組合，在H面網格中查找是否存在一個與之完全重合的角點-對角點組合，即二者間距d小於預設的容許誤差。
[0064](2e)若存在，則G面上的該角點(如g)和H面上與之重合的角點(如h)就是所需的搜索種子。「生成搜索種子」步驟結束。
[0065](2f)若不存在，則記錄上述間距最近的一對角點(如g』 -h』)，以此為初值，在G、H面內分別搜索g』連通區域和h』連通區域之間的最小距離值d』。
[0066](2g)若最小距離值d』大於容許誤差，則G、H不相交。此時，可更換H，並重複第Ca)步操作。
[0067](2h)若最小距離值d』小於容許誤差，則其所對應的一對網格節點(如g』、h』)就是所需的搜索種子。「生成搜索種子」步驟結束。
[0068]其中，給定邊界面網格H上一個網格節點h和邊界面網格G上一個網格節點g，計算H上與網格節點h連通區域的網格節點中與網格節點g的最小間距d的計算流程如圖6所示:
[0069](3a)初始時將網格節點h放入優先隊列Q中，將最小間距d初始化為網格節點g和網格節點h之間的距離；H中的所有節點標記為未訪問狀態；
[0070](3b)測試隊列Q是否非空。若隊列已空，此時記錄的最小距離d和達到該距離的邊界面網格中H中的節點即為所求，步驟(3)結束。
[0071](3c)若隊列Q非空，取出隊首元素網格節點h』，標記該網格節點為已訪問；計算網格節點h』與網格節點g之間的距離d』 ；若(1』比當前記錄的d小，則將d用d』替換，並記錄對應的網格節點h』 ；
[0072](3c)訪問網格節點h』周圍所有未訪問的點q，計算q與g點的距離I I q, g I I ;
[0073](3d)若q與g點的距離I |q，g| |比網格節點h』與網格節點g之間的距離小，則將q點放入隊列Q ;重複執行(b)到(d)步。
[0074]步驟(4)中:以邊界面網格G上網格節點g以及與之重合的邊界面網格H上的網格節點h構成的搜索種子g、h為起點，進行連續擴張，可以查找出G、H邊界面網格內與g、h連通的最大對接區域，具體計算流程如圖7所示。匕網格對接關係的方法，具體實現該技術方選實施方式，應當指出，對於本【技術領域】的:下，還可以做出若干改進和潤飾，這些改進1未明確的各組成部分均可用現有技術加以
【權利要求】
1.一種快速查找多塊結構化網格對接關係的方法，其特徵在於，包括以下步驟: (1)針對計算機三維幾何模型劃分的兩塊以上結構網絡的每個網格塊，提取每個網格塊所有六個邊界面網格的幾何特徵，生成待查找關係邊界面網格對的隊列； (2)在待查找對接關係的兩個不同邊界面網格中，查找並生成搜索種子，搜索種子是一對分別位於所述兩個不同邊界面網格上的重合的網格節點；網格節點是指結構網絡內網格線的交點；結構網格的網格節點在面網格內可以通過兩個下標值唯一確定； (3)以步驟(2)得到的搜索種子為起點，在搜索種子所在的兩個邊界面網格內各自進行連續擴張，找出兩個對應邊界面網格內最大的單連通對接區域； (4)保存已查找出的對接區域信息，更新待查找關係邊界面網格對的隊列； (5)重複第(2)至(4)步，直至待查找關係邊界面網格對的隊列為空； (6)輸出所有網格塊的邊界面網格對接區域信息。
2.根據權利要求1所述的一種快速查找兩塊及以上結構化網格對接關係的方法，其特徵在於，步驟(1)中，提取邊界面幾何特徵，包括以下步驟: (Ia)提取邊界面網格中心P、包絡半徑r、邊界面網格角點eg及該邊界面網格角點eg的對角點eg』 ；邊界面網格中心P的坐標為邊界面網格上所有網格節點坐標的算術平均，包絡半徑r指邊界面網格內其他網格節點到邊界面網格中心P的最大距離；邊界面網格的角點指的是邊界面網格的邊界線相交處的網格節點，邊界面網格角點的對角點指的是索引的兩個下標值與該邊界面網格角點索引的兩個下標值均相差I的網格節點，每個邊界面網格角點均對應唯--個對角點； (Ib)按順時針方向生成邊界面網格角點eg及其對應對角點eg』的列表； (Ic)提取所有邊界面網格的幾何特徵後，將未確定對接關係的邊界面網格放入待查找關係邊界面網格對的隊列中。
3.根據權利要求2所述的一種快速查找多塊結構化網格對接關係的方法，其特徵在於，在待查找關係邊界面網格對的隊列中，查找並生成從兩個相異邊界網格面上各取一個網格節點組成的搜索種子，包括以下步驟: (2a)從待查找關係邊界面網格對的隊列中取出隊首兩個邊界面網格，分別記為邊界面網格G和邊界面網格H，計算兩者面網格中心的距離d ;若面網格中心距離小於兩者包絡半徑之和，則執行第(2d)至(2h)步，否則，執行第(2b )至(2c )步； (2b)標記邊界面網格G和邊界面網格H不相交； (2c)若邊界面網格G與待查找關係邊界面網格對的隊列中其他所有邊界面網格均不相交，則將邊界面網格G標記為計算域的物理邊界，並將其從待查找關係邊界面網格對的隊列中剔除； (2d)針對邊界面網格G的角點和對角點組合，在邊界面網格H中查找是否存在一組邊界面網格角點和對角點組合，使得邊界面網格G的角點與邊界面網格H的角點重合，並且邊界面網格G角點對應的對角點與邊界面網格H的角點對應的對角點也重合；所述兩個網格節點重合指的是兩個網格節點小於預設的容許誤差，預設的容許誤差取值為全部三維網格模型區域中最小網格節點間距的一半； (2e)若存在，則將邊界面網格G上的該邊界面網格角點和邊界面網格H面上與所述邊界面網格G的角點重合的角點作為搜索種子；(2f)若不存在，則記錄邊界面網格G的角點和邊界面網格H的角點中距離最近的一對角點，以這對角點為初值，在邊界面網格G和邊界面網格H內搜索兩個角點所在的連通區域之間的最小距離值d』 ； (2g)若最小距離值d』大於容許誤差，則邊界面網格G和邊界面網格H不相交，更換邊界面網格H，返回步驟(2a) (2h)若最小距離值d』小於容許誤差，則達到最小距離值d』的邊界面網格G和邊界面網格H上的網格節點對就是所需的搜索種子。
4.根據權利要求3所述的一種快速查找多塊結構化網格對接關係的方法，其特徵在於，步驟(3)中以步驟(2h)得到的搜索種子為起點，進行連續擴張，查找出邊界面網格G和邊界面網格H內與兩個搜索種子連通的最大對接區域，包括以下步驟: (3a)將邊界 面網格G中所有網格節點標記為未訪問狀態； (3b)將搜索種子，即邊界面網格G中網格節點g以及邊界面網格H中與之重合的網格節點h形成的網格節點對g〈_>h放入查找隊列Q中； (3c)若查找隊列Q為空集，表明連續擴張已完成，輸出邊界面網格G和邊界面網格H對接區域的網格節點索引；步驟3結束； (3d)若查找隊列Q非空，取出隊首元素q，q為網格節點對，由邊界面網格G中網格節點g以及邊界面網格H中的網格節點h形成，標記邊界面網格G中網格節點g為已訪問；(3e)測試步驟(3d)邊界面網格H中的網格節點h以及網格節點h的相鄰網格節點中，是否存在與步驟(3d)中的邊界面網格G的網格節點g重合的網格節點h』 ； (3f)若步驟(3e)中邊界面網格H存在網格節點h』與邊界面網格G中網格節點g重合，對邊界面網格G中所有與網格節點g相鄰且未訪問過的網格節點g』，形成的所有網格節點對g』 h』加入查找隊列Q中； (3g)返回步驟(3c)。
【文檔編號】G06F17/50GK103838852SQ201410093541
【公開日】2014年6月4日 申請日期:2014年3月13日 優先權日:2014年3月13日
【發明者】毛峰, 丁可琦, 張日葵 申請人:北京大學工學院南京研究院, 南京北大工道軟體技術有限公司