1、利用Jacobi多項式實現Bézier曲面的顯式約束降多階周聯a,b 王國瑾* 通訊作者. Email地址: wanggj (王國瑾)a,ba浙江大學數學系, 杭州310027b浙江大學CAD&CG國家重點實驗室, 杭州 310027摘 要本文利用Jacobi多項式的表達形式及正交性質, 給出了張量積Bézier曲面在范數下一次性降多階的一個新算法. 在沒有端點或邊界約束的條件下, 它有以下三個優點：第一, 降階曲面的控制頂點可用矩陣形式由一個顯式來直接表出, 即降階曲面的控制頂點可以由原曲面的控制頂點和事先已經計算好并存于數據庫的幾個矩陣所決定, 因而計算簡單且快

2、捷；第二, 降階逼近的誤差可事先求出, 用于考察它是否小于用戶所指定的公差, 從而避免了無效的降階；第三, 本算法的精度是最佳的, 即不可改進的; 而在帶約束的情形下, 降階曲面也具有上面第一個優點, 同時還能保持降階前后的兩張曲面在四個角點處沿兩個參數方向的高階連續, 并保持兩張拼接曲面分別降階以后在相鄰邊界曲線處的連續. 本算法特別適用于由幾張Bézier曲面拼接而成的一張復雜曲面的降多階, 也適用于與曲面離散相結合的曲面降多階. 數值例子表明, 本算法與已有算法相比, 不但功能更強, 而且計算更簡單, 逼近效果更佳.關鍵詞 Bézier曲面, 降多階, 邊界約束, 矩

3、陣, 顯式, Jacobi多項式, 分塊矩陣1 引言 Bézier曲面是計算機輔助設計/制造(CAD/CAM)系統中的主要造型工具(Farin, 1991, 1995; Farin, Hoschek and Kim, 2002). 隨著數字化技術的廣泛使用,以不同階數的參數曲面為基準所設計的不同的造型系統之間, 或者同一個造型系統中不同階數的兩種參數曲面之間, 其幾何數據的交換與傳遞日見頻繁. 因而需要對參數曲面實施降階變換. 其次, 曲面的等距逼近和有理曲面的多項式逼近經常產生高階曲面, 也需要用降階算法來壓縮幾何信息(Farin, 2002; Prautzsch, Boehm a

4、nd Paluszny, 2001). 另外, 把曲面離散和降階相結合, 還可化曲面求交為平面求交, 實現造型曲面的快速繪制(Farin, 2002). 近年來, 國際上很多學者對曲線降階已經作了廣泛、深入的研究. 但迄今為止, 有關張量積Bézier曲面降階的研究工作卻屈指可數. Eck(Eck 1994)曾給出了一種簡單的曲面降階算法, 其基本思想是根據曲面的張量積性質,從兩個參數方向先后應用Bézier曲線的降階技術. 陳發來等(Chen and Ding, 1993)、周登文等(Zhou et al, 2002)、胡事民(Hu et al, 1997)等分別給出了B

5、ézier曲面的各種降階算法, 這些算法也都是Bézier曲線降階算法向曲面形式的成功推廣, 不過它們沒有考慮曲面的一次性降多階. 此后,陳國棟等(Chen and Wang, 2002)和郭清偉等(Guo and Zhu, 2004)給出了一次性降多階或帶角點插值的曲面降階方法. 然而這些方法仍或多或少地存在著局限性, 主要表現在降階曲面的邊界缺乏約束條件以及逼近精度不夠高. 事實上,近年來, 產品質量的提升及加工工藝的革新已經對幾何設計系統的功能提出了更高的要求,特別地,在曲面降階方面, 要求一個理想的算法必須同時具備以下6個功能：(1)能實現一次性降多階這是為了使算法

6、簡單并杜絕累積誤差；(2)能保持與原始曲面在角點處沿兩個參數方向的高階連續, 并保持兩張拼接曲面分別降階以后在邊界曲線處的位置連續這是為了適應由幾張Bézier曲面拼接而成的一張復雜曲面的降多階, 或者適應與曲面離散相結合的曲面降多階；(3)降階曲面用顯式表達這是為了使計算簡單而快捷；(4)降階逼近誤差最小；(5)降階計算耗時最少；(6)降階逼近誤差可在曲面降階之前先驗地求出這是為了避免無效的降階，因為一旦這個先驗性的誤差超過了用戶指定的公差,就可預先取消對原曲面的降階, 轉而把曲面離散,再對子曲面分別降階. 我們發現,Jacobi多項式的表達形式及正交性質, 非常適合用于同時滿足曲

