第三維幾何造型

（優(yōu)選）第三維幾何造型當前1頁，總共107頁。6.1.1形體的定義幾何形體由基本元素點、邊、面、體等組成，這些基本元素的定義如下。1．點它是0維幾何元素，分端點、交點、切點和孤立點等。但在形體定義中一般不允許存在孤立點。在自由曲線和曲面的描述中常用三種類型的點，即：(1)控制點用來確定曲線和曲面的位置與形狀，而相應曲線和曲面不一定經(jīng)過的點。(2)型值點用來確定曲線和曲面的位置與形狀，而相應曲線和曲面一定經(jīng)過的點。當前2頁，總共107頁。

(3)插值點

為提高曲線和曲面的輸出精度，在型值點之間插入的一系列點。

一維空間中的點用一元組{t}表示；二維空間中的點用二元組{x，y}或{x（t），y（t）}表示；三維空間中的點用三元組{x，y，z｝或{x（t），y（t），z(t)}表示。n維空間中的點在齊次坐標系下用n＋1維表示。點是幾何造型中的最基本元素，自由曲線、曲面或其他形體均可用有序的點集表示。用計算機存儲、管理、輸出形體的實質就是對點集及其連接關系的處理。

當前3頁，總共107頁。2．邊邊是一維幾何元素，是兩個鄰面（正則形體）或多個鄰面（非正則形體）的交界。直線邊由其端點（起點和終點）定界；曲線邊由一系列型值點或控制點表示，也可用顯式、隱式方程表示。

3．面面是二維幾何元素，是形體上一個有限、非零的區(qū)域，由一個外環(huán)和若干個內環(huán)界定其范圍。一個面可以無內環(huán)，但必須有一個且只有一個外環(huán)。

面有方向性，一般用其外法矢方向作為該面的正向。若一個面的外法矢向外，此面為正向面；反之，為反向面。

當前4頁，總共107頁。區(qū)分正向面和反向面在面面求交、交線分類、真實圖形顯示等方面都很重要。在幾何造型中常分平面、二次面、雙三次參數(shù)曲面等形式。

4．環(huán)環(huán)是有序、有向邊（直線段或曲線段）組成的面的封閉邊界。環(huán)中的邊不能相交，相鄰兩條邊共享一個端點。

環(huán)有內外之分，確定面的最大外邊界的環(huán)稱之為外環(huán)，通常其邊按逆時針方向排序。而把確定面中內孔或凸臺邊界的環(huán)稱之為內環(huán)，其邊與外環(huán)排序方向相反，通常按順時針方向排序?；谶@種定義，在面上沿一個環(huán)前進，其左側總是面內，右側總是面外。

當前5頁，總共107頁。5．體體是三維幾何元素，由封閉表面圍成的空間，也是歐氏空間R3中非空、有界的封閉子集，其邊界是有限面的并集。

為了保證幾何造型的可靠性和可加工性，要求形體上任意一點的足夠小的鄰域在拓撲上應是一個等價的封閉圓，即圍繞該點的形體鄰域在二維空間中可構成一個單連通域。我們把滿足這個定義的形體稱之為正則形體。不滿足上述要求的形體稱為非正則形體。

非正則形體的造型技術將線框、表面和實體模型統(tǒng)一起來，可以存取維數(shù)不一致的幾何元素，并可對維數(shù)不一致的幾何元素進行求交分類，從而擴大了幾何造型的形體覆蓋域。

當前6頁，總共107頁?；邳c、邊、面幾何元素的正則形體和非正則形體的區(qū)別如表6.1表所示。

表6.1正則形體和非正則形體的區(qū)別幾何元素正則形體非正則形體面是形體表面的一部分可以是形體表面的一部分,也可以是形體內的一部分,也可以與形體相分離。邊只有二個鄰面可以有多個鄰面、一個鄰面或沒有鄰面。點至少和三個面(或三條邊)鄰接可以與多個面(或邊)鄰接，也可以是聚集體、聚集面、聚集邊或孤立點。當前7頁，總共107頁。6．體素體素是可以用有限個尺寸參數(shù)定位和定形的體，常有三種定義形式。

（1）從實際形體中選擇出來，可用一些確定的尺寸參數(shù)控制其最終位置和形狀的一組單元實體，如長方體、圓柱體、圓錐體、圓環(huán)體、球體等。

（2）由參數(shù)定義的一條（或一組）截面輪廓線沿一條（或一組）空間參數(shù)曲線作掃描運動而產(chǎn)生的形體。

（3）用代數(shù)半空間定義的形體，在此半空間中點集可定義為：{(x，y，z)|f（x，y，z）≤0}，此處的f應是不可約多項式，多項式系數(shù)可以是形狀參數(shù)，半空間定義法只適用正則形體。

當前8頁，總共107頁。從上述定義中我們知道幾何形體有兩種重要信息：幾何信息和拓撲信息。幾何信息是指描述幾何元素（如點、線、面等）空間位置和大小的信息，如點的空間坐標值、線段的長度等。拓撲信息是指幾何元素之間的相互連接關系的信息。它只反映幾何元素的結構關系，而不考慮它們各自的絕對位置，這種關系稱為拓撲關系。幾何元素之間一共有九種拓撲關系，即面-面相鄰性、邊-邊相鄰性、頂點-頂點相鄰性、邊-面相鄰性、頂點-面相鄰性、頂點-邊相鄰性、面-邊包含性、面-頂點包含性、邊-頂點包含性。當前9頁，總共107頁。6.1.2形體的存儲模型

無論是形體的表示，還是新形體的生成都與其幾何信息和拓撲信息有關。只有幾何信息沒有拓撲信息是不能構成圖形的。這兩方面的信息如何在計算機中存儲和使用，達到既節(jié)省計算機的空間資源和時間資源，又能有效地進行各種操作運算，一般是通過研究圖形的數(shù)據(jù)結構來解決。

三維形體在計算機內的3種存儲模式?jīng)Q定了形體的3種存儲模型：線框模型、表面模型和實體模型。

當前10頁，總共107頁。1．線框模型（Wireframe

Model）三維線框模型是在二維線框模型的基礎上發(fā)展起來的。在60年代初期，用戶通過逐點、逐線地構造二維線框模型，就能用計算機代替手工繪圖。由于圖形幾何變換和投影變換理論的發(fā)展，認識到在計算機內部的存儲信息中加上第三維信息，再用不同視向的投影變換，就可以在顯示器上顯示出不同視向的立體圖。因此，三維繪圖系統(tǒng)迅速發(fā)展了起來。

線框模型采用頂點表和邊表兩個表的數(shù)據(jù)結構來表示三維物體，頂點表記錄各頂點的坐標值，邊表記錄每條邊所連接的兩個頂點。由此可見，三維物體可以用它的全部頂點及邊的集合來描述，線框一詞由此而來。

當前11頁，總共107頁。V1V2V3V4V5V6V7V8E8E10E1E2E3E4E5E6E7E9E11E12abcXZY圖6.2和表6.2、表6.3說明了線框模型在計算機內存儲的數(shù)據(jù)結構原理。

圖6.2組成長方體的頂點和邊

當前12頁，總共107頁。頂點表V1V2V3V4V5V6V7V8x坐標aaaa0000y坐標0bb00bb0z坐標00cc00cc邊號E1E2E3E4E5E6E7E8E9E10E11E12起點號V1V2V3V4V5V6V7V8V1V2V3V4終點號V2V3V4V1V6V7V8V5V5V6V7V8表6.2長方體的頂點表

