第7章自然景物模擬玉芬性藝術哈爾濱工業(yè)大學計算機學院蘇小紅2什么是分形？（1/21）著名理論物理學家約翰·惠勒(J.Wheeler)說過：在過去，一個人如果不懂得熵是怎么回事，就不能說是科學上有教養(yǎng)的人；在將來，一個人如果不能同樣熟悉分形，他就不能被認為是科學上的文化人。哈爾濱工業(yè)大學計算機學院蘇小紅3什么是分形？（2/21）非線性科學(nonlinearscience)中最重要的三個概念混沌(chaos,也譯作“渾沌”)分形(Fractal)孤子(soliton，也稱“孤波”(solitarywave))分形理論是非線性科學研究領域中一個十分活躍的分支本質是一種新的世界觀和方法論揭示了有序與無序的統(tǒng)一，確定性與隨機性的統(tǒng)一被認為是科學領域中繼相對論、量子力學之后，人類認識和改造世界的最富有創(chuàng)造性的第三次革命哈爾濱工業(yè)大學計算機學院蘇小紅4第一個分形例子由文藝復興時期德國著名畫家丟勒(AlbertDurer，1471-1528)

(“杜勒”)給出什么是分形？（3/21）D=log5/log(3+SQRT(5)/2)=1.672藝術創(chuàng)作特點：精細，講究科學和數(shù)學與其父精于金銀細工有關與文藝復興時期重視自然科學和數(shù)學的時代風氣也有關丟勒正五邊形分形哈爾濱工業(yè)大學計算機學院蘇小紅5什么是分形？（4/21）1827年，英國植物學家R.Brown（1773-1858）用顯微鏡發(fā)現(xiàn)微細顆粒在液體中作無規(guī)則行走，此現(xiàn)象被稱為布朗運動。后來科學家對布朗運動進行了多方面的研究，維納(N.Wiener，1894-1964)等人在此基礎上創(chuàng)立隨機過程理論。進入80年代，人們以分形的眼光看待布朗運動，并與“Levyflight”相聯(lián)系，找到了確定論與隨機論的內在聯(lián)系。

哈爾濱工業(yè)大學計算機學院蘇小紅6什么是分形？（5/21）學過微積分的人都知道，函數(shù)的可微(即可求導數(shù))性與連續(xù)性有內在聯(lián)系。兩者的關系是可微的函數(shù)必定連續(xù)，但連續(xù)的函數(shù)未必可微。一個簡單的例子就是函數(shù)y=｜x｜在x=0處連續(xù)，但不可微。有的函數(shù)在有限個點處是不可微的，也有更特別的函數(shù)，它們幾乎處處不可微。

哈爾濱工業(yè)大學計算機學院蘇小紅7什么是分形？（6/21）1860年，瑞士一個名氣不算大的數(shù)學家C.Cellerer(1818-1889)在課堂上講：“連續(xù)函數(shù)必定可微”的流行觀念是錯誤的，并給出一個類似維爾斯特拉斯(K.T.W.Weierstrass,1815-1897)函數(shù)的反例1970年有人證明，Cellerer函數(shù)不同于維爾斯特拉斯函數(shù)，它們不是處處不可微的，在某些點上它們是有導數(shù)的。

哈爾濱工業(yè)大學計算機學院蘇小紅8什么是分形？（7/21）1872年，維爾斯特拉斯向柏林科學院報告了分析學中的一個反例——一個處處連續(xù)、但處處不可微的三角函數(shù)級數(shù)，即著名的維爾斯特拉斯函數(shù)。不過此函數(shù)直到1875年才由杜布瓦-雷蒙(E.duBois-Reymond)正式發(fā)表出來。在維爾斯特拉斯之前，已有不少數(shù)學家知道存在所謂的“維爾斯特拉斯函數(shù)”，但都恥于發(fā)表它!因為它破壞了分析學的完美性。

哈爾濱工業(yè)大學計算機學院蘇小紅9什么是分形？（8/21）1883年，G.F.P.Cantor(1845-1918)構造了三分集與實直線相對立被認為是病態(tài)的如今它已成為分形幾何學的最典型、最簡單的模型每次去掉線段中間的1/3最后剩下的就是Cantorset為了顯示方便，無寬度的［0,1］線段在這里故意用一矩形框表示Cantor三分集的生成過程D=log2/log3=0.6309哈爾濱工業(yè)大學計算機學院蘇小紅10什么是分形？（9/21）從什么是曲線談起直觀上有長無寬的線叫曲線。但這不是定義，甚至矛盾

1890年，意大利數(shù)學家G.Peano構造了一種奇怪的曲線能夠通過正方形內的所有點，有面積令數(shù)學界吃驚Peano曲線(前四步)圍成的區(qū)域D=log4/log2=2.0哈爾濱工業(yè)大學計算機學院蘇小紅11什么是分形？（10/21）1891年，大數(shù)學家D.Hilbert也構造了一種性質相同的曲線按一定順序相繼穿過每一個小正方形的“中位線”。D=log4/log2=2.0哈爾濱工業(yè)大學計算機學院蘇小紅12性質：能夠填充空間十分曲折，連續(xù)但不可導具有自相似性什么是分形？（11/21）分形幾何興起以后由反例躍居為主角

這類曲線現(xiàn)在統(tǒng)稱為Peano曲線此性質很令數(shù)學界吃驚。如果這是可能的，那么曲線與平面如何區(qū)分?哈爾濱工業(yè)大學計算機學院蘇小紅131906年，瑞典數(shù)學家H.VonKoch在研究構造連續(xù)而不可微函數(shù)時，構造了Koch曲線。

周長無窮，但面積為定值（0）什么是分形？（12/21）構造方法演示哈爾濱工業(yè)大學計算機學院蘇小紅14構造方法周長無窮，但面積為定值

VonkochsnowflakeD=log4/log3=1.2618什么是分形？（13/21）哈爾濱工業(yè)大學計算機學院蘇小紅15什么是分形？（14/21）1915-1916年，波蘭數(shù)學家W.Sierpinski(1882-1969)構造了Sierpinski曲線、海綿、墓垛。Sierpinski地毯是平面萬有曲線(planeuniversalcurve)Sierpinski海綿是空間萬有曲線奧地利數(shù)學家門格爾(K.Menger)證明，任何曲線都可嵌入Sierpinski地毯中SierpinskigasketSierpinskicarpet哈爾濱工業(yè)大學計算機學院蘇小紅16什么是分形？（15/21）1919年，F(xiàn).Hausdorff(1868-1942)給出維數(shù)新定義，為維數(shù)的非整化提供了理論基礎。1918-1920年左右，法國數(shù)學家G.Julia(1893-1978)、法圖(P.J.L.Fatou,1878-1929)研究復迭代。G.Julia于1918年(當時他25歲)在《純粹數(shù)學與應用數(shù)學雜志》上發(fā)表了長達199頁的杰作，一舉成名。

1924年11月20日B.B.Mandelbrot生于波蘭。1952年，Mandelbrot獲博士學位。傳統(tǒng)的歐式幾何理論描繪已顯得無能為力

哈爾濱工業(yè)大學計算機學院蘇小紅17什么是分形？（16/21）60年代，B.B.Mandelbrot將雪花與海岸線、山水、樹木等自然景物聯(lián)系起來現(xiàn)代分形理論的奠基人經(jīng)歷、性格、舉止非同尋常的人物

Mandelbrot與北京大學非線性科學中心主任趙凱華教授

哈爾濱工業(yè)大學計算機學院蘇小紅什么是分形？（17/21）67年，英國《科學》雜志，《英國的海岸線有多長？統(tǒng)計自相似性與分數(shù)維數(shù)

