網(wǎng)格模型的表面曲線生成方法

李志豪，石志良

(武漢理工大學(xué) 機電工程學(xué)院，湖北 武漢 430070)

網(wǎng)格模型的表面曲線是模型編輯的重要組成部分，在三維設(shè)計、網(wǎng)格分割、曲面幾何計算、加工制造和計算機動畫等領(lǐng)域都有所應(yīng)用[1-2]。網(wǎng)格模型的表面曲線均要求其能夠反映模型特征、具有一定美感、曲線分布均勻用以規(guī)劃路徑以及保持良好的平滑度。因此，研究網(wǎng)格模型的表面曲線生成技術(shù)，實現(xiàn)表面曲線的個性化編輯，具有理論和實際應(yīng)用價值。

網(wǎng)格表面曲線的設(shè)計方法都聚焦于有特定性質(zhì)的曲線，如測地線[3-4]、具有特殊曲率的曲線以及等平面曲線[5]。目前主要有參數(shù)曲線、曲線光順以及曲線投影3種獲得表面曲線的方法。在曲線參數(shù)化設(shè)計方法中，將流形曲面轉(zhuǎn)換到歐式空間，使用曲線參數(shù)進行設(shè)計。韓林等[6]運用指數(shù)映射參數(shù)化的方法，提出一種離散指數(shù)映射的測地B樣條曲線設(shè)計與復(fù)用方法，但這種生成方法在大規(guī)模網(wǎng)格區(qū)域上表現(xiàn)不佳。該方法通常采用單一參數(shù)化的方法，需要頻繁地對參數(shù)域進行更新，同時也很少考慮到網(wǎng)格失真的影響。在曲線光順方法中，首先定義初始曲線，依據(jù)不同的光順策略對其進行平滑迭代處理。Chen等[7]提出一種優(yōu)化驅(qū)動的三角網(wǎng)格測地路徑計算方法，將目標(biāo)函數(shù)表示為總長度，采用L-BFGS求解器使其最小化，解決了現(xiàn)有方法收斂速度慢、大規(guī)模網(wǎng)格模型上光順效率不足的缺點。Jorge等[8]提出一種非線性表面曲線優(yōu)化方法，該方法基于測地圓錐貝塞爾曲線的定義，代表了有理二次型下測地貝塞爾曲線在網(wǎng)格表面的自然擴散過程，實現(xiàn)了表面曲線的光順。Kai等[9]提出一種基于測地線曲率局部約束的三角形曲面網(wǎng)格分段線性曲線光順新方法，該方法使最終曲線與初始曲線保持一定的接近性。此外，用戶可以調(diào)整貼近度，使用參數(shù)控制曲線的平滑過程，并通過實驗驗證算法的正確性與健壯性，但其受曲面的約束導(dǎo)致效率較低。在采用曲線投影的方法中，將定義的空間曲線進行投影映射，得到網(wǎng)格模型的表面曲線。Panozzo等[10]將網(wǎng)格嵌入到高維歐幾里德空間中，通過廣義加權(quán)平均和投影計算空間樣條曲線，并將結(jié)果映射到曲面上，通過這種投影，曲線的平滑度得到了良好的保持。此外，Jin等[11]提出了一種基于殼空間約束的曲面網(wǎng)格曲線設(shè)計方法，該方法通過自適應(yīng)地改變殼空間的厚度和流形能量的權(quán)重，綜合了基于投影和基于平滑的方法的優(yōu)點。

筆者針對網(wǎng)格模型表面曲線的生成方法進行研究，提出一種基于測地曲率的三角網(wǎng)格表面曲線生成方法。在最初定義的初始控制點上，使用最短路徑確定初始曲線，通過曲率和鄰域約束來逐步平滑原始曲線。這種方法控制初始曲線的平滑距離，使最終曲線與原曲線保持接近，同時避免其他方法出現(xiàn)的特殊頂點狀態(tài)，有較高的穩(wěn)定性。最后，將本文算法應(yīng)用到醫(yī)用外固定支具的網(wǎng)格模型上，結(jié)果顯示，算法適應(yīng)性好，能夠滿足工程應(yīng)用的要求。

