計算機圖形學（第3版）課件：形體的表示及其數(shù)據(jù)結(jié)構(gòu)

2024/12/141計算機圖形學

形體的表示及其數(shù)據(jù)結(jié)構(gòu)第一節(jié)二維形體的表示第二節(jié)三維幾何模型第三節(jié)分形第四節(jié)粒子系統(tǒng)第六章形體的表示及其數(shù)據(jù)結(jié)構(gòu)

與空間任意形體有關(guān)的信息可以分為1.圖形信息:點、線、面的位置,相互關(guān)系及大小等2.非圖形信息:顏色、亮度、質(zhì)量、體積。圖形信息包括1.幾何信息：形體在空間的位置和大小2.拓撲信息：組成形體各部分的數(shù)目及相互間的連接關(guān)系。形體的表示方法通?？煞譃閮深悾?.邊界表示：用邊界將形體分為內(nèi)部和外部。例如曲線曲面2.空間分區(qū)表示：描述形體的內(nèi)部性質(zhì),將包含形體的空間區(qū)域劃分為一組小的非重疊的連續(xù)實體。（四叉樹和八叉樹）二維圖形的邊界表示 帶樹法帶樹是一棵二叉樹,樹的每個結(jié)點對應一個矩形帶段,這樣每個結(jié)點可由八個字段組成,前六個字段描述矩形帶段,后二個是指向兩個子結(jié)點的指針,即矩形帶段的起點是(xb,yb),終點是(xe,ye)。相對從起點到終點的連線,矩形有兩邊與之平行,兩邊與之垂直,平行兩邊與之距離分別為wl和wr。第一節(jié)二維形體的表示設(shè)表示曲線有5個點(3,7)(9,12),(15,4),(18,5),(20,7),取分辨率w0=1,則上述算法構(gòu)造的帶樹設(shè)要表示的曲線是由經(jīng)過適當選取已確定的一組離散點P0,P1,…,Pn序列給出,則生成表示曲線的分辨率為w0的帶樹的算法,可簡略描述如下:BINARY*Create(float*P,inti,intj，floatW){/*BINARY帶樹節(jié)點類型,P[i]至P[j]描述折線表示的曲線,W為分辨率*/ Search(P,i,j,wl,wr);//確定P[i]至P[j]所有點所形成的矩形帶段的寬度

root=new(BINARY);//獲取帶樹節(jié)點

CBINARY(root,wl,wr,P,i,j);//構(gòu)造根節(jié)點

if(wl+wr<=W)returnroot;//返回帶樹根節(jié)點

else{ k=maxdis(P,i,j);//找出距Pi與Pj連線垂直距離最遠的點Pk t1=Create(P,i,k,W);//構(gòu)造P[i]至P[k]點間的帶樹

t2=Create(P,k,j,W);//構(gòu)造P[k]至P[j]點間的帶樹

Left(root,t1);//t1作為root左子樹

Right(root,t2);//t2作為root右子樹

return(root);// }}帶樹法解決曲線的問題：①以不同的分辨率顯示用帶樹表示的曲線 設(shè)給出允許的分辨率為w,表示曲線的帶樹的分辨率為w0,并設(shè)w0≤w,則顯示算法如下: (1)根結(jié)點 若當前正考查結(jié)點的W=wl+wr≤w,

則顯示該結(jié)點對應的矩形帶段;

否則,即W>w

則轉(zhuǎn)去分別考查該結(jié)點的左右兩個子結(jié)點, (2)對子結(jié)點做同樣的處理。

左右子結(jié)點都被顯示的結(jié)點就認為是被顯示了,按此看法,顯示帶樹表示的曲線就是顯示帶樹的結(jié)點。

voidDisplay(BINARY*root,floatW){//BINARY帶樹節(jié)點類型root帶樹根指針,

W為顯示分辨率 if(Width(root)<=W){//wl與wr之和函數(shù)

DisplayLine(root);//顯示帶樹為兩端點線段

return; }else{ Display(root->left,W);//顯示左子樹

Display(root->right,W);//顯示右子樹

return; }}

②利用帶樹求曲線相交

兩個矩形帶段S1和S2的位置關(guān)系有如下三種: (1)不相交。

(2)良性相交,即S1的與起點至終點連線平行的兩條邊都與S2相交,S2的與起點至終點連線平行的兩條邊也都與S1相交。

(3)可能性相交,這時不是良性相交,但也不是不相交。設(shè)表示要求交兩曲線的帶樹己構(gòu)造得足夠精確,即在樹葉一層,來自不同帶樹的矩形帶段或是不相交或是良性相交,而沒有可能性相交出現(xiàn)。兩樹T1和T2表示的兩條曲線是否相交的算法敘述如下:算法：1.若T1和T2對應的矩形帶段互不相交,那么它們代表的曲線不相交;2.若T1和T2對應的矩形帶段良性相交,那么它們代表的曲線相交;3.若T1和T2對應的矩形帶段可能性相交,且T1的面積大于或等于T2的面積,那么分別執(zhí)行T2與T1的左右兩個兒子結(jié)點的相交性檢查。4.若T1的面積小于T2的面積,則把它們位置對換一下再如上進行兩個檢查。4.1.若左右兩個子節(jié)點檢查的結(jié)果都是不相交,則認為所表示曲線不相交;4.2.若左右兩個子節(jié)點檢查中有一個是良性相交,則認為所表示曲線相交;4.3.若不是上述兩情形,即出現(xiàn)可能性相交,則對可能性相交的兩個矩形帶段中面積較大者,取其對應結(jié)點的兩個子結(jié)點,如此進行可直到樹葉那一層。左右子樹都不相交左右子樹有一個相交③

如何確定一點是否在一封閉曲線內(nèi) 從該點引射線與區(qū)域邊界相交的次數(shù)為奇數(shù)，點在區(qū)域內(nèi)，否則點在區(qū)域外。 判別兩曲線相交：一條射線（寬度為0的帶樹，與表示曲線的帶樹求交，交點的個數(shù)即為帶樹良性相交次數(shù)。

良性可能性(良性)可能性(不相交)帶樹法的優(yōu)點：1. 用帶樹法表示曲線對提高計算效率是有幫助的。2.兩個帶樹對并、交等運算是封閉的。3.與用像素陣列來表示圖形的方法相比，節(jié)省空間需求。二.平面圖形的四叉樹表示方法（表示實區(qū)域，不是邊界） 假定一個平面圖形是黑白的二值圖形,即組成圖形像素陣列的僅有黑色像素值1,白色像素值0,設(shè)表現(xiàn)圖形的像素陣列由2n×2n個像素組成。

表示該圖形的四叉樹結(jié)構(gòu)可以如下形成: 1.圖形包含于2n×2n的正方形中，這個正方形是四叉樹的根結(jié)點。

1.1若圖形整個地占據(jù)這個正方形,則圖形就用該正方形表示, 1.2否則將該正方形均分為四個小正方形，每個小正方形邊長為原正方形邊長的一半.它們是根結(jié)點的四個子結(jié)點,可編號為0,1,2,3。

2.每個小正方形

2.1若完全被圖形占據(jù)，則標記相應

結(jié)點為1，稱為黑結(jié)點。

2.2若與圖形完全不相交，則標記相

應結(jié)點為0，稱為白結(jié)點。

2.3若不是上述兩情形，即與圖形部

分相交，稱為灰結(jié)點，并將其一分

為四。

3.當再分生成小正方形邊長達到一個

像素單位時，再分終止，此時一般

應將仍是灰結(jié)點的改為黑結(jié)點，如

此形成了平面圖形的四叉樹表示。TreeCreateQuadtree

(V,C,n)//V是柵格圖形，C是正方形，n表示正方形邊長對應的層次{ if(intersect(V,C,n)==C){ new(P);P->V=1;return(P);//構(gòu)造黑結(jié)點 }elseif(intersect(V,C,n)==NULL){ new(P);P->V=0;returnNULL;//構(gòu)造白結(jié)點 }else//構(gòu)造灰結(jié)點 if(n==1){//正方形邊長為1 new(P);P->V=1;return(P); }else{//正方形邊大于1 new(P);P->V=0.5; C0=C.0;C1=C.1;C2=C.2;C3=C.3;//將正方形邊均分為四塊 P->F0=CreateQuadtree

(V,C0,n-1); P->F1=CreateQuadtree

(V,C1,n-1); P->F2=CreateQuadtree

(V,C2,n-1); P->F3=CreateQuadtree

(V,C3,n-1); return(P); }}V(0/1/0.5)F0F1F2F3四叉樹的存儲方式：即規(guī)則方式、線性方式和一對四方式

