圖形的層次結(jié)構(gòu)

關(guān)于圖形的層次結(jié)構(gòu)第1頁，共35頁，2023年，2月20日，星期三

現(xiàn)實(shí)世界中的客觀對(duì)象都有一定的組織結(jié)構(gòu),用圖形學(xué)來描繪實(shí)際的對(duì)象需要確定一定的圖形結(jié)構(gòu)(幾何模型)

現(xiàn)實(shí)中的對(duì)象往往有層次結(jié)構(gòu)，描述這些對(duì)象的圖形結(jié)構(gòu)也是層次的

利用層次結(jié)構(gòu)，可以方便地對(duì)圖形進(jìn)行編輯和繪制

本章給出了幾種常見的圖形層次結(jié)構(gòu)，包括PHIGS結(jié)構(gòu)和許多應(yīng)用系統(tǒng)中常用的面向?qū)ο蟮膶哟谓Y(jié)構(gòu)。

第2頁，共35頁，2023年，2月20日，星期三5.1圖形的層次結(jié)構(gòu)概述基本概念：圖形結(jié)構(gòu)也稱為幾何模型，是由具有明確幾何定義的元素，如點(diǎn)、線、面等及其相互間連接關(guān)系組成。

基本圖素點(diǎn)、線、面等稱為基本圖素/圖元基本圖素之間的連接關(guān)系稱為拓?fù)潢P(guān)系在層次結(jié)構(gòu)中，由基本元素構(gòu)成的對(duì)象可用來構(gòu)成更復(fù)雜的對(duì)象，這類對(duì)象也稱為基本元素。第3頁，共35頁，2023年，2月20日，星期三圖形層次結(jié)構(gòu)的組成部分幾何及其他附屬屬性物體及組成物體的基本元素的幾何屬性和其他影響外表的屬性，如顏色、線形和線寬等。拓?fù)潢P(guān)系物體及基本元素之間的拓?fù)潢P(guān)系，拓?fù)潢P(guān)系可以用樹結(jié)構(gòu)或鄰接矩陣表示，也可由其內(nèi)在的幾何定義表示。特定的圖形結(jié)構(gòu)，用來表示一些特定的屬性。與物體及基本元素相對(duì)應(yīng)的數(shù)據(jù)值和屬性，如電子文本和描述文字。第4頁，共35頁，2023年，2月20日，星期三自底向上的設(shè)計(jì)方法圖形結(jié)構(gòu)常常是層次的計(jì)算機(jī)硬件結(jié)構(gòu)圖是由很多諸如運(yùn)算器、控制器及存儲(chǔ)器部件等部件組成的，每一部件又由一些標(biāo)準(zhǔn)的單元電路、門電路及觸發(fā)器組成。圖形設(shè)計(jì)時(shí)，往往用自底向上的方法設(shè)計(jì)復(fù)雜的層次結(jié)構(gòu)圖首先由基本的圖形元素如線、圓弧等構(gòu)建形成門、窗和樓梯(高一層的圖素)，再由直線段、圓弧等基本元素和門、窗、樓梯等高一層的圖素形成房間和層等更高一層的結(jié)構(gòu)，最后組成一棟樓房，這些高層圖素一般稱為塊(block)或子圖。只要在圖形結(jié)構(gòu)中存在結(jié)構(gòu)相同的部分，而這些部分又在圖形結(jié)構(gòu)中出現(xiàn)多次，就可把這樣的部分組成塊。第5頁，共35頁，2023年，2月20日，星期三

在該結(jié)構(gòu)中，與門、非門及或門電路是基本電路，分別由不同的基本圖素線段及圓弧構(gòu)成?？砂雅c門、非門及或門組織成三個(gè)塊，任何邏輯圖便可利用這三個(gè)塊和基本元素根據(jù)實(shí)際組合來構(gòu)成。同一個(gè)塊可以有不同的實(shí)例，這些實(shí)例在圖中的位置，大小和方向都可以不同。這些門電路可以組成一些基本電路塊（如觸發(fā)器），而邏輯電路又由這些基本電路塊及門電路塊組成，這樣便形成了一個(gè)多層的層次結(jié)構(gòu)。圖5.1由門電路組成的邏輯電路實(shí)例：邏輯電路圖設(shè)計(jì)中的層次結(jié)構(gòu)第6頁，共35頁，2023年，2月20日，星期三實(shí)例與或非與第7頁，共35頁，2023年，2月20日，星期三

