利用Jacobi多項(xiàng)式實(shí)現(xiàn)Bézier曲面的顯式約束降多階

1、利用Jacobi多項(xiàng)式實(shí)現(xiàn)Bézier曲面的顯式約束降多階 利用Jacobi多項(xiàng)式實(shí)現(xiàn)Bézier曲面的顯式約束降多階周聯(lián)a,b王國瑾* 通訊作者. Email地址: wanggj/0>. 王國瑾*a,ba浙江大學(xué)數(shù)學(xué)系, 杭州310027b浙江大學(xué)CAD&CG國家重點(diǎn)實(shí)驗(yàn)室, 杭州 310027摘 要 本文利用Jacobi多項(xiàng)式的表達(dá)形式及正交性質(zhì), 給出了張量積Bézier曲面在范數(shù)下一次性降多階的一個(gè)新算法. 在沒有端點(diǎn)或邊界約束的條件下, 它有以下三個(gè)優(yōu)點(diǎn):第一, 降階曲面的控制頂點(diǎn)可用矩陣形式由一個(gè)顯式來直接表出, 即降階曲面的控制頂點(diǎn)可以

2、由原曲面的控制頂點(diǎn)和事先已經(jīng)計(jì)算好并存于數(shù)據(jù)庫的幾個(gè)矩陣所決定, 因而計(jì)算簡單且快捷;第二, 降階逼近的誤差可事先求出, 用于考察它是否小于用戶所指定的公差, 從而避免了無效的降階;第三, 本算法的精度是最佳的, 即不可改進(jìn)的; 而在帶約束的情形下, 降階曲面也具有上面第一個(gè)優(yōu)點(diǎn), 同時(shí)還能保持降階前后的兩張曲面在四個(gè)角點(diǎn)處沿兩個(gè)參數(shù)方向的高階連續(xù), 并保持兩張拼接曲面分別降階以后在相鄰邊界曲線處的連續(xù). 本算法特別適用于由幾張Bézier曲面拼接而成的一張復(fù)雜曲面的降多階, 也適用于與曲面離散相結(jié)合的曲面降多階. 數(shù)值例子表明, 本算法與已有算法相比, 不但功能更強(qiáng), 而且計(jì)算更簡

3、單, 逼近效果更佳.關(guān)鍵詞 Bézier曲面, 降多階, 邊界約束, 矩陣, 顯式, Jacobi多項(xiàng)式, 分塊矩陣1 引言 Bézier曲面是計(jì)算機(jī)輔助設(shè)計(jì)/制造CAD/CAM系統(tǒng)中的主要造型工具Farin, 1991, 1995; Farin, Hoschek and Kim, 2002. 隨著數(shù)字化技術(shù)的廣泛使用,以不同階數(shù)的參數(shù)曲面為基準(zhǔn)所設(shè)計(jì)的不同的造型系統(tǒng)之間, 或者同一個(gè)造型系統(tǒng)中不同階數(shù)的兩種參數(shù)曲面之間, 其幾何數(shù)據(jù)的交換與傳遞日見頻繁. 因而需要對(duì)參數(shù)曲面實(shí)施降階變換. 其次, 曲面的等距逼近和有理曲面的多項(xiàng)式逼近經(jīng)常產(chǎn)生高階曲面, 也需要用降階算法來壓

4、縮幾何信息Farin, 2002; Prautzsch, Boehm and Paluszny, 2001. 另外, 把曲面離散和降階相結(jié)合, 還可化曲面求交為平面求交, 實(shí)現(xiàn)造型曲面的快速繪制Farin, 2002 近年來, 國際上很多學(xué)者對(duì)曲線降階已經(jīng)作了廣泛、深入的研究. 但迄今為止, 有關(guān)張量積Bézier曲面降階的研究工作卻屈指可數(shù). EckEck 1994曾給出了一種簡單的曲面降階算法, 其基本思想是根據(jù)曲面的張量積性質(zhì),從兩個(gè)參數(shù)方向先后應(yīng)用Bézier曲線的降階技術(shù). 陳發(fā)來等Chen and Ding, 1993、周登文等Zhou et al, 2002、

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

