基于離散化的復(fù)雜曲面建筑網(wǎng)格劃分方法

李鐵瑞 吳慧 王奇勝 高博青

摘 要：為實(shí)現(xiàn)存在裁剪、孔洞的復(fù)雜自由曲面建筑網(wǎng)格劃分，提出了一種基于離散的、以均勻性為目標(biāo)的劃分方法.將復(fù)雜曲面離散并縫合，形成由大量面片組成的離散曲面，作為多個(gè)參數(shù)曲面的一體化表示.采用改進(jìn)的誤差擴(kuò)散算法，在離散曲面上按一定的密度進(jìn)行初始布點(diǎn).采用基于空間距離的粒子動(dòng)力松弛算法對(duì)點(diǎn)云進(jìn)行初步均勻化，并應(yīng)用基于曲面距離的k均值算法進(jìn)行再次均勻化.對(duì)均勻的點(diǎn)云求曲面距離的Voronoi圖，并獲得相應(yīng)網(wǎng)格.對(duì)網(wǎng)格進(jìn)行拓?fù)鋬?yōu)化和光順優(yōu)化.算例表明，本文算法可有效處理存在裁剪、孔洞的復(fù)雜自由曲面，并得到均勻光順的三角網(wǎng)格.

關(guān)鍵詞：復(fù)雜曲面；離散化；網(wǎng)格劃分；均勻化；松弛

中圖分類號(hào)：TU311.41 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1674—2974（2018）07—0048—06

Abstract： A grid generation method for complicated multiple surfaces with trimmings and holes is presented. This method is based on the discretization and concentrates on the aim of homogeneity. The multiple surfaces are discretized separately and seamed together to achieve a discrete surface. The points are distributed on the discrete surface according to the density applying improved error-diffusion method. The points are homogenized by particle dynamics method with Euclid distance and then homogenized once more by k-means algorithm with surface distance. The Voronoi diagram with surface distance is delivered on the discrete surface to obtain the grids. The topological and smooth relaxations are applied on the grids. Eventually， the case study indicates that this method can solve the problem of grid generation for complicated multiple surfaces effectively and achieve the homogeneous and smooth grids.

Key words： complex surfaces；discretization；grid generation；homogenization；relaxation

隨著計(jì)算機(jī)輔助設(shè)計(jì)技術(shù)，特別是建模技術(shù)的發(fā)展，建筑師的創(chuàng)造力可以得到更好的發(fā)揮，自由曲面的建筑形式因其強(qiáng)力的視覺效果得到了人們的青睞.但是，對(duì)復(fù)雜的曲面進(jìn)行網(wǎng)格劃分十分困難，尚沒有行之有效的方法，是目前空間結(jié)構(gòu)領(lǐng)域研究的一個(gè)難點(diǎn)與熱點(diǎn).

對(duì)自由曲面，采用顯式或隱式方程都無(wú)法表達(dá)，常采用NURBS技術(shù)[1]，或結(jié)合形態(tài)優(yōu)化方法[2]建模.而對(duì)于特別復(fù)雜的曲面，用單個(gè)NURBS曲面表達(dá)也甚為困難，乃至無(wú)法表達(dá)，此時(shí)需采用多個(gè)曲面來(lái)建模.T-Splines[3]技術(shù)產(chǎn)生于2003年，并由T-Splines 公司.商業(yè)化，近年來(lái)也有大量的研究，該技術(shù)對(duì)多曲面建模提供了良好的支撐.由于NURBS曲面是由高階非線性參數(shù)方程組表示的，一些經(jīng)典的算法難以應(yīng)用于NURBS曲面，而對(duì)于裁剪曲面特別是多曲面，則更為困難.