利用了層次結(jié)構(gòu)最主要的好處是可以將一組相關(guān)的圖素組織在一起，進(jìn)行整體的插入、刪除、移動(dòng)和放縮等操作。層次結(jié)構(gòu)的優(yōu)點(diǎn)

由于在圖中一個(gè)塊雖在圖中多處出現(xiàn)，但它的幾何及拓?fù)湫畔⑹窍嗤模虼酥恍璞４嬉淮?，所以可以?jié)省大量的內(nèi)存。第8頁，共35頁，2023年，2月20日，星期三

利用面向?qū)ο蟮某绦蛟O(shè)計(jì)類的繼承特性,可以很好地實(shí)現(xiàn)圖形的層次結(jié)構(gòu)，下面討論層次結(jié)構(gòu)的具體表示和相關(guān)的操作。通過對(duì)已有對(duì)象進(jìn)行增加或部分修改的方法建立新的對(duì)象，對(duì)已有對(duì)象可以增加數(shù)據(jù)和過程，也可以對(duì)其中某些過程進(jìn)行從新定義。最初的類被稱為基類，從基類擴(kuò)展出來的類稱為派生類。這樣，我們可以采用對(duì)象派生的方法建立一個(gè)有層次的對(duì)外部世界的描述5.2面向?qū)ο蟮膶哟谓Y(jié)構(gòu)的實(shí)現(xiàn)第9頁，共35頁，2023年，2月20日，星期三5.2.1面向?qū)ο蟮膶哟谓Y(jié)構(gòu)表示

將結(jié)構(gòu)中的基本圖素定義為類，并定義相應(yīng)的數(shù)據(jù)和方法來實(shí)現(xiàn)基本圖素，基本圖素的類又可以通過對(duì)其增加和更新形成更高一層的圖形部件classElement{UINTnType;voiddraw();booleanselect(x,y);modify();delete();voidsetColor(intcolor);intgetColor();}classLine:publicElement{floatx0,y0,x1,y1;voiddraw(){….}}classCirclepublicElement{floatxc,yc,xs,ys,xe,ye;voiddraw(){….}}

用類Line,Circle…等來描述直線段、圓弧等基本圖形元素，它們是構(gòu)成層次結(jié)構(gòu)中塊的最基本的元素?？梢詫penGL的函數(shù)嵌入以實(shí)現(xiàn)Line類的draw()函數(shù)。voiddraw(){glBegin(GL_LINES);glVertex2f(x0,y0);glVertex2f(x1,y1);glEnd();}第10頁，共35頁，2023年，2月20日，星期三圖形結(jié)構(gòu)塊2.圖形結(jié)構(gòu)塊

classBlockpublicElement{char*name;CElement**eList；

Block*next;voiddraw(){….}}

圖形結(jié)構(gòu)塊是由多個(gè)直線段、圓弧等基本圖形元素和多個(gè)塊的實(shí)例組成的，由基本元素和塊實(shí)例形成的塊又可以借助于塊實(shí)例成為高層塊的組成部分，形成一個(gè)嵌套結(jié)構(gòu)，當(dāng)然最底層的塊只能由基本圖形元素組成。eList用來保存構(gòu)成塊的所有基本圖形元素和塊實(shí)例的對(duì)象指針，它可以是一個(gè)動(dòng)態(tài)數(shù)組，也可以用鏈表等線性表結(jié)構(gòu)實(shí)現(xiàn)。繪制圖塊時(shí)，遍歷線性表中的所有對(duì)象，調(diào)用對(duì)象的draw()方法就可以完成整個(gè)塊的繪制。

