基于區(qū)域劃分和三角網(wǎng)格優(yōu)化的基段選擇算法

吳祿慎，王偉杰，陳華偉，馮 偉

（南昌大學(xué) 機(jī)電工程學(xué)院，江西 南昌330031）

0 引 言

構(gòu)建四邊形網(wǎng)格的所有算法可以歸類為直接法［1］和間接法［2］。直接法不經(jīng)過中間環(huán)節(jié)，把點(diǎn)云直接生成四邊形網(wǎng)格。由于需要處理的點(diǎn)云數(shù)據(jù)量巨大、模型形狀和邊界復(fù)雜，研究人員很難直接獲得分布均勻、拓?fù)涑伤倪呅蔚木W(wǎng)格模型，因此難以達(dá)到B 樣條曲面重構(gòu)四邊形參數(shù)域的要求。間接法先使用成熟Delaunay三角剖化［3］算法構(gòu)建散亂點(diǎn)云的三角網(wǎng)格，建立空間網(wǎng)格拓?fù)潢P(guān)系，然后把三角網(wǎng)格轉(zhuǎn)化為四邊形網(wǎng)格。與直接法相比，間接法程序更易實(shí)現(xiàn)，并且能生成質(zhì)量較好的四邊形網(wǎng)格。

在許多工程分析條件下，沿區(qū)域邊界單元尤其重要，理想情況是網(wǎng)格單元齊整地排列在區(qū)域邊界處。依據(jù)此理論，文獻(xiàn) ［4］將生成三角形曲面網(wǎng)格的前沿推進(jìn)算法擴(kuò)展到四邊形曲面網(wǎng)格生成，新算法從邊界處逐個(gè)單元前移前沿，解決了逐排推進(jìn)鋪路法中出現(xiàn)的魯棒性問題，能夠生成理想的四邊形網(wǎng)格；劉晶等［2］對(duì)Q－Morph算法中確定側(cè)邊方法進(jìn)行了改進(jìn)，雖然使網(wǎng)格轉(zhuǎn)化過程中殘留三角形單元數(shù)目大大減少，但是不能保證生成四邊形網(wǎng)格的質(zhì)量；陳陽等［5］改進(jìn)了前沿段生長算法，相比原算法，很好地解決了在幾何質(zhì)量較差、疏密變化較大的三角網(wǎng)格區(qū)域不能生成規(guī)則四邊形網(wǎng)格的問題，并通過改變網(wǎng)格頂點(diǎn)度和設(shè)置生長約束條件，一定程度上改善了四邊形網(wǎng)格質(zhì)量，但該算法對(duì)疏密度差別較大的三角網(wǎng)格區(qū)域使用相同方法生成四邊形，影響網(wǎng)格轉(zhuǎn)化的效率和質(zhì)量。

實(shí)驗(yàn)發(fā)現(xiàn)在哪一個(gè)前沿段上形成四邊形決定四邊形生長方向且嚴(yán)重影響最終生成四邊形網(wǎng)格的質(zhì)量，因此如何選擇基段成為網(wǎng)格轉(zhuǎn)化的關(guān)鍵。本文在生成點(diǎn)云前，使用一種基于多極線約束的重疊點(diǎn)云刪除算法［6］，以避免產(chǎn)生冗余點(diǎn)。對(duì)生成的點(diǎn)云數(shù)據(jù)使用曲率特征簡化［7］后，劃分出平坦區(qū)和非平坦區(qū)，然后三角化點(diǎn)云，優(yōu)化形成的三角網(wǎng)格，最后根據(jù)提出的基段選擇算法確定待生成四邊形的起始邊。

1 名詞解釋

節(jié)點(diǎn)、單元、棱和段：在網(wǎng)格生成中，節(jié)點(diǎn)和單元是基本實(shí)體。節(jié)點(diǎn)是點(diǎn)云的數(shù)據(jù)點(diǎn)，單元是一系列節(jié)點(diǎn)以逆時(shí)針方向首尾相連而成。棱是單元的一側(cè)，連接兩個(gè)端節(jié)點(diǎn)。為了區(qū)分一般棱，把位于三角網(wǎng)格與四邊形網(wǎng)格邊界上的棱稱為段。如圖1所示。

