形體的表示及其數(shù)據(jù)結(jié)構(gòu)

形體的表示及其數(shù)據(jù)結(jié)構(gòu)第一頁(yè)，共七十八頁(yè)，編輯于2023年，星期六第一節(jié)二維形體的表示二維圖形的邊界表示

折線法和帶樹(shù)法

折線法就是用多段線段形成的折線去逼近曲線折線表示曲線應(yīng)該解決的關(guān)鍵問(wèn)題是:如何恰當(dāng)?shù)卮_定曲線上一系列點(diǎn),使之在某些判定準(zhǔn)則下達(dá)到最優(yōu)。第二頁(yè)，共七十八頁(yè)，編輯于2023年，星期六帶樹(shù)法

帶樹(shù)是一棵二叉樹(shù),樹(shù)的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)矩形帶段,這樣每個(gè)結(jié)點(diǎn)可由八個(gè)字段組成,前六個(gè)字段描述矩形帶段,后二個(gè)是指向兩個(gè)子結(jié)點(diǎn)的指針,即矩形帶段的起點(diǎn)是(xb,yb),終點(diǎn)是(xe,ye)。相對(duì)從起點(diǎn)到終點(diǎn)的連線,矩形有兩邊與之平行,兩邊與之垂直,平行兩邊與之距離分別為wl和wr。第三頁(yè)，共七十八頁(yè)，編輯于2023年，星期六第四頁(yè)，共七十八頁(yè)，編輯于2023年，星期六

設(shè)要表示的曲線是由經(jīng)過(guò)適當(dāng)選取已確定的一組離散點(diǎn)P0,P1,…,Pn序列給出,則生成表示曲線的分辨率為w0的帶樹(shù)的算法,可簡(jiǎn)略描述如下:1.找出由起點(diǎn)P0,終點(diǎn)Pn確定的矩形帶段,其中包含P0至Pn的全部點(diǎn),構(gòu)造此矩形帶段的對(duì)應(yīng)結(jié)點(diǎn)并令為根。2.找出P0至Pn之間距離連線P0Pn為最遠(yuǎn)的點(diǎn)Pk,然后對(duì)P0至Pk和Pk至Pn這兩組點(diǎn)分別做與步1中相同的構(gòu)造矩形帶段及對(duì)應(yīng)結(jié)點(diǎn)的操作,產(chǎn)生的兩個(gè)結(jié)點(diǎn),分別是根的左右子結(jié)點(diǎn)。3.反復(fù)執(zhí)行上述操作,直到所產(chǎn)生結(jié)點(diǎn)的w=wl+wr≤w0。這樣的結(jié)點(diǎn)是葉結(jié)點(diǎn)。第五頁(yè)，共七十八頁(yè)，編輯于2023年，星期六

設(shè)表示曲線有5個(gè)點(diǎn)(3,7)(9,12),(15,4),(18,5),(20,7),取分辨率w0=1,則上述算法構(gòu)造的帶樹(shù)第六頁(yè)，共七十八頁(yè)，編輯于2023年，星期六

以不同的分辨率顯示用帶樹(shù)表示的曲線

設(shè)給出允許的分辨率為w*,表示曲線的帶樹(shù)的分辨率為w0,并設(shè)w0≤w*,則顯示算法可簡(jiǎn)略描述如下:

從根結(jié)點(diǎn)開(kāi)始,若當(dāng)前正考查結(jié)點(diǎn)的W=wl+wr≤w*,則顯示該結(jié)點(diǎn)對(duì)應(yīng)的矩形帶段;若不然,即W>w*則轉(zhuǎn)去分別考查該結(jié)點(diǎn)的左右兩個(gè)子結(jié)點(diǎn),對(duì)子結(jié)點(diǎn)做同樣的處理。左右子結(jié)點(diǎn)都被顯示的結(jié)點(diǎn)就認(rèn)為是被顯示了,按此看法,顯示帶樹(shù)表示的曲線就是顯示帶樹(shù)的結(jié)點(diǎn)。

第七頁(yè)，共七十八頁(yè)，編輯于2023年，星期六

帶樹(shù)表示的曲線求交

兩個(gè)矩形帶段S1和S2的位置關(guān)系有如下三種:(1)不相交。(2)良性相交,即S1的與起點(diǎn)至終點(diǎn)連線平行的兩條邊都與S2相交,S2的與起點(diǎn)至終點(diǎn)連線平行的兩條邊也都與S1相交。(3)可能性相交,這時(shí)不是良性相交,但也不是不相交。第八頁(yè)，共七十八頁(yè)，編輯于2023年，星期六第九頁(yè)，共七十八頁(yè)，編輯于2023年，星期六

設(shè)表示要求交兩曲線的帶樹(shù)己構(gòu)造得足夠精確,即在樹(shù)葉一層,來(lái)自不同帶樹(shù)的矩形帶段或是不相交或是良性相交,而沒(méi)有可能性相交出現(xiàn)。兩樹(shù)T1和T2表示的兩條曲線是否相交的算法,可以簡(jiǎn)略敘述如下:

若T1和T2對(duì)應(yīng)的矩形帶段互不相交,那么它們代表的曲線不相交;

若T1和T2對(duì)應(yīng)的矩形帶段良性相交,那么它們代表的曲線相交;

