細(xì)分曲面的漸進(jìn)插值及其光順

1、單位代碼:學(xué) 號(hào):103592016111171Hefei University ofTechnology碩士學(xué)位論文MASTER S DISSERTATION（學(xué)術(shù)碩士）論文題目:細(xì)分曲面的漸進(jìn)插值及其光順學(xué)科專業(yè):計(jì)算數(shù)學(xué)作者姓名:余祥榮導(dǎo)師姓名:張莉教授完成時(shí)間:2019年4月Hefei University of Technology碩士學(xué)位論文MASTERS DISSERTATION（學(xué)術(shù)碩士）論文題目：細(xì)分曲面的漸進(jìn)插值及其光順學(xué)位類別：學(xué)歷碩士學(xué)科專業(yè)：計(jì)算數(shù)學(xué)作者姓名：余祥榮導(dǎo)師姓名：張莉 教授完成時(shí)間：2019年4月合肥工業(yè)大學(xué)學(xué)歷碩士學(xué)位論文細(xì)分曲面的漸進(jìn)插值及其光順作者姓

2、名：余祥榮 指導(dǎo)教師： 張莉 教授 學(xué)科專業(yè)：計(jì)算數(shù)學(xué) 研究方向： 計(jì)算機(jī)輔助幾何設(shè)計(jì)2019年4月A Dissertation Submitted for the Degree of MasterProgressive interpolation and smoothing of subdivisionsurfacesByShe XiangrongHefei University of TechnologyHefei, Anhui, P.R.China4, 2019合肥工 業(yè)大學(xué)本論文經(jīng)答辯委員會(huì)全體委員審查，確認(rèn)符合合肥工業(yè) 大學(xué)學(xué)歷碩士學(xué)位論文質(zhì)量要求。答辯委員會(huì)簽名（工作單位、職稱、姓

3、名）主席：中國(guó)科學(xué)技術(shù)大學(xué)教授委員：合肥工業(yè)大學(xué)合肥工業(yè)大學(xué)合肥工業(yè)大學(xué)合肥工業(yè)大學(xué)導(dǎo)師：合肥工業(yè)大學(xué)學(xué)位論文獨(dú)創(chuàng)性聲明本人鄭重聲明：所呈交的學(xué)位論文是本人在導(dǎo)師指導(dǎo)下進(jìn)行獨(dú)立研究工作所 取得的成果。據(jù)我所知，除了文中特別加以標(biāo)注和致謝的內(nèi)容外，論文中不包含 其他人己經(jīng)發(fā)表或撰寫過(guò)的研究成果，也不包含為獲得合肥工業(yè)大學(xué)或其他教育 機(jī)構(gòu)的學(xué)位或證書而使用過(guò)的材料。對(duì)本文成果做出貢獻(xiàn)的個(gè)人和集體，本人己 在論文中作了明確的說(shuō)明，并表示謝意。學(xué)位論文中表達(dá)的觀點(diǎn)純屬作者本人觀點(diǎn)，與合肥工業(yè)大學(xué)無(wú)關(guān)。學(xué)位論文作者簽名：令并家 簽名日期：湖 年偵月4日學(xué)位論文版權(quán)使用授權(quán)書本學(xué)位論文作者完全了解合肥工業(yè)

4、大學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定，即: 除保密期內(nèi)的涉密學(xué)位論文外，學(xué)校有權(quán)保存并向國(guó)家有關(guān)部門或機(jī)構(gòu)送交論文 的復(fù)印件和電子光盤，允許論文被查閱或借閱。本人授權(quán)合肥工業(yè)大學(xué)可以將本 學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫(kù)，允許采用影印、縮印或掃描等復(fù)制 手段保存、匯編學(xué)位論文。（保密的學(xué)位論文在解密后適用本授權(quán)書）學(xué)位論文作者簽名：家耳兼指導(dǎo)教師簽名:簽名日期:*9 年S月，日簽名日期加年，月y日E-mail：郵政編碼:論文作者畢業(yè)去向工作單位：聯(lián)系電話：通訊地址：致謝伴隨著初夏的到來(lái)，時(shí)間仿佛回到了三年之前，滿懷著對(duì)研究生生活的些許 期許和緊張，而現(xiàn)在所有的都是滿滿的回憶。在此，我要衷心感

5、謝合肥工業(yè)大學(xué) 給我提供了充實(shí)的學(xué)習(xí)氛圍和良好的學(xué)習(xí)環(huán)境！首先，我要感謝我的導(dǎo)師張莉老師。很榮幸能成為張莉老師的學(xué)生。張莉老 師學(xué)識(shí)淵博，在計(jì)算機(jī)輔助幾何設(shè)計(jì)、數(shù)值逼近等方面內(nèi)容上都有涉及，給我們 講解了很多新的知識(shí)和新的方法，開(kāi)拓了我們的眼界。在學(xué)術(shù)上造詣深厚，對(duì)待 問(wèn)題認(rèn)真嚴(yán)謹(jǐn)，特別是在漸進(jìn)迭代逼近和曲線曲面細(xì)分等方向上，有著獨(dú)特的見(jiàn) 解，在國(guó)內(nèi)外發(fā)表了很多優(yōu)質(zhì)的論文，并慷慨的給予了我很多指導(dǎo)，讓我在學(xué)習(xí) 上有很大的收獲。張莉老師不僅分享了很多資源給學(xué)生，聯(lián)系國(guó)內(nèi)外優(yōu)秀學(xué)者開(kāi) 展講座，帶領(lǐng)我們參與學(xué)術(shù)會(huì)議，以此來(lái)鼓勵(lì)我們好好學(xué)習(xí)。而且在討論班，也 是親力親為，仔細(xì)的聽(tīng)取每位學(xué)生的匯報(bào)，給予

6、詳細(xì)的指導(dǎo)，面對(duì)面的幫助我們 解決問(wèn)題，對(duì)于我們的粗心大意，老師總是不厭其煩的講解，老師的這些耐心和 細(xì)心，對(duì)待學(xué)術(shù)的嚴(yán)謹(jǐn)態(tài)度，都在潛移默化的影響著我，我只是老師的一個(gè)學(xué)生, 而老師的這份師者心和學(xué)術(shù)心卻是要給每一位學(xué)生！在生活上老師也是很關(guān)心我 們，對(duì)于我們生活以及情感上問(wèn)題，老師也是會(huì)給出蒂助和指導(dǎo)，在老師的帶領(lǐng) 下，三年的研究生活，不僅讓我學(xué)了很多知識(shí)，也成長(zhǎng)了很多。其次，我要感謝討論班的檀結(jié)慶老師，唐爍老師，王旭輝老師在論文及學(xué)習(xí) 上的關(guān)心與蒂助，感謝數(shù)學(xué)學(xué)院所有老師對(duì)我的指導(dǎo)！感謝輔導(dǎo)員王曉莉老師在 生活與學(xué)習(xí)上的關(guān)心！在此，向各位老師致以深深的謝意！再次，感謝師兄師姐葛先玉、趙林、