6、:1能實(shí)現(xiàn)一次性降多階?這是為了使算法簡單并杜絕累積誤差;2能保持與原始曲面在角點(diǎn)處沿兩個(gè)參數(shù)方向的高階連續(xù), 并保持兩張拼接曲面分別降階以后在邊界曲線處的位置連續(xù)?這是為了適應(yīng)由幾張Bézier曲面拼接而成的一張復(fù)雜曲面的降多階, 或者適應(yīng)與曲面離散相結(jié)合的曲面降多階;3降階曲面用顯式表達(dá)?這是為了使計(jì)算簡單而快捷;4降階逼近誤差最小;5降階計(jì)算耗時(shí)最少;6降階逼近誤差可在曲面降階之前先驗(yàn)地求出?這是為了避免無效的降階,因?yàn)橐坏┻@個(gè)先驗(yàn)性的誤差超過了用戶指定的公差,就可預(yù)先取消對(duì)原曲面的降階, 轉(zhuǎn)而把曲面離散,再對(duì)子曲面分別降階 我們發(fā)現(xiàn),Jacobi多項(xiàng)式的表達(dá)形式及正交性質(zhì),

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

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

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

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

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

12、個(gè)優(yōu)點(diǎn). 最后把曲面還原為Bézier形式. 再次利用性質(zhì)2, 得到這里其中, 矩陣和分別表示單位矩陣和零矩陣, 是由的左列所構(gòu)成的子矩陣, 是由的上行所構(gòu)成的子矩陣. 以上公式表明,對(duì)1式所示曲面的不帶角點(diǎn)及邊界曲線約束的最佳降多階可用矩陣形式顯式表示. 由于矩陣都可預(yù)先算好, 存儲(chǔ)在計(jì)算機(jī)內(nèi)備調(diào)用, 所以計(jì)算十分快捷. 這是本算法的第三個(gè)優(yōu)點(diǎn).帶角點(diǎn)及邊界曲線約束的曲面顯式降多階 本節(jié)將實(shí)現(xiàn)Bézier曲面帶角點(diǎn)及邊界曲線約束的降多階. 為此, 將在曲面降階之前, 首先對(duì)它的四條邊界曲線執(zhí)行帶端點(diǎn)約束的降多階. 其基本原理Zhang and Wang, 2005可概述如

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

14、線的這個(gè)降階過程. 記降階曲線及相應(yīng)控制頂點(diǎn)為, ,假設(shè)降階前后兩曲線在首末端點(diǎn)分別保持階插值, 對(duì)應(yīng)的降階逼近誤差函數(shù)和誤差分別為和, 則我們有 2 類似地, 對(duì)1式所示曲面的其他三條邊界曲線, 記帶相應(yīng)端點(diǎn)插值條件的降多階逼近曲線和控制頂點(diǎn)分別為, , ;, , ;再記上述降多階逼近的相應(yīng)誤差函數(shù)和誤差分別為,和, 則有:3 4 5 下面執(zhí)行本算法的第二步. 把欲求的降多階逼近曲面的四條邊界的控制頂點(diǎn)取定為. 再來確定此曲面的其它控制頂點(diǎn). 為此, 首先定義四個(gè)矩陣6 7 89 根據(jù)7與8, 容易知道 10根據(jù)6, 7與9, 容易知道 11 然后可寫出恒等式這里, 12其中, 矩陣 13

