第10講 圖形消隱

第10講圖形消隱

1第10講圖形消隱基本概念提高消隱算法效率的常用方法畫家算法Z緩沖器算法掃描線Z緩沖器算法OpenGL相關(guān)函數(shù)2問題投影變換失去了深度信息，往往導(dǎo)致圖形的二義性及失去遮擋關(guān)系要消除二義性和保持遮擋關(guān)系，就必須在繪制（投影）時(shí)消除被遮擋的不可見的線或面，習(xí)慣上稱作消除隱藏線和隱藏面，簡(jiǎn)稱為消隱失去遮擋關(guān)系長(zhǎng)方體線框投影圖的二義性10.1基本概念3消隱的對(duì)象三維物體三維體的表示主要采用邊界（多邊形）表示消隱結(jié)果與觀察物體有關(guān)，也與視點(diǎn)位置和方向有關(guān)線框圖消隱圖真實(shí)感圖形10.1基本概念4消隱分類消除隱藏面：確定可見面（消除不可見面）——表面表示物體（本講討論）消除隱藏線：消除不可見線——線框表示物體10.1基本概念5面消隱算法分類投影窗口內(nèi)的像素為處理單元——確定最近點(diǎn)

for(窗口內(nèi)的每一個(gè)像素) {

確定距視點(diǎn)最近的物體，以該物體表面的顏色來顯示像素

}圖像空間－image-space10.1基本概念6面消隱算法分類（續(xù)）場(chǎng)景中的物體為處理單元——物體上的面是否最近for(場(chǎng)景中的每一個(gè)物體){

將其與場(chǎng)景中的其它物體比較，確定其表面的可見部分；顯示該物體表面的可見部分；}場(chǎng)景空間－object-space10.1基本概念710.2提高消隱算法效率的常用方法主要技術(shù)1.利用連貫性相鄰物體的屬性之間有一定的連貫性，其屬性值通常是平緩過渡的，如顏色值、空間位置關(guān)系等包括：物體連貫性面的連貫性區(qū)域連貫性掃描線連貫性深度連貫性810.2提高消隱算法效率的常用方法（1）物體連貫性：如果物體A與物體B是完全相互分離的，則在消隱時(shí)，只需比較A、B兩物體之間的遮擋關(guān)系，無須對(duì)它們的表面多邊形逐一進(jìn)行測(cè)試。例如，若A距視點(diǎn)較B遠(yuǎn)，則在測(cè)試B上的表面的可見性時(shí)，無須考慮A的表面（2）面的連貫性：一張面內(nèi)的各種屬性值一般都是緩慢變化的，允許采用增量形式對(duì)其進(jìn)行計(jì)算910.2提高消隱算法效率的常用方法（3）區(qū)域連貫性：區(qū)域指屏幕上一組相鄰的像素，它們通常為同一個(gè)可見面所占據(jù)，可見性相同。區(qū)域連貫性表現(xiàn)在一條掃描線上時(shí)，即為掃描線上的每個(gè)區(qū)間內(nèi)只有一個(gè)面可見（4）掃描線的連貫性：相鄰兩條掃描線上，可見面的分布情況相似（5）深度連貫性：同一表面上的相鄰部分深度是相近的，而占據(jù)屏幕上同一區(qū)域的不同表面的深度不同。這樣在判斷表面間的遮擋關(guān)系時(shí)，只需取其上一點(diǎn)計(jì)算出深度值，比較該深度值便能得出結(jié)果1010.2提高消隱算法效率的常用方法2.包圍盒技術(shù)定義：一個(gè)形體的包圍盒指的是包圍它的簡(jiǎn)單形體兩個(gè)條件包圍盒充分緊密包圍著形體對(duì)其的測(cè)試比較簡(jiǎn)單主要包圍盒長(zhǎng)方體正方體球1110.2提高消隱算法效率的常用方法作用—避免盲目求交例如：兩個(gè)空間多邊形A、B在投影平面上的投影分別為A’，B’，因?yàn)锳’、B’的矩形包圍盒不相交，則A’、B’不相交，無須進(jìn)行遮擋測(cè)試如果包圍盒相交，需進(jìn)一步測(cè)試。右下圖(a)包圍盒相交，投影也相交；(b)包圍盒相交，投影不相交一般情況下，判斷兩物體是否遮擋時(shí)，前一種情況大量存在，避免了物體間的復(fù)雜相交測(cè)試1210.2提高消隱算法效率的常用方法3.背面剔除外法向：規(guī)定每個(gè)多邊形的外法向都是指向物體外部的前向面：若多邊形的外法向與投影方向（觀察方向）的夾角為鈍角，稱為前向面后向面：若多邊形的外法向與投影方向（觀察方向）的夾角為銳角，稱為后向面（背面）夾角為180－u投影方向1310.2提高消隱算法效率的常用方法剔除依據(jù)：背面總是被前向面所遮擋，從而不可見前向面后向面JEAF、HCBG、JIHGF為后向面CGVABDEFHIJNVnVn1410.2提高消隱算法效率的常用方法4.空間分割技術(shù)遮擋判斷依據(jù)：場(chǎng)景中的物體，它們的投影在投影平面上是否有重疊部分？（是否存在相互遮擋的可能？）對(duì)于根本不存在相互遮擋關(guān)系的物體，應(yīng)避免這種不必要的測(cè)試原因：物體在場(chǎng)景中分散，有些物體的投影相距甚遠(yuǎn)，不會(huì)存在遮擋關(guān)系方法：將投影平面上的窗口分成若干小區(qū)域；為每個(gè)小區(qū)域建立相關(guān)物體表，表中物體的投影于該區(qū)域有相交部分；則在小區(qū)域中判斷那個(gè)物體可見時(shí)，只要對(duì)該區(qū)域的相關(guān)物體表中的物體進(jìn)行比較1510.2提高消隱算法效率的常用方法5.物體的分層表示表示形式：模型變換中的樹形表示方式原理：減少場(chǎng)景中物體的個(gè)數(shù)，從而降低算法復(fù)雜度16方法：將父節(jié)點(diǎn)所代表的物體看成子節(jié)點(diǎn)所代表物體的包圍盒，當(dāng)兩個(gè)父節(jié)點(diǎn)之間不存在遮擋關(guān)系時(shí)，就沒有必要對(duì)兩者的子節(jié)點(diǎn)做進(jìn)一步測(cè)試。父節(jié)點(diǎn)之間的遮擋關(guān)系可以用它們之間的包圍盒進(jìn)行預(yù)測(cè)試10.2提高消隱算法效率的常用方法17背景畫家作畫：先畫遠(yuǎn)景后畫近景畫家的作畫順序暗示出所畫物體之間的相互遮擋關(guān)系10.3畫家算法18算法基本思想：1）先把屏幕置成背景色2）將場(chǎng)景中的物體按其距觀察點(diǎn)的遠(yuǎn)近進(jìn)行排序，結(jié)果放在一張線性表中；（線性表構(gòu)造：距觀察點(diǎn)遠(yuǎn)的稱優(yōu)先級(jí)低，放在表頭；距觀察點(diǎn)近的稱優(yōu)先級(jí)高，放在表尾。該表稱為深度優(yōu)先級(jí)表）3）然后按照從遠(yuǎn)到近（從表頭到表尾）的順序逐個(gè)繪制物體關(guān)鍵如何對(duì)場(chǎng)景中的物體按深度（遠(yuǎn)近）排序，建立深度優(yōu)先級(jí)表？10.3畫家算法1910.3畫家算法世界坐標(biāo)系

