一類非線性細(xì)分格式的保凸與分形性質(zhì)

一類非線性細(xì)分格式的保凸與分形性質(zhì)丁友東(上海大學(xué)計(jì)算機(jī)學(xué)院上海200072)華宣積(復(fù)旦大學(xué)數(shù)學(xué)系上海200433)2000.9.261YoudongDing摘要在分析經(jīng)典插值細(xì)分格式的基礎(chǔ)上，本文提出了一類函數(shù)型非線性離散細(xì)分格式，它具有保凸性質(zhì)：在滿足一定條件時(shí),這種格式保證了對(duì)于凸數(shù)據(jù)，其每一步細(xì)分多邊形都是凸的，從而極限曲線也是凸的。數(shù)值例子說明，在不光滑情況下這種格式往往會(huì)產(chǎn)生具有分形性質(zhì)的曲線。2000.9.262YoudongDing1引言曲線曲面生成是CAD/CG領(lǐng)域一個(gè)重要的研究?jī)?nèi)容經(jīng)典方法：

離散連續(xù)離散

(Bézier方法)(deCasteljau算法)(控制點(diǎn)數(shù)學(xué)表達(dá)式曲線曲面離散點(diǎn))優(yōu)點(diǎn):易于分析…缺點(diǎn):計(jì)算量大2000.9.263YoudongDing離散細(xì)分方法根據(jù)初始數(shù)據(jù)由計(jì)算機(jī)直接生成曲線曲面或其它幾何形體的一類方法:

離散離散(控制點(diǎn)細(xì)分離散點(diǎn))優(yōu)點(diǎn):只須存儲(chǔ)離散點(diǎn)列，適合計(jì)算機(jī)存儲(chǔ)和繪制曲線曲面的特點(diǎn)，可以大大加快計(jì)算和生成的速度2000.9.264YoudongDing保形性與插值性的協(xié)調(diào)Bézier方法:有很好的保形性，但插值性差(端點(diǎn)插值)離散細(xì)分方法:有很好的插值性,但保形性差(受線性權(quán)因子的限制)如何兼顧保形性和插值性是幾何造型的許多實(shí)際問題要處理的問題2000.9.265YoudongDing離散細(xì)分方法的歷史1975年,Chaikin、Riesenfeld等提出光滑曲線曲面快速生成的離散細(xì)分算法1987年,Dyn等提出經(jīng)典插值兩步型四點(diǎn)細(xì)分格式1991年,Cararetta、Dahmen、Micchelli等提出穩(wěn)定細(xì)分法(StationarySubdivisionScheme)國內(nèi):1980s,梁友棟、金通光等提出“割角法”2000.9.266YoudongDing離散細(xì)分方法的歷史(續(xù))1990s,有廣泛討論和應(yīng)用(包括國內(nèi)丁瑋、齊東旭在分形曲線生成上的討論,駱巖林、汪國昭在地形地貌模擬上的應(yīng)用等)1992年,Dyn

、劉鼎元等提出了一種參數(shù)型離散點(diǎn)列的保凸插值細(xì)分格式(對(duì)凸數(shù)據(jù))1994年,LeMehaute等討論了一類函數(shù)型離散保凸插值細(xì)分方法2000年,丁友東等也提出了一種對(duì)參數(shù)型離散點(diǎn)列的保凸插值細(xì)分格式(對(duì)一般數(shù)據(jù))2000.9.267YoudongDing離散細(xì)分方法的歷史(續(xù))上述方法共同點(diǎn):均須對(duì)每個(gè)細(xì)分點(diǎn)進(jìn)行獨(dú)立判斷，選擇相應(yīng)的參數(shù),雖然每步采用線性細(xì)分格式，但總的格式不是穩(wěn)定的，即每步采用不同的線性權(quán)因子，這樣就需要花費(fèi)大量的非計(jì)算時(shí)間2000.9.268YoudongDing本文工作在分析經(jīng)典插值細(xì)分格式的基礎(chǔ)上，提出一類函數(shù)型非線性離散細(xì)分格式，在一定的條件下,這種格式保證了對(duì)于凸數(shù)據(jù)，其每一步細(xì)分多邊形都是凸的，從而極限曲線也是凸的。有趣的是，當(dāng)選取合適參數(shù)時(shí)，這種格式往往產(chǎn)生具有分形性質(zhì)的曲線2000.9.269YoudongDing2一類非線性插值細(xì)分格式2000.9.2610YoudongDing多邊形曲線的定義2000.9.2611YoudongDing引理2000.9.2612YoudongDing收斂性(定理1)2000.9.2613YoudongDing保凸性(定理2)2000.9.2614YoudongDing保凸性(定理3)2000.9.2615YoudongDing單調(diào)遞減性質(zhì)2000.9.2616YoudongDing單調(diào)遞減性質(zhì)(圖示)2000.9.2617YoudongDing細(xì)分格式(*)的推廣2000.9.2618YoudongDing細(xì)分格式(*)的推廣(續(xù))2000.9.2619YoudongDing細(xì)分格式(*)的推廣(續(xù))2000.9.2620YoudongDing收斂性(定理4)2000.9.2621YoudongDing保凸性(定理5)2000.9.2622YoudongDing保凸性(定理6)2000.9.2623YoudongDing函數(shù)F(x,y)的其它取法2000.9.2624YoudongDing分形性質(zhì)

當(dāng)合適的參數(shù)被選取時(shí),極限曲線出現(xiàn)分形結(jié)構(gòu)(實(shí)際上,每細(xì)分一次就是一次遞歸,細(xì)分格式就象生成分形圖形的生成元,反復(fù)遞歸生成復(fù)雜的具有分形結(jié)構(gòu)的圖形)2000.9.2625YoudongDing3數(shù)值算例數(shù)據(jù)：{yi}={16.0,9.0,4.0,1.0,0.0,1.0,4.0,9.0,16.0}2000.9.2626YoudongDing(1)經(jīng)典格式，參數(shù)滿足保凸條件2000.9.2627YoudongDing(2)經(jīng)典格式,參數(shù)不滿足保凸條件2000.9.2628YoudongDing(3)經(jīng)典格式,極限曲線有分形性質(zhì)2000.9.2629YoudongDing(4)非線性格式,參數(shù)滿足保凸條件2000.9.2630YoudongDing(5)非線性格式,參數(shù)不滿足保凸條件2000.9.2631YoudongDing(6)非線性格式,極限曲線有分形性質(zhì)2000.9.2632YoudongDing進(jìn)一步的工作考慮這類細(xì)分格式的應(yīng)用結(jié)合應(yīng)用找出特定的細(xì)分格式(函數(shù)F(x