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

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

造型技術(shù):

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

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

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

點(diǎn)是0維幾何元素，分端點(diǎn)、交點(diǎn)、切點(diǎn)和孤立點(diǎn)等。

邊是1維幾何元素，是兩個(gè)鄰面（正則形體）或多個(gè)鄰面（非正則形體）的交界。直線邊、曲線邊第4頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第4頁。面是2維幾何元素，是形體上一個(gè)有限、非零的區(qū)域，由一個(gè)外環(huán)和若干個(gè)內(nèi)環(huán)界定其范圍。一個(gè)面可以無內(nèi)環(huán)，但必須有一個(gè)且只有一個(gè)外環(huán)。面有方向性，以其外法線矢量方向?yàn)樵撁娴恼?。?頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第5頁。環(huán)是有序、有向邊（真線段或曲線段）組成的面的封閉邊界。環(huán)中的邊不能相交，相鄰兩條邊共享一個(gè)端點(diǎn)確定面的最大外邊界的環(huán)稱之為外環(huán)確定面中內(nèi)孔或凸臺(tá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幾何信息與拓?fù)湫畔D形對(duì)象及構(gòu)成它的點(diǎn)、線、面的位置、相互間關(guān)系和幾何尺寸等都是圖形信息；表示圖形對(duì)象的線型、顏色、亮度以及供模擬、分析用的質(zhì)量、比重、體積等數(shù)據(jù)，是有關(guān)對(duì)象的非圖形信息。第8頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第8頁。圖形信息往往從幾何信息及拓?fù)湫畔煞矫婵紤]。幾何信息：形體在歐氏空間中的位置和大小(物體的各部分幾何形狀及其在空間的位置)拓?fù)湫畔ⅲ盒误w各分量（點(diǎn)、邊、面）的數(shù)目及其相互間的連接關(guān)系。1.幾何信息(1)幾何分量的數(shù)學(xué)表示,如：點(diǎn):(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)系(拓?fù)湫畔?第10頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第10頁。幾何信息的二義性2.拓樸信息平面立體的幾何分量之間一共有九種拓?fù)潢P(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實(shí)體的定義(a)有懸面(b)有懸邊第14頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第14頁?？陀^存在的三維形體具有這樣一些性質(zhì)：(1)剛性(2)維數(shù)的一致性(3)占據(jù)有限的空間(4)邊界的確定性(5)封閉性三維空間中的物體是一個(gè)內(nèi)部連通的三維點(diǎn)集，是由其內(nèi)部的點(diǎn)集及緊緊包著這些點(diǎn)的表皮組成的。第15頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第15頁。利用正則集的概念來定義上述的三維有效物體：由內(nèi)部點(diǎn)構(gòu)成的點(diǎn)集的閉包就是正則集，三維空間中正則集就是正則形體，也就是三維有效物體。第16頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第16頁。定義點(diǎn)集的正則運(yùn)算r運(yùn)算為：正則運(yùn)算即為先對(duì)物體取內(nèi)點(diǎn)再取閉包的運(yùn)算。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頁。

二維流形指的是對(duì)于實(shí)體表面上的任意一點(diǎn)，都可以找到一個(gè)圍繞著它的任意小的領(lǐng)域，該領(lǐng)域與平面上的一個(gè)圓盤是拓?fù)涞葍r(jià)的。第19頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第19頁。實(shí)體：對(duì)于一個(gè)占據(jù)有限空間的正則形體，如果其表面是二維流形，則該正則形體為實(shí)體。歐拉公式是檢查實(shí)體有效性的一個(gè)必要條件（不是充分條件）4.1.7平面多面體與歐拉公式第20頁，本講稿共55頁圖形的表示與數(shù)據(jù)結(jié)構(gòu)全文共55頁，當(dāng)前為第20頁。簡(jiǎn)單多面體條件：（1）所在面是單連通的，上面沒有洞（2）立體是單連通的，而且沒有孔洞（3）每條棱邊上恰好鄰接兩個(gè)面（4）每一個(gè)頂點(diǎn)處至少有三條棱邊相遇其頂點(diǎn)數(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表示多面體表面上孔的個(gè)數(shù)，G表示貫穿多面體的孔的個(gè)數(shù)，C表示獨(dú)立的、不相連接的多面體數(shù)，則擴(kuò)展后的歐拉公式為：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è)物體的直線和曲線組成，每一條直線和曲線都是單獨(dú)構(gòu)造出來的，并不存在面的信息。線框模型存在著幾個(gè)缺陷：二義性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頁。不能正確表示曲面信息。無法進(jìn)行圖形的線面消隱。

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

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

邊表

面表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頁。表示其拓?fù)湫畔?/p>

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

可以利用平面方程：Ax+By+Cz+D=0求得平面的法向量鑒別空間上的點(diǎn)與物體平面的位置關(guān)系。判別點(diǎn)在面的內(nèi)部或外部實(shí)體存在側(cè)方法——平面法向量法向量指向物體外部，當(dāng)多邊形頂點(diǎn)指定為逆時(shí)針方向時(shí)，法向量方向滿足右手定則。第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）可以利用簡(jiǎn)單的運(yùn)動(dòng)規(guī)則生成有效實(shí)體。

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

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