第10講 圖形消隱

第10講圖形消隱

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

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

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

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

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

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

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

Q

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

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

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

nmax(P)

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

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

的所有頂點位于Q

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

所在平面的可見的一側(cè)(圖c)，則P,Q關(guān)系正確，令L=L–{P},返回2）;否則進行下一步（D）對P,Q投影P’,Q’求交，若P’,Q’不相交(圖d)，則P,Q在表中的次序不重要，令L=L–{P},返回2）;否則在它們所相交的區(qū)域中任取一點，計算P,Q在該點的深度值，如果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

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

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

A：如果大于，說明當前多邊形更靠近觀察點，用它的顏色替換像素原來的顏色；同時保存深度值

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

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

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

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

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

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

2）不需要整個場景的幾何數(shù)據(jù)缺點

1）需要一個額外的Z緩沖器

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

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

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

{

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

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

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

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

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

置Z緩沖器的第u單元值為d;}}}}//處理下一條掃描線10.5掃描線Z緩沖器算法32缺點在每一個被多邊形覆蓋像素處需要計算深度值被多個多邊形覆蓋的像素需要多次計算深度值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();//更新視點位置

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鍵移動視點*/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è)置的默認值為1（3）設(shè)置初始值：glClearDepth（maxDepth）激活：glEnable(GL_DEPTH_TEST);(默認為不激活）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();//更新視點位置

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鍵移動視點*/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