圖形的表示與數(shù)據(jù)結(jié)構(gòu)

圖形的表示與數(shù)據(jù)結(jié)構(gòu)第1頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第1頁。

造型技術(shù):

把研究如何在計算機中建立恰當(dāng)?shù)哪Ｐ捅硎静煌瑘D形對象的技術(shù)稱為造型技術(shù)。 有兩類圖形對象：

規(guī)則對象：幾何造型、幾何模型

不規(guī)則對象第2頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第2頁。4.1.1基本圖形元素4.1基本概念基本圖形元素：圖素或圖元、體素圖素是指可以用一定的幾何參數(shù)和屬性參數(shù)描述的最基本的圖形輸出元素。包括點、線、圓、圓弧、橢圓、二次曲線等。體素是三維空間中可以用有限個尺寸參數(shù)定位和定形的形體。WLHHRHR（a）方塊（b）圓柱（c）圓錐第3頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第3頁。通常的基本圖形元素包括：點、線、面、環(huán)、體等。

點是0維幾何元素，分端點、交點、切點和孤立點等。

邊是1維幾何元素，是兩個鄰面（正則形體）或多個鄰面（非正則形體）的交界。直線邊、曲線邊第4頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第4頁。面是2維幾何元素，是形體上一個有限、非零的區(qū)域，由一個外環(huán)和若干個內(nèi)環(huán)界定其范圍。一個面可以無內(nèi)環(huán)，但必須有一個且只有一個外環(huán)。面有方向性，以其外法線矢量方向為該面的正向。第5頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第5頁。環(huán)是有序、有向邊（真線段或曲線段）組成的面的封閉邊界。環(huán)中的邊不能相交，相鄰兩條邊共享一個端點確定面的最大外邊界的環(huán)稱之為外環(huán)確定面中內(nèi)孔或凸臺邊界的環(huán)稱之為內(nèi)環(huán)第6頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第6頁。

體是3維幾何元素，由封閉表面圍成空間，也是歐氏空間R3中非空、有界的封閉子集，其邊界是有限面的并集。第7頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第7頁。4.1.2幾何信息與拓撲信息圖形對象及構(gòu)成它的點、線、面的位置、相互間關(guān)系和幾何尺寸等都是圖形信息；表示圖形對象的線型、顏色、亮度以及供模擬、分析用的質(zhì)量、比重、體積等數(shù)據(jù)，是有關(guān)對象的非圖形信息。第8頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第8頁。圖形信息往往從幾何信息及拓撲信息兩方面考慮。幾何信息：形體在歐氏空間中的位置和大小(物體的各部分幾何形狀及其在空間的位置)拓撲信息：形體各分量（點、邊、面）的數(shù)目及其相互間的連接關(guān)系。1.幾何信息(1)幾何分量的數(shù)學(xué)表示,如：點:(x,y,z)

直線：x=(y-y0)/a=(z-z0)/b平面：ax+by+cz+b=0第9頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第9頁。(2)幾何分量之間的相互關(guān)系(拓撲信息)第10頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第10頁。幾何信息的二義性2.拓樸信息平面立體的幾何分量之間一共有九種拓撲關(guān)系第11頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第11頁。第12頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第12頁。4.1.3坐標(biāo)系第13頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第13頁。4.1.4實體的定義(a)有懸面(b)有懸邊第14頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第14頁?？陀^存在的三維形體具有這樣一些性質(zhì)：(1)剛性(2)維數(shù)的一致性(3)占據(jù)有限的空間(4)邊界的確定性(5)封閉性三維空間中的物體是一個內(nèi)部連通的三維點集，是由其內(nèi)部的點集及緊緊包著這些點的表皮組成的。第15頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第15頁。利用正則集的概念來定義上述的三維有效物體：由內(nèi)部點構(gòu)成的點集的閉包就是正則集，三維空間中正則集就是正則形體，也就是三維有效物體。第16頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第16頁。定義點集的正則運算r運算為：正則運算即為先對物體取內(nèi)點再取閉包的運算。r·A稱為A的正則集。第17頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第17頁。圖4-7正則形體第18頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第18頁。

二維流形指的是對于實體表面上的任意一點，都可以找到一個圍繞著它的任意小的領(lǐng)域，該領(lǐng)域與平面上的一個圓盤是拓撲等價的。第19頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第19頁。實體：對于一個占據(jù)有限空間的正則形體，如果其表面是二維流形，則該正則形體為實體。歐拉公式是檢查實體有效性的一個必要條件（不是充分條件）4.1.7平面多面體與歐拉公式第20頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第20頁。簡單多面體條件：（1）所在面是單連通的，上面沒有洞（2）立體是單連通的，而且沒有孔洞（3）每條棱邊上恰好鄰接兩個面（4）每一個頂點處至少有三條棱邊相遇其頂點數(shù)V、邊數(shù)E和面數(shù)F滿足如下關(guān)系：

V-E+F=2。第21頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第21頁。

