基于小波技術(shù)的曲面邊界光順及簡化算法

何 川，趙 罡，王愛增

(1.北京航空航天大學(xué)機(jī)械工程及自動(dòng)化學(xué)院，北京 100191；2.北京航空航天大學(xué)虛擬現(xiàn)實(shí)技術(shù)與系統(tǒng)國家重點(diǎn)實(shí)驗(yàn)室，北京 100191)

自由曲線曲面在計(jì)算機(jī)輔助設(shè)計(jì)(computer-aided design，CAD)和計(jì)算機(jī)輔助制造(computer aided manufacturing，CAM)中發(fā)揮著重要作用[1-4]。其中，非均勻有理 B 樣條(non-uniform rational B-splines，NURBS)已成為CAD 中表示產(chǎn)品幾何外形的標(biāo)準(zhǔn)形式。相比于網(wǎng)格建模，NURBS 曲線曲面具有較好的參數(shù)連續(xù)性與光順性，其在3D 建模等領(lǐng)域應(yīng)用廣泛?；趯?duì)有理曲線曲面的細(xì)分區(qū)間估計(jì)[5]，LI 等[6]提出了一種基于GPU 的NURBS 曲面自適應(yīng)細(xì)分方法，與基于CPU 的方法相比，算法性能有了明顯提高，便于實(shí)時(shí)渲染復(fù)雜的NURBS模型。DBSCs (disk B-spline curves)是一類擴(kuò)展的B樣條曲線，近年來，AO 等[7]提出了求DBSCs 之間所有二維相交區(qū)域的方法，為DBSCs 在計(jì)算機(jī)二維動(dòng)畫領(lǐng)域的廣泛應(yīng)用提供了理論基礎(chǔ)。文獻(xiàn)[8-10]關(guān)于NURBS 正則曲線曲面[11]的理論也為曲面變形、計(jì)算機(jī)動(dòng)畫提供了潛在的應(yīng)用基礎(chǔ)。

遺憾的是，B 樣條曲面只能在矩形網(wǎng)格上定義(圖1)?？刂祈旤c(diǎn)的矩形拓?fù)浣Y(jié)構(gòu)使得B 樣條曲面具有一定的局限性，特別是在處理局部細(xì)分、曲面拼接和設(shè)計(jì)的靈活性方面(圖2)，具有很大挑戰(zhàn)。針對(duì)這些問題，SEDERBERG 等[12-13]提出了T 樣條的概念，在NURBS 的基礎(chǔ)上進(jìn)行了改進(jìn)，且仍與NURBS 系統(tǒng)兼容。與B 樣條曲面不同，T 樣條曲面可以定義在非矩形拓?fù)浣Y(jié)構(gòu)上(圖3)，允許T 型節(jié)點(diǎn)、L 型節(jié)點(diǎn)甚至I 型節(jié)點(diǎn)。非矩形拓?fù)浣Y(jié)構(gòu)使得T 樣條曲面比B 樣條曲面具有更多優(yōu)勢，在局部細(xì)分、數(shù)據(jù)壓縮和曲面拼接(圖4)時(shí)更加方便。

圖1 B-mesh 拓?fù)浣Y(jié)構(gòu) Fig.1 B-mesh topology

圖2 B 樣條曲面的局部加細(xì)((a)插入一個(gè)控制點(diǎn)；(b)最終的矩形拓?fù)浣Y(jié)構(gòu)) Fig.2 Local refinement of B-spline surfaces ((a) Inserting one control point;(b) The final rectangular topology)

圖3 非矩形拓?fù)浣Y(jié)構(gòu) Fig.3 Non-rectangular topology

圖4 T 樣條曲面的局部加細(xì)((a)插入一個(gè)控制點(diǎn)；(b)最終的非矩形拓?fù)浣Y(jié)構(gòu)) Fig.4 Local refinement of T-spline surfaces ((a) Inserting one control point;(b) The final non-rectangular topology)

小波分析是一種數(shù)學(xué)工具，具有良好的濾波特性，在信號(hào)和圖像處理以及計(jì)算機(jī)輔助設(shè)計(jì)等領(lǐng)域都有著廣泛地應(yīng)用。其中，非均勻B 樣條小波常被用于曲線和曲面的多分辨建模與幾何處理中[14-18]。參考文獻(xiàn)[15]構(gòu)造了非均勻B 樣條小波，并給出了相應(yīng)的分解和重構(gòu)算法。非均勻B 樣條小波基于非均勻節(jié)點(diǎn)矢量，可直接用于NURBS 曲線曲面的建模和編輯。