表6.3長方體的邊表

當前13頁，總共107頁。線框模型的優(yōu)點主要是可以產(chǎn)生任意視圖，視圖間能保持正確的投影關系，這為生成需要多視圖的工程圖紙帶來了很大方便。還能生成任意視點或視向的透視圖及軸測圖。構造模型時操作簡便，在CPU時間及存儲方面開銷低。

線框模型的缺點也很明顯，因為所有棱線全都顯示出來，物體的真實形狀須由人腦的解釋才能理解，因此容易出現(xiàn)二義性。當形狀復雜時，棱線過多，也會引起模糊理解。缺少曲面輪廓線。由于在數(shù)據(jù)結構中缺少邊與面、面與體之間關系的信息，即所謂拓撲信息，因此不能構成實體，無法識別面與體，更談不上區(qū)別體內與體外。當前14頁，總共107頁。因此從原理上講，此種模型不能消除隱藏線，不能作任意剖切，不能計算物性，不能進行兩個面的求交，無法生成數(shù)控加工刀具軌跡，不能自動劃分有限元網(wǎng)格，不能檢查物體間碰撞、干涉等。但目前有些系統(tǒng)從內部建立了邊與面的拓撲關系，因此具有消隱功能。

盡管這種模型有許多缺點，但由于它仍能滿足許多設計與制造的要求，加上上面所說的優(yōu)點，因此在實際工作中使用很廣泛，而且在許多CAD／CAM系統(tǒng)中仍將此種模式作為表面模型與實體模型的基礎。線框模型系統(tǒng)一般具有豐富的交互功能，用于構圖的圖素是大家所熟知的點、線、圓、圓弧、二次曲線、樣條曲線、Bezier曲線等。

當前15頁，總共107頁。2．表面模型（SurfaceModel）這種模型通常用于構造復雜的曲面物體，構形時常常利用線框功能，先構造一線框圖，然后用掃描或旋轉等手段變成曲面，當然也可以用系統(tǒng)提供的許多曲面圖素來建立各種曲面模型。該模型的數(shù)據(jù)結構原理見圖6.3，與線框模型相比，多了一個面表（頂點表和邊表與表6.2和表6.3完全相同，面表見表6.4），記錄了邊、面間的拓撲關系，但仍舊缺乏面、體間的拓撲關系，無法區(qū)別面的哪一側是體內,哪一側是體外，依然不是實體模型。當前16頁，總共107頁。V1V2V3V4V5V6V7V8E8E10E1E2E3E4E5E6E7E9E11E12abcXZYF1F3F4F2F5F6圖6.3長方體的頂點、邊和面

當前17頁，總共107頁。面號F1F2F3F4F5F6邊號E1E2E3E4E5E6E7E8E1E10E5E9E2E11E6E10E3E12E7E11E4E9E8E12表6.4長方體的面表

表面模型的優(yōu)點是能實現(xiàn)以下功能：消隱、著色、表面積計算、二曲面求交、數(shù)控刀具軌跡生成、有限元網(wǎng)格劃分等。此外擅長于構造復雜的曲面物體，如模具、汽車、飛機等表面。它的缺點是有時產(chǎn)生對物體二義性理解。

當前18頁，總共107頁。需要指出的是不僅表面模型中常常包括了線框模型的構圖圖素，而且表面模型還時常與線框模型一起同時存在于同一個CAD／CAM系統(tǒng)中。表面模型系統(tǒng)中常用的曲面圖素有平面、直紋面、旋轉面、柱狀面、貝塞爾曲面、B樣條曲面、孔斯曲面和等距面。

3．實體模型實體模型與表面模型的不同之處在于確定了表面的哪一側存在實體這個問題。常用辦法是用有向邊的右手法則確定所在面的外法線的方向（即用右手沿著邊的順序方向握住，大拇指所指向的方向則為該面的外法線的方向）。當前19頁，總共107頁。例如規(guī)定正向指向體外，如圖6.4所示。如此只須將表6.4的面表改成表6.5的環(huán)表形式，就可確切地分清體內體外，形成實體模型了。

體外圖6.4有向邊確定外法線方向

實體模型的數(shù)據(jù)結構當然不會這么簡單，可能有許多不同的結構。但有一點是肯定的，即數(shù)據(jù)結構不僅記錄了全部幾何信息，而且記錄了全部點、線、面、體的拓撲信息，這是實體模型與線框或表面模型的根本區(qū)別。

當前20頁，總共107頁。面號F1F2F3F4F5F6邊號E1E2E3E4E8E7E6E5E1E9E5E10E2E10E6E11E3E11E7E12E4E12E8E9表6.5長方體的環(huán)表

實體模型成了設計與制造自動化及集成的基礎。依靠機內完整的幾何與拓撲信息，所有前面提到的工作，從消隱、剖切、有限元網(wǎng)格劃分、直到NC刀具軌跡生成都能順利地實現(xiàn)，而且由于著色、光照及紋理處理等技術的運用使物體有著出色的可視性，使它在CAD／CAM、計算機藝術、廣告、動畫等領域有廣泛的應用。

實體模型的構造方法常用機內存儲的體素(Primitive),經(jīng)集合論中的交、并、差運算構成復雜形體。

當前21頁，總共107頁。形體的線框模型、表面模型和實體模型是一種廣義的概念，并不反映形體在計算機內部，或對最終用戶而言所用的具體表示方式。從用戶角度看，形體表示以特征表示和構造的實體幾何表示（CSG）較為方便；從計算機對形體的存儲管理和操作運算角度看，以邊界表示（BRep）最為實用。為了適合某些特定的應用要求，形體還有一些輔助表示方式，如單元分解表示和掃描表示。對于一個幾何造型系統(tǒng)不可能同時采用上述五種表示，也不可能只采用一種表示，一般根據(jù)應用的要求和計算機條件采用某幾種表示的混合方式。6.2三維實體表示方法當前22頁，總共107頁。例如，70年代初，美國Rochester大學推出了以CSG表示為基礎的PADL-1系統(tǒng)；日本北海道大學推出了以Coons曲面片為邊界的TIPS系統(tǒng)；美國MIT大學推出了以線框邊界為基礎的ADAM系統(tǒng)；美國Stanford大學推出了以歐拉操作為基礎的Geomod系統(tǒng)；英國Cambridge大學推出了以邊界表示為基礎的Build-1系統(tǒng)。目前，國際上應用較廣的幾何造型系統(tǒng)有IBM公司的CADAM和CATIA；SDRC公司的Geomod；PT公司的Pro/Engineer；SpatialTechnology公司的ACIS；Solidworks公司的Solidworks等。當前23頁，總共107頁。構造的實體幾何(CSG：ConstructiveSolidGeometry)法的含意是任何復雜的形體都可用簡單形體（體素）的組合來表示。通常用正則集合運算（構造正則形體的集合運算）來實現(xiàn)這種組合，其中可配合執(zhí)行有關的幾何變換。

形體的CSG表示可看成是一棵有序的二叉樹，稱為CSG樹。其終端結點或是體素，如長方體、圓柱體等；或是剛體運動的變換參數(shù)，如平移參數(shù)△x等。非終端結點或是正則的集合運算，一般有交、并、差運算；或是剛體的幾何變換，如平移、旋轉等。