類Block中的name用來保存塊的名字，可用于標(biāo)識(shí)塊，當(dāng)然也可以根據(jù)具體的應(yīng)用附加其他的屬性進(jìn)行擴(kuò)充。next指針指向下一個(gè)塊結(jié)構(gòu)，通過它可以將該塊及塊中所涉及子塊連接在一起。第11頁，共35頁，2023年，2月20日，星期三塊的實(shí)例3.塊的實(shí)例classInstancepublicElement{Block*pt;floatdx,dy,rax,ray,sx,sy;}

把塊的實(shí)例放在圖中(所在的高層的塊)的不同位置，這相對(duì)于世界坐標(biāo)系來講是一個(gè)平移變換。同一個(gè)塊在不同位置的實(shí)例其大小、方向和位置可以不同，因此要在世界坐標(biāo)變換基礎(chǔ)上作一個(gè)局部的變換，這種局部變換就是我們第四章講的變換。第12頁，共35頁，2023年，2月20日，星期三塊的實(shí)例一般把塊的中心放在坐標(biāo)原點(diǎn)，通過局部變換產(chǎn)生放在不同位置及不同大小方向的實(shí)例圖5.2通過局部變換產(chǎn)生放在不同位置及不同大小方向

在類Instance中我們分別用dx,dy,rax,ray,sx,sy表示變換的參數(shù)，用于描述實(shí)例實(shí)際的位置、大小和旋轉(zhuǎn)角度。第13頁，共35頁，2023年，2月20日，星期三塊的實(shí)例這里并不要求專門建立局部坐標(biāo)系的變換，我們還是可以用世界坐標(biāo)中的變換來實(shí)現(xiàn)。在OpenGL中世界坐標(biāo)系的二維變換為：

glScale（sx，sy,0,0）在x、y方向分別放縮sx及sy倍

glRotate（rax,ray,0,0）旋轉(zhuǎn)ra角

gltranslate（dx，dy,0,0）在x、y方向分別平移dx、dy第14頁，共35頁，2023年，2月20日，星期三5.2.2面向?qū)ο蟮膶哟谓Y(jié)構(gòu)編輯圖形塊的存取操作

用命令Block*createBlock(name)創(chuàng)建一個(gè)名為name值的新圖形塊，

用Block*openBlock(name)打開一個(gè)已存在的圖形塊；

用closeBlock(name)關(guān)閉當(dāng)前打開的圖形塊；

用booldeleteBlock(name)刪除名為name的圖形塊第15頁，共35頁，2023年，2月20日，星期三5.2.2面向?qū)ο蟮膶哟谓Y(jié)構(gòu)編輯

圖形塊的編輯操作增加圖素。

add(newLine(x0,y0,x1,y1))//增加一條新的直線

選擇圖素。Select（x，y）在圖形塊中找出被選擇的對(duì)象

修改和刪除操作第16頁，共35頁，2023年，2月20日，星期三優(yōu)點(diǎn)：5.2.3面向?qū)ο蟮膶哟谓Y(jié)構(gòu)的討論

1）同一層的塊結(jié)構(gòu)是相同的，不同層的結(jié)構(gòu)用統(tǒng)一的Block來表示，存儲(chǔ)、修改、顯示、編輯等可以用統(tǒng)一的方法來處理。2）采用面向?qū)ο蟮脑O(shè)計(jì)，易于擴(kuò)充，可以很方便地支持其他的基本圖形元素。3）用過程和數(shù)據(jù)結(jié)合來靈活地表示層次結(jié)構(gòu)的復(fù)雜圖形。第17頁，共35頁，2023年，2月20日，星期三5.2.3面向?qū)ο蟮膶哟谓Y(jié)構(gòu)的討論