若T1和T2對(duì)應(yīng)的矩形帶段可能性相交,且T1的面積大于或等T2的面積,那么分別執(zhí)行T2與T1的左右兩個(gè)兒子結(jié)點(diǎn)的相交性檢查。第十頁(yè)，共七十八頁(yè)，編輯于2023年，星期六

若T1的面積小于T2的面積,則把它們位置對(duì)換一下再如上進(jìn)行兩個(gè)檢查。若兩個(gè)檢查的結(jié)果都是不相交,則認(rèn)為所表示曲線不相交;若兩個(gè)檢查中有一個(gè)是良性相交,則認(rèn)為所表示曲線相交;若不是上述兩情形,即出現(xiàn)可能性相交,則對(duì)可能性相交的兩個(gè)矩形帶段中面積較大者,取其對(duì)應(yīng)結(jié)點(diǎn)的兩個(gè)子結(jié)點(diǎn),如此進(jìn)行可直到樹(shù)葉那一層。

實(shí)踐表明用帶樹(shù)方法表示曲線對(duì)提高計(jì)算效率是有幫助的。另外兩個(gè)帶樹(shù)對(duì)并、交等運(yùn)算是封閉的,與用象素陣列來(lái)表示圖形的方法比較空間需求也算是節(jié)省的。第十一頁(yè)，共七十八頁(yè)，編輯于2023年，星期六平面圖形的四叉樹(shù)表示方法假定一個(gè)平面圖形是黑白的二值圖形,即組成圖形象素陣列的僅有黑色象素值1,白色象素值0,設(shè)表現(xiàn)圖形的象素陣列由2n×2n個(gè)象素組成。表示該圖形的四叉樹(shù)結(jié)構(gòu)可以如下形成:圖形顯然包括2n×2n的正方形中，這個(gè)正方形是四叉樹(shù)的根結(jié)點(diǎn)。若圖形整個(gè)地占據(jù)這個(gè)正方形,則圖形就用該正方形表示,否則將該正方形均分為四個(gè)小正方形，每個(gè)小正方形邊長(zhǎng)為原正方形邊長(zhǎng)的一半.它們是根結(jié)點(diǎn)的四個(gè)子結(jié)點(diǎn),可編號(hào)為0,1,2,3。第十二頁(yè)，共七十八頁(yè)，編輯于2023年，星期六

再考查每個(gè)小正方形,若整個(gè)被圖形占據(jù),則標(biāo)記相應(yīng)結(jié)點(diǎn)為1,可稱(chēng)為黑結(jié)點(diǎn)。若整個(gè)與圖形不相交,則標(biāo)記相應(yīng)結(jié)點(diǎn)為0，可稱(chēng)為白結(jié)點(diǎn)。若不是上述兩情形，即與圖形部分相交，則稱(chēng)相應(yīng)結(jié)點(diǎn)是灰結(jié)點(diǎn)并將其一分為四。當(dāng)再分生成小正方形邊長(zhǎng)達(dá)到一個(gè)象素單位時(shí)，再分終止，此時(shí)一般應(yīng)將仍是灰結(jié)點(diǎn)的改為黑結(jié)點(diǎn)，如此形成了平面圖形的四叉樹(shù)表示

第十三頁(yè)，共七十八頁(yè)，編輯于2023年，星期六第十四頁(yè)，共七十八頁(yè)，編輯于2023年，星期六

四叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，即規(guī)則方式、線性方式和一對(duì)四方式，相應(yīng)的四叉樹(shù)也就稱(chēng)為規(guī)則四叉樹(shù)、線性四叉樹(shù)和一對(duì)四式四叉樹(shù)。規(guī)則四叉樹(shù)是用五個(gè)字段的記錄來(lái)表示樹(shù)中的每個(gè)結(jié)點(diǎn)，其中一個(gè)用來(lái)描述結(jié)點(diǎn)的特性，即是灰、黑、白三類(lèi)結(jié)點(diǎn)中的哪一種。其余四個(gè)用于存放指向四個(gè)子結(jié)點(diǎn)的指針。線性四叉樹(shù)以某一預(yù)先確定的次序遍歷四叉樹(shù)形成一個(gè)線性表結(jié)構(gòu)。

RA’abcdBCD’efgh。其中R表示根，字母右上角加’表示是灰結(jié)點(diǎn)。第十五頁(yè)，共七十八頁(yè)，編輯于2023年，星期六

一對(duì)四式四叉樹(shù)的存儲(chǔ)結(jié)構(gòu)每個(gè)結(jié)點(diǎn)有五個(gè)字段，其中四個(gè)字段用來(lái)描述該結(jié)點(diǎn)的四個(gè)子結(jié)點(diǎn)的狀態(tài)，另一個(gè)結(jié)點(diǎn)存放指向子結(jié)點(diǎn)記錄存放處的指針。四個(gè)子結(jié)點(diǎn)對(duì)應(yīng)的記錄是依次連續(xù)存放的。

第十六頁(yè)，共七十八頁(yè)，編輯于2023年，星期六

為節(jié)省存貯空間,有兩個(gè)途徑可以采取。一個(gè)是增加計(jì)算量；另一個(gè)途徑是在記錄中再增加一個(gè)字節(jié),一分為四,每個(gè)子結(jié)點(diǎn)對(duì)應(yīng)2位,表示它的子結(jié)點(diǎn)在指針指向區(qū)域中的偏移。