15、或, 14滿足等式;類似地有此外, 根據(jù)曲面邊界曲線的端點(diǎn)插值條件與Bernstein基的線性無關(guān)性, 我們可以得到下面的恒等式:, , ,15, , 16 另一方面, 簡單的計(jì)算可以導(dǎo)出,17其中18若對(duì)于矩陣, , 定義運(yùn)算, 再記 1920則 21 應(yīng)當(dāng)指出, 17式所表示的曲面是從曲面中去除其四條邊界得來的. 而 又是從原始曲面減去其四條邊界的最佳降多階逼近得來的. 這樣做的目的主要是體現(xiàn)本文的主導(dǎo)思想, 即把原始曲面降階轉(zhuǎn)化為邊界降階及曲面降階這樣兩個(gè)步驟, 這里曲面是從上述剩余部分中去除其四條邊界所獲得的. 只要注意到20就不難理解這一點(diǎn). 而其中的第一步在上面已經(jīng)完成. 此外,

16、這樣做的目的也是為了讓曲面具有一個(gè)因子, 以便它在最佳降多階前后保持邊界曲線處的連續(xù), 從而進(jìn)一步保證原始曲面的降多階逼近滿足邊界約束條件. 下面來對(duì)曲面作最佳降階逼近.根據(jù)性質(zhì)2, 有這里 22于是, 根據(jù)性質(zhì)1中Jacobi多項(xiàng)式的正交性, 立即知道在范數(shù)下, 滿足邊界連續(xù)的、對(duì)曲面的最佳降階逼近曲面是這里矩陣是分塊矩陣 23中位于左上角的一個(gè)子矩陣. 我們斷言曲面是曲面的最佳降階逼近, 乃是因?yàn)榇私惦A逼近在范數(shù)下的誤差為而由性質(zhì)1可知, 任何異于的次曲面, 其相應(yīng)的降階逼近誤差都將大于. 最后還需把曲面轉(zhuǎn)換為Bernstein基形式. 再次利用性質(zhì)2, 得這里所以, 若記 24 25按8

17、式可知矩陣26從而由10式能得到矩陣, 且知 27 進(jìn)一步, 按6式及11式, 可以得到矩陣. 所以, 根據(jù)2-6,8,10-14及18-26等公式, 我們最終得到了在范數(shù)下, 保持角點(diǎn)處連續(xù)并滿足邊界約束的, 對(duì)曲面的近似最佳的顯式降階逼近曲面 至于逼近的誤差界, 可以利用15-17式來得到:實(shí)例和比較 這里我們將文獻(xiàn)Guo and Zhu, 2004的方法記為方法1, 將文獻(xiàn)Chen and Wang, 2002的方法記為方法2, 將本文的降階方法記為方法3. 下面我們對(duì)這三種方法作一個(gè)比較. 首先, 在無約束條件下, 方法1和2得到的降階逼近曲面不是最佳的, 而方法3能求得最佳降階曲面.

18、 其次, 三個(gè)方法都能處理帶角點(diǎn)插值條件的情形. 方法1是利用曲線最小二乘降多階的方法, 采取分向降階: 先對(duì)曲面在向上進(jìn)行一次性降階, 并且使其滿足角點(diǎn)插值條件中的向插值要求, 然后對(duì)降階后的曲面在向上進(jìn)行一次性降階, 并且使其滿足角點(diǎn)插值條件中的向插值要求. 其思想本質(zhì)是EckEck 1994所提出來的. 但事實(shí)上, 這是不必要的. 容易明白, 我們只需對(duì)Bézier曲面的四條邊界作約束, 而無須對(duì)B網(wǎng)的每行列控制頂點(diǎn)所構(gòu)成的一大批曲面生成曲線都去提出端點(diǎn)約束要求. 基于這個(gè)考慮, 方法2和方法3都先對(duì)原始曲面的四條邊界曲線分別作端點(diǎn)插值的降多階逼近, 再利用曲面轉(zhuǎn)換, 對(duì)原始曲

