一種基于能量模型的曲面展開改進(jìn)算法

嚴(yán)國彪,劉斌

(華僑大學(xué)機(jī)電及自動化學(xué)院,福建泉州 362021)

一種基于能量模型的曲面展開改進(jìn)算法

嚴(yán)國彪,劉斌

(華僑大學(xué)機(jī)電及自動化學(xué)院,福建泉州 362021)

針對現(xiàn)有算法存在的問題,提出一種基于能量模型的自由曲面展開改進(jìn)算法.算法的改進(jìn)主要是對時間步長的調(diào)整.通過調(diào)整時間步長,避免展開過程中發(fā)散現(xiàn)象,同時也有效地提高曲面展開的精度,較好地解決展開過程中因迭代次數(shù)過多而引起的振蕩現(xiàn)象,提高曲面展開的質(zhì)量.算例結(jié)果表明,算法是有效的,可以滿足實時交互設(shè)計的要求.

曲面展開;能量模型;時間步長;三角網(wǎng)格

3D曲面展開技術(shù)廣泛應(yīng)用于飛機(jī)、汽車、船舶,以及服裝和鞋類等設(shè)計和制造領(lǐng)域中.這些行業(yè)都需要得到設(shè)計產(chǎn)品的平面外形圖.傳統(tǒng)的方法是將最初的平面外形圖手工進(jìn)行反復(fù)縫合、修改,直至最終得到理想的外形圖.許多應(yīng)用于產(chǎn)業(yè)的CAD/CAM系統(tǒng)具有將立體曲面展開為平面的功能,大大方便了后繼的設(shè)計和制造.曲面的展開問題,特別是復(fù)雜曲面的展開問題[1-2],一直是計算機(jī)輔助幾何設(shè)計領(lǐng)域研究的熱點和難點.合理地展開三維曲面是CAD&CG領(lǐng)域中眾多技術(shù)得以實現(xiàn)的重要基礎(chǔ),國內(nèi)外眾多學(xué)者進(jìn)行了不少相關(guān)的研究.文獻(xiàn)[3-5]在曲面展開系統(tǒng)中采用了彈簧-質(zhì)點模型對其曲面展開進(jìn)行優(yōu)化,但他們研究的側(cè)重點不同.上述算法都未考慮到迭代優(yōu)化中的發(fā)散問題,即如果參數(shù)選擇不合理的話,則很容易產(chǎn)生發(fā)散,使迭代過程不收斂,導(dǎo)致展開計算失敗.基于此,本文提出基于能量模型曲面展開的改進(jìn)方法.

1 曲面展開的能量模型

1.1 能量模型的建立

曲面展開前,先對曲面進(jìn)行三角化,并由三角化網(wǎng)格建立一個彈簧質(zhì)點系統(tǒng).該系統(tǒng)的物理量與某些幾何量是相對應(yīng)的,如力、質(zhì)量和彈性變形能是由網(wǎng)格節(jié)點間的距離和三角片的面積確定的.原始網(wǎng)格形狀和展開后二維片形狀之間的差別,可視為一種貯存在彈簧質(zhì)點系統(tǒng)中的彈性變形能,通過釋放變形能,提高曲面展開質(zhì)量.由于能量是狀態(tài)的單值函數(shù),與過程無關(guān),所以能量的關(guān)系式比較容易列出.

在能量模型中,大多數(shù)基于物理的參數(shù),如系統(tǒng)力、質(zhì)量和彈性變形能等,均由其相關(guān)的幾何量定義而得[6-7].研究中可將材料特性加入,由此,不同的材料特性將可得到不同的展開結(jié)果,有利于工程上的實際應(yīng)用.

彈簧質(zhì)點系統(tǒng)的示意圖,如圖1所示.圖1中,Pi為質(zhì)點,質(zhì)點Pi和Pj間的聯(lián)接為彈簧.在曲面展開成平面的過程中,如果平面上Pi和Pj的間距大于對應(yīng)的原始曲面上此兩點的間距,則對Pi和Pj施以拉力(圖1中P0和P1點);反之,則施以推力(圖1中P0和P6點).

彈性變形能E和彈性力f的計算式為

圖1 彈簧質(zhì)點系統(tǒng)Fig.1 Sp ring-mass system

上式中:C為彈簧彈性變形系數(shù);|Pi Pj|是曲面展開后的平面上Pi到Pj的距離;dj為空間曲面上的Pi到Pj的距離;是從Pi指向Pj的單位矢量,n為質(zhì)點Pi相鄰的質(zhì)點數(shù).

在曲面展開過程中,質(zhì)點的運(yùn)動可以用拉格朗日方程來描述,即