第十七頁(yè)，共七十八頁(yè)，編輯于2023年，星期六第二節(jié)三維幾何模型

幾何元素

形體的模型主要指的就是包含圖形信息所形成的模型。形體本身的構(gòu)造有一定的層次性，低層部分組合構(gòu)成上一層部分，而上一層部分組合又可以構(gòu)成更高一層的部分，依此類(lèi)推可形成多層結(jié)構(gòu)。其中，每一層中的部分，我們把它有稱(chēng)為幾何元素。第十八頁(yè)，共七十八頁(yè)，編輯于2023年，星期六點(diǎn)

它是0維幾何元素，有端點(diǎn)、交點(diǎn)、切點(diǎn)、孤立點(diǎn)等形式。曲線、曲面的應(yīng)用中會(huì)涉及到三種類(lèi)型的點(diǎn)：型值點(diǎn)相應(yīng)曲線、曲面必然經(jīng)過(guò)的點(diǎn)?？刂泣c(diǎn)相應(yīng)曲線、曲面不一定經(jīng)過(guò)的點(diǎn)，僅用于確定位置和形狀。插值點(diǎn)在型值點(diǎn)之間插入的一系列點(diǎn)，用于提高曲線曲面的輸出精度。

第十九頁(yè)，共七十八頁(yè)，編輯于2023年，星期六

不同的空間中點(diǎn)的表示方式一維空間中用一元組{t}表示；二維空間中用二元組{x,y}或{x(t),y(t)}表示；三維空間中用三元組{x,y,z}或{x(t),y(t),z(t)}表示；點(diǎn)是幾何造型中的最基本的元素，曲線、曲面和其它形體都可以用有序的點(diǎn)集描述。用計(jì)算機(jī)存儲(chǔ)、管理、輸出形體的實(shí)質(zhì)就是對(duì)點(diǎn)集及其連接關(guān)系的處理。第二十頁(yè)，共七十八頁(yè)，編輯于2023年，星期六邊邊是一維幾何元素，是兩個(gè)鄰面（正則形體）或多個(gè)鄰面（非正則形體）的交界。邊分直線邊和曲線邊。直線邊由起點(diǎn)和終點(diǎn)兩端點(diǎn)確定；曲線邊由一系列型值點(diǎn)或控制點(diǎn)表示，也可以用顯示、隱式方程描述。環(huán)環(huán)是有序有向邊（直線段或曲線段）組成的面的封閉邊界。環(huán)中的邊不能相交，相鄰兩條邊共享一個(gè)端點(diǎn)。環(huán)有內(nèi)外之分，確定面的最大外邊界的環(huán)稱(chēng)之為外環(huán)，通常其邊按逆時(shí)針?lè)较蚺判?。而把確定面中內(nèi)孔或凸臺(tái)邊界的環(huán)稱(chēng)之為內(nèi)環(huán)，其邊相應(yīng)外環(huán)排序方向相反，通常按順時(shí)針?lè)较蚺判颉５诙豁?yè)，共七十八頁(yè)，編輯于2023年，星期六面面是二維元素，是形體上一個(gè)有限、非零的區(qū)域，它由一個(gè)外環(huán)和若干個(gè)內(nèi)環(huán)所界定。面有方向性，一般用其外法向量作為該面的正向。若一個(gè)面的外法向量向外，此面為正；否則，為反向面。體體是三維幾何元素，由封閉表面圍成的空間，它是歐氏空間R3中非空、有界的封閉子集，其邊界是有限面的并集。在實(shí)際應(yīng)用中，要求形體是正則形體，即形體上任意一點(diǎn)的足夠小的鄰域在拓?fù)渖蠎?yīng)是一個(gè)等價(jià)的封閉圓。不滿足上述要求的形體稱(chēng)為非正則形體。存在懸面、懸邊的形體是非正則形體。第二十二頁(yè)，共七十八頁(yè)，編輯于2023年，星期六體素體素是可以用有限個(gè)尺寸參數(shù)定位和定型的體，常有下面三種定義形式。一組單元實(shí)體長(zhǎng)方體、圓柱體、圓錐體、球體。掃描體由參數(shù)定義的一條（一組）截面輪廓線沿一條（一組）空間參數(shù)曲線作掃描運(yùn)動(dòng)而產(chǎn)生的形體。用代數(shù)半空間定義的形體，在此半空間中點(diǎn)集可定義{(x,y,z)|f(x,y,z)0}此處的f應(yīng)是不可約的多項(xiàng)式。形體的層次結(jié)構(gòu)點(diǎn)→邊→環(huán)→面→外殼→形體。

第二十三頁(yè)，共七十八頁(yè)，編輯于2023年，星期六