7、孫燕、陸中華，同學(xué)馬歡歡，師弟師妹 趙志遠(yuǎn)、吳月旺、姚紅麗、張能俊，與我一起學(xué)習(xí)一起討論，給我營(yíng)造良好的學(xué) 習(xí)環(huán)境和學(xué)術(shù)氛圍，讓我在這個(gè)大家庭中充實(shí)的學(xué)習(xí)！感謝一直陪伴我的室友程 創(chuàng)創(chuàng)、張陽(yáng)洋、章翔同學(xué)的關(guān)心和蒂助。最后，感謝我的家人對(duì)我學(xué)習(xí)和生活的極大支持和鼓舞。正是有了他們?cè)诮?jīng) 濟(jì)上對(duì)我的支持和心理上的疏通指導(dǎo)，我才能有有適度的環(huán)境和壓力，繼續(xù)我三 年的潛心學(xué)習(xí)和研究。在此，我還要感謝評(píng)閱、評(píng)議碩士論文和出席碩士論文答辯會(huì)的各位專家學(xué)者, 感謝你們?cè)诎倜Φ墓ぷ髦心荞雎?tīng)和指導(dǎo)！作者：余祥榮2019年4月22日摘要細(xì)分曲面具備了靈活性和多分辨率結(jié)構(gòu)并可表示任意拓?fù)渚W(wǎng)格，所以在許多 領(lǐng)域中有著諸

8、多應(yīng)用。根據(jù)極限曲面是否插值于給定初始網(wǎng)格的頂點(diǎn)，可將細(xì)分 格式分為插值型細(xì)分和逼近型細(xì)分。一般情況下，插值型細(xì)分對(duì)不規(guī)則網(wǎng)格和尖 銳特征比較敏感，且產(chǎn)生的細(xì)分曲面質(zhì)量低于逼近型細(xì)分，因此學(xué)者們提出了一 系列迭代插值算法來(lái)實(shí)現(xiàn)逼近型細(xì)分曲面插值于初始頂點(diǎn)；其中，基于漸進(jìn)插值 的細(xì)分曲面算法是漸進(jìn)迭代逼近在細(xì)分曲面上的拓展。這種漸進(jìn)插值算法不僅具 有局部方法和全局方法的優(yōu)點(diǎn)，即可以處理任意大小和任何拓?fù)浣Y(jié)構(gòu)的網(wǎng)格，而 且可以生成光滑的插值型細(xì)分曲面，且細(xì)分曲面較好的保持了初始網(wǎng)格的形狀。采用傳統(tǒng)的漸進(jìn)插值算法，可以實(shí)現(xiàn)讓逼近型細(xì)分曲面插值初始頂點(diǎn)，已取 得了較為理想的效果，然而隨著數(shù)據(jù)點(diǎn)的不斷增

9、加，計(jì)算量的不斷增大，因此如 何利用該算法處理大規(guī)模數(shù)據(jù)點(diǎn)是現(xiàn)今的熱點(diǎn)問(wèn)題。此外，在流體動(dòng)力學(xué)和空氣 動(dòng)力學(xué)領(lǐng)域的功能曲線/曲面設(shè)計(jì)中，切平面及曲率的插值至關(guān)重要。因此有必要 給出一種插值于法向量的漸進(jìn)插值算法。鑒于以上研究現(xiàn)狀，本文做了如下工作:根據(jù)漸進(jìn)插值的局部性質(zhì)，給出了細(xì)分曲面漸進(jìn)插值的自適應(yīng)數(shù)據(jù)擬合算 法。初始頂點(diǎn)被分為兩個(gè)動(dòng)態(tài)調(diào)整的點(diǎn)集，即動(dòng)點(diǎn)集和定點(diǎn)集。當(dāng)精度給定時(shí)， 根據(jù)每次迭代的結(jié)果動(dòng)態(tài)地調(diào)整這兩類頂點(diǎn)。迭代算法僅操作動(dòng)點(diǎn)集的頂點(diǎn)，隨 著動(dòng)點(diǎn)集內(nèi)頂點(diǎn)數(shù)不斷的減少，定點(diǎn)集內(nèi)頂點(diǎn)數(shù)不斷的增加，需操作的頂點(diǎn)隨之 減少，從而大大減少了計(jì)算量。此外，文中還給出了自適應(yīng)權(quán)值算法，即自適應(yīng)

10、 給頂點(diǎn)賦權(quán)值，對(duì)前期迭代中收斂較慢頂點(diǎn)的收斂速度進(jìn)行加速，使其滿足給定 的收斂速度閾值。提出一種帶矩陣權(quán)值的Catmull-Clark細(xì)分曲面漸進(jìn)插值算法，旨在進(jìn)一步 解決漸進(jìn)插值算法不能插值細(xì)分曲面法向量的局限。首先，定義了一個(gè)3x3的矩 陣類型的權(quán)值，稱之為矩陣權(quán)值，借助于選取不同的矩陣權(quán)值來(lái)控制漸進(jìn)插值算 法的收斂速度和極限曲面的形狀，并通過(guò)插值細(xì)分曲面法向量來(lái)實(shí)現(xiàn)細(xì)分曲面的 光順；其次，將矩陣權(quán)值分解為兩個(gè)矩陣之和，分別控制收斂速度和曲面形狀及 光順；最后，給出了兩種矩陣權(quán)值的取法，分別通過(guò)對(duì)角矩陣權(quán)值實(shí)現(xiàn)極限曲面 形狀的控制，及旋轉(zhuǎn)矩陣權(quán)值實(shí)現(xiàn)插值法向量，進(jìn)而實(shí)現(xiàn)曲面光順。關(guān)鍵詞：

11、漸進(jìn)迭代逼近；細(xì)分曲面；漸進(jìn)插值；自適應(yīng)；矩陣權(quán)值A(chǔ)BSTRACTSubdivision surface has lots of applications in many fields due to its flexibility, multi-resolution structure and the ability to represent arbitrary topological meshes. A subdivision scheme is called an interpolating scheme if the limit surface interpolates vertices

12、 of the original mesh. Otherwise, it is called an approximating scheme. In general, interpolating subdivision schemes are sensitive to sharp features & irregular meshes and may produce low quality surfaces comparing with those of the approximating subdivision schemes. In order to make approximating

13、scheme interpolate or fit original vertices, scholars have proposed a series of iterative interpolation algorithms. Among them, progressive interpolating subdivision scheme is an extension of the progressive-iterative approximation(PIA) method on the subdivision surface. This progressive interpolati