式(3)中:M,D和K分別為系統(tǒng)的質(zhì)量矩陣、阻尼矩陣和剛度矩陣;gq為局部自由度與全局自由度之差引起的系統(tǒng)內(nèi)力,fq為系統(tǒng)外力.

在彈簧系統(tǒng)中,gq和fq為零,而阻尼矩陣D可以忽略,所以拉格朗日方程可簡化為

當(dāng)考慮質(zhì)點運(yùn)動中的時間間隔Δt很小時,質(zhì)點Pi的加速度可被認(rèn)為是常量,則整個系統(tǒng)中的各個質(zhì)點處于平衡.利用歐拉法可以求解式(4)的拉格朗日方程,即式(4)可變換為

式(5)中:mi是節(jié)點Pi的質(zhì)量;ζ是曲面的面密度;fi(t)是作用在節(jié)點Pi上的彈性力;Ak是包含節(jié)點Pi的所有三角形中第k個三角形的面積;¨q(t)是節(jié)點Pi的加速度;˙q(t)是節(jié)點Pi的速度;qi(t)是節(jié)點Pi在時間t的位置.

1.2 算法的改進(jìn)

為了得到精確的展開平面,需要進(jìn)行能量算法的多次迭代.從式(5)的第3個式子可以看出,前一時刻的速度對后一時刻的速度是有很大影響的.當(dāng)?shù)螖?shù)較多時(一般復(fù)雜曲面要進(jìn)行很多次的迭代),慣性作用會產(chǎn)生累積效應(yīng),導(dǎo)致的后果是在當(dāng)前時刻得到的質(zhì)點速度非常大.即使后一時刻加速度與前一時刻速度是反向的,質(zhì)點的運(yùn)動也不能立即反向,而是會繼續(xù)向原來方向運(yùn)動.這樣就會導(dǎo)致越來越偏離平衡位置,網(wǎng)格邊長的變形程度越來越厲害,最終的結(jié)果是在曲面展開中產(chǎn)生較大的振蕩.曲面越復(fù)雜,這種副作用就越明顯,以致得不到符合需要的展開平面.

為了避免這種不利的副作用,采取忽略初速度的方法,對式(5)中的第3,4式進(jìn)行調(diào)整,即

采取忽略初速度的初衷是為了避免發(fā)散現(xiàn)象.若優(yōu)化的時間Δt過小,曲面展平的優(yōu)化速度太慢,迭代次數(shù)過多,展開時間過長,所得到的優(yōu)化效果不明顯;若優(yōu)化的時間Δt過大,展平過程中會引起迭代振蕩,得不到所需的展開平面.所以,如何取優(yōu)化時間Δt是算法的關(guān)鍵.

適當(dāng)?shù)剡x取優(yōu)化時間,可避免初始時間步長取值不合適而浪費大量的計算時間或迭代發(fā)散的情況.Δt是隨著迭代次數(shù)的增多而不斷減小,其計算式為

式(8)中:t0是初始優(yōu)化時間;dt為迭代過程中每次優(yōu)化時間的變化量;N為算法的當(dāng)前迭代次數(shù);M為Δt變化一次所需的迭代次數(shù).

在算法迭代的初期,為達(dá)到優(yōu)化的高效率目的,適當(dāng)選取較大的t0值(這里取t0為0.5～0.6).隨著迭代次數(shù)的增加,質(zhì)點離平衡點越來越近,此時,Δt應(yīng)當(dāng)取較小值,以防止振蕩現(xiàn)象的產(chǎn)生.在算法中,為了防止Δt過小,甚至為負(fù)值的情況發(fā)生,就必須合理地選取dt,N和M.實驗結(jié)果表明,若參數(shù)dt,N和M選取不當(dāng),使Δt變化緩慢,則容易發(fā)生展開震蕩;或使Δt變化過快,導(dǎo)致展開精度不佳.

1.3 評判準(zhǔn)則

不可展曲面的展開不可避免地會發(fā)生變形.角度誤差、面積誤差和邊長誤差都可以作為衡量展開精度的衡量標(biāo)準(zhǔn).在這里,主要考慮面積誤差和邊長誤差.在曲面展開過程中,原始曲面和展開平面的面積會有所不同,而三角形網(wǎng)格上的邊長也會發(fā)生變化,其相對面積誤差(eS)和相對形變誤差(eL)[8-9]為

式(9)中:S是曲面片展開前的實際面積;S′是曲面展開后所對應(yīng)的的面積;L為曲線段在展開前的實際長度;L′是展開后曲線段所對應(yīng)的長度.

