第6章實(shí)體幾何造型基礎(chǔ)實(shí)體造型（SolidModeling）幾何造型技術(shù)第一代：手工繪制工程圖第二代：二維計(jì)算機(jī)繪圖第三代：三維線架系統(tǒng)第四代：曲面造型第五代：實(shí)體造型哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅2三維實(shí)體的表示（1/7）模型分類哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅3完全以數(shù)據(jù)描述規(guī)則形體的建模方法邊界表示分解表示構(gòu)造表示以過程和控制參數(shù)描述不規(guī)則形體的建模方法隨機(jī)插值模型迭代函數(shù)系統(tǒng)L系統(tǒng)粒子系統(tǒng)動(dòng)力系統(tǒng)三維實(shí)體的表示（2/7）過程模型哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅4包括----隨機(jī)插值模型、迭代函數(shù)系統(tǒng)、L系統(tǒng)、粒子系統(tǒng)、復(fù)變函數(shù)迭代等以一個(gè)過程和相應(yīng)的控制參數(shù)描述例如用一些控制參數(shù)和一個(gè)生成規(guī)則描述的植物以一個(gè)數(shù)據(jù)文件和一段代碼的形式存在三維實(shí)體的表示（3/7）數(shù)據(jù)模型哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅5完全以數(shù)據(jù)描述例如用以8個(gè)頂點(diǎn)表示的立方體以中心點(diǎn)和半徑表示的球以數(shù)據(jù)文件的形式存在包括----邊界表示、分解表示、構(gòu)造表示等三維實(shí)體的表示（6/7）線框模型哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅6相鄰頂點(diǎn)連接構(gòu)成棱邊表示幾何形狀特征形體表示成一組輪廓線的集合，只需建立三維線段表數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單、處理速度快所構(gòu)成的圖形含義不確切，與形體之間不存在一一對(duì)應(yīng)關(guān)系，有二義性不能計(jì)算面積、體積等物理量，不便進(jìn)行光照或消隱處理，不適合真實(shí)感顯示和數(shù)控加工----物體的骨架圖6-8用線框模型表示的有二義性的物體可以有三種不同的理解，從三個(gè)方向中的一個(gè)方向打一個(gè)方孔

三維實(shí)體的表示（7/7）表面模型哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅7----物體的皮膚用有向棱邊圍成的部分來定義形體表面，由面的集合來定義形體形體與其表面一一對(duì)應(yīng)，避免了二義性能夠滿足真實(shí)感顯示和數(shù)控加工等需求能夠計(jì)算面積，表達(dá)物體的表面形狀，只有面的信息，形體信息不完整進(jìn)行剖切操作時(shí)，內(nèi)部為空洞，無法計(jì)算和分析物體的整體性質(zhì)（如體積、重心等），限制了在工程分析方面的應(yīng)用在面模型上打孔，內(nèi)部為“空洞”三維實(shí)體的表示（7/7）實(shí)體模型哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅8----”有血有肉”的物體模型主要是明確定義了表面的哪一側(cè)存在實(shí)體，在表面模型的基礎(chǔ)上，使用表面的外法線矢量方向來指明實(shí)體存在的一側(cè)，例如規(guī)定正向指向體外。通常用有向棱邊隱含地表示表面的外法線矢量方向在定義表面時(shí)，有向棱邊按右手法則取向，沿著閉合的棱邊所得的方向與表面外法線矢量方向一致。用此方法還可檢查形體的拓?fù)湟恢滦裕貥愫戏ǖ男误w在相鄰兩個(gè)面的公共邊界上，棱邊的方向正好相反。包含描述實(shí)體所需的較多信息，如幾何信息、拓?fù)湫畔?，表示完整而無歧義。實(shí)現(xiàn)所有的CAD/CAM任務(wù)，保證CAD/CAM的自動(dòng)化三種表示模型的功能比較哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅9多面體模型（1/10）每個(gè)多邊形的數(shù)據(jù)被存儲(chǔ)在多邊形數(shù)據(jù)表中多邊形數(shù)據(jù)表可分兩組：幾何表包括物體的幾何數(shù)據(jù)（如頂點(diǎn)坐標(biāo)等）和用來標(biāo)識(shí)多邊形表面空間取向的參數(shù)（如表面外法線方向）屬性表包括物體透明度、表面反射系數(shù)以及紋理特征參數(shù) 哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅10多面體模型（2/10）通常以層次結(jié)構(gòu)存儲(chǔ)哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅11圖6-1繪制多面體所需的層次數(shù)據(jù)結(jié)構(gòu)信息表面表0表面表1…多邊形表0多邊形表1…V0,Nv0V1,Nv1V2,Nv2V3,Nv3…Np0Np1…表面表數(shù)組多邊形表面數(shù)組頂點(diǎn)數(shù)組多邊形法向量數(shù)組Nv3Nv0Nv1Nv2V3V0V1V2Np0(b)多邊形信息(a)層次數(shù)據(jù)結(jié)構(gòu)信息在Phong明暗處理算法中用到在背面剔除中用到多面體模型（3/10）缺點(diǎn)：相鄰多邊形的共享邊在上述數(shù)據(jù)結(jié)構(gòu)中沒有得到顯式表達(dá)，這使得同一條邊在繪制過程中可能被處理兩次。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅12多面體模型（4/10）基于邊的表示邊數(shù)組的每個(gè)元素包含4個(gè)指針，分別指向?qū)?yīng)邊的兩個(gè)頂點(diǎn)和它鄰接的兩個(gè)多邊形法向量哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅13圖6-2基于邊的繪制方法所需的數(shù)據(jù)結(jié)構(gòu)信息(a)多邊形信息邊數(shù)組頂點(diǎn)數(shù)組法向量數(shù)組V0,Nv0V1,Nv1V2,Nv2V3,Nv3…1,2,2,00,1,1,03,0,1,02,3,2,03,1,2,1…NULLNp1Np2…V0Nv3Nv0Nv1Nv2V3V1V2Np1Np2E1E0E2E3E4(b)基于邊的數(shù)據(jù)結(jié)構(gòu)信息多面體模型（8/10）多面體模型的優(yōu)點(diǎn)數(shù)據(jù)結(jié)構(gòu)相對(duì)簡(jiǎn)單集合運(yùn)算、明暗圖的生成和顯示速度快缺點(diǎn)：雖然多面體可以任意精度逼近任意復(fù)雜的曲面物體，但它畢竟是曲面物體的一種近似逼近表示，存在誤差

哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅14圖6-5曲面物體的多面體近似逼近表示過程曲面物體曲面逼近多邊形多邊形頂點(diǎn)曲面模型（1/10）曲面造型研究在計(jì)算機(jī)內(nèi)如何描述一張曲面，如何對(duì)曲面的形狀進(jìn)行控制與顯示可以由數(shù)學(xué)函數(shù)來定義包括二次曲面、超二次曲面、隱函數(shù)曲面等也可以由用戶輸入一系列離散的數(shù)據(jù)點(diǎn)來確定的參數(shù)曲面（第4章）如Coons曲面、B樣條曲面、NURBS曲面等哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅15哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅16四面體網(wǎng)格模型表示方法將包含實(shí)體的空間分割成四面體單元的集合特點(diǎn)可以以邊界面片為四面體的一個(gè)面，模型精度高能夠構(gòu)建復(fù)雜形體的網(wǎng)格模型在復(fù)雜對(duì)象的科學(xué)計(jì)算和工程分析中具有重要的應(yīng)用四面體網(wǎng)格模型數(shù)據(jù)結(jié)構(gòu)復(fù)雜，實(shí)現(xiàn)復(fù)雜空間域邊界一致的四面體剖分是近年來的研究熱點(diǎn)。

描述實(shí)體的信息GeometryTopology哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅17描述形體的幾何元素（頂點(diǎn)、邊、面）之間的連接關(guān)系，形成物體邊界表示的“骨架”描述形體的幾何元素性質(zhì)和度量關(guān)系，如位置、大小、方向、尺寸、形狀等信息猶如附著在“骨架”上的肌肉按照：體－面－環(huán)－邊－點(diǎn)的層次記錄信息

實(shí)體的定義（1/14）表示形體的基本幾何元素：頂點(diǎn)（Vertex）邊（Edge）面（Face）環(huán)（Loop）體（Body）哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅18零維幾何元素。在齊次坐標(biāo)系下，n維空間中的點(diǎn)用n+1維向量來表示。

一維幾何元素。對(duì)正則形體，邊是兩鄰面的交集，對(duì)非正則形體，邊有可能是多個(gè)鄰面的交集。邊的形狀可以是直線，也可以是曲線。二維幾何元素。可以無內(nèi)環(huán)，但必須有一個(gè)且只有一個(gè)外環(huán)。面有方向性，一般用其外法線方向作為該面的正向。面的形狀可以是平面，也可以是曲面

