姜曉通,戴 寧,武智磊,楊思遠(yuǎn)

(1.常熟理工學(xué)院 機(jī)械工程學(xué)院,江蘇 蘇州 215500;2.南京航空航天大學(xué) 機(jī)電學(xué)院,江蘇 南京 210016)

0 引 言

曲線設(shè)計(jì)是幾何造型中的一項(xiàng)重要研究?jī)?nèi)容[1-3],其在自由曲面的設(shè)計(jì)、交互和編輯中起著重要作用,且經(jīng)常用于一些高級(jí)的幾何操作中,例如曲面求交[4]、曲面裁剪[5]、加工曲面的數(shù)控刀具軌跡規(guī)劃[6]等。針對(duì)歐氏空間的曲線設(shè)計(jì)的研究較早,相關(guān)的設(shè)計(jì)理論和算法已趨于成熟。但對(duì)于曲面上的曲線設(shè)計(jì),因其在設(shè)計(jì)過程中需要滿足流行約束(曲線位于曲面上),其問題較為復(fù)雜,難度較大。近年來,隨著離散網(wǎng)格建模需求的快速增長(zhǎng),如在齒科領(lǐng)域的建模設(shè)計(jì)需求越來越多,離散網(wǎng)格曲面上的曲線設(shè)計(jì)逐漸受到人們的關(guān)注,因此研究網(wǎng)格曲面上曲線的設(shè)計(jì)方法具有重要意義和工程應(yīng)用價(jià)值。

網(wǎng)格曲面上的曲線通常由離散的分段線段構(gòu)成,常見的曲線形式有樣條曲線、測(cè)地線、細(xì)分曲線等。受流行的約束,其求解難度相對(duì)較大。為了處理流行約束問題,現(xiàn)有的網(wǎng)格曲面的曲線設(shè)計(jì)方法大致可以分為3類:投影法、光順法及參數(shù)化法。

投影法先在歐氏空間完成曲線設(shè)計(jì),然后依次迭代將曲線投影到網(wǎng)格曲面上。Hofer等[7-8]提出能量最小化的樣條曲線插值方法,將問題表示為具有流行約束的優(yōu)化問題,基于樣條能量和測(cè)地能量對(duì)樣條曲線進(jìn)行優(yōu)化,并采用梯度投影法進(jìn)行求解,該方法可用于網(wǎng)格曲面、參數(shù)曲面、隱式曲面,但其投影步驟不能保證一定能計(jì)算出理想的投影點(diǎn),魯棒性較差。Morera等[9]提出一種內(nèi)蘊(yùn)投影法來計(jì)算流行三角網(wǎng)格上的細(xì)分曲線,魯棒性得到了一定的改善,但由于設(shè)計(jì)測(cè)地線計(jì)算,時(shí)間復(fù)雜度較高。金耀等[10]用切平面逼近局部曲面,并將距離約束松弛成用點(diǎn)到切平面的距離,使曲線能夠逐步光順的同時(shí),穩(wěn)步地貼近曲面,從而使投影步驟的魯棒性和可靠性大為提高。投影法實(shí)現(xiàn)方式簡(jiǎn)單,但是由于需要迭代,使得計(jì)算量較大,且對(duì)于復(fù)雜曲面投影可能存在多解,魯棒性較差。

光順法首先對(duì)光滑約束進(jìn)行松弛,然后在流行約束下以光滑能量為驅(qū)動(dòng)對(duì)初始曲線進(jìn)行光順。Jung等[11]在網(wǎng)格曲面上運(yùn)用主動(dòng)輪廓模型演化曲線,在曲面上對(duì)曲線進(jìn)行分段光順,使曲線演化到具有高斯曲率相關(guān)特征附近。Lawonn等[12]提出一種網(wǎng)格曲線的拉普拉斯光順?biāo)阕?通過降低測(cè)地曲率來對(duì)三角網(wǎng)格上分段曲線進(jìn)行光順,可以調(diào)整光順曲線與其原始形狀的接近程度以及規(guī)定測(cè)地線曲率的偏差,但需要對(duì)曲線進(jìn)行多次迭代且無法插值控制點(diǎn)。宋瀅等[13]提出了一種基于多層次優(yōu)化的網(wǎng)格域樣條曲線設(shè)計(jì)方法,該方法放松了曲線嚴(yán)格位于曲面的約束,僅將曲線的離散控制點(diǎn)置于流形空間,并采用內(nèi)點(diǎn)法的思想,運(yùn)用基于塊坐標(biāo)下降法的全局優(yōu)化方法進(jìn)行數(shù)值求解,最后借助局部參數(shù)化將曲線段映射到網(wǎng)格曲面。光順法魯棒性較好,曲線也較為光順,但由于需要進(jìn)行多次迭代且無法插值控制點(diǎn),因此計(jì)算效率低,難以滿足曲線實(shí)時(shí)交互的要求。