Owen[4]對(duì)經(jīng)典網(wǎng)格劃分算法進(jìn)行了總結(jié).早期的學(xué)者提出如波前推進(jìn)法[5]、Delaunay法[6]、映射法[7]等.但是這些方法在自由曲面應(yīng)用有其局限性.近年來(lái)，不少學(xué)者對(duì)該問題進(jìn)行了深入研究，并提出了一些針對(duì)NURBS曲面的解決方案.現(xiàn)有的設(shè)計(jì)多采用參數(shù)域設(shè)計(jì)并映射到曲面，通過一些技術(shù)手段改善映射變形，或采用空間距離.熊英等[8]使用空橢圓準(zhǔn)則代替?zhèn)鹘y(tǒng)的空?qǐng)A準(zhǔn)則解決曲面Delaunay問題；江存等[9]應(yīng)用自定義單元法改善映射變形；蘇亮等[10]采用基于主應(yīng)力線的波前推進(jìn)法，實(shí)現(xiàn)網(wǎng)格劃分；危大結(jié)等[11]、潘煒等[12]采用等面積曲面展開方法，改善從平面到曲面的映射關(guān)系.對(duì)于多重曲面，現(xiàn)有的方法多是在各個(gè)曲面上分別劃分網(wǎng)格，再進(jìn)行調(diào)整.然而，此法曲面交界處可能會(huì)存在明顯的彎折現(xiàn)象，且由于曲線分屬多個(gè)曲面，難以共同優(yōu)化調(diào)整，難以達(dá)到設(shè)計(jì)要求.

面對(duì)復(fù)雜曲面，先將其離散為多面體的離散化表示，是一種解決方案.得到離散化表達(dá)的曲面后，裁剪邊界、洞口、多曲面，以及映射關(guān)系的負(fù)面影響將不再存在.一些基于曲面距離的算法也更容易應(yīng)用.另一種情形是，建筑師首先制作實(shí)物模型，再采用3-D掃描技術(shù)數(shù)字化，得到離散化表示的曲面數(shù)據(jù)，就可以不必進(jìn)行復(fù)雜的曲面擬合重構(gòu)步驟[13]，而直接進(jìn)行網(wǎng)格劃分.

本文基于曲面離散，提出針對(duì)復(fù)雜自由曲面的網(wǎng)格劃分方法.經(jīng)過多個(gè)復(fù)雜自由曲面的驗(yàn)證，表明網(wǎng)格劃分算法的有效性、可靠性.

1 算法概覽

本算法的基本流程如下：

步驟1：將曲面離散為小面片組成的離散表示；

步驟2：設(shè)置密度控制函數(shù)與曲率控制函數(shù)；

步驟3：在離散曲面上按密度要求生成初始點(diǎn)；

步驟4：對(duì)初始點(diǎn)進(jìn)行密度與曲率控制的均勻化；

步驟5：形成網(wǎng)格；

步驟6：對(duì)網(wǎng)格進(jìn)行拓?fù)渑c光順優(yōu)化.

1.1 離散方法

對(duì)參數(shù)曲面，如NURBS曲面，若曲面完整，則采用參數(shù)域均勻布點(diǎn)，形成網(wǎng)格，映射至曲面.對(duì)裁剪曲面，先形成均勻點(diǎn)，再將邊界外的點(diǎn)舍棄，接著在參數(shù)平面上求剖分，并映射至曲面.對(duì)于多重曲面或環(huán)面，需要在曲面交界處進(jìn)行縫合.

1.2 改進(jìn)誤差擴(kuò)散算法

誤差擴(kuò)散算法（Error-Diffusion，簡(jiǎn)稱E-D算法）由Floyd和Steinberg[14]于1976年發(fā)明.最初被應(yīng)用于計(jì)算機(jī)圖像處理領(lǐng)域的灰度圖打印.一張圖片上每一個(gè)像素點(diǎn)都有一個(gè)灰度信息，而打印時(shí)只存在有墨點(diǎn)和無(wú)墨點(diǎn)兩種狀態(tài)，如何分布這些墨點(diǎn)使得圖片打印后看起來(lái)與原圖一致即是誤差擴(kuò)散算法所要解決的問題.