圖1 名詞解釋

合并前沿、前沿段、額角和基段：合并前沿是待轉(zhuǎn)換區(qū)域中所有邊界段的集合。合并前沿把已轉(zhuǎn)換區(qū)域從待轉(zhuǎn)換區(qū)域中分離開，且必須形成至少一個(gè)閉合環(huán)。合并前沿上的棱為前沿段；在前沿段兩端節(jié)點(diǎn)處與其相鄰前沿段的夾角稱為額角。作為形成四邊形起始邊的前沿段稱為基段。如圖1所示。

2 標(biāo)記平坦區(qū)和非平坦區(qū)

定義1 設(shè)X＝ ｛x1，x2，…，xn｝是將要建立曲面S上的n 個(gè)點(diǎn)集，集合X 中離任意點(diǎn)xi最近的k 個(gè)點(diǎn)稱為xi的K－鄰域，記為K（xi）。

本文利用樹的層級(jí)結(jié)構(gòu)對(duì)空間中每一個(gè)點(diǎn)進(jìn)行K－鄰域搜尋［8］。然后在每一個(gè)點(diǎn)如xi的K－鄰域基礎(chǔ)上擬合有約束的最小二乘平面P（xi）作為將要建立曲面在該點(diǎn)的切平面，K（xi）的形心位置是切平面的中心點(diǎn)oi。計(jì)算切平面P（xi）的單位法矢ni，使K（xi）內(nèi)的k 個(gè)點(diǎn)到這個(gè)切平面距離的平方和達(dá)到最小，然后以ni為xi點(diǎn)的單位法矢。為了計(jì)算ni的值，需建立K（xi）的協(xié)變矩陣

式中：（p－oi）是列向量， （p－oi）T是 （p－oi）的轉(zhuǎn)置，CV 是一個(gè)對(duì)稱的半正定3×3 矩陣，記矩陣CV 的最小特征值所對(duì)應(yīng)的單位特征向量為ei，法矢ni取對(duì)ei同向化處理后所對(duì)應(yīng)的值。將求得所有數(shù)據(jù)點(diǎn)的法矢量存在一個(gè)一維數(shù)組Vector中，順序與原始數(shù)據(jù)點(diǎn)數(shù)組相對(duì)應(yīng)。

如果K（xi）準(zhǔn)確表達(dá)了將要建立曲面S 在xi點(diǎn)附近的幾何形狀，那么曲面S在xi點(diǎn)上的曲率越大，點(diǎn)xi到切平面P（xi）的垂直距離越大，曲面S在xi點(diǎn)上的曲率越小，點(diǎn)xi到切平面P（xi）的垂直距離越小?？傻贸鱿旅娴亩x：

定義2 設(shè)X＝ ｛x1，x2，…，xn｝是將要建立曲面S上的n 個(gè)點(diǎn)集，對(duì)每一個(gè)數(shù)據(jù)點(diǎn)xi用它的K－鄰域擬合將要建立曲面S 在該點(diǎn)處的切平面P（xi），D＝ ｛d1，d2，…，dn｝為每一個(gè)點(diǎn)到它的切平面距離的絕對(duì)值

切平面距離計(jì)算如圖2所示。

圖2 切平面距離計(jì)算

為標(biāo)記平坦點(diǎn)和非平坦點(diǎn)，根據(jù)模型幾何形狀設(shè)定距離閾值Ωd，一般取經(jīng)驗(yàn)值Ωd＝0.1。如果di＜Ωd，則該點(diǎn)為平坦點(diǎn)，否則為非平坦點(diǎn)。確定出所有點(diǎn)的類型后，用長度為N的一維數(shù)組FP記錄其類型，平坦點(diǎn)標(biāo)記為1，非平坦點(diǎn)標(biāo)記為0。在此基礎(chǔ)上再劃分出平坦區(qū)域和非平坦區(qū)域。