19、面減去四條降階邊界曲線后所得到的新曲面作降多階逼近. 但方法2和方法3的不同點(diǎn)在于, 方法2既沒有對(duì)四條邊界作最佳降多階逼近, 又沒有對(duì)移去四條降階邊界曲線的新曲面作最佳降多階逼近, 它僅對(duì)此新曲面利用Chebyshev多項(xiàng)式來作逼近, 因而得到的是一張逼近程度較為遜色的降階曲面. 至于方法3, 它首先對(duì)曲面的四條邊界作端點(diǎn)約束的最佳降多階逼近, 再從原始曲面減去這四條降多階邊界曲線, 進(jìn)一步又從余項(xiàng)中去除其四條邊界曲線, 最后對(duì)新曲面利用Jacobi多項(xiàng)式的正交性作了最佳降多階逼近, 所以方法3的誤差遠(yuǎn)小于方法1, 也小于方法2. 大量數(shù)值實(shí)驗(yàn)也驗(yàn)證了我們以上的分析結(jié)論. 當(dāng)然, 我們還不能

20、斷言, 在角點(diǎn)及邊界曲線約束的情況下, 用本方法所得到的一張降階曲面, 其逼近程度是不可改進(jìn)的. 不過, 事實(shí)上, 它幾乎已是一種最佳逼近. 此外, 在約束條件下, 方法3所得的降階逼近誤差界比方法1, 2所得到的小. 最后, 方法1與方法2不滿足降階曲面在邊界的約束條件, 而方法3則可以滿足這一條件, 所以它既適用于由幾張曲面拼接而成的一張復(fù)雜曲面的降多階, 也適用于與離散相結(jié)合的曲面降多階. 下面給出幾個(gè)例子.例1.將一張次Bézier曲面降為次, 并且在四個(gè)角點(diǎn)處保持1階連續(xù). 由方法1所得曲面的絕對(duì)誤差為0.2941;由方法2所得曲面的絕對(duì)誤差為0.0754;由方法3所得曲面

21、的絕對(duì)誤差為0.0131例2.將一張次Bézier曲面降為次, 并且在四個(gè)角點(diǎn)處保持1階連續(xù). 由方法1所得曲面的絕對(duì)誤差為0.2072;由方法2所得曲面的絕對(duì)誤差為0.0196;由方法3所得曲面的絕對(duì)誤差為0.0123例3.將兩張具有公共邊界的次張量積Bézier曲面, 同時(shí)降為次, 并且在四個(gè)角點(diǎn)處保持1階連續(xù). 記降階曲面分別為,曲面的降階誤差為0.0087, 曲面的降階誤差為0.0209. 由圖可見, 降階后的兩張拼接曲面仍保持邊界線重合 7 結(jié)論實(shí)例表明, 本文的方法要優(yōu)于目前所有的方法. 從功能上說, 用本文方法所得的降階曲面其控制頂點(diǎn)可用顯式直接表出; 降階逼

22、近的誤差可預(yù)先報(bào)告, 避免了無效的降階; 特別是, 降階曲面能保持角點(diǎn)處連續(xù)并滿足邊界約束, 特別適用于拼接曲面的降多階, 也適用于與離散相結(jié)合的曲面降多階. 從計(jì)算上說, 操作更簡單, 逼近效果更佳, 滿足了現(xiàn)代CAGD設(shè)計(jì)系統(tǒng)的要求. 所以本文方法有廣闊的應(yīng)用前景.參 考 文 獻(xiàn)Zhang Renjiang and Wang Guojin, Constrained Bézier curves best multi-degree reduction in the -norm, Progress in Natural Science, 2005, 159: 843-850 Chen

23、Guodong and Wang Guojin, Multi-degree reduction of tensor product Bézier surfaces with conditions of corners interpolations, SCIENCE IN CHINA, Series F,2002, 451: 5158 陳國棟, 王國瑾, 帶角點(diǎn)插值條件的張量積Bézier曲面降多階, 中國科學(xué)E輯, 2002, 323: 386392Borwein P. and Erdelyi T. Polynomail and Polynomial Inequalitie

24、s. 1st ed.Berlin:Spring-Verlag, 1995, 64Farin 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 Aided Geometric Design. Amsterdam, Netherla