6.2.1構造的實體幾何法當前24頁，總共107頁。這里，正則集合運算是在傳統(tǒng)點集的集合運算基礎上附加一定的限制而定義的。傳統(tǒng)的點集之間的并、交、差運算可能改變點集的正則性質，也就是說，兩個正則點集的集合運算的結果可能產(chǎn)生一個非正則點集。但在實際生活中，兩物體并、交、差運算的結果總是產(chǎn)生一新的物體（或一空物體）。為了反映這樣一個事實，有必要對傳統(tǒng)的點集的集合運算施加一定的限制。為此，對點集的正則集合運算作如下定義：A∪*B=r(A∪B)A∩*B=r(A∩B)A―*B=r(A―B)當前25頁，總共107頁。這種運算或變換只對其緊接著的子結點（子形體）起作用。每棵子樹（非變換葉子結點）都代表一個集合，表示了其下兩個結點組合及變換的結果，它是用算子對體素進行運算后生成的。樹根表示了最終的結點，即整個形體。CSG樹可能是一顆不完全的二叉樹，這取決于用戶拼合該物體時所設計的步驟。

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

其中，∪*、∩*、―*分別稱為正則并、正則交、正則差，而∪、∩、―則表示傳統(tǒng)的點集的并、交、差集合運算，r表示點集正則化算子。當前26頁，總共107頁。（2）每個CSG表示都和一個實際的有效形體相對應；

（3）CSG表示可方便地轉換成BRep表示，從而可支持廣泛的應用；（4）比較容易修改CSG表示形體的形狀。CSG法的缺點：（1）產(chǎn)生和修改形體的操作種類有限，基于集合運算對形體的局部操作不易實現(xiàn)；（2）由于形體的邊界幾何元素（點、邊、面）是隱含地表示在CSG中，故顯示與繪制CSG表示的形體需要較長的時間。

CSG法的優(yōu)點：（l）數(shù)據(jù)結構比較簡單，數(shù)據(jù)量比較小，內部數(shù)據(jù)的管理比較容易；當前27頁，總共107頁。邊界表示（BoundaryRepresentation）法詳細記錄了構成形體的所有幾何元素的幾何信息及其相互連接關系的拓撲信息，以便直接存取構成形體的各個面、面的邊界以及各個頂點的定義參數(shù)，有利于以面、邊、點為基礎的各種幾何運算和操作。如形體線框的繪制、有限元網(wǎng)格的劃分、數(shù)控加工軌跡的計算、真實感彩色圖形的生成等。

所謂邊界就是物體內部點與外部點的分界面。形體的邊界表示就是用面、環(huán)、邊、點來定義形體的位置和形狀。例如，長方體由六個面圍成，對應有六個環(huán)，每個環(huán)由四條邊界定，每條邊又由兩個端點定義。而圓柱體由上頂面、下底面和圓柱面圍成，對應的有上頂面圓環(huán)、下底面圓環(huán)。

6.2.2邊界表示法當前28頁，總共107頁。在邊界表示法中，為了對記錄的頂點、邊和平面數(shù)據(jù)信息進行存儲管理，需要選取一定的數(shù)據(jù)結構。常用的數(shù)據(jù)結構有：翼邊結構、半邊結構和多表結構。每種方法均有一定的應用范圍和優(yōu)缺點。其中最簡單易用的是采用3個表結構，即頂點表、邊表和面表。如圖6.3中，長方體由頂點表、邊表和面表（表6.2~6.4）描述。

點、邊、面之間的連接關系共有9種：V:{V}、V:{E}、V:{F}、E:{V}、E:{E}、E:{F}、F:{V}、F:{E}、F:{F}，如圖6.6(P197)所示。

一個簡單多面體用邊界表示法表示時滿足歐拉公式：

V-E+F=2當前29頁，總共107頁。其中，V、E、F為實體的頂點、邊和面數(shù)。如一個長方體，V=8，E=12，F(xiàn)=6。對于具有孔洞的正則多面體，相應的歐拉公式擴展為：

V-E+F-H=2（B-P）

其中，新增的參數(shù)H為實體表面的空穴數(shù)，B為實體個數(shù)，P為穿透實體的孔洞數(shù)。如一個帶一個長方體孔的長方體，V=16，E=24，F(xiàn)=10，H=2，B=1，P=2。

BRep表示的優(yōu)點是：（1）表示形體的點、邊、面等幾何元素是顯式表示的，使得繪制BRep表示形體的速度較快，而且比較容易確定幾何元素間的連接關系；

當前30頁，總共107頁。（2）修改形體的操作比較難以實現(xiàn)；（3）BRep表示并不一定對應一個有效形體，即需要有專門的程序來保證BRep表示形體的有效性、正則性等。

掃描表示法是指通過平移、旋轉及其他對稱變換來構造三維物體的方法。一個集合在空間運動就能“掃”成一實體。通常用二維形體及它的運動軌跡來表示掃描生成的物體。有兩種掃描方法：平移掃描和旋轉掃描。

6.2.3掃描表示法當前31頁，總共107頁。如圖6.7(左)所示的平移掃描，圖中A(五邊形)是一個二維的多邊形，B是一條有向的直線，相當于運動軌跡，A沿著B路徑進行掃描運動，則形成圖中所示物體。由于路徑B的表達很簡單，又由于集合A的表示可用A的邊界的邊來表示，所以平移掃描的表示可減為A集合的二維表示。

圖6.7兩種掃描形成的實體

當前32頁，總共107頁。圖6.7(中、右)的旋轉掃描，這個物體可以看作為集合A按繞Z軸旋轉的路徑B運動而成。同樣，集合A是一個二維形體，可用其邊界的邊來表示。

通常在以邊界表示法為基礎的幾何造型系統(tǒng)中，時常將這兩類掃描方法列為輸入形體的手段之一，只要在屏幕上設計出所要的一個二維圖形，調用系統(tǒng)提供的掃描命令，立即就能形成三維實體，因此成為形體輸入的強有力的手段之一。掃描表示中的二維集合由有界邊線組合而成的這個特點，對經(jīng)過傳統(tǒng)訓練的繪圖人員來說，給了他們一個方便的接口,使他們能在屏幕上得心應手地進行設計。

這兩類掃描表示中，只要二維集合A無二義性，實體就不會有二義性。

