基于點云的鞋楦模型三角網格曲面重構

(華僑大學機電及自動化學院，福建 廈門361021）

鞋楦作為鞋的基準，其設計制作過程是制鞋的關鍵工序之一。隨著信息技術的發展，將數字化技術應用到鞋業生產中，能夠有效縮短制鞋周期，加快產品更新換代的周期，提高企業的市場競爭力。筆者采用自主研制開發的三維楦型激光掃描儀獲得鞋楦的三維表面點云數據，基于有符號距離場表面重構方法構造鞋楦曲面網格模型，實現鞋楦的數字化設計，為個性化鞋楦快速定制奠定基礎。

1 鞋楦模型重構

常用的曲面重構方法主要有Delaunay三角剖分的方法、切片法、徑向基函數法、水平集法和有向距離場隱函數法等。筆者采用基于有向距離場的三角網格曲面重構方法，其原理示意圖如圖1所示[1-2]。空間任意一點到待求曲面的距離與該點在曲面上最近點的法矢方向有關，如果該點和其對應點的法矢方向一致，則設該點到曲面的距離為正，否則為負，則正距離與負距離場的界面——0等值面即為所求曲面。

點云三角網格模型重構流程如圖2所示。

圖1 有向距離場示意圖

1．1 點云數據獲取

采用自主研制開發的鞋楦／腳型激光掃描測量系統進行楦面數據采集，獲得鞋楦的點云數據。

1．2 頂點法矢計算

由于點云數據只包含點的坐標信息，沒有任何的拓撲結構信息，所以每一點的微分幾何信息如曲率、法矢等，只能由其最臨近的一些點來決定。搜索點云中任一點的k個最臨近點的方法一般有柵格法、八叉樹法、近似最近鄰庫ANN方法以及k-d樹方法等[3]。筆者采用k-d樹方法來快速構建點云中每一點的k-鄰近。

設點云中一點Pi的k-鄰域為S= ｛Vj｜j=1，…，k｝，則該鄰域的形心坐標（各點的平均坐標）為：

圖2 點云三角網格模型重構流程

其協方差矩陣為：

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

1．3 法矢一致化

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

圖3 法矢一致化調整

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

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

圖4 新的成本函數示意圖

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

1．4 有向距離計算

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

式中，xi為所有測點中與p最近的點；ni為相對應的切平面法矢。

為了能夠實現帶邊界曲面的重構，對于密度為ρ，噪聲為δ的點集X，式（4）可改寫如下。

p點到最近切平面的投影為：

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

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

1．5 三角網格曲面生成

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

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

2 應用實例

通過VC6．0和OpenGL編程在微機平臺上實現筆者提出的方法，在CPU為2．26GHz、內存為2．0GB的PC機上共用時9s。

圖5所示為鞋楦模型重構結果，其中點云模型中共有63750個頂點(見圖5（a）），重構后的三角網格模型中有50464個三角形(見圖5（b））。

圖5 鞋楦模型重構結果

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

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

圖6 點云模型重構參數面板

3 結 論

給出了一種基于點云數據重構鞋楦曲面模型的方法。利用改進的成本函數實現點云模型法矢的一致化，采用k-d樹數據結構加速搜索過程并減少有符號距離場的計算量。算法實例顯示，該方法是有效的，能夠應用于鞋楦曲面逆向工程實踐。

圖7 重構參數對重構結果的影響

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

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

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

[4]鐘武洋．利用局部點特性進行有效率之表面重建 [D]．新竹：中原大學，2005．