離散曲面布點(diǎn)和灰度圖生成情形類似，每一小三角形面片都具有一個(gè)點(diǎn)密度值，需要解決的問題是怎樣分布這些點(diǎn)，以滿足密度分布要求.

本文采用密度修正函數(shù)fρ與曲率修正函數(shù)fk對(duì)離散曲面上點(diǎn)密度的分布進(jìn)行調(diào)整.該函數(shù)根據(jù)用戶的美學(xué)需求，可任意定義.

根據(jù)前人的實(shí)踐經(jīng)驗(yàn)，誤差擴(kuò)散算法容易出現(xiàn)重復(fù)模式（artifacts）缺陷.現(xiàn)有的研究采用以蛇形[15]或空間填充曲線[16]替代逐行掃描，以及精心設(shè)計(jì)誤差分配的范圍與系數(shù)[17]，甚至采用變系數(shù)法[18]等方法規(guī)避這一缺陷.然而這些研究的對(duì)象都為像素矩陣，而本文的應(yīng)用情形不存在行列概念，故難以采用現(xiàn)成的改進(jìn)方法.

本文參考前人的思路對(duì)E-D算法進(jìn)行改進(jìn).傳統(tǒng)算法中，當(dāng)某點(diǎn)處密度累積到達(dá)閾值t后，即布點(diǎn).作者在該步驟中加入了概率因子p，布點(diǎn)前需要進(jìn)行隨機(jī)判斷，p概率布點(diǎn)，解決了重復(fù)模式問題.概率因子p建議值受布點(diǎn)數(shù)k與離散曲面頂點(diǎn)數(shù) n的比值k/n影響，該比值越大p的取值應(yīng)越大，反之亦然.

傳統(tǒng)算法中閾值t一般取常量0.5，即四舍五入.而根據(jù)作者的實(shí)驗(yàn)結(jié)果，t取常量0.5將會(huì)有起始點(diǎn)附近出現(xiàn)空洞的現(xiàn)象.本文針對(duì)此現(xiàn)象進(jìn)行改進(jìn)，采用變化的閾值，t將隨著訪問點(diǎn)數(shù)的增加而逐漸增大至0.5，即初始時(shí)更容易布點(diǎn)，以解決起始點(diǎn)附近的空洞現(xiàn)象.t的增長(zhǎng)率取值根據(jù)比值k/n確定，該比值越大，則增長(zhǎng)率取值應(yīng)越高；反之亦然.根據(jù)作者實(shí)驗(yàn)，修正后的算法，起始點(diǎn)選擇對(duì)最終結(jié)果影響不大，一般取0號(hào)點(diǎn)即可.

圖1為該布點(diǎn)算法的平面算例，該算法可以有效地滿足密度分布，且并未出現(xiàn)重復(fù)模式現(xiàn)象，為下一步均勻性優(yōu)化提供了一個(gè)可行的初值.

1.3 基于空間距離的均勻化算法

前文生成的點(diǎn)陣雖然在曲面上基本滿足密度分布要求，但是均勻性不良，需要應(yīng)用松弛算法進(jìn)行優(yōu)化.本文采用粒子動(dòng)力松弛算法[19].

本算法基本思想為，將各點(diǎn)視為具有質(zhì)量mi、電量qi的粒子，質(zhì)量與電量一般取1.0.任意兩個(gè)粒子Vi，Vj間存在斥力：

其中，kq為用于控制斥力強(qiáng)度的系數(shù)，該系數(shù)對(duì)布點(diǎn)結(jié)果影響較大，需要試算并調(diào)整；ri，j為節(jié)點(diǎn)Vi與Vj的距離，此處采用歐幾里得距離.本文中不考慮引力，距離大于臨界距離rc后，即認(rèn)為不存在相互作用力，臨界距離rc一般可取為1.5 ～ 2.5倍目標(biāo)桿長(zhǎng)，亦可根據(jù)計(jì)算結(jié)果調(diào)整.其中，kq與rc可受用戶自定義函數(shù)fρ與fk的調(diào)整，以控制不同區(qū)域的點(diǎn)密度.點(diǎn)將在斥力作用下運(yùn)動(dòng)并穩(wěn)定在平衡位置附近.

