NURBS曲面光順方法綜述

尹小奎， 李奇敏， 葉仲泉， 蔣恒恒

（1.重慶大學數學與統計學院，重慶 400044；2. 重慶大學機械工程學院，重慶 400044）

在飛機、汽車、船舶以及家用電器等的計算機輔助設計中經常遇到許多由二次曲線弧與二次曲面所表示的形狀，為描述這些形狀，Gordon和Riesenfeld于1974年提出了B樣條曲線曲面，較成功地解決了曲線曲面局部控制問題，并在參數連續性基礎上解決了連接問題。由于B樣條方法不能精確表示圓錐及初等解析曲面，Verspril于1975年首次提出有理B樣條方法。后來由于Pieg和Tille等的工作，終于使非均勻有理B樣條(NURBS)方法成為現代曲面造型中最為廣泛流行的技術。隨著生產的發展，人們對于產品的外形也有了要求，其中之一就是外形的光順性。如果曲線、曲面不光順，就不能滿足產品的設計要求，也不便于加工。因此，NURBS曲線、曲面的光順處理就成為 CAD/CAM 中非常重要的一個問題。

由于曲線、曲面的光順性涉及幾何外形的美觀性，難免受到主觀因素的影響，而且在不同的實際問題中，對其的要求也不同。對于判斷曲線、曲面的光順性的光順準則一般可分為兩類：一類是整體光順準則，如在能量法中采用的光順準則為“彈性模板應變能較小”，而最小二乘法采用的是“剪力躍度較小”。另一類是局部光順準則，如根據曲面上的關鍵曲線（如 u，v方向的參數線，或者曲面與平行于坐標平面的一系列平面的截面線等）是否光順，以及曲面的曲率（主曲率、高斯曲率、平均曲率等）的變化是否均勻等來判定。浙江大學的馬利莊和石教英給出了如下的曲面光順準則[1]：

關鍵曲線（如飛機或船舶曲面的骨架線）光順；

網格線無多余拐點（或平點）及變撓點；

主曲率（低次曲面）在節點處的躍度和足夠?。?/p>

彈性薄板的應變能較??；

高斯曲率變化均勻。

此外，在汽車工業中，還常用平行光照射到車身上來檢查曲面的光順性。對于帶有特征的曲線、曲面，如在復雜產品設計中需要設計出的曲面帶有邊界輪廓，表面棱線等特征，這些帶有關鍵信息的特征應該在光順過程中被保留。本文在總結了曲面光順中的幾種常用方法的特點，針對這些方法在光順中保特征性的不足，結合各向異性小波在表達高維信息的優勢，提出將其融入曲面的多分辨率分析，以達到保特征的目的。

1 基于能量的曲面光順方法

1.1 最小二乘法

上世紀 60年代初，最小二乘法曾是最有影響的一種光順方法。最小二乘法將樣條的剪力躍度平方和作為目標函數進行優化，使其達到最小值來實現光順，因而可以使樣條在光順后的曲率變化比較均勻。朱心雄等人將其推廣到對空間參數三次B樣條曲線的光順[2]。此外，用拉格朗日乘數法對帶約束的光順目標函數進行優化設計，可以得到保形的光順逼近曲線[3]。但是最小二乘法是整體光順法，需要將曲線、曲面的所有控制頂點作為未知量，計算量大、計算速度慢。

1.2 能量法

能量法的基本思想是將光順問題轉化為包含型值點偏差和光順兩部分加權平均的目標函數的極小化問題。能量法的關鍵是能量函數（光順準則）E(V)的選取，通常是通過對彈性薄板應變能進行簡化或近似得到的。在選取能量函數時，需要考慮其是否具有明確的物理意義或幾何意義，以及實際問題中對光順性的具體要求等。如針對參數曲面，Lott和Pullin[4]提出的一種薄板應變能的簡化形為曲面的主曲率）對曲面光順時會使曲面趨于平坦。Moreton[5]提出的采用

