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

圖形的表示與數(shù)據(jù)結(jié)構(gòu)第一頁，共五十五頁，編輯于2023年，星期二

造型技術(shù):

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

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

不規(guī)則對象第二頁，共五十五頁，編輯于2023年，星期二4.1.1基本圖形元素4.1基本概念基本圖形元素：圖素或圖元、體素圖素是指可以用一定的幾何參數(shù)和屬性參數(shù)描述的最基本的圖形輸出元素。包括點、線、圓、圓弧、橢圓、二次曲線等。體素是三維空間中可以用有限個尺寸參數(shù)定位和定形的形體。WLHHRHR（a）方塊（b）圓柱（c）圓錐第三頁，共五十五頁，編輯于2023年，星期二通常的基本圖形元素包括：點、線、面、環(huán)、體等。

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

邊是1維幾何元素，是兩個鄰面（正則形體）或多個鄰面（非正則形體）的交界。直線邊、曲線邊第四頁，共五十五頁，編輯于2023年，星期二面是2維幾何元素，是形體上一個有限、非零的區(qū)域，由一個外環(huán)和若干個內(nèi)環(huán)界定其范圍。一個面可以無內(nèi)環(huán)，但必須有一個且只有一個外環(huán)。面有方向性，以其外法線矢量方向為該面的正向。第五頁，共五十五頁，編輯于2023年，星期二環(huán)是有序、有向邊（真線段或曲線段）組成的面的封閉邊界。環(huán)中的邊不能相交，相鄰兩條邊共享一個端點確定面的最大外邊界的環(huán)稱之為外環(huán)確定面中內(nèi)孔或凸臺邊界的環(huán)稱之為內(nèi)環(huán)第六頁，共五十五頁，編輯于2023年，星期二

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

直線：x=(y-y0)/a=(z-z0)/b平面：ax+by+cz+b=0第九頁，共五十五頁，編輯于2023年，星期二(2)幾何分量之間的相互關(guān)系(拓撲信息)第十頁，共五十五頁，編輯于2023年，星期二幾何信息的二義性2.拓樸信息平面立體的幾何分量之間一共有九種拓撲關(guān)系第十一頁，共五十五頁，編輯于2023年，星期二第十二頁，共五十五頁，編輯于2023年，星期二4.1.3坐標(biāo)系第十三頁，共五十五頁，編輯于2023年，星期二4.1.4實體的定義(a)有懸面(b)有懸邊第十四頁，共五十五頁，編輯于2023年，星期二客觀存在的三維形體具有這樣一些性質(zhì)：(1)剛性(2)維數(shù)的一致性(3)占據(jù)有限的空間(4)邊界的確定性(5)封閉性三維空間中的物體是一個內(nèi)部連通的三維點集，是由其內(nèi)部的點集及緊緊包著這些點的表皮組成的。第十五頁，共五十五頁，編輯于2023年，星期二利用正則集的概念來定義上述的三維有效物體：由內(nèi)部點構(gòu)成的點集的閉包就是正則集，三維空間中正則集就是正則形體，也就是三維有效物體。第十六頁，共五十五頁，編輯于2023年，星期二定義點集的正則運算r運算為：正則運算即為先對物體取內(nèi)點再取閉包的運算。r·A稱為A的正則集。第十七頁，共五十五頁，編輯于2023年，星期二圖4-7正則形體第十八頁，共五十五頁，編輯于2023年，星期二

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

V-E+F=2。第二十一頁，共五十五頁，編輯于2023年，星期二

V-E+F=2第二十二頁，共五十五頁，編輯于2023年，星期二 令H表示多面體表面上孔的個數(shù)，G表示貫穿多面體的孔的個數(shù)，C表示獨立的、不相連接的多面體數(shù)，則擴展后的歐拉公式為：V-E+F-H=2(C-G)V=24E=36F=16H=2C=1G=0第二十三頁，共五十五頁，編輯于2023年，星期二線框模型由定義一個物體的直線和曲線組成，每一條直線和曲線都是單獨構(gòu)造出來的，并不存在面的信息。線框模型存在著幾個缺陷：二義性4.2三維形體的表示第二十四頁，共五十五頁，編輯于2023年，星期二容易構(gòu)造出無效形體第二十五頁，共五十五頁，編輯于2023年，星期二不能正確表示曲面信息。無法進行圖形的線面消隱。