二維幾何元素。有序、有向邊（直線段或曲線段）組成的面的封閉邊界。外環(huán)邊通常按逆時(shí)針方向排序，內(nèi)環(huán)邊通常按順時(shí)針方向排序。三維幾何元素。由封閉表面圍成的空間，其邊界是有限面的并集。實(shí)體的定義（2/14）幾何造型就是通過對(duì)點(diǎn)、線、面、體等幾何元素經(jīng)平移、放縮、旋轉(zhuǎn)等幾何變換和并、交、差等集合運(yùn)算產(chǎn)生實(shí)際的或想象的物體模型哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅19實(shí)體幾何造型（SolidModeling）研究三維幾何實(shí)體在計(jì)算機(jī)中的完整信息表示的模型和方法的技術(shù)實(shí)體的定義（3/14）如何保證實(shí)體的有效性呢？一個(gè)無效的實(shí)體當(dāng)然也不具備可加工性要保證實(shí)體的有效性和可加工性，形體必須是正則的那么什么是正則形體呢？哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅20實(shí)體的定義（3/14）二維流形（2-manifold）美國H.B.Voelcker和A.A.G.Requicha等為描述正則形體引入的概念指這樣一些面，其上任意一點(diǎn)都存在一個(gè)充分小的鄰域，該鄰域與平面上的封閉圓盤是同構(gòu)的，即在該鄰域與圓盤之間存在連續(xù)的一一映射正則形體？對(duì)于任一形體，它是三維歐氏空間R3中非空、有界的封閉子集，且其邊界是二維流形（即該形體是連通的）否則稱為非正則形體哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅21實(shí)體的定義（3/14）如何得到一個(gè)正則形體？將三維形體點(diǎn)集分成內(nèi)部點(diǎn)集和邊界點(diǎn)集兩部分先找出形體的內(nèi)部點(diǎn)集然后形成形體內(nèi)部點(diǎn)集的閉包哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅22圖6-9正則形體的形成過程示意圖(a)形體的開集(b)圖(a)開集的閉包(c)圖(a)形體的內(nèi)部點(diǎn)集(d)圖(c)內(nèi)部點(diǎn)集的閉包實(shí)體的定義（3/14）正則形體的性質(zhì)？（1）剛性不變形的實(shí)體，不能隨實(shí)體的位置和方向而發(fā)生形狀變化（2）維數(shù)的一致性三維空間中的實(shí)體的各部分均應(yīng)是三維的哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅23實(shí)體的定義（8/14）

幾何元素

正則形體

非正則形體

面

是形體表面的一部分不允許存在懸面

可以是形體表面的一部分，也可以是形體內(nèi)的一部分，也可以與形體相分離。

邊

只有兩個(gè)鄰面不允許存在懸邊

可以有多個(gè)鄰面、一個(gè)鄰面或沒有鄰面。

點(diǎn)

至少和三個(gè)面（或三條邊）鄰接不允許存在孤立點(diǎn)

