計(jì)算機(jī)圖形學(xué)CG07-二維觀察

第7章

二維觀察1本章目標(biāo)理解二維圖形的繪制過程圖形裁剪方法窗口到視區(qū)的變換學(xué)會(huì)使用OpenGL的顯示函數(shù)2主要內(nèi)容二維觀察流水線窗口到視區(qū)的變換OpenGL二維觀察函數(shù)裁剪直線段裁剪多邊形裁剪字符裁剪37.1二維觀察流水線幾個(gè)概念裁剪窗口(ClippingWindow)：需要顯示的場(chǎng)景區(qū)域又稱為世界窗口或觀察窗口，簡(jiǎn)稱窗口在世界坐標(biāo)系（又稱用戶坐標(biāo)系）內(nèi)定義視口(Viewport)：指顯示設(shè)備上用來顯示圖形的區(qū)域又稱視區(qū)，在設(shè)備（屏幕）坐標(biāo)系內(nèi)定義裁剪(Clip)：從場(chǎng)景中確定位于窗口內(nèi)的圖形視口屏幕47.1二維觀察流水線裁剪窗口和視區(qū)的關(guān)系改變視口位置可以在輸出設(shè)備的不同位置上觀察物體使用多個(gè)視口可以在屏幕不同的位置觀察場(chǎng)景的不同部分改變窗口的尺寸達(dá)到改變視口內(nèi)顯示對(duì)象的多少改變視口的尺寸實(shí)現(xiàn)對(duì)象放縮57.1二維觀察流水線二維觀察變換二維世界坐標(biāo)系場(chǎng)景描述到設(shè)備坐標(biāo)系的映射又稱為窗口到視區(qū)的變換或窗口變換二維圖形的觀察流水線（顯示流程）幾何變換裁剪67.2窗口到視區(qū)的變換目標(biāo)將窗口之中的圖形變換到視區(qū)中變換的計(jì)算變換的分解與合成窗口

(xmin,ymin):長(zhǎng)度（Ex）;寬度（Ey）視區(qū)(umin,vmin):長(zhǎng)度（Eu）;寬度（Ev）？77.2窗口到視區(qū)的變換步驟在世界坐標(biāo)系中，平移使(xmin,ymin)至坐標(biāo)原點(diǎn)，變換為T(－xmin,－ymin)放縮使窗口的大小與視區(qū)相等，變換為S(Eu/Ex,Ev/Ey)在設(shè)備坐標(biāo)系中，平移使窗口與視區(qū)重合，變換為T(umin,vmin)87.2窗口到視區(qū)的變換變換矩陣注意:這里不需要逆變換97.3OpenGL二維觀察函數(shù)流程程序窗口－>裁剪窗口－>視區(qū)GLUT顯示窗口初始化：glutInit(&argc,argv);//參數(shù)與main函數(shù)一致位置：glutInitWindowPosition(xTopLeft,yTopLeft);大?。篻lutInitWindowSize(dwWidth,dwHeight);建立：glutCreateWindow(“TitleofDisplayWindows”);模式：glutInitDisplayMode(mode);選擇顏色和緩存,如GLUT_RGB|GLUT_SINGLE背景顏色：glClearColor(red,green,blue,alpha)參數(shù)與選擇的顏色模式相關(guān)，取值在0和1之間107.3OpenGL二維觀察函數(shù)投影模式OpenGL專門為三維應(yīng)用而設(shè)計(jì)，但可將三維觀察函數(shù)應(yīng)用于二維觀察投影函數(shù)

glMatrixMode(GL_PROJECTION);//指定投影矩陣為當(dāng)前矩陣

glLoadIdentity();//初始化GLU裁剪窗口函數(shù)定義函數(shù)：gluOrtho2D(left,right,bottom,top);功能：將場(chǎng)景映射到屏幕的正交投影參數(shù)為4個(gè)平面（3維）默認(rèn)大小為（－1，1，－1，1）117.3OpenGL二維觀察函數(shù)OpenGL視口函數(shù)定義函數(shù)：glViewport(xvmin,yvmin,vpwidth,vpheight);視口為矩形在視口內(nèi)繪制圖形對(duì)象指定顯示內(nèi)容函數(shù)：glutDisplayFunc(pictureDescrip)pictureDescrip為回調(diào)函數(shù)，主要繪制圖形啟動(dòng)程序glutMainLoop()127.3OpenGL二維觀察函數(shù)實(shí)例7-1#include<gl/glut.h>#include<stdlib.h>#include<math.h>classwcPt2D{public:GLfloatx,y;};voidinit(void){