1 表面曲線的生成

1.1 算法目標(biāo)及要求

表面曲線生成算法是從最初的鋸齒狀曲線獲得光滑的表面曲線，最終應(yīng)用于網(wǎng)格模型的切割。因此，算法的總體目標(biāo)是基于初始曲線和底層曲面網(wǎng)格構(gòu)建一條平滑曲線。通過曲線平滑，調(diào)整曲線在網(wǎng)格上的位置與形狀，以此來獲得較光滑的曲面曲線，同時還要盡可能與初始曲線接近。但是，由于初始曲線處理后形狀和拓?fù)鋾l(fā)生改變，甚至超出可控范圍，因此需要對平滑曲線的生成做一定要求：

(1)自適應(yīng)性。在網(wǎng)格的局部區(qū)域上，網(wǎng)格拓?fù)漭^復(fù)雜，平滑曲線必須適應(yīng)局部網(wǎng)格拓?fù)洹Ｒ虼耍惴ㄒ笄€在平滑階段可以根據(jù)局部情況適當(dāng)?shù)馗淖兺負(fù)洌诒ＷC表面曲線質(zhì)量的同時保持適應(yīng)性。

(2)曲面域。為便于后續(xù)的網(wǎng)格處理，平滑后的曲線必須位于曲面上，不能與初始曲線的形狀差異過大。因此，需要對平滑范圍適當(dāng)控制，并且每個插入或合并的曲線點必須位于曲面上。

(3)穩(wěn)健性。曲線平滑階段需保持穩(wěn)健性，避免因劣質(zhì)面片和崎嶇表面拓?fù)鋵?dǎo)致算法崩潰。

1.2 算法概述

表面曲線生成算法主要由3個部分組成：

(1)初始化。用戶提供初始曲線、最終曲線的所需曲率及其到初始曲線的最大距離。

(2)平滑。在平滑過程中，曲線點在用戶定義的區(qū)域內(nèi)沿曲面邊移動，這個過程可能需要對曲面點做局部調(diào)整，如分割和合并。

(3)求值。每個平滑步驟之后都會對曲線求值，以確定終止點并識別臨界曲面頂點。這些臨界頂點會限制曲線點的移動，當(dāng)曲線點向這些頂點移動時，需要對其進行適當(dāng)?shù)奶幚怼?/p>

1.3 初始化

算法的輸入由初始曲線和期望曲率以及到初始曲線的最大距離組成。初始曲線由用戶交互控制，用戶在網(wǎng)格上添加控制頂點，然后由最短路徑連接。該曲線是由一系列頂點線段組成，若3個相鄰點位于一個三角形上，即這3個點都是該三角形的3個頂點，則進行簡化操作，將這3個點的中間點刪除，使第一個點直接與第三個點相連形成新的曲線段。此外，還有其他方法生成初始曲線，如基于特征的分割等方法，這種方法采用計算相鄰兩個面片曲率的方法，得到的曲線可以反映網(wǎng)格模型的特征，大多是模型上的銳邊，但其靈活性較差。

圖1為點pi的一環(huán)鄰域，pi-1和pi+1分別為該點的上一個點與下一個點。

圖1 點pi的一環(huán)鄰域

曲線上的每個點定義的初始測地線曲率kg計算公式為：

(1)

式中:θ為該點的總角度，即以點pi為頂點的相鄰三角形的角度和；β為曲線上該點的角度，即pipi-1和pipi+1的夾角。

對每個曲線點pi賦予一個期望的測地曲率kd(pi)，目的是便于后續(xù)將曲線點移動到與其測地曲率相似的位置上。所需的測地曲率kd(pi)通過使用用戶指定的值t在測地曲率kg和0之間執(zhí)行線性插值來計算。

kd(pi)=t·kg(pi)t∈[0,1]

(2)