參數(shù)化法將曲線所在的設(shè)計(jì)區(qū)域進(jìn)行參數(shù)化,在參數(shù)域內(nèi)進(jìn)行曲線設(shè)計(jì),并將曲線設(shè)計(jì)結(jié)果映射回網(wǎng)格曲面。Lee等[14]提出了一種“幾何蛇形”曲線作為三角網(wǎng)格模型的特征檢測(cè)工具,將曲線所在的局部區(qū)域進(jìn)行參數(shù)化,在參數(shù)域內(nèi)使用能量函數(shù)演化曲線從初始位置成功捕獲附近的特征;朱文明等[15]通過對(duì)流行網(wǎng)格進(jìn)行保角參數(shù)化,并在參數(shù)域內(nèi)生成細(xì)分曲線,可以快速生成網(wǎng)格曲面上的光滑曲線;韓林等[16]使用離散指數(shù)映射技術(shù)參數(shù)化B樣條曲線的控制頂點(diǎn),實(shí)現(xiàn)了網(wǎng)格曲面上B樣條曲線的設(shè)計(jì)與復(fù)用。劉斌等[17]通過離散指數(shù)映射參數(shù)化技術(shù)將源曲線控制頂點(diǎn)映射到切空間,獲得它們的法坐標(biāo),按照陣列前后控制頂點(diǎn)法坐標(biāo)不變的原則,實(shí)現(xiàn)了曲線在網(wǎng)格曲面上的陣列。參數(shù)化法對(duì)于小范圍曲線設(shè)計(jì)魯棒性較好,計(jì)算效率高,曲線設(shè)計(jì)較為靈活。但當(dāng)進(jìn)行大范圍的曲線設(shè)計(jì)時(shí),大范圍的曲面參數(shù)化較為耗時(shí),影響了曲線設(shè)計(jì)的效率,難以實(shí)現(xiàn)曲線的實(shí)時(shí)編輯,同時(shí)大范圍的曲面參數(shù)化會(huì)導(dǎo)致局部參數(shù)化畸變嚴(yán)重,甚至出現(xiàn)大面積的“重疊”現(xiàn)象,導(dǎo)致曲線在局部畸變的情況,甚至?xí)鹪谇€設(shè)計(jì)時(shí)求交算法的不穩(wěn)定性問題。另外,參數(shù)化方法并不能完全適用于網(wǎng)格曲面存在“虧格”的情況,也限制了參數(shù)化方法的適用范圍。

齒科是離散網(wǎng)格曲面應(yīng)用最為廣泛的領(lǐng)域之一,齒科掃描模型的復(fù)雜性及相關(guān)建模軟件個(gè)性化設(shè)計(jì)的需求,其對(duì)樣條曲線的設(shè)計(jì)也提出了具體要求,主要有如下特點(diǎn):

(1)齒科三維掃描模型三角面片個(gè)數(shù)較多,在曲線設(shè)計(jì)時(shí)需要進(jìn)行實(shí)時(shí)編輯,要求曲線設(shè)計(jì)效率較高,能夠滿足實(shí)時(shí)交互的需求;

(2)齒科三維掃描模型較為復(fù)雜,對(duì)曲線設(shè)計(jì)的精度要求不高,但建模軟件的使用人員在繪制曲線時(shí)較為“隨意”,因此對(duì)魯棒性提出了較高的要求;

(3)因建模軟件的設(shè)計(jì)要求,需要基于網(wǎng)格曲線進(jìn)行個(gè)性化建模,因此對(duì)樣條線的設(shè)計(jì)原理提出了具體的要求。