7、面降多階及邊界約束這兩個要求, 更為降階逼近的先驗誤差最小以及降階曲面的顯式表達提供了十分有利的條件. 基于這種思想, 本文利用Jacobi多項式與Bernstein多項式相互轉換的公式, 給出了張量積Bézier曲面在范數下顯式降多階的一個新算法. 在曲面的邊界曲線及角點無約束的情形下, 本算法的精度是最佳的; 而在有約束的情形下, 降階前后的兩張曲面能保持在四個角點處沿每條邊界線方向的高階連續, 且任何兩張拼接曲面分別降多階以后能保持在公共邊界曲線處的連續, 從而避免了一張分片連續的Bézier曲面在逐片降階以后于拼接處有“裂痕”出現. 同時, 降階操作的公式是簡單的矩

8、陣表示, 這些矩陣僅依賴于曲面降階前后的次數, 從而可被存儲于數據庫以備隨時調用. 此外,用戶可以預先檢驗曲面的降階逼近誤差是否在給定公差范圍內, 再決定要不要降階, 當先驗誤差大于公差, 可以直接應用與曲面離散相結合的降階技術. 數值實驗表明, 本文算法與文獻(Chen and Wang, 2002)和(Guo and Zhu, 2004)中的方法相比,不但計算更簡單,而且逼近效果更佳.本文是如下安排的: 第2節對曲面的約束降階問題進行描述; 第3節介紹Jacobi多項式的相關性質; 第4節研究不帶任何約束條件的曲面降多階方法, 給出降階曲面控制頂點的顯式表達、降階的先驗誤差; 第5節研究帶

9、角點及邊界曲線約束的曲面降多階并給出誤差界; 第6節給出與其他方法的比較并用實例驗證算法的有效性與優越性; 第7節給出結論.2 帶角點及邊界曲線約束的Bézier曲面降多階問題的描述給定一組控制頂點, 可確定一張張量積次Bézier曲面, , (1)其中為Bernstein多項式基函數.所謂對(1)式給出的Bézier曲面在范數下進行降多階逼近, 是指找到另一張次Bézier曲面, ,使得距離函數所謂對(1)式給出的Bézier曲面在范數下進行帶角點插值條件的降多階，是指去找到滿足距離函數為極小的那張Bézier曲面, 且降階曲面與原

10、曲面在四個角點處沿著每條邊界線方向分別保持預先給定的階連續. 即存在四個角點處在兩個參數方向分別需要滿足的連續階, , 使得所謂對(1)式給出的Bézier曲面在范數下進行帶角點及邊界曲線約束的降多階逼近, 系指除了上面所講的兩個條件, 即距離函數為極小, 以及降階曲面在四個角點處沿兩個參數方向分別保持階連續以外, 還須其四條邊界曲線, , ; 恰為已知曲面的四條邊界曲線在范數下帶各自端點約束的降多階逼近.3 Jacobi多項式的相關知識本文將應用Jacobi多項式的以下重要性質, 其中性質1引自(Borwein and Erdelyi, 1995), 性質2引自(Chen and

11、Wang, 2002; Sunwoo, 2004).性質1. 一個次Jacobi多項式為關于權函數, , 的正交多項式, 即滿足：這里.性質2. Jacobi多項式與Berstein多項式可以相互線性表出, 即有以下關系式: , .或簡單地記為,這里,4 不帶角點及邊界曲線約束的曲面顯式最佳降多階將(1)式寫成矩陣形式.這里.利用第3節中Jacobi多項式的性質2, 得到.記.根據性質1, 容易知道在范數下, 曲面的無約束最佳降階的逼近曲面為.其降階逼近誤差為而如果用任何別的次曲面代替, 其逼近誤差將明顯增大. 這表明, 此降階逼近的誤差不但是不可改進的, 而且可以在計算降階曲面之前先驗地求得

12、. 這是本算法的兩個優點.最后把曲面還原為Bézier形式. 再次利用性質2, 得到.這里其中, 矩陣和分別表示單位矩陣和零矩陣, 是由的左列所構成的子矩陣, 是由的上行所構成的子矩陣.以上公式表明，對(1)式所示曲面的不帶角點及邊界曲線約束的最佳降多階可用矩陣形式顯式表示. 由于矩陣都可預先算好, 存儲在計算機內備調用, 所以計算十分快捷. 這是本算法的第三個優點.5 帶角點及邊界曲線約束的曲面顯式降多階本節將實現Bézier曲面帶角點及邊界曲線約束的降多階. 為此, 將在曲面降階之前, 首先對它的四條邊界曲線執行帶端點約束的降多階. 其基本原理(Zhang and Wa

13、ng, 2005)可概述如下:設, 為一條次Bézier曲線, 為的在兩端點具有階與階約束:, , 的最佳降階的次Bézier曲線, 則的控制頂點可由以下矩陣形式顯式求出:, 這里,且, , 其中, 矩陣是由次Bernstein基到同次冪基的轉換矩陣; 矩陣是由次冪基到同次Bernstein基的轉換矩陣.為了對原始次Bézier曲面在范數下一次性地向降階, 向降階, 且保持角點處連續并滿足邊界約束, 作為算法的第一步, 我們先對的四條邊界曲線, , , , ,進行帶端點階插值的最優降多階逼近,其中前兩條降階,后兩條降階; 它們的原始控制頂點分別記為, , , .