當(dāng)t=1時，算法應(yīng)返回初始曲線；t=0時，曲線為最短測地線，這種情況意味著曲線盡可能平滑，但可能與初始曲線有很大的偏差。

引入曲線點的最大移動距離約束，將曲線點的移動限制在一個允許的區(qū)域限制內(nèi)，該區(qū)域由曲面上初始曲線的歐幾里德距離定義。在實際應(yīng)用中，使用初始曲線點的一環(huán)鄰域，定義平滑允許區(qū)域。如果需要一條最直的測地線曲線，即上述的t=0的情況，則應(yīng)允許曲線在整個網(wǎng)格上自由移動。

1.4 曲線平滑迭代

網(wǎng)格模型表面曲線生成算法的核心是初始化后的迭代平滑階段。在此過程中，曲線上的點可以沿著網(wǎng)格模型的邊自由移動，但需要保證每個曲線點都始終在某個面片的邊上，并且每個頂點的平滑過程中不會移動到邊的兩端點上。該方法在對曲線點pi進行平滑時存在兩種情況:pi在邊上或者在頂點上。在第一種情況下，pi可以向兩個方向移動，移動終點在該邊的兩頂點，或者在跨越邊緣的一個頂點上。第二種情況需要分割:當(dāng)點離開頂點時，需要新的曲線段，如圖2所示。因此，pi必須被分割成多個曲線點，每個點都位于與頂點相關(guān)聯(lián)的邊上。迭代中的一個曲線平滑步驟包括所有曲線點的松弛。在對pi點進行平滑時，對pi的所在面片域進行提取，如圖3所示，并將該區(qū)域以線段pi-1pi和pipi+1分成兩部分，將這兩部分分別展開，在兩個區(qū)域內(nèi)移動pi點，使得折線pi-1pipi+1最短，取最短長度的點作為調(diào)整后的pi點。如上所述，在pi位于某些特殊頂點處時，平滑過程中可能需要添加新的頂點，這就需要將原曲線分割為多段然后參與下一步迭代。

圖2 點pi的分散平滑迭代

圖3 點pi的平滑迭代

1.5 終止條件

在每次迭代之后，都需要對表面曲線上點的位置進行檢查，檢查其是否出現(xiàn)在合理的位置、曲線的曲率是否滿足要求，以此來決定是否進行下一步迭代。因此，引入曲率限制與移動區(qū)域限制來實現(xiàn)算法的終止。除了平滑的迭代步數(shù)到達(dá)上限，額外采用兩個評價標(biāo)準(zhǔn)來決定算法的終止。第一，平滑后的曲線不應(yīng)該離初始曲線太遠(yuǎn)，因此引入了最大移動距離，將曲線點的移動限制在允許的區(qū)域內(nèi)，這種距離限制可以作為第一種約束，當(dāng)一個點超出這個區(qū)域時，迭代就停止了。第二，定義一個新的百分?jǐn)?shù)τ來表示當(dāng)前曲率與期望曲率的關(guān)系，如果每個當(dāng)前測地曲率與理想的測地曲率相差的程度小于百分?jǐn)?shù)τ時，就停止迭代。

2 算法流程

首先對算法進行初始化，然后計算預(yù)期曲率和計算允許區(qū)域來創(chuàng)建輸入曲線，并計算所需的測地線曲率和最大基于距離的可行域，然后開始平滑迭代。在每次迭代中，對每個點pi應(yīng)用以下操作：先計算點的鄰域集合N1和N2(圖3)，然后根據(jù)展開的表面選擇適當(dāng)?shù)募稀Ｗ詈髮i的新位置求值，并且對特殊位置的頂點進行特殊處理，在每一次迭代后都需要判斷算法是否滿足終止條件。其算法流程如圖4所示。

圖4 算法流程圖

3 應(yīng)用與討論