glClearColor(1.0,1.0,1.0,0.0);//設(shè)置裁剪窗口

glMatrixMode(GL_PROJECTION);gluOrtho2D(-100.0,100.0,-100.0,100.0);//幾何變換矩陣模式

glMatrixMode(GL_MODELVIEW);}137.3OpenGL二維觀察函數(shù)實(shí)例7-1（續(xù)）voidtriangle(wcPt2D*verts){

GLintk;

glBegin(GL_TRIANGLES);for(k=0;k<3;k++)glVertex2f(verts[k].x,verts[k].y);

glEnd();}voidviewport(floatx0,floaty0,floatx1,floaty1){

glBegin(GL_LINE_LOOP);glVertex2i(x0,y0);glVertex2i(x1,y0);glVertex2i(x1,y1);glVertex2i(x0,y1);

glEnd();}147.3OpenGL二維觀察函數(shù)實(shí)例7-1（續(xù)）voiddisplayFcn(void){//定義三角形

wcPt2Dverts[3]={{-50.0,-25.0},{50.0,-25.0},{0.0,50.0}};

glClear(GL_COLOR_BUFFER_BIT);//清屏

glLoadIdentity();glColor3f(0.0,0.0,1.0);

glViewport(0,0,300,300);triangle(verts); glColor3f(0.0,1.0,0.0);viewport(-100,-100,100,100);/*旋轉(zhuǎn)三角形并在右半窗口*/glColor3f(1.0,0.0,0.0);

glViewport(300,0,300,300);

glRotatef(180.0,0.0,0.0,1.0);triangle(verts);viewport(-100,-100,100,100);

glFlush();}157.3OpenGL二維觀察函數(shù)實(shí)例7-1（續(xù)）voidmain(int

argc,char**argv){

glutInit(&argc,argv);

glutInitDisplayMode(GLUT_SINGLE|GLUT_RGB);

glutInitWindowPosition(50,50);

glutInitWindowSize(600,300);

glutCreateWindow("Split-ScreenExample");init();

glutDisplayFunc(displayFcn);

glutMainLoop();}167.3OpenGL二維觀察函數(shù)問題圖形越出視口？只繪制視口內(nèi)還是全繪制？voiddisplayFcn(void){wcPt2Dverts[3]={{-50.0,-25.0},{50.0,-25.0},{0.0,50.0}};

glClear(GL_COLOR_BUFFER_BIT);

glLoadIdentity();glColor3f(0.0,0.0,1.0);

glViewport(0,0,300,300);triangle(verts); glColor3f(0.0,1.0,0.0);viewport(-100,-100,100,100);

glColor3f(1.0,0.0,0.0);

glViewport(300,0,300,300);

glPushMatrix();glTranslatef(80,0,0);

glRotatef(180.0,0.0,0.0,1.0);triangle(verts);

glPopMatrix();

viewport(-100,-100,100,100);

glFlush();}177.4

裁剪流程二維顯示流程掃描轉(zhuǎn)換+裁剪算法簡(jiǎn)單（判斷像素是否落在視區(qū)中）裁剪+掃描轉(zhuǎn)換最常用，節(jié)約計(jì)算時(shí)間（先對(duì)參數(shù)表示的圖形裁剪）187.4