圖2為該松弛算法的平面算例.實(shí)驗(yàn)表明，該算法可以有效地均勻化點(diǎn)陣， 且對(duì)初始布點(diǎn)不敏感.

但應(yīng)用于曲面時(shí)，由于動(dòng)態(tài)更新兩點(diǎn)間的曲面距離復(fù)雜度較高，本算法采用歐幾里得距離，存在不足.因此僅作為初步優(yōu)化，為后文步驟提供初值.

1.4 基于曲面距離的均勻化算法

Lloyd算法（又稱Voronoi迭代、Voronoi松弛）由Lloyd[20]于1957年發(fā)明，1982年發(fā)表.Macqueen[21]改進(jìn)后用于離散對(duì)象，也稱k均值算法（k-means）.用于機(jī)器學(xué)習(xí)領(lǐng)域的聚類分析.

對(duì)于空間中需要聚類（cluster）的n個(gè)d維向量（x1，x2，…，xn），k均值算法的目標(biāo)是將其分為k個(gè)簇 S = {S1，S2，…，Sk}，且簇內(nèi)各點(diǎn)到其中心的距離之和最小.即：

直接求解優(yōu)化函數(shù)（2）較困難.k均值算法采用迭代思想，交替進(jìn)行以下兩個(gè)步驟直至收斂[22]：分配步驟：根據(jù)距離函數(shù)確定xi屬于哪個(gè)簇Si.更新步驟：用各個(gè)簇的中心更新其均值.

k均值算法目標(biāo)與本文均勻分布離散曲面點(diǎn)的目標(biāo)一致.Du Qiang等[23]采用該算法進(jìn)行二維點(diǎn)的變密度分布，周炎濤等[24]將其應(yīng)用于復(fù)雜三維點(diǎn)的聚類，取得良好的效果.

本文將該算法應(yīng)用于離散化曲面.且可受函數(shù)fρ與fk的調(diào)整.實(shí)驗(yàn)表明該算法可以有效地實(shí)現(xiàn)空間曲面上點(diǎn)的變密度分布.

1.5 離散曲面Voronoi圖計(jì)算方法

Voronoi圖的基本思想是存在k個(gè)站點(diǎn)（site），平面分成k個(gè)區(qū)域，使得每個(gè)區(qū)域內(nèi)的點(diǎn)到它所屬區(qū)域站點(diǎn)的距離最近.

本文將曲面離散化后，可以應(yīng)用Voronoi圖的定義求解.將Voronoi圖定義推廣到離散曲面.離散曲面可視作一個(gè)以面片為頂點(diǎn)，相鄰面片之間存在一條邊的圖.當(dāng)小面片的相對(duì)尺度足夠小時(shí)，即可認(rèn)為該圖兩點(diǎn)間的最短路徑即是對(duì)應(yīng)的曲面距離.

求得Voronoi圖后，即可形成網(wǎng)格.

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

然而，三角形質(zhì)量最優(yōu)的網(wǎng)格并非建筑上要求的網(wǎng)格.在1.5節(jié)步驟之后，需要對(duì)網(wǎng)格進(jìn)行拓?fù)鋬?yōu)化.Frey等[25]認(rèn)為，對(duì)于三角網(wǎng)格，內(nèi)部節(jié)點(diǎn)度數(shù)為6是較優(yōu)的.基本思想為遍歷每一個(gè)四邊形，若交換該四邊形的對(duì)角線能使內(nèi)部頂點(diǎn)度數(shù)更接近6，則進(jìn)行交換.

如圖3所示，左圖圈中四邊形箭頭所指對(duì)角線對(duì)應(yīng)著質(zhì)量更高的兩個(gè)三角形，但四個(gè)頂點(diǎn)皆為奇異點(diǎn)，其度數(shù)分別為5，7，5，7.進(jìn)行邊交換后，得到右圖，對(duì)應(yīng)的四個(gè)頂點(diǎn)度數(shù)都為6，規(guī)整性提高.

