張 偉

（中國計量學(xué)院機電工程學(xué)院，浙江 杭州 310018）

逼近散亂點云數(shù)據(jù)的三角形網(wǎng)格精確剖分

張 偉

（中國計量學(xué)院機電工程學(xué)院，浙江 杭州 310018）

基于自組織特征映射神經(jīng)網(wǎng)絡(luò)構(gòu)建的三角形網(wǎng)格模型可以實現(xiàn)測量點云壓縮后的Delaunay三角逼近剖分，但該模型存在逼近誤差和邊緣誤差。為減小三角形網(wǎng)格的逼近誤差和邊緣誤差，構(gòu)建了精確逼近的三角形網(wǎng)格模型。首先采用整個測量點云，對三角形網(wǎng)格模型中的所有神經(jīng)元進行整體訓(xùn)練；然后對三角形網(wǎng)格中的網(wǎng)格神經(jīng)元的位置權(quán)重，沿網(wǎng)格頂點法矢方向進行修正；最后采用測量點云中的邊界點集，對三角形網(wǎng)格模型中的網(wǎng)格邊界神經(jīng)元進行訓(xùn)練。算例表明，應(yīng)用該模型，可以有效減小三角形網(wǎng)格的邊緣誤差，三角形網(wǎng)格逼近散亂點云的逼近精度得到大幅提高并覆蓋散亂點云整體分布范圍。

逆向工程；三角形網(wǎng)格；神經(jīng)網(wǎng)絡(luò)；逼近誤差；邊緣誤差；散亂點云

逆向工程是從一個已有的物理模型產(chǎn)生出相應(yīng)CAD模型或?qū)嶓w模型的過程。在離散數(shù)據(jù)的逆向工程中，常采用小三角平面片（三角形網(wǎng)格）或三角域上的Bezier曲面片進行產(chǎn)品外形擬合。三角曲面能夠適應(yīng)復(fù)雜的形狀及不規(guī)則的邊界，因而在對復(fù)雜型面的曲面構(gòu)造過程中以及在逆向工程中，具有很大的應(yīng)用潛力。在面向快速原型制造的應(yīng)用中，只要對給定的離散數(shù)據(jù)點進行三角剖分就能得到STL格式的零件幾何表示。

近年來，以掃描測量為基礎(chǔ)的“點云”數(shù)據(jù)采集的發(fā)展非常迅速，由此生成的三角形網(wǎng)格可多達幾萬甚至上百萬個，這樣不僅占用了大量的存儲空間，也不利于網(wǎng)格的后續(xù)處理，尤其是在快速原型制造領(lǐng)域的應(yīng)用更是存在著很多不便之處。如果依然沿用傳統(tǒng)的三角片逼近造型方法，將遇到難以克服的困難[1]。

國內(nèi)外學(xué)者對模型簡化的研究已取得了一系列成果。Schroeder和Zarge[2]提出了基于頂點刪除的網(wǎng)格刪減方法；Hamann[3]通過曲率計算移去三角形，從而簡化模型；Hoppe和Derose[4]提出了一種整體的網(wǎng)格優(yōu)化過程，此后又采用漸進網(wǎng)格[5]的表示方法來存儲和傳輸三角網(wǎng)格；Eck的 Rossignac[6]利用小波技術(shù)進行模型簡化；Dehamer和Zyda[7]應(yīng)用了自適應(yīng)剖分方法進行網(wǎng)格簡化；Garland和Heckbert[8]應(yīng)用了邊折疊操作方法進行網(wǎng)格簡化；Hussain[9]提出了一種高效的特征保持簡化算法；Chong等[10]結(jié)合遺傳算法對大規(guī)模網(wǎng)格模型進行簡化和優(yōu)化。國內(nèi)在這方面的研究起步較晚，但也取得了許多研究成果[11-17]。張偉等[18]進行了基于自組織特征映射(self-organizing feature map, SOFM)神經(jīng)網(wǎng)絡(luò)[19]的三維散亂測量點云的拓撲三角形網(wǎng)格自組織壓縮重建的探索。該文所建三角形網(wǎng)格模型可以實現(xiàn)測量點云壓縮后的Delaunay三角逼近剖分。Zhang等[20]在文獻[18]的基礎(chǔ)上，將單視密集散亂數(shù)據(jù)壓縮、拓撲三角形網(wǎng)格逼近剖分和網(wǎng)格頂點法矢量生成統(tǒng)一在一個進程中。文獻[18]、[20]不足之處是三角形網(wǎng)格模型在效率與精度層面與神經(jīng)網(wǎng)絡(luò)規(guī)模關(guān)聯(lián)程度較高，提高神經(jīng)網(wǎng)絡(luò)規(guī)模，可以提高三角形網(wǎng)格的逼近精度，但同時也使神經(jīng)網(wǎng)絡(luò)的訓(xùn)練時間延長。

