江 磊

JIANG Lei

（成都紡織高等?？茖W(xué)校 基礎(chǔ)部，成都 611731）

1 網(wǎng)格的局部加密

1.1 局部網(wǎng)格加密算法的問題

在有限元網(wǎng)格加密中主要存在的問題[1]：多級(jí)加載和半帶寬。對(duì)于單元局部加密的最大問題就是新增的單元、節(jié)點(diǎn)的編號(hào)如何處理，對(duì)于一般的有限元程序來說，如果單元和節(jié)點(diǎn)的變化不合理，對(duì)于生成的總體剛度矩陣的半帶寬會(huì)加大，消耗更多的計(jì)算機(jī)內(nèi)存。如壩體有限元計(jì)算程序，可模擬壩體修建的整個(gè)過程，模型是最終的壩體，然后記錄了修建工程中的某些階段，也就是多次加載。另外，為了能夠適應(yīng)現(xiàn)有的計(jì)算能力還必須合理的確定節(jié)點(diǎn)單元編碼，這樣可以減小半帶寬。

1.2 算法具體描述

1.2.1 獲得加密單元和過渡單元

有限元計(jì)算的結(jié)果通常經(jīng)過后處理，我們?cè)谏傻牡戎稻€、彩色云圖上很容易指定哪一部分的變化較劇烈，需要加密。用戶使用鼠標(biāo)選擇加密區(qū)域，獲得這個(gè)矩形的左上角和右下角的坐標(biāo)：(left, top)，(right, bottom)。然后掃描所有的單元，只要單元的一個(gè)節(jié)點(diǎn)落在加密區(qū)域內(nèi)，這個(gè)單元就是需要加密的。掃描結(jié)束后，生成一張表，記錄需要加密的單元號(hào)。

1.2.2 產(chǎn)生新的節(jié)點(diǎn)

因?yàn)榻佑|單元不可以劃分為三角形單元，出現(xiàn)二角形單元有兩種情況：(1)需加密的單元中含有三角形單元，在這種情況下，應(yīng)為三角形單元不是接觸單元，所以，劃分不會(huì)產(chǎn)生三角形的接觸單元。(2)在生成過渡單元這樣的過渡單元時(shí)，如果過渡單元是接觸單元的話，就產(chǎn)生了三角形的接觸單元，這是不允許的，必須采取必要的措施。采取的方式是，如果某個(gè)加密單元的過渡單元是接觸單元的話，則對(duì)應(yīng)的這邊就不增加節(jié)點(diǎn)，過渡單元也不進(jìn)行劃分。新增節(jié)點(diǎn)延續(xù)原來的節(jié)點(diǎn)編號(hào)，節(jié)點(diǎn)的坐標(biāo)由所在的邊或者所在單元型心確定。在這一過程中擴(kuò)充原來的加密單元、過渡單元表格，使其包含需加密單元新增加的節(jié)點(diǎn)的信息。依次為邊1增加的節(jié)點(diǎn)號(hào)，邊2增加的節(jié)點(diǎn)號(hào)，邊3增加的節(jié)點(diǎn)號(hào)，邊4增加的節(jié)點(diǎn)號(hào)，型心處增加的節(jié)點(diǎn)編號(hào)。如果對(duì)應(yīng)的部分沒有增加節(jié)點(diǎn)，就寫-1。

1.2.3 節(jié)點(diǎn)排序

要使生成的剛度矩陣具有合理的半帶寬，需要單元和節(jié)點(diǎn)編碼有一定的規(guī)律。通常網(wǎng)格在生成的時(shí)候都考慮了結(jié)構(gòu)半帶寬的優(yōu)化，加密后的網(wǎng)格破壞了原有的半帶寬。對(duì)于像壩體這樣的矩形結(jié)構(gòu)，可以先按照水平方向編碼，然后豎直方向編碼。把原來的節(jié)點(diǎn)信息表做一個(gè)備份。

1.2.4 單元排序

如何合理的對(duì)單元進(jìn)行排序，是局部加密的關(guān)鍵。采用的是這樣的一種想法：在加密前，如果一個(gè)單元的編碼出現(xiàn)在另外一個(gè)單元的編碼前，經(jīng)過加密處理后，如果這個(gè)單元被拆分了，那么拆分后的幾個(gè)單元的編碼也要出現(xiàn)在另外的那個(gè)單元的前面。

2 網(wǎng)格質(zhì)量優(yōu)化

網(wǎng)格生成完畢后，其拓?fù)浣Y(jié)構(gòu)(如節(jié)點(diǎn)-單元關(guān)系、單元-單元關(guān)系、節(jié)點(diǎn)-節(jié)點(diǎn)關(guān)系)也就確定了，這些關(guān)系在一定程度上反映著網(wǎng)格的規(guī)則程度。通常，在四邊形網(wǎng)格中任一個(gè)內(nèi)部節(jié)點(diǎn)相連的最佳單元個(gè)數(shù)為4，但是任何一種生成四邊形有限元網(wǎng)格的算法中，由于只考慮了節(jié)點(diǎn)周圍局部的情況，而往往會(huì)在生成的網(wǎng)格中存在著不規(guī)則節(jié)點(diǎn)和由此導(dǎo)致的畸形單元。這些節(jié)點(diǎn)和單元的存在都直接影響著網(wǎng)格的質(zhì)量，從而影響著有限元分析結(jié)果的準(zhǔn)確性。