1.7 光順優(yōu)化

本文采用彈簧質(zhì)點(diǎn)法[26].其基本思想是將桿件視為具有剛度ks的彈簧，節(jié)點(diǎn)視為具有質(zhì)量的質(zhì)點(diǎn).其中， m一般取常量1.0即可；ks的大小影響計(jì)算速度與收斂性，需要根據(jù)經(jīng)驗(yàn)調(diào)整；計(jì)算過程中通過調(diào)整各桿件的原長(zhǎng)控制彈簧力的大小與方向，并影響最終結(jié)果.原長(zhǎng)可受密度修正函數(shù)fρ與曲率修正函數(shù)fk的修正，以控制不同區(qū)域的密度.節(jié)點(diǎn)將在彈簧力作用下運(yùn)動(dòng)，并穩(wěn)定在平衡位置.實(shí)驗(yàn)表明，最終可得到較為光順的網(wǎng)格.

2 算例分析

2.1 完整單曲面算例

作者創(chuàng)建了一個(gè)月牙形曲面模型，如圖4（a）所示.長(zhǎng)約100 m，跨度約40 m，矢高約20 m.該模型建模時(shí)采用一個(gè)完整曲面，無(wú)裁剪及孔洞，作為基準(zhǔn)算例.將其離散為320 000個(gè)小三角形面片.點(diǎn)布置以及Voronoi圖如圖4（c）所示，網(wǎng)格效果如圖4（d）所示.本算法生成的網(wǎng)格均勻性較好，但由于曲面變化較大，為保證均勻，網(wǎng)格流線存在發(fā)散和收縮現(xiàn)象，存在少量奇異節(jié)點(diǎn)，但過渡較為流暢.

作為對(duì)照的映射法網(wǎng)格如圖4（b）所示.由于該模型為單曲面，且無(wú)裁剪及孔洞，適合應(yīng)用映射法，由于曲面形態(tài)、建模方式等原因，映射變形較大，生成的網(wǎng)格流暢性較好，但是存在明顯均勻性問題.

均勻性指標(biāo)如表1所示，桿長(zhǎng)相近的情況下，本算法網(wǎng)格均勻性顯著優(yōu)于映射法.

2.2 裁剪孔洞曲面算例

作者對(duì)2.1節(jié)曲面進(jìn)行了裁剪，如圖5（a）所示.模型尺寸同2.1節(jié)，洞口直徑為12 m，遠(yuǎn)大于網(wǎng)格尺寸，因此將會(huì)影響網(wǎng)格生成.

算例表明，本算法可有效處理裁剪和孔洞，優(yōu)化后的點(diǎn)布置及Voronoi圖如圖5（c）所示，生成的網(wǎng)格如圖5（d）所示.洞口附近通過少量奇異點(diǎn)過渡，無(wú)明顯不流暢現(xiàn)象.洞口網(wǎng)格質(zhì)量較好，整體流暢性尚可.均勻性指標(biāo)如表2所示，桿長(zhǎng)相近的情況下，本算法網(wǎng)格均勻性顯著優(yōu)于映射法.

作為對(duì)照的映射法網(wǎng)格如圖5（b）所示.從圖中，可以發(fā)現(xiàn)，映射法受孔洞影響較大，孔洞和裁剪邊界周圍網(wǎng)格難以處理，出現(xiàn)明顯的不流暢、不均勻現(xiàn)象.且由于過于不均勻，1.7節(jié)的優(yōu)化算法難以應(yīng)用，優(yōu)化過程中易出現(xiàn)網(wǎng)格折疊現(xiàn)象.

2.3 復(fù)雜曲面算例

復(fù)雜的建筑模型，采用多重曲面建模可以簡(jiǎn)化建模的難度，提高建模質(zhì)量，提高建模效率[3].