用戶用來定義圖形的坐標(biāo)系，主要用于計(jì)算機(jī)圖形場(chǎng)景中所有圖形對(duì)象的空間定位和定義。觀察坐標(biāo)系可以在世界坐標(biāo)系的任何位置、任何方向定義，通常以視點(diǎn)的位置為原點(diǎn)，通過用戶指定的一個(gè)向上的觀察向量來定義整個(gè)坐標(biāo)系統(tǒng)。unvP0(x0,y0,z0)xyz2010.3畫家算法畫家算法的觀察變換將世界坐標(biāo)系中的三個(gè)坐標(biāo)軸轉(zhuǎn)換為與觀察坐標(biāo)系的三個(gè)坐標(biāo)軸對(duì)應(yīng)重合的逆變換平移變換，將觀察參考點(diǎn)移到世界坐標(biāo)系的原點(diǎn)處旋轉(zhuǎn)變換，將u，v，n分別對(duì)應(yīng)到x，y，z 即繞x軸旋轉(zhuǎn)角，繞y軸旋轉(zhuǎn)角，繞z軸旋轉(zhuǎn)角21多邊形的排序算法1）將場(chǎng)景中所有多邊形存入一個(gè)線性表，記為L(zhǎng)；2）如果L中僅有一個(gè)多邊形，算法結(jié)束；否則根據(jù)每個(gè)多邊形的nmin

對(duì)它們預(yù)排序。不妨假定多邊形P落在L的表首，即nmin(P)為最小再記

Q

