行開新， 田 凌， 童秉樞

（清華大學(xué)精密儀器及機(jī)械學(xué)系，北京 100084）

隨著網(wǎng)絡(luò)技術(shù)的發(fā)展和全球化進(jìn)程的不斷推進(jìn)，協(xié)同設(shè)計成為企業(yè)縮短設(shè)計周期，增強(qiáng)競爭力的有效手段。傳統(tǒng)CAD零件模型體積龐大，現(xiàn)有網(wǎng)絡(luò)條件下很難進(jìn)行遠(yuǎn)程異地的傳輸，不同CAD系統(tǒng)的零件模型格式又互不兼容，因此傳統(tǒng)模型格式其無法實(shí)現(xiàn)對異地協(xié)同設(shè)計和跨CAD平臺設(shè)計的支持。VRML模型具有標(biāo)準(zhǔn)化、造型逼真、交互性強(qiáng)以及體積小等諸多優(yōu)點(diǎn)；同時，大多數(shù)CAD軟件均提供了VRML格式輸出接口。因此，VRML模型提供了適合在 Internet上可視化顯示和操縱不同CAD系統(tǒng)產(chǎn)生的零件模型的理想方式[1]。

用于協(xié)同設(shè)計的 VRML環(huán)境與普通的網(wǎng)絡(luò)三維 VRML環(huán)境有所不同，前者除了需要詳細(xì)的外形表述外，還需要相關(guān)的設(shè)計特征參數(shù)。目前在協(xié)同設(shè)計方面對 VRML的研究主要集中在實(shí)時交互處理[2]及三維模型的優(yōu)化[3]。對于復(fù)雜的產(chǎn)品零部件模型 VRML都是采用三角面片造型方式，其設(shè)計特征參數(shù)無法從模型本身直接獲得。對于這個問題，當(dāng)前主要方法是在模型之外附加零件特征信息[4-5]，但這無疑增加了協(xié)同設(shè)計尤其是異地協(xié)同設(shè)計的網(wǎng)絡(luò)負(fù)擔(dān)。因此對VRML模型的設(shè)計信息進(jìn)行重建，使設(shè)計者能夠進(jìn)行完善的協(xié)同設(shè)計，是基于 VRML協(xié)同設(shè)計亟待解決的問題。

通過調(diào)查發(fā)現(xiàn)，零件裝配特征中，90%為平面和回轉(zhuǎn)體（如圓柱面，圓錐面，球面等）?；剞D(zhuǎn)體在機(jī)械模型設(shè)計特征中約占70%，其特征參數(shù)（如回轉(zhuǎn)中心，回轉(zhuǎn)半徑等）在設(shè)計過程中有重要意義。本文對這些特征信息的重建進(jìn)行了研究，提出變步長同步移動搜索算法，并對其計算效率及復(fù)雜度進(jìn)行了分析驗(yàn)證。

1 算法中的若干定義

VRML模型是一個表面模型，它由一系列（平）面片包圍形成，一個面片可包含多個頂點(diǎn)。為了確保所有頂點(diǎn)位于一個平面上，CAD系統(tǒng)輸出 VRML模型時常將模型表面分解為一系列具有鄰接關(guān)系的三角面片，一個 VRML模型可表示為

各點(diǎn)及矢量的關(guān)系如圖1所示。

圖1 VRML模型面片定義

2 算法描述

VRML模型將設(shè)計特征中的圓柱、圓錐回轉(zhuǎn)體分別離散成了由若干三角面片構(gòu)成的正棱柱和正棱臺，而球體則被離散成為了多段正棱臺組成的近似球體，各種回轉(zhuǎn)體垂直軸線的截平面形狀均為正多邊形，如圖2所示。計算回轉(zhuǎn)中心時，初始條件選取設(shè)計模型的一個頂面定位點(diǎn)0P和3個側(cè)面定位點(diǎn)同時獲得四點(diǎn)所在面片的法向量n0, n1, n2, n3，3個側(cè)面點(diǎn)屬于不同的三角面片單元。算法主要思想是首先將不在同一平面的映射到與 n0垂直的平面內(nèi)，由VRML模型的幾何特征可知，投影后的點(diǎn)在以回轉(zhuǎn)中心為圓心，以回轉(zhuǎn)半徑為外切圓半徑的正多邊形的弦上。通過算法將投影后的各點(diǎn)移至各自所在弦的中點(diǎn)，進(jìn)而計算回轉(zhuǎn)中心及回轉(zhuǎn)半徑。其具體步驟如下：

Step 1 投影各點(diǎn)

根據(jù)柱面，錐面和球面的不同特點(diǎn)，將側(cè)面的3個點(diǎn)投影到P1所在的垂直于軸線n0的面Φ上，投影后的各點(diǎn)為P1, P2', P3'，并求出投影后的單位法向量n1, n2', n3'，如圖2所示。

