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

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

0 引言

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

1 局部加密方法及相關(guān)概念

四邊形自適應(yīng)局部加密算法的具體步驟如下:首先進行網(wǎng)格生成,然后使用有限元方法對變分問題進行數(shù)值求解,得到數(shù)值結(jié)果后進行誤差分析,根據(jù)結(jié)果標記誤差超出允許閾值的區(qū)域,對這些區(qū)域進行網(wǎng)格加密,然后針對不同區(qū)域?qū)嵤┽槍π缘募用?再次進行求解,最后經(jīng)過多次循環(huán)直至得到滿足要求的結(jié)果。本研究基于給定的標記區(qū)域進行加密,主要研究網(wǎng)格調(diào)整過程中的加密策略,簡化了初始網(wǎng)格的生成以及邊界網(wǎng)格的處理,假設(shè)初始的四邊形網(wǎng)格劃分算法已生成協(xié)調(diào)的計算網(wǎng)格[1-4],并對相關(guān)概念進行了詳細說明和定義。

1.1 單元及網(wǎng)格剖分

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

1.2 正規(guī)網(wǎng)格

令M為Ω上的網(wǎng)格,Γ:=?Ω為Ω的邊界,如果:

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

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

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

2 四邊形網(wǎng)格的加密策略

2.1 消除懸點

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

圖1 網(wǎng)格中單元的加密

2.2 加密模板a

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

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

圖3 二次加密出現(xiàn)四邊形內(nèi)角最小值變小的情況

2.3 加密模板b

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

圖4 二次加密后四邊形內(nèi)角角度最小值不發(fā)生變化的情況

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

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

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

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

2.4 加密算法

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

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

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

圖7 單元加密模板

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

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

3 加密策略的程序?qū)崿F(xiàn)和驗證

3.1 二分策略

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

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

3.2 兩種基本單元類型

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

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

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

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

3.3 驗證算法

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

圖11 初始網(wǎng)格

4 結(jié)語

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

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

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

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

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

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

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

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