》正確答案令人吃驚：不確定，依賴測量單位長度研究發(fā)現(xiàn)一個很重要而有趣的性質，即自相似性。75年，法文專著《分形對象:形、機遇與維數(shù)》77年，英譯本《分形：形、機遇與維數(shù)》(Fractals:Form,Chance,andDimension)82年，增補本，改名為《大自然的分形幾何學》哈爾濱工業(yè)大學計算機學院蘇小紅19什么是分形？（18/21）70年代末，fractal傳到中國，一時難以定譯。中國科學院物理所李蔭遠(1919-)院士說，fractal應當譯成“分形”郝柏林、張恭慶、趙凱華、朱照宣等科學家表示贊同于是在中國大陸fractal逐漸定譯為“分形”如今臺灣還譯“碎形”，顯然不如“分形”好。創(chuàng)造的詞Fractal根據(jù)拉丁語fractus造的詞詞根含義：細片的，破碎的，分裂的，分數(shù)的哈爾濱工業(yè)大學計算機學院蘇小紅20什么是分形？（19/21）分形？指具有多重自相似的對象它可以是自然存在的，也可以是人造的分形幾何在極端有序與真正混沌之間提供了一種中間可能性.它的最顯著特征是:看起來十分復雜的事物,大多數(shù)可以用很少參數(shù)的簡單公式來描述哈爾濱工業(yè)大學計算機學院蘇小紅21什么是分形？（20/21）典型的分形隨處可見花椰菜、樹木、山川、云朵、腦電圖、材料斷口、海岸線、樹枝、山脈、星系分布、云朵、聚合物、多變的天氣、大腦皮層褶皺、肺部支氣管分支、血液微循環(huán)管道、動蕩的股市、經(jīng)濟收入分配關系、棉花的價格波動視網(wǎng)膜中央動脈顳上支阻塞視乳頭旁毛細血管瘤河流分布圖星云語音信號股票分時走勢圖哈爾濱工業(yè)大學計算機學院蘇小紅22什么是分形？（21/21）85年獲得BarnardMedal獎章愛因斯坦(A.Einstein,1879-1955)、費米(E.Fermi,1901-1954)、盧瑟福(L.Rutherford,1871-1937)等人獲得過此殊榮1986年獲FranklinMedal

1993年獲WolfPrizeinPhysics1994年獲本田獎(HondaPrize)美國藝術與科學學院(AmericanAcademyofArtsandSciences)院士美國國家科學院(U.S.NationalAcademyofSciences)院士現(xiàn)任職于耶魯大學哈爾濱工業(yè)大學計算機學院蘇小紅23什么是分形維數(shù)？（1/12）分形物體的細節(jié)變化用分形維數(shù)（分數(shù)維）來描述，它是物體粗糙性或細碎性的度量。什么是分數(shù)維？整數(shù)維數(shù)分數(shù)維數(shù)拓撲維數(shù)度量維數(shù)哈爾濱工業(yè)大學計算機學院蘇小紅24什么是分形維數(shù)？（2/12）只能取整數(shù)表示描述一個對象所需的獨立變量的個數(shù)在一維直線上確定一個點需要一個坐標在二維平面上確定一個點得用兩個坐標在三維空間中確定一個點得用三個坐標整數(shù)維數(shù)拓撲維數(shù)哈爾濱工業(yè)大學計算機學院蘇小紅25什么是分形維數(shù)？（3/12）從測量的角度定義的從測量的角度看，對象的維數(shù)是可變的。例如：看一個毛線團遠看是一個0維的點，在廣闊的銀河系外宇宙空間看地球近看是三維的球進入太陽系后，乘航天飛機在太空沿地球軌道飛行貼近其表面看是二維球面，甚至是二維平面站在曠野上環(huán)顧左右再近一些，看一根毛線再接近，看毛線上的纖維分數(shù)維數(shù)度量維數(shù)哈爾濱工業(yè)大學計算機學院蘇小紅26什么是分形維數(shù)？（4/12）從測量的角度重新理解維數(shù)概念精確描述世界中的現(xiàn)象要有度量“尺度”的觀念《楚辭·卜居》中說：“夫尺有所短，寸有所長”事物都有其自己的特征尺度，要用適宜的尺度去測量用寸來量度細菌，用尺來量度萬里長城前者失之過長，后者又嫌太短對于一個有確切維數(shù)的幾何體若用與其維數(shù)相同的“尺”去度量，可得到確切數(shù)值若用低于其維數(shù)的“尺”去度量，結果為無窮大若用高于其維數(shù)的“尺”去度量，結果就會為零哈爾濱工業(yè)大學計算機學院蘇小紅27什么是分形維數(shù)？（4/12）分形曲線的測量和冪律不同長度尺子s測得的海岸線長度us/kmu/km50025001003800505700178640分形測量哈爾濱工業(yè)大學計算機學院蘇小紅28210345612345678109081632241101001110100100010100(a)線性(b)指數(shù)(c)冪指數(shù)(d)線性坐標系(e)半對數(shù)坐標系(f)雙對數(shù)坐標系

幾種函數(shù)關系及研究這些函數(shù)關系常用的坐標系N

cl

+dN

clN

l

c與維數(shù)定義有關的函數(shù)關系是冪指數(shù)關系，簡稱冪律(Powerlaw)哈爾濱工業(yè)大學計算機學院蘇小紅29什么是分形維數(shù)？（5/12）1919年F.Hausdorff(1868-1942)

推廣了維數(shù)的概念,為維數(shù)的非整化提供了理論基礎理論性強，實際背景較少在很多情形下難以用計算方法求得

在實際應用中，經(jīng)常應用的是盒維數(shù)能通過實驗近似地計算，且在一些比較“規(guī)則”的分形集上，這種維數(shù)的值與Hausdorff維數(shù)相等哈爾濱工業(yè)大學計算機學院蘇小紅30什么是分形維數(shù)？（6/12）一根一維線段L，單位長度A，將其邊長擴大到原來的3倍，能得到幾個原始對象(單位長度為A的線段)。3個：

L→3L=3^1*LL3L哈爾濱工業(yè)大學計算機學院蘇小紅31什么是分形維數(shù)？（7/12）一根一維線段L，單位長度A，將其邊長擴大到原來的3倍，能得到幾個原始對象(單位長度為A的線段)。3個：

L→3L=3^1*L平面上的一個正方形P，邊長為A，將其邊長擴大到原來的3倍9個正方形：

P→9P=3^2*P哈爾濱工業(yè)大學計算機學院蘇小紅32什么是分形維數(shù)？（8/12）一根一維線段L，單位長度A，將其邊長擴大到原來的3倍，能得到幾個原始對象(單位長度為A的線段)。3個：

L→3L=3^1*L平面上的一個正方形P，邊長為A，將其邊長擴大到原來的3倍9個正方形：

P→9P=3^2*P三維空間上的正方體V，邊長為A，將其邊長擴大到原來的3倍27個立方體：V→27V=3^3*V

哈爾濱工業(yè)大學計算機學院蘇小紅33什么是分形維數(shù)？（9/12）一根一維線段L，單位長度A，將其邊長擴大到原來的3倍，能得到幾個原始對象(單位長度為A的線段)。3個：

L→3L=3^1*L平面上的一個正方形P，邊長為A，將其邊長擴大到原來的3倍9個正方形：

P→9P=3^2*P三維空間上的正方體V，邊長為A，將其邊長擴大到原來的3倍27個立方體：V→27V=3^3*V

得到的總個數(shù)可表達為：

M=B^d其中，B指放大倍數(shù)，M是總個數(shù)，d相當于對象的維數(shù)。換一種寫法有：

