幾何造型中參數(shù)化與擬合技術(shù)的研究.pdf

1、幾何造型研究三維幾何信息如何在計(jì)算機(jī)內(nèi)表示、分析和綜合．幾何造型是CAD/CAM內(nèi)在的理論基礎(chǔ)和關(guān)鍵技術(shù)，是隨著航空、汽車等現(xiàn)代工業(yè)發(fā)展與計(jì)算機(jī)的出現(xiàn)而產(chǎn)生與發(fā)展起來(lái)的一門學(xué)科．幾何造型作為信息技術(shù)的一個(gè)重要組成部分，將計(jì)算機(jī)高速、海量數(shù)據(jù)存儲(chǔ)及處理和挖掘能力與人的綜合分析及創(chuàng)造性思維能力結(jié)合起來(lái)，對(duì)加速產(chǎn)品開(kāi)發(fā)、縮短設(shè)計(jì)制造周期、提高質(zhì)量、降低成本、增強(qiáng)企業(yè)市場(chǎng)競(jìng)爭(zhēng)能力與創(chuàng)新能力發(fā)揮著重要作用．不論是軍事工業(yè)和民用工業(yè)，建筑行業(yè)和制造

2、加工業(yè)，機(jī)械、電子、輕紡產(chǎn)品，還是文體、影視廣告制作都離不開(kāi)幾何造型技術(shù)． 曲線曲面造型是幾何造型的核心之一．曲線曲面造型研究在計(jì)算機(jī)內(nèi)如何描述曲線曲面，如何對(duì)它的形狀進(jìn)行交互式的顯示與控制．傳統(tǒng)的數(shù)學(xué)方法雖然提供了平面、圓柱面、圓錐面、球面等一類規(guī)則形狀的曲面，但很難用以表達(dá)飛機(jī)、輪船、汽車等現(xiàn)實(shí)生活中千姿百態(tài)的自由曲線曲面形狀．早期，在飛機(jī)和船舶的制造工廠里，傳統(tǒng)的設(shè)計(jì)方法要求設(shè)計(jì)與制造人員必須具備豐富的設(shè)計(jì)經(jīng)驗(yàn)，付出繁重的

3、體力勞動(dòng)，設(shè)計(jì)制造周期長(zhǎng)，制造精度低，互換協(xié)調(diào)性差，不能適應(yīng)現(xiàn)代工業(yè)的發(fā)展．曲線曲面造型就是應(yīng)現(xiàn)代工業(yè)發(fā)展的要求而產(chǎn)生與發(fā)展起來(lái)的，又對(duì)現(xiàn)代工業(yè)的發(fā)展起著巨大推動(dòng)作用． 曲線曲面造型的核心問(wèn)題是計(jì)算機(jī)表示，即要找到既適合計(jì)算機(jī)處理且有效地滿足形狀表示與幾何設(shè)計(jì)要求，又便于形狀信息傳遞和產(chǎn)品數(shù)據(jù)交換的形狀描述的數(shù)學(xué)方法．在曲線曲面造型中，參數(shù)曲線曲面以其構(gòu)造簡(jiǎn)單直觀、易于顯示等特點(diǎn)而流行于世．這種曲線曲面表示方法脫離了對(duì)坐標(biāo)系的依