3 三角網(wǎng)格質(zhì)量評(píng)價(jià)與修正

三角網(wǎng)格和網(wǎng)格轉(zhuǎn)化過程中的局部混合網(wǎng)格的質(zhì)量參差不齊，而修正網(wǎng)格結(jié)構(gòu) （連通性）會(huì)相應(yīng)提高網(wǎng)格的質(zhì)量，因此在網(wǎng)格轉(zhuǎn)化前和網(wǎng)格轉(zhuǎn)化過程中，以及局部后處理和全局后處理時(shí)，將會(huì)頻繁對(duì)基本網(wǎng)格進(jìn)行修正。

3.1 網(wǎng)格質(zhì)量評(píng)價(jià)

為了使背景三角網(wǎng)格的單元大小分布與度量規(guī)范相兼容，在三角網(wǎng)格所有節(jié)點(diǎn)處定義曲面度量張量［9］M。

在3D 空間，度量張量是一個(gè)對(duì)稱正定矩陣M3D，如Det（M3D）＞0，同時(shí)矩陣M3D的特征對(duì) （gi，λi） （i＝1，2，3）定義網(wǎng)格的主要延伸方向和節(jié)點(diǎn)空間。通過利用M3D，規(guī)范化空間中的基本矢量dε和3D 空間中對(duì)應(yīng)矢量dx 之間的長度尺度變換為

在參數(shù)空間中，通過使用等式 （x，y，z）T＝r（u，v），把節(jié)點(diǎn)密度的用戶規(guī)范效果M3D和曲面映射結(jié)合在一起的2×2曲面度量張量M 可以定義為

假設(shè)參數(shù)空間中存在兩點(diǎn)p1（u1，v1）和p2（u2，v2），則相對(duì)于M 兩點(diǎn)p1和p2間的距離定義為

通過利用度量規(guī)范描述曲面映射 （參數(shù)化），三角化和四邊形轉(zhuǎn)化方法都可以被應(yīng)用到范圍廣泛的曲面，包括那些具有快速變化的曲面偏導(dǎo)數(shù)和奇異點(diǎn)。

若存在△P1P2P3，由長度尺度測量和曲面度量張量，并根據(jù)式 （3）和式 （4），它的形狀質(zhì)量評(píng)價(jià)如下

式中

在式（7）中，Mi是Pi點(diǎn)處的曲面度量，Det（M）是矩陣M 的行列式。注意等式 （6）中的形狀質(zhì)量僅僅取決于三角形的形狀變形（相對(duì)于度量張量），而與邊長偏差沒有關(guān)系。由于任何尺寸等邊三角形的最大值都等于1。鑒于此，使用結(jié)合形狀和尺寸的參數(shù)來表示三角單元總體質(zhì)量

本文使用結(jié)合形狀和尺寸的參數(shù)珘μ 對(duì)三角形總體質(zhì)量進(jìn)行評(píng)價(jià)，這比使用α 質(zhì)量因子更能在質(zhì)量參差不齊的三角單元中分辨出不滿足要求的三角單元。

3.2 修正策略

完成三角網(wǎng)格質(zhì)量評(píng)價(jià)后，采用以下4種網(wǎng)格修正策略對(duì)不滿足要求的網(wǎng)格進(jìn)行修正。

（1）棱交換：用連接相對(duì)節(jié)點(diǎn)的新棱替換相鄰兩單元原有共有棱，如圖3 （a）所示。對(duì)于一個(gè)有效的交換操作，在度量空間和參數(shù)空間中兩對(duì)新形成的角度和都應(yīng)小1800，如圖3 （b）所示。

圖3 棱交換