可以與多個(gè)面（或邊）鄰接，也可以是聚集體、聚集面、聚集邊或孤立點(diǎn)。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅24實(shí)體的定義（4/14）正則形體的性質(zhì)？（3）有限性一個(gè)實(shí)體必須占據(jù)有限的三維空間（4）邊界的確定性根據(jù)實(shí)體的邊界能區(qū)分出實(shí)體的內(nèi)部和外部（5）封閉性經(jīng)過一系列剛體運(yùn)動(dòng)和任意次序的集合運(yùn)算之后，實(shí)體仍保持其同等的有效性哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅25實(shí)體的定義（4/14）正則形體的表面的性質(zhì)（1）連通性位于實(shí)體表面上的任意兩個(gè)點(diǎn)都可用實(shí)體表面上的一條路經(jīng)連接起來（2）有界性實(shí)體在有限空間內(nèi)是可定義的，即實(shí)體表面可將空間分成互不連通的兩個(gè)區(qū)域，其中一個(gè)區(qū)域是有界的。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅26實(shí)體的定義（4/14）正則形體的表面的性質(zhì)（3）非自交性實(shí)體的表面不能自交克萊茵瓶（KleinBottle）就是一個(gè)自交且不可定向的封閉曲面（4）可定向性表面的兩側(cè)可明確地定義出屬于實(shí)體的內(nèi)側(cè)還是外側(cè)莫比烏斯帶（MobiusBand）則是一個(gè)單邊不可定向的例子哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅27實(shí)體的定義（4/14）確定多面體表面是否具有可定向性的方法Mobius提出將實(shí)體的每個(gè)表面的邊環(huán)定義一個(gè)一致的方向（例如逆時(shí)針方向），這樣，每條邊會(huì)得到兩個(gè)指示方向的箭頭，當(dāng)且僅當(dāng)每條邊在每個(gè)方向都具有一個(gè)箭頭時(shí)，該實(shí)體表面就是可定向的。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅28歐拉公式與歐拉運(yùn)算歐拉特征設(shè)表面s由一個(gè)平面模型給出，且v,e,f分別表示其頂點(diǎn)、邊和小面的個(gè)數(shù)，那么v-e+f是一個(gè)常數(shù)，它與s劃分形成平面模型的方式無關(guān)。該常數(shù)稱為Euler特征。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅29v=8,e=13,f=7v-e+f=2歐拉公式歐拉公式與歐拉運(yùn)算歐拉物體滿足歐拉公式的物體歐拉運(yùn)算增加或者刪除面、邊和頂點(diǎn)以生成新的歐拉物體的過程哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅30歐拉公式只是檢查實(shí)體有效性的一個(gè)必要條件，而不是充分條件實(shí)體的正則集合運(yùn)算為什么在正則實(shí)體造型中，不使用普通的并、交、差等集合運(yùn)算，而要使用正則集合運(yùn)算呢？普通的集合運(yùn)算會(huì)產(chǎn)生懸邊、懸面等低于三維的形體哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅31正則集合運(yùn)算保證集合運(yùn)算的結(jié)果仍是一個(gè)正則形體實(shí)體的正則集合運(yùn)算如何實(shí)現(xiàn)正則集合運(yùn)算？方法1：先按照普通集合運(yùn)算再刪去不符合正則形體定義的部分：懸邊、懸面等方法2：定義正則集合算子，直接計(jì)算得到哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅32正則集合運(yùn)算任何物體都可用三維歐氏空間中點(diǎn)的集合來表示，但三維歐氏空間中任意點(diǎn)的集合卻不一定對(duì)應(yīng)于一個(gè)有效的物體設(shè)有三維空間中的一個(gè)點(diǎn)集A，那么稱為A的正則點(diǎn)集。如果A滿足那么稱A為正則點(diǎn)集。其中，r表示正則化算子，b、i分別表示取閉包運(yùn)算和取內(nèi)點(diǎn)運(yùn)算。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅33正則集合運(yùn)算正則集合運(yùn)算定義如下：正則并正則交正則差哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅34正則集合運(yùn)算以正則交集合運(yùn)算為例符合正則形體定義的實(shí)體，是三維空間中的點(diǎn)的正則點(diǎn)集，可以用它的邊界點(diǎn)集和內(nèi)部點(diǎn)集來表示，即寫成A為符合正則形體定義的實(shí)體bA代表A的邊界點(diǎn)集iA代表A的內(nèi)部點(diǎn)集哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅35正則集合運(yùn)算普通集合交運(yùn)算確定兩個(gè)相交物體的重疊邊界中的有效部分確定圖中粗實(shí)線所示邊界中的有效部分哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅36圖6-17正則交運(yùn)算的候選部分(a)

(b)(d)ABABAB12AB(c)正則集合運(yùn)算確定兩個(gè)相交物體的重疊邊界中的有效部分確定圖中粗實(shí)線所示邊界中的有效部分如果對(duì)物體的邊界采用一致的方向約定，那么，在兩個(gè)相交物體的重疊邊界上，如果某點(diǎn)處的切矢同向，則重疊邊界線段就是的有效邊界，否則，就是無效的邊界哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅37圖6-17正則交運(yùn)算的候選部分(a)