在CAD 中，邊界區(qū)域?qū)φw造型的形狀有著重要影響，在產(chǎn)品設(shè)計(jì)中需要首先對(duì)邊界區(qū)域的形狀進(jìn)行良好地控制。在交互設(shè)計(jì)中，設(shè)計(jì)者希望將注意力集中在局部邊界區(qū)域的形狀上，而保持其他部分形狀不變。然而，根據(jù)矩形拓?fù)浣Y(jié)構(gòu)[14,16-18]的要求，基于B-mesh 的曲面邊界光順方法通常包含冗余控制點(diǎn)(圖5(c))，且一些控制點(diǎn)對(duì)幾何形狀沒有實(shí)質(zhì)性貢獻(xiàn)。如何減少NURBS 曲面邊界光順時(shí)包含的冗余控制點(diǎn)成為亟待解決的問題。

本文利用非矩形拓?fù)渚W(wǎng)格和B 樣條小波，提出了一種基于T-mesh 的曲面邊界光順?biāo)惴?。與文獻(xiàn)[14]和[16-18]方法相比，新算法經(jīng)過曲面重構(gòu)形成的T樣條曲面(圖5(d))，在光順后具有更少的控制點(diǎn)。

圖5 曲面邊界光順((a)初始B-mesh；(b)選定的一條邊界；(c)傳統(tǒng)方法的邊界光順；(d)基于T-mesh 的邊界光順) Fig.5 Surface boundary shape fairing ((a) Original B-mesh;(b) Selected one boundary part;(c) Boundary fairing by traditional methods;(d) Boundary fairing based on T-mesh)

1 B 樣條小波分解技術(shù)

1.1 傳統(tǒng)小波變換

與經(jīng)典的傅里葉變換相比，傳統(tǒng)小波變換是對(duì)空間/時(shí)間頻率的局部化分析，利用二進(jìn)伸縮與平移，對(duì)函數(shù)進(jìn)行多尺度細(xì)化。小波分析的基本思想是將給定的尺度空間用一個(gè)低分辨空間VL-1(尺度空間)和一個(gè)高分辨空間WL-1(小波空間)表示。傳統(tǒng)小波性質(zhì)如下：

1.2 B 樣條小波分解

與傳統(tǒng)小波變換相比，B 樣條小波是廣泛應(yīng)用于CAD 領(lǐng)域的新型小波變換技術(shù)。

d次B 樣條曲線為

其中，Ci(0≤i≤n)為B 樣條曲線的控制點(diǎn)；Ni,d(t) (0≤i≤n)為節(jié)點(diǎn)矢量t定義的d次B 樣條基函數(shù)。

根據(jù)文獻(xiàn)[15]，構(gòu)造非均勻B 樣條小波步驟如下：

(1) 選擇初始尺度空間VL；

(2) 在尺度空間VL內(nèi)定義任意2 個(gè)函數(shù)的內(nèi)積；

(3) 選擇子空間VL-1和小波空間WL-1。

本文假定

通過B 樣條小波分解[15]，式(2)定義的曲線可以表示為

圖6 給出了具有34 個(gè)控制點(diǎn)的三次非均勻B樣條Face-shape 曲線對(duì)應(yīng)的B 樣條小波分解結(jié)果。經(jīng)過一次B 樣條小波變換，得到了僅含12 個(gè)控制點(diǎn)的光順曲線，如圖6(c)和(d)所示。由光順前后曲線的曲率梳可知，B 樣條小波分解不僅減少了曲線的控制點(diǎn)個(gè)數(shù)，而且優(yōu)化了曲線的曲率分布。

圖6 Face-shape 曲線((a)原始曲線；(b)原始曲線對(duì)應(yīng)的曲率梳；(c)光順曲線；(d)光順曲線對(duì)應(yīng)的曲率梳) Fig.6 Face-shape curve ((a) Original curve;(b) Associated curvature comb;(c) Fairing curve; (d) Associated curvature comb)

1.3 T 樣條技術(shù)