1.規(guī)則四叉樹 用五個字段的記錄來表示樹中的每個結(jié)點 一個用來描述結(jié)點的特性，即是灰、黑、白三類結(jié)點中的一種。其余四個用于存放指向四個子結(jié)點的指針。

缺點：大量的存儲空間被指針占用，存儲空間利用率差

2.線性四叉樹 以某一預先確定的次序遍歷四叉樹形成一個線性表結(jié)構(gòu)。

R’A’abcdBCD’efgh。其中R表示根，字母右上角加’表示是灰結(jié)點。 優(yōu)點：節(jié)省存儲空間空間 缺點：靈活性差3.一對四式四叉樹 一對四式四叉樹的存儲結(jié)構(gòu)每個結(jié)點有五個字段，其中四個字段用來描述該結(jié)點的四個子結(jié)點的狀態(tài)，另一個結(jié)點存放指向子結(jié)點記錄存放處的指針。四個子結(jié)點對應的記錄是依次連續(xù)存放的。

改進的一對四式四叉樹(為節(jié)省存貯空間)：a.增加計算量（緊湊的一對四式四叉樹） 存取相應節(jié)點時，先檢查其父節(jié)點，看在它之前有幾個葉節(jié)點b.一個記錄增加一個字節(jié) 該字節(jié)一分為四,每個子結(jié)點對應2位,表示它的子結(jié)點在指針指向區(qū)域中的偏移。01|00|00|00第二節(jié)三維幾何模型