由于面向?qū)ο蟮膱D形層次結(jié)構(gòu)從存儲(chǔ)結(jié)構(gòu)上支持圖形塊的循環(huán)嵌套，因此在圖形的顯示、遍歷等操作時(shí)有可能陷入死循環(huán)。但實(shí)際的圖形結(jié)構(gòu)是不可能出現(xiàn)循環(huán)嵌套的，這就要求在實(shí)現(xiàn)將圖形塊實(shí)例插入時(shí)，要進(jìn)行必要的檢查，避免出現(xiàn)循環(huán)嵌套。下面結(jié)合實(shí)例給出了一個(gè)具體的層次表示第18頁，共35頁，2023年，2月20日，星期三5.2.3面向?qū)ο蟮膶哟谓Y(jié)構(gòu)的討論圖5.3邏輯電路5.1的層次表示第19頁，共35頁，2023年，2月20日，星期三ISO1986年公布的計(jì)算機(jī)圖形系統(tǒng)標(biāo)準(zhǔn)PHIGS（Programmer’sHierarchicalInteractiveGraphicsSystem）提供實(shí)現(xiàn)圖形層次結(jié)構(gòu)的結(jié)構(gòu)方法。在PHIGS中，賦于標(biāo)號(hào)的一系列輸入圖元（包括有關(guān)特性）稱為結(jié)構(gòu)。5.3用結(jié)構(gòu)方法實(shí)現(xiàn)層次結(jié)構(gòu)第20頁，共35頁，2023年，2月20日，星期三5.3.1基本的結(jié)構(gòu)函數(shù)建立一個(gè)新的結(jié)構(gòu)的過程openStructure（id）；id為整數(shù)，將id賦予這個(gè)結(jié)構(gòu)作為標(biāo)號(hào)定義圖形的屬性及繪制圖形用closeStructure關(guān)閉這個(gè)結(jié)構(gòu)第21頁，共35頁，2023年，2月20日，星期三實(shí)例下列程序定義了一個(gè)標(biāo)號(hào)為6的繪制多邊形的結(jié)構(gòu)。

openStructure(6)；

setLinetype(lt)；

setPolylineColorIndex(lc)；

polyline(n，pts)；

closeStructure；第22頁，共35頁，2023年，2月20日，星期三5.3.1基本的結(jié)構(gòu)函數(shù)

元素：一個(gè)結(jié)構(gòu)中，介于openStructure及closeStructure二命令中的屬性設(shè)置及圖形輸出命令稱為元素。元素以先后次序從1開始有個(gè)編號(hào)。1SetLinetype(lt)2SetPolylineColourIndex(lc);3Polyline(n,pts);元素指針第23頁，共35頁，2023年，2月20日，星期三5.3.1基本的結(jié)構(gòu)函數(shù)postStructure(ws，id，priority)

在工作站ws上顯示標(biāo)號(hào)為id的結(jié)構(gòu)。

priority是顯示的優(yōu)先級(jí)，在[0，1]中取值。當(dāng)兩個(gè)結(jié)構(gòu)在顯示屏上重疊時(shí)，在重疊處顯示優(yōu)先級(jí)大的結(jié)構(gòu)。工作站ws可以是顯示器或激光打印機(jī)等圖形輸出設(shè)備。unpostStructure(ws，id)

使結(jié)構(gòu)在顯示器工作站ws上不顯示從輸出設(shè)備的激活機(jī)構(gòu)表中刪除了結(jié)構(gòu)，但并不影響系統(tǒng)結(jié)構(gòu)表。在光柵系統(tǒng)中要使一個(gè)結(jié)構(gòu)不再顯示，則用背景色重畫屏幕上的圖元即可。但是這樣處理會(huì)影響到與被刪除結(jié)構(gòu)有重疊的其他結(jié)構(gòu)圖元的顯示。為了避免這一點(diǎn)，可以用場景中不同結(jié)構(gòu)的坐標(biāo)范圍來判斷哪些結(jié)構(gòu)與要被刪除的結(jié)構(gòu)重疊，在刪除結(jié)構(gòu)之后只要重畫這些有重疊的結(jié)構(gòu)就可以。第24頁，共35頁，2023年，2月20日，星期三5.3.1基本的結(jié)構(gòu)函數(shù)changeStructureIdentifier(oldID,newID)；重新標(biāo)識(shí)一個(gè)結(jié)構(gòu)unpostAllStructures(ws)；將所有的結(jié)構(gòu)從工作站ws的輸出設(shè)備中刪除：deleteStructure(id)要?jiǎng)h掉一個(gè)結(jié)構(gòu)，一旦結(jié)構(gòu)id被刪除后，所有工作站就都不能顯示該結(jié)構(gòu)了。此后，該結(jié)構(gòu)的名字可以被其他圖形結(jié)構(gòu)使用。