與NURBS 相比，T 樣條曲面在局部細(xì)分、曲面拼接和數(shù)據(jù)壓縮等方面具有優(yōu)勢[10-11]。T 樣條曲面定義在非矩形拓?fù)浣Y(jié)構(gòu)的T-mesh 上(圖7(a))，并允許T 型節(jié)點(diǎn)和L 型節(jié)點(diǎn)[10-11]。本質(zhì)上，B-mesh是一種特殊的T-mesh。

d次T 樣條曲面可表示為[10-11]

其中，di為控制點(diǎn)；Ti(u,v)為di對(duì)應(yīng)的調(diào)配函數(shù)。與NURBS 曲面不同，T 樣條曲面的調(diào)配函數(shù)可以從T-mesh 的局部拓?fù)浣Y(jié)構(gòu)推斷出來(圖7(b))，即

圖7 T 樣條曲面的拓?fù)浣Y(jié)構(gòu)及調(diào)配函數(shù) ((a) T-mesh 拓?fù)浣Y(jié)構(gòu)；(b) T 樣條調(diào)配函數(shù)) Fig.7 The topology and blending function of T-spline ((a) T-mesh topology;(b) T-spline blending function)

其中，Ni(u)和Ni(v)為B 樣條基函數(shù)，根據(jù)特定的規(guī)則，其對(duì)應(yīng)的節(jié)點(diǎn)矢量依賴于T-mesh 拓?fù)浣Y(jié)構(gòu)[10-11]。

2 NURBS 曲面邊界光順及簡化算法

對(duì)NURBS 曲面邊界進(jìn)行光順，重建一個(gè)非矩形拓?fù)浣Y(jié)構(gòu)的T 樣條曲面，算法流程如圖8 所示。對(duì)于給定的原始NURBS 曲面，選取待光順的邊界區(qū)域，并利用非均勻B 樣條小波進(jìn)行分解，保留尺度部分，隨后通過T 樣條技術(shù)對(duì)結(jié)果進(jìn)行簡化，得到最終的非矩形拓?fù)浣Y(jié)構(gòu)的曲面。

圖8 曲面邊界區(qū)域光順及簡化算法 Fig.8 Fairing and simplification algorithm of surface boundary shape

NURBS 曲面邊界光順及簡化的過程步驟如下：

步驟1.給出原始曲面(圖9)；

圖9 原始曲面 Fig.9 Original surface

步驟2.選擇原始曲面的邊界區(qū)域(圖10)；

圖10 邊界區(qū)域選擇 Fig.10 Selected boundary shape topology

步驟3.對(duì)原始邊界區(qū)域進(jìn)行B 樣條小波分解(圖11)；

圖11 邊界區(qū)域的小波分解((a)原始拓?fù)浣Y(jié)構(gòu)；(b)尺度部分拓?fù)浣Y(jié)構(gòu)) Fig.11 Wavelet decomposition of the boundary shape ((a) Boundary shape;(b) The scale part by wavelet decomposition)

步驟4.通過T-mesh 重建曲面(圖12)；

圖12 光順及簡化后的邊界區(qū)域 Fig.12 The final result with the faired and simplified boundary shape

與文獻(xiàn)[14]和[16-18]算法相比，本文新算法允許存在非矩形拓?fù)浣Y(jié)構(gòu)的T 樣條曲面，其大大減少了曲面邊界光順之后的控制點(diǎn)個(gè)數(shù)。對(duì)于傳統(tǒng)文獻(xiàn)[14]和[16-18]方法，邊界區(qū)域可以進(jìn)行局部光順，但邊界區(qū)域的控制點(diǎn)個(gè)數(shù)不能減少，由于這些方法要求曲面具有矩形拓?fù)浣Y(jié)構(gòu)，因此無法獲得邊界區(qū)域的數(shù)據(jù)簡化。

3 實(shí) 例

通過2 個(gè)例子來說明本文算法的優(yōu)勢。例1 是Column-shape 曲面，其為三次B 樣條曲面，有441個(gè)控制點(diǎn)。圖13(a)中的紅色實(shí)線是選擇的邊界部分，綠色實(shí)線是對(duì)應(yīng)的曲率梳。由光順前后邊界曲線的曲率梳(圖13(a)和(c))可知，光順后的邊界曲線，曲率單調(diào)段數(shù)比原始曲線要少得多。本文算法將原始曲面的邊界曲線變得更加光順，且含12 個(gè)控制點(diǎn)(圖13(a)～13(d))。