在幾何造型中最基本的幾何元素是點(diǎn)（V）、邊(E)、面(F),這三種元素一共有九種連接關(guān)系第二十四頁(yè)，共七十八頁(yè)，編輯于2023年，星期六線框、表面及實(shí)體表示常用的多面體表示法是三表表示法，即采用三個(gè)表:頂點(diǎn)表,用來(lái)存放多面體各頂點(diǎn)的坐標(biāo);邊表,指出哪兩個(gè)頂點(diǎn)之間有多面體的邊；面表，指出哪些邊圍成了多面體的表面。任意多面體容易得到它的三表表示,但任意三張表卻不一定表示了一個(gè)真實(shí)的多面體。這里必須滿足的條件至少有以下幾項(xiàng):頂點(diǎn)表中的每個(gè)頂點(diǎn)至少是三邊的端點(diǎn);邊表中的每條邊是兩個(gè)多邊形面的公共邊；每個(gè)多邊形面是封閉的等等。第二十五頁(yè)，共七十八頁(yè)，編輯于2023年，星期六第二十六頁(yè)，共七十八頁(yè)，編輯于2023年，星期六xyz100110010000101111011001122334415667788515263748110592116103127114981256783214頂點(diǎn)表面表邊表第二十七頁(yè)，共七十八頁(yè)，編輯于2023年，星期六

空間正二十面體V20,的三表表示。引人一個(gè)正數(shù)Φ>0,它滿足二次方程Φ2-Φ-1=0,因此Φ=1/2(1+)≈1.618034。

XYZ第二十八頁(yè)，共七十八頁(yè)，編輯于2023年，星期六編號(hào)xyz編號(hào)xyz11Φ0123-1Φ01213-ΦΦ001-12431-10-Φ10Φ14-Φ0-13201-Φ211Φ0330-1Φ221-Φ0340-1-Φ第二十九頁(yè)，共七十八頁(yè)，編輯于2023年，星期六邊編號(hào)

邊編號(hào)

111，131621，32212，141722，33321，231822，34422，241923，31531，332023，32632，342124，33711，212224，34811，222331，11邊編號(hào)

邊編號(hào)

912，232431，121012，242532，131113，212632，141213，222733，111314，232833，121414，242934，131521，313034，14第三十頁(yè)，共七十八頁(yè)，編輯于2023年，星期六面編號(hào)

面編號(hào)

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第三十一頁(yè)，共七十八頁(yè)，編輯于2023年，星期六第三十二頁(yè)，共七十八頁(yè)，編輯于2023年，星期六三維實(shí)體表示方法從用戶角度來(lái)看，形體以特征表示和構(gòu)造的實(shí)體幾何表示比較適宜；從計(jì)算機(jī)對(duì)形體的存儲(chǔ)管理和操作運(yùn)算角度看，以邊界表示最為實(shí)用。

1構(gòu)造的實(shí)體幾何法構(gòu)造的實(shí)體幾何(CSG:ConstructiveSolidGeometry)法是指任意復(fù)雜的形體都可以用簡(jiǎn)單形體(體素)的組合來(lái)表示。形體的CSG表示可看成是一棵有序的二叉樹(shù)，稱(chēng)為CSG樹(shù)。其終端結(jié)點(diǎn)或是體素，如長(zhǎng)方體、圓錐等；或是剛體運(yùn)動(dòng)的變換參數(shù)，如平移參數(shù)Tx等；非終端結(jié)點(diǎn)或是正則的集合運(yùn)算，一般有交、并、差運(yùn)算；第三十三頁(yè)，共七十八頁(yè)，編輯于2023年，星期六或是剛體的幾何變換，如平移、旋轉(zhuǎn)等。采用BNF范式可定義CSG樹(shù)若下：

<CSG>::=<體素葉子>|<CSG樹(shù)><正則集合運(yùn)算結(jié)點(diǎn)><CSG樹(shù)>|<CSG樹(shù)><剛體運(yùn)動(dòng)結(jié)點(diǎn)><剛體運(yùn)動(dòng)變量>CSG樹(shù)是無(wú)二義性的，但不是唯一的，其定義域取決于所用體素以及所允許的幾何變換和正則集合運(yùn)算算子。

CSG表示的優(yōu)點(diǎn)：數(shù)據(jù)結(jié)構(gòu)比較簡(jiǎn)單，數(shù)據(jù)量比較小，內(nèi)部數(shù)據(jù)的管理比較容易；第三十四頁(yè)，共七十八頁(yè)，編輯于2023年，星期六每個(gè)CSG表示都和一個(gè)實(shí)際的有效形體所對(duì)應(yīng)；CSG表示可方便地轉(zhuǎn)換成Brep表示，從而可支持廣泛的應(yīng)用；比較容易修改CSG表示形體的形狀。CSG表示的缺點(diǎn)：產(chǎn)生和修改形體的操作種類(lèi)有限，基于集合運(yùn)算對(duì)形體的局部操作不易實(shí)現(xiàn)；由于形體的邊界幾何元素(點(diǎn)、邊、面)是隱含地表示在CSG中，故顯示與繪制CSG表示的形體需要較長(zhǎng)的時(shí)間。第三十五頁(yè)，共七十八頁(yè)，編輯于2023年，星期六并第三十六頁(yè)，共七十八頁(yè)，編輯于2023年，星期六2特征表示特征表示是從應(yīng)用層來(lái)定義形體，因而可以較好地表達(dá)設(shè)計(jì)者的意圖，為制造和檢驗(yàn)產(chǎn)品和形體提供技術(shù)依據(jù)和管理信息。從功能上看可分為形狀、精度、材料和技術(shù)特征。形狀特征：體素、孔、槽、鍵等精度特征：形位公差、表面粗糙度等；材料特征：材料硬度、熱處理方法等；技術(shù)特征：形體的性能參數(shù)和特征等。形狀特征單元是一個(gè)有形的幾何實(shí)體，是一組可加工表面的集合。如采用長(zhǎng)、寬、高三尺寸表示的長(zhǎng)方體；采用底面半徑及高度表示的圓柱體均是可選用的形狀特征單元。第三十七頁(yè)，共七十八頁(yè)，編輯于2023年，星期六形狀特征單元的BNF范式可定義如下：