4、賴，給許多應(yīng)用帶來(lái)了極大的方便．與非參數(shù)表示相比，參數(shù)曲線曲面能較好的滿足形狀數(shù)學(xué)描述的要求．長(zhǎng)期以來(lái)，參數(shù)曲線曲面一直是描述幾何形狀的主要工具，早在20世紀(jì)60年代初被美國(guó)波音公司的弗格森所采用，由Coons、Bézier等大師奠定其理論基礎(chǔ)．Coons曲面、Bézier曲面、NURBS(Non-Uniform Rational B-Spline)曲面等不僅成為幾何設(shè)計(jì)的主要工具，已被作為工業(yè)產(chǎn)品數(shù)據(jù)交換的sTEP(standard

5、for The Exchange of Product Model Data)標(biāo)準(zhǔn)，也作為描述參數(shù)曲線曲面造型按用戶提供的初始信息不同可分為兩類：一類是自由設(shè)計(jì)方法，它只要求設(shè)計(jì)者根據(jù)構(gòu)思給出一些控制點(diǎn)和控制參數(shù)來(lái)定義曲線和曲面，然后在設(shè)計(jì)過(guò)程中允許改變這些控制點(diǎn)和參數(shù)來(lái)調(diào)整曲線和曲面的形狀，直至它們符合設(shè)計(jì)要求為止．另一類是插值或逼近法(工程上統(tǒng)稱為擬合法)，其特點(diǎn)是給定一組離散點(diǎn)，要求生成的曲線或曲面要么通過(guò)所有這些點(diǎn)(成為插值曲線

6、或曲面)，要么以一定的精度貼近這些點(diǎn)(稱為逼近曲線和曲面)．這兩類方法生成的曲線曲面的形狀都受參數(shù)化的影響．參數(shù)化既決定了所表示曲線曲面的形狀，也決定了該曲線曲面上的點(diǎn)與其參數(shù)域內(nèi)的點(diǎn)(即參數(shù)值)之間的一種對(duì)應(yīng)關(guān)系．由此可見(jiàn)，參數(shù)化和插值與逼近技術(shù)是曲線曲面造型的基礎(chǔ)問(wèn)題，具有重要的理論價(jià)值和實(shí)際意義．圍繞這兩個(gè)問(wèn)題，本文研究了參數(shù)曲線的最優(yōu)多邊形逼近、參數(shù)曲線的最優(yōu)參數(shù)化和高密度的海量數(shù)據(jù)點(diǎn)擬合等一類關(guān)鍵問(wèn)題． 本文的主要研究

7、工作如下： 1．研究了參數(shù)曲線的最優(yōu)多邊形逼近 對(duì)傳統(tǒng)的逼近算法——參數(shù)逼近算法和幾何逼近算法進(jìn)行了討論，找出了傳統(tǒng)算法的不足，并在幾何逼近算法的基礎(chǔ)上提出了多邊形逼近新算法．該算法采用貪心技術(shù)，從端點(diǎn)開(kāi)始，逐步定位逼近點(diǎn)．除最后一段外，參數(shù)曲線與逼近線段的最大偏移量總是等于給定的逼近精度，而傳統(tǒng)算法不能確保這一點(diǎn)，導(dǎo)致傳統(tǒng)算法得到的逼近線段數(shù)目偏多．對(duì)于凸參數(shù)曲線，給定逼近精度，證明了該算法得到逼近線段的數(shù)目最少．如果

8、以生成的逼近線段的數(shù)目越少則算法越優(yōu)為標(biāo)準(zhǔn)，則該算法是最優(yōu)的．算法包含求解一個(gè)非線性方程．對(duì)于Bèzier曲線，提出了一種技術(shù)把算法涉及的非線性方程的次數(shù)降低兩次，使得算法能夠精確處理二次曲線． 文中用三個(gè)實(shí)例來(lái)對(duì)比該算法與傳統(tǒng)子分算法的效果，驗(yàn)證了在同一逼近公差下，該算法所需的逼近多邊形的頂點(diǎn)最少．算法直觀可行，具有一定的實(shí)用價(jià)值．該算法的不足之處在于，對(duì)于非凸參數(shù)曲線，不能保證得到最優(yōu)解，不過(guò)得到逼近線段的數(shù)目與最優(yōu)逼近的差

9、額，不超過(guò)該曲線中拐點(diǎn)的數(shù)目，由于生產(chǎn)實(shí)踐中，常用的參數(shù)曲線含有拐點(diǎn)的數(shù)目有限，該算法能夠得到近似最優(yōu)解． 2．研究了參數(shù)曲線的最優(yōu)參數(shù)化問(wèn)題 討論了參數(shù)曲線的弧長(zhǎng)參數(shù)化，分析了有理重新參數(shù)化對(duì)參數(shù)曲線產(chǎn)生的影響．研究了利用有理重新參數(shù)化的自由度，求解參數(shù)曲線最優(yōu)逼近弧長(zhǎng)參數(shù)化的問(wèn)題．提出了一種新的度量曲線的參數(shù)速度與弧長(zhǎng)參數(shù)化接近程度的方法，基于該方法求出了參數(shù)曲線的最優(yōu)參數(shù)化．最優(yōu)參數(shù)化的參數(shù)速度偏離單位速度的最大值