基于Windows平臺、Visual Studio開發(fā)環(huán)境、QT和VTK開源工具，開發(fā)網(wǎng)格模型的表面曲線生成系統(tǒng)。系統(tǒng)要求CPU主頻在2 GHz以上，內(nèi)存2 G以上，顯存1 G以上。所測試的網(wǎng)格模型是標(biāo)準(zhǔn)橢球模型以及醫(yī)用外固定支具的關(guān)節(jié)掃描踝關(guān)節(jié)模型，該模型通過三維掃描儀獲取原始網(wǎng)格數(shù)據(jù)，并對其進行光順、簡化和切割等預(yù)處理操作以保證網(wǎng)格質(zhì)量。為了便于保存數(shù)據(jù)提高測試效率，將掃描到的網(wǎng)格模型數(shù)據(jù)存儲為STL格式文件[12-13]。讀取STL文件，得到網(wǎng)格模型的點和單元信息，將其轉(zhuǎn)化為特定的數(shù)據(jù)結(jié)構(gòu)后，使用VTK的內(nèi)部渲染管線來實現(xiàn)模型的加載和渲染。

將本文算法應(yīng)用到醫(yī)用外固定支具網(wǎng)格模型上，如圖5所示，分別為橢球模型和踝關(guān)節(jié)模型，頂點數(shù)為1 986和3 968，面片數(shù)為30 240和60 111，在定義初始曲線之后執(zhí)行本算法，分別比較初始曲線和處理后的曲線，并使用網(wǎng)格切割算法進行切割測試。

圖5 網(wǎng)格模型

圖6和圖7為橢球和踝關(guān)節(jié)網(wǎng)格模型的測試實例。圖6(a)中，曲線l1為初始定義曲線，曲線l2為平滑后曲線。并使用網(wǎng)格切割算法進行分割編輯，得到局部分割后的網(wǎng)格模型，如圖6(b)所示。由于橢球模型數(shù)據(jù)量較小，平滑算法對尖銳部分平滑較好，可以實現(xiàn)個性化的設(shè)計意圖。圖7(a)中，曲線l1為初始定義曲線，曲線l2為平滑后曲線。踝關(guān)節(jié)網(wǎng)格模型含6萬余個單元面片，因此初始曲線沒有出現(xiàn)明顯的尖銳效果，同時，平滑效果較好，使光順曲線與原始曲線保持接近，并使用網(wǎng)格分割算法完成模型的分割編輯，如圖7(b)所示。

圖6 橢球網(wǎng)格模型表面曲線

圖7 踝關(guān)節(jié)網(wǎng)格模型表面曲線

本算法的計算消耗主要集中在平滑迭代過程，由于定義高效的數(shù)據(jù)結(jié)構(gòu)，可快速根據(jù)網(wǎng)格拓?fù)湓L問鄰接點和鄰接面片，使頂點位置的搜索變得高效快捷。此外，網(wǎng)格模型的處理效率與其數(shù)據(jù)量關(guān)系密切，頂點數(shù)和面片數(shù)的增加會導(dǎo)致算法運行時間的幾何級數(shù)式增長，因此需要控制網(wǎng)格模型的數(shù)據(jù)量。在外固定支具中，常見的網(wǎng)格模型的數(shù)據(jù)量在1～3萬個頂點左右，本算法運行穩(wěn)定，可得到光順的表面曲線。對百萬級數(shù)據(jù)量的網(wǎng)格模型缺乏實驗驗證，需要進一步研究。

4 結(jié)論

筆者以網(wǎng)格模型為對象，提出一種基于測地曲率的網(wǎng)格表面曲線生成方法，采用交互式的方法簡化了操作，使用基于測地曲率的表面曲線平滑算法對原始曲線進行迭代平滑處理，引入曲率限制和最大移動距離限制，使最終曲線與初始曲線保持良好的接近度，避免由于過度平滑導(dǎo)致的曲線特征消失。同時，本算法結(jié)合醫(yī)用外固定支具掃描網(wǎng)格模型進行實驗驗證，得到了較好的表面曲線平滑結(jié)果，降低網(wǎng)格編輯操作的難度，為操作人員提供便利的交互。