14、on algorithm has the advantages of local and global methods. That is, it can handle control meshes of any size and any topology while generating smooth subdivision surfaces that faithfully resemble shapes of initial meshes.Traditional progressive interpolation subdivision schemes can interpolate or

15、fit vertices by applying approximating subdivision schemes, and it can achieve desirable results. However, with the increasing number of original vertices, the convergence speeds become slow and computation complexity gets huge. Therefore, how to use interpolation algorithm to deal with large-scale

16、data is a hot issue nowadays. Furthermore, in the field of hydrodynamics and aerodynamics, the interpolation or fitting tangent planes and curvatures of the given surfaces is very important. Consequently, it is necessary to propose an progressive interpolation subdivision schemes which can interpola

17、te or fit tangent planes and curvatures of the given surfaces. In view of the above research status, the following work has been done in this dissertation:1. Base on the local properties of progressive interpolation, an adaptive progressive interpolation subdivision scheme is presented. The vertices

18、 of control mesh are classified into two classes: active vertices and fixed ones. When precision is given, two classes vertices are changed dynamically according to result of each iteration. Only the active vertices are adjusted, thus the class of active vertices keep running down while the fixed on

19、es keep rising, which saves computation greatly. Furthermore, an adaptive weight algorithm is also given, which assigns weights to the vertex adaptively, speeds up the convergence of slower vertices, and make them satisfies the given convergence speed threshold, so that the convergence speed can be

20、adaptively controlled.One progressive interpolation algorithm of Catmull-Clark subdivision surface with matrix weight is presented. It aims to interpolate the normal vector of subdivision surface which traditional progressive interpolation algorithm cant make it. First, a 3 X3 weight matrix is prese

21、nted as the weight of the given progressive interpolation algorithm. Different matrix weights have been given in order to not only control convergence speeds & shapes but also interpolate the normal vector so as to smooth the limit surface. Second, the weight matrix can be decomposed into the sum of

22、 two matrices, one controls the convergence rate, the other controls the surface shape and smoothness. Finally, this dissertation also presents two different ways to determine the weight matrix. One is designing the diagonal matrix in order to control the shape of the limit surface. The other is des

23、igning the rotation matrix in order to iteratively interpolate the normal vector to smooth the limit surface.KEYWORDS: progressive-iterative approximation; subdivision surface; progressive interpolation; adaptive; matrix weight TOC o 1-5 h z HYPERLINK l bookmark51 o Current Document 第一章緒論11.1漸進(jìn)迭代逼近和

24、漸進(jìn)插值算法的研究背景及發(fā)展現(xiàn)狀11.2本文的主要研究工作2 HYPERLINK l bookmark54 o Current Document 第二章Loop細(xì)分曲面漸進(jìn)插值的自適應(yīng)擬合算法32.1局部加權(quán)的Loop細(xì)分曲面漸進(jìn)插值算法32.2擬合精度分析52.3自適應(yīng)算法82.3.1自適應(yīng)數(shù)據(jù)擬合算法82.3.2自適應(yīng)權(quán)值算法82.4數(shù)值實(shí)例92.4.1自適應(yīng)數(shù)據(jù)擬合算法實(shí)例9242自適應(yīng)權(quán)值算法實(shí)例132.5本章小結(jié)14 HYPERLINK l bookmark67 o Current Document 第三章 帶矩陣權(quán)值的Catmull-Clark細(xì)分曲面漸進(jìn)插值算法153.1預(yù)備知識(shí)

25、153.2帶矩陣權(quán)值的漸進(jìn)插值算法173.2.1帶矩陣權(quán)值的漸進(jìn)插值算法描述173.2.2收斂性分析183.2.3兩種矩陣權(quán)值的取法203.3數(shù)值實(shí)例213.4本章小結(jié)26 HYPERLINK l bookmark85 o Current Document 第四章總結(jié)與展望27 HYPERLINK l bookmark88 o Current Document 參考文獻(xiàn)28攻讀碩士學(xué)位期間的學(xué)術(shù)活動(dòng)及成果情況31插圖清單 TOC o 1-5 h z 圖2. 1Bishop模型自適應(yīng)數(shù)據(jù)擬合效果圖 10圖2. 2螞蟻模型自適應(yīng)數(shù)據(jù)擬合效果圖 11圖2. 3老虎模型自適應(yīng)數(shù)據(jù)擬合效果圖 11圖2.

26、 3麻雀模型自適應(yīng)數(shù)據(jù)擬合效果圖12S3. 1面分割15圖3. 2尹及其鄰域16圖3. 3L&T矩陣權(quán)值漸進(jìn)插值效果圖21圖3. 4正方體矩陣權(quán)值漸進(jìn)插值效果圖22圖3. 5正八面體矩陣權(quán)值漸進(jìn)插值效果圖24圖3. 6正八面體法向量漸進(jìn)插值效果圖 25圖3. 7法向量漸進(jìn)插值效果圖 26表格清單 TOC o 1-5 h z 表2.1 Bishop模型的迭代次數(shù)和精度 10表2. 2螞蟻模型的迭代次數(shù)和精度 11表2. 3老虎模型的迭代次數(shù)和精度12表2. 4麻雀模型的迭代次數(shù)和精度12表2. 5老虎模型的迭代次數(shù)、精度和權(quán)值13表2. 6 Bishop模型的迭代次數(shù)、精度和權(quán)值13表3.1不同

27、權(quán)值下正方體迭代誤差對(duì)比 23表3.2正八面體頂點(diǎn)(0, 0, 0. 9417)迭代法向量角度差25第一章緒論第一章緒論1.1漸進(jìn)迭代逼近和漸進(jìn)插值算法的研究背景及發(fā)展現(xiàn)狀數(shù)據(jù)點(diǎn)的插值擬合技術(shù)在幾何設(shè)計(jì)和逆向工程中有著廣泛的應(yīng)用，傳統(tǒng)的方 法是通過(guò)解線性方程組來(lái)反求控制頂點(diǎn)，但是隨著數(shù)據(jù)點(diǎn)規(guī)模的增加，對(duì)應(yīng)的線 性方程組規(guī)模也在變大，提高了計(jì)算成本。不僅如此，這些線性方程組經(jīng)常是奇 異的或病態(tài)的，這就導(dǎo)致了無(wú)法通過(guò)求解線性方程組來(lái)解決插值擬合問(wèn)題。為了 解決這一問(wèn)題，學(xué)者們提出了一系列迭代算法。近來(lái)，一種基于“盈虧修正”思 想且具有明顯幾何意義并無(wú)需求解線性方程組的迭代算法一一漸進(jìn)迭代逼近 (P

28、rogressive Iteration Approximation, abbr. PIA)被提出。PIA方法首先由齊東旭 等1在1975年提出，隨后de Boor在一次演講中也闡述了這一思想。2004年，Lin 等證明了非均勻3次B樣條曲線曲面的“盈虧修正性質(zhì)，并證明了其收斂性； 隨后，Lin等人又證明了所有的全正基混合曲線曲面都具有這一性質(zhì)，并創(chuàng)造了英 文術(shù)Progressive Iterative Approximation囹。2007年，Maekawa等將數(shù)據(jù)點(diǎn)的參 數(shù)值取為每次迭代生成的擬合曲線曲面上最近點(diǎn)的參數(shù)值，并命名為geometric interpolation(GI)5_7