(b)(d)ABABAB12AB(c)正則集合運(yùn)算哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅38數(shù)據(jù)模型——邊界表示BoundaryRepresentation，也稱BR表示或BRep表示最成熟、無二義性當(dāng)前CAD/CAM系統(tǒng)中的最主要的表示方法物體的邊界與物體一一對(duì)應(yīng)實(shí)體的邊界是表面的并集表面的邊界是邊的并集哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅39數(shù)據(jù)模型——邊界表示多面體表示的實(shí)體的表面、棱邊、頂點(diǎn)之間的連接關(guān)系有9種類型至少需要選擇其中的2種才能表示一個(gè)實(shí)體的完整的拓?fù)湫畔⒐枮I工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅40圖6-20表面、棱邊、頂點(diǎn)之間的拓?fù)潢P(guān)系ffffff→{f}feeeef→{e}fvvvvf→{v}effe→{f}eeeeee→{e}evve→{v}vfffv→{f}veeev→{e}vvvvv→{v}采用較少的關(guān)系類型進(jìn)行組合來表示一個(gè)實(shí)體，所需的存儲(chǔ)空間小，但對(duì)數(shù)據(jù)的查找時(shí)間長(zhǎng)反之，所需的存儲(chǔ)空間大，但對(duì)數(shù)據(jù)的查找時(shí)間短數(shù)據(jù)模型——邊界表示比較著名的有半邊數(shù)據(jù)結(jié)構(gòu)、翼邊數(shù)據(jù)結(jié)構(gòu)、輻射邊數(shù)據(jù)結(jié)構(gòu)等翼邊數(shù)據(jù)結(jié)構(gòu)最早是由美國斯坦福大學(xué)B.G.Baumgart等人于1972年提出以邊為核心來組織數(shù)據(jù)的一種數(shù)據(jù)結(jié)構(gòu)用指針記錄每一邊的兩個(gè)鄰面（即左外環(huán)和右外環(huán)）、兩個(gè)頂點(diǎn)、兩側(cè)各自相鄰的兩個(gè)鄰邊（即左上邊、左下邊、右上邊和右下邊）用這一數(shù)據(jù)結(jié)構(gòu)表示多面體模型是完備的，但它不能表示帶有精確曲面邊界的實(shí)體哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅41圖6-21翼邊數(shù)據(jù)結(jié)構(gòu)左上邊右上邊左下邊右下邊左外環(huán)右外環(huán)eP2P1數(shù)據(jù)模型——邊界表示與翼邊數(shù)據(jù)結(jié)構(gòu)的主要區(qū)別：將一條物理邊拆成兩條邊來表示使其中每條邊只與一個(gè)鄰接面相關(guān)由于半邊數(shù)據(jù)結(jié)構(gòu)中的邊只表示相應(yīng)物理邊的一半信息，所以稱其為半邊哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅42數(shù)據(jù)模型——分解表示（1/5）空間位置枚舉表示選擇一個(gè)立方體空間，將其均勻劃分哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅43

當(dāng)C[I][j][k]=1時(shí)，表示對(duì)應(yīng)的小立方體被物體占據(jù)當(dāng)C[I][j][k]=0時(shí)，表示對(duì)應(yīng)的小立方體沒有被物體占據(jù)用三維數(shù)組C[I][J][K]表示物體，數(shù)組中的元素與單位小立方體一一對(duì)應(yīng)數(shù)據(jù)模型——分解表示（2/5）八叉樹（octrees）表示對(duì)空間位置枚舉表示的空間分割方法作了改進(jìn)：均勻分割自適應(yīng)分割哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅44數(shù)據(jù)模型——分解表示（3/5）哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅45八叉樹建立過程八叉樹的根節(jié)點(diǎn)對(duì)應(yīng)整個(gè)物體空間如果它完全被物體占據(jù)，將該節(jié)點(diǎn)標(biāo)記為F(Full)，算法結(jié)束；如果它內(nèi)部沒有物體，將該節(jié)點(diǎn)標(biāo)記為E(Empty)，算法結(jié)束；如果它被物體部分占據(jù)，將該節(jié)點(diǎn)標(biāo)記為P(Partial)，并將它分割成8個(gè)子立方體，對(duì)每一個(gè)子立方體進(jìn)行同樣的處理(a)(b)zyx55554777FPEEEEEEEEEFEFFEP1023456012345677數(shù)據(jù)模型——分解表示（4/5）單元分解（celldecomposition）表示對(duì)空間位置枚舉表示的空間分割方法作了改進(jìn)：?jiǎn)我惑w素多種體素哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅46數(shù)據(jù)模型——分解表示（5/5）三種空間分割方法的比較空間位置枚舉表示----同樣大小立方體粘合在一起表示物體八叉樹表示----不同大小的立方體粘合在一起表示物體單元分解表示----多種體素粘合在一起表示物體哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅47數(shù)據(jù)模型——構(gòu)造實(shí)體幾何表示（1/5）構(gòu)造實(shí)體幾何表示constructivesolidgemetry，簡(jiǎn)稱CSG采用單一的“建筑塊”形式的實(shí)體造型方法，由兩個(gè)物體的正則集合操作生成新的物體并（union）交（intersection）差（difference）哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅48U－數(shù)據(jù)模型——構(gòu)造實(shí)體幾何表示（3/5）將物體表示成一棵二叉樹，稱為CSG樹葉節(jié)點(diǎn)----基本體素，如立方體、圓柱體、圓環(huán)、錐體、球體等中間節(jié)點(diǎn)----并、交、差正則集合運(yùn)算哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅49數(shù)據(jù)模型——掃描表示(1/6)sweeprepresentations基于一個(gè)基體（一般為封閉的二維區(qū)域）沿某一路徑運(yùn)動(dòng)而產(chǎn)生形體sweep體

哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅50兩個(gè)分量被運(yùn)動(dòng)的基體基體運(yùn)動(dòng)的路徑如果是變截面的掃描，還要給出截面變化規(guī)律

數(shù)據(jù)模型——掃描表示(2/6)根據(jù)掃描路徑和方式的不同，可將sweep體分為以下幾種類型：平移sweep體

旋轉(zhuǎn)sweep體

廣義sweep體

哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅51數(shù)據(jù)模型——掃描表示(3/6)平移sweep將一個(gè)二維區(qū)域沿著一個(gè)矢量方向（線性路徑）推移，拉伸曲面哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅52數(shù)據(jù)模型——掃描表示(4/6)旋轉(zhuǎn)sweep將一個(gè)二維區(qū)域繞旋轉(zhuǎn)軸旋轉(zhuǎn)一特定角度（如一周），旋轉(zhuǎn)曲面哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅533DMAX例子旋轉(zhuǎn)掃描法數(shù)據(jù)模型——掃描表示(5/6)哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅54廣義sweep任意剖面沿著任意軌跡掃描指定的距離

，掃描路徑可以用曲線函數(shù)來描述可以沿掃描路徑變化剖面的形狀和大小或者當(dāng)移動(dòng)該形狀通過某空間時(shí)變化剖面相對(duì)于掃描路徑的方向也稱掃描曲面

掃描體的掃描路徑為曲線時(shí)得到的廣義sweep體基面基面(a)等截面掃描(b)變截面掃描廣義掃描法元球表示法用相互重疊的球體表示物體形狀特點(diǎn)數(shù)據(jù)描述方法簡(jiǎn)單球體只需要球心和半徑兩個(gè)參數(shù)就能完全確定計(jì)算速度快、所需內(nèi)存小特殊性質(zhì)：球體的平行投影總是圓因此用球體表示三維物體（尤其是人體）計(jì)算速度快Badler使用300多個(gè)球體就相當(dāng)好地表示了人體哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅55第7章自然景物模擬玉芬性藝術(shù)什么是分形？（1/21）著名理論物理學(xué)家約翰·惠勒(J.Wheeler)說過：在過去，一個(gè)人如果不懂得熵是怎么回事，就不能說是科學(xué)上有教養(yǎng)的人；在將來，一個(gè)人如果不能同樣熟悉分形，他就不能被認(rèn)為是科學(xué)上的文化人。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅57什么是分形？（2/21）非線性科學(xué)(nonlinearscience)中最重要的三個(gè)概念混沌(chaos,也譯作“渾沌”)分形(Fractal)孤子(soliton，也稱“孤波”(solitarywave))分形理論是非線性科學(xué)研究領(lǐng)域中一個(gè)十分活躍的分支本質(zhì)是一種新的世界觀和方法論揭示了有序與無序的統(tǒng)一，確定性與隨機(jī)性的統(tǒng)一被認(rèn)為是科學(xué)領(lǐng)域中繼相對(duì)論、量子力學(xué)之后，人類認(rèn)識(shí)和改造世界的最富有創(chuàng)造性的第三次革命哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅58哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅59第一個(gè)分形例子由文藝復(fù)興時(shí)期德國著名畫家丟勒(AlbertDurer，1471-1528)

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

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

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

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

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

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

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

周長(zhǎng)無窮，但面積為定值（0）構(gòu)造方法演示什么是分形？（13/21）哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅69構(gòu)造方法周長(zhǎng)無窮，但面積為定值

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

1924年11月20日B.B.Mandelbrot生于波蘭。1952年，Mandelbrot獲博士學(xué)位。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅71傳統(tǒng)的歐式幾何理論描繪已顯得無能為力

什么是分形？（16/21）60年代，B.B.Mandelbrot將雪花與海岸線、山水、樹木等自然景物聯(lián)系起來現(xiàn)代分形理論的奠基人經(jīng)歷、性格、舉止非同尋常的人物

哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅72Mandelbrot與北京大學(xué)非線性科學(xué)中心主任趙凱華教授

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

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

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

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

cl

+dN

clN

l

c與維數(shù)定義有關(guān)的函數(shù)關(guān)系是冪指數(shù)關(guān)系，簡(jiǎn)稱冪律(Powerlaw)什么是分形維數(shù)？（5/12）1919年F.Hausdorff(1868-1942)

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

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

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

L→3L=3^1*L平面上的一個(gè)正方形P，邊長(zhǎng)為A，將其邊長(zhǎng)擴(kuò)大到原來的3倍9個(gè)正方形：

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

L→3L=3^1*L平面上的一個(gè)正方形P，邊長(zhǎng)為A，將其邊長(zhǎng)擴(kuò)大到原來的3倍9個(gè)正方形：

P→9P=3^2*P三維空間上的正方體V，邊長(zhǎng)為A，將其邊長(zhǎng)擴(kuò)大到原來的3倍27個(gè)立方體：V→27V=3^3*V

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

L→3L=3^1*L平面上的一個(gè)正方形P，邊長(zhǎng)為A，將其邊長(zhǎng)擴(kuò)大到原來的3倍9個(gè)正方形：

P→9P=3^2*P三維空間上的正方體V，邊長(zhǎng)為A，將其邊長(zhǎng)擴(kuò)大到原來的3倍27個(gè)立方體：V→27V=3^3*V

得到的總個(gè)數(shù)可表達(dá)為：

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

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

log(1/r)logN(r)r為細(xì)分時(shí)縮放因子什么是分形維數(shù)？（11/12）以Koch曲線為例細(xì)分線段數(shù)為N=4，細(xì)分單元長(zhǎng)度為S=1/3Koch曲線的分?jǐn)?shù)維為：

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

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

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

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

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

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

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

哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅105

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

（ContractiveAffineTransformation）

迭代函數(shù)系統(tǒng)（7/20）設(shè)給定一個(gè)仿射變換f，對(duì)任意向量x和y，如果總存在一個(gè)非負(fù)實(shí)數(shù)，滿足則s稱為壓縮因子使得上式成立的最小實(shí)數(shù)稱為L(zhǎng)ipschitz常數(shù)（李普希茨常數(shù)

）因s<1，因此仿射變換f是收縮仿射變換哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅107

迭代函數(shù)系統(tǒng)（8/20）

上的收縮仿射變換（壓縮映射）記為哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅108迭代函數(shù)系統(tǒng)

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

確定仿射變換

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

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

設(shè)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的過程相當(dāng)于為每種迭代規(guī)則R_i指派一個(gè)概率p_i怎樣確定概率向量？控制概率就是控制圖形各部分的落點(diǎn)密度，使圖形在有限迭代步數(shù)內(nèi)顯現(xiàn)出濃淡虛實(shí)不同的繪制效果。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅112迭代函數(shù)系統(tǒng)（12/20）D=log3/log2=1.585Sierpinski三角形fabc

defp