2 曲面展開

2.1 初始曲面的展開

2.1.1 不含能量釋放的展開 無約束和有約束的三角片的展開,如圖2,3所示.

圖2 無約束的三角面片展開Fig.2 Unconstrained triangle flattening

圖3 有約束的三角面片展開Fig.3 Constrained triangle flattening

由圖2可知,P1P2是三角面片T1和T的共邊.當(dāng)三角面片T1已經(jīng)展開,而三角面片T未展開.即T的兩個點P1和P2的位置已經(jīng)在二維平面確定(即P′1和P′2),而點P3在二維平面的位置尚未確定時,以P′1和P′2為圓心的兩個圓的交點來確定(圓的半徑分別為r1,3和r2,3)點P′3的位置,r1,3和r2,3的長度即為它們在空間網(wǎng)格上的長度,所有點的第1次展開都是以無約束方法得到的.

包含點P3的三角面片有多個,由這些三角形面片展開的P3的點位置也有多個.當(dāng)曲面是可展曲面時,所求的這些點位置是一致的.當(dāng)曲面是不可展曲面時,這些點位置有可能不一致.此時,會有層疊和裂縫的現(xiàn)象產(chǎn)生,影響曲面展開的精度,甚至曲面展開的獲得.一般所展開的曲面大部分是不可展曲面,所以必須考慮帶約束的三角片展開.

由圖3可知,假設(shè)包含P3點的三角片T2已展開,這時P3在由已展開T2所決定的二維平面中的位置為P′3.若不采取有約束的展開方法,當(dāng)繼續(xù)展開T時,由T展開時所決定的P3的位置為P″3.很明顯,這兩點的位置并不一致.為了使P3在二維平面具有唯一性,可以取兩點的平均位置作為P3在二維平面的對應(yīng)點來初步解決這個問題.

但是,此方法肯定有相當(dāng)大的誤差,將會產(chǎn)生彈性能量,導(dǎo)致層疊或裂縫現(xiàn)象的發(fā)生,必須采取適當(dāng)?shù)姆椒▉肀M可能地減少這個誤差.對此,可以采取能量釋放方法來初步減少誤差.

2.1.2 含能量釋放的方法 在對三角片進(jìn)行有約束的展開時,為了使展開點具有唯一性,可采取平衡位置的方法.這樣所造成的后果是原始曲面的曲線長度與其展開后的長度存在很大的誤差,使得面積誤差和形狀誤差很大,不利于曲面的精確展開.通過釋放在位置平均處理過程中產(chǎn)生的彈性能量,可以解決這個問題.

曲面上所有網(wǎng)格化三角形根據(jù)上述無約束展開或約束展開方法展開為平面三角形后,得到曲面的初始展開平面網(wǎng)格;然后,用式(5)計算三角網(wǎng)格上的每個點的能量,通過釋放能量來改善展開的平面.如果整張展開網(wǎng)格曲面有m個離散點,則所有離散點的展開變形能為

展開變形能的大小反映曲面整體展開變形程度.為了減小展開的變形,需要能最大程度地減小變形能,釋放變形能.

2.2 能量展開算法

能量展開算法主要有如下7個步驟.

(1)建立3個集合V,A和F.V為包含所有尚未展開的曲面三角形的集合;A為有序活動集合,即從集合V中挑選出來的三角形集合,這些三角形是與已展開三角形共邊而將要被展開的三角形;F為所有已展開到二維平面的三角形集合.對這3個集合進(jìn)行初始化,把所有要展開的空間三角形添加到集合V中,置集合A和F為空.

(2)從V集中選擇展開基本三角形T0.一般在曲面的對稱中心或曲率較大的部位選擇該三角面片,然后將其無約束展開在平面上任意位置,并將該基本三角形從V中刪除,直接加入到F中.

(3)在V集中尋找與基本三角形T0共邊的所有三角形{Ti}.將這些三角形加入到A集中,并從V中減去.

(4)判斷A集是否為空.如果A集不為空,則從A集中取出下一個三角形Ti,并按步驟(5)或步驟(6)的方法展開;如果A集為空,則判斷V集是否為空;如果V集為空,則轉(zhuǎn)到步驟(7)執(zhí)行;否則,轉(zhuǎn)到步驟(3)執(zhí)行.

(5)如果三角形的第3點還沒有展開(其余兩點已在展開集F的某個三角形中),此時采用三角形無約束展開,并將三角形Ti加入到展開集F中;然后,從A中減去Ti,轉(zhuǎn)到步驟(4).