該文針對(duì)在齒科建模領(lǐng)域中,對(duì)于網(wǎng)格曲線設(shè)計(jì)在高效性、魯棒性及基于網(wǎng)格曲線個(gè)性化建模等方面的要求,提出了一種適用于大范圍網(wǎng)格曲面曲線編輯的參數(shù)化設(shè)計(jì)方法,使用離散指數(shù)映射參數(shù)化技術(shù),將三維的曲線設(shè)計(jì)轉(zhuǎn)換成二維曲線設(shè)計(jì),在二維平面內(nèi)進(jìn)行基于曲線的建模設(shè)計(jì),滿足建模軟件個(gè)性化建模的需求。利用分段樣條線替代全局樣條線,分段設(shè)計(jì)網(wǎng)格曲面樣條曲線,減小參數(shù)化區(qū)域,能夠?qū)崿F(xiàn)在大范圍網(wǎng)格曲面內(nèi)快速設(shè)計(jì)曲線,同時(shí)將參數(shù)化設(shè)計(jì)方法擴(kuò)展到虧格網(wǎng)格曲面。針對(duì)建模軟件使用人員在建模過程中繪制曲線較為“隨意”,樣條曲線兩型值點(diǎn)間距較大而導(dǎo)致的魯棒性問題,引入兩點(diǎn)間的最近路徑,在兩型值點(diǎn)中加入若干型值點(diǎn),滿足離散建模軟件對(duì)算法魯棒性的要求。針對(duì)曲線分段設(shè)計(jì)時(shí)在部分型值點(diǎn)處出現(xiàn)不連續(xù)(尖點(diǎn))的問題,在型值點(diǎn)處進(jìn)行局部光順,從而保證曲線的質(zhì)量。相比其他方法,該算法在效率、魯棒性及適用性等方面具有一定優(yōu)勢(shì),綜合性能較好。

1 離散指數(shù)參數(shù)化技術(shù)

1.1 指數(shù)映射及測(cè)地極坐標(biāo)

設(shè)Tp是曲面S在p點(diǎn)的切平面,那么指數(shù)映射就是從切平面Tp到曲面S上的一個(gè)對(duì)應(yīng)關(guān)系,記為Tp→S,定義如下:設(shè)v是曲面S在p點(diǎn)的一個(gè)切向量,過點(diǎn)p作曲面S上與切向量v相切的測(cè)地線γ,在此測(cè)地線上取一點(diǎn)m,使得從p到m的弧長(zhǎng)正好等于v的長(zhǎng)度|v|,則定義指數(shù)映射exp(v)=m。

指數(shù)映射可以看作是曲面到切平面的一種映射,它將曲面上的三維空間上的點(diǎn)映射到二維平面上(見圖1)。對(duì)于曲面S上任意一點(diǎn)p,過點(diǎn)p作其切平面Tp,對(duì)任一單位向量v∈Tp來說,都唯一存在一條用弧長(zhǎng)來參數(shù)化的測(cè)地線γ,使得γ(0)=p且γ(0)'=v。對(duì)于p點(diǎn)的任一鄰域點(diǎn)q來說,都會(huì)有唯一的一條測(cè)地線通過它。因此,可以使用測(cè)地極坐標(biāo)(ρ,φ)將三維空間點(diǎn)q映射到二維切平面Tp上,其中ρ是p點(diǎn)到q點(diǎn)的測(cè)地線距離,φ是v在Tp上的極角,這就是測(cè)地極坐標(biāo)的表示形式,也可以將其看作二維矢量,稱作測(cè)地矢量。

圖1 指數(shù)映射

1.2 離散指數(shù)映射參數(shù)化基本原理

該文采用Schmidt等[18]提出的離散指數(shù)參數(shù)化技術(shù)計(jì)算測(cè)地矢量,該方法并不直接計(jì)算網(wǎng)格曲面上的點(diǎn)到種子點(diǎn)的測(cè)地矢量,而是通過Dijkstra算法進(jìn)行擴(kuò)散傳播,先記錄每個(gè)網(wǎng)格頂點(diǎn)到種子點(diǎn)的路徑并在每個(gè)網(wǎng)格頂點(diǎn)上建立局部坐標(biāo)系,然后對(duì)每個(gè)網(wǎng)格頂點(diǎn)向其最短路徑上的前一個(gè)鄰接頂點(diǎn)作指數(shù)映射,最后對(duì)Dijkstra算法產(chǎn)生的分段測(cè)地矢量進(jìn)行疊加。