29、 o Lu】提出了 加權(quán)漸進(jìn)迭代逼近(Weighted progressive iteration approximation, abbr. WPIA),旨在提高迭代收斂速度。最近，Lin等一些學(xué)者將PIA 方法應(yīng)用到諸多領(lǐng)域J%PIA方法可應(yīng)用在張量積混合曲線曲面上，但是張量積混合曲面不能表現(xiàn)任意 拓?fù)浣Y(jié)構(gòu)，而細(xì)分曲面解決了這一問(wèn)題。細(xì)分曲面是指對(duì)給定的多邊形控制網(wǎng)格, 采用特定的細(xì)分格式，對(duì)其不斷的迭代細(xì)化，進(jìn)而得到光滑的極限曲面。細(xì)分曲 面由于具備了靈活性和多分辨率結(jié)構(gòu)并可表現(xiàn)任意拓?fù)渚W(wǎng)格，所以在諸多領(lǐng)域中 有著重要的應(yīng)用。例如計(jì)算機(jī)圖形學(xué)、曲面建模、計(jì)算機(jī)動(dòng)畫以及數(shù)據(jù)處理等。 根據(jù)極限

30、曲面是否插值于給定初始網(wǎng)格的頂點(diǎn)，將細(xì)分格式分為插值型細(xì)分和逼 近型細(xì)分。流行的插值型細(xì)分有Butterfly細(xì)分的,14以及Kobbelt細(xì)分戚。眾所周 知的逼近型細(xì)分有Catmull-Clark細(xì)分口刀、Doo-Sabin細(xì)分網(wǎng)以及Loop細(xì)分凹。一般 情況下，插值型細(xì)分對(duì)不規(guī)則網(wǎng)格和尖銳特征比較敏感，產(chǎn)生的細(xì)分曲面質(zhì)量低 于逼近型細(xì)分。因此越來(lái)越多的人致力于得到光順的插值于初始網(wǎng)格的細(xì)分曲面 的方法。提高插值細(xì)分曲面光順性的方法主要分為兩類。一類是提出新的插值型 細(xì)分方法，比如變分細(xì)分RS和基于法向的細(xì)分；另一類是通過(guò)求解線性方程組 的方法讓逼近型細(xì)分得到的極限曲面插值于初始網(wǎng)格的頂點(diǎn)2

31、2-26。而實(shí)際情況中 常常要求解大規(guī)模線性方程組，計(jì)算量很大16,26。為了避免求解大規(guī)模線性方程 組，學(xué)者們提出了一系列算法27-29。其中，將漸進(jìn)迭代逼近方法應(yīng)用于細(xì)分曲面上，從而得到了漸進(jìn)插值算法(progressive interpolation abbr. PI)。這種漸進(jìn)插值 算法具有局部方法和全局方法的優(yōu)點(diǎn)，即它可以處理任意大小和任何拓?fù)浣Y(jié)構(gòu)的 網(wǎng)格，同時(shí)生成光滑的插值型細(xì)分曲面，且細(xì)分曲面較好的保持了初始網(wǎng)格的形 狀。Cheng等3。最近提出了一種新的基于Loop細(xì)分曲面的漸進(jìn)插值方法。Chen等 也提出了一種新的基于Catmull-Clark細(xì)分曲面的漸進(jìn)插值方法。Deng

32、等閔提出了 Loop細(xì)分曲面的加權(quán)漸進(jìn)插值方法，分析并給出了最優(yōu)權(quán)值的取法。趙宇等33】提 出了細(xì)分曲面漸進(jìn)插值具有局部性質(zhì)，即僅調(diào)整初始網(wǎng)格頂點(diǎn)集合的某一子集， 保持其余頂點(diǎn)不變，最終生成的極限曲面仍然插值于初始網(wǎng)格中這些被調(diào)整頂點(diǎn)。 因此，用漸進(jìn)插值算法可以實(shí)現(xiàn)逼近型細(xì)分曲面插值初始網(wǎng)格上的點(diǎn)，并取得了 較為理想的效果。漸進(jìn)迭代逼近和漸進(jìn)插值算法從提出以來(lái)，經(jīng)過(guò)眾多學(xué)者的不斷研究，逐漸 得到了完善。各種方法的提出，使得漸進(jìn)迭代逼近和漸進(jìn)插值算法在理論和實(shí)際 應(yīng)用中不斷發(fā)展。1.2本文的主要研究工作本文主要研究了細(xì)分曲面的漸進(jìn)插值算法及其光順，包括：1)針對(duì)傳統(tǒng)擬合 算法對(duì)現(xiàn)今大規(guī)模數(shù)據(jù)擬合

33、過(guò)程的計(jì)算開(kāi)銷過(guò)大的問(wèn)題，提出細(xì)分曲面漸進(jìn)插值 的自適應(yīng)擬合算法；2)由于漸進(jìn)插值算法僅能插值初始頂點(diǎn)而不能控制曲面形狀, 提出帶矩陣權(quán)值的漸進(jìn)插值算法，該算法不僅能控制曲面形狀，還能通過(guò)插值曲 面的法向量實(shí)現(xiàn)曲面光順。本文內(nèi)容安排如下：第一章介紹了細(xì)分曲面漸進(jìn)插值算法的研究背景和發(fā)展現(xiàn)狀，以及本文的主 要研究工作。第二章 給出了局部加權(quán)的Loop細(xì)分曲面漸進(jìn)插值算法，并在此基礎(chǔ)上，提出 了自適應(yīng)數(shù)值擬合算法和自適應(yīng)權(quán)值算法。通過(guò)對(duì)自適應(yīng)算法精度和收斂性的分 析，證明了算法的正確性和有效性，章節(jié)最后給出的數(shù)值實(shí)例進(jìn)一步驗(yàn)證了算法 的有效性。第三章 提出了帶矩陣權(quán)值的Catmull-Clark細(xì)