進(jìn)行網(wǎng)格優(yōu)化就是進(jìn)一步提高網(wǎng)格質(zhì)量以滿足有限元分析的需要?？偟膩碚f，網(wǎng)格優(yōu)化分為拓?fù)鋬?yōu)化和幾何優(yōu)化兩種。拓?fù)鋬?yōu)化是改變網(wǎng)格的拓?fù)浣Y(jié)構(gòu)以達(dá)到優(yōu)化的目的；而幾何優(yōu)化則不改變網(wǎng)格的拓?fù)浣Y(jié)構(gòu)，只是重新調(diào)整網(wǎng)格節(jié)點(diǎn)的位置，使單元盡量地接近正方形。本文采用網(wǎng)格優(yōu)化算法，首先是通過改變網(wǎng)格的拓?fù)浣Y(jié)構(gòu)來使不規(guī)則單元的數(shù)量減少到最小，然后再對(duì)網(wǎng)格進(jìn)行位置的優(yōu)化，最終達(dá)到對(duì)整個(gè)網(wǎng)格質(zhì)量的提高和改善。

2.1 拓?fù)鋬?yōu)化

網(wǎng)格的拓?fù)鋬?yōu)化[2]側(cè)需要對(duì)網(wǎng)格節(jié)點(diǎn)之間的連接關(guān)系作出調(diào)整，對(duì)于四邊形單元，節(jié)點(diǎn)連接的單元數(shù)介于3到6之間，認(rèn)為是可以接受的。拓?fù)鋬?yōu)化主要有以下幾種模式：

刪除節(jié)點(diǎn)；

刪除單元；

刪除邊；

對(duì)角線調(diào)換；

在介紹網(wǎng)格的拓?fù)鋬?yōu)化之前，先引進(jìn)一個(gè)“度”的概念。在圖論中，一個(gè)無向圖中節(jié)點(diǎn)的度是指共享該節(jié)點(diǎn)的邊的數(shù)目，這里重新定義為共享該節(jié)點(diǎn)的單元的數(shù)目：

2.1.1 點(diǎn)刪除

這種拓?fù)鋬?yōu)化主要應(yīng)用于刪除那些合并過程中四邊形單元的內(nèi)角有大于180o的單元的情況。依次檢驗(yàn)內(nèi)部節(jié)點(diǎn)，當(dāng)某個(gè)節(jié)點(diǎn)的度為2時(shí)，必然會(huì)產(chǎn)生。

2.1.2 單元?jiǎng)h除

依次檢驗(yàn)所有的單元，如果此單元中存在一對(duì)相對(duì)的節(jié)點(diǎn)設(shè)為(A, B)度皆為3時(shí)，則刪除此單元，并將節(jié)點(diǎn)A、B合并為一個(gè)節(jié)點(diǎn)。

2.1.3 邊刪除

依次檢驗(yàn)連接了兩個(gè)節(jié)點(diǎn)的單元邊，如果某邊AB的兩個(gè)端點(diǎn)的度皆為3，則刪除此邊，連接到A、B節(jié)點(diǎn)的單元需要重新構(gòu)建成兩個(gè)新的四邊形單元。這兩個(gè)單元的公共邊的選擇需要按照節(jié)點(diǎn)的度來確定。設(shè)NC、ND、NF、NG分別為節(jié)點(diǎn)C、D、F、G的度，則兩個(gè)四邊形公共邊的選擇按如下原則：

2.1.4 對(duì)角線調(diào)換

依次檢驗(yàn)每一對(duì)相互連接的單元，公共邊AD將被調(diào)換成EB或者CF，如果滿足以下關(guān)系N1=NA+ND；N1= NA+ ND；N1= NA+ ND，則：

1)公共邊AD調(diào)換成BE

2)公共邊AD調(diào)換成CF