一.幾何元素

形體的模型主要指的就是包含圖形信息所形成的模型。 形體本身的構(gòu)造有一定的層次性，低層部分組合構(gòu)成上一層部分，而上一層部分組合又可以構(gòu)成更高一層的部分，依此類推可形成多層結(jié)構(gòu)。其中，每一層中的部分，稱為幾何元素。(1)點

點是0維幾何元素，有端點、交點、切點、孤立點等形式。 曲線、曲面的應用中會涉及到三種類型的點： 型值點相應曲線、曲面必然經(jīng)過的點。 控制點相應曲線、曲面不一定經(jīng)過的點，僅用于確定位置和形狀。 插值點在型值點之間插入的一系列點，用于提高曲線曲面的輸出精度。

不同的空間中點的表示方式

(1)一維空間中用一元組{t}表示；

(2)二維空間中用二元組{x,y}或{x(t),y(t)}表示；

(3)三維空間中用三元組{x,y,z}或{x(t),y(t),z(t)}表示； 點是幾何造型中的最基本的元素，曲線、曲面和其它形體都可以用有序的點集描述。 用計算機存儲、管理、輸出形體的實質(zhì)就是對點集及其連接關(guān)系的處理。(2)邊 邊是一維幾何元素，是兩個鄰面（正則形體）或多個鄰面（非正則形體）的交界。邊分直線邊和曲線邊。直線邊由起點和終點兩端點確定；曲線邊由一系列型值點或控制點表示，也可以用顯式、隱式方程描述。正則形體：滿足歐拉公式V-E+F=2的形體

(例如立方體V=8,E=12,F=6)。非正則形體：不滿足歐拉公式的形體。存在懸面、懸邊的形體是非正則形體。V=10E=13F=6V=9E=12F=6V=10E=17F=10(3)環(huán) 環(huán)是有序有向邊（直線段或曲線段）組成的面的封閉邊界。環(huán)中的邊不能自相交，相鄰兩條邊共享一個端點。環(huán)有內(nèi)外之分，確定面的最大外邊界的環(huán)稱之為外環(huán)，通常其邊按逆時針方向排序。而把確定面中內(nèi)孔或凸臺邊界的環(huán)稱之為內(nèi)環(huán)，其邊相應外環(huán)排序方向相反，通常按順時針方向排序。(4)面 面是二維幾何元素，是形體上一個有限、非零的區(qū)域，它由一個外環(huán)和若干個內(nèi)環(huán)所界定。面有方向性，一般用其外法向量作為該面的正向。若一個面的外法向量向外，此面為正；否則，為反向面。(5)體 體是三維幾何元素，由封閉表面圍成的空間，它是歐氏空間R3中非空、有界的封閉子集，其邊界是有限面的并集。在實際應用中，要求形體是正則形體，即形體上任意一點的足夠小的鄰域在拓撲上應是一個等價的封閉圓。不滿足上述要求的形體稱為非正則形體。存在懸面、懸邊的形體是非正則形體。(6)體素 體素是可以用有限個尺寸參數(shù)定位和定型的體，常有下面三種定義形式。

一組單元實體長方體、圓柱體、圓錐體、球體。 掃描體由參數(shù)定義的一條（一組）截面輪廓線沿一條（一組）空間參數(shù)曲線作掃描運動而產(chǎn)生的形體。 用代數(shù)半空間定義的形體在此半空間中點集可定義{(x,y,z)|f(x,y,z)≤0}此處的f應是不可約的多項式。 形體的層次結(jié)構(gòu) 點→邊→環(huán)→面→外殼→形體。

掃描體掃描法的基本思想非常簡單：“運動的物體”加上“軌跡”。常用的掃描方式有：平移式、旋轉(zhuǎn)式和廣義式。平移掃描：沿垂直于二維集合進行掃描；旋轉(zhuǎn)掃描：繞某一軸線旋轉(zhuǎn)某一角度；廣義掃描：二維幾何集合沿一條空間曲線的集合掃描；

平移掃描旋轉(zhuǎn)掃描廣義掃描

在幾何造型中最基本的幾何元素是點(V)、邊(E)、面(F),這三種元素一共有九種連接關(guān)系頂點、棱邊、表面之間的拓撲關(guān)系

要用實體的邊界信息表示一個實體，必須同時表示出實體邊界的拓撲和幾何信息。物體的拓撲信息指物體上所有的頂點、棱邊、表面間是怎樣連接的。就多面體而言，其頂點、棱邊、表面之間的連接關(guān)系可以用九種不同的形式予以描述。數(shù)據(jù)結(jié)構(gòu)中保存的拓撲關(guān)系越多，對多面體的操作越方便，但是占用的存儲空間也就越大。因此要根據(jù)實際情況選擇拓撲關(guān)系，以提高系統(tǒng)的整體效率。二.線框、表面及實體表示（多面體的表示）常用的多面體表示法是三表表示法，即采用三個表:

頂點表：頂點坐標,用來存放多面體各頂點的坐標;

邊表：兩個頂點編號表達一條邊,指出哪兩個頂點之間有多面體的邊 面表：邊的編號表示面,指出哪些邊圍成了多面體的表面多面體的表示 線框模型：點表，邊表 表面模型：點表，邊表，面表 實體模型：點表，邊表，面表，其它圖形和非圖形信息 形體確定→三表確定 給出三表→不一定表示一個真實形體(正則形體：V-E+F=2)真實形體應滿足的條件

1.頂點表中的每個頂點至少是三邊的端點; 2.邊表中的每條邊是兩個多邊形面的公共邊；

3.每個多邊形面是封閉的等等。

頂點表面表邊表編號XYZ11002110301040005101611170118001編號起點終點112223334441556667778885915102611371248編號邊1邊2邊3邊4111059221161033127114498125567863214空間正二十面體V20,的三表表示。引入一個正數(shù)Φ>0,它滿足二次方程Φ2-Φ-1=0,因此Φ=1/2(1+)≈1.618034。XYZ編號xyz11Φ0112-Φ0113Φ0-114-Φ0-1211Φ0221-Φ023-1Φ024-1-Φ03101Φ3201-Φ330-1Φ340-1-Φ邊編號邊編號111,131621,33212,141722,32321,231822,34422,241923,31531,332023,32632,342124,33711,212224,34811,222331,11912,232431,121012,242532,131113,212632,141213,222733,111314,232833,121414,242934,131521,313034,14面編號

面編號

17，23，151125，6，2928，17，271230，6，26311，16，251311，1，7429，28，12148，1，1259，19，24159，2，13628，21，101614，2，10726，20，131719，3，15814，22，301816，3，20927，5，231917，4，211024，5，282022，4，18三.三維實體表示方法 從用戶角度來看，形體以特征表示和構(gòu)造的實體幾何表示比較適宜；從計算機對形體的存儲管理和操作運算角度看，以邊界表示最為實用。1.構(gòu)造的實體幾何法 構(gòu)造的實體幾何(CSG:ConstructiveSolidGeometry)法是指任意復雜的形體都可以用簡單形體(體素)的組合來表示。 形體的CSG表示可看成是一棵有序的二叉樹，稱為CSG樹。 終端結(jié)點或是體素，如長方體、圓錐等；或是剛體運動的變換參數(shù)，如平移參數(shù)Tx等； 非終端結(jié)點或是正則的集合運算，一般有交、并、差運算；或是剛體的幾何變換，如平移、旋轉(zhuǎn)等。

采用BNF范式可定義CSG樹如下：

<CSG>::=<體素葉子>| <CSG樹><正則集合運算><CSG樹>| <CSG樹><剛體運動><剛體運動變量> CSG樹是無二義性的，但不是唯一的，其定義域取決于所用體素以及所允許的幾何變換和正則集合運算算子。

CSG樹一個復雜物體可由一些比較簡單、規(guī)則的物體經(jīng)過布爾運算而得到。因而，這個復雜的物體可描述為一棵樹。這棵樹的終端結(jié)點為基本體素(如立方體、圓柱、圓錐)，而中間結(jié)點為正則集合運算結(jié)點。這棵樹叫做CSG樹。

U－CSG樹CSG表示的優(yōu)點：數(shù)據(jù)結(jié)構(gòu)比較簡單，數(shù)據(jù)量比較小，內(nèi)部數(shù)據(jù)的管理比較容易；每個CSG表示都和一個實際的有效形體所對應；CSG表示可方便地轉(zhuǎn)換成Brep表示，從而可支持廣泛的應用；比較容易修改CSG表示形體的形狀。CSG表示的缺點：產(chǎn)生和修改形體的操作種類有限，基于集合運算對形體的局部操作不易實現(xiàn)；由于形體的邊界幾何元素(點、邊、面)是隱含地表示在CSG中，故顯示與繪制CSG表示的形體需要較長的時間。2特征表示 特征表示是從應用層來定義形體，因而可以較好地表達設(shè)計者的意圖，為制造和檢驗產(chǎn)品和形體提供技術(shù)依據(jù)和管理信息。從功能上看可分為形狀、精度、材料和技術(shù)特征。

特征造型器幾何造型器特征模型幾何模型用戶應用系統(tǒng)基于特征的造型系統(tǒng)WLHHRHR（a）方塊（b）圓柱（c）圓錐特征形狀表示2特征表示 形狀特征：體素、孔、槽、鍵等 精度特征：形位公差、表面粗糙度等； 材料特征：材料硬度、熱處理方法等； 技術(shù)特征：形體的性能參數(shù)和特征等。 形狀特征單元是一個有形的幾何實體，是一組可加工表面的集合。如采用長、寬、高三尺寸表示的長方體；采用底面半徑及高度表示的圓柱體均是可選用的形狀特征單元。形狀特征單元的BNF范式可定義如下：<形狀特征單元>::=<體素>| <形狀特征單元><集合運算><形狀特征單元>| <體素><集合運算><體素>| <體素><集合運算><形狀特征單元>| <形狀特征單元><集合運算><形狀特征過渡單元>;<體素>::=長方體|圓柱體|球體|圓錐體|棱錐體|棱柱體|棱臺體|圓環(huán)體|楔形體|圓角體|…；<集合運算>::=并|交|差|縮放；<形狀特征過渡單元>::=外圓角|內(nèi)圓角|倒角。特征表示

