四邊形自適應網格的局部加密算法

王志明,肖源明,李留洋,王 波,劉心志

(1.南京理工大學,江蘇 南京 210094;2.南京大學, 江蘇 南京 210008;3.中國船舶及海洋工程設計研究院,上海 200011;4.故宮博物院,北京 100009)

0 引言

在工程結構計算領域,為了精確描述結構特征,通常采用加密的網格化模型進行仿真運算,由于模型包含的網格數量可高達上百萬個,但是如果直接對整個計算區域進行網格加密,硬件資源需求較高、計算時間相對較長,會造成巨大的資源浪費。局部網格加密就是在部分降低計算時間和資源使用要求的基礎上,提高計算精度的網格處理方法,相較于整體均勻網格化處理,有著巨大的優勢。使用該方法可以很好地解決計算精度與計算時間之間的矛盾,具體方法表現為在粗網格區域演化時間步較長,計算量較小,可以較快獲得運算場的大致結構;在細網格區域則可以捕捉變化劇烈區域更加準確的數值變化,因此可以兼顧計算精度與效率,自適應地解決這類問題。工程上稱這種可合理地分配計算資源的數值方法為自適應有限元方法。在實際工程中,人們需要的只是獲得局部區域結構的精確解,故提出一種四邊形網格的局部加密策略,在減少計算量和計算時間的同時,快速獲得所需局部的精確計算結果。

1 局部加密方法及相關概念

四邊形自適應局部加密算法的具體步驟如下:首先進行網格生成,然后使用有限元方法對變分問題進行數值求解,得到數值結果后進行誤差分析,根據結果標記誤差超出允許閾值的區域,對這些區域進行網格加密,然后針對不同區域實施針對性的加密,再次進行求解,最后經過多次循環直至得到滿足要求的結果。本研究基于給定的標記區域進行加密,主要研究網格調整過程中的加密策略,簡化了初始網格的生成以及邊界網格的處理,假設初始的四邊形網格劃分算法已生成協調的計算網格[1-4],并對相關概念進行了詳細說明和定義。

1.1 單元及網格剖分

上述定義的單元m∈M,包含其邊界。這里的劃分區域所使用的單元主要是一般的四邊形,允許網格單元中出現懸點。所謂懸點v,即v作為某個單元m1∈M的頂點,卻位于另一單元m2∈M邊的內部[5]。而實驗需要考慮的正規網格(或稱協調網格)是不存在懸點的。

1.2 正規網格

令M為Ω上的網格,Γ:=?Ω為Ω的邊界,如果:

(1)對于所有的m∈M,m∩Γ若非空,則為m的一個頂點或m的一條整邊;

(2)對于所有的m1≠m2∈M,m1∩m2若非空,則為他們的一個共同頂點或一條共同邊。

若同時滿足以上兩個條件則稱網格M為正規的,根據這一定義判斷,本文中的正規網格皆不存在懸點[6-7]。

2 四邊形網格的加密策略

2.1 消除懸點

由于加密策略是基于正規網格進行的,因此,加密后的網格也應保證正規性。此外,加密策略中還需要注意網格單元的穩定性,即單元角度不會隨著加密過程變得越來越小。研究過程中,如圖1所示的單元加密模板,其中數字表示單元需要加密的次數。假設將單元的邊三等分為9個單元作為一次基本加密操作。然而,如果不進行額外處理,將會導致單元中出現懸點,從而破壞網格正規性。因此,需要設計相應的模板,在加密單元的鄰域中引入過渡單元,以消除懸點。

圖1 網格中單元的加密

2.2 加密模板a

通過處理非加密單元可以消除懸點,如圖2所示是一種加密模板方法,該模板具有網格正規性。但是,當將圖中兩個單元的加密次數設為2時,將會產生新的問題。如圖3所示,使用該加密模板會導致內角角度較小的四邊形單元的出現,而隨著加密次數增多,這種角度變小的趨勢將會持續。過于畸形的單元出現會導致后續計算的精度大大降低。

圖2 通過處理非加密單元來消除懸點

圖3 二次加密出現四邊形內角最小值變小的情況

2.3 加密模板b

若使用如圖4所示的加密模板,加密過程中產生的四邊形單元內角的最小值將不會受加密次數的影響。以一個單元數較多的網格為例,如圖5所示,左側為原始網格(區域中有一個洞,灰色為標記加密單元),右側為加密一次后的網格,其中除標記單元需要被三等分外,其鄰居單元也需作部分加密。

圖4 二次加密后四邊形內角角度最小值不發生變化的情況

圖5 原始網格(左)和根據模板加密一次以后的網格注:其中灰色標記單元做了完全加密。

本研究中的加密策略具體將基于單元頂點的標記數目進行選擇不同的加密模板,如圖6所示。在加密過程中,所有標記單元的頂點被標記為實心標記點,具有標記頂點的關聯單元將逐個獨立地加密,而不依賴于鄰居單元的加密方式。值得一提的是,每個單元的加密并不會影響鄰居單元,從而可以自動達成局部加密后的全局協調,實現正規網格。這種局部操作有利于程序實現,還可以進行并行網格調整。

圖6 單元的6種加密模板注:根據單元頂點的標注方式,實心標注的頂點在某標記單元上。