d=logM/logB其中指數(shù)d相當于維數(shù)哈爾濱工業(yè)大學計算機學院蘇小紅34什么是分形維數(shù)？（10/12）從放大的反面——鋪砌或者細分的角度去理解對給定對象，用小單元塊（相當于測量尺度）r填充（覆蓋）它，數(shù)一數(shù)所使用的小單元數(shù)目N(r)r越小，得到的N越大；r越大，得到的N就越小將測得結果在“雙對數(shù)”坐標紙上繪制出來，會得到一條直線此直線斜率的絕對值就是對象的維數(shù)d。容量維數(shù)的數(shù)學表達：

log(1/r)logN(r)r為細分時縮放因子哈爾濱工業(yè)大學計算機學院蘇小紅35什么是分形維數(shù)？（11/12）以Koch曲線為例細分線段數(shù)為N=4，細分單元長度為S=1/3Koch曲線的分數(shù)維為：

d=ln4/ln3=1.2619而按照歐氏幾何方法將一條線段4等分則N=4，S=1/4，d=1。一般來說，二維空間中的分形曲線維數(shù)介于1和2之間三維空間中的分形曲線維數(shù)在2和3之間。哈爾濱工業(yè)大學計算機學院蘇小紅36什么是分形維數(shù)？（11/12）對于實際的自然景物，我們可以用計盒維數(shù)的方法測量分維數(shù)盒子法(Box-countingMethod)取邊長為r的小盒子(可以理解為拓撲維為d的小盒子)，把分形覆蓋起來。由于分形內部有各種層次的空洞和縫隙，所以，有些小盒子是空的，有些小盒子覆蓋了分形的一部分。數(shù)數(shù)多少小盒子不是空的，所得的非空(non-empty)盒子數(shù)記為N(r)。然后縮小盒子的尺寸r，所得N(r)自然要增大。海岸線哈爾濱工業(yè)大學計算機學院蘇小紅37什么是分形維數(shù)？（12/12）其它分數(shù)維容量維柯爾莫哥洛夫維信息維關聯(lián)維雷尼(A.Renyi)維不同定義的分數(shù)維概念，從不同的角度描述分形圖形的不規(guī)則性、復雜或粗糙程度哈爾濱工業(yè)大學計算機學院蘇小紅38什么是分形？（1/2）什么是分形？Mandelbrot開始時把那些Hausdorff維數(shù)不是整數(shù)的集合稱為分形但該定義將某些顯然為分形的集合排除在外例如，Peano曲線是分形曲線，但Hausdorff維數(shù)為2，是整數(shù)修改了這個定義強調具有自相似性的集合為分形哈爾濱工業(yè)大學計算機學院蘇小紅39什么是分形？（2/2）至今無統(tǒng)一定義，比較合理、普遍被人接受的定義定義具有如下性質的集合F為分形F具有精細的結構，有任意小比例的細節(jié)F是如此地不規(guī)則，以至于它的整體與局部都不能用傳統(tǒng)的幾何語言來描述F通常有某種自相似的性質，這種自相似性可以是近似的或者是統(tǒng)計意義下的一般地，F(xiàn)的某種定義之下的分形維數(shù)大于它的拓撲維數(shù)

在大多數(shù)令人感興趣的情形下，F(xiàn)通常能以非常簡單的方法定義，由迭代過程產(chǎn)生哈爾濱工業(yè)大學計算機學院蘇小紅40分形幾何歐氏幾何使用方程描述有平滑的表面和規(guī)則形狀的物體分形幾何使用過程對具有不規(guī)則幾何形態(tài)的物體（如自然景物）建模哈爾濱工業(yè)大學計算機學院蘇小紅41分形幾何應用自然景物的逼真模擬自然景物的表面往往包含有豐富的細節(jié)或具有隨機變化的形狀，它們很難用傳統(tǒng)的解析曲面來描述盡管凹凸紋理映射技術可以模擬規(guī)則景物表面的幾何紋理細節(jié)，但在表達諸如山脈、云彩、火焰、樹木、浪花等自然景象時，凹凸紋理映射技術仍難以勝任海圖制作分形圖像壓縮——作為文獻綜述內容之一地震預報信號處理蘇小紅哈爾濱工業(yè)大學計算機科學與技術學院第6章自然景物模擬與分形藝術哈爾濱工業(yè)大學計算機學院蘇小紅43隨機插值模型（1/3）1982年由AlainFournierDonFussellLorenCarpenter提出能有效地模擬海岸線和山等自然景象不是事先決定各種圖素和尺度用一個隨機過程的采樣路徑作為構造模型的手段

哈爾濱工業(yè)大學計算機學院蘇小紅44隨機插值模型（2/3）構造二維海岸線的模型：選擇控制大致形狀的若干初始點在相鄰兩點構成的線段上取中點，沿垂直連線方向隨機偏移一個距離將偏移后的點與該線段兩端點分別連成兩個新線段如此繼續(xù)可得到一條曲折的有無窮細節(jié)的海岸線，其曲折程度由隨機偏移量控制，它也決定了分數(shù)維的大小

哈爾濱工業(yè)大學計算機學院蘇小紅45隨機插值模型（3/3）在三維情況下用類似過程構造山模型：多邊形（如三角形）細分在三角形三邊上隨機各取一點沿垂直方向隨機偏移一段距離得到三個新點連接成四個三角形如此繼續(xù)，可形成皺褶的山峰哈爾濱工業(yè)大學計算機學院蘇小紅46迭代函數(shù)系統(tǒng)（1/20）IteratedFunctionSystem（簡稱IFS）美國佐治亞理工學院Demko,Barnsley教授首創(chuàng)在SIGGRAPH’85國際會議上，IFS專題報告IFS方法的魅力是分形迭代生成的“反問題”哈爾濱工業(yè)大學計算機學院蘇小紅47迭代函數(shù)系統(tǒng)（2/20）確定性算法與隨機性算法相結合的方法生成植物桿莖或葉片用以迭代的規(guī)則是確定性的，它們由一組仿射變換(如R_1，R_2，R_3等)構成迭代過程是不確定的，每一次迭代哪一個規(guī)則，即R_i中具體哪一個，非預先定好，而要靠擲骰子的辦法來決定。設最終要生成的植物形態(tài)圖為M，它要滿足下述集合方程：

M=R_1∪R_2∪…∪R_N含義：隨機地從R_i(i=1,…，N)中挑選一個迭代規(guī)則迭代一次然后再隨機地在R_i(i=1,…，N)中選一個規(guī)則迭代一次不斷重復此過程最后生成的極限圖形M就是欲求的植物形態(tài)圖。每個迭代規(guī)則R_i都是一個仿射變換。

哈爾濱工業(yè)大學計算機學院蘇小紅48迭代函數(shù)系統(tǒng)（3/20）一個變換S：Rn→Rn稱為線性的假若S(x+y)=S(x)+S(y)，且S(λx)=λS(x)S稱為非奇異線性變換當且僅當x=0時，有S(x)=0ω稱為仿射變換如果變換ω

：Rn→Rn具有形式ω(x)=S(x)+a，這里S為非奇異線性變換，a為Rn中一點哈爾濱工業(yè)大學計算機學院蘇小紅49迭代函數(shù)系統(tǒng)（4/20）正交變換保持幾何圖形的度量性質不變向量的夾角，點與點之間的距離，圖形的面積等仿射變換一般會改變幾何圖形的度量性質但不改變共線、平行、相交、共線點的順序、中心對稱、二次曲線的次數(shù)等仿射變換在不同方向可以有不同的壓縮和擴張例如可將球變換為橢球，正方形變換為平行四邊形哈爾濱工業(yè)大學計算機學院蘇小紅50迭代函數(shù)系統(tǒng)（5/20）每個迭代規(guī)則R_i都是一個仿射變換。