現(xiàn)有的三角形網(wǎng)格簡化模型構(gòu)建方法在效率與精度層面有待提高。本文將在文獻[20]的基礎(chǔ)上研究構(gòu)建高效精確逼近散亂點云數(shù)據(jù)的簡化三角形網(wǎng)格模型及其訓(xùn)練模式。

1 精確逼近的三角形網(wǎng)格模型

1.1 三角形網(wǎng)格自組織壓縮重建

用于散亂點云數(shù)據(jù)壓縮的 SOFM神經(jīng)網(wǎng)絡(luò)二維陣列模型，如圖1所示。圖中網(wǎng)絡(luò)的輸入矢量就是復(fù)雜曲面上的測點矢量Pj(x, y, z)，網(wǎng)絡(luò)輸出層具有m×n個神經(jīng)元結(jié)點，即該三角形網(wǎng)格重建模型具有m×n個神經(jīng)元。網(wǎng)絡(luò)神經(jīng)元對曲面空間測量樣本點的學(xué)習(xí)和訓(xùn)練來模擬曲面上的點與點之間的內(nèi)在關(guān)系，結(jié)點連接權(quán)重矢量集重構(gòu)曲面樣本點的內(nèi)在拓撲關(guān)系及實現(xiàn)對測點集的工程近似化，實現(xiàn)曲面三維散亂點云的自組織壓縮，構(gòu)成三角剖分。

圖1 數(shù)據(jù)壓縮二維陣列網(wǎng)絡(luò)模型

圖2 六角形陣列鄰區(qū)Nc

圖1所示神經(jīng)網(wǎng)絡(luò)的權(quán)重矢量調(diào)節(jié)算法如式(1)所示。

式中，Pj為測點矢量；Wi(t)為神經(jīng)元連接權(quán)重矢量； α( t)為修正率；Nc為以結(jié)點 c為中心的輸出結(jié)點集合，如圖2所示，圖中c為與輸入矢量Pj匹配最佳的輸出結(jié)點； β（ di）是修正率加權(quán)函數(shù)，其中 di為鄰區(qū)集合Nc中結(jié)點i到c之間的距離。

經(jīng)過訓(xùn)練，權(quán)重矢量Wi收斂到所代表的感受野（即測量點集中與權(quán)重矢量Wi的歐氏距離最近的點集）的平均值，其反映了測量點集的統(tǒng)計特性。三角網(wǎng)格剖分可按如下步驟進行：①圖2中tc時刻的六角形陣列鄰區(qū)Nc集合中的結(jié)點c依次與Nc中6個相鄰結(jié)點相連便形成三角網(wǎng)格剖分；②對輸出層上的每一結(jié)點都如此處理；③神經(jīng)元結(jié)點對應(yīng)的權(quán)重矢量Wi在三維空間構(gòu)成測量點集壓縮后的Delaunay三角網(wǎng)格逼近剖分[18]。

1.2 三角形網(wǎng)格頂點法向矢量

設(shè)欲重構(gòu)的曲面可以用參數(shù)方程式(2)表示。

式中，P表示曲面的笛卡兒坐標(x, y, z), Q表示曲面參數(shù)(u, v)。對于曲面采樣測點矢量集，曲面參數(shù)可設(shè)為(x, y)。

曲面參數(shù)方程(2)是一復(fù)雜的非線性變換，要用一個函數(shù)擬合所測得的數(shù)字化點群數(shù)據(jù)是困難的。為此可將式(2)在Qs處泰勒展開。