34、分曲面漸進(jìn)插值算法，通過(guò)選取 不同的矩陣權(quán)值來(lái)控制漸進(jìn)插值算法的收斂速度和極限曲面的形狀，并插值細(xì)分 曲面法向量來(lái)實(shí)現(xiàn)細(xì)分曲面的光順。章節(jié)最后的數(shù)值實(shí)例，展示了矩陣權(quán)值的作 用。第四章 本文研究的總結(jié)，并給出了未來(lái)還可以進(jìn)一步研究的內(nèi)容。第二章Loop細(xì)分曲面漸進(jìn)插值的自適應(yīng)擬合算法細(xì)分曲面和數(shù)據(jù)擬合技術(shù)近年來(lái)在計(jì)算機(jī)輔助幾何設(shè)計(jì)、計(jì)算機(jī)圖形學(xué)以及 游戲動(dòng)畫等得到了廣泛的應(yīng)用。這使得細(xì)分曲面和數(shù)據(jù)擬合越來(lái)越受到學(xué)者們關(guān) 注。隨著數(shù)據(jù)點(diǎn)規(guī)模的增加，數(shù)據(jù)點(diǎn)插值擬合的計(jì)算量不斷變大。為了解決這些 問(wèn)題，本章提出了細(xì)分曲面漸進(jìn)插值的自適應(yīng)擬合算法，從而大大節(jié)省了計(jì)算量。 本章首先給出了自適應(yīng)算法的理論

35、基礎(chǔ)，然后分析了擬合精度并給出了自適應(yīng)數(shù) 據(jù)擬合算法和自適應(yīng)權(quán)值算法，最后通過(guò)數(shù)值算例驗(yàn)證了該方法的正確性和有效 性。2.1局部加權(quán)的Loop細(xì)分曲面漸進(jìn)插值算法Zhao和Lin等人33的研究表明，漸進(jìn)插值可以根據(jù)不同的應(yīng)用背景，全局或 局部插值細(xì)分曲面的頂點(diǎn)。漸進(jìn)插值的局部特性為形狀控制帶來(lái)了更大的靈活性, 使自適應(yīng)擬合成為可能。因此，提出了一種基于局部加權(quán)的Loop細(xì)分曲面漸進(jìn)插 值算法，該算法也可用于其它逼近型細(xì)分曲面。局部加權(quán)漸進(jìn)插值的過(guò)程如下：給定一個(gè)三角形網(wǎng)格=咋,*吁。初始頂點(diǎn)分為兩個(gè)子集，一個(gè)是 固定集*, j E J = 描其差分向量小于給定閾值；另一個(gè)是活動(dòng)集 、,作I =

36、 iV其差分向量大于給定閾值。操作只應(yīng)用于動(dòng)點(diǎn)集，定點(diǎn) 集保持不變。在迭代*次后，我們可以得到第*次三角網(wǎng)格7T =咋,頃.,吁及其對(duì)應(yīng)的 頂點(diǎn)咋EJ = 】,/, e/ = 知勺廣叫 o第S次網(wǎng)格MS可以通 過(guò)操作動(dòng)點(diǎn)集(V；WI = iVj)得到：D： = y -,(2.1)咋+1 =咋 + 叫,(2.2)其中是權(quán)值，其取值范圍是(0,2)。通過(guò)對(duì)動(dòng)點(diǎn)集中的每個(gè)頂點(diǎn)進(jìn)行上述操作后， 可以得到=咋+吁+.,吁+1。重復(fù)上述步驟，可以得到一系列網(wǎng)格 Mk =定義函數(shù)：*是與匕相鄰的動(dòng)點(diǎn)出匕匕)=0,其他令D. =EDD.、D：V為動(dòng)點(diǎn)集差分向量的集合,D=叫由.塑是 定點(diǎn)集差分向量的集合。對(duì)于

37、上述Loop細(xì)分曲面的局部加權(quán)漸進(jìn)插值，有如下定 理。1 定理2.1.1當(dāng)?shù)螖?shù)上oo時(shí)，D：收斂到0, D：收斂到D； +wCB D；,其中，1-/3IfHn如柘hHn M1-/3Hn hHn s11-8 x (- + (- +-cos8842tt= H(ypvy3j證明：對(duì)于動(dòng)點(diǎn)集(z= - c1 = - y-+1+(i 0)q：h)，根據(jù)式(2.1)、(2.2)以及Q,Q： +w項(xiàng)D 可以得到QS和邛之間的關(guān)系,71 心,“d：+ =玖ME + 上n lei,其中，是頂點(diǎn)咋的價(jià)，Q：和Q；是與咋相鄰的動(dòng)點(diǎn)，匕是與咋相鄰的動(dòng)點(diǎn)的指 標(biāo)集。上述關(guān)系寫成矩陣形式如下：D/+i = e - w

38、B D/ = E-wB Dz.(2.3)切入異 1 ,文獻(xiàn)30證明了 0 A(B) 1 o令p(A)為矩陣A的譜半徑，入帥為矩陣B的最 小特征值。由0也CXDk8這意味著當(dāng)?shù)螖?shù)k x時(shí)，動(dòng)點(diǎn)集差分向量1)收斂到0。 對(duì)于定點(diǎn)集(項(xiàng)0以廣，力)，Dk+1 = y = V0 - (3 儼+1 +(1-(3 )QW,jjj,oojn j/ n / j 7根據(jù)式(2.1)、(2.2)以及Q：+i=q；+初上刀* ,可以得到皆+i和巧之間的關(guān)系, n 叫，/其中，匕是與咋相鄰的動(dòng)點(diǎn)的指標(biāo)集。上述關(guān)系寫成矩陣形式如下:kD尸=D； + wCDj = D； + wCD,l=Q由 p(E - wB) 1,

39、可得klim D尸=D； + 初C lim V D；,Aj OC心一OC Xl=Q根據(jù)式(2.3)可知D； + wC lim J2(E 3B)，D； = D； + wCB D.l=o因此，對(duì)任意的w(0 w 2),當(dāng)?shù)螖?shù)k oo時(shí)，定點(diǎn)集差分向量D；收 斂到 D； + wCB_1D o證畢 定理2.1.1說(shuō)明了迭代格式的動(dòng)點(diǎn)集差分向量收斂到0,定點(diǎn)集差分向量收斂于 一個(gè)常數(shù)。2.2擬合精度分析在自適應(yīng)擬合算法中，將初始頂點(diǎn)分為兩個(gè)動(dòng)態(tài)可調(diào)子集。迭代過(guò)程中需要 調(diào)整的動(dòng)點(diǎn)集中的頂點(diǎn)個(gè)數(shù)在減少，不需要調(diào)整的定點(diǎn)集中的頂點(diǎn)在增加。因此, 自適應(yīng)擬合算法的關(guān)鍵是推導(dǎo)出在每次迭代過(guò)程中隨著動(dòng)點(diǎn)集的變