哈爾濱工業(yè)大學計算機學院蘇小紅51迭代函數(shù)系統(tǒng)（6/20）圖形經(jīng)仿射變換后面積變小，則此變換是收縮的面積變大，則是擴張的保持不變，則是恒等的。因為極限圖形M應是所有迭代R_i的吸引子每個仿射變換是收縮性的才能保證迭代收斂到M上所以只用到收縮性仿射變換

（ContractiveAffineTransformation）

哈爾濱工業(yè)大學計算機學院蘇小紅52迭代函數(shù)系統(tǒng)（7/20）設給定一個仿射變換f，對任意向量x和y，如果總存在一個非負實數(shù)，滿足則s稱為壓縮因子使得上式成立的最小實數(shù)稱為Lipschitz常數(shù)（李普希茨常數(shù)

）因s<1，因此仿射變換f是收縮仿射變換

哈爾濱工業(yè)大學計算機學院蘇小紅53迭代函數(shù)系統(tǒng)（8/20）

上的收縮仿射變換（壓縮映射）記為迭代函數(shù)系統(tǒng)

若干個收縮仿射變換的組合哈爾濱工業(yè)大學計算機學院蘇小紅54迭代函數(shù)系統(tǒng)（9/20）IFS方法生成分形圖像的步驟：一個二維的IFS的組成收縮仿射變換的集合概率的集合

確定仿射變換

確定概率向量按照相應的概率，隨機從仿射變換集中選擇一個作為迭代規(guī)則迭代一次，不斷重復此迭代過程（通過迭代過程產(chǎn)生點集序列來繪制分形圖形）

哈爾濱工業(yè)大學計算機學院蘇小紅55迭代函數(shù)系統(tǒng)（10/20）怎樣確定仿射變換？確定a,b,c,d,e,f哈爾濱工業(yè)大學計算機學院蘇小紅56迭代函數(shù)系統(tǒng)（11/20）怎樣實現(xiàn)擲骰子操作？設N=4，每次生成一個隨機數(shù)E∈(0，100)

設0＜β_1＜β_2＜β_3＜100，作如下規(guī)定：

若0＜E＜β_1，則選擇規(guī)則R_1若β_1≤E＜β_2，則選擇規(guī)則R_2若β_2≤E＜β_3，則選擇規(guī)則R_3若β_3≤E＜100，則選擇規(guī)則R_4指定β_i的過程相當于為每種迭代規(guī)則R_i指派一個概率p_i怎樣確定概率向量？控制概率就是控制圖形各部分的落點密度，使圖形在有限迭代步數(shù)內顯現(xiàn)出濃淡虛實不同的繪制效果。哈爾濱工業(yè)大學計算機學院蘇小紅57迭代函數(shù)系統(tǒng)（12/20）D=log3/log2=1.585Sierpinski三角形fabc

defp

10.5000.52510.3320.5000.51500.3330.5000.550500.33哈爾濱工業(yè)大學計算機學院蘇小紅58Sierpinskicarpet迭代函數(shù)系統(tǒng)（13/20）D=log8/log3=1.8927哈爾濱工業(yè)大學計算機學院蘇小紅59迭代函數(shù)系統(tǒng)（14/20）Barnsley蕨的參數(shù)表fabc

defp

10000.16000.0120.850.04-0.040.8501.60.8530.2-0.260.230.2201.60.074-0.150.280.260.2400.440.07fabc

defp

10000.250-0.140.0220.850.02-0.020.83010.8430.09-0.280.30.1100.60.074-0.090.250.30.0900.70.07蕨子葉的參數(shù)表哈爾濱工業(yè)大學計算機學院蘇小紅60迭代函數(shù)系統(tǒng)（15/20）樹冠的參數(shù)表fabcdef

pi

f00.01000.45000.05f1-0.0100-0.4500.40.15f20.42-0.420.420.4200.40.4f30.420.42-0.420.4200.40.4fabcdef

pi

f00.01000.45000.05f1-0.0100-0.4500.20.15f20.12-0.820.420.4200.20.4f30.120.82-0.420.4200.20.4六角楓葉的參數(shù)表哈爾濱工業(yè)大學計算機學院蘇小紅61迭代函數(shù)系統(tǒng)（16/20）fabcdef

pi

f00.6000.60.180.360.25f10.6000.60.180.120.25f20.40.3-0.30.40.270.360.25f30.4-0.30.30.40.270.090.25fabcdef

pi

f00.05000.6000.1f10.0500-0.5010.1f20.460.32-0.3860.38300.60.2f30.47-0.1540.1710.423010.2f40.430.275-0.260.476010.2f50.421-0.3570.3540.30700.70.2哈爾濱工業(yè)大學計算機學院蘇小紅62迭代函數(shù)系統(tǒng)（17/20）fabcdef

pi

f00.25000.5000.154f10.5000.5-0.250.50.307f2-0.2500-0.250.2510.078f30.5000.500.750.307f40.500-0.250.51.250.154fabcdef

pi

f00.382000.3820.30720.6190.2f10.382000.3820.60330.40440.2f20.382000.3820.01390.40440.2f30.382000.3820.12530.05950.2f40.382000.3820.4920.05950.2哈爾濱工業(yè)大學計算機學院蘇小紅63迭代函數(shù)系統(tǒng)（18/20）fabcdef

pi

f00.5-0.50.50.5000.5f10.50.5-0.50.50.50.50.5fabcdef

pi

f00.8240740.281482-0.2123460.864198-1.882290-0.1106070.8f10.0882720.520988-0.463889-0.3777780.7853608.0957950.2哈爾濱工業(yè)大學計算機學院蘇小紅64迭代函數(shù)系統(tǒng)（19/20）增減規(guī)則R_i，可以改變最終植物M的形態(tài)。即使不改變迭代規(guī)則，采用同樣的程序，只改變參數(shù)也可以生成完全不同的植物形態(tài)。ProcedureAFF(a,b,c,d,e,f,S,T:real);Varlins:real;Beginlins:=a*S+b*T+e;y:=c*S+d*y+f;x:=lins;End;65迭代函數(shù)系統(tǒng)（20/20）應用自然景物模擬分形圖像壓縮哈爾濱工業(yè)大學計算機學院蘇小紅66L系統(tǒng)（1/13）由美國生物學家林德梅葉(Lindenmayer)創(chuàng)立，1984年由Smith等人將L系統(tǒng)引入圖形學1990年，普魯辛凱維奇(P.Prusinkiewicz)與林氏出版《植物的算法美》(TheAlgorithmicBeautyofPlants)是一種形式語言字符串重寫系統(tǒng)通過符號串的解釋，轉化為造型工具基本思想：從一個初始串(叫做公理)開始將變換規(guī)則多次作用于其上最后產(chǎn)生一個較長的命令串哈爾濱工業(yè)大學計算機學院蘇小紅67L系統(tǒng)（2/13）L系統(tǒng)分類0L系統(tǒng)與上下文無關1L系統(tǒng)僅考慮單邊的文法關系，即左相關或右相關在植物的生態(tài)模擬中左相關文法用于模擬植物從根向葉、莖的傳播過程右相關文法用于模擬從葉到莖、根的傳播過程2L系統(tǒng)同時考慮左邊和右邊文法關系哈爾濱工業(yè)大學計算機學院蘇小紅68L系統(tǒng)（3/13）D0L系統(tǒng)確定的上下文無關的L系統(tǒng)定義為一個三元組〈V,ω,P〉V：字符表(alphabet)V*：V上的所有單詞(words)ω：ω∈V*是一個非空的單詞，稱公理(axiom)P