圖13 Column-shape 曲面的邊界光順及簡化 ((a) Column-shape 曲面。原始邊界曲線(紅色實(shí)線)有21 個(gè)控制點(diǎn)，綠色實(shí)線是對(duì)應(yīng)的曲率梳；(b)原始拓?fù)浣Y(jié)構(gòu)；(c)用本文算法進(jìn)行邊界光順。光順邊界曲線(紅色實(shí)線) 有12 個(gè)控制點(diǎn)，綠色實(shí)線是對(duì)應(yīng)的曲率梳；(d)新的拓?fù)浣Y(jié)構(gòu)) Fig.13 Boundary fairing and simplification of a Column-shape surface ((a) Column-shape surface.The original boundary shape (red solid line) has 21 control points,and the green solid line is the corresponding curvature comb;(b) Original topology; (c) Boundary shape fairing by the new algorithm.The fairing boundary shape (red solid line) has 12 control points,and the green solid line is the corresponding curvature comb;(d) New topology)

例2 是Mountain-shape 曲面，其是具有121 個(gè)控制點(diǎn)的三次B 樣條曲面。圖14(a)中的紅色實(shí)線是選擇的邊界部分，綠色實(shí)線是對(duì)應(yīng)的曲率梳。由圖14(a)和(c)可知，光順后的邊界曲線比原邊界曲線具有更少的曲率單調(diào)段?；谛滤惴?，采用7個(gè)控制點(diǎn)對(duì)原曲面的邊界曲線進(jìn)行了光順和簡化(圖14(a)～(d))。由光順前后的高光圖可知，控制點(diǎn) 個(gè)數(shù)的減少對(duì)曲面形狀產(chǎn)生了一定的影響，但差異不大。對(duì)曲面進(jìn)行簡化時(shí)，剔除冗余點(diǎn)越多，結(jié)果越偏離原形狀，因此需要在保證形狀基本不變的前提下，對(duì)曲面進(jìn)行簡化。

圖14 Mountain-shape 曲面的邊界光順及簡化 ((a) Mountain-shape 曲面。原始邊界曲線(紅色實(shí)線)有11個(gè)控制點(diǎn)，綠色實(shí)線是對(duì)應(yīng)的曲率梳；(b)原始拓?fù)浣Y(jié)構(gòu)；(c)用本文算法進(jìn)行邊界光順。光順邊界曲線 (紅色實(shí)線)有7 個(gè)控制點(diǎn)，綠色實(shí)線是對(duì)應(yīng)的曲率梳；(d)新的拓?fù)浣Y(jié)構(gòu)) Fig.14 Boundary fairing and simplification of a Mountain -shape surface ((a) Mountain -shape surface.The original boundary shape (red solid line) has 11 control points,and the green solid line is the corresponding curvature comb; (b) Original topology; (c) Boundary shape fairing by the new algorithm.The fairing boundary shape (red solid line) has 7 control points,and the green solid line is the corresponding curvature comb;(d) New topology)

傳統(tǒng)文獻(xiàn)[14]和[16-18]方法由于受矩形拓?fù)浣Y(jié)構(gòu)的限制，無法得到最終的邊界數(shù)據(jù)簡化結(jié)果。文獻(xiàn)[14]采用非均勻B 樣條小波對(duì)NURBS 曲線曲面進(jìn)行光順與簡化，在簡化后需要重新調(diào)整邊界控制點(diǎn)，無法局部壓縮邊界控制點(diǎn)的個(gè)數(shù)。本文方法則能夠?qū)Ψ蔷匦瓮負(fù)浣Y(jié)構(gòu)的曲面邊界區(qū)域進(jìn)行光順，利用T 樣條技術(shù)進(jìn)一步得到控制點(diǎn)簡化后的模型。

4 結(jié)束語

本文提出了一種基于T樣條與小波技術(shù)的曲面邊界光順及簡化算法。首先利用非均勻B 樣條小波對(duì)邊界部分進(jìn)行分解和光順。然后基于T-mesh 進(jìn)行曲面重構(gòu)，得到具有光順邊界的T 樣條曲面。與文獻(xiàn)[14]和[16-18]傳統(tǒng)方法相比，新算法允許光順曲面中存在非矩形拓?fù)浣Y(jié)構(gòu)，因此對(duì)曲面邊界進(jìn)行光順時(shí)可以大大簡化數(shù)據(jù)。