如圖2所示,假設(shè)網(wǎng)格曲面上有3個(gè)頂點(diǎn),分別為p、r、q,可以根據(jù)指數(shù)映射理論計(jì)算出p點(diǎn)到r點(diǎn)的測(cè)地矢量Up,r和r點(diǎn)到q點(diǎn)的測(cè)地矢量Ur,q,則p點(diǎn)到q點(diǎn)的測(cè)地矢量Up,r可以表示為:

圖2 離散指數(shù)映射疊加

Up,q=Up,r+(Up,q-Up,r)

(1)

Up,q≈Up,r+Rot2D(θp,r)Ur,q

(2)

式中,Rot2D為二維旋轉(zhuǎn)變換矩陣。

對(duì)于網(wǎng)格模型上的任意一個(gè)頂點(diǎn)q,利用Dijkstra算法生成從種子點(diǎn)p到目標(biāo)點(diǎn)q的近似測(cè)地路徑,利用公式(2)計(jì)算得到該路徑中每一個(gè)頂點(diǎn)在種子點(diǎn)p所在切平面上的坐標(biāo)值。由于公式(2)在變換過程中存在誤差,該誤差在從點(diǎn)p到點(diǎn)q的近似測(cè)地路徑會(huì)累計(jì)疊加,因此在進(jìn)行大范圍網(wǎng)格曲面的參數(shù)化或網(wǎng)格曲面較為復(fù)雜時(shí),其參數(shù)化結(jié)果會(huì)產(chǎn)生較大畸變,甚至“重疊”現(xiàn)象。但是若不謀求網(wǎng)格全局參數(shù)化,只考慮局部映射,其精度是能夠保證的。同時(shí)由于離散指數(shù)映射無需計(jì)算測(cè)地線,減小了計(jì)算成本,非常適用于三角網(wǎng)格的局部快速參數(shù)化,對(duì)于分段樣條曲線的設(shè)計(jì)具有很大優(yōu)勢(shì),能夠滿足曲線編輯實(shí)時(shí)交互的要求。

2 分段樣條曲線設(shè)計(jì)

2.1 準(zhǔn)均勻B樣條曲線

給定條件①控制頂點(diǎn):P0,P1,…,Pn;②B樣條曲線基函數(shù)的次數(shù)k;③節(jié)點(diǎn)矢量:[u0,u1,…,un,…,un+k+1],可以唯一定義k次B樣條曲線為:

(3)

式中,u∈[uk,un+1]。

根據(jù)均勻B樣條基函數(shù)的遞推定義,可以得到均勻3次B樣條曲線基函數(shù)如下:

(4)

準(zhǔn)均勻B樣條曲線就是在均勻B樣條曲線的基礎(chǔ)上增加了k+1個(gè)重節(jié)點(diǎn)的限制,使其不僅具有均勻B樣條的局部支撐性,即當(dāng)用戶想要改變型值點(diǎn)的位置,只需重新計(jì)算該型值點(diǎn)臨近的樣條曲線即可,而且準(zhǔn)均勻B樣條具有Bezier曲線的端點(diǎn)性質(zhì),使用戶對(duì)曲線在端點(diǎn)處的行為有較好的控制。因此,文中算法采用準(zhǔn)均勻B樣條曲線在參數(shù)化平面內(nèi)生成樣條線。

2.2 局部分段樣條曲線

給定一個(gè)離散網(wǎng)格曲面S,在網(wǎng)格曲面上依次拾取型值點(diǎn)p0,p1,…,pn,文中算法僅利用最新拾取的三個(gè)型值點(diǎn),在局部參數(shù)域內(nèi)生成分段的準(zhǔn)均勻3次B樣條曲線,并對(duì)整體樣條曲線進(jìn)行局部更新,算法主要分3步:

(1)確定參數(shù)化區(qū)域。

離散指數(shù)映射是一種局部參數(shù)化技術(shù),在計(jì)算參數(shù)化區(qū)域時(shí),需要給定參數(shù)化原點(diǎn)和半徑,參數(shù)化區(qū)域必須盡可能覆蓋測(cè)地B樣條曲線設(shè)計(jì)區(qū)域。假設(shè)在繪制當(dāng)前樣條曲線時(shí)正拾取第i個(gè)型值點(diǎn)。