特征造型器幾何造型器特征模型幾何模型用戶應用系統(tǒng)基于特征的造型系統(tǒng)WLHHRHR（a）方塊（b）圓柱（c）圓錐特征形狀表示3邊界表示 邊界表示詳細記錄了構(gòu)成形體的所有幾何元素的幾何信息及其相互連接關(guān)系—拓撲關(guān)系，便于直接存取構(gòu)成形體的各個面、面的邊界以及各個頂點的定義參數(shù)，有利于以面、邊、點為基礎(chǔ)的各種幾何運算和操作。 形體的邊界表示就是用面、環(huán)、邊、點來定義形體的位置和形狀。例如，一個長方體由六個面圍成，對應有六個環(huán)，每個環(huán)由四條邊界定義，每條邊又由兩個端點定義。而圓柱體則由上頂面、下底面和圓柱面所圍成，對應有上頂面圓環(huán)、下底面圓環(huán)。

邊界表示法（B－rep）三維物體可以通過描述它的邊界來表示。Brep表示的優(yōu)點是：表示形體的點、邊、面等幾何元素是顯式表示的，使得繪制Brep表示形體的速度較快，而且比較容易確定幾何元素間的連接關(guān)系；對形體的Brep表示可有多種操作和運算。Brep表示的缺點是：數(shù)據(jù)結(jié)構(gòu)復雜，需要大量的存儲空間，維護內(nèi)部數(shù)據(jù)結(jié)構(gòu)的程序比較復雜；修改形體的操作比較難以實現(xiàn)；Brep表示并不一定對應一個有效形體，即需要有專門的程序來保證Brep表示形體的有效性、正則性等。四.八叉樹 假設(shè)要表示的形體V可以放在一個充分大的正立方體C內(nèi),C的邊長為2n,形體VC,它的八又樹表示可以遞歸定義為:

八叉樹每個結(jié)點與C的一個子立方體對應，樹根就和C本身對應。如果V=C,那么V八叉樹僅有樹根。如果V≠C,則將C均分為八個子立方體,每個子立方體對應根結(jié)點的一個子結(jié)點。只要某個子立方體不是完全空白或完全被V所占據(jù),它就要被八等分,從而它對應的結(jié)點也有了八個子結(jié)點。這樣的遞歸判斷及可能分割一直進行,直到結(jié)點對應的立方體或完全空白,或完全被占據(jù),或其大小已是預先規(guī)定的體素大小.TreeCreateOctree

(V,C,n)//V是形體，C是立方形，n表示正方形邊長對應的層次{ if(intersect(V,C,n)==C){ new(P);P->V=1;return(P);//構(gòu)造黑結(jié)點 }elseif(intersect(V,C,n)==NULL){ P->V=0;returnNULL;//構(gòu)造白結(jié)點 }else//構(gòu)造灰結(jié)點 if(n==1){//正方形邊長為1 new(P);P->V=1;return(P); }else{//正方形邊大于1 new(P);P->V=0.5; C0=C.0;C1=C.1;C2=C.2;C3=C.3;//將立方體均分為八塊 C4=C.4;C5=C.5;C6=C.6;C7=C.7; P->F0=CreateOctree

(V,C0,n-1); P->F1=CreateOctree

(V,C1,n-1); P->F2=CreateOctree

(V,C2,n-1); P->F3=CreateOctree

(V,C3,n-1); P->F4=CreateOctree

(V,C4,n-1); P->F5=CreateOctree

(V,C5,n-1); P->F6=CreateOctree

(V,C6,n-1); P->F7=CreateOctree

(V,C7,n-1); return(P); }}

這時對它與V之交作一定的“舍入”,使體素或認為是空白,或認為是被V占據(jù)的。這里所謂的體素,就是指被分割后得到的小立方體。

對應立方體被形體V完全占據(jù)的結(jié)點為黑結(jié)點,

完全不占據(jù)的為白結(jié)點,

部分被占據(jù)的為灰結(jié)點。

存貯結(jié)構(gòu),有常規(guī)的、線性的、一對八式的八叉樹等等。 優(yōu)點：

1.占用存儲空間少

2.便于形體的交并差的集合運算

3.可以顯式不同精度的實體，消隱便于實現(xiàn)八叉樹表示的三維形體的幾何變換1.比例變換2.旋轉(zhuǎn)變換相對通過原點的一條任意方向的直線做任意角度的旋轉(zhuǎn)變換。多次變換誤差會積累，解決方法

第一項措施是保持一個原始的八叉樹做為參考的源樹。設(shè)指定了一次變換R1,接著又要做變換R2,可以計算出復合變換R=R1·R2,然后對原始的八叉樹做一次變換。這樣來避免誤差的積累。