40、化，定點(diǎn)集中 頂點(diǎn)的差分向量的范數(shù)界。設(shè)在第人次迭代中，動(dòng)點(diǎn)集的指標(biāo)集是匕=z,&.%，動(dòng)點(diǎn)集差分向量集 合為 D* =伏,氣,定義1/的M范數(shù)為回L =max問(wèn)其中，|e是向量的歐幾里得范數(shù)。引理221假設(shè)在*次迭代后，頂點(diǎn)咋變?yōu)槎c(diǎn)，動(dòng)點(diǎn)集的指標(biāo)集為 :z,&.,那么頂點(diǎn)咋的差分向量滿足L of)1 嘰 +iElk(2.4)中，n是頂點(diǎn)咋的價(jià)， QI是與頂點(diǎn)V；相鄰的動(dòng)點(diǎn)，3q /3 ,3 12tt 2。11 8 x (Icos )88 4n證明：假設(shè)初始動(dòng)點(diǎn)集的指標(biāo)集為1 =,且第頂個(gè)頂點(diǎn)是定點(diǎn)。 在迭代過(guò)程中，動(dòng)點(diǎn)集頂點(diǎn)的數(shù)量在減少，定點(diǎn)集頂點(diǎn)的數(shù)量在增加。假設(shè)在第 奸1次迭代后，動(dòng)點(diǎn)