然而對(duì)于復(fù)雜曲面，網(wǎng)格劃分困難.現(xiàn)有的方法多是在各個(gè)曲面上分別劃分網(wǎng)格，再對(duì)多個(gè)網(wǎng)格進(jìn)行縫合，最后進(jìn)行調(diào)整和優(yōu)化.由于一條曲線分屬兩個(gè)曲面，難以共同調(diào)整優(yōu)化.流暢性與均勻性都難以保證，曲面交界處往往存在明顯彎折.

圖6是一個(gè)船形曲面的局部.由圖6（a）可見，由于模型形式復(fù)雜，建筑師建模時(shí)采用了兩個(gè)曲面組合來(lái)表達(dá).如圖6（a）的曲面結(jié)構(gòu)線所示，上部曲面是裁剪曲面，且一端存在急劇收縮的現(xiàn)象，這都給傳統(tǒng)網(wǎng)格劃分方法造成了很大困難.

對(duì)于該算例，采用1.1節(jié)中所述的方法，先分別將兩個(gè)曲面離散為約150 000、210 000個(gè)小三角形面片，再對(duì)兩個(gè)網(wǎng)格進(jìn)行縫合，最終形成共360k個(gè)面片.

實(shí)驗(yàn)證明本算法可以處理裁剪曲面、多重曲面等形式復(fù)雜的模型.如圖6（b）所示，生成的網(wǎng)格均勻性較好，桿長(zhǎng)均值為2.313 m，桿長(zhǎng)方差僅為0.044 m2.但由于模型變化較大，為保證上下網(wǎng)格密度相同，則網(wǎng)格流線不可避免存在發(fā)散和收縮現(xiàn)象，個(gè)別內(nèi)部節(jié)點(diǎn)所連桿件數(shù)量不為6，優(yōu)化后的網(wǎng)格整體流暢性尚可.

作者對(duì)上下兩個(gè)曲面分別采用映射法劃分網(wǎng)格，如圖6（c）所示，下部曲面是完整曲面，映射法效果較好；而上部曲面由于是裁剪曲面，且一端急劇收縮，映射法僅保證了拓?fù)淞鲿?，?shí)際空間效果較差.由圖6（c）可見，映射法存在嚴(yán)重的映射變形問題.對(duì)上下兩曲面分別應(yīng)用1.7節(jié)的均勻化后，如圖6（d）所示，上部曲面的映射變形問題得到一定改善.但整體仍存在下部桿件過于密集，上部桿件過長(zhǎng)的問題.而且網(wǎng)格流線在兩曲面分界線處存在明顯的彎折現(xiàn)象，而流線分屬兩個(gè)曲面，難以調(diào)整.而圖6（b）所示的本算法網(wǎng)格并沒有受到曲面分界線的影響.

作者根據(jù)標(biāo)高設(shè)置了分段密度控制函數(shù)，上部疏下部密，并得到了圖6（e）和（f）的最終結(jié)果，網(wǎng)格流暢，且滿足密度分布，僅存在少量奇異點(diǎn).實(shí)驗(yàn)表明本算法可以根據(jù)用戶的美學(xué)需求進(jìn)行變密度網(wǎng)格生成.

3 結(jié) 論

針對(duì)復(fù)雜曲面，本文提出了一種以密度控制為目標(biāo)的網(wǎng)格劃分方法.首先，對(duì)復(fù)雜曲面離散并縫合，一體化為由大量三角面片組成的離散曲面，可消除裁剪邊界、孔洞、多曲面拼接、閉合等負(fù)面影響.其次，采用改進(jìn)的誤差擴(kuò)散算法進(jìn)行初始點(diǎn)的分布，該算法布點(diǎn)結(jié)果雖不夠均勻，但滿足密度分布，為之后的步驟提供了可靠的初值.然后，采用基于空間距離的粒子動(dòng)力松弛算法，對(duì)點(diǎn)云進(jìn)行初步均勻化，應(yīng)用基于曲面距離的k均值算法對(duì)點(diǎn)云進(jìn)行再次均勻化，得到曲面上滿足密度要求的均勻點(diǎn)陣.接著求離散曲面Voronoi圖，由此得到曲面Delaunay圖.之后，進(jìn)行拓?fù)鋬?yōu)化，提高規(guī)整性.最后，采用彈簧質(zhì)點(diǎn)松弛算法對(duì)該三角網(wǎng)格進(jìn)行光順優(yōu)化，得到均勻流暢的最終網(wǎng)格.