（2）棱塌陷（單元?jiǎng)h除）：在棱塌陷操作中，把滿足一定條件的兩個(gè)單元共有棱刪除，共有棱兩端的節(jié)點(diǎn)合并成一個(gè)節(jié)點(diǎn)。因此與該棱相鄰的兩個(gè)單元同時(shí)被刪除。如圖4所示。

圖4 棱塌陷 （單元?jiǎng)h除）

（3）棱分割：棱分割過程中，在相鄰兩單元共有棱的中點(diǎn)處裂開，兩個(gè)相鄰單元將會(huì)被分為4個(gè)單元，如圖5所示。

圖5 棱分割

（4）節(jié)點(diǎn)刪除：當(dāng)一個(gè)節(jié)點(diǎn)被3個(gè)或4個(gè)三角形單元圍繞時(shí)，可以執(zhí)行節(jié)點(diǎn)刪除操作。如果節(jié)點(diǎn)被3個(gè)三角形包圍，如圖6 （a）所示，它們將合并為一個(gè)三角單元；對(duì)于節(jié)點(diǎn)由4 個(gè)三角形單元圍繞的情況，如圖6 （b）所示，將生成一條新棱，且這條棱為四邊形長度最短的對(duì)角線。

圖6 節(jié)點(diǎn)刪除

為了改善三角網(wǎng)格質(zhì)量，利用以上4種網(wǎng)格修正方法優(yōu)化背景三角單元。首先遍歷計(jì)算三角形網(wǎng)格中每一個(gè)三角形單元的形狀和尺寸參數(shù)，若不在規(guī)定的閾值Ω 范圍內(nèi) （0.3≤Ω≤0.7），可根據(jù)每一個(gè)不滿足質(zhì)量要求的三角形單元的具體情況選擇合適修正策略對(duì)其進(jìn)行處理。

4 基段選擇算法

在四邊形網(wǎng)格形成過程中，基段決定新單元的位置以及合并前沿前進(jìn)方向。四邊形質(zhì)量優(yōu)劣以及轉(zhuǎn)化過程是否順利進(jìn)行取決于是否選擇最優(yōu)基段。Q－Morph根據(jù)每一個(gè)前沿段的H 值和兩個(gè)前沿額角選擇最優(yōu)基段 （優(yōu)先權(quán)給予具有較小的H 值和額角接近理想值θrect＝1350的前沿段），前沿段和額角如圖 （1）所示。利用這種算法選擇基段之前需要知道每個(gè)前沿段的H 值和額角，并比較各前沿段H 值的大小，判斷額角是否接近理想值。因?yàn)槭褂迷撍惴ù_定基段需要計(jì)算、比較兩個(gè)值，所以選擇程序復(fù)雜，花費(fèi)時(shí)間多。并且在四邊形網(wǎng)格形成過程中沒有考慮不同區(qū)域幾何形狀的差異，僅使用一種基段選擇方法。除此之外，QMorph使用的額角計(jì)算公式僅適用于常規(guī)三角網(wǎng)格，而對(duì)于各項(xiàng)異性或幾何質(zhì)量較差的三角網(wǎng)格，計(jì)算精度不高。本文算法思想是首先計(jì)算出每個(gè)前沿段兩端節(jié)點(diǎn)處的額角值，然后依據(jù)給定的判別條件確定每個(gè)前沿段的狀態(tài)；在平坦區(qū)域，當(dāng)前沿段狀態(tài)相同時(shí)，計(jì)算每個(gè)前沿段的H值，選擇H 值最大的前沿段作為基段；當(dāng)前沿段狀態(tài)不相同時(shí)，則選擇狀態(tài)級(jí)別高的前沿段作為基段；對(duì)于不平坦區(qū)域，選擇長度小于cHmin（1.5≤c≤2）且狀態(tài)級(jí)別相對(duì)高的前沿段為基段。由于前沿段狀態(tài)不同是大概率事件，因此算法減少了計(jì)算量，提高了算法運(yùn)行效率。此外，本文算法采用適用于各向異性三角網(wǎng)格的額角計(jì)算公式，能夠明顯提高額角的計(jì)算精度。