裁剪裁剪（clip）判斷圖形元素是否落在裁剪窗口之內(nèi)并找出其位于內(nèi)部的部分裁剪處理的主要步驟圖元關(guān)于窗口內(nèi)外關(guān)系的判別圖元與窗口的求交假定條件矩形裁剪窗口：[xmin,

ymin]－[xmax,ymax]主要內(nèi)容：線段、多邊形裁剪裁剪窗口197.5直線段裁剪待裁剪線段待裁剪線段和窗口的關(guān)系線段完全可見：端點(diǎn)位于窗口內(nèi)顯然不可見：端點(diǎn)位于邊界同側(cè)線段至少有一端點(diǎn)在窗口之外，但非顯然不可見為提高效率，算法設(shè)計(jì)時(shí)應(yīng)考慮：(一）快速判斷情形(1)(2)(二)設(shè)法減少情形(3)求交次數(shù)和每次求交時(shí)所需的計(jì)算量(非盲目求交)207.5.1點(diǎn)裁剪線段的特殊情況兩端點(diǎn)重合點(diǎn)(x,y)在窗口內(nèi)的充分必要條件是問題：對(duì)于任何多邊形裁剪窗口，如何判別？217.5.2直接求交算法端點(diǎn)與窗口位置關(guān)系都在窗口內(nèi)（完全可見）1個(gè)在窗口內(nèi)，另一個(gè)在外(有1個(gè)交點(diǎn))2個(gè)都不在窗口內(nèi)可能相交可能不相交P5P2P3P4P1P6P7P8P9P10227.5.2直接求交算法計(jì)算交點(diǎn)方法線段與窗口的邊求交點(diǎn)直線與窗口邊都寫成參數(shù)形式，求參數(shù)值只有當(dāng)

s和

t同時(shí)落在[0,1]區(qū)間上的交點(diǎn)才算有效交點(diǎn)（x0,y0）（x1,y1）（x’0,y’0）（x’1,y’1）237.5.2直接求交算法算法流程特點(diǎn)方法直接，易懂不能快速判斷顯然不可見的線段247.5.3編碼算法Cohen-Sutherland算法(編碼算法)算法步驟（思想）第一步判別線段兩端點(diǎn)是否都落在窗口內(nèi)，如果是，則線段完全可見；否則進(jìn)入第二步；第二步判別線段是否為顯然不可見，如果是，則裁剪結(jié)束；否則進(jìn)行第三步；第三步求線段與窗口邊延長(zhǎng)線的交點(diǎn)，這個(gè)交點(diǎn)將線段分為兩段，其中一段顯然不可見，丟棄。對(duì)余下的另一段重新進(jìn)行第一步，第二步，第三步處理，直至結(jié)束257.5.3編碼算法區(qū)域編碼由窗口四條邊所在直線把二維平面分成9個(gè)區(qū)域，每個(gè)區(qū)域賦予一個(gè)四位編碼，CtCbCrCl，上下左右267.5.3編碼算法端點(diǎn)編碼：定義為它所在區(qū)域的編碼根據(jù)頂點(diǎn)編碼判斷線段與多邊形的關(guān)系當(dāng)兩個(gè)端點(diǎn)的編碼全為0時(shí)，線段完全可見當(dāng)線段的兩個(gè)端點(diǎn)的編碼的邏輯“與”非零時(shí)，線段為顯然不可見的277.5.3編碼算法對(duì)于那些非完全可見、又非顯然不可見的線段，需要求交（如，線段CD)求交前先測(cè)試與窗口哪條邊所在直線有交？規(guī)則：判斷端點(diǎn)編碼中各位的值CtCbCrCl分別對(duì)應(yīng)：上、下、右和左邊端點(diǎn)碼值位值不同時(shí)，說明線段與對(duì)應(yīng)窗口邊相交次序：上、下、右和左邊以交點(diǎn)為界，丟棄外側(cè)線段，以交點(diǎn)為新端點(diǎn)判斷另一線段，重復(fù)上述過程如：CDC：0000D:1000Ct位不同，與上邊相交287.5.3編碼算法例DKMABCEFGHJINLO最多求交次數(shù)為4AB:與窗口左邊相交，求交點(diǎn)H,AH和BH顯然不可見EF:與窗口上邊交點(diǎn)I,棄EI

與窗口下邊交點(diǎn)K,棄KF

與窗口右邊交點(diǎn)K，棄KJ

保留IJCD:與窗口上邊交點(diǎn)L,棄CL與窗口下邊交點(diǎn)O,棄OD與窗口右邊交點(diǎn)M,棄LM與窗口左邊交點(diǎn)N,棄NO