加重用戶的輸入負擔(dān)難以保證數(shù)據(jù)的統(tǒng)一性和有效性。第二十六頁，共五十五頁，編輯于2023年，星期二可以將實體模型的表示可分為以下方法：邊界表示法（BR）掃描表示法構(gòu)造實體幾何法（CSG）空間位置枚舉表示法八叉樹法二叉空間分割法（BSP）第二十七頁，共五十五頁，編輯于2023年，星期二4.2.1多邊形表面模型 邊界表示(B-reps)的最普遍方式是多邊形表面模型，它使用一組包圍物體內(nèi)部的平面多邊形，也即平面多面體，來描述實體。第二十八頁，共五十五頁，編輯于2023年，星期二第二十九頁，共五十五頁，編輯于2023年，星期二 1.多邊形表幾何表屬性表

例如：頂點表、邊表和多邊形表。 為圖4-17所示的四面體建立的三張表如下：第三十頁，共五十五頁，編輯于2023年，星期二頂點表

邊表

面表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

第三十一頁，共五十五頁，編輯于2023年，星期二表示其拓撲信息

例如，翼邊結(jié)構(gòu)表示（WingedEdgesStructure）第三十二頁，共五十五頁，編輯于2023年，星期二 2.平面方程

可以利用平面方程：Ax+By+Cz+D=0求得平面的法向量鑒別空間上的點與物體平面的位置關(guān)系。判別點在面的內(nèi)部或外部實體存在側(cè)方法——平面法向量法向量指向物體外部，當(dāng)多邊形頂點指定為逆時針方向時，法向量方向滿足右手定則。第三十三頁，共五十五頁，編輯于2023年，星期二3.多邊形網(wǎng)格 三維形體的曲面邊界通常用多邊形網(wǎng)格（polygonmesh）的拼接來模擬。 三角形帶、四邊形網(wǎng)格第三十四頁，共五十五頁，編輯于2023年，星期二4.2.2掃描表示掃描表示法（sweeprepresentation）可以利用簡單的運動規(guī)則生成有效實體。

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

（c）01234567第四十七頁，共五十五頁，編輯于2023年，星期二4.2.6BSP樹 二叉空間分割（binaryspacepartitioning，BSP）方法每次將一實體用任一位置和任一方向的平面分為二部分。第四十八頁，共五十五頁，編輯于2023年，星期二4.3.1分形幾何(fractalgeometry)分形幾何物體具有一個基本特征：無限的自相似性。無限的自相似性是指物體的整體和局部之間細節(jié)的無限重現(xiàn)。分形物體的描述又包含：分形維數(shù)，又稱分?jǐn)?shù)維數(shù)生成過程：初始生成元（initiator）、生成元（genenator）4.3非規(guī)則對象的表示第四十九頁，共五十五頁，編輯于2023年，星期二第五十頁，共五十五頁，編輯于2023年，星期二4.3.2形狀語法形狀語法（shapegrammars）：給定一組產(chǎn)生式規(guī)則，形狀設(shè)計者可以在從給定初始物體到最終物體結(jié)構(gòu)的每一次變換中應(yīng)用不同的規(guī)則。第五十一頁，共五十五頁，編輯于2023年，星期二4.3.3微粒系統(tǒng)用于模擬自然景物或模擬其它非規(guī)則形狀物體展示“流體”性質(zhì)的一個方法是微粒系統(tǒng)（particlesystems）。這一方法尤其擅長描述隨時間變化的物體。微粒運動的模擬方式：隨機過程模擬、運動路徑模擬、力學(xué)模