(華僑大學(xué)機(jī)電及自動化學(xué)院，福建 廈門361021）

鞋楦作為鞋的基準(zhǔn)，其設(shè)計(jì)制作過程是制鞋的關(guān)鍵工序之一。隨著信息技術(shù)的發(fā)展，將數(shù)字化技術(shù)應(yīng)用到鞋業(yè)生產(chǎn)中，能夠有效縮短制鞋周期，加快產(chǎn)品更新?lián)Q代的周期，提高企業(yè)的市場競爭力。筆者采用自主研制開發(fā)的三維楦型激光掃描儀獲得鞋楦的三維表面點(diǎn)云數(shù)據(jù)，基于有符號距離場表面重構(gòu)方法構(gòu)造鞋楦曲面網(wǎng)格模型，實(shí)現(xiàn)鞋楦的數(shù)字化設(shè)計(jì)，為個性化鞋楦快速定制奠定基礎(chǔ)。

1 鞋楦模型重構(gòu)

常用的曲面重構(gòu)方法主要有Delaunay三角剖分的方法、切片法、徑向基函數(shù)法、水平集法和有向距離場隱函數(shù)法等。筆者采用基于有向距離場的三角網(wǎng)格曲面重構(gòu)方法，其原理示意圖如圖1所示[1-2]?？臻g任意一點(diǎn)到待求曲面的距離與該點(diǎn)在曲面上最近點(diǎn)的法矢方向有關(guān)，如果該點(diǎn)和其對應(yīng)點(diǎn)的法矢方向一致，則設(shè)該點(diǎn)到曲面的距離為正，否則為負(fù)，則正距離與負(fù)距離場的界面——0等值面即為所求曲面。

點(diǎn)云三角網(wǎng)格模型重構(gòu)流程如圖2所示。

圖1 有向距離場示意圖

1．1 點(diǎn)云數(shù)據(jù)獲取

采用自主研制開發(fā)的鞋楦／腳型激光掃描測量系統(tǒng)進(jìn)行楦面數(shù)據(jù)采集，獲得鞋楦的點(diǎn)云數(shù)據(jù)。

1．2 頂點(diǎn)法矢計(jì)算

由于點(diǎn)云數(shù)據(jù)只包含點(diǎn)的坐標(biāo)信息，沒有任何的拓?fù)浣Y(jié)構(gòu)信息，所以每一點(diǎn)的微分幾何信息如曲率、法矢等，只能由其最臨近的一些點(diǎn)來決定。搜索點(diǎn)云中任一點(diǎn)的k個最臨近點(diǎn)的方法一般有柵格法、八叉樹法、近似最近鄰庫ANN方法以及k-d樹方法等[3]。筆者采用k-d樹方法來快速構(gòu)建點(diǎn)云中每一點(diǎn)的k-鄰近。

設(shè)點(diǎn)云中一點(diǎn)Pi的k-鄰域?yàn)镾= ｛Vj｜j=1，…，k｝，則該鄰域的形心坐標(biāo)（各點(diǎn)的平均坐標(biāo)）為：

圖2 點(diǎn)云三角網(wǎng)格模型重構(gòu)流程

其協(xié)方差矩陣為：

對協(xié)方差矩陣C進(jìn)行特征分解，計(jì)算其特征值以及與其對應(yīng)的特征向量，則其最小的特征值對應(yīng)的特征向量即為該點(diǎn)的法矢。這里需要注意的是，矩陣的特征分解對積累誤差比較敏感，在計(jì)算過程中，最好采用雙精度變量進(jìn)行計(jì)算，否則有可能導(dǎo)致計(jì)算失敗。

1．3 法矢一致化

在用上述方法得出各點(diǎn)的法矢后，并不能保證所有的法矢方向具有一致協(xié)調(diào)性，即保證所有的法矢朝向模型外側(cè)或內(nèi)側(cè)，因而必須依序逐一修正各個取樣點(diǎn)的法矢。然而，在2個不同但相當(dāng)接近的曲面上，用文獻(xiàn) [1]所進(jìn)行的法矢方向修正，卻可能在2平面上跳躍修正，如此一來，即有可能在法矢方向修正完畢后，仍然有法矢方向不一致性的問題產(chǎn)生，如圖3（a）所示。

圖3 法矢一致化調(diào)整

為了解決該問題，參照文獻(xiàn) [4]中的方法，采用一種新的成本函數(shù)來協(xié)助修正法矢的方向，這種新的成本函數(shù)對于在2個不同平面上但有相似方向的取樣點(diǎn)有較高的成本。該成本函數(shù)為：