能量法具有很強的物理背景，光順效果好，但計算量大，計算速度慢。對此，穆國旺等[6]提出分片能量法，大大地減少了存儲量和計算量。此外，將能量法與選點法相結合進行曲線曲面光順[7]，一次性修改所有對壞點有影響的控制頂點，減少了計算量，也使得曲線曲面的形狀改變盡可能小。將能量法與最小二乘法相結合[8]，在對 B樣條曲線光順時可以使曲線的光順性及逼近性提高，使曲線的曲率變化更加均勻。

1.3 選點修改法

選點修改法是一種局部光順法，適用于少數型值點處不光順的情況。該方法充分利用NURBS曲面可以通過調整控制頂點來達到修改曲面形狀的特點，逐次找出不符合光順準則的型值點（稱為“壞點”），并依次對“壞點”進行修改。特別是對于曲面上“壞點”的選取較為復雜，需借助曲面的等曲率線、等照度線或反射線等曲面分析工具，結合交互的方法來判斷曲面在哪些區域不光順。目前，“壞點”的修改方法主要有Kejellander方法和Farin的節點刪除與插入法、圓率法、基樣條方法等。選點修改法的優點是計算速度快，修改能力強，具有局部性。但當連續出現多個壞點時，光順效果往往比較差。胡海艷等[9]應用廣義逆矩陣使節點消去，并通過升階和最小二乘逼近等步驟得到光順的目標曲線。該方法減少了Farin光順方法的計算量，但不能直接用于樣條曲面的光順。將選點修改法與小波多分辨率分析方法結合，Martin Bertram提出的單節點小波[10]，刪除“壞點”后根據小波系數以重新插入控制頂點，可以在保存幾何細節的基礎上使曲面更逼近原曲面，也更光順。

2 升階光順法

升階[11]是 B樣條方法配套技術中一項重要技術，通過增加B樣條基函數的次數來提高曲面的光順性，使曲線、曲面更為光順。B樣條曲線升階的主要方法有：Prautzsch的升階方法、Cohen等的升階方法、Piegl等的升階方法、秦開懷的升階方法[12]等。采用升階的方法，即是將B樣條函數的次數升高，特別是對于數據點個數變化較大的部分，得到的擬合曲線也更光順[13]，但加大了數據量。

3 保特征光順方法

為滿足產品的設計意圖，要求所設計曲面的光順性不僅僅要美觀，同時也要滿足功能上的需求，這就需要在光順過程中，對曲面特征進行保留，即采用保特征光順方法。但目前對這類NURBS曲面的保特征光順問題研究還很少。