：包含于V×V*，是產(chǎn)生規(guī)則的有窮集。

哈爾濱工業(yè)大學計算機學院蘇小紅69L系統(tǒng)（4/13）設計D0L系統(tǒng)的步驟：定義字符表V給出公理，即初始圖ω定義產(chǎn)生式P

哈爾濱工業(yè)大學計算機學院蘇小紅70L系統(tǒng)（5/13）L系統(tǒng)的符號串也稱“龜圖”(turtle)龜圖的狀態(tài)用三元組(X,Y,D)表示X：橫坐標Y：縱坐標D：當前的朝向δ：角度增量H：步長。L系統(tǒng)的符號規(guī)定與解釋符號圖形解釋F從當前位置向前走一步，同時畫線G從當前位置向前走一步，但不畫線+從當前方向向右轉一個給定的角度-從當前方向向左轉一個給定的角度｜原地轉向180°［Push,將龜圖當前狀態(tài)壓進棧(stack)］Pop,將圖形狀態(tài)重置為棧頂?shù)臓顟B(tài)，

并去掉該棧中的內容\nn增加角度nn度/nn減少角度nn度Cnn選擇顏色nn＜nn在此基礎上增加顏色nn＞nn在此基礎上減少顏色nn!倒轉方向(控制+,-,/)@nnn將線段長度乘以nnn，nnn也可以是簡單函數(shù)其他也是合法的，主要用于獲得復雜的解釋哈爾濱工業(yè)大學計算機學院蘇小紅71L系統(tǒng)（6/13）13世紀數(shù)學家Fibonacci（1170-1250）兔子的理想化繁衍問題

baby(b),adult(a)V：{a,b}W:bP:a->abb->abaababaabaababaababaabaababaabaababaababaabaababaababa哈爾濱工業(yè)大學計算機學院蘇小紅72L系統(tǒng)（7/13）vonKoch雪花曲線V：{F,+,-}w：FP：F->F-F++F-Fδ=60o幾何解釋F：向前畫一條線+：右轉60o-：左轉60o

n=0n=1n=2n=3w：F++F++F

倒置的正三角形生成元初始圖哈爾濱工業(yè)大學計算機學院蘇小紅73L系統(tǒng)（8/13）Koch島V：{F,+,-}w：F﹣F﹣F﹣FP：F→F﹢F﹣F﹣FF﹢F﹢F﹣Fδ=90o令步長d在相鄰兩級子圖之間縮短4倍，規(guī)定后繼多邊形線(折線)端點之間的距離等于前驅線段的長度

哈爾濱工業(yè)大學計算機學院蘇小紅74L系統(tǒng)（9/13）四方內生樹四方內生樹V：{F,+,-}w：F+F+F+FP：F->FF+F++F+F

δ=90o

生成元初始圖哈爾濱工業(yè)大學計算機學院蘇小紅75L系統(tǒng)（10/13）植物w：FP：F->F[+F]F[-F]F[:將當前烏龜爬行的狀態(tài)壓入堆棧，信息包括所在位置和方向等]:從堆棧中彈出一個狀態(tài)作為烏龜?shù)漠斍盃顟B(tài)，但不畫線哈爾濱工業(yè)大學計算機學院蘇小紅76L系統(tǒng)（11/13）植物（a）n=5，δ=30°S：FP：F→F[﹢F]F[﹣F]F(b)n=5，δ=20°S:FP：F→F[﹢F]F[﹣F][F]

（c）n=4，δ=20.5°S:FP：F→FF﹣[﹣F﹢F﹢F]﹢[﹢F﹣F﹣F]哈爾濱工業(yè)大學計算機學院蘇小紅77L系統(tǒng)（12/13）模擬側柏形態(tài)（左圖）w：FP：F->F［+F］F［-F］［F］

δ=90o哈爾濱工業(yè)大學計算機學院蘇小紅78L系統(tǒng)（13/13）設計L系統(tǒng)的過程是根據(jù)自相似結構形成信息壓縮的一個過程利用設計好的L系統(tǒng)進行繪制的過程是信息壓縮的逆過程，或者說是信息復原的過程。

L系統(tǒng)能有效給出植物的拓撲結構但繪制真實感的二、三維植物形態(tài)還必須結合幾何造型技術例如，若要生成逼真的樹干和樹枝的柱狀曲面、花瓣或樹葉的自由曲面等，還需要使用曲面造型技術哈爾濱工業(yè)大學計算機學院蘇小紅79粒子系統(tǒng)（1/8）ParticleSystem

W.T.Reeves1983年提出最重要的計算機生成模型方法描述對象不規(guī)則、結構隨時間而變化的FuzzyObject

尤其擅長模擬不規(guī)則物體的隨機動態(tài)特性自然現(xiàn)象，密集場景，真實的物理過程如跳動的火焰、煙霧、下雨、行云、遠處隨風搖曳的樹林和草叢等

哈爾濱工業(yè)大學計算機學院蘇小紅80粒子系統(tǒng)（2/8）1985年，Reeves和Blau進一步發(fā)展了粒子系統(tǒng)并維妙維肖的模擬了小草隨風搖曳的景象模擬動態(tài)模糊自然景物電視電影的特技制作最初引入是為了模擬火焰跳動的火焰被看作是一個噴出許多粒子的火山每個粒子都有一組隨機取值的屬性初始位置、速度、運動方向、初始大小、形狀、顏色、透明度、紋理作為文獻綜述內容之一哈爾濱工業(yè)大學計算機學院蘇小紅81粒子系統(tǒng)（3/8）基本思想造型和動畫是一個有機的整體單個隨時間變化的粒子(Particle)作為景物造型的基本元素

由一組粒子構成的系統(tǒng)每個粒子有一個生命周期包括出生、成長、死亡等幾個階段粒子在不同的階段具有不同的形態(tài)和屬性（位置和速度）粒子形狀可以是小球、橢球、立方體或其它形狀粒子的運動由一定的規(guī)則控制，遵循Newton運動定律哈爾濱工業(yè)大學計算機學院蘇小紅82粒子系統(tǒng)（4/8）本質是隨機模型采用隨機過程的方法來實現(xiàn)粒子在“出生”、“生長”、“死亡”三個階段的不確定性在生長過程中，粒子的屬性被隨機地改變粒子的大小和形狀隨時間變化其它性質如粒子透明度、顏色和移動等都隨機地變化哈爾濱工業(yè)大學計算機學院蘇小紅83粒子系統(tǒng)（5/8）模擬動態(tài)自然景物的過程生成新的粒子，分別賦予不同的屬性以及生命周期將新粒子加到系統(tǒng)中刪去系統(tǒng)中老的已經(jīng)死亡的粒子

根據(jù)粒子的屬性，按適當?shù)倪\動模型或規(guī)則，對余下的存活粒子的運動進行控制（Transformation）繪制當前系統(tǒng)中存活的所有粒子哈爾濱工業(yè)大學計算機學院蘇小紅84粒子系統(tǒng)（6/8）對于粒子系統(tǒng)的隨機性Reeves采用一些非常簡單的隨機過程來控制粒子在它所在系統(tǒng)中的形狀、特征及運動。先確定每個粒子的變化范圍然后在該范圍內隨機地確定它的值變化范圍由給定的平均期望值和最大方差來確定粒子的基本屬性包括：（1）初始位置、大??；

〔2）初始運動速度和方向；（3）初始顏色；（4）初始透明度；