當(dāng)i=0時(shí),型值點(diǎn)個(gè)數(shù)為1,無需繪制網(wǎng)格樣條曲線。

當(dāng)i=1時(shí),2個(gè)型值點(diǎn)為p0,p1,此時(shí)參數(shù)化原點(diǎn)為任意一個(gè)型值點(diǎn),將p0和p1之間的歐氏距離記作|p0p1|,則參數(shù)化半徑paraDis=1.4|p0p1|,此時(shí)生成的為一段測(cè)地直線。

當(dāng)i=2時(shí),3個(gè)型值點(diǎn)為p0,p1,p2,則參數(shù)化原點(diǎn)為p1,參數(shù)化半徑paraDis=1.4max{|p0p1|,|p1p2|},此時(shí)生成的為一段測(cè)地樣條曲線,此后用戶繼續(xù)增加型值點(diǎn),則總是取最后三個(gè)型值點(diǎn)pi-2,pi-1,pi生成一段測(cè)地樣條曲線,其中參數(shù)化原點(diǎn)和半徑的確定方法與上述一致。

(2)二維參數(shù)化平面上的樣條曲線設(shè)計(jì)。

將三個(gè)型值點(diǎn)為一組的樣條曲線段所在網(wǎng)格區(qū)域進(jìn)行參數(shù)化后,可以得到型值點(diǎn)的二維UV坐標(biāo)。根據(jù)型值點(diǎn)的UV坐標(biāo)及非均勻B樣條曲線插值方法可以生成位于參數(shù)化平面上的二維樣條曲線,但由于網(wǎng)格曲線通常由離散的分段線段構(gòu)成,因此需要對(duì)樣條曲線段進(jìn)行采樣。由于采樣點(diǎn)只有坐標(biāo)信息,沒有網(wǎng)格位置信息,并且型值點(diǎn)和采樣點(diǎn)之間連線與網(wǎng)格的交點(diǎn)未知,因此需要進(jìn)行計(jì)算。給定起點(diǎn)ps和終點(diǎn)pt,計(jì)算過程如下:

①若起點(diǎn)ps在網(wǎng)格三角面片面內(nèi),計(jì)算起點(diǎn)ps和終點(diǎn)pt連線與起點(diǎn)ps所在三角面片相交的邊,并將計(jì)算得到的交點(diǎn)pc賦值給ps,更新起點(diǎn)。

②若起點(diǎn)ps在網(wǎng)格邊上,與起點(diǎn)ps所在網(wǎng)格邊共邊的有兩個(gè)三角形,判斷起點(diǎn)ps和終點(diǎn)pt連線經(jīng)過哪個(gè)三角形,并確定連線與該三角形相交的邊,并將計(jì)算得到的交點(diǎn)pc賦值給ps,更新起點(diǎn)。

③重復(fù)上述過程直至到達(dá)終點(diǎn)pt。

(3)二維參數(shù)化平面到三維網(wǎng)格曲面的映射。

二維平面內(nèi)的樣條曲線設(shè)計(jì)完成后,需要將其映射回三維網(wǎng)格曲面。假定在二維參數(shù)化網(wǎng)格平面取樣條曲線上任一點(diǎn)為p,點(diǎn)p所在三角面片的三個(gè)頂點(diǎn)V0,V1,V2可以定義平面內(nèi)包圍該點(diǎn)的凸多邊形,用公式可以表示為:

(5)

構(gòu)造方程組并求解可得到α0,α1,如圖3所示,(α0,α1,1-α0-α1)代表點(diǎn)p相對(duì)于三角面片三個(gè)頂點(diǎn)的相對(duì)位置關(guān)系。

圖3 三角形內(nèi)一點(diǎn)p相對(duì)位置關(guān)系

由于離散指數(shù)參數(shù)化技術(shù)并不改變?nèi)敲嫫男螤?因此利用公式(5)可以將二維參數(shù)化平面上三角面片上的任意一點(diǎn)映射回其三維網(wǎng)格上的三角面片上,則點(diǎn)p的三維空間坐標(biāo)p3可表示為:

(6)

2.3 樣條曲線優(yōu)化

(1)最短路徑優(yōu)化。