當前33頁，總共107頁。特征表示是從應用層來定義形體，可以較好地表達設計者的意圖，為制造和檢驗產(chǎn)品和形狀提供技術依據(jù)和管理信息。特征造型是面向制造全過程、實現(xiàn)CAD/CAM集成的重要手段。1988年,ISO頒布的STEP(產(chǎn)品模型數(shù)據(jù)交換標準）標準草案，將形狀、容差、材料等特征列為產(chǎn)品信息模型的構成要素，從而使特征造型獲得法定地位。所謂特征是指一個產(chǎn)品模型的相關元素集，是在設計、加工、裝配等過程中定義的關于幾何形狀和其他屬性的信息集合。不同的面向應用的觀點，形成了各種不同的特征定義，由此也形成了不同的特征分類標準。6.2.4特征表示法當前34頁，總共107頁。從產(chǎn)品的整個生命發(fā)展周期來看，特征可分為設計特征、加工特征、分析特征公差及檢測特征、裝配特征。從功能上看，特征可分為形狀特征、精度特征、技術特征、材料特征、裝配特征。一般公認的基本特征分為：形狀特征：具有特定形狀且對應特定功能意義的零件局部形狀在整體上的布局。精度特征：在工程設計和加工中使用的形位公差、尺寸公差、表面光潔度等非幾何信息，此外還包括檢測特征。材料特征：規(guī)定了材料類型、強度、延展度、熱導度等特征。當前35頁，總共107頁。裝配特征：包括裝配體中各零件的位置關系、公差配合、功能關系、動力學關系等。分析特征：有關部門工程分析方面的特征，如有限元分析中的梁特征和板件特征。上述特征分類中最基本的是形狀特征，平常一般說到特征時，主要指形狀特征。形狀特征單元是一個有形的幾何實體，是一組可加工表面的集合。常用的體素定義如圖6.1(P191)所示。當前36頁，總共107頁。<形狀特征單元>::=<體素>|<形狀特征單元><集合運算><形狀特征單元>|<體素><集合運算><體素>|<體素><集合運算><形狀特征單元>|<形狀特征單元><集合運算><形狀特征過渡單元>；<體素>::=長方體|圓柱體|球體|圓錐體|棱錐體|棱柱體|

棱臺體|圓環(huán)體|楔形體|圓角體|…；<集合運算>::=并|交|差|放；<形狀特征過渡單元>::=外圓角|內圓角|倒角。當前37頁，總共107頁。雖然物體之間的并、交、差運算是物體造型的十分有用的手段，然而由于在邊界表示中，物體之間的集合運算涉及到兩物體上所有表面的求交、比較，由此形成的巨大計算量不僅影響了集合運算的效率，而且由于求交情況復雜，也影響了算法的可靠性。解決的途徑有兩條，一是改進已有的集合運算算法（特別是其中的求交算法），二是探索物體在計算機內新的表示模式。三維物體的八叉樹表示正是這種探索的結果。物體的八叉樹表示是一種層次數(shù)據(jù)結構，是對二維空間中四叉樹編碼方法的擴展。四叉樹將二維區(qū)域分成四等分而得，八叉樹是將三維區(qū)域分成八等分而得。6.2.5單元分解表示法當前38頁，總共107頁。首先在空間中定義一個能夠包含所表示物體的立方體。立方體的三條棱邊分別與x,y,z軸平行，邊長為2n。若立方體內空間完全由所表示的物體所占據(jù)，則物體可用這個立方體予以表示，否則將立方體在x,y,z軸三個方向都分成二等分，整個立方體共等分為八個小塊，每塊仍為一個小立方體，其邊長為原來立方體邊長的1/2。將這八個小立方體依序編號為0，1，2，…，7，如圖6.9所示。1305467xz圖6.9八叉樹的結點編碼

當前39頁，總共107頁。若某一小立方體的體內空間全部被所表示的物體占據(jù)，則將此立方體標識為“Full”；若它與所表示物體無交，則該立方體被標識為“Empty”；否則將它標識為“Partial”，并繼續(xù)分割下去。依此方式，物體在計算機內可表示為一棵八叉樹。注意，凡是標識為“Full”或“Empty”的立方體均為終端結點，而標識為“Partial”的立方體為非終端結點。最后，當分割生成的每一小立方體的邊長為單位長時，分割即告終止。此時可將每一小立方體標識為“Full”。當前40頁，總共107頁。物體之間的集合運算在八叉樹表示中具有十分簡單的形式。由定義可知，兩物體的并就是這兩個物體一共占有的空間，而物體之間的交即它們共同占據(jù)的空間。由于物體的八叉樹表示就是由它內部含有的大大小小的立方體（稱為體元）組成，因此對物體執(zhí)行并、交、差運算時，只需同時遍歷參加集合運算的兩物體相應的八叉樹，就可以獲得拼合體的八叉樹，而無需進行復雜的求交運算。

八叉樹的數(shù)據(jù)結構也大大簡化了隱藏線和隱藏面的消除。眾所周知，各類消隱算法的核心部分是排序，即將待顯示的物體上的點、線、面按離觀察點的遠近排定次序，離觀察點近的元素遮擋較遠的元素。

當前41頁，總共107頁。在八叉樹表示中，物體上的各元素已按空間位置排成一定順序，同一層次的八叉樹結點組成三維空間中可線性分離的叢。因此可按Schumacker算法，建立叢的優(yōu)先級樹。由于每一層次的八叉樹結點均按同一規(guī)律編碼，因此叢的優(yōu)先級適用于同一八叉樹的所有結點，故其消隱算法的時間復雜度呈線性關系即O(n)，其中n為所要顯示物體的體元數(shù)目。

計算物體的體積（或質量）則更為簡單。實際上，只需從物體的八叉樹的根結點開始，逐層計算所表示物體的最大和最小體積（質量）。當標識為“Patial”的體元以“Full”計時得最大體積（質量），若不計入時得最小體積（質量）。由于樹的每一層都是在一定精度下對所表示物體的一種近似，因此若所得的最大最小體積（質量）之差小于給定的誤差，計算即結束。

當前42頁，總共107頁。事實上，由于八叉樹中物體由一系列的體元表示，因此對物體的各項操作都可以轉化為對體元的操作。體元是一種非常規(guī)則的形體（立方體），因此可大大地簡化算法。其次，對物體上各體元的操作可以并行處理，這就為實時實體造型和物體的各種實時分析計算以及顯示開辟了道路。

采用八叉樹表示物體的最大缺點是它占用存儲很多。這是因為每一體元都是立方體，且體元各表面分別與三個坐標平面平行。只有當所表示的物體具有相似的形狀和位置時，才會獲得簡潔的八叉樹表示。在一般情況下，一個普通物體相應的八叉樹可能多達數(shù)千個結點。即使像圓柱、球這樣規(guī)則的物體，如用大大小小的立方體來逼近，相應八叉樹上體元的數(shù)目也是相當可觀的。

當前43頁，總共107頁。在每一個八叉樹結點中，除去一個描述該結點性質的域外，還需存儲它指向父結點及八個子結點地址的指針。定義物體的八叉樹所需的眾多的結點連同描述每個結點的10個存儲域，使得物體的八叉樹表示在空間花費上十分昂貴。實際上，八叉樹表示以存儲空間換取了算法的時間效率。

如果每次將空間分成二等分而不是八等分，這種表示方法類似于八叉樹表示法，稱為BSP（BinarySpacePartitioning）樹表示法。BSP樹表示法每次將一個物體用任一位置和任一方向的平面分為二部分。在八叉樹中，每次將物體用平行于笛卡爾坐標平面的三個兩兩垂直的平面分割。

當前44頁，總共107頁。對使用空間細分法而言，BSP樹提供了一種更有效的分割，因為可將分割平面的位置和方向按適合于物體的空間屬性來確定。與八叉樹相比，可以減少樹的表示深度，這樣減少搜索樹的時間。

6.3.1布爾運算的概念在幾何造型中，布爾運算主要用于二維實體和三維實體的復雜造型。三維實體的布爾運算比較復雜，下面僅討論二維多邊形實體的布爾運算。

6.3布爾運算當前45頁，總共107頁。多邊形的布爾運算指的是；在兩個多邊形之間進行并、交、差的運算。見圖6.10所示。

圖6.10多邊形的布爾運算

設有兩個多邊形A和B，它們之間進行布爾運算的結果如下：

當前46頁，總共107頁。

(a)表示兩個多邊形A和B并的結果，記作A∩B。其結果中是既有A的部分也有B的部分。

(b)表示A和B進行交運算的結果，記作A∪B。其結果是只有A和B的共同部分。

(c)表示A和B進行差運算的結果，記作A—B。其結果是在A中去掉了B的部分。

任何一個多邊形是由頂點和邊組成的。我們把描述多邊形的數(shù)據(jù)結構組織成兩張數(shù)據(jù)表：頂點表和邊表。

在進行布爾運算的過程中，為了算法處理的方便，我們可以把多邊形的邊表改為環(huán)表。環(huán)表是由組成多邊形的頂點按一定的順序連接而成。

6.3.2多邊形的描述當前47頁，總共107頁。因為一個平面多邊形可以只有一個外輪廓，如圖6.11中的(左)；也可以既有一個外輪廓，又有一個或多個內輪廓(即孔)，如圖6.11中的(右)。我們稱由外輪廓頂點組成的環(huán)為外環(huán)；由內輪廓頂點組成的環(huán)為內環(huán)。并且規(guī)定：外環(huán)由外輪廓頂點按逆時針方向組成；內環(huán)由內輪廓頂點按順時針方向組成。

所以在圖6.11中，外環(huán)為

1—2—3—4—5—6—1；內環(huán)為

7—8—9—10—7。

12345612345678910圖6.11多邊形的環(huán)表

當前48頁，總共107頁。在環(huán)表中，每相鄰兩個頂點組成一條有向線段，它的方向與環(huán)的方向相同，這些有向線段即是多邊形的邊。

兩個多邊形能進行布爾運算的前提是，這兩個多邊形必須有相互重疊的部分。這可以應用多邊形的重疊性檢驗來判斷。

多邊形重疊性檢驗用到了“最小最大試驗法”，這種方法也被稱為“排斥試驗”。在二維圖形中，該方法可以用來快速判斷兩個多邊形是否會有可能相互重疊，迅速排除掉不可能相互重疊的情況，從而減少計算工作量，加快圖形處理的速度

6.3.3多邊形重疊性檢驗當前49頁，總共107頁。①多邊形的最小包含矩形所謂多邊形的最小包含矩形，是指在平面上能包含該多邊形的最小的矩形。該矩形的四條邊分別平行于兩坐標軸，所以矩形的位置和大小可以用Xmax，Xmin，Ymax，Ymin四個參數(shù)來定義，而這四個參數(shù)就是多邊形頂點坐標中的極值。見圖6.12所示。

YXymaxyminxminxmax圖6.12最小包含矩形

當前50頁，總共107頁。②重疊性檢驗為了快速排除兩個多邊形互不重疊的情況，可以利用多邊形的最小包含矩形。見圖6.13所示。

(a)(b)(c)圖6.13重疊性檢驗當前51頁，總共107頁。如果兩個多邊形的最小包含矩形不發(fā)生相互重疊，則這兩個多邊形必定不會相互重疊，見圖6.13中的(a)。此時，必定有如下四個不等式中的一個得到滿足。即：

Xamax≤Xbmin；

Xamin≥Xbmax；

Yamax≤Ybmin；

Yamin

≥Ybmax。

只有當兩個最小包含矩形發(fā)生相互重疊的情況下，即上述四個不等式均得不到滿足時，這兩個小包含矩形所包含的多邊形才有可能互相重疊。這里說的也僅僅是有可能，也就是還會有重疊的可能，見圖6.13中的(b)。此時為了進一步地確定多邊形是否會確實相互重疊，則還要進行更深一步的逐邊判斷。

當前52頁，總共107頁。當兩個多邊形相互重疊時，分別表示兩多邊形的兩個環(huán)相交，其交點將相交的兩條有向線段分為兩部分：環(huán)內部分和環(huán)外部分，分別表示處于另一個環(huán)的內部或外部。交點分為出點和入點兩種：當一個環(huán)的有向線段經(jīng)過交點進入另一環(huán)，則該交點稱為入點；反之，如果是走出另一環(huán)，而該交點稱為出點。對于同一個交點，相對于不同的環(huán)來說，其出點和入點是不同的。

當兩個環(huán)由于相交而產(chǎn)生新的交點后，因新交點的加入而使得原來的環(huán)擴充了。見圖6.14所示。

111234567891012AB圖6.14中間擴充環(huán)的形成

6.3.4布爾運算的規(guī)則當前53頁，總共107頁。圖中，多邊形A的環(huán)由原來的1-2-3-4-1，擴充為：1-9(入點)-2-11(出點)-3-4-1；多邊形B的環(huán)由原來的5-6-7-8-5，擴充為：5-6-7-12(入點)-8-10(出點)-5。

從圖中可以對照看出：點9和點10，點11和點12，原本分別為同一個交點，這里由于分別處在兩個環(huán)上，為了說明的方便，所以分開標識。

在進行布爾運算時，搜索路徑應從交點處開始。其運算的規(guī)則如下：

當前54頁，總共107頁。①并運算順著環(huán)的方向搜索，當遇到的交點為入點時，則從該點在另一環(huán)上的對應點轉入另一環(huán)，而沿另一環(huán)的方向搜索；當遇到的交點為出點時，則繼續(xù)順本環(huán)進行。見圖6.15所示。

191056712113419(入)211(出)3410(出)56712(入)8圖6.15并運算規(guī)則

當前55頁，總共107頁。②交運算交運算的規(guī)則剛好和并運算的規(guī)則相反。當遇到的交點為出點時，則從該點在另一環(huán)上的對應點轉入另一環(huán)，順另一環(huán)的方向進行；如遇到的交點為入點時，則仍沿本環(huán)的方向進行。見圖6.16所示。

19(入)211(出)3410(出)56712(入)889,10211,12圖6.16交運算規(guī)則

當前56頁，總共107頁。③差運算在進行差運算的時候，首先要將差環(huán)的方向倒轉過來，然后按照同并運算相同的規(guī)則進行處理。見圖6.17所示。

419,10811,12319(入)211(出)3410(出)56712(入)8圖6.17差運算規(guī)則

綜合運用并、交、差運算，可以完成復雜平面圖形的構形。

當前57頁，總共107頁。根據(jù)以上我們對多邊形布爾運算的分析，可以歸納出簡要的算法步驟如下：①建立參加布爾運算多邊形的頂點表和環(huán)表；②應用多邊形重疊性檢驗，判別兩多邊形的關系；③求出兩多邊形邊的有效交點，擴充頂點表和環(huán)表，并分別標識交點為出點或入點；④以一個交點為出發(fā)點，按布爾運算的規(guī)則進行搜索；⑤按照搜索經(jīng)過的路徑，在頂點之間連線輸出。也可以在搜索的過程中記錄下路徑，待搜索結束后，按照記錄下的路徑頂點統(tǒng)一繪線輸出。

當前58頁，總共107頁。6.4分形幾何造型

一直以來，歐氏幾何是人們認識自然物體形狀的有力工具。歐氏幾何的主要描述工具是直線、平滑的曲線、平面及邊界整齊的平滑曲面，這些工具在描述一些抽象圖形或人造物體的形態(tài)時是非常有力的，但對一些復雜的自然景象形態(tài)就顯得無能為力了，諸如山、樹、草、火、云、浪等，如果用直線、圓弧、樣條曲線等去建模生成，則其逼真程度就非常差。這是由于從歐氏幾何來看，它們是極端無規(guī)則的。

當前59頁，總共107頁。6.4.1分形和分形幾何造型的概念

為了解決復雜圖形生成，分維幾何（Fractal）造型應運而生。另外，在科學研究中，對許多非規(guī)則對象建模分析，如：星系分布、凝聚生長、滲流、金融市場的價格浮動等復雜對象，都需要一種新的幾何學來描述。

對復雜現(xiàn)象的探索早在圖形學產(chǎn)生以前就已經(jīng)開始，可以回溯到1904年。當時HeigeVonKoch研究了一種他稱為雪花的圖形，他將一個等邊三角形的三邊都三等分，在中間的那一段上再凸起一個小正三角形，這樣一直下去，理論上可證明這種不斷構造成的雪花周長是無窮，但其面積卻是有限的。當前60頁，總共107頁。這和正統(tǒng)的數(shù)學直觀是不符的，周長和面積都無法刻劃出這種雪花的特點，歐氏幾何對這種雪花的描述無能為力。

20世紀60年代開始，曼德布羅特(B.B.Mandelbrot)重新研究了這個問題，并將雪花與自然界的海岸線、山、樹等自然景象聯(lián)系起來，找出了其中的共性。

1973年，曼德布羅特在法蘭西學院講課時，首次提出了分形和分形幾何的概念。Fractal（分形或分數(shù)維）這個詞，是曼德布羅特創(chuàng)造出來的，其原意具有不規(guī)則、支離破碎等意義。分形幾何是一門以非規(guī)則幾何形狀為研究對象的幾何學。

當前61頁，總共107頁。曼德布羅特曾舉了一個海岸線的例子來說明他的理論。假設我們要測量不列顛的海岸線長度，我們可以用一個1000m的尺子，一尺一尺地向前量，同時數(shù)出有多少個1000m，這樣得到一個長度為L1。然而這樣測量會漏掉許多小于1000m的小灣，因而結果不準確。如果尺子縮到1m，那么我們會得到一個新的結果L2，顯然L2＞L1。一般來說，如果用長度為r的尺子來量，將會得到一個與r有關的數(shù)值L（r）。與Koch的雪花一樣r→0，L（r）→∝。也就是說，不列顛的海岸線長度是不確定的，它與測量用的尺子長度有關。

當前62頁，總共107頁。曼德布羅特注意到Koch雪花與海岸線的共同特點：它們都有細節(jié)的無窮回歸，測量尺度的減少都會得到更多的細節(jié)。換句話說，就是將其中一部分放大會得到與原來部分基本一樣的形態(tài)，這就是曼德布羅特發(fā)現(xiàn)的復雜現(xiàn)象的自相似性。為了定量地刻劃這種自相似性，他引入了分數(shù)維（Fractal）概念，這是與歐氏幾何中整數(shù)維相對應的。

6.4.2分形維數(shù)和分形幾何造型當前63頁，總共107頁。設N為每一步細分的數(shù)目，S為細分時的放大（縮?。┍稊?shù)，則分數(shù)維D定義為：