V-E+F=2第22頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第22頁。 令H表示多面體表面上孔的個數(shù)，G表示貫穿多面體的孔的個數(shù)，C表示獨立的、不相連接的多面體數(shù)，則擴展后的歐拉公式為：V-E+F-H=2(C-G)V=24E=36F=16H=2C=1G=0第23頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第23頁。線框模型由定義一個物體的直線和曲線組成，每一條直線和曲線都是單獨構(gòu)造出來的，并不存在面的信息。線框模型存在著幾個缺陷：二義性4.2三維形體的表示第24頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第24頁。容易構(gòu)造出無效形體第25頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第25頁。不能正確表示曲面信息。無法進行圖形的線面消隱。

加重用戶的輸入負擔(dān)難以保證數(shù)據(jù)的統(tǒng)一性和有效性。第26頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第26頁。可以將實體模型的表示可分為以下方法：邊界表示法（BR）掃描表示法構(gòu)造實體幾何法（CSG）空間位置枚舉表示法八叉樹法二叉空間分割法（BSP）第27頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第27頁。4.2.1多邊形表面模型 邊界表示(B-reps)的最普遍方式是多邊形表面模型，它使用一組包圍物體內(nèi)部的平面多邊形，也即平面多面體，來描述實體。第28頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第28頁。第29頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第29頁。 1.多邊形表幾何表屬性表

例如：頂點表、邊表和多邊形表。 為圖4-17所示的四面體建立的三張表如下：第30頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第30頁。頂點表

邊表

面表Ax1,y1,z1

ABA,B

ABCAB,BC,ACBx2,y2,z2

BCB,C

ABDAB,BD,ADCx3,y3,z3

CAC,A

BCDBC,CD,BDDx4,y4,z4

ADA,D

ACDAC,CD,AD

BCB,C

CDC,D

第31頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第31頁。表示其拓撲信息

例如，翼邊結(jié)構(gòu)表示（WingedEdgesStructure）第32頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第32頁。 2.平面方程

可以利用平面方程：Ax+By+Cz+D=0求得平面的法向量鑒別空間上的點與物體平面的位置關(guān)系。判別點在面的內(nèi)部或外部實體存在側(cè)方法——平面法向量法向量指向物體外部，當(dāng)多邊形頂點指定為逆時針方向時，法向量方向滿足右手定則。第33頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第33頁。3.多邊形網(wǎng)格 三維形體的曲面邊界通常用多邊形網(wǎng)格（polygonmesh）的拼接來模擬。 三角形帶、四邊形網(wǎng)格第34頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第34頁。4.2.2掃描表示掃描表示法（sweeprepresentation）可以利用簡單的運動規(guī)則生成有效實體。

包含兩個要素：一是作掃描運動的基本圖形；二是掃描運動的方式:平移、旋轉(zhuǎn)。第35頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第35頁。掃描方向基面回轉(zhuǎn)軸基面基面基面（a）（b）（c）（d）第36頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第36頁。4.2.3構(gòu)造實體幾何法構(gòu)造實體幾何法（CSG，ConstructiveSolidGeometry）由兩個實體間的并、交或差操作生成新的實體。第37頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第37頁。在構(gòu)造實體幾何法中，集合運算的實現(xiàn)過程可以用一棵二叉樹（稱為CSG樹）來描述：樹的葉子：體素或形體變換參數(shù)。樹的非終端結(jié)點：正則的集合運算或變換（平移或旋轉(zhuǎn)）操作二叉樹根結(jié)點：構(gòu)造的實體第38頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第38頁。第39頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第39頁。構(gòu)造實體幾何法的優(yōu)點：可以構(gòu)造出多種不同的符合需要的實體。問題：求交困難CSG樹不能顯式地表示形體的邊界解決：光線投射（Ray-casting）算法第40頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第40頁。光線投射（Ray-casting）算法：具體算法是：1)將射線與CSG樹中的所有基本體素求交，求出所有的交點。2)將所有交點相對于CSG樹表示的物體進行分類，確定位于物體邊界上的那部分交點。3)對所有位于物體邊界上的交點計算它們在射線上的參數(shù)值并進行排序，確定距離最近的交點。得到其所在基本體素表面的法矢量。第41頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第41頁。第42頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第42頁。4.2.4空間位置枚舉表示空間位置枚舉表示法將包含實體的空間分割為大小相同、形狀規(guī)則（正方形或立方體）的體素，然后，以體素的集合來表示圖形對象。二維情況，常用二維數(shù)組存放。三維情況下，常用三維數(shù)組p[i][j][k]來存放。P98圖4-29第43頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第43頁。4.2.5八叉樹 八叉樹（octrees）又稱為分層樹結(jié)構(gòu)，它對空間進行自適應(yīng)劃分，采用具有層次結(jié)構(gòu)的八叉樹來表示實體。第44頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第44頁。四叉樹第45頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第45頁。八叉樹第46頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第46頁。012356712337（a）（b）具有子孫的節(jié)點空節(jié)點實節(jié)點

（c）01234567第47頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第47頁。4.2.6BSP樹 二叉空間分割（binaryspacepartitioning，BSP）方法每次將一實體用任一位置和任一方向的平面分為二部分。第48頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第48頁。4.3.1分形幾何(fractalgeometry)分形幾何物體具有一個基本特征：無限的自相似性。無限的自相似性是指物體的整體和局部之間細節(jié)的無限重現(xiàn)。分形物體的描述又包含：分形維數(shù)，又稱分?jǐn)?shù)維數(shù)生成過程：初始生成元（initiator）、生成元（genenator）4.3非規(guī)則對象的表示第49頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為