〔5）初始形狀；（6）生命周期。哈爾濱工業(yè)大學計算機學院蘇小紅85粒子系統(tǒng)（7/8）粒子數(shù)目對模糊物體的密度有很重要的影響，粒子系統(tǒng)通過控制每一幀進入系統(tǒng)的粒子數(shù)和死亡的粒子數(shù)來控制粒子系統(tǒng)中粒子的數(shù)量。控制每幀的粒子數(shù)的兩種方法由每幀產(chǎn)生的粒子平均數(shù)和其方差控制粒子數(shù)，實際在f幀產(chǎn)生的粒子數(shù)為新產(chǎn)生的粒子數(shù)取決于物體的屏幕尺寸?？刂泼總€屏幕單位產(chǎn)生的粒子平均數(shù)MeanParts和其方差VarParts

，根據(jù)物體覆蓋的屏幕尺寸ScreanArea計算出所需的粒子數(shù)：f是當前幀，f0

是粒子系統(tǒng)開始的第一幀，InitialMeanParts

指第一幀粒子的平均數(shù)，DeltaMeanParts

是相應的變化率哈爾濱工業(yè)大學計算機學院蘇小紅86粒子系統(tǒng)（8/8）粒子系統(tǒng)運行的流程哈爾濱工業(yè)大學計算機學院蘇小紅87混沌吸引子氣象學家E.N.Lorenz混沌理論的少有幾位創(chuàng)立者之一，1963年，在研究大氣環(huán)流的對流運動時，發(fā)現(xiàn)了第1個奇異吸引子運動為非周期性的，而且具有不可預測的隨機性他在1963年發(fā)表的關于混沌理論的開創(chuàng)性研究在被冷落了12年之久以后才得到廣泛承認，并很快引發(fā)對混沌研究的熱潮，由此誕生和發(fā)展起了一門新興學科—混沌理論，成為現(xiàn)代新興學科的代表。(b)沿y軸方向投影的Lorenz吸引子(a)沿x軸方向投影的Lorenz吸引子(c)沿z軸方向投影的Lorenz吸引子圖6-43Lorenz吸引子混沌可以理解為貌似隨機的確定性。哈爾濱工業(yè)大學計算機學院蘇小紅88迭代（動力系統(tǒng)）的問題動力系統(tǒng)指隨時間確定性地變化的系統(tǒng)。系統(tǒng)的狀態(tài)可由一個或幾個變量的數(shù)值來確定。哈爾濱工業(yè)大學計算機學院蘇小紅89復平面上的迭代（1/18）動力系統(tǒng)中的分形動力系統(tǒng)的奇異吸引子通常都是分形集，它們產(chǎn)生于非線性函數(shù)的迭代和非線性微分方程中

復平面上解析映射的迭代（復數(shù)的非線性映射）1918~1919年，Julia和Fatou研究發(fā)現(xiàn)，此迭代把復平面劃分為兩部分：Fatou集和Julia集Julia集的定義哈爾濱工業(yè)大學計算機學院蘇小紅90復平面上的迭代（2/18）C=-1C=-0.5+0.5iC=-0.2+0.75iC=0.64iJulia集的圖象哈爾濱工業(yè)大學計算機學院蘇小紅91復平面上的迭代（3/18）80年代初，Mandebrot在迭代z→z^2+c時，用計算機繪制了著名的Mandebrot集，簡稱M集

哈爾濱工業(yè)大學計算機學院蘇小紅92復平面上的迭代（4/18）Julia集固定C值，對不同Zk值進行迭代，生成的圖像用屏幕上不同的點Zk(xk,yk)作為初值迭代，產(chǎn)生的Zk序列會出現(xiàn)收斂與發(fā)散兩種情況通過設定最大迭代次數(shù)N和閾值M對點著不同的色迭代到N，但模值未超過M——收斂，用固定顏色顯示迭代到N，但模值已超過M——發(fā)散，根據(jù)其發(fā)散速度用不同色顯示從Zk(xk,yk)到Zk+1(xk+1,yk+1)的迭代公式：哈爾濱工業(yè)大學計算機學院蘇小紅93復平面上的迭代（5/18）Julia集固定C值，對不同Zk值進行迭代，生成的圖像M集令Zk=0，對不同的C值進行迭代，生成的圖像Julia集是取一固定的c值后，觀察復平面上每一點(x,y)在迭代中的表現(xiàn)，并把結果記錄下來M集記錄的是整個區(qū)域上的c值情況哈爾濱工業(yè)大學計算機學院蘇小紅94復平面上的迭代（6/18）標色有很多技巧表面看來好像屬于計算機技術但實際上這屬于傳統(tǒng)的美術。分形圖形藝術是傳統(tǒng)美術與計算機的結合。雖然本質上具有同樣的數(shù)學結構標上不同的顏色，就有完全不同的視覺效果哈爾濱工業(yè)大學計算機學院蘇小紅95復平面上的迭代（7/18）M集特征：一個主要的心形圖與一系列圓盤形的“芽苞”突起連在一起每個芽苞又被更細小的芽苞所環(huán)繞還有精細的“發(fā)絲狀”分枝從芽苞向外長出M集逐步放大圖

哈爾濱工業(yè)大學計算機學院蘇小紅96復平面上的迭代（8/18）M集包含了關于Julia集構造的大量信息M集不同部位的形狀反映了對應于該處的J集的形狀哈爾濱工業(yè)大學計算機學院蘇小紅97復平面上的迭代（9/18）(a)c=0.1-0.1i，f有吸引不動點，J為擬圓(b)c=0.5-0.5i，f有吸引不動點，J為擬圓(c)c=1.0-0.05i，f有周期為2的吸引軌道(d)c=0.2-0.75i，f有周期為3的吸引軌道(e)c=-0.25-0.52i，f有周期為4的吸引軌道(f)c=0.5-0.55i，f有周期5的吸引軌道(g)c=-0.66i，f沒有吸引軌道，且J為全部連通(h)c=-i，f為無圈曲線改變常數(shù)c的取值，可以得到各式各樣的J集

主心形圖上芽苞上或心形圖邊界

芽苞與心形圖接觸的“頸部”

“發(fā)狀”分枝上

哈爾濱工業(yè)大學計算機學院蘇小紅98J集的快速生成算法圖6-46“區(qū)域四分法”的原理n1(0,0)n3(0,b)n2(a,0)n4(a,b)c2(0,b/2)c4(a,b/2)c5(a/2,b)c1(a/2,0)c3(a/2,b/2)2區(qū)4區(qū)1區(qū)3區(qū)哈爾濱工業(yè)大學計算機學院蘇小紅99復平面上的迭代（10/18）二維復平面上二次映射廣義的M集和J集任意多項式映射三角函數(shù)指數(shù)函數(shù)對數(shù)函數(shù)z→z^m+c,其中m分別為4，5，6，7，8，9哈爾濱工業(yè)大學計算機學院蘇小紅100廣義Julia集與Mandelbrot集(a)復指數(shù)Mandelbrot集(b)復指數(shù)Julia集(c)復映射z→z4+c的M集哈爾濱工業(yè)大學計算機學院蘇小紅101復平面上的迭代（11/18）在二維復平面中表示復數(shù)只用兩個基向量：1和i在四維空間中討論超復數(shù)，有四個基向量：1,i,j和k任一復數(shù)可以表示為：q=x+yi+zj+qk高維M集與J集通過“四元數(shù)”(quaternions)推廣到高維空間中