圖6.18用分形幾何造型產(chǎn)生雪花

如圖6.18所示，以Koch雪花為例，它的每一步細分線段的個數(shù)為4，而細分時的放大倍數(shù)為1／3，則雪花邊線的分數(shù)維D=log4/log3=1.2619。如果我們按歐氏幾何的方法，將一線段四等分，則N=4，S=1/4，D=1；如將一正方形16等分，此時N=16，線段的放大倍數(shù)S=1/4，則D=2。

當前64頁，總共107頁。一般說，二維空間中的一個分數(shù)維曲線的維數(shù)介于1和2之間；三維空間中的一個分數(shù)維曲線的維數(shù)在1和3之間，而三維空間中的一個分數(shù)維曲面的維數(shù)在2和3之間。分數(shù)維的引入，為研究復雜形體提供了全新的角度，使人們從無序中重新發(fā)現(xiàn)了有序，許多學科像物理、經(jīng)濟、氣象等都將分數(shù)維幾何學作為解決難題的新工具。計算機圖形學也從中受到啟發(fā)，并形成了以模擬自然界復雜景象、物體為目標的分形幾何造型。分形幾何造型是利用分形幾何學的自相似性，采用各種模擬真實圖形的模型，使整個生成的景象呈現(xiàn)出細節(jié)的無窮回歸性質的方法。