<形狀特征單元>：：=<體素>|<形狀特征單元><集合運(yùn)算><形狀特征單元>|<體素><集合運(yùn)算><體素>|<體素><集合運(yùn)算><形狀特征單元>|<形狀特征單元><集合運(yùn)算><形狀特征過(guò)渡單元>;<體素>：：=長(zhǎng)方體|圓柱體|球體|圓錐體|棱錐體|棱柱體|棱臺(tái)體|圓環(huán)體|楔形體|圓角體|…；<集合運(yùn)算>：：=并|交|差|放；<形狀特征過(guò)渡單元>：：=外圓角|內(nèi)圓角|倒角。第三十八頁(yè)，共七十八頁(yè)，編輯于2023年，星期六第三十九頁(yè)，共七十八頁(yè)，編輯于2023年，星期六3邊界表示邊界表示詳細(xì)記錄了構(gòu)成形體的所有幾何元素的幾何信息及其相互連接關(guān)系—拓?fù)潢P(guān)系，便于直接存取構(gòu)成形體的各個(gè)面、面的邊界以及各個(gè)頂點(diǎn)的定義參數(shù)，有利于以面、邊、點(diǎn)為基礎(chǔ)的各種幾何運(yùn)算和操作。形體的邊界表示就是用面、環(huán)、邊、點(diǎn)來(lái)定義形體的位置和形狀。例如，一個(gè)長(zhǎng)方體由六個(gè)面圍成，對(duì)應(yīng)有六個(gè)環(huán)，每個(gè)環(huán)由四條邊界定義，每條邊又由兩個(gè)端點(diǎn)定義。而圓柱體則由上頂面、下底面和圓柱面所圍成，對(duì)應(yīng)有上頂面圓環(huán)、下底面圓環(huán)。第四十頁(yè)，共七十八頁(yè)，編輯于2023年，星期六Brep表示的優(yōu)點(diǎn)是：表示形體的點(diǎn)、邊、面等幾何元素是顯式表示的，使得繪制Brep表示形體的速度較快，而且比較容易確定幾何元素間的連接關(guān)系；對(duì)形體的Brep表示可有多種操作和運(yùn)算。Brep表示的缺點(diǎn)是：數(shù)據(jù)結(jié)構(gòu)復(fù)雜，需要大量的存儲(chǔ)空間，維護(hù)內(nèi)部數(shù)據(jù)結(jié)構(gòu)的程序比較復(fù)雜；修改形體的操作比較難以實(shí)現(xiàn)；

Brep表示并不一定對(duì)應(yīng)一個(gè)有效形體，即需要有專(zhuān)門(mén)的程序來(lái)保證Brep表示形體的有效性、正則性等。第四十一頁(yè)，共七十八頁(yè)，編輯于2023年，星期六八叉樹(shù)假設(shè)要表示的形體V可以放在一個(gè)充分大的正立方體C內(nèi),C的邊長(zhǎng)為2n,形體VC,它的八又樹(shù)表示可以遞歸定義為:

八叉樹(shù)每個(gè)結(jié)點(diǎn)與C的一個(gè)子立方體對(duì)應(yīng)，樹(shù)根就和C本身對(duì)應(yīng)。如果V=C,那么V八叉樹(shù)僅有樹(shù)根。如果V≠C,則將C均分為八個(gè)子立方體,每個(gè)子立方體對(duì)應(yīng)根結(jié)點(diǎn)的一個(gè)子結(jié)點(diǎn)。只要某個(gè)子立方體不是完全空白或完全被V所占據(jù),它就要被八等分,從而它對(duì)應(yīng)的結(jié)點(diǎn)也有了八個(gè)子結(jié)點(diǎn)。這樣的遞歸判斷及可能分割一直進(jìn)行,直到結(jié)點(diǎn)對(duì)應(yīng)的立方體或完全空白,或完全被占據(jù),或其大小已是預(yù)先規(guī)定的體素大小.第四十二頁(yè)，共七十八頁(yè)，編輯于2023年，星期六

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

通常稱(chēng)對(duì)應(yīng)立方體被形體V完全占據(jù)的結(jié)點(diǎn)為黑結(jié)點(diǎn),完全不占據(jù)的為白結(jié)點(diǎn),部分被占據(jù)的為灰結(jié)點(diǎn)。存貯結(jié)構(gòu),有常規(guī)的、線性的、一對(duì)八式的八叉樹(shù)等等。第四十三頁(yè)，共七十八頁(yè)，編輯于2023年，星期六

