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

何 川，趙 罡，王愛增

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

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

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

圖1 B-mesh 拓撲結(jié)構(gòu) Fig.1 B-mesh topology

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

圖3 非矩形拓撲結(jié)構(gòu) Fig.3 Non-rectangular topology

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

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

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

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

圖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)小波變換是對空間/時間頻率的局部化分析，利用二進伸縮與平移，對函數(shù)進行多尺度細化。小波分析的基本思想是將給定的尺度空間用一個低分辨空間VL-1(尺度空間)和一個高分辨空間WL-1(小波空間)表示。傳統(tǒng)小波性質(zhì)如下：

1.2 B 樣條小波分解

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

d次B 樣條曲線為

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

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

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

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

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

本文假定

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

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

圖6 Face-shape 曲線((a)原始曲線；(b)原始曲線對應(yīng)的曲率梳；(c)光順曲線；(d)光順曲線對應(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 樣條曲面在局部細分、曲面拼接和數(shù)據(jù)壓縮等方面具有優(yōu)勢[10-11]。T 樣條曲面定義在非矩形拓撲結(jié)構(gòu)的T-mesh 上(圖7(a))，并允許T 型節(jié)點和L 型節(jié)點[10-11]。本質(zhì)上，B-mesh是一種特殊的T-mesh。

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

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

圖7 T 樣條曲面的拓撲結(jié)構(gòu)及調(diào)配函數(shù) ((a) T-mesh 拓撲結(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ī)則，其對應(yīng)的節(jié)點矢量依賴于T-mesh 拓撲結(jié)構(gòu)[10-11]。

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

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

圖11 邊界區(qū)域的小波分解((a)原始拓撲結(jié)構(gòu)；(b)尺度部分拓撲結(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

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

3 實 例

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

圖13 Column-shape 曲面的邊界光順及簡化 ((a) Column-shape 曲面。原始邊界曲線(紅色實線)有21 個控制點，綠色實線是對應(yīng)的曲率梳；(b)原始拓撲結(jié)構(gòu)；(c)用本文算法進行邊界光順。光順邊界曲線(紅色實線) 有12 個控制點，綠色實線是對應(yīng)的曲率梳；(d)新的拓撲結(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 個控制點的三次B 樣條曲面。圖14(a)中的紅色實線是選擇的邊界部分，綠色實線是對應(yīng)的曲率梳。由圖14(a)和(c)可知，光順后的邊界曲線比原邊界曲線具有更少的曲率單調(diào)段。基于新算法，采用7個控制點對原曲面的邊界曲線進行了光順和簡化(圖14(a)～(d))。由光順前后的高光圖可知，控制點 個數(shù)的減少對曲面形狀產(chǎn)生了一定的影響，但差異不大。對曲面進行簡化時，剔除冗余點越多，結(jié)果越偏離原形狀，因此需要在保證形狀基本不變的前提下，對曲面進行簡化。

圖14 Mountain-shape 曲面的邊界光順及簡化 ((a) Mountain-shape 曲面。原始邊界曲線(紅色實線)有11個控制點，綠色實線是對應(yīng)的曲率梳；(b)原始拓撲結(jié)構(gòu)；(c)用本文算法進行邊界光順。光順邊界曲線 (紅色實線)有7 個控制點，綠色實線是對應(yīng)的曲率梳；(d)新的拓撲結(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)文獻[14]和[16-18]方法由于受矩形拓撲結(jié)構(gòu)的限制，無法得到最終的邊界數(shù)據(jù)簡化結(jié)果。文獻[14]采用非均勻B 樣條小波對NURBS 曲線曲面進行光順與簡化，在簡化后需要重新調(diào)整邊界控制點，無法局部壓縮邊界控制點的個數(shù)。本文方法則能夠?qū)Ψ蔷匦瓮負浣Y(jié)構(gòu)的曲面邊界區(qū)域進行光順，利用T 樣條技術(shù)進一步得到控制點簡化后的模型。

4 結(jié)束語

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