根據圖6中的加密模板,已經能夠根據標記點對網格單元進行一次加密。為了處理單元需要多次加密的情形,還要給加密單元的頂點設置加密次數S(v), 初始S(v)=隸屬單元的最大加密次數。加密后網格中頂點加密次數S(v)這樣變化:對于加密前已經存在的頂點v,只需要將他們的加密次數減1即可;對于加密過程中產生的新節點,若新點在原網格單元的邊上,則該頂點的加密次數設置為原單元邊的兩頂點的新加密次數的最小值;若新點在原網格單元的內部,則該頂點的加密次數為單元原4個頂點的新加密次數的最小值。只要重復執行以上加密過程并調整加密次數的值直至網格中不存在標記點,網格加密便完成了,詳情見圖4。

2.4 加密算法

經過上述的設計,加密策略可以產生正規且穩定的加密網格,其單元角度不會隨著加密過程變得越來越小,這一點可以很容易地證明。這是因為圖6中的所有模板都會在標記點周圍生成一個與原單元相似的新單元,這可以控制加密過程中網格單元角度的變化,從而保證網格的穩定性。關于網格的正規性,首先指出:任意兩個標記點之間的邊均被三等分;任意一個標記點到網格邊的中點的邊均被二分;任意不包含標記點的網格邊保持不變。因此,根據此規律以及標記點加密次數S(v)的計算方法,初始網格中邊的劃分方式是唯一確定的,即插入的點的數目以及位置是唯一確定的。據此可以證明,加密后網格的正規性,經過上述分析,總結基于加密模板以及加密次數設計的四邊形網格加密算法如下。

步驟1:給每個點確定加密次數S(v)(確定標記點)。

步驟2:依據標記點組合情況從圖7中挑選合適的加密模板并加密單元。

圖7 單元加密模板

步驟3:更新加密后網格點的加密次數S(v)。

步驟4:重復步驟1—3,至所有點加密次數為0。

3 加密策略的程序實現和驗證

3.1 二分策略

由于需要控制網格尺寸,在程序中采用了二分策略,即將單元邊二等分,以便更好地加密。具體而言,如果單元被完全加密,將會產生4個單元。然而,在加密過程中需要考慮網格的整體協調性,因此需要在一些位置安置過渡單元。例如,如圖8所示,左側為原始網格,右側為加密兩次后的網格,其中標記單元被16等分,鄰近單元也做了部分加密。

圖8 原始網格(左)和根據模板加密二次以后的網格注:其中灰色標記單元做了兩次完全加密。

3.2 兩種基本單元類型

加密過程生成了兩種基本單元類型,其中完全加密類型被定義為“田”字型,其對應原單元的所有邊均已進行了加密。而過渡單元則被定義為“Y”字型,僅對兩條邊進行了加密。需要注意的是,當對一個“田”字型單元或一個“Y”字型單元進行加密時,加密方式并不是唯一的。為了確定加密方式,選擇使用如圖7所示的模板,并根據單元邊的標記情況進行加密。如圖9—10所示,在圖中打叉的邊表示標記加密的邊,即使用圖9來說明當“田”字型單元的邊被標記時的加密方式,使用圖10說明“Y”字型單元的加密方式。

圖9 “田”字型單元加密模板

圖10 “Y”字型單元加密模板

根據單元邊的加密標記選擇對應模板,逐個單元進行獨立加密。該算法的實現并不依賴于鄰居單元如何加密,因此能夠保證加密后的全局協調。此外,所有的操作都是局部的,這有利于算法的并行實現。

3.3 驗證算法

下面將通過一個算例來驗證網格加密程序的基本功能。初始網格如圖11所示,并選定其中部分單元(標記為深色)進行連續加密。在加密過程中,結果顯示成功地應用了圖7中的所有模板。運算表明,該加密方法可以成功地解決問題。

圖11 初始網格

4 結語

結合程序實現和算例結果可知,所設計的四邊形自適應網格局部加密算法可以根據單元邊的加密標記而選擇合適的模板,根據相應的模板,在加密單元的鄰域中引入過渡單元,以消除懸點。并對具體網格的逐個單元進行獨立加密,且不依賴于鄰居單元,因此能夠很好地保證加密后的整體單元協調性。此外,所進行的加密過程都是局部的,有利于算法的并行實現,并得到正確的計算結果。

[1]曲延鵬,張坤,陳頌英.MRT-LBM三重網格局部加密算法研究[J].北京理工大學學報,2018(5):441-448.

[2]劉維,劉宇迪,趙世梅.跨尺度預報模式的網格局部加密算法[J].解放軍理工大學學報,2016(6):571-577.

[3]王川,趙成璧,唐友宏,等.NURBS曲面和隱式曲面求交的局部加密算法[J].科學技術與工程,2013(17):4826-4832.

[4]伍書重,莫思陽,張友良,等.數值流形法局部網格加密算法[J].科學技術與工程,2021(7):2850-2856.

[5]劉登學,張友良,丁秀麗,等.數值流形法中基于適合分析T樣條的局部網格加密算法[J].巖土力學,2019(4):1584-1595.

[6]李紅巖,王玉惠.基于超混沌系統的三維網格模型幾何保留加密算法[J].現代電子技術,2018(7):90-964.

[7]蒲偉,王家序,周廣武,等.卷吸速度方向與橢圓短軸成一夾角的彈流潤滑漸近網格加密算法[J].西安交通大學學報,2014(9):95-1006.