式中，d為從點(diǎn)p指向點(diǎn)q的單位向量；np和nq分別為點(diǎn)p和點(diǎn)q的法矢；（·）表示2向量的內(nèi)積。對于相同平面上的2點(diǎn)p和q，其計(jì)算出的成本較低，如圖4（a）所示；對于不同平面上的2點(diǎn)p和q，其計(jì)算出的成本較高，如圖4（b）所示。圖3（a）數(shù)據(jù)采用新的成本函數(shù)進(jìn)行法矢調(diào)整的結(jié)果如圖3（b）所示。

圖4 新的成本函數(shù)示意圖

以點(diǎn)云模型中z坐標(biāo)值最大的測點(diǎn)作為法矢調(diào)整的種子點(diǎn)，調(diào)整其切平面法矢的方向，使之與矢量(0，0，1）的點(diǎn)積大于0，這將使調(diào)整后的法矢指向曲面外側(cè)。以成本函數(shù)作為權(quán)值遍歷由點(diǎn)云模型構(gòu)成的無向圖的最小生成樹，每遍歷1個頂點(diǎn)，若父頂點(diǎn)ni與子頂點(diǎn)nj滿足ni·nj＜0，則將nj反向。遍歷完畢，則點(diǎn)云的法矢也調(diào)整完畢，保證其整體的一致性。

1．4 有向距離計(jì)算

將切平面作為待重建曲面M的局部線性逼近，可以構(gòu)造空間一點(diǎn)p到M的有符號距離函數(shù)d（p）：

式中，xi為所有測點(diǎn)中與p最近的點(diǎn)；ni為相對應(yīng)的切平面法矢。

為了能夠?qū)崿F(xiàn)帶邊界曲面的重構(gòu)，對于密度為ρ，噪聲為δ的點(diǎn)集X，式（4）可改寫如下。

p點(diǎn)到最近切平面的投影為：

式中，L（z，X）表示z與測量點(diǎn)集X中最近點(diǎn)間的距離。