當前65頁，總共107頁。

(1)從整體上看，分形幾何圖形是處處不規(guī)則的。例如，海岸線和山川形狀，從遠距離觀察，其形狀是極不規(guī)則的。

(2)在不同尺度上，圖形的規(guī)則性又是相同的。上述的海岸線和山川形狀，從近距離觀察，其局部形狀又和整體形態(tài)相似，它們從整體到局部，都是自相似的。當然，也有一些分形幾何圖形，它們并不完全是自相似的。其中一些是用來描述一般隨機現(xiàn)象的，還有一些是用來描述混沌和非線性系統(tǒng)的。

分形幾何建立以后，很快就引起了許多學科的關注，這是由于它不僅在理論上，而且在實用上都具有重要價值。與傳統(tǒng)的幾何學相比,分形幾何有這樣的特點：

當前66頁，總共107頁。總之，分形幾何與傳統(tǒng)的幾何完全不同，傳統(tǒng)的歐幾里德幾何的對象具有一定的特征長度和標度，其所描述的是人類生產(chǎn)的工業(yè)產(chǎn)品的規(guī)則形狀，分形幾何則是無特征長度與標度的，它擅長描述自然界普遍存在的景物，分形幾何的圖形具有自相似性和遞歸性，它比較適于用計算機迭代生成。

6.4.3典型分形曲線集當前67頁，總共107頁。

1904年，瑞典數(shù)學家VonKoch發(fā)現(xiàn)了一種曲線，這種曲線有一個奇怪的特性：它處處連續(xù)，但處處不光滑、不可微。因而在當時認為是一種與常規(guī)不同的“病態(tài)”曲線，即

VonKoch曲線。如果在一個正三角形上按生成規(guī)則生成，則曲線形狀像一朵雪花，故又稱為Koch雪花曲線。VonKoch曲線是一種典型的分形曲線，在分形理論的建立過程中，VonKoch曲線具有重要地位。

1.VonKoch曲線當前68頁，總共107頁。

VonKoch的生成方法如下：首先，從一個簡單的圖形出發(fā)(這個圖形稱為源圖形)，然后按照一定的生成規(guī)律不斷進行變形，最后可以得到VonKoch曲線。

源圖形通常是一條直線或一個多邊形，在曲線的生成過程中，其變形的規(guī)律是將源圖形中的直線段用一段折線來代替，此折線稱為發(fā)生器。圖6.19(左)所示為發(fā)生器，圖6.19(右)為通過5次遞歸(N=5)所生成的VonKoch曲線。

圖6.19VonKoch曲線,(a)為發(fā)生器,(b)為N=5的Koch曲線）

(a)(b)當前69頁，總共107頁。

VonKoch曲線的具體生成過程中，由源圖形和發(fā)生器就可以決定曲線的形態(tài)。源圖形為一直線段，生成的曲線如圖中所示，可用以繪制海岸線或云彩的邊界。如果源圖形為一等邊三角形，生成的曲線形狀與雪花類似，稱為Koch雪花曲線。

由Koch曲線的生成過程知道：在極限的情形下，每小段折線的長度趨于無窮小，因而此曲線是一條無處不連續(xù)但處處不可微的曲線，其上任一點處，均無確定的切線，曲線的長度趨于無窮。對于閉合多邊形的Koch曲線，可以證明它的面積為源多邊形的8／5。

當前70頁，總共107頁。

Koch曲線的維數(shù)，可用相似維數(shù)來定義。由生成曲線的過程可知，從任何一步到下一步，其周長增加為4／3，圖6.18（左）中顯而易見，整體由四個線段組成，即N=4，a=3，其維數(shù)

D=log4／log3=1.2618

Koch曲線是典型的分形曲線，它具有自相似性。其中發(fā)生器是由n段直線和確定的二個端點組成。自相似的不變集的曲線段，是通過反復用一發(fā)生器的相似圖形，來取代每一直線段的遞歸調用過程而建立起來的。