保留MN297.5.3編碼算法特點(diǎn)對(duì)完全可見和顯然不可見線段的快速判別適用二種場(chǎng)合大裁剪窗口裁剪窗口特別小(如,光標(biāo)拾取圖形時(shí)，光標(biāo)看作小的裁剪窗口）裁剪窗口的拓展性可以延伸為凸多邊形，但隨著邊數(shù)的增加，編碼變復(fù)雜307.5.3編碼算法應(yīng)用：圖形拾取定義：選擇顯示的圖形元素操作：由光標(biāo)位置確定方法：以光標(biāo)位置為中心建立小矩形，判斷圖形被矩形裁剪后是否有局部圖形落在矩形內(nèi)。317.5.4中點(diǎn)分割法基本思想從P0點(diǎn)出發(fā)找出距P0最近的可見點(diǎn)A從P1點(diǎn)出發(fā)找出距P1最近的可見點(diǎn)BAB為可見部分中點(diǎn)法（求離P0最近的可見點(diǎn)）（1）取中點(diǎn)Pm=(P0+P1)/2（2）如P0

Pm不是顯然不可見，且P0P1在窗口中有可見部分，則距P0最近的可見點(diǎn)一定落在P0Pm上，所以用P0Pm代替P0P1；否則用PmP1代替P0P1（3）再對(duì)新的P0P1重復(fù)（1）（2），直到長(zhǎng)度小于給定的控制常數(shù)ε為止。327.5.4中點(diǎn)分割法說明ε取1（像素）;二分過程為N（分辨率為2N×2N

）次求P1的最近可見點(diǎn)方法類似算法框圖見右方(離P0)最近可見點(diǎn)）算法特點(diǎn)適合硬件實(shí)現(xiàn)適合并行計(jì)算不能直接判斷完全可見與顯然不可見337.5.5Liang-Barsky基本思想將二維裁剪化為一維裁剪，向X（或Y）方向投影以決定可見線段前提平行于X或Y的線段較容易，這里不作考慮假設(shè)P0P1為或其延長(zhǎng)線分別與窗口左、下、右和上邊（或其延長(zhǎng)線）交于L，B，R，T347.5.5Liang-Barsky方法P0P1所在直線l于裁剪窗口的交Q1Q2為Q1Q2：l∩□＝

l∩(△1∩△2)

＝(l∩△1)∩(l∩△2)

＝LR∩TBP0P1在窗口中的可見部分VW：P0P1∩Q1Q2

＝P0P1∩(LR∩TB)

＝P0P1∩LR∩TBQ1Q2稱為誘導(dǎo)窗口P0P1存在可見部分的充要條件：VW≠φLBRT△1△2□P0P1357.5.5Liang-Barsky投影：（X軸）確定可見線段上點(diǎn)的X坐標(biāo)范圍(1)P0P1：(2)LR：(3)TB：(4)VW上點(diǎn)X坐標(biāo)范圍為：

max(xmin,min(xT,xB),min(x0,x1))≤

x≤

min(xmax,max(x0,x1),max(xT,xB))令左式為xα,右式為xβ,則VW為可見的充要條件是：

xα

≤

xβ(min(x0,x1),max(x0,x1))(xmin,xmax)(min(xT,xB),max(xT,xB))36計(jì)算交點(diǎn)xT,xB（x0≠x1，y0≠y1）直線l（P0P1

所在直線）：交點(diǎn)坐標(biāo)：VW坐標(biāo)：7.5.5Liang-Barsky377.5.5Liang-Barsky改進(jìn)(減少求交點(diǎn)次數(shù)）max(xmin,min(xT,xB),min(x0,x1))≤

x≤

min(xmax,max(x0,x1),max(xT,xB))令LL=max(xmin,min(x0,x1))令RR=min(xmax,max(x0,x1))VW上點(diǎn)X坐標(biāo)范圍可表示為：

max(LL,min(xT,xB))≤

x≤

min(RR,max(xT,xB))充要條件變?yōu)?8xT與xB的關(guān)系P0P1斜率K>0:

max(xT,xB)=xT;min(xT,xB)=xBP0P1斜率K<0:

max(xT,xB)=xB;min(xT,xB)=xT7.5.5Liang-Barsky39算法(1)先測(cè)試LL≤RR？不成立，不存在可見線段，退出；否則，執(zhí)行（2）(2)線段P1P2的斜率K>0?不是執(zhí)行（3），否則執(zhí)行。計(jì)算xT,測(cè)試LL≤xT？若成立，計(jì)算xB，測(cè)試xB≤RR？若成立，有可見線段：xα

=max(LL，xB);xβ=min(RR，xT)(3)K<0:計(jì)算xB,測(cè)試LL≤xB？若成立，計(jì)算xT，測(cè)試xT≤R？若成立，有可見線段：xα

=max(LL,xT);

xβ=min(RR,xB)特點(diǎn)二維轉(zhuǎn)化為一維按需求交點(diǎn)，提高效率7.5.5Liang-Barsky407.6多邊形裁剪錯(cuò)覺多邊形邊界是直線段的組合，那么能否利用線段裁剪算法？不能用線段裁剪方法主多邊形417.6多邊形裁剪問題1）因?yàn)檫吔绮辉俜忾]，需要用窗口邊界的恰當(dāng)部分來封閉它，如何確定其邊界？裁剪結(jié)果多邊形的邊由裁剪多邊形和主多邊形的邊（邊的一部分）構(gòu)成422）一個(gè)凹多邊形可能被裁剪成幾個(gè)小的多邊形，如何確定這些小多邊形的邊界？7.6多邊形裁剪43S-H算法基本思想將多邊形關(guān)于矩形窗口的裁剪分解為多邊形關(guān)于窗口四邊所在直線的裁剪步驟多邊形由一系列頂點(diǎn)表示：V1V2…Vn按一定(左上右下)的次序依次裁剪;與左邊所在直線裁剪的結(jié)果是上邊的輸入，依次類推輸出為頂點(diǎn)序列7.6.1