在實(shí)際工程應(yīng)用中,用戶在繪制網(wǎng)格樣條曲線時(shí)較為“隨意”。當(dāng)相鄰兩型值點(diǎn)距離過大時(shí)會(huì)導(dǎo)致參數(shù)化區(qū)域增大,而離散指數(shù)參數(shù)化技術(shù)在參數(shù)化區(qū)域過大時(shí)會(huì)產(chǎn)生較大的網(wǎng)格畸變、重疊等現(xiàn)象,從而導(dǎo)致兩型值點(diǎn)之間的樣條線不光滑,甚至樣條線中斷的情況,如圖4(a)所示。為了提高算法的穩(wěn)定性,避免用戶在設(shè)計(jì)曲線時(shí)出現(xiàn)上述情況,引入Dijkstra算法計(jì)算兩點(diǎn)間的最短路徑,在兩型值點(diǎn)之間的最短路徑上進(jìn)行采樣,在采樣路徑上增加型值點(diǎn)的個(gè)數(shù),從而有效避免上述情況的出現(xiàn),如圖4(b)所示。

圖4 最短路徑優(yōu)化

(2)局部光順優(yōu)化。

在網(wǎng)格曲面生成樣條曲線時(shí),因?yàn)椴捎梅侄螛訔l線策略,因此在型值點(diǎn)處會(huì)出現(xiàn)“尖點(diǎn)”,從而降低了曲線的光順性,如圖5(a)所示。針對(duì)此問題,文中算法在型值點(diǎn)處進(jìn)行局部光順。設(shè)給定離散網(wǎng)格曲線點(diǎn)列Pi(i=0,1,…,n),該離散點(diǎn)列的能量可表示為:

圖5 局部光順優(yōu)化示意圖

(7)

在對(duì)離散點(diǎn)列進(jìn)行光順時(shí)有兩個(gè)原則:一是光順后離散點(diǎn)列的能量Ec盡可能小,二是光順后離散點(diǎn)列的偏離盡可能小。綜合以上兩點(diǎn),給出如下所示的離散點(diǎn)列的加權(quán)綜合光順方法:

(8)

式中,Pi(i=0,1,…,n)為光順后的離散點(diǎn)列;Qi(i=0,1,…,n)為光順前的離散點(diǎn)列;Ec為離散點(diǎn)列Pi的能量;α和β為用戶指定的非負(fù)常數(shù)。如圖5(b)所示,采用上述方法對(duì)型值點(diǎn)附近的離散點(diǎn)列進(jìn)行光順后,曲線的光順性得到了明顯提高。

3 實(shí)驗(yàn)結(jié)果與分析

文中算法利用C++語(yǔ)言,在Visual Studio2017環(huán)境下開發(fā),模型顯示是基于VTK圖形庫(kù),在AMD Ryzen 7 5800H處理器主頻為3.20 GHz,16 GB內(nèi)存的電腦上測(cè)試。測(cè)試過程中所有的數(shù)據(jù)都來源于實(shí)際掃描數(shù)據(jù),驗(yàn)證算法的有效性與實(shí)用性。

3.1 算法的實(shí)際設(shè)計(jì)效果

圖6為文中算法在牙頜模型上的實(shí)際曲線設(shè)計(jì)效果。因采用分段樣條線策略,該算法能夠?qū)崿F(xiàn)大范圍網(wǎng)格曲面樣條曲線的實(shí)時(shí)設(shè)計(jì)。同時(shí)在進(jìn)行曲線編輯時(shí),拖動(dòng)一個(gè)型值點(diǎn)只改變?cè)撔椭迭c(diǎn)附近的一段曲線而不會(huì)改變整段曲線的形狀,能夠快速對(duì)曲線進(jìn)行編輯修改。

圖6 牙頜模型上的曲線設(shè)計(jì)

該算法因采用局部參數(shù)化進(jìn)行分段曲線設(shè)計(jì),能夠在虧格模型上進(jìn)行曲線設(shè)計(jì)。圖7展示了利用該算法在虧格模型上進(jìn)行的曲線設(shè)計(jì),該曲線可以環(huán)繞虧格,而基于全局參數(shù)化的曲線設(shè)計(jì)方法則無法在虧格模型上生成如圖所示的曲線。

圖7 虧格模型上的曲線設(shè)計(jì)