圖2 將側(cè)面點(diǎn)映射到同一平面Φ上

Step 2 計算邊向量

計算P1, P2', P3'三個點(diǎn)所在的邊的單位向量Tp1, Tp2, Tp3，如式(1)所示

Step 3 確定初始搜索步長

選擇P1, P2', P3'組成的三角形中最長邊長為初始搜索步長τ。

圖3 投影后的截面

Step 4 移動點(diǎn)P2'

根據(jù)P1P2'與對應(yīng)兩條邊的法向量n1, n2'的夾角,α β的關(guān)系在P2'所在的邊上移動P2'，如圖3所示。由式(2)計算得到cosα,cosβ。

若前后兩次計算cosα, cosβ大小關(guān)系發(fā)生變化，則首先將搜索步長變?yōu)樵瓉淼?/10，之后再移動P2'。重復(fù)本步驟直到步長τ 小于要求的精度值或cosα, cosβ相等。

Step 5 移動點(diǎn)P3'

使用類似Step 3和Step 4的方法，根據(jù)P2'P3'和n2', n3'的關(guān)系，移動P3'。

Step 6 同步移動P1, P2', P3'三點(diǎn)

根據(jù)P1P3'和對應(yīng)兩條邊的法向量n1, n3'夾角,γ δ的關(guān)系在P1, P2', P3'所在的邊上移動三點(diǎn)。首先計算兩個角的余弦cosγ,cosδ

若cosγ＞cosδ，則1P,P2',P3'分別向-Tp1, Tp2,-Tp3方向移動τ

若cosγ＜cosδ，則1P,P2',P3'分別向Tp1, -Tp2,Tp3方向移動τ

若前后兩次計算cosγ,cosδ大小關(guān)系發(fā)生變化，則首先將搜索步長變?yōu)樵瓉淼?/10，之后再移動三點(diǎn)。重復(fù)本步驟直到步長τ小于要求的精度值或cosγ,cosδ相等。

通過上述移動后，1P, P2', P3'各點(diǎn)均位于所在邊的中點(diǎn)，以下根據(jù)幾何關(guān)系計算相應(yīng)的回轉(zhuǎn)特征參數(shù)，如圖4所示。

圖4 計算回轉(zhuǎn)中心等參數(shù)

Step 7 計算回轉(zhuǎn)中心

設(shè)回轉(zhuǎn)中心為cP，根據(jù)幾何關(guān)系可知點(diǎn)cP和1P,2P′滿足式(8)所示關(guān)系，由此求得回轉(zhuǎn)中心。

Step 8 計算回轉(zhuǎn)半徑

根據(jù)式(9)中關(guān)系可得到截面多邊形的某一頂點(diǎn)PA

由式(10)即可計算得到回轉(zhuǎn)半徑

3 算法復(fù)雜度分析

本算法完全基于向量空間，初始條件僅需要少量局部 VRML模型信息，采用變步長搜索比較方式自適應(yīng)性強(qiáng)，降低了計算和迭代次數(shù)，易于實(shí)現(xiàn)，計算效率高。為了進(jìn)一步分析該算法的計算性能，設(shè)計了以下實(shí)驗(yàn)。

在初始條件相同的條件下，實(shí)驗(yàn)選用已知回轉(zhuǎn)中心為Z軸，主軸最細(xì)處直徑為6mm的階梯軸VRML模型，如圖5所示。該模型由5525個面片組成，其回轉(zhuǎn)部分由正 22棱柱近似圓柱回轉(zhuǎn)體。計算所得的回轉(zhuǎn)中心精度取決于算法所采用的最小搜索步長，最小步長也決定著系統(tǒng)的迭代次數(shù)和計算效率。

圖5 階梯傳動軸

實(shí)驗(yàn)選擇了 0.00001、0.00005、0.0001、0.0005、0.001、0.005、0.01、0.05、0.1等 9個值作為最小搜索步長分別進(jìn)行測試，所選值分布在0.00001～0.1，約為軸直徑的0.00017%～1.67%。針對每個最小搜索步長分別用四組點(diǎn)做測試。此處定義絕對誤差的計算公式為式(11)

測得隨著迭代步長的增加，迭代次數(shù)和迭代誤差分布情況分別如圖6和圖7所示。

通過實(shí)驗(yàn)結(jié)果可以看出其分布具有以下規(guī)律：

（1）隨著最小搜索步長的增大，算法的誤差也隨之增大。不同組的數(shù)據(jù)計算結(jié)果的誤差不同，但是都分布在坐標(biāo)系45°線的附近或者下側(cè)。由此看出，計算誤差整體上和最小搜索步長成正比關(guān)系。同樣的結(jié)論也可以通過圖4的幾何關(guān)系推導(dǎo)出來：從圖上可以看出，圓心點(diǎn)的誤差和弦中點(diǎn)的誤差成近似正比關(guān)系。