為L(zhǎng)–{P}(表中其余多邊形）中任意一個(gè)；3）判別P,Q之間的關(guān)系，有如下二種： （1）對(duì)所有的Q，有nmax(P)<nmin(Q),則多邊形P

的確距觀察點(diǎn)最遠(yuǎn)，它不可能遮擋別的多邊形。令L=L–{P},返回第二步;

（2）存在某一個(gè)多邊形Q，使nmax(P)>nmin(Q)，需進(jìn)一步判別：10.3畫家算法在觀察坐標(biāo)系uvn中，觀察方向是n軸的負(fù)方向，因而n坐標(biāo)大者距觀察者更近。nmin(P)和

nmax(P)

分別為P各頂點(diǎn)n坐標(biāo)的最小和最大值。[投影為正平行投影]22（A）若P,Q的投影P’,Q’的包圍盒不相交(圖a)，則P,Q

在表中的次序不重要，令L=L–{P},返回2）;否則進(jìn)行下一步（B）若P

的所有頂點(diǎn)位于Q

所在平面的不可見的一側(cè)(圖b)，則P,Q關(guān)系正確，令L=L–{P},返回2）;否則進(jìn)行下一步10.3畫家算法23（C）若Q的所有頂點(diǎn)位于P

所在平面的可見的一側(cè)(圖c)，則P,Q關(guān)系正確，令L=L–{P},返回2）;否則進(jìn)行下一步（D）對(duì)P,Q投影P’,Q’求交，若P’,Q’不相交(圖d)，則P,Q在表中的次序不重要，令L=L–{P},返回2）;否則在它們所相交的區(qū)域中任取一點(diǎn)，計(jì)算P,Q在該點(diǎn)的深度值，如果P的深度小，則P,Q關(guān)系正確，令L=L–{P},返回2）;否則交換P,Q,返回3）10.3畫家算法24問題不能處理多邊形循環(huán)遮擋和多邊形相互穿透解決方法：分割10.3

畫家算法25又稱Z－Buffer算法(深度緩沖depth-buffer)組成：幀緩沖器--保存各像素顏色值

Z緩沖器--保存各像素處物體深度值

10.4Z緩沖器算法Z

緩沖器中的單元與幀緩沖器中的單元一一對(duì)應(yīng)26算法

（1）先將Z緩沖器中個(gè)單元的初始值置為最小值。（2）多邊形投影時(shí)，當(dāng)要改變某個(gè)像素的顏色值時(shí)，首先檢查當(dāng)前多邊形的深度值是否大于該像素原來的深度值（保存在該像素所對(duì)應(yīng)的Z緩沖器的單元中），

A：如果大于，說明當(dāng)前多邊形更靠近觀察點(diǎn)，用它的顏色替換像素原來的顏色；同時(shí)保存深度值

B：否則說明在當(dāng)前像素處，當(dāng)前多邊形被前面所繪制的多邊形遮擋了，是不可見的，像素的顏色值不改變10.4Z緩沖器算法27算法偽碼{ 幀緩存全置為背景色； 深度緩存全置為最小Z值；

for(每一個(gè)多邊形) {for(該多邊形所覆蓋的每個(gè)像素(x,y)){

計(jì)算該多邊形在該像素的深度值Z(x,y);if(Z(x,y)大于Z緩存在(x,y)的值) {

把Z(x,y)存入Z緩存中(x,y)處；把多邊形在(x,y)處的顏色值存入幀緩存的(x,y)處；

} } }}10.4Z緩沖器算法28特點(diǎn)Z緩沖器算法是所有圖像空間算法中最簡(jiǎn)單的一種隱藏面消除算法。在像素級(jí)上以近物取代遠(yuǎn)物，與形體在屏幕上的出現(xiàn)順序無關(guān)。優(yōu)點(diǎn)

1）簡(jiǎn)單穩(wěn)定，利于硬件實(shí)現(xiàn)

2）不需要整個(gè)場(chǎng)景的幾何數(shù)據(jù)缺點(diǎn)

1）需要一個(gè)額外的Z緩沖器

2）每個(gè)多邊形占據(jù)的每個(gè)像素處都要計(jì)算深度值，計(jì)算量大10.4Z緩沖器算法29由來Z緩沖器算法中所需要的Z緩沖器容量較大，為克服這個(gè)缺點(diǎn)，可以將整個(gè)繪圖區(qū)域分割成若干個(gè)小區(qū)域，然后一個(gè)區(qū)域一個(gè)區(qū)域地顯示，這樣Z緩沖器的單元數(shù)只要等于一個(gè)區(qū)域內(nèi)像素的個(gè)數(shù)如果將小區(qū)域取成屏幕上的掃描線，就得到掃描線Z緩沖器算法10.5掃描線Z緩沖器算法30算法思想在處理當(dāng)前掃描線時(shí)，用一個(gè)一維數(shù)組作為當(dāng)前掃描線的Z-buffer。首先找出與當(dāng)前掃描線相關(guān)的多邊形，以及每個(gè)多邊形中相關(guān)的邊對(duì)。對(duì)每一個(gè)邊對(duì)之間的小區(qū)間上的各像素，計(jì)算深度，并與Z-buffer中的值比較，找出各像素處可見平面。（采用增量算法計(jì)算深度）寫幀緩存。10.5掃描線Z緩沖器算法31算法

for(v=0;v<vmax;v++){ for(u=0;u<umax;u++){將幀緩沖器的第(u,v)單元置為背景色；將Z緩沖器的第u單元置為最小值；

}for(每個(gè)多邊形）//當(dāng)前掃描線相關(guān)的多邊形

{

求出多邊形在投影平面上的投影與當(dāng)前掃描線的相交區(qū)間；

for（該區(qū)間內(nèi)的每個(gè)像素(u,v)）

{計(jì)算多邊形在該像素處的深度值d；

if(d>Z緩沖器的第u單元的值）

{置幀緩沖器的第(u,v)單元值為當(dāng)前多邊形顏色；

置Z緩沖器的第u單元值為d;}}}}//處理下一條掃描線10.5掃描線Z緩沖器算法32缺點(diǎn)在每一個(gè)被多邊形覆蓋像素處需要計(jì)算深度值被多個(gè)多邊形覆蓋的像素需要多次計(jì)算深度值10.5掃描線Z緩沖器算法33多邊形剔除函數(shù)－消除后向面（背面）激活：glEnable（GL_CULL_FACE）無效：glDisable（GL_CULL_FACE）剔除背面：glCullFace（GL_BACK）顯示模式：線框方式

glPolygonMode(GL_GRONT_AND_BACK,GL_LINE)10.6OpenGL相關(guān)函數(shù)3410.6OpenGL相關(guān)函數(shù)例：剔除后向面#include<stdlib.h>#include<GL/glut.h>GLfloatvertices[][3]={{-1.0,-1.0,-1.0},{1.0,-1.0,-1.0},{1.0,1.0,-1.0},{-1.0,1.0,-1.0},{-1.0,-1.0,1.0},{1.0,-1.0,1.0},{1.0,1.0,1.0},{-1.0,1.0,1.0}};staticGLfloattheta[]={0.0,0.0,0.0};staticGLintaxis=2;staticGLdoubleviewer[]={0.0,0.0,5.0};voidpolygon(inta,intb,intc,intd){glBegin(GL_POLYGON);glVertex3fv(vertices[a]);glVertex3fv(vertices[b]);glVertex3fv(vertices[c]);glVertex3fv(vertices[d]);glEnd();}3510.6OpenGL相關(guān)函數(shù)voidcolorcube(){//正前面

glColor3f(1,1,1);polygon(4,5,6,7);//正背面

glColor3f(1.0,0,0);polygon(0,3,2,1);glColor3f(0,1,0);polygon(2,3,7,6);glColor3f(0,0,1);polygon(0,4,7,3);glColor3f(1,1,0);polygon(1,2,6,5);glColor3f(0,1,1);polygon(0,1,5,4);}voiddisplay(){glClear(GL_COLOR_BUFFER_BIT);glLoadIdentity();//更新視點(diǎn)位置

gluLookAt(viewer[0],viewer[1],viewer[2],0.0,0.0,0.0,0.0,1.0,0.0);glRotatef(theta[0],1.0,0.0,0.0);glRotatef(theta[1],0.0,1.0,0.0);/*旋轉(zhuǎn)立方體*/glRotatef(theta[2],0.0,0.0,1.0);colorcube();glutSwapBuffers();}3610.6OpenGL相關(guān)函數(shù)voidkeys(unsignedcharkey,intx,inty){/*用x,X,y,Y,z,andZ鍵移動(dòng)視點(diǎn)*/if(key=='x')viewer[0]-=1.0;if(key=='X')viewer[0]+=1.0;if(key=='y')viewer[1]-=1.0;if(key=='Y')viewer[1]+=1.0;if(key=='z')viewer[2]-=1.0;if(key=='Z')viewer[2]+=1.0;display();}voidmyReshape(intw,inth){glViewport(0,0,w,h);glMatrixMode(GL_PROJECTION);glLoadIdentity();if(w<=h)glFrustum(-2.0,2.0,-2.0*(GLfloat)h/(GLfloat)w,2.0*(GLfloat)h/(GLfloat)w,2.0,20.0);elseglFrustum(-2.0,2.0,-2.0*(GLfloat)w/(GLfloat)h,2.0*(GLfloat)w/(GLfloat)h,2.0,20.0);/*或者用gluPerspective(45.0,w/h,1.0,10.0);*/glMatrixMode(GL_MODELVIEW);}3710.6OpenGL相關(guān)函數(shù)voidmouse(intbtn,intstate,intx,inty){if(btn==GLUT_LEFT_BUTTON&&state==GLUT_DOWN)axis=0;if(btn==GLUT_MIDDLE_BUTTON&&state==GLUT_DOWN)axis=1;if(btn==GLUT_RIGHT_BUTTON&&state==GLUT_DOWN)axis=2; theta[axis]+=2.0;if(theta[axis]>360.0)theta[axis]-=360.0;display();}3810.6OpenGL相關(guān)函數(shù)intmain(intargc,char**argv){glutInit(&argc,argv);glutInitDisplayMode(GLUT_DOUBLE|GLUT_RGB);glutInitWindowSize(300,300);glutCreateWindow("cube");glutDisplayFunc(display);glutReshapeFunc(myReshape);glutMouseFunc(mouse);glutKeyboardFunc(keys);

glPolygonMode(GL_FRONT_AND_BACK,GL_LINE);glEnable(GL_CULL_FACE);glCullFace(GL_BACK);

glutMainLoop();}無剔除剔除39深度緩存函數(shù)顯示模式：glutInitDisplayMode(××|××|GLUT_DEPTH)深度緩存初始化：glClear(GL_DEPTH_BUFFER_BIT)（1）在每顯示新的一幀前清除（2）設(shè)置的默認(rèn)值為1（3）設(shè)置初始值：glClearDepth（maxDepth）激活：glEnable(GL_DEPTH_TEST);(默認(rèn)為不激活）10.6OpenGL相關(guān)函數(shù)4010.6OpenGL相關(guān)函數(shù)例：Z-Buffer消隱#include<stdlib.h>#include<GL/glut.h>GLfloatvertices[][3]={{-1.0,-1.0,-1.0},{1.0,-1.0,-1.0},{1.0,1.0,-1.0},{-1.0,1.0,-1.0},{-1.0,-1.0,1.0},{1.0,-1.0,1.0},{1.0,1.0,1.0},{-1.0,1.0,1.0}};staticGLfloattheta[]={0.0,0.0,0.0};staticGLintaxis=2;staticGLdoubleviewer[]={0.0,0.0,5.0};voidpolygon(inta,intb,intc,intd){glBegin(GL_POLYGON);glVertex3fv(vertices[a]);glVertex3fv(vertices[b]);glVertex3fv(vertices[c]);glVertex3fv(vertices[d]);glEnd();}4110.6OpenGL相關(guān)函數(shù)voidcolorcube(){//正前面

glColor3f(1,1,1);polygon(4,5,6,7);//正背面

glColor3f(1.0,0,0);polygon(0,3,2,1);glColor3f(0,1,0);polygon(2,3,7,6);glColor3f(0,0,1);polygon(0,4,7,3);glColor3f(1,1,0);polygon(1,2,6,5);glColor3f(0,1,1);polygon(0,1,5,4);}voiddisplay(){glClear(GL_COLOR_BUFFER_BIT|GL_DEPTH_BUFFER_BIT);glClearDepth(1);glLoadIdentity();//更新視點(diǎn)位置

gluLookAt(viewer[0],viewer[1],viewer[2],0.0,0.0,0.0,0.0,1.0,0.0);glRotatef(theta[0],1.0,0.0,0.0);glRotatef(theta[1],0.0,1.0,0.0);/*旋轉(zhuǎn)立方體*/glRotatef(theta[2],0.0,0.0,1.0);colorcube();glutSwapBuffers();}4210.6OpenGL相關(guān)函數(shù)voidkeys(unsignedcharkey,intx,inty){/*用x,X,y,Y,z,andZ鍵移動(dòng)視點(diǎn)*/if(key=='x')viewer[0]-=1.0;if(key=='X')viewer[0]+=1.0;if(key=='y')viewer[1]-=1.0;if(key=='Y')viewer[1]+=1.0;if(key=='z')viewer[2]-=1.0;if(key=='Z')viewer[2]+=1.0;display();}voidmyReshape(intw,inth){gl