10、達(dá)到最?。c國(guó)外著名學(xué)者Farouki的算法相比，該算法取得的最優(yōu)參數(shù)化的參數(shù)速度偏離單位速度的最大值較?。疚挠萌齻€(gè)實(shí)例來(lái)對(duì)比該算法與Farouki算法的效果，實(shí)例表明該算法比Farouki的算法效果好． 該算法的不足之處在于，由于有理重新參數(shù)化調(diào)整參數(shù)速度的能力有限，對(duì)于參數(shù)速度存在多次波動(dòng)的曲線，最優(yōu)參數(shù)化的參數(shù)速度不能保證處處逼近單位速度． 3．研究了數(shù)據(jù)點(diǎn)的曲線重建問(wèn)題 對(duì)曲線重建進(jìn)行了討論，研究了有序

11、數(shù)據(jù)點(diǎn)的曲線重建問(wèn)題．對(duì)樣條插值曲線進(jìn)行了分析，找出了樣條插值曲線擬合高密度數(shù)據(jù)點(diǎn)的不足．基于二次樣條函數(shù)，給出了一個(gè)擬合高密度的海量數(shù)據(jù)點(diǎn)的算法．對(duì)于給定的一組有序數(shù)據(jù)點(diǎn)，算法利用多邊形逼近，將該組數(shù)據(jù)點(diǎn)分成一個(gè)個(gè)子集，在誤差允許的范圍內(nèi)，每個(gè)子集內(nèi)的數(shù)據(jù)點(diǎn)近似在一條直線上．由一段二次曲線擬合每個(gè)子集的數(shù)據(jù)點(diǎn)，全部數(shù)據(jù)點(diǎn)由在連接處C<'1>連續(xù)的分段二次樣條曲線擬合．該算法保持了樣條函數(shù)結(jié)構(gòu)簡(jiǎn)單，易于計(jì)算的優(yōu)點(diǎn)，并在保持逼近精度的前提

12、下，大大減少了插值曲線的段數(shù)，提高了效率．文中給出實(shí)例來(lái)對(duì)比該算法與傳統(tǒng)樣條插值算法的效果，驗(yàn)證了該算法所需的插值曲線的段數(shù)遠(yuǎn)遠(yuǎn)少于傳統(tǒng)算法． 論文的主要?jiǎng)?chuàng)新點(diǎn)如下： 1)提出了多邊形逼近參數(shù)曲線的新算法．對(duì)于凸參數(shù)曲線，在同樣的逼近精度下，該算法逼近得到逼近線段的數(shù)目最少，因而逼近滿足最優(yōu)條件；除了最后一條邊以外，多邊形的每一條邊到被逼近曲線的最大距離都恰好等于給定的逼近誤差，而傳統(tǒng)算法不能確保這一點(diǎn)，導(dǎo)致傳統(tǒng)算法得到

13、的逼近線段較多；當(dāng)被逼近曲線為Bezier曲線時(shí)，有一種技術(shù)來(lái)降低本算法的計(jì)算復(fù)雜度，使得對(duì)2次Bezier曲線的逼近有精確解． 2)對(duì)于有理重新參數(shù)化，提出了一種度量曲線的參數(shù)速度與弧長(zhǎng)參數(shù)化接近程度的方法．基于該方法求出了參數(shù)曲線的最優(yōu)參數(shù)化．最優(yōu)參數(shù)化的參數(shù)速度偏離單位速度的最大值達(dá)到最?。?3)基于二次樣條函數(shù)，給出了一個(gè)擬合海量數(shù)據(jù)點(diǎn)算法．算法保持了樣條函數(shù)結(jié)構(gòu)簡(jiǎn)單，易于計(jì)算的優(yōu)點(diǎn)，并在保持逼近精度的前提下，大