Koch曲線可以派生為各種形態(tài)，用不同的發(fā)生器，就可以得到不同類型的結構形態(tài)。

當前71頁，總共107頁。下面介紹如何用計算機繪制Koch曲線，算法的基本設計思想是：根據(jù)曲線的生成原理，由于它是通過不斷細分遞歸生成的，因此，采用遞歸調用方法，由發(fā)生器產(chǎn)生Koch曲線。算法的具體步驟是：

（1）給出遞歸深度n；（2）計算發(fā)生器遞歸n次后的最小線元長度d=L／mn,式中L為曲線總長，m為Koch曲線發(fā)生器的等分數(shù)；（3）確定Koch曲線的起點；（4）執(zhí)行遞歸子程序，對發(fā)生器的各部分進行遞歸，并繪出曲線。

當前72頁，總共107頁。以維數(shù)D=1.2618的Koch曲線為例，曲線的發(fā)生器由三等分長度的四個部分組成，中間兩段線段的角度為60°，如圖6.20所示。

(xn-1,yn-1)(xn,yn)θ圖6.20Koch曲線發(fā)生器

設逆時針旋轉時角度為正，發(fā)生器的初始角度為0，圖中已標明發(fā)生器各段的位置和角度。每一段小的線元，其坐標可由下式確定

(xs,ys)600-1200600當前73頁，總共107頁。

xn=xn-1十d·cosθ

yn=yn-1十d·sinθ其中，θ為小的線元的當前角度。

由于Koch曲線的發(fā)生器由圖中所示的四部分線段組成，因此，在計算機生成Koch曲線的遞歸調用中，要分別對這四部分進行遞歸。

voidturn(doubleangle,double&ANGLE)//當前角度旋轉{ANGLE+=angle;ANGLE=ANGLE-(int)ANGLE+(int)ANGLE%360;}以下是生成Koch曲線的VC程序：當前74頁，總共107頁。voidKoch(doubleleng,intn,intN,double&LPX,double&LPY,double&ANGLE){CGraphDCg(this);doublex,y,RADIAN=ANGLE*3.1415926/180;//角度化弧度

if(n>=N){x=LPX+leng*cos(RADIAN);y=LPY-leng*sin(RADIAN);g.MoveTo(LPX,LPY);g.LineTo(x,y);LPX=x;LPY=y;}else{Koch(leng/3,n+1,N,LPX,LPY,ANGLE);turn(60.0,ANGLE);Koch(leng/3,n+1,N,LPX,LPY,ANGLE);turn(-120.0,ANGLE);Koch(leng/3,n+1,N,LPX,LPY,ANGLE);turn(60.0,ANGLE);Koch(leng/3,n+1,N,LPX,LPY,ANGLE);}}當前75頁，總共107頁。voidOnDrawKoch(){doubleLPX=120.0,LPY=240.0;//初始坐標

doubleANGLE=0.0;Koch(400.0,0,6,LPX,LPY,ANGLE);}當前76頁，總共107頁。分形圖形中最著名的是Mandelbrot集，這是分形的創(chuàng)始者Mandelbrot在非線性分形領域中作出的杰出貢獻。這是通過在復平面中G（Z）=Z2+C的反復迭代而得到的點的序列，其中C和Z都是復數(shù)。若Z的初始值取為零，改變C值，再用計算機對每一個點按一定規(guī)則著色，即可得到Mandelbrot分形集的計算機圖像。

在復平面中，Mandelbrot分形集是通過下述迭代式產(chǎn)生的：

Zn+1

＝Zn2＋C

2.Mandelbrot分形集當前77頁，總共107頁。其中，Z和C都是復數(shù)，由各自的實部和虛部組成。其實部和虛部分別為：

xn+1

＝xn2-yn2+Cx

（實部）

yn+1

＝2*xn

*yn+cy

（虛部〕

在迭代中，令初始值Z0=0，也就是Z0=0＋0·i，C≠0，對上述迭代式反復進行迭代，得到的數(shù)集，稱為Mandellrot集，簡稱M集。

在迭代過程中，Z的初值永遠定為0，用不同的C值反復進行迭代，由此產(chǎn)生的Zk序列有兩種情況：

（1）Zk序列自由地朝著無窮大的方向擴散，即發(fā)散；（2）Zk序列被限制在復平面的某一區(qū)域內，即收斂。

當前78頁，總共107頁。如果建立一套判斷收斂與發(fā)散的判斷準則，對于那些收斂的Zk序列的點，設置某種顏色的色調，就可以顯示M集的計算機圖像。對于那些發(fā)散的Zk序列的點，根據(jù)發(fā)散速度的不同，按照給定的規(guī)則著上不同顏色的色調，就能顯示M集周圍的圖像。

在迭代計算中，通常是把前一個Z值的輸出作為下一個Z值的輸入代入Zn+1

←Zn2＋C反復運算，得到一連串的復數(shù)。每作一次迭代，新的復數(shù)就離開前一復數(shù)一段距離，就好象一個點在復平面上跳舞一樣。

在M集的計算中，距離是一個重要的概念。在一系列通過迭代計算得出的復數(shù)，有的達到無窮大，有的則永遠被限制在平面上的某個區(qū)域內。當前79頁，總共107頁。在復平面的某一部位上，令C作有規(guī)律的變化，對不同的C值進行迭代，如果計算結果達到無窮大，則C被著成白色，否則，著成黑色，這樣就能顯示出M集的形狀。若達到無窮大的點，根據(jù)其發(fā)散的速度的快慢，用不同的色調來表示，就形成一幅奇妙無窮的M集彩色圖像。

M集圖像生成算法的核心過程如下：①n←0②當n＜100，且|Z|＜2時③Z←Z2＋C④n←n＋1

⑤標示當前點的顏色（根據(jù)n的大小）當前80頁，總共107頁。

n從0開始，每迭代一次，n就增加1，只要n＜100，Z的絕對值|Z|＜2，則上述循環(huán)就不斷地重復進行下去，如果上述兩個條件之一得到滿足，就退出循環(huán)，并根據(jù)n按一定的規(guī)律著色。根據(jù)斂散速度著色是最簡單的方法。

z的絕對值也可以取|Z|<100，或更大的數(shù)如1000，等等。這是門限值，即閾值。本章是根據(jù)不同的迭代值通過某個閾值的速度的不同而進行著色的。

在M集的圖像生成中，如果將上述速度比擬為M集的靜電場的值，則生成的M集圖案就更加壯觀，有如一幅山頂湖泊的自然風景畫。當前81頁，總共107頁。下面是M集圖像生成的C語言算法程序。#include"graphics.h"#include"math.h"voidMSB(cxmin,cxmax,cymin,cymax,nmax)floatcxmin,cxmax,cymin,cymax;/*復平面C實虛部變化范圍*/intnmax;/*最大迭代次數(shù)*/{floatsx=500.0,sy=450.0;/*要顯示的圖像大小尺寸*/floatcx,cy,x,y,xx,yy,dx,dy,z,L=4.0;inti,j,n,color;dx=(cxmax-cxmin)/sx;dy=(cymax-cymin)/sy;當前82頁，總共107頁。for(i=0;i<sx;i++){cx=cxmin+i*dx;for(j=0;j<sy;j++){cy=cymin+j*dy;x=0;y=0;for(n=0;n<nmax;n++){xx=x*x-y*y+cx;yy=2*x*y+cy;z=xx+yy;if(fabs(z)>L)break;x=xx;y=yy;}color=n%16;putpixel(i+50,j+40,color);/*50,40為畫圖起點*/}}}當前83頁，總共107頁。main(){intgdriver=DETECT,gmode;initgraph(&gdriver,&gmode,"");/*x的取值為-2.25至1.75，y取值為-1.8至1.5*/MSB(-2.25,1.75,-1.8,1.5,100);getch();}當前84頁，總共107頁。