八叉樹(shù)方法的主要優(yōu)點(diǎn)在于,可以非常方便地實(shí)現(xiàn)形體的集合運(yùn)算。八叉樹(shù)表示的三維形體的幾何變換比例變換旋轉(zhuǎn)變換相對(duì)通過(guò)原點(diǎn)的一條任意方向的直線做旋轉(zhuǎn)任意角度的旋轉(zhuǎn)變換。構(gòu)成原形體的直立的正立方體經(jīng)繞原點(diǎn)任意軸線旋轉(zhuǎn)任意角度后,一般都成為斜置的。為了使變換后形體的八叉樹(shù)仍對(duì)應(yīng)一系列直立的正立方體,必須對(duì)被斜置立方體部分占據(jù)體素做出選擇,即或認(rèn)為是占據(jù),為黑結(jié)點(diǎn),或認(rèn)為不占據(jù),為白結(jié)點(diǎn),這就必然帶來(lái)一定的誤差。而且執(zhí)行多次變換后,誤差積累會(huì)大到產(chǎn)生嚴(yán)重的錯(cuò)誤。第四十四頁(yè)，共七十八頁(yè)，編輯于2023年，星期六

第一項(xiàng)措施是保持一個(gè)原始的八叉樹(shù)做為參考的源樹(shù)。設(shè)指定了一次變換R1,接著又要做變換R2,可以計(jì)算出復(fù)合變換R=R1·R2,然后對(duì)原始的八叉樹(shù)做一次變換。這樣來(lái)避免誤差的積累。第二項(xiàng)措施是為了盡量減少"舍入"誤差,可以規(guī)定一個(gè)當(dāng)前正要重建的八叉樹(shù),如果它的最底層葉結(jié)點(diǎn)對(duì)應(yīng)的體素是部分地為顯示對(duì)象所占據(jù)，那么當(dāng)且僅當(dāng)這個(gè)體素的中心位于某個(gè)黑變換后立方體內(nèi)時(shí),這個(gè)體素才被規(guī)定為黑,否則就規(guī)定為白。這樣規(guī)定使得一般不會(huì)產(chǎn)生原來(lái)不存在的孔洞，而不這樣規(guī)定,例如簡(jiǎn)單地規(guī)定部分被占據(jù)的體素都為白,則可能在做450左右旋轉(zhuǎn)時(shí)原來(lái)黑立方體變換為部分占據(jù)若干體素而被指定為白,在變換后形體中間出現(xiàn)斷裂。

第四十五頁(yè)，共七十八頁(yè)，編輯于2023年，星期六第四十六頁(yè)，共七十八頁(yè)，編輯于2023年，星期六第四十七頁(yè)，共七十八頁(yè)，編輯于2023年，星期六

設(shè)己采取了上述兩項(xiàng)措施,已知形體變換前的八叉樹(shù)表示T1,己計(jì)算出要做的復(fù)合變換R,要確定變換后形體的八叉樹(shù)表示T2,可以寫(xiě)出如下的算法框架：1.遍歷形體原來(lái)的八叉樹(shù)T1,對(duì)遇到的每個(gè)黑結(jié)點(diǎn),做下述步2。2.對(duì)遇到黑結(jié)點(diǎn)對(duì)應(yīng)的正立方體做相應(yīng)變換,得它新的一般來(lái)說(shuō)是斜置的新位置。若這位置已超出定義八叉樹(shù)的充分大正立方體C之外,報(bào)告出錯(cuò);否則執(zhí)行下述的步3。3.從要計(jì)算求出的目標(biāo)樹(shù)T2的根開(kāi)始,檢查2中確定的處于新位置立方體與T2中結(jié)點(diǎn)對(duì)應(yīng)的直立的正立方體是否相交,分以下三種情況進(jìn)行處理:第四十八頁(yè)，共七十八頁(yè)，編輯于2023年，星期六(1)不相交,說(shuō)明正考查直立正立方體未被占據(jù),可保持為白結(jié)點(diǎn),不做處理。(2)直立的正立方體整個(gè)被占據(jù),即它在變換后"斜置"立方體內(nèi),置對(duì)應(yīng)結(jié)點(diǎn)為黑結(jié)點(diǎn)。(3)在上述兩條均不成立時(shí),生成當(dāng)前結(jié)點(diǎn)的八個(gè)子結(jié)點(diǎn),對(duì)八個(gè)子結(jié)點(diǎn)對(duì)應(yīng)的八個(gè)直立子立方體,依次再遞歸執(zhí)行步3。如果最終這八個(gè)結(jié)點(diǎn)被標(biāo)上同樣特性,比方為黑結(jié)點(diǎn),則應(yīng)再刪掉這八個(gè)子結(jié)點(diǎn)而把它們的共同父結(jié)點(diǎn)置為黑。算法中,主要工作是檢查某個(gè)直立的正立方體與一個(gè)斜置的正立方體是否相交,。對(duì)所有黑結(jié)點(diǎn)對(duì)應(yīng)正立方體處理相同,使得操作可以并行進(jìn)行。第四十九頁(yè)，共七十八頁(yè)，編輯于2023年，星期六線性八叉樹(shù)在對(duì)立方體做八等分時(shí),按一致的方式,對(duì)分出的子立方體進(jìn)行編號(hào)。若再分共進(jìn)行n層，則每個(gè)結(jié)點(diǎn)可以用n位的八進(jìn)制數(shù)的數(shù)串來(lái)表示,數(shù)串從左至右,第一位對(duì)應(yīng)第一次劃分，第二位對(duì)應(yīng)第二位劃分，依此類(lèi)推。據(jù)此整個(gè)八叉樹(shù)就可以根據(jù)對(duì)其做深度第一遍歷而依次列出的黑結(jié)點(diǎn)的編號(hào)序列來(lái)表示。前圖所示三維形體,其線性八叉樹(shù)表示是:{0x,10,12,13,14,2x,4x,6x,7x}第五十頁(yè)，共七十八頁(yè)，編輯于2023年，星期六求并運(yùn)算C1UC2

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