算例表明，本文算法可以處理裁剪、開洞、變化劇烈、環(huán)面、多曲面拼接等復(fù)雜情況，適應(yīng)性好.最終形成的網(wǎng)格能滿足密度要求，但網(wǎng)格流線可能存在發(fā)散和收縮情況，存在內(nèi)部節(jié)點(diǎn)連有5根或7根桿件的現(xiàn)象.

奇異節(jié)點(diǎn)不可避免，本文算法的缺陷在于，奇異節(jié)點(diǎn)的位置并不能控制，本文采用的拓?fù)鋬?yōu)化算法并無(wú)全局優(yōu)化能力，可能需要在形成網(wǎng)格后交互地修改拓?fù)洌娈慄c(diǎn)的負(fù)面影響.對(duì)此仍需要進(jìn)行更多的研究探索，在形成網(wǎng)格前就交互確定奇異點(diǎn)，或在算法中全局地優(yōu)化奇異點(diǎn)的數(shù)量與位置，以獲得更規(guī)整的網(wǎng)格.

參考文獻(xiàn)

[1] PIEGLL L，TILLER W. The NURBS Book[M] .2nd ed. Berlin Heidelberg： Springer-Verlag，1997.

[2] 王磊，楊彬，張其林. 非均勻有理B樣條曲面形狀優(yōu)化方法[J]. 湖南大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2012，39（7）：14—19.

WANG L， YANG B，ZHANG Q L. Shape optimization of non-uniform rational B-spline surface[J].Journal of Hunan University（Natural Sciences），2012，39（7）：14—19. （In Chinese）

[3] SEDERBERG T W， ZHENG J， BAKENOV A， et al. T-splines and T-NURCCs[J]. ACM Transactions on Graphics，2003，22（3）： 477 —484.

[4] OWEN S. A survey of unstructured mesh generation[C]// International Meshing Roundtable. Dearborn， USA： IMR， 1998： 239—267.

[5] LHNER R. Progress in grid generation via the advancing front technique[J]. Engineering with Computers，1996，12（3）：186—210.

[6] BOROUCHAKI H，HECHT F，SALTEL E，et al.Reasonably efficient Delaunay based mesh generator in 3 dimensions[C]// International Meshing Roundtable. South Lake Tahoe， USA： IMR， 1999： 3—14.

[7] COOK W A，OAKES W R. Mapping method for generating three-dimensional meshes： past and present[C]// International Computer Engineering Conference.San Diego，USA：ASME，1982.

[8] 熊英，胡于進(jìn)，趙建軍. 基于映射法和Delaunay方法的曲面三角網(wǎng)格劃分算法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)， 2002， 14（1）： 56—60.

XIONG Y， HU Y J， ZHAO J J. An algorithm of surface triangulation based on mapping and Delaunay method[J]. Journal of Computer-Aided Design & Computer Graphics，2002，14（1）： 56—60.（In Chinese）

[9] 江存，高博青. 基于自定義單元法的自由曲面網(wǎng)格劃分研究[J]. 建筑結(jié)構(gòu)， 2015， 45（5）： 44—48.

JIANG C，GAO B Q. Research on free-form surface meshing based on self-defined element method[J]. Building Structure， 2015， 45（5）： 44—48. （In Chinese）

[10] SU L， ZHU S， XIAO N， et al. An automatic grid generation approach over free-form surface for architectural design[J]. Journal of Central South University， 2014， 21（6）： 2444—2453.