14、今以曲線為例來說明邊界曲線的這個降階過程. 記降階曲線及相應控制頂點為, , .假設降階前后兩曲線在首末端點分別保持階插值, 對應的降階逼近誤差函數和誤差分別為和, 則我們有. (2)類似地, 對(1)式所示曲面的其他三條邊界曲線, 記帶相應端點插值條件的降多階逼近曲線和控制頂點分別為, , ; , , ;再記上述降多階逼近的相應誤差函數和誤差分別為,和, 則有: (3) (4) (5)下面執行本算法的第二步. 把欲求的降多階逼近曲面的四條邊界的控制頂點取定為. 再來確定此曲面的其它控制頂點. 為此, 首先定義四個矩陣 (6) (7) (8) (9)根據(7)與(8), 容易知道 (10)根據

15、(6), (7)與(9), 容易知道 (11)然后可寫出恒等式這里, (12)其中, 矩陣 (13) 或, (14)滿足等式;類似地有.此外, 根據曲面邊界曲線的端點插值條件與Bernstein基的線性無關性, 我們可以得到下面的恒等式:, , , . (15), , . (16)另一方面, 簡單的計算可以導出, (17)其中 (18)若對于矩陣, , 定義運算, 再記 (19) (20)則 (21)應當指出, (17)式所表示的曲面是從曲面中去除其四條邊界得來的. 而 又是從原始曲面減去其四條邊界的最佳降多階逼近得來的. 這樣做的目的主要是體現本文的主導思想, 即把原始曲面降階轉化為邊界降階

16、及曲面降階這樣兩個步驟, 這里曲面是從上述剩余部分中去除其四條邊界所獲得的. 只要注意到(20)就不難理解這一點. 而其中的第一步在上面已經完成. 此外, 這樣做的目的也是為了讓曲面具有一個因子, 以便它在最佳降多階前后保持邊界曲線處的連續, 從而進一步保證原始曲面的降多階逼近滿足邊界約束條件.下面來對曲面作最佳降階逼近.根據性質2, 有這里 (22)于是, 根據性質1中Jacobi多項式的正交性, 立即知道在范數下, 滿足邊界連續的、對曲面的最佳降階逼近曲面是這里矩陣是分塊矩陣 (23)中位于左上角的一個子矩陣. 我們斷言曲面是曲面的最佳降階逼近, 乃是因為此降階逼近在范數下的誤差為而由性質

17、1可知, 任何異于的次曲面, 其相應的降階逼近誤差都將大于.最后還需把曲面轉換為Bernstein基形式. 再次利用性質2, 得這里所以, 若記 (24) (25)按(8)式可知矩陣 (26)從而由(10)式能得到矩陣, 且知 (27)進一步, 按(6)式及(11)式, 可以得到矩陣. 所以, 根據(2)-(6),(8),(10)-(14)及(18)-(26)等公式, 我們最終得到了在范數下, 保持角點處連續并滿足邊界約束的, 對曲面的近似最佳的顯式降階逼近曲面 .至于逼近的誤差界, 可以利用(15)-(17)式來得到:6 實例和比較這里我們將文獻(Guo and Zhu, 2004)的方法記

18、為方法1, 將文獻(Chen and Wang, 2002)的方法記為方法2, 將本文的降階方法記為方法3.下面我們對這三種方法作一個比較.首先, 在無約束條件下, 方法1和2得到的降階逼近曲面不是最佳的, 而方法3能求得最佳降階曲面.其次, 三個方法都能處理帶角點插值條件的情形. 方法1是利用曲線最小二乘降多階的方法, 采取分向降階: 先對曲面在向上進行一次性降階, 并且使其滿足角點插值條件中的向插值要求, 然后對降階后的曲面在向上進行一次性降階, 并且使其滿足角點插值條件中的向插值要求. 其思想本質是Eck(Eck 1994)所提出來的. 但事實上, 這是不必要的. 容易明白, 我們只需對