式中，Ps，As和Qs可用擴展SOFM(ESOFM)[20]神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)而得。此式表示所構(gòu)造的神經(jīng)網(wǎng)絡(luò)權(quán)重矢量Ps處的微切平面方程。依據(jù)此式，微切平面逼近式(2)表示的曲面，在Qs局域Fs中可達到很高的精度。Fs由式(4)定義。

式中，s是激活神經(jīng)元；Fs是神經(jīng)元s對應(yīng)的輸入空間，即感受野；Ω是輸入空間；Qr是神經(jīng)元r的外部輸入權(quán)重，即分類核心。

設(shè)s為自組織特征映射神經(jīng)網(wǎng)絡(luò)陣列中的任一神經(jīng)元，SOFM自組織學(xué)習(xí)算法可使 s與 Qs形成空間有序特征映射。通過SOFM算法擴展同時使s與(Ps，As)建立映射關(guān)系。通過ESOFM神經(jīng)網(wǎng)絡(luò)訓(xùn)練，學(xué)習(xí)Ps、As及Qs，以滿足式(3)。ESOFM神經(jīng)網(wǎng)絡(luò)的權(quán)重矢量Ps、As及Qs的訓(xùn)練采用文獻[20]的調(diào)節(jié)算法。

按上述建立的ESOFM神經(jīng)網(wǎng)絡(luò)中，每一個神經(jīng)元s有一個感受野Fs以及外部輸入權(quán)重Qs，那么該神經(jīng)元的輸出就是Ps。當(dāng)輸入Q偏離Qs時，則神經(jīng)元的輸出由式(3)得到。這樣ESOFM神經(jīng)網(wǎng)絡(luò)將整個數(shù)字化點群數(shù)據(jù)分成許多子區(qū)域，每個子區(qū)域用一個微切平面逼近，每組權(quán)重各自對相應(yīng)的子區(qū)域負責(zé)。式(3)中的 As可用于計算相應(yīng)子區(qū)域權(quán)重矢量 Ps（即三角形網(wǎng)格頂點）處的法向矢量ns，其計算公式如下。

式中，As由ESOFM神經(jīng)網(wǎng)絡(luò)訓(xùn)練后直接得到。

1.3 三角形網(wǎng)格模型的改進訓(xùn)練模式

文獻[20]按照 1.1～1.2節(jié)所述模型及其訓(xùn)練算法，采用整個測量的散亂點云，對三角形網(wǎng)格模型中的神經(jīng)元陣列進行若干循環(huán)的整體訓(xùn)練，實現(xiàn)將單視密集散亂數(shù)據(jù)壓縮、拓撲三角形網(wǎng)格逼近剖分和網(wǎng)格頂點法向矢量生成統(tǒng)一在一個進程中。為減小三角形網(wǎng)格的逼近誤差和邊緣誤差，本文擬按照以下3步訓(xùn)練模式，依次進行三角形網(wǎng)格模型的訓(xùn)練，3步訓(xùn)練的結(jié)果之間具有繼承性（后繼承前）。

1.3.1 網(wǎng)格神經(jīng)元整體訓(xùn)練的改進

按照 1.1～1.2節(jié)所述模型及其訓(xùn)練算法，采用整個測量的散亂點云，對模型中的神經(jīng)元陣列進行若干循環(huán)的整體訓(xùn)練。此步訓(xùn)練與文獻[20]采用的訓(xùn)練方式不同之處在于此步的訓(xùn)練調(diào)高了與測量點云中的邊界點集匹配的神經(jīng)元的訓(xùn)練修正率 α( t)，以加大三角形網(wǎng)格邊界神經(jīng)元及其鄰區(qū)的神經(jīng)元對應(yīng)的位置權(quán)重矢量向測量點云邊界趨近的強度，如此生成的三角形網(wǎng)格Ⅰ可以減小邊緣誤差。

1.3.2 網(wǎng)格神經(jīng)元位置權(quán)重矢量的修正

設(shè)三角形網(wǎng)格頂點神經(jīng)元 s，網(wǎng)格頂點位置權(quán)重矢量為Ps，網(wǎng)格頂點法向矢量為ns，網(wǎng)格頂點神經(jīng)元s在位置權(quán)重矢量Ps處的空間感受野為Fs。則本文提出的網(wǎng)格神經(jīng)元s的位置權(quán)重矢量Ps修正如圖3所示，修正步驟如下：

（1）在位置權(quán)重矢量Ps處的空間感受野Fs中，求出與Ps最近的點q；