[11] 危大結(jié)，舒贛平. 自由曲面網(wǎng)格的劃分與優(yōu)化方法[J]. 建筑結(jié)構(gòu)， 2013， 43（19）： 48—53.

WEI D J， SHU G P. Mesh generation and optimization method for free-form surface grid[J]. Building Structure， 2013， 43（19）： 48—53. （In Chinese）

[12] 潘煒，吳慧，李鐵瑞，等.基于曲面展開的自由曲面網(wǎng)格劃分[J]. 浙江大學(xué)學(xué)報(bào)（工學(xué)版）， 2016， 50（10）： 1973—1979.

PAN W， WU H， LI T R，et al. Grid generation on free-form surface based on surface flattening[J]. Journal of Zhejiang University（Engineering Science），2016，50（10）：1973—1979.（In Chinese）

[13] SCHALL O， SAMOZINO M， FALCIDIENO B， et al. Surface from scattered points： a brief survey of recent developments[C]// Proccedings of the first international workshop towards Semantic Virtual Environments. Villars， Switzerland： SVE， 2005： 138—147.

[14] FLOYD R W， STEINBERG L. Adaptive algorithm for spatial greyscale[C]// Proceeding SID. New York， USA： SID， 1976：75—77.

[15] ULICHNEY R. Digital halftoning[M].Cambrige，MA：MIT Press， 1987：12—13.

[16] VELHO L， GOMES J D M. Digital halftoning with space filling curves[J]. ACM SIGGRAPH Computer Graphics， 1991， 25（4）：81—90.

[17] FAN Z. Set of easily implementable coefficients in error diffusion with reduced worm artifacts[C]// Proceeding SPIE. San Jose， USA： SPIE，1996：222—225.

[18] OSTROMOUKHOV V. A simple and efficient error-diffusion algorithm[C]// Proceeding SIGGRAPH. Los Angeles， USA： ACM， 2001： 567—572.

[19] BRONSON J R， LEVINE J A， WHITAKER R T. Particle systems for adaptive， isotropic meshing of CAD models[J]. Engineering with Computers， 2012， 28（4）： 331—344.

[20] LLOYD S. Least squares quantization in PCM[J]. IEEE Transactions on Information Theory， 1982， 28（2）： 129—137.

[21] MACQUEEN J. Some METHODS for classification and analysis of multi variate observations[C]//Proceedings of Berkeley Symposium

on Mathematical Statistics and Probability. Oakland， USA： University of California Press， 1967：281—297.

[22] MACKAY D.Information theory，inference，and learning algorithms[M]. Cambridge， UK： Cambridge University Press，2003： 640.

[23] DU Q， FABER V， GUNZBURGER M. Centroidal Voronoi tessellations： applications and algorithms[J]. Siam Review， 1999， 41（4）： 637—676.

[24] 周炎濤，吳正國(guó)，易興東. 基于網(wǎng)格帶有參考參數(shù)的擴(kuò)展聚類算法[J]. 湖南大學(xué)學(xué)報(bào)（自然科學(xué)版），2009，36（2）：48—52.

ZHOU Y T， WU Z G， YI X D. Extended grid-based clustering algorithm with referential parameters[J]. Journal of Hunan University（Natural Sciences），2009，36（2）：48—52.（In Chinese）

[25] FREY W H， FIELD D A. Mesh relaxation： a new technique for improving triangulations[J]. International Journal for Numerical Methods in Engineering， 1991， 31（6）： 1121—1133.

[26] 李基拓，陸國(guó)棟. 基于邊折疊和質(zhì)點(diǎn)-彈簧模型的網(wǎng)格簡(jiǎn)化優(yōu)化算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2006，18（3）：426—432.

LI J T， LU G D. Mesh simplification and optimization with edge collapse and mass-spring model[J]. Journal of Computer-Aided Design & Computer Graphics，2006，18（3）：426—432.（In Chinese）