19、Bézier曲面的四條邊界作約束, 而無須對B網的每行(列)控制頂點所構成的一大批曲面生成曲線都去提出端點約束要求. 基于這個考慮, 方法2和方法3都先對原始曲面的四條邊界曲線分別作端點插值的降多階逼近, 再利用曲面轉換, 對原始曲面減去四條降階邊界曲線后所得到的新曲面作降多階逼近. 但方法2和方法3的不同點在于, 方法2既沒有對四條邊界作最佳降多階逼近, 又沒有對移去四條降階邊界曲線的新曲面作最佳降多階逼近, 它僅對此新曲面利用Chebyshev多項式來作逼近, 因而得到的是一張逼近程度較為遜色的降階曲面. 至于方法3, 它首先對曲面的四條邊界作端點約束的最佳降多階逼近, 再從原始

20、曲面減去這四條降多階邊界曲線, 進一步又從余項中去除其四條邊界曲線, 最后對新曲面利用Jacobi多項式的正交性作了最佳降多階逼近, 所以方法3的誤差遠小于方法1, 也小于方法2. 大量數值實驗也驗證了我們以上的分析結論. 當然, 我們還不能斷言, 在角點及邊界曲線約束的情況下, 用本方法所得到的一張降階曲面, 其逼近程度是不可改進的. 不過, 事實上, 它幾乎已是一種最佳逼近.此外, 在約束條件下, 方法3所得的降階逼近誤差界比方法1, 2所得到的小.最后, 方法1與方法2不滿足降階曲面在邊界的約束條件, 而方法3則可以滿足這一條件, 所以它既適用于由幾張曲面拼接而成的一張復雜曲面的降多階,

21、 也適用于與離散相結合的曲面降多階.下面給出幾個例子.例1將一張次Bézier曲面降為次, 并且在四個角點處保持1階連續. 由方法1所得曲面的絕對誤差為0.2941；由方法2所得曲面的絕對誤差為0.0754；由方法3所得曲面的絕對誤差為0.0131. (1)(2) (3) (4)(5) (6) (7)圖1.（1）次原始Bézier曲面；（24）分別為用方法1, 方法2, 方法3作出的降階曲面, 并且在四個角點處均保持1階連續；（57）分別是以上方法對應的誤差圖. 例2將一張次Bézier曲面降為次, 并且在四個角點處保持1階連續. 由方法1所得曲面的絕對誤差為0.

22、2072；由方法2所得曲面的絕對誤差為0.0196；由方法3所得曲面的絕對誤差為0.0123. (1)(2) (3) (4) (5) (6) (7)圖2.（1）次原始Bézier曲面；（24）分別為用方法1, 方法2, 方法3做出的降階曲面, 并且在四個角點處均保持1階連續；（57）分別是以上方法對應的誤差圖. 例3將兩張具有公共邊界的次張量積Bézier曲面, 同時降為次, 并且在四個角點處保持1階連續. 記降階曲面分別為, . 曲面的降階誤差為0.0087, 曲面的降階誤差為0.0209. 由圖可見, 降階后的兩張拼接曲面仍保持邊界線重合. (1) (2) (3) (4

23、)圖3.（1）兩張具有公共邊界的次張量積Bézier曲面；（2）用本文方法所做的降階曲面, 邊界線保持重合, 且在各自角點處保持1階連續；（3-4）分別是曲面, 的降階誤差圖. 7 結論實例表明, 本文的方法要優于目前所有的方法. 從功能上說, 用本文方法所得的降階曲面其控制頂點可用顯式直接表出; 降階逼近的誤差可預先報告, 避免了無效的降階; 特別是, 降階曲面能保持角點處連續并滿足邊界約束, 特別適用于拼接曲面的降多階, 也適用于與離散相結合的曲面降多階. 從計算上說, 操作更簡單, 逼近效果更佳, 滿足了現代CAGD設計系統的要求. 所以本文方法有廣闊的應用前景.參 考 文 獻

24、Zhang Renjiang and Wang Guojin, Constrained Bézier curves best multi-degree reduction in the -norm, Progress in Natural Science, 2005, 15(9): 843-850 Chen Guodong and Wang Guojin, Multi-degree reduction of tensor product Bézier surfaces with conditions of corners interpolations, SCIENCE IN

25、 CHINA, Series F,2002, 45(1): 5158 陳國棟, 王國瑾, 帶角點插值條件的張量積Bézier曲面降多階, 中國科學(E輯), 2002, 32(3): 386392Borwein P. and Erdelyi T. Polynomail and Polynomial Inequalities. 1st ed.Berlin:Spring-Verlag, 1995, 64. Farin G., 1991. NURBS for curve and surface design. SIAM, Philadelphia.Farin G., 1995. NURBS curves and surfaces: from project geometry to practical use. A.K. Peters, Wellesley, MA.Farin G., Hoschek J., and Kim M.-S., 2002. Handbook of Computer Ai