（2）然后過點q作法向矢量ns（其經(jīng)過Ps點）的垂直交線，垂足為′相對于Ps更加逼近被測曲面；

（3）按式(7)修正位置權(quán)重矢量Ps。

圖3 網(wǎng)格神經(jīng)元位置權(quán)重矢量的修正

按照上述位置權(quán)重矢量修正而產(chǎn)生的三角形網(wǎng)格Ⅱ較三角形網(wǎng)格Ⅰ更加逼近采樣曲面。

1.3.3 網(wǎng)格邊界神經(jīng)元的微調(diào)訓(xùn)練

為進一步減小三角形網(wǎng)格邊緣誤差，按以下訓(xùn)練方式訓(xùn)練網(wǎng)格邊界神經(jīng)元。

（1）采用點云數(shù)據(jù)中的邊界點集，只對三角形網(wǎng)格模型中的網(wǎng)格邊界神經(jīng)元進行訓(xùn)練，微調(diào)三角形網(wǎng)格邊界神經(jīng)元對應(yīng)的位置權(quán)重矢量向測量點云邊界趨近。網(wǎng)格內(nèi)部神經(jīng)元不參與訓(xùn)練。三角形網(wǎng)格邊界神經(jīng)元采用“0”六角形鄰區(qū) Nc進行訓(xùn)練，其等價為一維訓(xùn)練方式，可有效使三角形網(wǎng)格邊界神經(jīng)元對應(yīng)的位置權(quán)重矢量趨近邊界點集。

（2）采用邊界點集中的角點點集，只對與邊界角點匹配最佳的網(wǎng)格邊界神經(jīng)元進行訓(xùn)練，微調(diào)與邊界角點匹配最佳的三角形網(wǎng)格邊界神經(jīng)元對應(yīng)的位置權(quán)重矢量向測量點云邊界角點趨近。網(wǎng)格其他神經(jīng)元不參與訓(xùn)練。與邊界角點匹配最佳的三角形網(wǎng)格邊界神經(jīng)元采用“0”六角形鄰區(qū)Nc進行訓(xùn)練，其等價為一維訓(xùn)練方式，可有效使與邊界角點匹配最佳的三角形網(wǎng)格邊界神經(jīng)元對應(yīng)的位置權(quán)重矢量趨近邊界角點點集。

如此生成的三角形網(wǎng)格Ⅲ可以進一步減小邊緣誤差。

2 三角形網(wǎng)格逼近精度的仿真實驗

分別以球面點集和復(fù)雜曲面點集為對象，對所構(gòu)建的三角形網(wǎng)格模型在個人計算機上進行仿真實驗。

2.1 采用球面點集的仿真實驗

仿真實驗中，三角形網(wǎng)格模型中的神經(jīng)元陣列包含10×12個神經(jīng)元，采用式(8)表示的球面的隨機采樣點集進行訓(xùn)練，仿真實驗結(jié)果如圖4所示。

圖4(a)表示采樣點集，球面采樣的參數(shù)范圍為：u=0～π/4，v=0～π/3，R=10。采樣點集包含3524個點，其中邊界點集包含324個點，角點點集包含4個點；圖4(b)表示應(yīng)用文獻[20]訓(xùn)練模式的仿真實驗結(jié)果，圖中繪出了所構(gòu)建的三角形網(wǎng)格的頂點位置、頂點處的法向矢量以及采樣邊界點集，從圖中可以看到存在較為明顯的三角形網(wǎng)格邊緣誤差；圖4(c)表示將圖4(b)所示的三角形網(wǎng)格神經(jīng)元位置權(quán)重矢量沿法向矢量方向修正的結(jié)果；圖4(d)表示應(yīng)用本文改進的整體訓(xùn)練模式的仿真實驗結(jié)果，圖中繪出了所構(gòu)建的三角形網(wǎng)格的頂點位置及頂點處的法向矢量，從圖中可以看到三角形網(wǎng)格邊緣誤差大幅減小；圖4(e)表示將圖4(d)所示的三角形網(wǎng)格神經(jīng)元位置權(quán)重矢量沿法向矢量方向修正的結(jié)果；圖4(f)表示應(yīng)用本文提出的網(wǎng)格邊界神經(jīng)元的微調(diào)訓(xùn)練模式對圖4(e)所示的三角形網(wǎng)格Ⅱ的網(wǎng)格邊界神經(jīng)元進行訓(xùn)練，所生成的三角形網(wǎng)格Ⅲ。