(6)如果三角形Ti的第3點在前面的三角形展開中已經(jīng)展開,并形成平面三角形,則用三角形約束展開方法進(jìn)行展開.處理后,將三角形Ti加入到展開集F中,從A中減去,然后轉(zhuǎn)到步驟(4).

(7)分別計算面積誤差eS和形變誤差eL,以及所有離散點的展開變形能E(φ′),判斷其值是否是在閥值內(nèi).若誤差都小于閥值,則說明已得到優(yōu)化的曲面展開;若誤差大于閥值,則回到步驟(3)重新進(jìn)行能量釋放,直到超過迭代次數(shù)N為止.

3 應(yīng)用實例

算法已通過VC 6.0編程在微機(jī)上實現(xiàn),圖4是用能量模型所作的曲面展開示例.該曲面有189個頂點,306個三角形.

當(dāng)時間初始步長dt=0.6時,如果在迭代中不采取改變時間步長的方法,很容易出現(xiàn)發(fā)散;而采取改進(jìn)算法后,面積誤差為1.455%,形變誤差為0.988%,基本符合精度要求.

當(dāng)時間初始步長dt=0.3時,如果在迭代中不采取改變時間步長的話,雖然不會出現(xiàn)發(fā)散的情況,但其面積誤差為4.668%,形變誤差為2.456%,展開質(zhì)量不是很好.

圖4 曲面展開實例Fig.4 Example of surface flattening

4 結(jié)束語

運(yùn)用能量模型的展開算法,可以很好地解決一般的曲面展開問題,而且計算量較小,不需要解大規(guī)模線性方程組.絕大部分的曲面可以三角網(wǎng)格化,所以能量模型算法具有很強(qiáng)的通用性.在實驗結(jié)果中發(fā)現(xiàn),時間步長、彈性系數(shù)和面密度都直接影響到曲面展開的質(zhì)量.改進(jìn)算法主要研究時間步長對算法的影響,而下一階段的目標(biāo)是考慮以上3個參數(shù)的合理配取,以期達(dá)到更好的展開結(jié)果.

[1]席平.三維曲面的幾何展開[J].計算機(jī)學(xué)報,1997,20(4):315-322.

[2]毛國棟,孫炳楠,徐浩祥.基于彈簧-質(zhì)點系統(tǒng)的薄膜結(jié)構(gòu)曲面展開算法[J].浙江大學(xué)學(xué)報:工學(xué)版,2005,39(8): 1238-1242.

[3]王弘,王昌凌.基于能量模型的曲面展開通用算法[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報,2001,13(6):556-560.

[4]梁偉文.基于彈性模型的三角網(wǎng)格曲面優(yōu)化展開[J].塑性工程學(xué)報,2007,14(1):129-132.

[5]雷軍鵬.一種基于能量法的自由曲面展開算法[J].機(jī)械設(shè)計與制造,2007(4):28-30.

[6]徐榮璋,劉曉毅,陳軍.曲面展開方法的發(fā)展現(xiàn)狀[J].模具技術(shù),2002(5):15-18.

[7]楊繼新,劉健,肖正揚(yáng).可展面在平面上的展開及其在工程上的應(yīng)用[J].機(jī)械科學(xué)與技術(shù),2001,20(5):201-202.

[8]SH IMADA T,TADA Y.Development of curved surface using finite element method[M].New York:Sp ringer-Verlag,1989:23-30.

[9]M ETAXASD N.Physics-based deformable models:Applications to computer vision,graphics,and medical imaging[M].Boston:Kluwer Academic Publishers,1997.

(責(zé)任編輯:陳志賢英文審校:鄭亞青)

An Improved Algorithm for Surface Flattening Based on Energy Model

YAN Guo-biao,L IU Bin
(College of Mechanical Engineering and Automation,Huaqiao University,Quanzhou 362021,China)

In allusion to occurring problems of existing algorithm s,an imp roved algorithm of surface flattening based on energy-model is presented.The imp roved algorithm is mainly to adjust time-step to avoid divergent phenomenon in the course of flattening,at the same time enhance the quality of the flattened surface,and better eliminate oscillating phenomena caused by too many iterative numbers.The results of case study have show n that the imp roved algorithm is effective, and can conform to the requirement of real-time and interactive design.

surface flattening;energy-model;time-step;triangular mesh

TP 391.7

A

1000-5013(2011)02-0135-05

2009-11-12

劉斌(1972-),男,副教授,主要從事聚合物材料模塑成型的研究.E-mail:mold_bin@hqu.edu.cn.

福建省科技計劃重點項目(2009H0032);福建省自然科學(xué)基金資助項目(E0810040);國務(wù)院僑辦科研基金資助項目(08QZR01)