《計算機圖形學(xué)》練習(xí)習(xí)題(答案)

1、計算機圖形學(xué)練習(xí)題1直線掃描轉(zhuǎn)換的Bresenham算法(1) 請寫出生成其斜率介于0和1之間的直線的Bresenham算法步驟。(2) 設(shè)一直線段的起點和終點坐標分別為(1,1)和(8,5)，請用Bresenham算法生成此直線段，確定所有要繪制象素坐標。(1)輸入線段的兩個端點，并將左端點存儲在(x0,y0)中 將(x0,y0)裝入幀緩存，畫出第一個點 計算常量x, y, 2y, and 2y-2x,并得到?jīng)Q策參數(shù)的第一個值： p0 = 2y - x 從k=0開始，在沿線路徑的每個xk處，進行下列檢測: 如果pk < 0,下一個要繪制的點就是(xk +1,yk) ，并且pk+1 =

2、pk + 2y 否則下一個要繪制的點就是(xk +1, yk +1)，并且 pk+1 = pk + 2y- 2x 重復(fù)步驟4，共 x-1次(2) m=(5-1)/(8-1)= x=7 y=4 P0=2y-x=1 2y=8 2y-2x=-6 kpk(xk+1,yk+1)01 (2,2) 1-5 (3,2)23 (4,3)3-3 (5,3)45 (6,4)5-1 (7,4)67 (8,5)2已知一多邊形如圖1所示，其頂點為V1、V2、V3、V4、V5、V6，邊為E1、E2、E3、E4、E5、E6。用多邊形的掃描填充算法對此多邊形進行填充時(掃描線從下到上)要建立邊分類表(sorted edge t

3、able)并不斷更新活化邊表(active edge list)。(1) 在表1中填寫邊分類表中每條掃描線上包含的邊(標明邊號即可)；(2) 在表2中寫出邊分類表中每條邊結(jié)構(gòu)中各成員變量的初始值(3) 指出位于掃描線y=6,7,8,9和10時活化邊表中包含那些邊，并寫出這些邊中的x值、ymax值、和斜率的倒數(shù)值1/m。x481圖1多邊形的邊和頂點y1482356791023567910V1V2V3V4V5V6E1E2E3E4E5E6表1邊分類表Y值(Scan Line Number)邊(Edge Number)1020304E15E6,E26E67E38E5,E39E4100123456789

4、10表2 邊的初始值邊xymax1/m41 1 97 4 60 051 97 60 061 96 6 0 071 1 87 7 90 1 -182 79 91 -193 3 69 9 91 -13. 二維變換(1) 記P(xf,yf)為固定點，sx、sy分別為沿x軸和y軸方向的縮放系數(shù)，請用齊次坐標(Homogeneous Coordinate)表示寫出二維固定點縮放變換的變換矩陣。(2) 把以A(0,0)、B(1,1)和C(5,2)為頂點的三角形以頂點C為固定點放大2倍。求出放大后的三角形的頂點坐標。(1) (2)平移這個對象，使得他的固定點與原點重合 縮放這個在坐標原點的對象 平移這個對象

5、，使得他的固定點回到原始位置 所以 A(-5,-2) B(-3,0) C(5,2)4二維變換(1) 請用齊次坐標表示寫出點Q(x,y)繞定點P(a,b)旋轉(zhuǎn)的旋轉(zhuǎn)變換矩陣。(2) 求出以A(0,0)、B(1,1)和C(5,2)為頂點的三角形繞固定點P(-1,-1)點旋轉(zhuǎn)450后的三角形的頂點坐標。(1) x=xr+(x- xr)cos -(y- yr)sin y=yr+(x- xr)sin +(y- yr)cos (2)平移這個對象，使得他的固定點與原點重合 旋轉(zhuǎn)這個在坐標原點的對象 平移這個對象，使得他的固定點回到原始位置 A(-1,-1+) B(-1,-1+2) C(-1+3/2*,-1+

6、9/2*)5. 如圖所示，L(-3,1)和R(2,6)為正方形裁剪窗口兩個對角線角點，線段AB、CD、EF、GH和IJ為被裁剪線段。用Cohen-Sutherland線裁剪算法進行裁剪時要對線段的端點進行編碼。(1) 請寫出編碼規(guī)則，并在圖中標出相應(yīng)區(qū)域的編碼(2) 分別指出于點A、B、C、D、E、F、G、H對應(yīng)的編碼(3) 根據(jù)線段端點的編碼對圖中所有線段分類，指出哪些線段是可見的哪些是不可見的哪些是候選的裁剪線段。 J(-2,10)D(3,8)B(-1,7)I(-4,7)R(2,6)C(-1,5)E(-2,3)H(3,3)A(-4,2)F(1,2)L(-3,1)1-113-1G(1,-2)