圖4 仿真實例1

仿真實驗中生成的三角形網(wǎng)格逼近散亂數(shù)據(jù)的逼近誤差與邊緣誤差如表1所示。表1中2～6列分別表示圖4(b)～(f)所對應(yīng)的仿真實驗精度。

表1 仿真實例1的實驗精度(mm)

表1中三角形網(wǎng)格的邊緣誤差表示三角形網(wǎng)格邊界頂點與曲面邊界相離的程度。本文按以下步驟計算度量：①搜尋與網(wǎng)格邊界頂點距離最近的邊界點集中的點；②計算兩者的歐氏距離；③求取所有網(wǎng)格邊界頂點與邊界點集相應(yīng)的歐氏距離的平均值。這是一種相對評估邊緣誤差的方式，邊界點集的采樣密度對按此方式計算的邊緣誤差量值有較大影響。

表1中三角形網(wǎng)格的逼近誤差表示三角形網(wǎng)格頂點集偏離曲面的程度，具體可采用逼近誤差Ⅰ和逼近誤差Ⅱ進行度量。

逼近誤差Ⅰ按式(9)進行計算度量。

式中，m×n表示神經(jīng)元陣列中分布的神經(jīng)元數(shù)目；R表示球面半徑；Ps表示三角形網(wǎng)格頂點的位置權(quán)重矢量，即三角形網(wǎng)格頂點的空間位置。

逼近誤差Ⅱ表示沿網(wǎng)格頂點法矢方向度量網(wǎng)格頂點偏離曲面的程度，其按以下步驟計算度量：①過網(wǎng)格頂點并沿網(wǎng)格頂點法向矢量 ns方向，相交于曲面得交點p；②計算網(wǎng)格頂點與相應(yīng)交點p之間的歐氏距離；③求取所有網(wǎng)格頂點與相應(yīng)交點之間的歐氏距離的平均值。

采用不同神經(jīng)網(wǎng)絡(luò)規(guī)模進行仿真實驗，各種訓(xùn)練模式的仿真實驗精度對比，如表2所示。

表2 仿真實驗的逼近誤差I(lǐng)(mm)

2.2 采用非規(guī)則曲面點集的仿真實驗

仿真實驗中，三角形網(wǎng)格模型中的神經(jīng)元陣列包含8×8個神經(jīng)元，采用式(10)表達的非規(guī)則曲面的隨機采樣點集進行訓(xùn)練，仿真實驗結(jié)果，如圖5所示。

圖5(a)表示采樣點集，非規(guī)則曲面采樣的參數(shù)范圍為：x=π/2～5π/4，y=π/7～5π/6。采樣點集包含2524個點，其中邊界點集包含324個點，角點點集包含4個點；圖5(b)表示應(yīng)用文獻[20]訓(xùn)練模式的仿真實驗結(jié)果，圖中繪出了所構(gòu)建的三角形網(wǎng)格的頂點位置、頂點處的法向矢量以及采樣邊界點集；圖5(c)表示將圖5(b)所示的三角形網(wǎng)格神經(jīng)元位置權(quán)重矢量沿法向矢量方向修正的結(jié)果；圖5(d)表示應(yīng)用本文改進的整體訓(xùn)練模式的仿真實驗結(jié)果，圖中繪出了所構(gòu)建的三角形網(wǎng)格的頂點位置及頂點處的法矢；圖5(e)表示將圖5(d)所示的三角形網(wǎng)格神經(jīng)元位置權(quán)重矢量沿法矢方向修正的結(jié)果；圖5(f)表示應(yīng)用本文提出的網(wǎng)格邊界神經(jīng)元的微調(diào)訓(xùn)練模式對圖5(e)所示的三角形網(wǎng)格Ⅱ的網(wǎng)格邊界神經(jīng)元進行訓(xùn)練，所生成的三角形網(wǎng)格Ⅲ。