Sutherland-Hodgman算法亦稱逐邊裁剪算法447.6.1

Sutherland-Hodgman算法裁剪線裁剪輸入輸出：頂點(diǎn)序列V0V1V2V3V4….多邊形與窗口每條邊的裁剪裁剪線：窗口邊以及其延長(zhǎng)線內(nèi)側(cè)空間與外側(cè)空間包含裁剪窗口的半空間為內(nèi)側(cè)空間，否則為外側(cè)空間裁剪線內(nèi)側(cè)空間裁剪窗口外側(cè)空間457.6.1

Sutherland-Hodgman算法多邊形與窗口裁剪線的裁剪依據(jù)多邊形的邊SP與半空間的關(guān)系情況1：同在內(nèi)側(cè)，裁剪后輸出P情況2：S在內(nèi)側(cè)，P

在外側(cè)，裁剪后輸出交點(diǎn)

i情況3：同在外側(cè)，裁剪后不輸出情況4：S

在外側(cè)，P

在內(nèi)側(cè)，裁剪后輸出交點(diǎn)

i和P467.6.1

Sutherland-Hodgman算法算法將頂點(diǎn)序列P1P2…Pn作為輸入依次對(duì)窗口的每條裁剪線作下列處理輸入頂點(diǎn)序列依次頂點(diǎn)序列中相鄰頂點(diǎn)構(gòu)成的邊PiPi+1進(jìn)行裁剪處理輸出頂點(diǎn)序列（下條裁剪線的輸入）47例子7.6.1

Sutherland-Hodgman算法上：輸入

I1P2P3P4P5P6P7P8I2

輸出

P2I3I4P4P5P6P7P8I2I1下：輸入

I3I4P4I5I6P6P7P8I2I1P2

輸出

I4P4I5I6I7I8P8I2I1P2I3左：輸入

P1P2P3P4P5P6P7P8

輸出

I1P2P3P4P5P6P7P8I2右：輸入

P2I3I4P4P5P6P7P8I2I1

輸出

I3I4P4I5I6P6P7P8I2I1P2注意：（1）交點(diǎn)是邊與裁剪線的交點(diǎn)（2）邊的頂點(diǎn)是有序的48特點(diǎn)裁剪算法采用流水線方式，算法簡(jiǎn)單推廣到任意凸多邊形裁剪窗口原因是：凸多邊形的邊能將平面空間分成2部分，其中一部分含裁剪窗口7.6.1

Sutherland-Hodgman算法497.6.2Weiler-Athenton算法*裁剪窗口為任意多邊形（凸、凹、帶內(nèi)環(huán)）的情況主多邊形：被裁剪多邊形，記為A裁剪多邊形：裁剪窗口，記為B507.6.2Weiler-Athenton算法*主多邊形A被裁剪多邊形B裁剪后內(nèi)裁剪：A∩B外裁剪：A－B內(nèi)裁剪的特點(diǎn)裁剪結(jié)果區(qū)域的邊界由A的部分邊界和B的部分邊界兩部分構(gòu)成，并且在交點(diǎn)處邊界發(fā)生交替，即由A

的邊界轉(zhuǎn)至B的邊界，或由B的邊界轉(zhuǎn)至A的邊界51交點(diǎn)交點(diǎn)成對(duì)出現(xiàn)：既在A中也在B中兩類：（1）進(jìn)點(diǎn)：主多邊形邊界由此進(jìn)入裁剪多邊形內(nèi)如，I1,I3,I5,I7,I9,I11（2）出點(diǎn)：主多邊形邊界由此離開裁剪多邊形區(qū)域如，I0,I2,I4,I6,I8,I107.6.2Weiler-Athenton算法*BAA是主多邊形52內(nèi)裁剪算法步驟

1、建立主多邊形和裁剪多邊形的頂點(diǎn)表

2、求主多邊形和裁剪多邊形的交點(diǎn)，并將這些交點(diǎn)按順序插入兩多邊形的頂點(diǎn)表中。在兩多邊表形頂點(diǎn)表中的相同交點(diǎn)間建立雙向指針7.6.2Weiler-Athenton算法*533、裁剪如果存在沒有被跟蹤過的交點(diǎn)，執(zhí)行以下步驟

(1)建立裁剪