deleteAllStructures；清除整個(gè)系統(tǒng)結(jié)構(gòu)表：第25頁，共35頁，2023年，2月20日，星期三5.3.2設(shè)置結(jié)構(gòu)屬性setInvisibilityFilter(ws,devCode,invisSet,visSet)invisSet包括不可見的結(jié)構(gòu)名，visSet包括可見的結(jié)構(gòu)名。不可見過濾器對(duì)于工作站上的結(jié)構(gòu)起了開關(guān)顯示的作用，因此不用將結(jié)構(gòu)真正的從工作站表中刪除。setHighlightingFilter(ws,devCode,highlightSet,nohighlightSet)highlightSet包括需要高亮度顯示的結(jié)構(gòu)名，nohighlightSet包括不用高亮度顯示的結(jié)構(gòu)名。第26頁，共35頁，2023年，2月20日，星期三5.3.3結(jié)構(gòu)編輯

如果需要在建立一個(gè)新的結(jié)構(gòu)的元素后添加另外一些新的元素，只要再調(diào)用openStructure及closeStructure，并把要添加的元素寫在它們中間即可。openStructure(shape)；setInteriorStyle(solid)；setInteriorColourIndex(4)；fillArea(n，verts1)；closeStructure；┇openStructure(shape)；setInterierStyle(hellow)；

fillArea(n2，verts2)；

closeStructure；第27頁，共35頁，2023年，2月20日，星期三5.3.3結(jié)構(gòu)編輯在相繼兩次打開結(jié)構(gòu)shape中，第一次調(diào)用closeStructure以后指針指在第三個(gè)元素，圖5.5元素表第二次調(diào)用openStructure（shape）以后便把它后續(xù)的元素加在元素指針下面的位置。這一系列操作等價(jià)于一次打開結(jié)構(gòu)shape進(jìn)行如下操作：。

openStructure(shape)setInteriorStyle（solid）；

setInteriorColourIndex(4)；

fillArea（n，vertsl）；

setInteriorStyle(hellow)；fillArea(n2，verts2)closeStructure；

1setInteriorStyle(solid)2setInteriorColourIndex(4)3fillArea(n,verts1)元素指針第28頁，共35頁，2023年，2月20日，星期三5.3.3結(jié)構(gòu)編輯setElementPointer（k）改變指針?biāo)赶虻奈恢?，指針指向第k個(gè)元素。setEditMode(mode);設(shè)置編輯模式的值mode可設(shè)定為插入（insert）或者代替（replace）。第29頁，共35頁，2023年，2月20日，星期三結(jié)構(gòu)編輯的實(shí)例例如，如果要在本節(jié)開始時(shí)建立的結(jié)構(gòu)shape的第1個(gè)元素處加一條定義線寬為lw的元素，則可用下面一段程序來實(shí)現(xiàn)：

openStructure(shape)；

setEditMode(insert)；

setElementPointer(0)；

setLinewidth(lw)；

closeStructure；其中第一個(gè)元素把編輯模式設(shè)為insert，第二個(gè)元素把元素指針指在0元素處，這樣便會(huì)把第三個(gè)元素嵌入到第1個(gè)位置，即指針下面一個(gè)位置，如圖5.6。1SetLinewidth(1w)2SetInteriorStyle(solid)3SetInteriorColourindex(4)4FillArea(n,verts1)第30頁，共35頁，2023年，2月20日，星期三5.3.3結(jié)構(gòu)編輯如果要把某一元素?fù)Q成另一元素，則要把編輯模式設(shè)成replace。例如，要把上例的顏色換成5，則可調(diào)用：

openStructure(shape)；

setEditMode(replace)；

setElementPointer(3)；

SetInteriorColourIndex(5)；

closeStructure；

deleteElement；刪除指針指向的當(dāng)前位置上的元素例如，如果要?jiǎng)h除上例中設(shè)置線型的元素，則可調(diào)用

openStructure(