4.1 前沿段H 值和額角

第i個(gè)前沿段的H 值計(jì)算公式如式 （10）所示

式中：λAk和λBk，k＝1，2分別是節(jié)點(diǎn)A 和節(jié)點(diǎn)B處度量張量M 的特征值 （參考3.1）。

根據(jù)度量張量M 和等式 （5），額角的計(jì)算如下

式中：du，dv——無窮小矢量。

4.2 前沿段狀態(tài)和分級(jí)

前沿段在兩端節(jié)點(diǎn)處的額角值決定這個(gè)前沿段的狀態(tài)，額角計(jì)算參考式（11）。對(duì)合并前沿中的每一段根據(jù)它的狀態(tài)進(jìn)行分級(jí)，得到的分級(jí)結(jié)果影響選擇哪一個(gè)前沿段作為基段。

由于一條前沿段狀態(tài)是根據(jù)前沿段兩個(gè)端節(jié)點(diǎn)處的額角值確定的，因此前沿段狀態(tài)由兩個(gè)要素進(jìn)行定義：一個(gè)表示左節(jié)點(diǎn)位，另一個(gè)表示右節(jié)點(diǎn)位。如果一個(gè)節(jié)點(diǎn)處的額角值小于特定閾值Φ （通常Φ＝1350），則該節(jié)點(diǎn)位設(shè)置為1，否則設(shè)置為0。每一個(gè)前沿段狀態(tài)分類存放在4種狀態(tài)列表中的一個(gè)，前沿段的4種狀態(tài)如圖7所示，圖中當(dāng)前前沿段用粗實(shí)線顯示。

圖7 前沿段狀態(tài)

根據(jù)狀態(tài)對(duì)前沿段分級(jí)有兩個(gè)目的：一是明確處理前沿段的優(yōu)先次序。狀態(tài)為1－1的前沿段給予第一優(yōu)先權(quán)，然后依次是狀態(tài)為0－1、1－0和0－0的前沿段；二是為定義側(cè)邊做準(zhǔn)備，因?yàn)橥ǔ６x至少一端已設(shè)置狀態(tài)位的棱為待形成四邊形的側(cè)邊。

4.3 基段選擇算法流程

（1）通過計(jì)算確定合并前沿中每個(gè)前沿段兩端節(jié)點(diǎn)處的額角值，判定出它們的狀態(tài)；

（2）判斷合并前沿是否在平坦區(qū)，若在平坦區(qū)，繼續(xù)向下進(jìn)行，否則轉(zhuǎn)到 （7）；

（3）若前沿段狀態(tài)相同，計(jì)算每個(gè)前沿段的H 值，選擇H 值最大的前沿段作為基段，否則轉(zhuǎn)到 （8）；

（4）把作為基段的前沿段從前沿列表中刪除；

（5）在基段基礎(chǔ)上生成四邊形后，若前沿列表非空，把新形成的前沿段添加到前沿列表中，同時(shí)更新與新四邊形相鄰前沿段的狀態(tài)以及相鄰三角網(wǎng)格的結(jié)構(gòu)，然后返回（1），否則轉(zhuǎn)到 （6）；

（6）若前沿段列表為空，算法結(jié)束；

（7）若在不平坦區(qū)，選擇長度小于cHmin且狀態(tài)級(jí)別相對(duì)高的前沿段為基段，然后轉(zhuǎn)到 （4）；

（8）若前沿段狀態(tài)不同，選擇等級(jí)高的前沿段作為基段，并轉(zhuǎn)到 （4）。

根據(jù)算法選擇出基段之后，由以下步驟構(gòu)建一個(gè)新四邊形單元：①確定待生成四邊形的左右側(cè)邊；②執(zhí)行頂邊再生操作，連接兩個(gè)側(cè)邊的頂節(jié)點(diǎn)，生成頂邊；③合并四條邊圍成的閉合區(qū)域內(nèi)所有三角形，形成一個(gè)四邊形單元。