哈爾濱工業(yè)大學計算機學院蘇小紅102復平面上的迭代（12/18）四元數(shù)英國數(shù)學家W.Hamilton，1843年是復數(shù)的推廣四元數(shù)表示在球面上的光滑旋轉非常有效球面線性插值計算量小哈爾濱工業(yè)大學計算機學院蘇小紅103復平面上的迭代（13/18）四元數(shù)的二次迭代將z取為四元數(shù)表示哈爾濱工業(yè)大學計算機學院蘇小紅104復平面上的迭代（14/18）在四維空間中研究迭代x→x^2+c下的超Julia集按照四元數(shù)運算法則，做出Julia集和Mandelbrot集的空間結構圖像選一個截面，將超Julia集投影到三維空間中，可以得到立體的J集圖象用四元數(shù)法得到的高維Julia集的投影圖哈爾濱工業(yè)大學計算機學院蘇小紅105復平面上的迭代（15/18）復平面域的牛頓法求根本質是“以直代曲”首先猜測一個值x1，用它近似方程的根c用過(x1,f(x1))點的切線

y=f(x1)+f’(x1)(x-x1)

近似代替曲線f(x)然后用切線方程

y=f(x1)+f’(x1)(x-x1)=0

的根

x=x2=x1-f(x1)/f’(x1)

近似代替曲線方程的根c這樣就得到c的第二個近似值依此類推可得到迭代公式

x(n+1)=xn-f(xn)/f’(xn)哈爾濱工業(yè)大學計算機學院蘇小紅106復平面上的迭代（16/18）f(x)=x^p-1,其中p是大于2的正整數(shù)x^3-1=0有三個根：x1=1x2=[-1+SQRT(3)i]/2x3=[-1-SQRT(3)i]/2哈爾濱工業(yè)大學計算機學院蘇小紅107復平面上的迭代（17/18）用牛頓法求z^3-1=0的根得到的分形圖三個根均勻地分布在單位圓上,這三個根周圍構成三個“吸引盆”(attractorbasin)初始點迅速被吸引到盆內，最后停止在三點之一。用計算機迭代，以當前點到三個終點的距離遠近為標準，標上不同的顏色，就能得到美麗的分形圖特別是在120°線、240°線附近有復雜的“項鏈”結構。哈爾濱工業(yè)大學計算機學院蘇小紅108復平面上的迭代（18/18）改進方法分式線性映射w=1/z在擴充的復平面上是一一對應的且為具有保圓性和保對稱性的保角映射將牛頓函數(shù)取倒數(shù)，并在迭代過程中嵌入控制參數(shù)用牛頓法求z^4-1=0的根得到的分形圖分子部分完全相同超吸引不動點相同哈爾濱工業(yè)大學計算機學院蘇小紅109(a)α=1,β=1,p=1,q=0xmax=ymax=1.5(b)α=1.5,β=1,p=1,q=0xmax=ymax=1(c)α=1,β=1,p=1.3,q=0xmax=ymax=2(d)α=1,β=1.8,p=1,q=0xmax=ymax=2(e)α=0.5,β=1.2,p=1,q=0xmax=ymax=1.5(f)α=1,β=1,p=1,q=0xmax=ymax=2.5哈爾濱工業(yè)大學計算機學院蘇小紅110(a)α=2.5,β=1,p=1.5,q=0xmax=ymax=1.5(a)α=1,β=1.8,p=1.5,q=0xmax=ymax=1(a)α=0.5,β=1,p=0.5,q=0xmax=ymax=1.2(b)α=1.2,β=1,p=1,q=0xmax=ymax=1.5哈爾濱工業(yè)大學計算機學院蘇小紅111復平面上的迭代蘇曉紅等，Julia集的快速顯示算法，計算機工程，1996，22(6):300-303蘇曉紅等．用改進的Newton-Raphson方法生成對稱的分形藝術圖形，計算機學報．1999,22(11):1147-1152（一）第8章真實感圖形生成

真實感圖形繪制流程場景造型113取景變換背面剔除和視域四棱錐裁剪計算場景中可見面的光亮度和顏色

透視投影隱藏面消除

取景變換（1/6）場景坐標系場景的局部坐標系完成物體的造型場景的世界坐標系（整體坐標系）放入待繪制的場景，定義物體之間的相互位置如果物體被設置了動畫動畫系統(tǒng)將提供一個隨時間變化的變換矩陣逐幀把物體變換到世界坐標系中114xzyzyx取景變換（2/6）觀察坐標系也稱攝像機坐標系，或者視點坐標系完成取景變換所需建立的第一個坐標系115取景變換（3/6）建立觀察坐標系的步驟確定觀察參考點，即視點位置可以設在任何位置通常選在靠近或在物體的表面將視點位置取為視點坐標系的原點確定觀察方向，即視線方向一般取深度坐標軸，即ze軸的正向為簡便起見，設為總是指向場景坐標系的原點確定觀察平面，即視平面位置一般取過視點且垂直于視線方向的平面，即xeye平面116取景變換（4/6）場景坐標系一般取右手坐標系觀察坐標系通常取左手坐標系符合人們的觀察習慣117xwzwywzexeye視點E觀察坐標系為左手坐標系場景坐標系為右手坐標系O取景變換（5/6）將物體投影到觀察平面之前必須將場景坐標系中的點轉換到觀察坐標系中

這一過程稱為取景變換，也稱視向變換包括平移和旋轉的一系列幾何變換的級聯(lián)取景變換矩陣118取景變換（6/6）場景坐標系原點平移到視點位置E繞xe軸逆時針旋轉90o繞ye軸順時針旋轉Ψ角繞xe軸逆時針旋轉θ角調整x軸指向對x軸作對稱變換119xwzwywzexeyeEOCxCyCzΨxwzwywzexeyeEOCxCyCz90oxwzwywzexeyeEOCxCyCzxwzwywzexeyeEOCxCyCzΨθθ消隱算法（1/2）消隱的基本（核心）問題：排序整體排序：畫家算法點排序：Z-Buffer算法、光線投射算法區(qū)間排序：掃描線算法區(qū)域排序：區(qū)域子分算法120消隱算法（2/2）按實現(xiàn)方式不同分為兩大類：景物空間（objectspace）

消隱算法直接在視點坐標系中確定視點不可見的表面區(qū)域將它們表達成同原表面一致的數(shù)據(jù)結構側重于景中各物體之間的幾何關系圖像空間（imagespace）消隱算法

在投影屏幕上，以屏幕像素為采樣單位，確定投影于每一像素的可見景物表面區(qū)域將其顏色作為該像素的顯示光亮度側重于向屏幕投影后形成的圖像121提高消隱算法效率的常用方法（1/5）提高消隱算法效率利用各種形式的相關性（連貫性）物體的連貫性面的連貫性區(qū)域的連貫性掃描線的連貫性幀的連貫性122提高消隱算法效率的常用方法（2/5）包圍盒技術避免盲目求交包圍盒--包圍目標的簡單形體包圍簡單常用的包圍盒長方體球圓柱123提高消隱算法效率的常用方法（3/5）空間分割技術124提高消隱算法效率的常用方法（5/5）背面剔除算法

125法向向量N

視線向量V法向向量N

法向向量N<90°<90°可見可見不可見>90°隱藏面的消除-畫家算法

（1/4）畫家算法

1972年M.E.Newell受畫家由遠至近作畫的啟發(fā)景物空間消隱算法126隱藏面的消除-畫家算法

（2/4）基本思想127畫家消隱算法{

對場景中的多邊形按深度進行排序， 形成深度優(yōu)先級隊列； 按從遠到近的順序顯示多邊形；}也稱優(yōu)先級表算法隱藏面的消除-畫家算法

（3/4）基本步驟生成深度優(yōu)先級隊列據(jù)視點距離遠的多邊形優(yōu)先級低，排在隊列的前端據(jù)視點距離近的多邊形優(yōu)先級高，排在隊列的后端從隊列中依次取出多邊形，計算其表面光亮度寫入幀緩沖器

直到隊列中所有多邊形的光亮度都計算完畢，并寫入幀緩沖器128隱藏面的消除-畫家算法