為了減少計(jì)算量，首先以點(diǎn)集X構(gòu)造k-d樹，在空間點(diǎn)p的一個指定半徑的球體范圍內(nèi)搜索其在X中的最近點(diǎn)，如果得到了最近點(diǎn)，則按改寫的式（4）計(jì)算其有符號距離；如果沒有得到其在X內(nèi)的對應(yīng)最近點(diǎn)，則直接給該點(diǎn)的有符號距離值賦值undefine，而不用再按改寫的式(4）計(jì)算。這樣不但減少了有符號距離計(jì)算量，也有利于下一步的三角網(wǎng)格生成。

1．5 三角網(wǎng)格曲面生成

在計(jì)算出空間任意一點(diǎn)的有符號距離之后，就要根據(jù)有符號距離場的分布情況進(jìn)行三角網(wǎng)格曲面重構(gòu)，其中常采用的三角形生成方法為Marching Cubes算法。該算法的基本原理是基于一個假設(shè)，即沿著立方體的棱邊，數(shù)據(jù)是連續(xù)線變化的，比如，如果等值面的值介于1條邊的2個頂點(diǎn)值的中間，則等值面必與該條邊相交于一點(diǎn)。根據(jù)該原理可以計(jì)算出與等值面相交的立方體。為確定體元中等值面的結(jié)構(gòu)，需要首先給出一個閾值以便求出等值面，然后對立方體的8個頂點(diǎn)進(jìn)行分類，以頂點(diǎn)位于等值面之內(nèi)還是位于等值面之外為分類規(guī)則；最后再根據(jù)頂點(diǎn)分類的結(jié)果確定等值面的結(jié)構(gòu)模式。其中分類頂點(diǎn)的規(guī)則是：①當(dāng)頂點(diǎn)的數(shù)據(jù)值大于等值面的值，則設(shè)定該頂點(diǎn)位于等值面內(nèi)部，記為 “0”；②當(dāng)頂點(diǎn)的數(shù)據(jù)值小于等值面的值，則設(shè)定該頂點(diǎn)位于等值面外部，記為 “1”。由于每個頂點(diǎn)有2種狀態(tài)，因此，8個頂點(diǎn)共有28=256種組合結(jié)果。由此可見，從立方體的256種狀態(tài)中求出等值面還是非常煩瑣的。在實(shí)踐中，可以根據(jù)互補(bǔ)對稱性和旋轉(zhuǎn)對稱性將這256種組合狀態(tài)化簡為15種。

除了生成用于組合成等直面的三角形，Marching Cubes算法還必須計(jì)算出用于3D顯示的表面法向量，得到三角形的法向量，就可以利用相應(yīng)的光照模型計(jì)算光照，最后生成具有真實(shí)感的3D圖形。等值面上的每一點(diǎn)，在沿面的切線方向的梯度分量為零，這說明每一點(diǎn)的梯度矢量方向就代表了點(diǎn)的法向量。直接計(jì)算三角形的法向量的運(yùn)算量很大，而且由于三角形的法向量在方向上有較大的隨機(jī)性，在三角形之間的鏈接處也會出現(xiàn)不連續(xù)性，使三維顯示圖形不能很好的表現(xiàn)目標(biāo)的結(jié)構(gòu)。因此，目前比較常見的法向量計(jì)算方法是通過三角形各頂點(diǎn)的法向量，生成哥羅德(Gouraud）模型來繪制三角形，進(jìn)而組合成等值面[2-4]。筆者采用中心差分的方法計(jì)算各立方體頂點(diǎn)處的梯度，然后通過棱邊的2個頂點(diǎn)的梯度線性差值求出三角形3個頂點(diǎn)的梯度，即為頂點(diǎn)法向量[2]。

2 應(yīng)用實(shí)例

通過VC6．0和OpenGL編程在微機(jī)平臺上實(shí)現(xiàn)筆者提出的方法，在CPU為2．26GHz、內(nèi)存為2．0GB的PC機(jī)上共用時9s。

圖5所示為鞋楦模型重構(gòu)結(jié)果，其中點(diǎn)云模型中共有63750個頂點(diǎn)(見圖5（a）），重構(gòu)后的三角網(wǎng)格模型中有50464個三角形(見圖5（b））。

圖5 鞋楦模型重構(gòu)結(jié)果

點(diǎn)云三角網(wǎng)格曲面重構(gòu)的主要參數(shù)有最臨近點(diǎn)個數(shù)k、噪聲影響系數(shù)、網(wǎng)格間距系數(shù)、是否考慮邊界的影響以及是否進(jìn)行法矢一致化處理等，如圖6所示。最臨近點(diǎn)個數(shù)k過大，難以重構(gòu)尖銳特征，過小則易受噪聲的影響，一般取8～15。噪聲影響系數(shù)是以點(diǎn)云密度(點(diǎn)云頂點(diǎn)間的平均距離）為基準(zhǔn)的比例系數(shù)，曲面中小于噪聲的細(xì)節(jié)是不能重建的。網(wǎng)格間距系數(shù)是以點(diǎn)云密度為基準(zhǔn)，定義網(wǎng)格格子間距的大小。

重構(gòu)參數(shù)對重構(gòu)結(jié)果的影響如圖7所示。圖7（b）中不考慮邊界的影響，因而構(gòu)造出的三角網(wǎng)格曲面明顯比點(diǎn)云模型多出一部分；圖7（c）和圖7（d）都考慮邊界的影響，但網(wǎng)格間距系數(shù)不一樣，所得重構(gòu)結(jié)果也不一樣。

圖6 點(diǎn)云模型重構(gòu)參數(shù)面板

3 結(jié) 論

給出了一種基于點(diǎn)云數(shù)據(jù)重構(gòu)鞋楦曲面模型的方法。利用改進(jìn)的成本函數(shù)實(shí)現(xiàn)點(diǎn)云模型法矢的一致化，采用k-d樹數(shù)據(jù)結(jié)構(gòu)加速搜索過程并減少有符號距離場的計(jì)算量。算法實(shí)例顯示，該方法是有效的，能夠應(yīng)用于鞋楦曲面逆向工程實(shí)踐。

圖7 重構(gòu)參數(shù)對重構(gòu)結(jié)果的影響

[1]Hoppe H，DeRo se T，Duchamp T，et al．Surface reconstruction from unorganized points [J]．Computer Graphics，1992，26（2）：71-78．

[2]周儒榮，張麗艷，蘇旭，等．海量散亂點(diǎn)的曲面重建算法研究 [J]．軟件學(xué)報(bào)，2001，12（2）：249-255．

[3]熊邦書，何明一，俞華璟．三維散亂數(shù)據(jù)的k個最近鄰域快速搜索算法 [J]．計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2004，16（7）：909-912．

[4]鐘武洋．利用局部點(diǎn)特性進(jìn)行有效率之表面重建 [D]．新竹：中原大學(xué)，2005．