多次變換誤差會積累，解決方法

第二項措施是為了盡量減少“舍入”誤差,可以規(guī)定一個當前正要重建的八叉樹,如果它的最底層葉結(jié)點對應的體素是部分地為顯示對象所占據(jù)，那么當且僅當這個體素的中心位于某個黑變換后立方體內(nèi)時,這個體素才被規(guī)定為黑,否則就規(guī)定為白。這樣規(guī)定使得一般不會產(chǎn)生原來不存在的孔洞，避免在變換后形體中間出現(xiàn)斷裂。

設(shè)己采取了上述兩項措施,已知形體變換前的八叉樹表示T1,己計算出 要做的復合變換R,要確定變換后形體的八叉樹表示T2,可以寫出如下的算法框架：

1.遍歷形體原來的八叉樹T1,對遇到的每個黑結(jié)點,做下述步2。

2.對遇到黑結(jié)點對應的正立方體做相應變換,得它新的一般來說是斜置的新位置。若這位置已超出定義八叉樹的充分大正立方體C之外,報告出錯;否則執(zhí)行下述的步3。

3.從要計算求出的目標樹T2的根開始,檢查2中確定的處于新位置立方體與T2中結(jié)點對應的直立的正立方體是否相交,分以下三種情況進行處理: (1)不相交,說明正考查直立正立方體未被占據(jù),可保持為白結(jié)點,不做處理。

(2)直立的正立方體整個被占據(jù),即它在變換后"斜置"立方體內(nèi),置對應結(jié)點為黑結(jié)點。