Julia的分形集也是復平面上的點列，它是Mandelbrot圖形中一些周邊瘤包的放大部分，Mandelbrot圖形可看作是Julia集合的縮圖。Julia集合可分為Zc為實數(shù)、Zc為復數(shù)、三次函數(shù)和發(fā)散區(qū)域幾種情況。

(1)Zc為實數(shù)的Julia集合對于復數(shù)數(shù)列

Zn=Z2n-1+Zc(Zc為實數(shù))生成的點列，因復數(shù)常量Zc和初值Z0的不同值，有4種動向，即收斂、振動、無秩序、發(fā)散。對于某個Zc，數(shù)列不發(fā)散的初值Z0的集合稱為Julia集合，不發(fā)散即意味著必為收斂、振動、無秩序三者之一。

3.Julia分形集當前85頁，總共107頁。固定Zc后，定下復數(shù)平面上某區(qū)域，對于該區(qū)域內的所有的點，看看將這些點作為初值的點列的動向，對于各個值，根據(jù)動向的不同分別用下列顏色表示：

l收斂，用1號色（藍色）ln(2~13)周期的振動用n號色，但8周期時用14號色（淡黃）這樣用所賦予的色彩描繪點時，有色部分即為Julia集合。

l14以上周期的振動用15號色（白）l無秩序用15號色l發(fā)散則不畫當前86頁，總共107頁。

(2)Zc為復數(shù)的Julia集合

Zc為實數(shù)時的Julia集合是關于x和y軸都對稱的圖形，而當Zc為復數(shù)時，這種對稱性就不存在了，只有繞原點旋轉1800的對稱性，即所謂點對稱圖形。

生成Zc為復數(shù)的Julia集合只需給出復數(shù)的初始值即可。

(3)三次函數(shù)的Julia集合若將Mandelbrot分形集的迭代式由2次換成3次：

Zn+1

＝Zn3＋C其中，Z和C都是復數(shù)，由各自的實部和虛部組成。當前87頁，總共107頁。則其實部和虛部分別變更為：

xn+1

＝xn3-3xnyn2+Cx

（實部）

yn+1

＝3xn2

yn–yn3+cy

（虛部）

3次函數(shù)的Julia集合是繞原點旋轉的3次對稱。

(4)發(fā)散區(qū)域的Julia集合從眾多所描畫的Julia、Mandelbrot集合的圖形可以看出，在集合外部有許多復雜的條紋花樣，這部分區(qū)域即為發(fā)散區(qū)域，這些條紋花樣可根據(jù)發(fā)散速度來分類。當前88頁，總共107頁。如前所述，在復數(shù)數(shù)列

Zn+1

＝Zn2＋C中，Zn+1的絕對值為2以上（Zn+1絕對值的平方4以上）的話，則該數(shù)列是發(fā)散的，也即在描畫以原點為中心、半徑為2的圓時，對于某個n，如果Zn+1跳到圓外，那么它不會再回到圓內。以z0=x0+y0i為初值，按z1,z2,…順序進行計算，使Zn+1跳到圓外。在下面程序中，對于點(x0,y0)，將賦予由二維數(shù)組col[][2]和函數(shù)getcol指定的顏色號碼，數(shù)組為

intcol[][2]={{2,3},{4,6},{8,5},{16,2},{32,4},{64,1},{201,7}};時，n和描畫顏色之間的關系如下：

當前89頁，總共107頁。

l

1≤n≤2顏色為3號（青色）

l

2<n≤4顏色為6號（棕色）

l

4<n≤8顏色為5號（紫紅色）不發(fā)散時，與前面相反，什么也不描畫，這樣一來就可描畫出周圍有條紋話樣的黑色分形集合。以下是生成Julia集合的VC源程序。

l

8<n≤16顏色為2號（綠色）

l

16<n≤32顏色為4號（紅色）

l

32<n≤64顏色為1號（藍）

l

64<n≤KL+1顏色為7號（淺灰色）當前90頁，總共107頁。voidjulia(doublex0,doubley0,doublexc,doubleyc,intsx,intsy){inti,k,KL=200;//KL為計算精度,也是數(shù)列個數(shù)

doubles,BOX=0.01;intcx=320,cy=240;//繪圖中點

intcol[][2]={{2,3},{4,6},{8,5},{16,2},{32,4},{64,1},{201,7}};staticdoublex[201],y[201];//存儲數(shù)列的數(shù)組

CGraphDCdc(this);COLORREFcolor;x[0]=x0;y[0]=y0;當前91頁，總共107頁。for(k=1;k<=KL;k++)//計算復數(shù)數(shù)列{if(Num<29){//二次函數(shù)

x[k]=x[k-1]*x[k-1]-y[k-1]*y[k-1]+xc;//實部

y[k]=2*x[k-1]*y[k-1]+yc;//虛部

}else{//三次函數(shù)

x[k]=x[k-1]*x[k-1]*x[k-1]-3*x[k-1]*y[k-1]*y[k-1]+xc;y[k]=3*x[k-1]*x[k-1]*y[k-1]-y[k-1]*y[k-1]*y[k-1]+yc;}s=x[k]*x[k]+y[k]*y[k];當前92頁，總共107頁。

if(s>=4.0)//發(fā)散

{if(Num>=21&&Num<=28)//描畫發(fā)散區(qū)域

{i=0;while(k>col[i][0]&&k<=KL) i++;color=dc.GetColor(col[i][1]);dc.SetPixel(cx+sx,cy-sy,color);}return;}}當前93頁，總共107頁。

if(s<4.0&&(Num<21||Num>28)){//非發(fā)散情況（收斂、振動、無秩序）

for(k=1;k<=13;k++)//周期點數(shù)計算，根據(jù)點數(shù)著色

{//從數(shù)列的最后項起若第k項落在以最后一項為中心

+-BOX的小正方形內，則周期點數(shù)為k if(fabs(x[KL]-x[KL-k])<BOX&&fabs(y[KL]-y[KL-k])<BOX) {color=dc.GetColor(k);dc.SetPixel(cx+sx,cy+sy,color); return; }}//無秩序用15號白色描畫，周期點數(shù)14以上時也用白色

color=dc.GetColor(15);dc.SetPixel(cx+sx,cy+sy,color);}}當前94頁，總共107頁。voidDrawJulia(intNum)//Num為子菜單序號{intcx=320,cy=240;//繪圖中點

intsx,sy,dx=192,dy=192;//繪圖區(qū)域x,y軸均為-192~192doublex_min=-1.5,x_max=1.5,y_min=-1.5,y_max=1.5;doublex0,y0,xc,yc;switch(Num){//下面4個為實數(shù)

case1:xc=-0.6;yc=0.0;break;//實數(shù)初始值

case2:xc=-0.85;yc=0.0;break;case3:xc=-1.1;yc=0.0;break;case4:xc=-1.35;yc=0.0;break;}當前95頁，總共107頁。//下面18個為復數(shù)case5:xc=-1.1;yc=0.2;break;case6:xc=-0.1;yc=0.77;break;case7:xc=0.3;yc=0.5;break;case8:xc=-0.52;yc=0.55;break;case9:xc=-1.15;yc=0.25;break;ca