【文章內(nèi)容簡介】 hirlwind I）計(jì)算機(jī)的附件誕生。 1958 年美國 Cal p 公司發(fā)明了滾筒式繪圖儀， Gerber 公司研制出了平板式繪圖儀。 1962 年， MIT林肯實(shí)驗(yàn)室的 ()發(fā)表了一篇題為“ Sketchpad:一個(gè)人 機(jī)通信的圖形系統(tǒng) ” 的博士論文，首次使用了計(jì)算機(jī)圖 形學(xué)（ Computer Graphics）這個(gè)術(shù)語。 60年代中期，美國的 MIT、通用汽車公司、貝爾實(shí)驗(yàn)室和洛克希德等眾多的公司紛紛開展了計(jì)算機(jī)圖形學(xué)的應(yīng)用和研究。 70年代是計(jì)算機(jī)圖形學(xué)技術(shù)進(jìn)入實(shí)用化階段，美國蘋果公司的 Macintosh、IBM 公司的 PC， Apollo、 SUN 公司的工作站都配備了圖形系統(tǒng) 。 在 80 年代，配備有光柵圖形顯示器的個(gè)人計(jì)算機(jī)和工作站已相當(dāng)普及，不僅在工業(yè)、管理、藝術(shù)領(lǐng)域發(fā)揮巨大的作用，而且圖形系統(tǒng)已進(jìn)入了家庭，如計(jì)算機(jī)家庭教育和游戲。 90 年代至今，計(jì)算機(jī)圖形學(xué)朝著標(biāo)準(zhǔn)化、集 成化和智能化的方向發(fā)展 。豐富多彩的 Web 網(wǎng)頁更加激勵(lì)了計(jì)算機(jī)圖形學(xué)的應(yīng)用，科學(xué)計(jì)算的可視化、虛擬現(xiàn)實(shí)技術(shù)等新興課題又向計(jì)算機(jī)圖形學(xué)提出了更新更高的要求。 . 計(jì)算機(jī)圖形學(xué)的發(fā)展趨勢 計(jì)算機(jī)圖形學(xué)狹義上是一種研究基于物理定律、經(jīng)驗(yàn)方法以及認(rèn)知原理，使用各種數(shù)學(xué)算法處理二維或三維圖形數(shù)據(jù)，生成可視數(shù)據(jù)表現(xiàn)的科學(xué)。它是 計(jì)算機(jī)科學(xué) 的一個(gè)分支領(lǐng)域與應(yīng)用方向，主要關(guān)注數(shù)字合成與操作視覺的圖形 內(nèi)容。廣義上來看，計(jì)算機(jī)圖形學(xué)不僅包含了從三維圖形建模、繪制到動(dòng)畫的過程，同時(shí)也包括了對二維矢量圖形以及圖像視頻融合處理的研究。計(jì)算機(jī)圖形學(xué)經(jīng)過將近 40 年的發(fā)展，已進(jìn)入了較為成熟的發(fā)展期。目前，其主要應(yīng)用領(lǐng)域包括計(jì)算機(jī)輔助設(shè)計(jì)與加工，影視動(dòng)漫，軍事仿真，醫(yī)學(xué)圖像處理，氣象、地質(zhì)、財(cái)經(jīng)和電磁等的 科學(xué)可視化 等。由于計(jì)算機(jī)圖形學(xué)在這些領(lǐng)域的成功運(yùn)用，特別是在迅猛發(fā)展的動(dòng)漫產(chǎn)業(yè)中， 帶來了可觀的經(jīng)濟(jì)效益 [1]。 10 從計(jì)算機(jī)圖形學(xué)目前學(xué)科發(fā)展來看，有以下幾個(gè)發(fā)展趨勢 [7]： 1) 與圖形硬件的發(fā)展緊密結(jié)合，突破實(shí)時(shí)高真實(shí)感、高分辨率渲染的技術(shù)難點(diǎn) 。 2) 研究和諧自然的三維模型建模方法 。 3) 利用日益增長的計(jì)算性能，實(shí)現(xiàn)具有高度物理真實(shí)的動(dòng)態(tài)仿真 。 4) 研究多種高精度數(shù)據(jù)獲取與處理技術(shù)，增強(qiáng)圖形技術(shù)的表現(xiàn) 。 5) 計(jì)算機(jī)圖形學(xué)與圖像視頻處理技術(shù)的結(jié)合 。 6) 從追求絕對的真實(shí)感向追求與強(qiáng)調(diào)圖形的表意性轉(zhuǎn)變 。 第一階段為 18751925 年，在此階段上人們已經(jīng)認(rèn)識了幾類典型的分形集，并力圖對這類 幾何與經(jīng)典的歐式幾何的差別進(jìn)行描述、分類和刻畫。 19世紀(jì)初，人們已經(jīng)能區(qū)別連續(xù)和可微的曲線，但卻普遍認(rèn)為連續(xù)而不可微的點(diǎn)應(yīng)是極少的。 1872 年，維爾斯特拉斯證明了一種連續(xù)函數(shù)在任意一點(diǎn)均不具有有限或無限導(dǎo)數(shù)，即 Weierstrass 函數(shù)。馮科赫于 1904 年通過初等函數(shù)方法構(gòu)造了如今被稱為 Van Koch 曲線的處處不可微的連續(xù)函數(shù)，并討論了該曲線的性質(zhì) [12]曲線的構(gòu)造極為簡單，改變了人們認(rèn)為不連續(xù)曲線的構(gòu)造一定非常復(fù)雜的這樣一種看法。特別重要的是該曲線是第一個(gè)人為構(gòu)造出的在結(jié)構(gòu)上具有局部與整體相似的例子。 Peano 于 1890 年構(gòu)造出填充平面的曲線，這一曲線出現(xiàn)后，人們提出應(yīng)正確考慮以前的長度與面積的概念。 Cantor 于 1872 年引入一類現(xiàn)今稱為Cantor 三分集的全不連通的緊集。在當(dāng)時(shí)，人們認(rèn)為這類集合在傳統(tǒng)的研究中是可以忽略的，但是進(jìn)一步的研究結(jié)果表明，這類集合在像三角級數(shù)的唯一性這樣重要問題的研究中不僅不能忽略 ,而且起著非常重要的作用。在分形幾何發(fā)展的第一階段，人們已提出了典型分形對象及相關(guān)問題，并為討論這些問題提供了最基本的工具。 第二階段大致為 1926 年至 1975 年，這一階段更為系統(tǒng)、深入研究深化了 第一階段的思想，逐漸形成了理論，并將研究范圍擴(kuò)大到數(shù)學(xué)的許多分支中。Besicovitch 等人研究了曲線的維數(shù)、分形集的局部性質(zhì)、分形集的結(jié)構(gòu)以及在 11 數(shù)論、調(diào)和分析、幾何測度論等方面的應(yīng)用。這些研究結(jié)果極大的豐富了分形幾何的理論，同時(shí)維數(shù)理論也得到了進(jìn)一步發(fā)展并日臻成熟。 1928 年至 1959 年先后引入了 Bouligand 維數(shù)、覆蓋維數(shù)、熵 9維數(shù)?？坍嫾稀按笮　钡娜萘考捌淙萘烤S數(shù)亦引入到分析中來。同時(shí)，維數(shù)的乘積理論、投影理論、位勢方法、網(wǎng)測度技巧、隨機(jī)技巧均先后建立并成熟，使得分形幾何的研究具有自己的特色與方法。 第三階段為 1975 年至今 ,是分形幾何在各個(gè)領(lǐng)域的應(yīng)用取得全面發(fā)展 ,并形成獨(dú)立學(xué)科的階段。在此之前雖取得許多重要成果，但主要還是局限于純數(shù)學(xué)理論的研究，與其它學(xué)科未發(fā)生聯(lián)系，同時(shí)物理、地質(zhì)、天文和工程學(xué)等學(xué)科已產(chǎn)生大量與分形幾何有關(guān)的問題，迫切需要新的思想與有力的工具來處理。正是在這種形勢下， Mandelbrot 以其獨(dú)特的思想，系統(tǒng)、深入、創(chuàng)造性的研究了海岸線的結(jié)構(gòu)、具強(qiáng)噪聲干擾的電子通訊、月球的表面、銀河系中星體的分布、地貌的生成、湍流的幾何性質(zhì)等典型的自然界中的分形現(xiàn)象，取得了一系列令人矚目的成功 。 Mandelbrot 將前人的研究進(jìn)行總結(jié)，集其大成，于 1975 年以“分形 :形狀、機(jī)遇和維數(shù)”為名發(fā)表了他的劃時(shí)代專著，第一次系統(tǒng)地闡述了分形幾何的思想、內(nèi)容、意義和方法。此專著的發(fā)表標(biāo)志著分形幾何作為一門獨(dú)立的學(xué)科正式誕生。自 1975 年以來，分形理論無論是在數(shù)學(xué)基礎(chǔ)還是在應(yīng)用方面都有快的發(fā)展。在維數(shù)的估計(jì)與算法，分形集的生成結(jié)構(gòu)，分形圖形的計(jì)算機(jī)生成，分形的隨機(jī)理論等方面獲得較深入的結(jié)果，并在自然科學(xué)、材料科學(xué)和工程技術(shù)中取得巨大成功 。 Mandelbrot 在對 19 世紀(jì)下半葉到 20 世紀(jì) 上半葉出現(xiàn)的當(dāng)時(shí)被人們形象的稱為“數(shù)學(xué)怪物”的數(shù)學(xué)實(shí)例及許多物理和經(jīng)濟(jì)現(xiàn)象進(jìn)行研究后，終于創(chuàng)立了這門重要學(xué)科 — 分形幾何（ Fractal Geometry）， Fractal 這個(gè)詞是 Mandelbrot 創(chuàng)造的，來源于拉丁文 Fractus, 其英文意思是 broken。 1975 年， Mandelbrot 在巴黎出版了發(fā)文著作《 Les objects fractals： forme， basard et dimension》[12,18]， 1977年他在美國出版了其英文版《 Fractals： Form， Chance， and dimension》，標(biāo)志著分形理論的正式誕生。同年，他又出版了《 The Fractal Geometry of 12 Nature》，但這三本書對社會的影響并不大，但到了 1982 年，隨著《 The Fractal Geometry of Nature》二版的問世，在美國乃至歐洲，迅速形成了“分形熱”。那么究竟什么是分形呢？ 1982 年 Mandelbrot 對分形的定義是“ A fractal is by definition a set for which the HausdorffBesicoritch dimension strictly exceed the topological dimension”，即分形是一個(gè)其豪斯道夫 —— 貝西科維奇維數(shù)嚴(yán)格大于其拓?fù)渚S數(shù)的集合。這個(gè)定義包括一大類具有分?jǐn)?shù)維的分形集，但忽略了某些維數(shù)為整數(shù)的分形集。 1986年 Mandelbrot又給出了分形的另一個(gè)定義“ A fractal is a shape made of parts similar to the whole in some way”，即分形集具有某種自相似的特征，有很多分形集沒有包括其中。目前， 最為流行的一個(gè)定義是： 分形是一種具有自相似特性的現(xiàn)象、圖像或者物理過程。 就像對生命的定義一樣，迄今為止對分形尚未有嚴(yán)密的定義，但具有如下的幾何特征 [14,16]： （ 1）分形集具有精細(xì)的結(jié)構(gòu)，即是說在任意小的尺度之下，它總有復(fù)雜的細(xì)節(jié)。 （ 2）分形集是如此的不規(guī)則，以至它的整體和局部都不能用傳統(tǒng)的幾何語言來描述。 （ 3）分形集通常具有某種自相似性，這種自相似性可以是近似的，也可以是統(tǒng)計(jì)意義上的。 （ 4）分形集在某種意義下的分形維數(shù)一般大于它的拓?fù)渚S數(shù)。 （ 5）分形集在多數(shù)令人感興趣的情形下，以非常簡單的方法定義，或許以遞歸過程產(chǎn) 生。 需要說明的是，并不是所有的分形都滿足上面的所有性質(zhì)，有的滿足其中的某條或幾條性質(zhì)，或?qū)δ硞€(gè)性質(zhì)有另外。自然界和各門應(yīng)用科學(xué)中涉及的分形絕大部分是近似的。當(dāng)尺度縮小到分子的尺寸，分形性也就消失了，嚴(yán)格的分形只存在于理論研究之中。 分形一般分成兩大類，確定性分形和隨機(jī)性分形。如果算法的多次重復(fù)仍然產(chǎn)生同一個(gè)分形圖，這種分形稱之為確定性分形。確定性分形具有可重復(fù)性，即使在生成過程中可能引入了一些隨機(jī)性，但最終的圖形是確定的。隨機(jī)分形指的是盡管產(chǎn)生分形的規(guī)則是確定的，但受隨機(jī)因素的影響，雖然可以使每次生成過 13 程 產(chǎn)生的分形具有一樣的復(fù)雜度，但是形態(tài)會有所不同。隨機(jī)分形雖然也有一套規(guī)則，但是在生成過程中對隨機(jī)性的引入，將使得最終的圖形是不可預(yù)知的。即不同時(shí)間的兩次操作產(chǎn)生的圖形，可以具有相同的分維數(shù)，但形狀可能不同，隨機(jī)分形不具有可重復(fù)性。 . 分?jǐn)?shù)維 在歐氏空間中，人們習(xí)慣把空間看成三維的，平面或球面看成二維，而把直線或曲線看成一維。也可以稍加推廣，認(rèn)為點(diǎn)是零維的，還可以引入高維空間，但通常人們習(xí)慣于整數(shù)的維數(shù)。分形理論把維數(shù)視為分?jǐn)?shù)，這類維數(shù)是物理學(xué)家在研究混沌吸引子等理論時(shí)需要引入的重要概念。為 了定量地描述客觀事物的“非規(guī)則”程度， 1919 年，數(shù)學(xué)家從測度的角度引入了維數(shù)概念，將維數(shù)從整數(shù)擴(kuò)大到分?jǐn)?shù)，從而突破了一般拓?fù)浼S數(shù)為整數(shù)的界限 [8,12]。 分維的概念我們可以從兩方面建立起來：一方面，我們首先畫一個(gè)線段、正方形和立方體，它們的邊長都是 1。將它們的邊長二等分，此時(shí)，原圖的線度縮小為原來的 1/2，而將原圖等分為若干個(gè)相似的圖形。其線段、正方形、立方體分別被等分為 2 22和 23個(gè)相似的子圖形，其中的指數(shù) 3，正好等于與圖形相應(yīng)的經(jīng)驗(yàn)維數(shù)。一般說來，如果某圖形是由把原圖縮小為 1/a 的相似 的 b 個(gè)圖形所組成，有： ,baD? abD lo glo g? （ ） 的關(guān)系成立，則指數(shù) D 稱為相似性維數(shù)， D 可以是整數(shù)，也可以是分?jǐn)?shù)。另一方面，當(dāng)我們畫一根直線，如果我們用 0 維的點(diǎn)來量它，其結(jié)果為無窮大，因?yàn)橹本€中包含無窮多個(gè)點(diǎn)；如果我們用一塊平面來量它，其結(jié)果是 0，因?yàn)橹本€中不包含平面。那么，用怎樣的尺度來量它才會得到有限值呢？看來只有用與其同維數(shù)的小線段來量它才會得到有限值，而這里直線的維數(shù) 為 1（大于 0、小于 2）。與此類似，如果我們畫一個(gè) Koch 曲線，其整體是一條無限長的線折疊而成，顯然，用小直線段量，其結(jié)果是無窮大，而用平面量，其結(jié)果是 0（此曲線中不包含平面），那么只有找一個(gè)與 Koch 曲線維數(shù)相同的尺子量它才會得到有限值， 14 而這個(gè)維數(shù)顯然大于 小于 2，那么只能是小數(shù)（即分?jǐn)?shù)）了，所以存在分維。其實(shí)， Koch 曲線的維數(shù)是： 26 3ln 4ln ??D。 Mandelbrot 認(rèn)為維數(shù)比起形狀和機(jī)遇，更易描述集合的不規(guī)整度或破碎度，因此，他定義：若一個(gè)集合的 Hausdorff 維數(shù) 嚴(yán)格大于它的拓?fù)渚S數(shù)，那么該集合就稱為分形集。 Hausdorff 維就是一種分?jǐn)?shù)維，當(dāng)然，從今天看來這種定義有不令人滿意的地方，它排除一些明顯應(yīng)當(dāng)是分形的集合，但是分?jǐn)?shù)維本身的重要性仍然是不言而喻的，它是分形可以廣泛應(yīng)用于各學(xué)科領(lǐng)域的出發(fā)點(diǎn)。 數(shù)學(xué)上的維數(shù)并不是一個(gè)很簡單的、易于理解的東西， Caratheodory1914 年提出了用集的覆蓋來定義測度的思想， Hausdorff 于 1919 年用這種方法定義了并以他名字命名的測度和維數(shù)。以此為基礎(chǔ)，至今數(shù)學(xué)家們已經(jīng)發(fā)展出了十多種不同的維數(shù)，拓?fù)渚S， Hausdorff 維，相似維，盒子維，信息維等等。 . Hausdorff 維 Hausdorff 維數(shù)是波恩大學(xué)數(shù)學(xué)家豪斯道夫（ FelixHausdorff）在 1919 年從測量的角度引進(jìn)了的定義。要講解 Hausdorf 維首先要理解什么是 Hausdorff 測度，因?yàn)樗且?Hausdorff 測度為基礎(chǔ)的，是各種分?jǐn)?shù)維中最基本的一種，Hausdorff 測度的定義如下 [16]： U是 n維 Euclid 空間 Rn的任意非空子集， U的直徑 U是這樣定義的 ? ?UyxyxU ??? ,:s u p ， () 即 U 中任意兩個(gè)點(diǎn)的最大距離。 如果集合 F ???? Ii Ui1，且 Ui 的最大直徑為 ? ，即 0Ui ≤ ,，則說 {Ui }是 F 的一個(gè) ?? 覆蓋。 假定 F是 Rn的子集， p是非負(fù)數(shù)，對任意的 ? 0，定義 ，覆蓋的是 }F}{:i nf{)( 1 ?? ??? ?? ipi ip UUFH () 并約定空集 0p ?? ，當(dāng) ? 遞減時(shí)，上式的下確界（縮寫為： inf）是非遞減的。記 15 )(lim)( 0 FHFH pp ?? ?? () 稱 )(FHp 為