需要注意的是：上面的拓?fù)鋬?yōu)化執(zhí)行的前提是這種調(diào)整不會(huì)引起任何的單元交疊或產(chǎn)生畸形單元。網(wǎng)格拓?fù)湔{(diào)整應(yīng)該按照1-4的順序進(jìn)行。節(jié)點(diǎn)刪除將首先執(zhí)行，然后接著是單元?jiǎng)h除、邊刪除和對(duì)角線的調(diào)換，當(dāng)對(duì)角線調(diào)換完畢，再回到節(jié)點(diǎn)的刪除，從而進(jìn)行下一輪的拓?fù)湔{(diào)整，直到不需進(jìn)行拓?fù)湔{(diào)整為止。

2.2 幾何優(yōu)化

網(wǎng)格的幾何優(yōu)化是指通過移動(dòng)內(nèi)部節(jié)點(diǎn)的位置來調(diào)整網(wǎng)格的形狀以達(dá)到優(yōu)化網(wǎng)格質(zhì)量的目的。這類方法中最為典型的是Laplacian修勻方法，它用迭代法將每一個(gè)內(nèi)部非固定節(jié)點(diǎn)移至由其鄰接節(jié)點(diǎn)構(gòu)成的多邊形的形心位置，公式如下：

其中Ni是節(jié)點(diǎn)i所連接的節(jié)點(diǎn)總數(shù)，j是與i相連的節(jié)點(diǎn)，節(jié)點(diǎn)xi和yj是節(jié)點(diǎn)i的橫坐標(biāo)和縱坐標(biāo)值。這種方法是通過移動(dòng)內(nèi)部節(jié)點(diǎn)位置的方法來優(yōu)化網(wǎng)格單元的形狀，同時(shí)使網(wǎng)格看起來更加光順，所以也稱其為一種網(wǎng)格的修勻或光順的方法。

上式作為一個(gè)簡單而又常常比較有效的迭代公式被廣泛應(yīng)用于網(wǎng)格修勻，但它也存在一些根本的缺陷：1)當(dāng)存在非凸的幾何區(qū)域時(shí)，某些單元可能會(huì)重疊，結(jié)點(diǎn)可能被移到區(qū)域的邊界之外；2)在3D網(wǎng)格中，一個(gè)結(jié)點(diǎn)可能被移至某個(gè)相鄰單元的內(nèi)部；3)不能用于邊界結(jié)點(diǎn)的調(diào)整。盡管后來Herrmann及其他研究人員又分別提出了一些改進(jìn)的算法，但終究不可能克服修勻技術(shù)所固有的不足。

眾所周知，在結(jié)構(gòu)優(yōu)化中優(yōu)化方法可分為準(zhǔn)則法和數(shù)學(xué)規(guī)劃法兩大類。數(shù)學(xué)規(guī)劃法是嚴(yán)格按優(yōu)化問題的數(shù)學(xué)描述進(jìn)行求解，在理論上是嚴(yán)謹(jǐn)?shù)?，但在?shí)際應(yīng)用中其效率將隨優(yōu)化問題的規(guī)模增大而下降；準(zhǔn)則法是基十直觀推測(cè)，盡管有一定道理，但在理論上并不能保證獲得最佳的結(jié)果。著名的三桿析架向題，己嚴(yán)格證明了滿應(yīng)力準(zhǔn)則設(shè)計(jì)和最輕重量設(shè)計(jì)并不總是等價(jià)的。關(guān)于上述兩類方法的實(shí)際應(yīng)用，一般說來，設(shè)計(jì)變量少規(guī)模小的問題盡可能采用數(shù)學(xué)規(guī)劃法來逼近最優(yōu)解，而設(shè)計(jì)變量多規(guī)模人的問題盡可能引進(jìn)準(zhǔn)則的技巧來調(diào)整計(jì)算規(guī)模。

與此類似，在網(wǎng)格結(jié)點(diǎn)位置的優(yōu)化中，Laplacian修勻?qū)儆跍?zhǔn)則法，它具有準(zhǔn)則法普遍所具有的優(yōu)點(diǎn)：方法簡單，計(jì)算量小，速度快。Laplacian修勻技術(shù)作為網(wǎng)格生成方法的一種補(bǔ)充，己為大多數(shù)研究人員所接受。但是Laplacian修勻同樣也具有準(zhǔn)則法所固有的不足，最根本的問題在于不能確定修勻后的網(wǎng)格是否為最優(yōu)網(wǎng)格。

圖1為網(wǎng)格優(yōu)化前后的比較。鋪路法由于是從邊界向區(qū)域內(nèi)部生成單元，所以內(nèi)部單元的質(zhì)量比較差。從圖中可以看出，經(jīng)Laplacina修勻后，中心的網(wǎng)格質(zhì)量得到提高。

圖1 網(wǎng)格修勻

3 結(jié)論

本文主要介紹了網(wǎng)格加密算法，采用加密算法，達(dá)到了網(wǎng)格局部加密效果，而且提高了計(jì)算精度，滿足了計(jì)算要求。此外還介紹了網(wǎng)格質(zhì)量優(yōu)化和節(jié)點(diǎn)編號(hào)優(yōu)化算法，經(jīng)過優(yōu)化后網(wǎng)格質(zhì)量更高，利用節(jié)點(diǎn)編號(hào)優(yōu)化算法，減少了網(wǎng)格的半帶寬，節(jié)省存儲(chǔ)容量，而且能夠提高計(jì)算速度。

[1]黃曉東.二維有限元網(wǎng)格的局部加密方法[J].華南理工大學(xué)學(xué)報(bào).2004, 32(12)∶45-53.

[2]陳立崗.全四邊形有限元網(wǎng)格的拓?fù)鋬?yōu)化策略[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào).2007,19(1)∶78-83