圖6 迭代次數(shù)變化情況

圖7 迭代誤差分布情況

（2）隨著最小搜索步長的減小，算法的搜索迭代次數(shù)不斷增加，但是可以看出，搜索最小搜索步長變?yōu)樵瓉淼?/10，搜索迭代次數(shù)僅增加10～30次，迭代次數(shù)增加遠(yuǎn)遠(yuǎn)慢于搜索步長的減小。

（3）不同組的數(shù)據(jù)計算出來的誤差和迭代次數(shù)差異比較大。計算誤差雖然在坐標(biāo)系 45°線附近分布較多，但是有少數(shù)分布在較下側(cè)；最小搜索步長不變的條件下，算法的迭代次數(shù)也會出現(xiàn)差異。這是由于搜索算法本身的特點(diǎn)決定的，搜索算法是在一定的范圍內(nèi)進(jìn)行搜索，因此，實(shí)際點(diǎn)離邊界點(diǎn)的遠(yuǎn)近就導(dǎo)致了搜索迭代次數(shù)的差異；計算誤差也一樣，計算結(jié)果只是最后一次搜索的邊界值，而實(shí)際點(diǎn)離該邊界的遠(yuǎn)近直接影響著迭代誤差的大小。

（4）綜上，可以看出迭代步長是算法效率和精度的重要指標(biāo)，隨著迭代步長的增大，迭代次數(shù)呈下降趨勢，迭代誤差總體呈上升趨勢。所以迭代步長的選取可以根據(jù)迭代次數(shù)和迭代誤差的分布規(guī)律來綜合考慮，使算法既具備很好的計算效率又具備很好的精度。

4 算法應(yīng)用

本文所述方法為協(xié)同瀏覽尺寸信息查詢、協(xié)同裝配模型定位等協(xié)同設(shè)計過程提供了重要的特征參數(shù)信息，是 VRML環(huán)境下實(shí)現(xiàn)深層次協(xié)同設(shè)計操作的基礎(chǔ)。目前，該算法已經(jīng)應(yīng)用于一些協(xié)同設(shè)計系統(tǒng)，如協(xié)同虛擬裝配系統(tǒng)、協(xié)同瀏覽批注系統(tǒng)[6]等。圖8為利用本文介紹的裝配特征信息重建方法開發(fā)的協(xié)同虛擬裝配系統(tǒng)進(jìn)行某型號萬向節(jié)總成的虛擬裝配，裝配過程中只需要分別依次選擇零件和裝配體回轉(zhuǎn)特征上的4個點(diǎn)就可以實(shí)現(xiàn)以零件的裝配。實(shí)際使用表明該方法計算效率和計算結(jié)果均滿足協(xié)同設(shè)計的要求。

圖8 利用本文算法進(jìn)行虛擬裝配

5 結(jié) 論

在基于Web設(shè)計應(yīng)用越加深入的背景下，本文提出了變步長移動搜索算法，該算法能夠利用少量局部 VRML模型信息通過搜索迭代方法實(shí)時高效地計算各種回轉(zhuǎn)體特征的參數(shù)信息，對VRML零件回轉(zhuǎn)體裝配特征進(jìn)行信息重建。此外，該算法計算初始條件少，自適應(yīng)性強(qiáng)，亦適用于其它網(wǎng)格模型的數(shù)據(jù)信息提取。

[1]Ando H, Kubota A, Kiriyama T. Study on the collaborative design process over the Internet: a case study on VRML 2.0 specification design [J]. Design Studies, 1998, 19(3): 289-308.

[2]周自強(qiáng), 沈連婠, 趙 瑋, 等. 基于Web的虛擬設(shè)計中VRML實(shí)時模型的可交互處理方法[J]. 計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報, 2005, 17(16): 1371-1377.

[3]Jeong-Hwan Ahn, Chang-Su Kim, Yo-Sung Ho. An efficient coding algorithm for color and normal data of three-dimensional mesh models [C]//IEEE International Conference on Image Processing,Barcelona, 2003: 789-792.

[4]劉檢華, 姚 珺, 寧汝新. CAD 系統(tǒng)與虛擬裝配系統(tǒng)間的信息集成技術(shù)研究[J]. 計算機(jī)集成制造系統(tǒng),2005, 11(1): 44-47, 67.

[5]蘇 艷, 廖文和, 郭 宇. 面向虛擬裝配的 VRML模型優(yōu)化重構(gòu)[J]. 計算機(jī)工程與設(shè)計, 2007, 28(11):2509-2512, 2722.

[6]Tian Ling, Chen Jizhong, Wang Qiaoyu, et al.CoDesign space: a collaborative design support system in a network environment [J]. International Journal of Computer Integrated Manufacturing, 2007,20(2-3): 265-279.