（4/4）優(yōu)點：簡單，容易實現(xiàn)適于圖形的動態(tài)顯示飛行訓練模擬器中顯示飛機著陸時的情景場景中的物體是不變的，只是視點在變化只要事先把不同視點的景物的優(yōu)先級隊列算出再實時地采用畫家算法來顯示圖形就可以實現(xiàn)圖形的快速消隱與顯示缺點：深度排序計算量大129隱藏面的消除-畫家算法

（4/4）問題：深度優(yōu)先級表的建立是動態(tài)進行的。假定觀察方向同Z軸同向，則最初可按各面的最小z值排序。但排序可能出錯130盡管面S1的最小z值小于面S2的最小z值，但正確順序是面S2位于面S1前若存在兩面相交和循環(huán)遮擋，必須求交分割后再進行排序隱藏面的消除-畫家算法

（4/4）算法(1）計算各面最小z值zmin，并以此值的優(yōu)先級進行排序，建立初步的深度優(yōu)先表；(2）表空結束。否則取表中深度最大的面Sn,檢查表中其它各面Sk(k=0,1,...,n-1)與Sn是否在Z方向存在重疊的關系。存在，記重疊面為Sj轉(3)。否則，將Sn寫入幀緩沖器，n=n-1轉(2)；(3)檢查Sn是否遮擋Sj，不遮擋則將Sn寫入幀緩存器，n=n-1轉(2)。否則，交換Sn和Sj在表中位置，轉(2)。如果Sn和Sj已經(jīng)交換過位置，則兩面交叉遮擋，轉(4)；(4)用Sn和Sj的交線分割Sn為兩部分，轉(1)。131隱藏面消除-Weiler-Atherton算法（1/3）Weiler-Atherton算法景物空間消隱算法基于Weiler-Atherton多邊形裁剪操作132隱藏面消除-Weiler-Atherton算法（2/3）基本步驟

1)深度預排序，形成景物多邊形表

將變換到屏幕坐標系中的景物表面按各頂點的z最小值進行排序2)當前具有最大z值的景物表面作為裁剪多邊形CP

深度最大、離視點最近3)用CP對景物多邊形表中排在后面的表面進行裁剪

產(chǎn)生內部多邊形Pin和外部多邊形Pout

133裁剪多邊形將主多邊形裁剪為內部多邊形和外部多邊形PinPout裁剪多邊形CP主多邊形SP隱藏面消除-Weiler-Atherton算法（3/3）4)比較CP與Pin的深度，檢查CP是否真正離視點最近是，則CP為可見表面不是，則取Pin為新的CP，重復步驟3)5)將位于CP之外的景物表面組成外裁剪結果多邊形表

取表中深度最大的表面為CP，重復步驟3)6)遞歸進行直到外裁剪結果多邊形表為空時為止134隱藏面的消除-BSP樹算法（1/2）BSP樹算法BinarySpacePartitioning景物空間消隱算法基于BSP樹，對景物表面進行二叉分類與畫家算法類似，景物多邊形由遠至近繪制特別適合的場合場景中物體位置固定不變、僅視點移動135隱藏面的消除-BSP樹算法（2/2）基本步驟

選一剖分平面P1，將場景空間分割成兩個半空間剖分結果表示為一棵BSP樹葉節(jié)點：景物左分支：位于剖分平面前面的景物右分支：位于剖分平面后面的景物依據(jù)視點位置，對子空間進行分類包含視點的子空間標識為“front”另一側子空間標識為“back”遞歸搜索該BSP樹，優(yōu)先繪制標識為“back”的子空間中所含的景物136P1P2P2frontfrontfrontbackbackbackACDB與物體相交，就將它分割為兩個物體

BfrontfrontbackbackACDP1P2隱藏面消除-深度緩沖器算法（1/10）深度緩沖器算法Depth—bufferalgorithm圖像空間消隱算法1975年，Catmull提出在像素級上以近物取代遠物有利于硬件實現(xiàn)，但需要較多存儲空間137隱藏面消除-深度緩沖器算法（2/10）深度與可見性138uvnxmaxymax隱藏面消除-深度緩沖器算法（3/10）基本思想將投影到顯示屏上的每一個象素所對應的多邊形表面的深度進行比較取最靠近視點的表面的屬性值作為該像素的屬性值用frame—buffer記錄該表面在該像素點的顏色或亮度值用Z—buffer記錄該表面在該像素點的深度深度緩沖器幀緩沖器的擴充也稱Z-Buffer算法139隱藏面消除-深度緩沖器算法（4/10）基本步驟

取景變換、透視變換、掃描轉換將物體描述轉化為屏幕坐標系中的投影坐標初始化深度緩沖器初始化為離視點最遠的最小值幀緩沖器初始化為背景的屬性值140隱藏面消除-深度緩沖器算法（5/10）流程：for（場景中的每一個多邊形）{

掃描轉換該多邊形；

for（多邊形所覆蓋的每一個像素點(x,y)）

{

計算多邊形在該像素點的深度值z(x,y)；

if（z(x,y)>Z-buf中對應此像素點(x,y)的z值）

{

把多邊形在(x,y)處的深度值z(x,y)存入Z-buf中的(x,y)處；把多邊形在(x,y)處的亮度值存入f-buf中的(x,y)處；

}}}當所有的多邊形都處理完后，幀緩沖器中的內容即為消除隱藏面后的圖像141隱藏面消除-深度緩沖器算法（6/10）優(yōu)點簡單，可輕而易舉地處理任意復雜的畫面在象素級上以近物代替遠物，易于消除隱藏面，并準確顯示復雜曲面之間的交線。計算量呈線性復雜度O(n)n:場景中景物表面采樣點的數(shù)目圖象空間的大小是固定的，計算量最多隨畫面復雜度線性增長無需對各景物表面片作深度預排序景物表面上的可見點可按任意次序寫入深度緩沖器和幀緩沖器易于硬件實現(xiàn)圖形工作站上帶有用于消隱的深度緩存，克服了深度緩存算法占用大量存儲單元的缺點很多微型機上都裝有基于深度緩沖器算法的圖形加速卡142隱藏面消除-深度緩沖器算法（7/10）缺點需要很大的存儲空間例如：象素數(shù)目500×500，深度值采用浮點型（4字節(jié)）除刷新緩存外，還需500*500*4=1M字節(jié)的額外存儲空間在實現(xiàn)反走樣、處理透明和半透明等效果方面存在困難，并產(chǎn)生巨大的處理時間開銷由于在幀緩沖器內的同一象素點上可見表面的寫入順序是不確定的，所以可能導致畫面上的局部錯誤。143隱藏面消除-深度緩沖器算法（8/10）改進一：減少需要相對測試的多邊形平面數(shù)最小最大測試

144不重疊,不可能互相遮蔽測試無確定結果

對每條邊進行最小最大測試XminXmax隱藏面消除-深度緩沖器算法（9/10）改進二：利用連貫性計算深度水平方向豎直方向145xmaxymax隱藏面消除-深度緩沖器算法（10/10）改進三：降低對存儲空間的需求圖像空間劃分為4、16甚至更多的子正方形或條狀區(qū)域在最小情況下，只對應一條掃描線的深度緩沖器掃描線相關算法146隱藏面的消除-掃描線相關算法（1/5）掃描線相關算法按掃描線順序處理一幀畫面在掃描平面（ZOX平面）上解決消隱問題由視點和掃描線所決定深度緩沖器算法的一維版本深度緩沖器所需的存儲空間屏幕水平分辨率×每個深度值所占的存儲位數(shù)147隱藏面的消除for(每條掃描線){

將掃描線幀緩沖器f_bu