(3)在上述兩條均不成立時,生成當前結(jié)點的八個子結(jié)點,對八個子結(jié)點對應的八個直立子立方體,依次再遞歸執(zhí)行步3。如果最終這八個結(jié)點被標上同樣特性,例如為黑結(jié)點,則應再刪掉這八個子結(jié)點而把它們的共同父結(jié)點置為黑。 算法中,主要工作是檢查某個直立的正立方體與一個斜置的正立方體是否相交。對所有黑結(jié)點對應正立方體處理相同,使得操作可以并行進行。設(shè)已采取了上述兩項措施,已知形體變換前的八叉樹表示T1,已計算出要做的復合變換R,要確定變換后形體的八叉樹表示T2。CCT1T2T1CC(a)(b)算法框架：for(遍歷原形體八叉樹上的每個黑結(jié)點,記為T1){

變換黑結(jié)點T1對應的立方體,得到新位置; if(新位置超出定義八叉樹的立方體C之外){報告出錯;continue;} T2=C的根結(jié)點; { while(T2被T1部分占據(jù)&&T2>預定義的最小體素) {生成結(jié)點T2的八個子結(jié)點;T2=第一個子結(jié)點;} if(T2和T1不相交)T2屬性=白結(jié)點; elseif(T2被T1完全占據(jù))T2屬性=黑結(jié)點; //T2被T1部分占據(jù)&&T2=預定義的最小體素

elseif(T1占據(jù)結(jié)點T2對應的立方體的中心)T2屬性=黑結(jié)點; elseT2屬性=白結(jié)點; while(T2無后續(xù)兄弟結(jié)點&&T2!=C的根結(jié)點){ T2=T2的父結(jié)點; if(T2的八個子結(jié)點被標上同樣屬性) {T2=子結(jié)點屬性;刪除T2的八個子結(jié)點;} } if(T2有后續(xù)兄弟結(jié)點)T2=下一個后續(xù)兄弟結(jié)點; }while(T2!=C的根結(jié)點)T2線性八叉樹 在對立方體做八等分時,按一致的方式,對分出的子立方體進行編號。若劃分共進行n層，則每個結(jié)點可以用n位的八進制數(shù)的數(shù)串來表示,數(shù)串從左至右,第一位對應第一次劃分，第二位對應第二次劃分，依此類推。據(jù)此整個八叉樹就可以根據(jù)對其做深度優(yōu)先遍歷而依次列出的黑結(jié)點的編號序列來表示。

上圖所示三維形體,其線性八叉樹表示是: {0x,10,12,13,14,2x,4x,6x,7x}0x101213142x4x6x7x求并運算C1∪C2

兩棵線性八叉樹:C1={122,123,301,302,303,305,307}C2={12x,300,302,304,306}

將C2的各結(jié)點依次插入到C1的適當位置,使插入后編號漸增這一性質(zhì)保持不變。當C2(C1)中結(jié)點可以包含C1(C2)中若干結(jié)點時,則取而代之。另外,如果插入后可以進行結(jié)點"壓縮",也應該立即進行:C1∪C2={12x,300,301,302,303,304,305,306,307}={12x,30x}

八叉樹表示形體的顯示 當觀察位置是x1>0,y1<0,z1>0時,最可能被遮擋看不見的是編號2的子立方體,全部依次排出可以是26034715

z1

y1

x1

優(yōu)先級<0<0<073561240<0<0>037125604<0>0<051743062<0>0>015307426>0<0<062470351>0<0>026034715>0>0<040652173>0>0>004216537zl>0,y1<0,x1>0優(yōu)先級26034715。下圖表示形體的線性八叉樹{0x,10,12,13,14,2x,4x,6x,7x}按結(jié)點應顯示次序排出的序列就是:{2x,6x,0x,4x,7x,12,10,13,14}0x101213142x4x6x7x第三節(jié)分形

一.分形的概念 三分康托(Cantor)集 設(shè)E0是閉區(qū)間[0,1],即E0是滿足0≤x≤1的實數(shù)x組成的點集;E1是E0去掉中間1/3之后的點集,即E1是兩個閉區(qū)間[0，1/3]和[1/3，2/3];E2是分別去掉E1中兩個區(qū)間的中間1/3之后的點集,即E2已經(jīng)是四個閉區(qū)間。此過程要繼續(xù)進行,Ek是2k個長度為1/3k的閉區(qū)間組成的點集。三分康托集F是屬于所有的Ek的點組成的集,即。

F可以看成是集序列Ek當k趨于無窮時的極限。只能畫出k取定時的某個Ek。當k充分大時,Ek是對F的很好的近似的表現(xiàn)。

三分康托集是區(qū)間[0,1]中的可以展成以3為底的幕級數(shù)的下面形式的數(shù)組成的: a13-1+a23-2+a33-3…

其中ai的取值限制為0或2,不取1。為看清這一事實,注意從E0得到E1時,去掉的是ai=1的數(shù),從E1得E2時,去掉的是a2=1的數(shù),并以此類推。

三分康托集具有的一些值得注意的特征,這些特征對許多其它的分形也是大體上適合的。(1)F是自相似的。E1的兩個區(qū)間[0，1/3]，[1/3，2/3]的每一個,其內(nèi)部F的部分與F整體相似,相似比為1/3。(2)F具有“精細結(jié)構(gòu)”，即它包含有任意小比例的細節(jié)。(3)F的實際定義是簡單的和明確的。(4)傳統(tǒng)的幾何學很難描述F的性質(zhì),因為F不是滿足某些簡單條件的點的軌跡,也不是任何簡單的方程的解的集合。(5)F的局部幾何性質(zhì)也很難描述,在它的每點附近都有大量被各種不同間隔分開的其它點。(6)按傳統(tǒng)幾何學中的長度概念,F的長度為零。就是說,盡管從不可數(shù)集合這點上說F是一個相當大的集,但它卻沒有長度,或者說長度不能對F的形狀或大小提供有意義的描述。vonKoch曲線稱集合F是分形,即認為它具有下面典型的性質(zhì):(1)F具有精細的結(jié)構(gòu)，即有任意小比例的細節(jié)。(2)F是如此的不規(guī)則以至它的整體和局部都不能用傳統(tǒng)的幾何語言來描述。(3)F具有某種自相似的形式,可能是近似的或是統(tǒng)計的。(4)一般地,F的"分形維數(shù)"大于它的拓撲維數(shù)。(5)在大多數(shù)令人感興趣的情形下,F以非常簡單的方法定義,可能由迭代產(chǎn)生。

Hausdorff維數(shù) 考慮一個簡單的幾何圖形,取一個邊長為1的正方形,若每邊擴大2倍,則正方形面積放大4倍,其數(shù)學表達式為22=4,這是2維圖形。對3維圖形,如考慮邊長為1的立方體,令每邊長放大2倍,則立方體體積擴大8倍,其數(shù)學表達式為23=8。 類似地,對一個Df維的幾何對象,若每邊長擴大L倍,則這個幾何對象相應地放大K倍,歸納前述結(jié)果,Df,L,K三者間的關(guān)系式應為:

LDf=K

解出Df,有:

Df=lnK/lnL

這里Df不必是整數(shù)。這就是Hausdorff引人的維數(shù)概念,可以稱為Hausdorff維數(shù)(相似性維數(shù))。

假定有一個單位正方形,把它每邊三等分得九個小的正方形,九個小正方形面積總和是原單位正方形面積,即9×(1/3)2=1?，F(xiàn)在我們把Df維的幾何對象等分為N個小的幾何圖形,則每個小圖形每維縮小為原來的r倍,而N個小圖形的總和應有N·rDf=1。這時解出DF,有:

容易看出式(1)和(2)本質(zhì)上是相同的,即這樣引入的也是Hausdorff維數(shù) vonKoch曲線,每次分為4個小圖形,每個小圖形縮小1/3倍,故其Hausdorff維數(shù)為DF

：二、分形一般算法規(guī)則分形的生成算法。對算法的輸入是事先給定的一個整數(shù)k、源形E0及生成規(guī)則,算法操作步驟如下:voidFractal(RuleR,intk,SourceE0,intm){ /*R分形規(guī)則k分形迭代層數(shù)m分形組成數(shù)E0源形*/ //i記層數(shù)j記生成部分圖形的數(shù)目隊列Q保存圖形A0記源形 i=0;j=1;Q=φ;A0=E0;

do{ do{ //由A0和R計算它的m個分解部分; calculate(A0,R,A1,A2,…,Am); draw(Al,A2,…,Am);//圖形繪制

//生成各部分圖形依次加到隊尾

insert(A1,A2,…,Am,Q);

A0=delete(Q);//從隊頭取出一個部分圖形

j=j+1; }while(j<=m^i); j=1;i++;//進入下一層

}while(i<=k);//結(jié)束判斷}

例如：vonKoch曲線 其源形E0可以是一條線段,記其端點坐標為P0,P1。 在算法步1,應令A0=E0=(Po,Pl),

在算法步2,需要依據(jù)Po,Pl,計算圖中P2,P3,P4三點的坐標。這樣m=4,分別得到四個部分圖形是A1=(P0,P2),A2=(P2,P3),A3=(P3,P4),A4=(P4,P1)。 在算法步3,可畫出四條線段P0P2,P2P3,P3P4,P4P1,擦去前次畫線時可能畫出的P2P4部分。三、VonKoch算法 利用自相似變換來繪制分形 設(shè)D是歐氏空間Rn的閉子集,映射S:D→D稱為是D上的壓縮，如果對所有D上的點x,y,存在一個數(shù)c,0<c<1,能使|S(x)-S(y)|≤c|x-y|。如果其中等號成立,即若|S(x)-S(y)|=c|x-y|,則S把一個集變成了它的幾何相似集,此時映射S稱為是相似的。 設(shè)S1,…,Sn是壓縮,稱D的子集F對變換S1,…,Sn是不變的,如果

三分康托集的情形,這時令S1,S2是R→R的變換,分別由 P0和P1的坐標是(0,0)和(1,0),則可以計算求出P2,P3,P4的坐標是

自相似變換S1和S2是平面變換,可一般地設(shè)變換矩陣為:

第一個變換S1把點P0,P1,P3,依次變到Po,P3,P2,這就得到:于是有

第二個變換S2把點P0,P1,P3,依次變到P3,P1,P4，這就得到：于是有因此繪制VonKoch曲線voidvon_Koch_display(void){ x1=0;y1=0;s=1;u=1;//(x1,y1)為初始點

do{ x2=1/2.0*x1+sqrt(3)/6*y1;y2=sqrt(3)/6*x1-1/2.0*y1; x3=1/2.0*x1+sqrt(3)/6*y1+1/2.0;//變換

y3=-sqrt(3)/6*x1-1/2.0*y1+sqrt(3)/6; Setpixel(x2,y2,RGB(0,0,0));//畫點

Setpixel((x3,y3),RGB(0,0,0)); Ps.x=x2;Ps.y=y2;Ps+1.x=x3; Ps+1.y=y3;s=s+2;//〔存貯〕 x1=Pu.x;y1=Pu.y;u++;//〔準備下次〕 }while(u<=k);//〔結(jié)束判斷〕}

上面的變換能產(chǎn)生很緊松樹樹枝的圖象。四.Julia和Mandelbrot集 設(shè)有復數(shù)域上如下形式的二次函數(shù):f(z)=z2+c

其中c是復數(shù)值常數(shù),做迭代操作: zn+1=zn2+c,n=0,1,2,…

研究的問題是: 1.給定z0,當參數(shù)c在什么范圍內(nèi)取值能保證|zn|有界

2.當c給定,如何選取z0,使|zn|有界?

上述迭代,當c=0時,可以有以下三種情況: 1.序列中的數(shù)按模來說越來越小,且趨于零。這時說零是z→z2的吸引子。所有與坐標原點相距小于1的點都產(chǎn)生趨向零的序列。

2.序列中的數(shù)按模來說越來越大,且趨向無窮,這時"無窮"也稱為過程的吸引子。與坐標原點的距離超過1的所有點都產(chǎn)生趨向無窮的序列; 3.距坐標原點為1的點,序列總是產(chǎn)生在上面兩個吸引區(qū)域之間的邊界上,此時邊界恰為復平面上的單位圓周。 對于上述迭代,當c≠0時,吸引子不再是零,吸引區(qū)域的邊界不再是光滑的,而是具有自似形的分形結(jié)構(gòu),這種邊界稱為Julia集。

在復平面上，使z→z2+c的迭代過程成為有界的復參數(shù)c的集合叫做Mandelbrot。設(shè)復平面上的迭代過程是: zk+1=zk2+c

分離實部和虛部,記zk=xk+yki,c=p+qi,有

設(shè)計算機顯示屏幕的圖形分辨率是a×b點,可顯示顏色是k+1種,以數(shù)字0到k表示,0表示黑色。取定p和q的值,考慮平面上每一點(x,y),探討吸引區(qū)域的結(jié)構(gòu)及其邊界即Julia集。Julia集a=600,b=400,M=100,K=100,p=-0.605,q=-0.43,-1.5≤x≤1.5,-1.5≤y≤1.5,voidJulia(inta,intb,intK,intM,doublep,doubleq){ doublex