7、（1）100110001010000100000010010101000110（2）A:0001B:1000C:0000D:1010E:0000F:0000G:0100H:0010I:1000J:1000（3）可見的：EF不可見的：GH,IJ候選的：AB,CD6. 分別用Sutherland-Hodgman算法和Weiler-Atherton算法裁剪圖1所示的多邊形p1p2p3p4p5p6p7p8p9p1，裁剪窗口為如圖所示的矩形窗口。要求：(1) 用實線分別在圖1(a)(b)(c)(d)中繪出用Sutherland-Hodgman算法沿裁剪窗口的左、右、上、下窗口邊裁剪后的中間結(jié)果 (2)

8、用Weiler-Atherton算法對圖1所示的多邊形進行裁剪，以p1為起點，以圖1箭頭所示的方向為走向，在圖1(e)中用箭頭表示畫出所有走過的邊(包括多邊形邊和窗口邊)及其走向；并在圖1(f)中用實線繪出最后裁剪結(jié)果。圖1(a)P1P2P3P4P5P6P7P8P9圖1(b)P1P2P3P4P5P6P7P8P9圖1多邊形裁剪P1P2P3P4P5P6P7P8P9圖1(c)P1P2P3P4P5P6P7P8P9圖1(d)P1P2P3P4P5P6P7P8P9圖1(e)P1P2P3P4P5P6P7P8P9圖1(f)P1P2P3P4P5P6P7P8P97 簡述多邊形掃描填充算法基本原理和大致步驟，并以具體

9、例子說明邊分類表內(nèi)容、掃描過程中活化邊表的信息變化。(1)原理：在直角坐標系中，假設(shè)有一條從左至右的掃描線穿過多邊形，從左至右開始計數(shù)，與多邊形交點為奇數(shù)時，開始進入多邊形，與多邊形交點為偶數(shù)時，走出多邊形。這樣在這相鄰配對的奇偶交點間的所有象素都在多邊形內(nèi)。如圖，奇數(shù)交點a，c，都是入多邊形，偶數(shù)交點b，d都是走出多邊形，相鄰的奇偶交點配對，a，b之間，c，d之間的象素都多邊形內(nèi)，可見一條掃描線上，與多邊形交點個數(shù)需要為偶數(shù)。依據(jù)這樣的思路，掃描線從上到下從左到右依次掃過多邊形即可求得多邊形所占據(jù)的象素。（注意退化情況的處理，也就是掃描線剛好經(jīng)過頂點或者多邊形的邊本身就是水平的情況） (2)

10、步驟： 1)輸入多邊形的頂點的坐標 2)建立邊表（ET） 3)初始化Y值 4)初始化活性邊表（AEL），設(shè)置為空 5)每個掃描線從底部到頂部，做以下步驟直到ET和AEL是空的： 建立AEL 設(shè)置顏色 更新AEL： 當Y= YMAX時,刪除邊 x = x +X Y = y + 1 返回AEL(3) 例子：8 由坐標A(0,0,0)，B(1,0,0)，C(0,1,0)，D(0,01)確定的錐體繞直線L旋轉(zhuǎn)450,其中L的方向為V=J+K，且通過點C(0,1,0)。寫出錐體旋轉(zhuǎn)后的坐標。9.設(shè)3次參數(shù)多項式函數(shù)P(u)=au3+bu2+cu+d,求出滿足下列邊