3.2 樣條曲線設(shè)計(jì)效率

在齒科建模工程應(yīng)用中,曲線設(shè)計(jì)需滿足實(shí)時(shí)交互的要求,即曲線設(shè)計(jì)算法必須高效。為了驗(yàn)證文中算法的高效性,選擇如圖8所示的4個(gè)不同規(guī)模的模型進(jìn)行測(cè)試。

圖8 不同牙頜模型上的曲線設(shè)計(jì)

在測(cè)試過程中,分別在不同模型上選取3個(gè)型值點(diǎn)生成樣條曲線,并計(jì)算生成這段曲線所需時(shí)間。表1為在這些模型上生成曲線所用的時(shí)間。

表1 不同的模型上網(wǎng)格曲線的生成時(shí)間

從表中可以看出,當(dāng)樣條曲線離散點(diǎn)數(shù)大致相同時(shí),參數(shù)化區(qū)域大小(頂點(diǎn)數(shù)和面片數(shù))相差不大。但隨著模型頂點(diǎn)數(shù)和面片數(shù)的增加,運(yùn)行時(shí)間會(huì)相應(yīng)增加。但從表中可以看出網(wǎng)格規(guī)模與算法效率的相關(guān)度較小,在網(wǎng)格頂點(diǎn)數(shù)為22萬,曲線離散點(diǎn)數(shù)為194時(shí),其計(jì)算時(shí)間僅為88.6 ms,可以滿足實(shí)際工程應(yīng)用中曲線設(shè)計(jì)實(shí)時(shí)交互的要求。

圖9為網(wǎng)格頂點(diǎn)不同量級(jí)的牙頜模型在模型表面的同一位置上繪制的網(wǎng)格曲線,計(jì)算曲線在每一個(gè)模型的生成時(shí)間,其結(jié)果如表2所示。

表2 不同規(guī)模的同一模型上網(wǎng)格曲線的生成時(shí)間

圖9 不同規(guī)模的牙頜模型上同一位置的曲線設(shè)計(jì)

從表中可以看出,隨著模型頂點(diǎn)量級(jí)的增大,參數(shù)化區(qū)域大小(頂點(diǎn)數(shù)和面片數(shù))會(huì)相應(yīng)增大,導(dǎo)致所生成的曲線包含的離散點(diǎn)數(shù)增多,生成曲線的時(shí)間也隨之增加,與參數(shù)化區(qū)域頂點(diǎn)的個(gè)數(shù)基本上成正比。

從上述兩個(gè)測(cè)試實(shí)驗(yàn)可以看出,文中算法的效率主要受局部參數(shù)化區(qū)域內(nèi)網(wǎng)格頂點(diǎn)的數(shù)量的影響,局部參數(shù)化網(wǎng)格頂點(diǎn)越多,效率越低,而網(wǎng)格模型總頂點(diǎn)數(shù)量對(duì)算法效率的影響較小,因此文中算法能夠在大規(guī)模網(wǎng)格模型上進(jìn)行高效的大范圍曲線設(shè)計(jì),能夠滿足工程應(yīng)用的要求。

3.3 實(shí)驗(yàn)對(duì)比

文中算法是為滿足網(wǎng)格曲線在齒科建模軟件中的應(yīng)用而設(shè)計(jì),為了驗(yàn)證算法的效果,從曲線的光滑度、效率、局部編輯性及擴(kuò)展應(yīng)用性等方面與文獻(xiàn)[10,13]進(jìn)行比較與分析,如表3所示。

表3 算法比較