將C2的各結(jié)點(diǎn)依次插入到C1的適當(dāng)位置,使插入后編號(hào)漸增這一性質(zhì)保持不變。當(dāng)C2中結(jié)點(diǎn)可以包含C1中若干結(jié)點(diǎn)時(shí),則取而代之。另外,如果插入后可以進(jìn)行結(jié)點(diǎn)"壓縮",也應(yīng)該立即進(jìn)行:C1UC2={12x,300,301,302,303,304,305,306,307}={12x,30x}第五十一頁(yè)，共七十八頁(yè)，編輯于2023年，星期六八叉樹(shù)表示形體的顯示當(dāng)觀察位置是x1>0,y1<0,z1>0時(shí),最可能被遮擋看不見(jiàn)的是編號(hào)2的子立方體,全部依次排出可以是26034715第五十二頁(yè)，共七十八頁(yè)，編輯于2023年，星期六zl>0,y1<0,x1>0

優(yōu)先級(jí)26034715。前圖表示形體的線性八叉樹(shù){0x,10,12,13,14,2x,4x,6x,7x}按結(jié)點(diǎn)應(yīng)顯示次序排出的序列就是:{2x,6x,Ox,4x,7x,12,10,13,14}

z1

y1

x1

優(yōu)先級(jí)<0<0<073561240<0<0>037125604<0>0<051743062<0>0>015307426>0<0<062470351>0<0>026034715>0>0<040652173>0>0>004216537第五十三頁(yè)，共七十八頁(yè)，編輯于2023年，星期六第三節(jié)分形

分形的概念

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

F可以看成是集序列Ek當(dāng)k趨于無(wú)窮時(shí)的極限。只能畫(huà)出k取定時(shí)的某個(gè)Ek。當(dāng)k充分大時(shí),Ek是對(duì)F的很好的近似的表現(xiàn)

第五十四頁(yè)，共七十八頁(yè)，編輯于2023年，星期六第五十五頁(yè)，共七十八頁(yè)，編輯于2023年，星期六

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

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

三分康托集具有的一些值得注意的特征,這些特征對(duì)許多其它的分形也是大體上適合的。(1)F是自相似的。E1的兩個(gè)區(qū)間[0，1/3]，[1/3，2/3]的每一個(gè),其內(nèi)部F的部分與F整體相似,相似比為1/3。第五十六頁(yè)，共七十八頁(yè)，編輯于2023年，星期六(2)F具有“精細(xì)結(jié)構(gòu)”，即它包含有任意小比例的細(xì)節(jié)。(3)F的實(shí)際定義是簡(jiǎn)單的和明確的。(4)傳統(tǒng)的幾何學(xué)很難描述F的性質(zhì),因?yàn)镕不是滿足某些簡(jiǎn)單條件的點(diǎn)的軌跡,也不是任何簡(jiǎn)單的方程的解的集合。(5)F的局部幾何性質(zhì)也很難描述,在它的每點(diǎn)附近都有大量被各種不同間隔分開(kāi)的其它點(diǎn)。

(6)按傳統(tǒng)幾何學(xué)中的長(zhǎng)度概念,F的長(zhǎng)度為零。就是說(shuō),盡管從不可數(shù)集合這點(diǎn)上說(shuō)F是一個(gè)相當(dāng)大的集,但它卻沒(méi)有長(zhǎng)度,或者說(shuō)長(zhǎng)度不能對(duì)F的形狀或大小提供有意義的描述。第五十七頁(yè)，共七十八頁(yè)，編輯于2023年，星期六vonKoch曲線

第五十八頁(yè)，共七十八頁(yè)，編輯于2023年，星期六

稱(chēng)集合F是分形,即認(rèn)為它具有下面典型的性質(zhì):(1)

F具有精細(xì)的結(jié)構(gòu)，即有任意小比例的細(xì)節(jié)。

(2)F是如此的不規(guī)則以至它的整體和局部都不能用傳統(tǒng)的幾何語(yǔ)言來(lái)描述。(3)F具有某種自相似的形式,可能是近似的或是統(tǒng)計(jì)的。(4)一般地,F的"分形維數(shù)"大于它的拓?fù)渚S數(shù)。

(5)在大多數(shù)令人感興趣的情形下,F以非常簡(jiǎn)單的方法定義,可能由迭代產(chǎn)生。第五十九頁(yè)，共七十八頁(yè)，編輯于2023年，星期六