仿真實驗中生成的三角形網(wǎng)格逼近散亂數(shù)據(jù)的逼近誤差Ⅱ、邊緣誤差及神經(jīng)網(wǎng)絡(luò)訓(xùn)練時間如表3所示。表3中2～6列分別表示圖5(b)～(f)所對應(yīng)的仿真實驗結(jié)果。表3中的訓(xùn)練時間表示得到相應(yīng)三角形網(wǎng)格所需的訓(xùn)練時間總和。

圖5 仿真實例2

表3 仿真實例2的實驗精度(mm)

2.3 仿真實驗結(jié)果的分析

由表1和表3可知本文所構(gòu)建的三角形網(wǎng)格模型及其訓(xùn)練模式顯著減小了三角形網(wǎng)格的逼近誤差和邊緣誤差。

在采用二種點集的仿真實驗中，對網(wǎng)格頂點位置權(quán)重矢量Ps，采用沿網(wǎng)格頂點法向矢量方向修正的算法，可以使三角形網(wǎng)格更加逼近采樣曲面，大幅降低了三角形網(wǎng)格的逼近誤差。該算法對本文和文獻[20]構(gòu)建的三角形網(wǎng)格模型均適用。表1中逼近誤差Ⅰ與逼近誤差Ⅱ相差極其微小，這可以間接證明所求的三角形網(wǎng)格頂點處的法向矢量非常接近相應(yīng)交點 p處的曲面法向矢量，也表明了逼近誤差Ⅰ與逼近誤差Ⅱ在度量三角形網(wǎng)格逼近散亂數(shù)據(jù)點集的偏離程度方面是等同的。經(jīng)過運用本文提出的網(wǎng)格邊界神經(jīng)元的微調(diào)訓(xùn)練模式，三角形網(wǎng)格的邊緣誤差再次明顯減小，網(wǎng)格邊界神經(jīng)元逼近球面的逼近精度略有提高，結(jié)果使三角形網(wǎng)格頂點集逼近球面的平均逼近誤差進一步減小。表 2表明，提高神經(jīng)網(wǎng)絡(luò)規(guī)?？梢詼p小三角形網(wǎng)格的逼近誤差。相比較而言，在減小三角形網(wǎng)格的逼近誤差方面，采用本文構(gòu)建的三角形網(wǎng)格模型中的訓(xùn)練算法，要比采用提高神經(jīng)網(wǎng)絡(luò)規(guī)模的方法更加合理和更有成效。

3 結(jié) 束 語

仿真實驗表明本文構(gòu)建的三角形網(wǎng)格模型及其訓(xùn)練模式在應(yīng)用中呈現(xiàn)以下特性：①可以實現(xiàn)測量點云壓縮后的Delaunay三角逼近剖分；②顯著減小了三角形網(wǎng)格的邊緣誤差；③三角形網(wǎng)格逼近散亂點云的逼近誤差得到大幅降低；④三角形網(wǎng)格覆蓋點云整體分布范圍。所構(gòu)建的三角形網(wǎng)格，既可用于構(gòu)造散亂數(shù)據(jù)插值曲面的前置處理，也可用于快速原型STL格式的零件幾何表示。今后此研究主題的工作重心是關(guān)于復(fù)雜拓撲模型和大規(guī)模分布范圍的密集散亂數(shù)據(jù)的三角形網(wǎng)格高效精確重建，擬采取先分片三角形網(wǎng)格構(gòu)建，后整體融合訓(xùn)練重構(gòu)的思路。

[1] 王平江, 黃雪梅, 陳吉紅, 周 濟. 曲面激光密集測量三維數(shù)據(jù)的三角片逼近方法[J]. 工程圖學(xué)學(xué)報, 1998, 19(1): 17-27.

[2] Schroeder W J, Zarge J A. Decimation of triangle meshes [J]. Computer Graphics, 1992, 26(2): 65-70.

[3] Hamann B. A data reduction scheme for triangulated surfaces [J]. Computer Aided Geometric Design, 1994, 11(2): 197-214.

[4] Hoppe H, Derose T. Mesh optimization [J]. Computer Graphics, 1993, 27(1): 19-26.

[5] Hoppe H. Progressive meshes [J]. Computer Graphics, 1996, 30(2): 119-128.

[6] Eck M, Rossignac J R. Multi-resolution analysis of arbitrary meshes [J]. Computer Graphics, 1995, 29(2): 171-182.