41、集的指標(biāo)集為/*= &洪,定點(diǎn)集的指標(biāo)集為那 么有k+l其中，是與頂點(diǎn)咋相鄰的動(dòng)點(diǎn)。根據(jù)式(2.1)、(2.2)以及如：*浴%,可得= D_y3 + 上4 刀，隨著迭代的進(jìn)行，動(dòng)點(diǎn)集的差分向量是減小的，這意味著E iElk+iE因此，可得MLD尸一瓦D +碼為n E a-W-(i-)z+1E. n閂妨+(1-刀耕+.+(1-為刀打,金叫+詫y 根據(jù)范數(shù)的性質(zhì)，可得I玲以卻1-時(shí)|嘰+:片號(hào)又因?yàn)? (1 一久)1,所以身岫-5嘰+。烏專=(1-時(shí)以+十/ n證畢引理2.2.1確定了極限差分向量的范數(shù)界。定理2.2.1將給出確定動(dòng)點(diǎn)集的頂 點(diǎn)可以固定的條件。定理221假設(shè)頂點(diǎn)*在前k-1次迭代中

42、均是動(dòng)點(diǎn)，在第k次迭代后變?yōu)槎c(diǎn)，如果它的差分向量巧滿足如下條件釧M(i耳)lEIk(2.5)那么，在之后的迭代過(guò)程中，頂點(diǎn)匕將會(huì)一直為定點(diǎn)，且|刀兒滿足(2.6)|刀；|L M %, (Z =心 + L心 + 2,),其中，&。為給定的精度。證明：因?yàn)閛 + tEe；/ =ij(3.5)n(n + 5)再由文獻(xiàn)26可得Catmull-Clark細(xì)分曲面極限點(diǎn)廣的法向量為(3.6)其中,2tiAn = 1 + cos() + cos(/2(9 + cos(),nn=IZA cos()ej+i + (cos() + cosf + D)*i.)nnn3.2帶矩陣權(quán)值的漸進(jìn)插值算法3.2.1算法描述

43、首先，取一個(gè)3X3的矩陣人為矩陣權(quán)值且其譜半徑為02,矩陣人可以分解 成2個(gè)矩陣之和，即( ) a a】 a21(/ )Q Q Q(2一a3 b Q4U)1+a3 bf Q4缶 c ,1 /5 ae d,其次，給出算法描述。給定初始網(wǎng)格作為控制網(wǎng)格，記為初始網(wǎng)格經(jīng) 過(guò)上次迭代之后得到的網(wǎng)格。對(duì)上的每個(gè)頂點(diǎn)它的細(xì)分極限點(diǎn)位置記為 廣對(duì)應(yīng)的初始網(wǎng)格上的頂點(diǎn)7與其極限點(diǎn)之間的差分向量7/為(3.7)調(diào)整頂點(diǎn) 得到第k + 1次對(duì)應(yīng)的頂點(diǎn)廣+i =侄 + Wk .(3.8)其中，人是漸進(jìn)插值算法的矩陣權(quán)值。依次對(duì)上所有頂點(diǎn)如此操作，可以得到 一組由新的控制頂點(diǎn)構(gòu)成的新網(wǎng)格Mk+通過(guò)不斷重復(fù)上述步驟，可

44、以得到一組 網(wǎng)格序列肱* , (k 1,2, ) o式(3.8)可以寫成(jj(/ ) a s 缶儼+UJDk +a3 bf Q4zQ5 cLq dvk + wkDk.yk+1前一個(gè)矩陣控制收斂速度，后一個(gè)矩陣根據(jù)其取法的不同實(shí)現(xiàn)形狀控制和光順。可以證明，隨著迭代次數(shù)極限曲面插值于初始網(wǎng)格的頂點(diǎn)，也即細(xì) 分算法是收斂的。稱這種算法為帶矩陣權(quán)值的Catmull-Clark細(xì)分曲面漸進(jìn)插值算 法，簡(jiǎn)稱帶矩陣權(quán)的漸進(jìn)插值算法。下面給出了收斂性的具體分析。3.2.2收斂性分析定理321對(duì)于帶矩陣權(quán)的漸進(jìn)插值算法，給定矩陣W ,其最大特征值為入w， 且滿足0 4 2,即0但(W)2。當(dāng)?shù)螖?shù)k oo時(shí)

45、，7/收斂到0,即 迭代格式是收斂的。其中，A ,w = A ;人為3x3的矩陣。證明：不失一般性，考慮經(jīng)過(guò)&次迭代之后的網(wǎng)格上的任意頂點(diǎn)If ,則 第k + 1次的差分向量礦+】與第k次的差分向量的遞推關(guān)系為=咋_咋 + 1)00雄+ )咋+】+|2咋+】+*咋+1=yoz_:n(n + 5)心 + M+tEK：+iE； + +fAE.+lAE %_ yOJJJJn(n + 5)n(n + 5)=D：-n(n + |)Z+fZ+|Zn(n + 5) 寫成矩陣形式為1、刀;+1=E -WB=E -WB k+10。D； /其中，&形如W分塊的矩陣；對(duì)角線上均為3x3單位矩陣；矩陣no(no +f

46、)no(no + 5)9.8%(%. +5)7.2% (%. + 5)B =98.E + .)7.2勺(.+ 5)勺(.+ 5)勺(.+ 5)98 .72 .+ .)+ 5)+ 5)nE +5),根據(jù)Q山與殄之間的遞推關(guān)系，可知矩陣b的第2行有化個(gè)元素等于 ?/（%（%+5）,另外有化個(gè)元素等于（%+5）,分別對(duì)應(yīng)于與頂點(diǎn)匕相連 的點(diǎn)和與頂點(diǎn)匕共面不相連的點(diǎn)，其余元素為零。矩陣B的元素4/0且|可，=1, 并且當(dāng)如=。時(shí), = 。定理3.2.1關(guān)鍵是證明矩陣E-WB的譜半徑小于1。因此，將矩陣B拆分成2 個(gè)矩陣的乘積，即B = DS o根據(jù)文獻(xiàn)30可知矩陣。和S是對(duì)稱正定矩陣，并且 |q|wi

47、,所以矩陣。和s的特征值均滿足0 A（Z）1, o a（s）io因此，矩陣B的特征值0 o記矩陣E-WB的譜半徑為P（E-WB）,矩陣B 的最小特征值為入心。由于矩陣W最大特征值為棚（。 匕 2）,所以有P（E - WB） = max|l-|,|l- Amin| 1.因此，帶矩陣權(quán)的漸進(jìn)插值算法是收斂的。證畢上述定理給出了帶矩陣權(quán)的漸進(jìn)插值算法收斂性條件，下面將分析矩陣權(quán)值 對(duì)收斂速度的影響。定理322對(duì)于帶矩陣權(quán)的漸進(jìn)插值算法有21 P（W）M 0 P（W） P（E_WB）=【十八minp（W）-1,P（W） 2I1 + Anin其中，入心是矩陣B的最小特征值；但（W）是矩陣W的譜半徑（但（

48、匹）=棚）。證明：根據(jù)定理3.2.1以及0 入可知，P（E - WB） = max（|l- p（W）|,|l P（W）Amin|.因此，9P（W）M 0 p（W） P（E -WB）=十人minp（W）-1,P（W） 2I1 + 入 min證畢根據(jù)定理3.2.2,有如下推論。2推論3.2.1當(dāng)P（W） = h時(shí)，帶矩陣權(quán)的漸進(jìn)插值算法收斂速度最快， min1 - A 此時(shí)矩陣E - WB的譜半徑為p（E - WB） = -骰。1 + Amin推論3.2.1給出了算法的最優(yōu)權(quán)值，但實(shí)際中往往需計(jì)算規(guī)模較大的矩陣B的最小特征值，計(jì)算量開(kāi)銷大。借助文獻(xiàn)32,本文算法加速收斂時(shí)采用的是實(shí)際效果較好的最優(yōu)

49、權(quán)值1.7o3.2.3兩種矩陣權(quán)值的取法首先，取矩陣權(quán)值人為對(duì)角矩陣形式，通過(guò)對(duì)角線上的元素分別控制漸進(jìn)插值 頂點(diǎn)各分量的收斂速度，進(jìn)而改變極限曲面的形狀。當(dāng)矩陣權(quán)值為標(biāo)量矩陣 時(shí)，帶矩陣權(quán)的漸進(jìn)插值算法退化為基于Catmull-Clark細(xì)分曲面加權(quán)漸進(jìn)插值算 法，此時(shí)只能實(shí)現(xiàn)漸進(jìn)插值的收斂速度控制。其次，利用旋轉(zhuǎn)矩陣給出了一種矩陣權(quán)值的取法，其步驟如下：Stepl.計(jì)算初始網(wǎng)格上的點(diǎn)*對(duì)應(yīng)的極限點(diǎn)吁，8的法向量。Step2,求頃與給定法向量Y的角度差砰。Step3.讓礦向此旋轉(zhuǎn)評(píng)，得到礦，即= RDf , R。是旋轉(zhuǎn)矩陣。Step4.式（3.8）改為葉=咋+Q,重復(fù)上述迭代步驟，直到達(dá)到給

50、定精度。 根據(jù)羅德里格旋轉(zhuǎn)公式可以得到旋轉(zhuǎn)矩陣cos 0 + (1 cos(1 cos 6)nynx + (sin 0)nz (1 cos 0)n n. (sin 9)n(1 cos d)Tixny (sin ff)n,cos 9 + (1 cos 9)riy(1 cos G)nzny + (sin(1 cos B)nxriz + (sin ff)ny(1 cos G)nynz (sin ff)nx . cos 9 + (1 cos其中，(n”n妒nJ是旋轉(zhuǎn)軸由D?和N.叉乘得到的單位向量；。是旋轉(zhuǎn)角即以。根據(jù)旋轉(zhuǎn)矩陣法所取的矩陣權(quán)值，可以實(shí)現(xiàn)在迭代過(guò)程中不斷減小頂點(diǎn)法向 量與初始法向量的角度

51、差，從而得到更加光順的極限曲面。3.3數(shù)值實(shí)例選取不同的矩陣權(quán)值可以控制細(xì)分曲面的收斂速度，控制曲面的形狀及其光 順性。圖3.3所示為L(zhǎng)和T模型在矩陣權(quán)值為標(biāo)量矩陣的效果圖，其矩陣權(quán)值為(1.71.71.7圖3.3(a)所示為L(zhǎng)和T型的初始網(wǎng)格，圖3.3(b)所示為Deng等32的算法應(yīng)用 在Catmull-Clark細(xì)分上的結(jié)果，圖3.3(c)所示為本文算法的結(jié)果。其中，紅線為初 始網(wǎng)格線。在取上述矩陣權(quán)值情況下，本文算法效果退化為基于Catmull-Clark細(xì)分曲面 加權(quán)漸進(jìn)插值算法，其效果與Deng等32的算法權(quán)值取1.7時(shí)應(yīng)用在Catmull-Clark 細(xì)分上是一致的。a.初始網(wǎng)格

52、b.文獻(xiàn)32算法c.本文算法a.初始網(wǎng)格b.文獻(xiàn)32算法c.本文算法圖3.3 L&T矩陣權(quán)值漸進(jìn)插值效果圖Fig 3.3 Fit model L&T by matrix weight progressive interpolation圖3.4所示為正方體模型在矩陣權(quán)值為對(duì)角矩陣圮的效果圖，均迭代10次, 其權(quán)值為町= A = 1,2,3).其中,0.1、L7、L7A =1.7，A =0.14 =1.71.7 /1.7 /0.1 /當(dāng)權(quán)值取Wi時(shí)，對(duì)應(yīng)頂點(diǎn)的工分量收斂較慢，極限曲面向工方向收縮，如圖 3.4(d)中綠色所示。類似地，當(dāng)權(quán)值取W2,W3時(shí)，極限曲面分別向y,z方向收縮， 其效果分別

53、如圖3.4(e), 3.4(f)中藍(lán)色和黃色所示，表3.1所示為不同權(quán)值對(duì)應(yīng)的誤 差對(duì)比。b.插值曲面c. Catmull-Clark 細(xì)分a.初始網(wǎng)格d.權(quán)值為Wie.權(quán)值為%f.權(quán)值為叫圖3.4正方體矩陣權(quán)值漸進(jìn)插值效果圖Fig 3.4 Fit model Cube by matrix weight progressive interpolation表3.1不同權(quán)值下正方體迭代誤差對(duì)比Table 3.1 Comparison of squared iteration errors under different weights人“24迭代次數(shù)XyXyzXyz04.565.78E-017.3

54、8E-017.20E-013.667.38E-017.20E-015.78E-014.6714.338.67E-021.11E-011.08E-013.481.11E-011.08E-018.67E-024.4353.534.39E-055.60E-055.47E-052.835.60E-055.47E-054.39E-053.61102.872.22E-082.84E-082.77E-082.302.84E-082.77E-082.22E-082.94圖3.5所示為正八面體模型在矩陣權(quán)值為對(duì)角矩陣叱的效果圖,均迭代10次, 其權(quán)值為町=A ,(z = i,6).lz )其中，0、L71.7、

55、A =1.7,A =0乂 =1.71.7z1.7 /0 /L7、0、0L4 =04 =1.7,& =00071.7 /當(dāng)權(quán)值取W1時(shí)，僅迭代頂點(diǎn)的分量，極限曲面插值于頂點(diǎn)A, E, D, F,如 圖3.5(e)中綠色所示。類似地，當(dāng)權(quán)值取W2,皿時(shí)，極限曲面分別插值于頂點(diǎn)A B, C, D和C, E, B, F,其效果分別如圖3.5(f), 3.5(g)中藍(lán)色和黃色所示。當(dāng)權(quán)值取W4時(shí)，僅迭代頂點(diǎn)的工分量，極限曲面插值于頂點(diǎn)8 C,如圖3.5(h) 中綠色所示。類似地，當(dāng)權(quán)值取W5, W6時(shí)，極限曲面分別插值于頂點(diǎn)氏尸和A, D, 其效果分別如圖3.5(i), 3.5中藍(lán)色和黃色所示。a.初始

56、網(wǎng)格b.插值曲面c. Catmull-Clark細(xì)分d.初始網(wǎng)格線e.插值 A,E, C,Ff.插值 A 3 C,Dg.插值 B,E, D,Fh.插值8,0i.插值E, Fj.插值A(chǔ) C圖3.5正八面體矩陣權(quán)值漸進(jìn)插值效果圖Fig 3.5 Fit model Octahedron by matrix weight progressive interpolation圖3.6所示為正八面體模型在利用旋轉(zhuǎn)矩陣取的矩陣權(quán)值的效果圖，通過(guò)迭 代，產(chǎn)生一組極限曲面序列，極限曲面序列不斷插值初始控制頂點(diǎn)，極限曲面序 列的法向量與初始給定的法向量角度差不斷減小。圖3.6(a)是初始網(wǎng)格，紅線是初始給定的法向量

57、，綠線是迭代0次極限曲面的 法向量;3.6(b)是利用旋轉(zhuǎn)矩陣取的矩陣權(quán)值經(jīng)過(guò)10次漸進(jìn)插值迭代得到的光滑曲 面，藍(lán)色網(wǎng)格是迭代后的極限曲面，紅線是初始給定的法向量，綠線是迭代10 次的極限曲面法向量。表3.2是圖3.6中正八面體頂點(diǎn)(0,0,0.9417)的迭代法向量角 度誤差。a.初始網(wǎng)格及法向量b.迭代后的網(wǎng)格及法向量圖3.6正八面體法向量漸進(jìn)插值效果圖Fig 3.6 Fit model Octahedron with normal vector by progressive interpolation表3.2正八面體頂點(diǎn)(0,0,0.9417)迭代法向量角度差Table 3.2 Ite

58、rative normal vector angle difference of regular octahedral vertices (0,0,0.9417)迭代次數(shù)初始給定單位法向量極限曲面單位法向量法向量角度差/()0(0,0,1)(0.1756,0.0000,0.9845)10.1341(0,0,1)(0.1582,0.0000,0.9874)9.1055(0,0,1)(0.0181,0.0000,0.9998)1.14610(0,0,1)(0.0023,0.0002,0.9999)0.141圖3.7所示分別為十二面體、圓環(huán)和環(huán)形結(jié)模型在利用旋轉(zhuǎn)矩陣取的矩陣權(quán)值 的效果圖，通過(guò)迭代，

59、產(chǎn)生一組極限曲面序列，極限曲面序列不斷插值初始控制 頂點(diǎn)，極限曲面序列的光順性也不斷提高。圖3.7(a)分別是十二面體、圓環(huán)和環(huán)形結(jié)的初始網(wǎng)格，圖3.7(b)分別是對(duì)應(yīng)的 利用旋轉(zhuǎn)矩陣取的矩陣權(quán)值經(jīng)過(guò)10次漸進(jìn)插值迭代得到的光滑曲面；其中，紅線 為初始網(wǎng)格線網(wǎng)格。a.初始網(wǎng)格b.極限曲面圖3.7法向量漸進(jìn)插值效果圖Fig 3.7 Fit model with normal vector by progressive interpolation3.4本章小結(jié)本章提出了一種帶矩陣權(quán)值的Catmull-Clark細(xì)分曲面漸進(jìn)插值算法。通過(guò)取 不同的矩陣權(quán)值來(lái)控制收斂速度及極限曲面形狀，以實(shí)現(xiàn)光順的效

60、果。對(duì)角矩陣 權(quán)可以控制漸進(jìn)插值各分量的收斂速度，實(shí)現(xiàn)了對(duì)極限曲面的形狀控制。當(dāng) 矩陣權(quán)值為標(biāo)量矩陣時(shí)，其效果與Deng等32的算法應(yīng)用在Catmull-Clark細(xì)分上 是一致的。當(dāng)矩陣權(quán)值為利用旋轉(zhuǎn)矩陣所取時(shí)，則可以通過(guò)插值曲面法向量來(lái)提 高極限曲面的光順性。第四章總結(jié)與展望總結(jié)本文工作如下：第一，回顧了漸進(jìn)迭代逼近和漸進(jìn)插值的發(fā)展現(xiàn)狀，針 對(duì)現(xiàn)有方法插值擬合大規(guī)模數(shù)據(jù)點(diǎn)的局限性，提出了漸進(jìn)插值的自適應(yīng)數(shù)據(jù)擬合 算法，即將數(shù)據(jù)點(diǎn)分為動(dòng)態(tài)調(diào)整的動(dòng)點(diǎn)集和定點(diǎn)集，在迭代過(guò)程中僅操作動(dòng)點(diǎn)集, 使得動(dòng)點(diǎn)集頂點(diǎn)個(gè)數(shù)不斷減小，這樣大大減少了計(jì)算量，同時(shí)還給出了自適應(yīng)權(quán) 值算法，可以控制收斂速度。第二，從