另一種對曲面進行光順的方式是將其轉化為網格線的光順性問題來進行處理。網格光順的目的是要從原始網格模型中去除噪聲，并在局部和整體的體積變形最小化的基礎上保持模型的幾何形狀特征。近年來，一些學者致力于這方面的研究，提出了不少好的保特征的網格光順算法。Klaus Hildebrandt等[14]融合平均曲率流與各向異性方法定義了各向異性平均曲率向量，并提出了去除噪聲保特征的光順算法。該算法能夠保留并加強曲面上的非線性幾何特征，如曲面上的彎曲部分、特征線等。Xu Guoliang[15]通過用有限元離散化的方法求解偏微分方程——曲面熱流方程(Heat equation），提出的保特征光順算法能解決曲面光順不夠或過于光順而丟失細節的問題。目前，這些保特征光順方法主要集中于基于主曲率、平均曲率等幾何流的各向異性融合方法。這些方法雖然能夠增強曲面尖銳度，但是對多尺度形狀特征并存的曲面光順還需進一步探討。

4 基于各向同性小波的曲面光順算法

近年來，小波分析這種新的時頻分析數學方法在NURBS曲線曲面光順中得到廣泛的運用。利用小波的分解與重構算法，可以使B樣條曲線曲面具有很好的多分辨特性。因此，可用于B樣條曲線曲面的幾何造型、光順處理以及數據壓縮等。采用不同的基函數對曲線曲面進行多分辨率分析也會得到不同的結果。Finkelstein[16]提出了在閉區間上基于半正交 B樣條小波構造的多分辨率曲線編輯系統。孫延奎、朱心雄等[17]給出了準均勻雙二次 B樣條曲面小波分解與重構的基本概念，描述了曲面小波分解與重構的快速算法并論述了準均勻 B樣條曲線曲面的多分辨分析理論。趙罡等[18]基于多分辨率技術，對曲線、曲面的光順和編輯進行了研究，實現了在誤差控制下準均勻B樣條曲線的光順。

但是準均勻小波光順算法不能處理邊界約束的問題，不適合進行曲線曲面局部光順。對此，吳維勇[19]提出將能量法與小波光順法結合，構造分層能量算法，以達到靈活高效地進行曲線局部光順。然而此算法無法直接應用于任意B樣條曲線，需要先對原始曲線進行準均勻B樣條曲線逼近，這增加了計算量和計算誤差。此外，由于準均勻小波光順算法要求被光順 B樣條曲線的控制頂點數必須為2j+k（ j為整數，k為B樣條曲線的次數）。對此，可以直接插入節點來滿足小波光順對控制點個數的要求[20]。但是這個方法并沒有從本質上做出改變。紀小剛等[21]根據多分辨分析的思想，將 m個控制點的曲線用 n(n

由于準均勻 B樣條曲線曲面的邊界處采用了重節點技術，與定義域內部的小波表達形式不一致，導致在小波重構時計算量較大。對此，趙罡等[22]從幾何概念出發論述了基于小波的均勻三次 B樣條曲線曲面多分辨表示的原理及其實現。與準均勻B樣條曲線曲面采用的半正交小波不同的是，均勻B樣條曲線曲面采用的是雙正交小波，這使其計算速度更快。但是其小波分解后的邊界控制和誤差控制還有待于進一步研究。

為了進一步減少小波方法的運算量，出現了基于離散范數l2的雙正交非均勻B樣條小波基等的分解和重構算法。這種雙正交小波只需要尺度函數和小波線性獨立，且重構矩陣滿足=0，因此小波分解和重構不需要積分運算，計算較簡便。根據這一特點，吳福鳴等[23]提出利用雙正交非均勻 B樣條小波對非均勻 B樣條曲面進行光順的方法。但是這種光順方法未考慮曲面邊界的約束誤差精度的控制，較適用于對誤差精度要求不高的情況。

為了用小波實現對曲線、曲面的某一個局部進行光順操作，Lyche[24]給出了非均勻小波的構造。李奇敏等[25]將非均勻 B樣條小波分解用于NURBS曲面光順，通過整體光順度量確定B樣條曲面的光順方向，實現曲面的整體光順。同時根據曲面在節點處的光順性選出曲面上的壞點，通過局部小波分解實現曲面的局部光順，并通過添加邊界約束的方式實現了曲線的保邊界光順。但對于曲面其算法只能保證單參數方向分解時邊界不發生變化，因此不具有真正的保邊界性。如圖1(a)所示為原始曲面，圖1(b)所示為經過非均勻小波方法光順后所得到的曲面，圖1(c)所示是經過升階光順后的曲面，可以看出光順的效果要差些。

圖1 不同方法對曲面進行光順

此外，利用細分和提升模式構造的第2代小波也具有計算簡單，運算速度快等特點。Martin[26]構造了雙正交提升B樣條小波用于科學可視化。吳維勇在基于二元提升 B樣條小波給出了復雜拓撲曲面小波光順算法，突破了能量法只能對四邊域參數曲面進行光順的限制，并指出適當修改提升小波規則，可以保留尖角棱邊等不連續的特征[27]。

上述這些小波的光順算法主要適用于具有各向同性奇異性(Isotropic Singularities)的對象，而對于具有各向異性奇異性特征(Anisotropic Singularities)的曲面，上述小波光順算法均不是很好的工具。因為各向同性小波是可分離的和各向同性的，難以有效地表達圖像、圖形中帶有關鍵信息的邊緣、曲線等更高維的特征，也增加了圖像、圖形表達的冗余度和處理時間。如圖2(a)所示為依次帶有s形、矩形、三角形類特征的不光順曲面，圖2(b)所示為經過小波光順后的曲面，其中黑色部分為光順中的改變，可以看出為各特征已經沒有了原有的形狀。

圖2 帶特征曲面的光順

5 基于各向異性小波的 NURBS曲面光順

5.1 各向異性小波

各向異性小波理論是近幾年出現的一種新的數學分析方法，它為圖像提供了新的稀疏表示方法，能夠有效地捕捉信號中的高維奇異特征，從而保留幾何結構等重要信息。各向異性小波包括 Ridgelet、Curvelet、Contourlet等。

1998至1999年，D.L Donoho和E.J.Candes提出了脊波變換(Ridgelet Transform)[28]。其本質上是通過對小波基函數添加一個表征方向的參數得到的，因此具有很強的方向選擇和辨識的能力，可以非常有效地表示信號中具有方向性的奇異特征，如圖像的線性輪廓等。為處理以奇異邊界為曲線的對象，Candes在脊波理論的基礎上，利用剖分的方法構造了單尺度脊波（Monoscale Ridgelet）。但是，其獲得好的逼近性能也是以計算復雜度增加為代價的。

接著，Candes和Donoho在1999年提出第1代曲波變換[29]（Curvelet transform），可以在所有可能的尺度S≥0上進行分解。但是，第1代曲波的數字實現比較復雜，需要子帶分解、平滑分塊、正規化和脊波分析等一系列步驟，其金字塔的分解也帶來了巨大的數據冗余量。因此Candes等人又提出了實現更簡單、更便于理解的快速曲波變換算法，即第2代曲波。

在繼承了Curvelet變換的各向異性尺度關系的基礎上，Donoho和Vetterli于 2002年提出了Contourlet變換[30]，也稱為金字塔方向濾波器組(Pyramid Direction Filter Bank, PDFB)。Contourlet變換的優點在于能夠在使用少量系數的基礎上有效地表示平滑輪廓，而平滑輪廓正是自然圖像中的重要特征。目前，Contourlet變換已經在圖像重建、壓縮、融合等領域有了初步的應用。

圖3 基于Contourlet變換和NURBS的重構曲面

參考Contourlet在圖像處理中的應用，可以把Contourlet用于曲面處理中。我們把準均勻B樣條曲面控制頂點坐標做為變換對象，對其進行Contourlet變換。圖3(a)是所用原始曲面，圖3(b)是對控制頂點坐標利用小波變換后重構得到的曲面，后者邊緣和隆起部分的誤差都較明顯。可以看出，對于這種特征比較突出的曲面，小波重構方法存在不足。圖3(c)是基于Contourlet變換的NURBS重構曲面。與圖3(b)對比，前者誤差為 0.0046，后者為 0.0034。實驗結果表明，Contourlet變換的擬合精度要優于小波變換，具有較高的實際應用價值。

綜上所述，這些各向異性小波的出現，為提高曲面多分辨率表達的效率，減少表達的冗余，加快曲面顯示、處理的速度等提供了新的思路和方法。

5.2 基于各向異性小波的NURBS曲面光順

在復雜產品設計中，多尺度特征并存是常見的現象。多尺度特征并存曲面的保特征光順是多尺度特征并存曲面建模中的關鍵。而其目的就是要得到滿足設計要求的曲面模型，這就需要解決尺度分析、微分幾何屬性分布規律提取、特征提取、連續性、約束優化等問題。其中微分幾何屬性分布規律的數學描述、全局約束優化方程的建立及優化算法是實現曲面保特征光順的難點。目前關于多尺度特征并存曲面的主要處理方法是把基曲面和各個局部特征曲面之間通過剪裁、過渡和搭接等方法實現曲面從整體到局部的造型，這樣的造型過程對設計者要求非常高，而且在很多情況下得不到滿意的結果。

隨著多分辨率分析方法在圖形學中的廣泛應用，基于小波的多分辨率表達已經被應用到參數曲線，并被推廣到張量基曲面、任意拓撲類型曲面、球面及體數據。但是已有的多分辨率曲面表達方法對多尺度特征并存曲面及其上有曲線類特征的曲面表達能力也不足，相應的會帶來曲面顯示、壓縮及傳輸方面的數據冗余。

基于這種小波多分辨率分析方法，李奇敏提出了平面曲線多尺度分析方法，定義了曲線的局部形狀尺度因子，結合去除細節小波重建方法，分析了曲線上各個尺度特征的曲率主要分布規律，實現了大尺度特征在較低分辨率下分析，小尺度特征在較高分辨率下分析，并利用分析結果指導曲線的光順和特征提取[31]。但是曲面的情況要比平面曲線復雜得多，在分析時既要考慮特征的大小還要考慮特征的方向問題。而基于各向同性小波的多分辨率分析技術對特征方向的表達能力有限，為了提取多尺度特征并存曲面各尺度特征微分幾何屬性分布規律，有必要把基于各向異性小波的多分辨率分析方法和多尺度分析方法結合起來，對曲面各局部特征主要微分幾何信息分布規律進行分析。

如上所述，要實現多尺度特征并存曲面保特征光順，首先需要建立基于各向異性小波的曲面多分辨率表達和分析框架，用各向異性小波基代替各向同性小波基，把分析相關的Fourier變換、Radon變換等運算推廣到張量積曲面和離散曲面，實現曲面的各項異性小波多分辨率分析。

其次，在曲面光順之前對曲面形狀即設計意圖進行分析，提取各局部特征尺度，然后基于各向異性小波的多分辨率分析方法對曲面進行多尺度分析，確定各局部特征存在的尺度及其微分幾何屬性分布規律，然后用數學的語言對該分布規律進行描述，在所得微分幾何屬性分析基礎上提取特征區域的邊界、曲線類特征的脊線等特征曲線，并分析各特征間其連續性，以所提取特征曲線和微分幾何屬性分布規律為約束，利用帶約束的全局優化算法實現曲面保形光順。

6 結束語

本文在總結分析了NURBS曲線曲面各種光順算法的基礎上，詳細介紹了小波方法并與其他光順方法進行了對比。我們指出了小波光順算法在多尺度特征并存曲面保特征光順上的不足，提出了將各向異性小波融入曲面的多分辨率分析中的思想和實現這種方法的思路。我們將繼續對該問題進行更詳細的研究。

[1]馬利莊, 石教英. 曲線曲面的幾何光順算法[J]. 計算機學報, 1996, 19: 210-216.

[2]朱心雄. 自由曲線曲面造型技術[M]. 北京:科學出版社, 2000: 358-360.

[3]蔣大為, 李安平. B樣條曲線的最小二乘保形光順逼近[J]. 工程數學學報, 2000, 17(1): 125-128.

[4]Lott N J, Pullin D I. Method for fairing B-spline surfaces [J]. Computer-Aided Design, 1988, 20(10):597- 604.

[5]Moreton H P, Sequin C H. Functional optimization for fair surfaces design [J]. Computer Graphics, 1992,26(2): 167-175.

[6]穆國旺, 朱心雄, 涂侯杰, 等. 曲面光順的分片能量法[J]. 工程圖學學報, 1999, (1): 29-34.

[7]Zhang Caiming, Zhang Pifu, Cheng Fuhua. Fairing spline curves and surfaces by minimizing energy [J].Computer-Aided Design, 2001, 33(13): 913-923.

[8]王瑩瑩, 劉德平, 陳建軍, 等. 基于曲率均化的B樣條曲線能量光順方法[J]. 機床與液壓, 2010, 38(3):94- 96.

[9]胡海艷, 吳振遠. 基于廣義逆矩陣的 8樣條曲線的節點消去與光順[J]. 工程地球物理學報, 2010, 7(2):106- 110.

[10]Bertram M. Single-knot wavelets for non-uniform B-splines [J]. Computer Aided Geometric Design,2005, 22(9): 849-864.

[11]施法中. 計算機輔助幾何設計與非均勻有理 B樣條[M]. 北京: 高等教育出版社, 2001: 285-293.

[12]秦開懷. 非均勻B樣條曲線升階的新算法[J]. 計算機學報, 1996, 19(7): 537-542.

[13]曹利新, 游 洪. 基于升階的 B 樣條曲面光順擬合[J]. 機械制造, 2003, 41(7): 23-25.

[14]Hildebrandt K, Polthier K. Anisotropic filtering of non-linear surface features [C]//Eurographics 2004 Comput Graph Forum, 2004: 391-400.

[15]Xu Guoliang. Surface fairing and featuring by mean curvature motions [J]. Journal of Computational and Applied Mathematics, 2004, 163(1): 295-309.

[16]Finkelstein D H, Salesin. Multiresolution curves [C]//Proceedings of SIGGRAPH. ACM, 1994: 261-268.

[17]孫延奎, 朱心雄, 唐 龍, 等. 準均勻 B 樣條曲面小波分解的快速算法[J]. 清華大學學報(自然科學版), 2001(z1): 209-213.

[18]趙 罡, 穆國旺, 朱心雄. 基于小波的準均勻 B樣條曲線曲面變分造型[J]. 計算機輔助設計與圖形學學報, 2002, (1): 61-65.

[19]吳維勇, 王小椿. 自由曲線局部光順的分層能量算法[J]. 計算機輔助設計與圖形學學報, 2002, 14(10):959-966.

[20]潘洋宇, 姜福祥. 任意控制點曲線小波光順方法研究[J]. 機械設計, 2009, 26(11): 12-13.

[21]紀小剛, 龔光容. 準均勻三次B樣條曲線的任意分辨率光順[J]. 機械科學與技術, 2009, 28(11): 1477-1481.

[22]趙 罡, 穆國旺, 閆光榮, 等. 均勻 B 樣條曲線曲面的小波表示[J]. 工程圖學學報, 2001, (1): 80-87.

[23]吳福鳴, 潘日晶. 基于雙正交非均勻B樣條小波的曲面光順[J]. 福建師范大學學報(自然科學版),2010, (1): 33-37.

[24]Lyche T, Mrken K. Spline-wavelets of minimal support [J]. Numerical Methods of Approximation Theory, 1992, (9): 177-194.

[25]李奇敏, 柯映林, 何玉林. 基于非均勻B樣條小波的NURBS曲面光順[J]. 中國機械工程, 2007, 18(5):577-582.

[26]Bertram M, Mark A D, Hamann B, el at. Bicubic subdivision-surface wavelets for large-scale isosurface representa-tionand visualization [C]//Proceedings of IEEE Visualization, 2000:389-396&579.

[27]吳維勇. 自由曲線曲面多分辨率造型技術研究與應用[D]. 西安: 西安交通大學, 2003.

[28]Emmanuel J, Candès, David L, et al. Ridgelets:a key to higher-dimensional intermittency [C]//Phil. Trans.R. Soc. Lond. A. 1999: 2495-2509.

[29]焦李成, 譚 山, 劉 芳. 脊波理論: 從脊波變換到 Curvelet變換[J]. 工程數學學報, 2005, 22(5):761-773.

[30]Lounsbery M, De R T, Warren J. Multiresolution analysis for surfaces of arbitrary topological type [J].ACM Transaction on Graphics, 1997, 16(1): 34-73.

[31]李奇敏. 小波在反求工程中的若干應用[D]. 杭州:浙江大學, 2006.