把三角網(wǎng)格轉(zhuǎn)化為四邊形網(wǎng)格后，執(zhí)行全局后處理。應(yīng)用一組標(biāo)準(zhǔn)網(wǎng)格改進(jìn)程序和網(wǎng)格光順程序［10］，進(jìn)一步提升四邊形網(wǎng)格質(zhì)量。轉(zhuǎn)化完成后形成的四邊形網(wǎng)格與三角網(wǎng)格自由的拓?fù)溥B接關(guān)系不同，具有規(guī)則的連接，網(wǎng)格邊沿主曲率方向分布，能自然表現(xiàn)出模具幾何形狀的變化［11］。

5 實(shí) 例

以某汽車模具為例進(jìn)行了實(shí)例驗(yàn)證，實(shí)驗(yàn)結(jié)果如圖8、圖9所示。其中圖8 （a）是模具點(diǎn)云經(jīng)三角化和優(yōu)化后得到的三角網(wǎng)格模型，它有156886個(gè)三角形；圖8 （c）是轉(zhuǎn)化后生成的四邊形網(wǎng)格模型，四邊形數(shù)為70229 個(gè)，圖中顯示出模型曲面處的網(wǎng)格密度大，平坦區(qū)域網(wǎng)格密度小，并且生成的四邊形單元?jiǎng)蚍Q，整個(gè)模型很好保持了模具的特征，達(dá)到了不同區(qū)域分別采用相適宜方法轉(zhuǎn)化的效果。

圖8 模具點(diǎn)云網(wǎng)格化

圖9 模具點(diǎn)云曲面擬合

表1是Q－Morph改進(jìn)算法與本文算法在轉(zhuǎn)化速率和網(wǎng)格質(zhì)量方面的比較。比較結(jié)果表明本文算法達(dá)到了預(yù)期效果。表中質(zhì)差率為質(zhì)量差的四邊形數(shù)占總數(shù)的百分比。

表1 兩種算法的數(shù)據(jù)比較

6 結(jié)束語

本文在優(yōu)化三角網(wǎng)格后，使用基于區(qū)域劃分的基段選擇算法確定待形成四邊形基段，其優(yōu)勢有以下3點(diǎn)：

（1）采用長度尺度測量和曲面度量張量相結(jié)合的三角形質(zhì)量評(píng)價(jià)準(zhǔn)則，可以更準(zhǔn)確檢測出質(zhì)量差的三角形單元。

（2）使用新額角計(jì)算公式，提高了計(jì)算精度，從而更準(zhǔn)確對(duì)前沿段進(jìn)行分級(jí)；

（3）簡化選擇基段的判斷條件，并能夠根據(jù)不同區(qū)域采用與之相適宜的基段選擇方法，因此提高了網(wǎng)格轉(zhuǎn)化效率以及增大了選擇出最優(yōu)基段的概率。

實(shí)例驗(yàn)證在優(yōu)化三角網(wǎng)格的基礎(chǔ)上，使用本文算法提高了四邊形網(wǎng)格生成效率，明顯改善了最終生成的四邊形網(wǎng)格質(zhì)量，保證了隨后進(jìn)行的曲面重構(gòu)效果，并為下一步模型改進(jìn)、缺損模具修復(fù)以及數(shù)控加工創(chuàng)造了有利條件。

此外，算法還存在不足之處：平坦區(qū)網(wǎng)格密度要求盡可能小，但是在平坦區(qū)由于沒有結(jié)合前沿段的級(jí)別和長度選擇最優(yōu)基段，會(huì)造成平坦區(qū)網(wǎng)格沒有達(dá)到最理想的密度。如果兩者都考慮，會(huì)大幅增大計(jì)算量，也會(huì)對(duì)網(wǎng)格質(zhì)量產(chǎn)生一定影響。