11、界條件的3次Hermite插值曲線(用矩陣表示): P(0) = Pk P(1) = Pk+1 P(0) = DPk P(1) = DPk+1直線段裁剪算法和Liang-Barsky直線段裁剪算法是直線段裁剪的兩種基本算法，試述兩種算法的基本原理，并分析它們的優(yōu)點和不足。（1）通過一個矩形的裁剪區(qū)域?qū)⒄麄€屏幕分成9個部分，并為每一個部分賦予相應(yīng)的區(qū)域碼，然后根據(jù)端點的位置確定這個端點的區(qū)域碼。先判斷能否完全接受或者完全排除一條線段，若以上2個判斷無法直接得出，則逐步裁剪，選取一個位于裁剪區(qū)外的端點，把端點的區(qū)域碼和裁剪邊界的區(qū)域碼進行邏輯與運算，若結(jié)果為真，則端點在該裁剪邊界外部，這時將端點移

12、向線段和該邊界的交點處，如此循環(huán)，直到裁剪結(jié)束。（2）利用線段的參數(shù)表達形式直接判別落在窗口內(nèi)的部分線段.大體上有以下幾步,有些步驟依據(jù)中間的判斷結(jié)果可以省略或跳轉(zhuǎn).第一步：計算出pk和qk(k=1,2,3,4)第二步：看pki的符號進行判斷第三步：計算u1=max(0,qk/pk),u2=min(1,qk/pk) 如果,u2>u1,則線段是可見的第四步：利用u1和u2計算端點坐標（3） 比較：Cohen-Sutherland：直觀方便，速度較快 多次重復(fù)計算線段與裁剪窗口邊界的交點，計算量大 采用位邏輯乘，在有些高級語言中不便進行 全部舍棄的判斷僅適用于那些僅在窗口的線段，不適合跨越三

13、個區(qū)域的 線段，就不能一次做出判別Liang-Barsky：所需計算量小，更有效 可以擴展成三維裁剪算法 只能應(yīng)用于矩陣窗口的情形 10. 簡述Bezier曲線與B-Spline曲線的異同點，指出他們的特點和不足。11. DDA算法和Bresenham算法是兩種直線生成的基本算法，試述兩種算法的基本原理，并分析它們的優(yōu)點和不足。（1） DDA算法：選定x2x1和y2y1中較大者作為步進方向(假設(shè)x2x1較大)，取該方向上的增量為一個象素單位(x=1)，利用式(21)計算另一個方向的增量(y=x·m=m)。通過遞推公式(22)至(25)，把每次計算出的(xi+1，yi+1)經(jīng)取整后送到

14、顯示器輸出，則得到掃描轉(zhuǎn)換后的直線。之所以取x2x1和y2y1中較大者作為步進方向，是考慮沿著線段分布的象素應(yīng)均勻，這在下圖中可看出。另外，算法實現(xiàn)中還應(yīng)注意直線的生成方向，以決定x及y是取正值還是負值。（2） Bresenham算法：假定直線斜率k在01之間。此時，只需考慮x方向每次遞增1個單位，決定y方向每次遞增0或1。 設(shè)：直線當前點為(xi,y)直線當前光柵點為(xi,yi)則：下一個直線的點應(yīng)為(xi+1,y+k) 下一個直線的光柵點為右光柵點(xi+1,yi)（y方向遞增量0）或為右上光柵點(xi+1,yi+1)（y方向遞增量1）（3） 優(yōu)缺點：DDA算法：算法簡單，實現(xiàn)容易 由于