文獻(xiàn)[10,13]的算法都屬于投影法和光順法相結(jié)合的算法。在曲線光順度方面,由于該文采用分段樣條曲線進(jìn)行設(shè)計(jì),并對(duì)樣條線進(jìn)行局部光順,因此相比文獻(xiàn)[10,13]的算法,文中算法生成的曲線光順度相對(duì)較差,但由于文中算法主要應(yīng)用于齒科建模軟件中,其對(duì)曲線的光順度要求不高,能滿足要求。在效率方面,文獻(xiàn)[10]的算法效率最高,在模型點(diǎn)數(shù)3 070,曲線離散點(diǎn)數(shù)258的情況下,其運(yùn)行時(shí)間為12.5 ms;文獻(xiàn)[13]的算法和文中算法次之。文獻(xiàn)[13]的算法,在模型點(diǎn)數(shù)15 000,曲線離散點(diǎn)數(shù)190的情況下,其運(yùn)行時(shí)間為39 ms,而文中算法在模型點(diǎn)數(shù)78 417,曲線離散點(diǎn)數(shù)199的情況下,其運(yùn)行時(shí)間為63 ms。在局部編輯性方面,由于文獻(xiàn)[10,13]的算法對(duì)曲線進(jìn)行全局光順,因此在改變曲線的一個(gè)型值點(diǎn)時(shí),整個(gè)曲線都會(huì)發(fā)生相應(yīng)的變化;而文中算法采用分段樣條曲線,因此在進(jìn)行曲線編輯時(shí),改變曲線一個(gè)型值點(diǎn),其作用范圍只局限于該型值點(diǎn)前后兩個(gè)型值點(diǎn)之間的曲線,因此文中算法的局部編輯性更好。在應(yīng)用擴(kuò)展性方面,文獻(xiàn)[13]的算法松弛了曲線嚴(yán)格位于曲面的約束,因此并不能用于曲線裁剪、基于曲線的個(gè)性化建模(圖10所示)等方面;文獻(xiàn)[10]的算法中的曲線嚴(yán)格約束于網(wǎng)格曲面上,因此可以應(yīng)用于曲線裁剪,但在齒科建模軟件中基于曲線的個(gè)性化建模中,該算法生成的曲線并不適用;而文中算法因采用局部參數(shù)化方法,可以在垂直于樣條線走向的方向上生成一系列具有一定寬度的直線,通過鋪面、抽殼等操作生成具有一定形態(tài)的三維模型(如圖10(b)所示的卡環(huán)),同時(shí)算法嚴(yán)格約束于曲面,因此可以用于曲線裁剪。

圖10 可摘局部義齒建模

3.4 基于樣條線的建模應(yīng)用

圖10為文中算法在齒科建模軟件中的應(yīng)用。圖10(a)為利用文中算法在牙頜模型的不同區(qū)域進(jìn)行網(wǎng)格裁剪,生成子網(wǎng)格,用于網(wǎng)格模型局部區(qū)域的偏置。圖10(b)為利用文中算法在牙頜模型上進(jìn)行基于樣條曲線的三維建模,在牙頜模型上生成卡環(huán)、連接體等(沿著樣條曲線方向,具有一定寬度且與原始模型緊密相貼的條狀或半圓柱狀模型),用于可摘局部義齒的設(shè)計(jì)。圖10(c)為利用文中算法完成的可摘局部義齒的設(shè)計(jì)。

4 結(jié)束語(yǔ)

該文提出了一種基于局部參數(shù)化的離散網(wǎng)格曲面樣條曲線設(shè)計(jì)方法。該方法放松了對(duì)樣條曲線全局連續(xù)性的約束,將平面參數(shù)域內(nèi)的全局樣條線設(shè)計(jì)轉(zhuǎn)化成在局部區(qū)域內(nèi)的分段樣條曲線設(shè)計(jì)。同時(shí)引入兩型值點(diǎn)間的最短路徑,解決在樣條線設(shè)計(jì)過程中,因相鄰兩型值點(diǎn)距離過大而導(dǎo)致算法存在的魯棒性問題,引入局部光順?biāo)惴?提高網(wǎng)格曲線在型值點(diǎn)附近的光順性。相比于全局參數(shù)化的網(wǎng)格曲線設(shè)計(jì)方法,該方法魯棒、高效,并且能滿足大范圍網(wǎng)格實(shí)時(shí)編輯的要求,綜合性能較好。

該方法采用局部參數(shù)化方法進(jìn)行曲線設(shè)計(jì),其中參數(shù)化區(qū)域大小(頂點(diǎn)數(shù)和面片數(shù))對(duì)曲線設(shè)計(jì)效率影響較大,而算法所生成的參數(shù)化區(qū)域?yàn)榫嚯x中心點(diǎn)參數(shù)化半徑范圍內(nèi)的所有三角面片,一定程度上造成了計(jì)算的浪費(fèi),因此如何識(shí)別曲線所在網(wǎng)格區(qū)域,從而減小參數(shù)化區(qū)域是未來需要研究的工作。