［1］Park C，Noh JS，Jang IS，et al.A new automated scheme of quadrilateral mesh generation for randomly distributed line constraints ［J］.Computer－Aided Design，2007，39 （4）：258－267.

［2］LIU Jing，NIE Yufeng，SU Shaopu.Indirect method of quadrilateral mesh generation ［J］.Computer Engineering and Application，2010，46 （2）：44－47 （in Chinese）. ［劉晶，聶玉峰，蘇少普.四邊形網(wǎng)格間接生成方法 ［J］.計(jì)算機(jī)工程與應(yīng)用，2010，46 （2）：44－47.］

［3］Lo SH.Delaunay triangulation of nonuniform point distributions by means of multigrid insertion ［J］.Finite Elements in Analysis and Design，2013，63：8－22.

［4］CHEN Jianjun，ZHEN Jianjing，JI Tingwei，et al.Advancing front quadrilateral surface mesh generation ［J］.Chinese Journal of Computational Mechanics，2011，28 （5）：779－784 （in Chinese）.［陳建軍，鄭建靖，季廷煒，等.前沿推進(jìn)曲面四邊形網(wǎng) 格 生 成 算 法 ［J］.計(jì) 算 力 學(xué) 學(xué) 報(bào)，2011，28 （5）：779－784.］

［5］CHEN Yang，CUI Hanguo，LIU Jianxin，et al.Improved algorithm for advancing front growth in quadrilateral mesh generation ［J］.Computer Engineering，2011，37 （9）：291－293 （in Chinese）.［陳陽，崔漢國，劉健鑫，等.四邊形網(wǎng)格生成中的前沿邊生長改進(jìn)算法 ［J］.計(jì)算機(jī)工程，2011，37（9）：291－293.］

［6］GUO Jin，YUAN Jianying，CHEN Xiaoning.Algorithm for removing redundancy points based on multiview geometric［J］.Computer Engineering ＆Design，2014，35 （3）：958－962 （in Chinese）.［郭進(jìn)，袁建英，陳小寧.基于多視幾何的重疊點(diǎn)云 刪 除 算 法 ［J］.計(jì) 算 機(jī) 工 程 與 設(shè) 計(jì)，2014，35 （3）：958－962.］

［7］DAI Xing，CUI Hanguo，HU Huaiyu.Fast data point simplification algorithm based on curvature character［J］.Journal of Computer Applications，2009，29 （11）：3030－3032 （in Chinese）.［代星，崔漢國，胡懷宇.基于曲率特征的點(diǎn)云快速簡化算法 ［J］.計(jì)算機(jī)應(yīng)用，2009，29 （11）：3030－3032.］

［8］Connor M，Kumar P.Fast construction of K－nearest neighbor graphs for point clouds ［J］.IEEE Transactions on Visualization ＆Computer Graphics，2010，16 （4）：599－608.

［9］Xie Hehu，Yin Xiaobo.Metric tensors for the interpolation error and its gradient in Lp norm ［J］.Journal of Computational Physics，2014，256：543－562.

［10］HU Shimin，LAI Yukun，YANG Yongliang.A curvature flow based fairing algorithm of quad－dominant meshes ［J］.Chinese Journal of Computers，2008，31 （9）：1622－1628 （in Chinese）.［胡事民，來煜坤，楊永亮.基于曲率流的四邊形主導(dǎo)網(wǎng)格的光順方法 ［J］.計(jì)算機(jī)學(xué)報(bào)，2008，31 （9）：1622－1628.］

［11］ZHU Weipeng，GAO Chengying，LUO Xiaonan.Global anisotropic quad－dominant remeshing ［J］.Journal of Soft，2012，23 （5）：1305－1314 （in Chinese）.［朱為鵬，高成英，羅笑男.全局各向異性四邊形主導(dǎo)網(wǎng)格重建方法 ［J］.軟件學(xué)報(bào)，2012，23 （5）：1305－1314.］