考慮一個(gè)簡(jiǎn)單的幾何圖形,取一個(gè)邊長(zhǎng)為1的正方形,若每邊擴(kuò)大2倍,則正方形面積放大4倍,其數(shù)學(xué)表達(dá)式為22=4,這是2維圖形。對(duì)3維圖形,如考慮邊長(zhǎng)為1的立方體,令每邊長(zhǎng)放大2倍,則立方體體積擴(kuò)大8倍,其數(shù)學(xué)表達(dá)式為23=8。類(lèi)似地,對(duì)一個(gè)Df維的幾何對(duì)象,若每邊長(zhǎng)擴(kuò)大L倍,則這個(gè)幾何對(duì)象相應(yīng)地放大K倍,歸納前述結(jié)果,Df,L,K三者間的關(guān)系式應(yīng)為:LDf=K解出Df,有:Df=lnK/lnL這里Df不必是整數(shù)。這就是Hausdorff引人的維數(shù)概念,可以稱(chēng)為Hausdorff維數(shù)。第六十頁(yè)，共七十八頁(yè)，編輯于2023年，星期六

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

容易看出式(1)和(2)本質(zhì)上是相同的,即這樣引入的也是Hausdorff維數(shù)第六十一頁(yè)，共七十八頁(yè)，編輯于2023年，星期六vonKoch曲線,每次分為4個(gè)小圖形,每個(gè)小圖形縮小1/3倍,故其Hausdorff維數(shù)為：

分形一般算法

規(guī)則分形的生成算法。對(duì)算法的輸入是事先給定的一個(gè)整數(shù)k、源形E0及生成規(guī)則,算法操作步驟如下:第六十二頁(yè)，共七十八頁(yè)，編輯于2023年，星期六1.〔初始化〕i←0,j←1,隊(duì)Q←φ,A0←Eo;{用在第i層表示正處在生成Ei的階段。對(duì)m≥2,設(shè)生成規(guī)則指明了Ei由m個(gè)Ei+1組成,則在第i層共應(yīng)生成mi個(gè)部分圖形。用A0記一個(gè)部分圖形,j是己生成部分圖形的數(shù)目。第i層部分圖形要在第i+1層再分,故生成后要送到一個(gè)先進(jìn)先出的隊(duì)Q中等待;}2.〔一次生成〕依據(jù)生成規(guī)則,由一個(gè)部分圖形A0,計(jì)算它的m個(gè)分解部分A1,A2,…Am;3.〔圖形繪制〕對(duì)Al,A2,…,Am做圖形繪制;4.〔存貯〕隊(duì)Q←(A1,A2,…,Am){生成各部分圖形依次加到隊(duì)尾;}第六十三頁(yè)，共七十八頁(yè)，編輯于2023年，星期六5.〔準(zhǔn)備下次〕A0←隊(duì)Q;{從隊(duì)取出一個(gè)部分圖形;}6.〔第i層是否結(jié)束〕j←j+1,若j>mi,則j←1;i←i+1;7.〔結(jié)束判斷〕若i>k,則算法結(jié)束;否則返回步

2.vonKoch曲線其源形E0可以是一條線段,記其端點(diǎn)坐標(biāo)為P0,P1。在算法步1,應(yīng)令A(yù)0=E0=(Po,Pl),在算法步2,需要依據(jù)Po,Pl,計(jì)算圖中P2,P3,P4三點(diǎn)的坐標(biāo)。這樣m=4,分別得到四個(gè)部分圖形是A1=(P0,P2),A2=(P2,P3),A3=(P3,P4),A4=(P4,P1)。在算法步3,可畫(huà)出四條線段P0P2,P2P3,P3P4,P4P1,擦去前次畫(huà)線時(shí)可能畫(huà)出的P2P4部分。第六十四頁(yè)，共七十八頁(yè)，編輯于2023年，星期六VonKoch算法利用自相似變換來(lái)繪制分形設(shè)D是歐氏空間Rn的閉子集,映射S:D→D稱(chēng)為是D上的壓縮，如果對(duì)所有D上的點(diǎn)x,y,存在一個(gè)數(shù)c,0<c<1,能使|S(x)-S(y)|≤c|x-y|。如果其中等號(hào)成立,即若|S(x)-S(y)|=c|x-y|,則S把一個(gè)集變成了它的幾何相似集,此時(shí)映射S稱(chēng)為是相似的。設(shè)S1,…,Sn是壓縮,稱(chēng)D的子集F對(duì)變換S1,…,Sn是不變的,如果第六十五頁(yè)，共七十八頁(yè)，編輯于2023年，星期六

三分康托集的情形,這時(shí)令S1,S2是R→R的變換,分別由第六十六頁(yè)，共七十八頁(yè)，編輯于2023年，星期六P0和P1的坐標(biāo)是(0,0)和(1,0),則可以計(jì)算求出P2,P3,P4的坐標(biāo)是

自相似變換S1和S2是平面變換,可一般地設(shè)變換矩陣為:第六十七頁(yè)，共七十八頁(yè)，編輯于2023年，星期六

第一個(gè)變換S1把點(diǎn)P0,P1,P3,依次變到Po,P3,P2,這就得到:第六十八頁(yè)，共七十八頁(yè)，編輯于2023年，星期六于是有第六十九頁(yè)，共七十八頁(yè)，編輯于2023年，星期六

第二個(gè)變換S2把點(diǎn)P0,P1,P3,依次