15、在循環(huán)中涉及實型數(shù)的運算，因此生成直線的速度較慢。 浮點數(shù)運算  不易硬件實現(xiàn)Bresenham算法：不必計算直線之斜率,因此不做除法;  不用浮點數(shù),只用整數(shù);  只做整數(shù)加減法和乘2運算,而乘2運算可以用硬件移位實現(xiàn).  算法速度很快,并適于用硬件實現(xiàn). 12. 簡述直線段裁剪與多邊形裁剪的異同點。多邊形的剪裁比直線剪裁復(fù)雜。如果按照直線剪裁算法對多邊形的邊作剪裁，剪裁后的多邊形的邊就會成為一組彼此不連貫的折線，從而給填色帶來困難。多邊形剪裁算法的關(guān)鍵在于，通過剪裁，不僅要保持窗口內(nèi)多邊形的邊界部分，而且要將窗框的有關(guān)部分按一定次序插入多邊

16、形的保留邊界之間，從而使剪裁后的多邊形的邊仍然保持封閉狀態(tài)，以便填色算法得以正確實現(xiàn)13. 在計算機輔助設(shè)計與圖形學(xué)中，樣條曲線通常采用3次多項式參數(shù)表示，請說明理由。14. 圖形學(xué)中消隱算法有兩大類，z緩沖器(z-buffer)算法屬于哪一類請闡述它的基本原理和特點。(1)屬于圖像空間消隱(2)基本原理：Z緩沖器中每個單元的值是對應(yīng)象素點所反映對象的z坐標值。Z緩沖器中每個單元的初值取成z的極小值，幀緩沖器每個單元的初值可放對應(yīng)背景顏色的值。圖形消隱的過程就是給幀緩沖器和Z緩沖器中相應(yīng)單元填值的過程。在把顯示對象的每個面上每一點的屬性（顏色或灰度）值填入幀緩沖器相應(yīng)單元前，要把這點的z坐標值

17、和z緩沖器中相應(yīng)單元的值進行比較。只有前者大于后者時才改變幀緩沖器的那一單元的值，同時z緩沖器中相應(yīng)單元的值也要改成這點的z坐標值。如果這點的z坐標值小于z緩沖器中的值，則說明對應(yīng)象素已經(jīng)顯示了對象上一個點的屬性，該點要比考慮的點更接近觀察點。對顯示對象的每個面上的每個點都做了上述處理后，便可得到消除了隱藏面的圖(3)特點：優(yōu)點：（1） 算法復(fù)雜度(O(nN)：對于給定的圖像空間，N是固定的，所以算法復(fù)雜度只會隨著場 景的復(fù)雜度線性地增加（2） 無須排序：場景中的物體是按任意順序?qū)懭霂彌_器和z緩沖器的，無須對物體進行 排序，從而節(jié)省了排序的時間（3）適合于任何幾何物體：能夠計算與直線交點（4

18、）適合于并行實現(xiàn)(硬件加速)不足：（1）z緩沖器需要占用大量的存儲單元：一個大規(guī)模復(fù)雜場景中：深度范圍可能為106，一個像素需要24bit來存儲其深度信息。 如果顯示分辨率為1280×1024，那么深度緩沖器需要4MB存儲空間（2）深度的采樣與量化帶來走樣現(xiàn)象（3）難以處理透明物體解決存儲問題：逐區(qū)域進行z緩沖器消隱(A-Buffer method: accumulation buffer)16. OpenGL庫函數(shù)由哪幾部分組成，請簡單說說各部分的分工。 (1)OpenGL核心庫 核心庫包含有115個函數(shù)，函數(shù)名的前綴為gl。 這部分函數(shù)用于常規(guī)的、核心的圖形處理。 (2)OpenGL實用庫The OpenGL Utility Library (GLU)包含有43個函數(shù)，函數(shù)名的前綴為glu。 OpenGL提供了強大的但是為數(shù)不多的繪圖命令，所有較復(fù)雜的繪圖都必須從點。線、面開始。Glu 為了減輕繁重的編程工作，封裝了OpenGL函數(shù)，Glu函數(shù)通過調(diào)用核心庫的