【正文】 30 第二步，令 )1()( m inm a x ??? axxdx ， )1()( m inm a x ??? byydy ，對顯示區(qū)域內(nèi) 的所有點，按序執(zhí)行下面的循環(huán)操作。 29 . Julia 集 Julia 集是由法國數(shù)學(xué)家 Gaston Julia 和 Pierre Faton 在發(fā)展了復(fù)變函數(shù)迭代的基論后獲得的。該集合的面積是零，而線的歐氏長度趨于無窮大。在這里，長度和面積對 F的形狀和大小都沒有提供很有效的描述。選取一個歐氏長度為L0的直線段，將該線段三等分，去掉中間一段，剩下兩段。 設(shè)函數(shù) )(xfy? ，若給 定 x 的一個初值，記為 0x ，則由式子 )(xfy? 可得到y(tǒng) 的一個值，可記為 1x ，下面將這個 1x 作為 x 的新值，可以得到 y 的新值 )(xfy? ，記為 2x ，即 )( 12 xfx ? ，這樣反復(fù)迭代 )(1 nn xfx ?? ，即， n=0,1,2,? ,從而得到一個序列 0x ， 1x ， 2x ，?， nx ，?，這個序列稱為 0x 的軌道 [5]。 （字符串替換） 文法構(gòu)圖算法是仿照語言學(xué)中的語法生成方法來構(gòu)造圖形的一種算法。為了便于研究，往往作重要的理想化假設(shè)，即假定它是自相似的。 設(shè) F 是 Rn中任一非空有界子集，記 N(F,δ )表示最大直徑為δ且能覆蓋 F的集合的最小數(shù)，則 F的上下維盒定義為 )/1ln( ),(lnlimdi m 0 ? ?? FNFB ??， )/1ln( ),(lnlimdi m 0 ? ?? FNFB ??. () 如果上下相等，則 F的盒維數(shù)定義為 )/1ln( ),(lnlimdi m 0 ? ?? FNFB ??. () 盒維數(shù)存在下面的等價定義，這是由于在上面的定義中可以對 N(F,δ )有不同的取法，通?？扇∠旅嫖宸N之一： （ 1）覆蓋 F的半徑為δ的最小閉球數(shù)； （ 2）覆蓋 F的邊長為δ的最小立方塊數(shù)； （ 3）相交于 F 的δ 網(wǎng)格塊數(shù)； （ 4）覆蓋 F的直徑至多為δ的最小集合數(shù)； （ 5）球心在 F 中半徑為δ的相互不交球的最大數(shù)。 數(shù)學(xué)上的維數(shù)并不是一個很簡單的、易于理解的東西， Caratheodory1914 年提出了用集的覆蓋來定義測度的思想， Hausdorff 于 1919 年用這種方法定義了并以他名字命名的測度和維數(shù)。隨機分形雖然也有一套規(guī)則，但是在生成過程中對隨機性的引入，將使得最終的圖形是不可預(yù)知的。那么究竟什么是分形呢？ 1982 年 Mandelbrot 對分形的定義是“ A fractal is by definition a set for which the HausdorffBesicoritch dimension strictly exceed the topological dimension”，即分形是一個其豪斯道夫 —— 貝西科維奇維數(shù)嚴格大于其拓撲維數(shù)的集合。 第二階段大致為 1926 年至 1975 年，這一階段更為系統(tǒng)、深入研究深化了 第一階段的思想，逐漸形成了理論，并將研究范圍擴大到數(shù)學(xué)的許多分支中。 10 從計算機圖形學(xué)目前學(xué)科發(fā)展來看，有以下幾個發(fā)展趨勢 [7]： 1) 與圖形硬件的發(fā)展緊密結(jié)合，突破實時高真實感、高分辨率渲染的技術(shù)難點 。它綜合了應(yīng)用數(shù)學(xué)、計算機科學(xué)等多方面的知識 圖形與圖像兩個概念間的區(qū)別越來越模糊，但還是有區(qū)別的： 圖像指計算機內(nèi)以位圖形式存在的灰度信息，而圖形含有幾何屬性，或者說更強調(diào)場景的幾何表示，是由場景的幾何模型和景物的物理屬性共同組成的。 在大量的收集資料以及學(xué)習(xí)和借鑒前人研究成果的基礎(chǔ)上，本文將重點進行如下的研究工作： (1) 分形圖形的計算機生成算法設(shè)計。 Cantor 集、 Koch 曲線、 Sierpinski 集、 Julia集、 Mandelbrot 集、牛頓法迭代分形、 Lsysterm 分形等都是經(jīng)典分形圖形。 . 分形圖的計算機生成 我們知道要用計算機來生成圖形，必須遵循一定的規(guī)則，即一定的算法 [1]。所以分形圖形錯綜、多變、絢麗和富于表現(xiàn)，在圖像設(shè)計上具有重要的應(yīng) 4 用價值。 本文主要研究分形理論在計算機科學(xué)中的應(yīng)用，特別是在計算機圖形繪制方面的實際應(yīng)用。分形在用于壓縮圖像信息中的圖像信息的提取和識別、紋理圖像分割、分形圖像編碼等方面，都取得了很好的效果。借助于分形的計算機生成，從少量的數(shù)據(jù)生成復(fù)雜的自然景物圖形，使我們在仿真模擬方面前進了一大步。 幾 乎 在曼德布勞特獲得 Barnard 獎?wù)碌耐瑫r，以德國布來梅大學(xué)的數(shù)學(xué)家和計算機專家 與 等為代表，在當時最先進的計算機圖形工作站上制作了大量的分 形圖案； J. Hubbard 等人還完成了一部名為《混沌》的計算機動畫。就是最追求時尚元素的舞蹈服裝和演藝服裝也很少用到分形圖案。 2. 分形理論的基本知識 本章主要介紹計算機圖形學(xué)的一些基本知識并給出分形理論發(fā)展的三個階段，分形的定義和基本特征，分形維數(shù)定義和計算，分形幾何與歐氏幾何的區(qū)別等。豐富多彩的 Web 網(wǎng)頁更加激勵了計算機圖形學(xué)的應(yīng)用，科學(xué)計算的可視化、虛擬現(xiàn)實技術(shù)等新興課題又向計算機圖形學(xué)提出了更新更高的要求。馮 Mandelbrot 將前人的研究進行總結(jié)，集其大成，于 1975 年以“分形 :形狀、機遇和維數(shù)”為名發(fā)表了他的劃時代專著，第一次系統(tǒng)地闡述了分形幾何的思想、內(nèi)容、意義和方法。 需要說明的是，并不是所有的分形都滿足上面的所有性質(zhì)，有的滿足其中的某條或幾條性質(zhì)，或?qū)δ硞€性質(zhì)有另外。一般說來，如果某圖形是由把原圖縮小為 1/a 的相似 的 b 個圖形所組成，有： ,baD? abD lo glo g? （ ） 的關(guān)系成立，則指數(shù) D 稱為相似性維數(shù)， D 可以是整數(shù)，也可以是分數(shù)。 Hausdorff 維的定義： 對任意給定的集合 F和 1?? ， )(FHp? 對于 p來說是非增的，因為當 p=0 時，只要 F非空，必有 ??)(FHp? 。 歐式幾何學(xué)以規(guī)整的幾何圖形作為其研究對象。如圖 所示。 IFS 將待生成的圖像看成是由許多與整體相似的（自相似）或經(jīng)過一定變換與整體相似的（自仿射）小塊拼貼而成。本章主要描述一些經(jīng)典的分形圖形的生成原理，以便推導(dǎo)出更一般的分形圖形的生成方法。 三分 Cantor 集 F 是由屬于所有 Ek當 k 趨于無窮時的極限，是一個不可數(shù)的無窮集。對該四面體無限次等分操作后，原來的等邊三角形成了具有相似結(jié)構(gòu)的不均勻地向上凸起的面。 (2)它們都具有無窮多個自相似的內(nèi)部結(jié)構(gòu)。 在這里，一個迭代函數(shù)圖 { kf }就稱為一個離散的動力系統(tǒng)。 由于定義 ()不適合計算的目的，下面將給出一個等價定義，它在確定參數(shù)c 是否在 M 中，及在研究 M 的非常復(fù)雜的結(jié)構(gòu)中十分有用。集 V稱為 F 的吸引域。在 Sierpinski 墊中，它的面積趨于零，而其周長趨于無窮大，因此它的維數(shù)只可能介于 1 和 2 之間； Sierpinski 海綿的體積趨于零，而其表面積卻趨于無窮大，所以它的 維數(shù)只能介于 2 和 3 之間。例如，四次 Koch 曲線，其相似維數(shù)為： 8ln ??sD 另一種推廣，是將上述的直線段向二維歐氏平面推廣。再分別去掉這兩個區(qū)間的中間 1/3而得到 E2，即 E 包含 [0， 1/9]、 [2/9，1/3]、 [2/3， 7/9]、 [8/9， 1]四個區(qū)間。特別是隨著計算機的發(fā)展，用這種方法編寫的代碼在計算機上實現(xiàn)分形圖非常方便。 迭代函數(shù)系統(tǒng)可以追溯到 Hutchinson 于 1981 年對相似集的研究。下面以 Koch 曲線為例對遞歸算法進行說明。比如，當 F 為一條平面曲線時，測量值 )(FM?可以看成是以長度δ為步長的兩腳規(guī)穿越整個 F 而得到的步數(shù)。實際上，（ ）式中的極限通常為 ? 或零。將它們的邊長二等分，此時，原圖的線度縮小為原來的 1/2，而將原圖等分為若干個相似的圖形。 （ 4）分形集在某種意義下的分形維數(shù)一般大于它的拓撲維數(shù)。在此之前雖取得許多重要成果，但主要還是局限于純數(shù)學(xué)理論的研究，與其它學(xué)科未發(fā)生聯(lián)系，同時物理、地質(zhì)、天文和工程學(xué)等學(xué)科已產(chǎn)生大量與分形幾何有關(guān)的問題，迫切需要新的思想與有力的工具來處理。 19世紀初，人們已經(jīng)能區(qū)別連續(xù)和可微的曲線，但卻普遍認為連續(xù)而不可微的點應(yīng)是極少的。 在 80 年代，配備有光柵圖形顯示器的個人計算機和工作站已相當普及，不僅在工業(yè)、管理、藝術(shù)領(lǐng)域發(fā)揮巨大的作用，而且圖形系統(tǒng)已進入了家庭，如計算機家庭教育和游戲。通過對這些經(jīng)典分形圖形及其生成過程的進認識和了解，使讀者能夠?qū)Ψ中卫碚摷胺中螆D生成過程有更深入的理解。而在跟我們大家接觸最多的服裝圖案、家具設(shè)計圖案等并沒有更多的以分形圖形作為圖案的選項，家居設(shè)計中普遍采用橫豎交叉的直線或曲線形成“格子”，比如用格子圖案應(yīng)用在門、沙發(fā)套、床罩、枕罩；還有花卉圖案、幾何圖形、插圖，這些圖形成為近幾年家居圖案的流行元素。在每五年一次的獲獎?wù)呙麊沃?，有愛因斯坦、費米這樣一批享譽世界的科學(xué)家 ,可見曼德布勞特的分形研究在科學(xué)上的地位和影響。 分形理論越來越多的被應(yīng)用到計算機圖形學(xué)領(lǐng)域。 分形理論應(yīng)用于計算機圖形設(shè)計，可以生成許多絢麗多彩的分形圖形，計算機與藝術(shù)很好的結(jié)合在一起，在時裝設(shè)計、家具設(shè)計、廣告設(shè)計等領(lǐng) 域都有廣闊的圖形設(shè)計空間。以 VC++ 作為軟件開發(fā)的工具，實現(xiàn)了對一些經(jīng)典分形圖的繪制，在計算機上實現(xiàn)了牛頓迭代分形圖、 Koch曲線、 Sierpinski墊片， Mandelbrot集、分形樹等經(jīng)典分形圖形?，F(xiàn)在隨著計算機的發(fā)展，這類圖形也可以用計算機生成 ，在分形幾何誕生以來，這一部分的研究一直很熱，科學(xué)家和圖形工作者已經(jīng)用計算機生成了許多經(jīng)典的分形圖形，如 Cantor集； Koch 曲線； Sierpinski 集； Julia 集 Mandelbrot 集等 [1,5]，還有一些根據(jù)分形理論生成的圖形，也可以根據(jù)分形幾何理論自己設(shè)計算法用計算機生成。應(yīng)用這些計算機算法，都可以生成絢麗多彩的分形圖形。 由于 分形理論首先是由國外學(xué)者首先提出的，所以國外開展分形圖形的研究要早于國內(nèi)的研究，并且也取得了一些豐碩成果。根據(jù)收集的各種相關(guān)資料，在對分形理論有更進一步理解和認識的情況下，推導(dǎo)出一些常見的分形圖形的分形維數(shù)，以此可以了解分形圖形的產(chǎn)生過程，從而得到常見的一些分形圖形的生成的計算機程序算法。 9 . 計算機圖形學(xué)的發(fā)展歷史與現(xiàn)狀 1950年，第一臺圖形顯示器作為美國麻省理工學(xué)院 (MIT)旋風(fēng) I號（ Whirlwind I）計算機的附件誕生。 3) 利用日益增長的計算性能，實現(xiàn)具有高度物理真實的動態(tài)仿真 。這些研究結(jié)果極大的豐富了分形幾何的理論，同時維數(shù)理論也得到了進一步發(fā)展并日臻成熟。 1986年 Mandelbrot又給出了分形的另一個定義“ A fractal is a shape made of parts similar to the whole in some way”，即分形集具有某種自相似的特征，有很多分形集沒有包括其中。 . 分數(shù)維 在歐氏空間中，人們習(xí)慣把空間看成三維的，平面或球面看成二維，而把直線或曲線看成一維。 . Hausdorff 維 Hausdorff 維數(shù)是波恩大學(xué)數(shù)學(xué)家豪斯道夫（ FelixHausdorff）在 1919 年從測量的角度引進了的定義。設(shè) iP 表示分形維的元素屬于覆蓋 iU 中的概率，則信息維數(shù)為 ?? lnln10lim????NiiiiPPD （ ） 在等概率 iP =1/N(δ )的情況下，信息維數(shù)等于 Hausdorff 維數(shù)，有時 iD 也被稱為信息量維數(shù)。盡管這種假設(shè)過于簡單化，但只有這樣我們 19 才能研究它們，同時仍適合應(yīng)用的目的。美國語言學(xué)家喬姆斯基（ ）在 20 世紀 50 年代給出了遞歸生成語法的方法，指定了一個或幾個初始字母和一組“生成規(guī)則”，將生成規(guī)則反復(fù)作用到初始字母和新生成的字母上，產(chǎn)生了整個語言。其中的一些點的軌道無論怎樣迭代也不會跑出一定的范圍：而另一些點的軌道則通向無窮遠處。這樣的操作繼續(xù)下去，直至無窮，則可得到一個離散的點集，點數(shù)趨于無窮多，而歐氏長度趨于零。 根據(jù) Hausdorff 維數(shù)的定義， Koch 曲線的 3ln4ln4lo g 3 ??HD ，即HD =，與相似維數(shù)相一致。將這八個小正方形再分別進行九等分，各自去掉中間的一個，保留它們的 27 邊。 一般地， Julia 集是動力系統(tǒng)中的斥子，通過對復(fù)平面上的解析函數(shù)的研究，可關(guān)于排斥集構(gòu)造的很多知識。 第四步，由上式的迭代公式，從 (kx ， ky )計算出 ( 1?kx ， 1?ky )，并令 k=k+1。 Julia 集是將 C值固定，即 p 和 q保持為常數(shù)，讓 Z作為原始點通過迭代而生成新的 Z，以此循環(huán)，每選定一個 C值，就可以在復(fù)平面上生成一幅新的計算機圖形。 對于復(fù)平面迭代產(chǎn)生的 Julia集、 Mandelbrot集的研究大大豐富了分形理論，也顯示了分形幾何在處理復(fù)雜圖形上的突出作用，并且為計算機圖像模擬開辟了一個廣闊的天地。將剩下