[7] Dehamer J M, Zyda M J. Simplification of objects rendered by polygonal approximations [J] Computer Graphics, 1991, 25(2): 175-184.

[8] Garland M, Heckbert P S. Surface simplification using quadric error metrics [J]. Computer Graphics, 1997, 31(3): 209- 216.

[9] Hussain M. Efficient and feature-preserving triangular mesh decimation [J]. Journal of WSCG, 2004, 12(1): 167-174.

[10] Chong C S, Lee H P, Kumar A S. Genetic algorithms in mesh optimization for visualization and finite element models [J]. Journal of Neural Computing & Applications, 2006, 15(3): 366-372.

[11] 孫玉文, 王曉明, 郭東明. 反求工程中復(fù)雜多面體模型的網(wǎng)格簡化算法[J]. 中國機械工程, 2001, 12(8): 922-925.

[12] 蔣亞軍, 朱 理. 一種基于視覺特性的三角網(wǎng)格簡化算法[J]. 計算機仿真, 2006, 23(10): 178-180.

[13] 陳華鴻. 基于四邊形折疊的三角網(wǎng)格簡化算法[J].中山大學(xué)學(xué)報(自然科學(xué)版), 2008, 47(4): 19-24.

[14] 車翔玖, 劉 楊, 趙義武, 車 娜, 高占恒. 基于k-鄰域密度的離散點云簡化算法與實現(xiàn)[J]. 吉林大學(xué)學(xué)報(理學(xué)版), 2009, 47(5): 994-998.

[15] 閆 濤, 姜曉峰, 王 昱. 基于三角網(wǎng)格模型簡化的研究[J]. 計算機工程與科學(xué), 2010, 32(12): 69-72.

[16] 李 龍, 何明一. 基于特征保持和二次誤差測度的網(wǎng)格簡化[J]. 西北大學(xué)學(xué)報(自然科學(xué)版), 2010, 40(3): 419-422.

[17] 張 果, 劉旭敏. 一種基于八叉剖分的近似曲率的邊折疊簡化算法[J]. 計算機應(yīng)用研究, 2010, 27(5): 1955-1958.

[18] 張 偉, 姜獻峰, 陳麗能, 馬亞良. 基于神經(jīng)網(wǎng)絡(luò)的三角形網(wǎng)格智能重建[J]. 工程圖學(xué)學(xué)報, 2004, 25(1): 71-75.

[19] Kohonen T. The self-organizing map [J]. Proceeding of IEEE, 1990, 78(9): 1464-1479.

[20] Zhang Wei, Jiang Xianfeng, Chen Lineng, Ma Yaliang. Mesh generation from dense 3D scattered data using neural network [J]. CADDM, 2004, 14(1): 30-35.

Reconstruction of Triangle Mesh for Unorganized Point Cloud Data with High Approximation Precision

Zhang Wei
(College of Mechanical and Electronic Engineering, China Jiliang University, Hangzhou Zhejiang 310018, China)

An approach based on the self-organizing feature map (SOFM) neural network has been developed to reconstruct Delaunay triangle mesh for the unorganized measured point cloud. However the approach suffers from approximation and boundary problems. A triangle mesh model with high approximation precision is proposed in order to reduce the approximation error and boundary error. First all the neurons of the mesh model are trained directly over the unorganized point cloud. Next the neuron location weights of the mesh model are adjusted along the normal vectors of the mesh vertices. Last only the boundary neurons of the mesh model undergo training by the boundary points of the measured point cloud. As a result of applying the proposed mesh model, the boundary error is greatly reduced and the mesh is drawn toward the sampled object with higher precision comparing with the original SOFM training algorithm. The feasibility of the developed mesh model is demonstrated on two examples.

reverse engineering; triangle mesh; neural network; approximation error; boundary error; unorganized point cloud

TP 391

A

2095-302X (2014)02-0188-07

2013-05-13；定稿日期：2013-06-17

浙江省自然科學(xué)基金資助項目（Y1091012）；國家質(zhì)檢總局科技計劃資助項目（2006QK65）

張 偉（1964-），男，浙江金華人，副教授，博士。主要研究方向為CAD/CAM/RE、神經(jīng)網(wǎng)絡(luò)技術(shù)與應(yīng)用等。E-mail：zhangwei@cjlu.edu.cn