10.5000.52510.3320.5000.51500.3330.5000.550500.33哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅113Sierpinskicarpet迭代函數(shù)系統(tǒng)（13/20）D=log8/log3=1.8927迭代函數(shù)系統(tǒng)（14/20）哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅114Barnsley蕨的參數(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ù)表迭代函數(shù)系統(tǒng)（15/20）哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅115樹冠的參數(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è)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅116迭代函數(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è)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅117迭代函數(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è)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅118迭代函數(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迭代函數(shù)系統(tǒng)（19/20）增減規(guī)則R_i，可以改變最終植物M的形態(tài)。即使不改變迭代規(guī)則，采用同樣的程序，只改變參數(shù)也可以生成完全不同的植物形態(tài)。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅119ProcedureAFF(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;迭代函數(shù)系統(tǒng)（20/20）應(yīng)用自然景物模擬分形圖像壓縮120L系統(tǒng)（1/13）由美國生物學(xué)家林德梅葉(Lindenmayer)創(chuàng)立，1984年由Smith等人將L系統(tǒng)引入圖形學(xué)1990年，普魯辛凱維奇(P.Prusinkiewicz)與林氏出版《植物的算法美》(TheAlgorithmicBeautyofPlants)哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅121是一種形式語言字符串重寫系統(tǒng)通過符號(hào)串的解釋，轉(zhuǎn)化為造型工具基本思想：從一個(gè)初始串(叫做公理)開始將變換規(guī)則多次作用于其上最后產(chǎn)生一個(gè)較長(zhǎng)的命令串L系統(tǒng)（2/13）L系統(tǒng)分類0L系統(tǒng)與上下文無關(guān)1L系統(tǒng)僅考慮單邊的文法關(guān)系，即左相關(guān)或右相關(guān)在植物的生態(tài)模擬中左相關(guān)文法用于模擬植物從根向葉、莖的傳播過程右相關(guān)文法用于模擬從葉到莖、根的傳播過程2L系統(tǒng)同時(shí)考慮左邊和右邊文法關(guān)系哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅122L系統(tǒng)（3/13）哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅123D0L系統(tǒng)確定的上下文無關(guān)的L系統(tǒng)定義為一個(gè)三元組〈V,ω,P〉V：字符表(alphabet)V*：V上的所有單詞(words)ω：ω∈V*是一個(gè)非空的單詞，稱公理(axiom)P

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

L系統(tǒng)（4/13）設(shè)計(jì)D0L系統(tǒng)的步驟：定義字符表V給出公理，即初始圖ω定義產(chǎn)生式P

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

并去掉該棧中的內(nèi)容\nn增加角度nn度/nn減少角度nn度Cnn選擇顏色nn＜nn在此基礎(chǔ)上增加顏色nn＞nn在此基礎(chǔ)上減少顏色nn!倒轉(zhuǎn)方向(控制+,-,/)@nnn將線段長(zhǎng)度乘以nnn，nnn也可以是簡(jiǎn)單函數(shù)其他也是合法的，主要用于獲得復(fù)雜的解釋L系統(tǒng)（6/13）13世紀(jì)數(shù)學(xué)家Fibonacci（1170-1250）兔子的理想化繁衍問題

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

哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅127n=0n=1n=2n=3w：F++F++F

倒置的正三角形生成元初始圖L系統(tǒng)（8/13）Koch島V：{F,+,-}w：F﹣F﹣F﹣FP：F→F﹢F﹣F﹣FF﹢F﹢F﹣Fδ=90o令步長(zhǎng)d在相鄰兩級(jí)子圖之間縮短4倍，規(guī)定后繼多邊形線(折線)端點(diǎn)之間的距離等于前驅(qū)線段的長(zhǎng)度

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

δ=90o

生成元初始圖L系統(tǒng)（10/13）植物w：FP：F->F[+F]F[-F]F[:將當(dāng)前烏龜爬行的狀態(tài)壓入堆棧，信息包括所在位置和方向等]:從堆棧中彈出一個(gè)狀態(tài)作為烏龜?shù)漠?dāng)前狀態(tài)，但不畫線哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅130L系統(tǒng)（11/13）哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅131植物（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]L系統(tǒng)（12/13）哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅132模擬側(cè)柏形態(tài)（左圖）w：FP：F->F［+F］F［-F］［F］

δ=90oL系統(tǒng)（13/13）設(shè)計(jì)L系統(tǒng)的過程是根據(jù)自相似結(jié)構(gòu)形成信息壓縮的一個(gè)過程利用設(shè)計(jì)好的L系統(tǒng)進(jìn)行繪制的過程是信息壓縮的逆過程，或者說是信息復(fù)原的過程。

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

W.T.Reeves1983年提出最重要的計(jì)算機(jī)生成模型方法哈爾濱工業(yè)大學(xué)計(jì)算機(jī)學(xué)院蘇小紅134描述對(duì)象不規(guī)則、結(jié)構(gòu)隨時(shí)間而變化的FuzzyObject

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

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

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

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

〔2）初始運(yùn)動(dòng)速度和方向；（3）初始顏色；（4）初始透明度；

〔5）初始形狀；（6）生命周期。粒子系統(tǒng)（7/8）粒子數(shù)目對(duì)模糊物體的密度有很重要的影響，粒子系統(tǒng)通過控制每一幀進(jìn)入系統(tǒng)的粒子數(shù)和死亡的粒子數(shù)來控制粒子系統(tǒng)中粒子的數(shù)量?？刂泼繋牧Ｗ訑?shù)的兩種方法由每幀產(chǎn)生的粒子平均數(shù)和其方差控制粒子數(shù)，實(shí)際在f幀產(chǎn)生的粒子數(shù)為新產(chǎn)生的粒子數(shù)取決于物體的屏幕尺寸?？刂泼總€(gè)屏幕單位產(chǎn)生的粒子平均數(shù)MeanParts和其方差VarParts

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

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

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

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

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

復(fù)平面上的迭代（4/1