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

2、,yk),并且pk+1 = Pk + 2 ? y否則下一個要繪制的點就是(Xk +1, yk +1),并且 pk+1 = Pk + 2 ? y- 2? X 重復步驟4 ,共？ x-1次(2) m=(5-1)(8-1)=0.57x=7y=4P0=2 y- x=12 y=82 y-2x=-6kPk(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 ,邊為日、E2、E3、E4、E5、E6。用多邊形的掃描填充算法對此多邊形進行填充時(掃描線從下到上)要建立

3、邊分類表(SOrted edge table)并不斷更新活化邊表(active edge list)。(1) 在表1中填寫邊分類表中每條掃描線上包含的邊(標明邊號即可)；(2) 在表2中寫出邊分類表中每條邊結(jié)構(gòu)中各成員變量的初始值(3) 指出位于掃描線 y=6,7,8,9和10時活化邊表中包含那些邊，并寫出這些邊中的X值、ymax值、和斜率的倒數(shù)值 1/m。表1邊分類表2X表2邊的初始值邊Xymax1/m41197460 051 97 60 061 96 60 071 1 87790 1 -182 79 91 -1933699 91 -112345678910Y 值(SCa n LineNUm

4、ber)邊(EdgeNUmber)1020304E15E6,E26E67E38E5,E39E41003. 二維變換(1)記P(xf,yf)為固定點，sx、Sy分別為沿X軸和y軸方向的縮放系數(shù)，請用齊次坐標 (Homoge neous Coordi nate) 表示寫出二維固定點縮放變換的變換矩陣。把以A(0,0)、B(1,1)和 C(5,2)為頂點的三角形以頂點C為固定點放大2倍。求出放大后的三角形的頂點坐標。I 0 XJ Q 01 G -U I Oo-o 1 -0 0 10 0 10 0 1.0 Xr(I-JI)一 0 Sjf0 0 1(1)二 X7+(S% =yf-(y-yfyH二小氓十兀

5、0碼)二嚴虧+乃(1 一片)(2)平移這個對象，使得他的固定點與原點重合縮放這個在坐標原點的對象平移這個對象，使得他的固定點回到原始位置x'SX0Xf(1SX)Xry'0SyYf(1Sy)yr10011所以A(-5,-2)B(-3,0)C(5,2)4二維變換(1)請用齊次坐標表示寫出點 Q(x,y)繞定點P(a,b)旋轉(zhuǎn)的旋轉(zhuǎn)變換矩陣。求出以A(0,0)、B(1,1)和 C(5,2)為頂點的三角形繞固定點P(-1,-1)點旋轉(zhuǎn)45°后的三角形的頂點坐標。(1)IO一 Sin O1 O -耳O19Sin t?-O 1 -OO1OOIO O 1sf?SiIlXiH(I-

6、CoS) in 6=inCoiifryr( -一 碼 in 6O1x' =xr+(x- Xr)CoS -(y- yr)sin y' =yr+(x- Xr)Si n +(y- yr)cos 12(2)平移這個對象，使得他的固定點與原點重合 旋轉(zhuǎn)這個在坐標原點的對象平移這個對象，使得他的固定點回到原始位置A(-1,-1+、2)B(-1,-1+22)C(-1+32*2 ,-1+9/2* 2 )X'cosSinXr(1cos )yrsiny'Sincosyr(1cos )XrSin10015.如圖所示，L(-3,1)和R(2,6)為正方形裁剪窗口兩個對角線角點，線段AB

7、、CD、EF、GH和IJ為被裁剪線段。用Cohen-Sutherland線裁剪算法進行裁剪時要對線段的端點進行編碼。(1)請寫出編碼規(guī)則，并在圖中標出相應區(qū)域的編碼分別指出于點 A、B、C、D、E、F、G、H對應的編碼(3) 根據(jù)線段端點的編碼對圖中所有線段分類，指出哪些線段是可見的？哪些是不可見的？ 哪些是候選的裁剪線段。J(-2,10)t(1)100110001010000100000010010101000110(2)A:0001B:1000C:0000D:1010E:0000F:0000G:0100H:00101:1000J:1000(3)可見的：EF不可見的：GH,IJ 候選的：AB

8、,CD6.分別用 SUtherIand-Hodgman 算法和 Weiler-Atherton算法裁剪圖1所示的多邊形p1p2p3p4p5p6p7p8p9p1,裁剪窗口為如圖所示的矩形窗口。要求：(1) 用實線分別在圖1(a)(b)(c)(d)中繪出用SUtherIand-Hodgman 算法沿裁剪窗口的左、右、 上、下窗口邊裁剪后的中間結(jié)果用WeiIer-AthertOn算法對圖1所示的多邊形進行裁剪，以p1為起點，以圖1箭頭所示的方向為走向，在圖1(e)中用箭頭表示畫出所有走過的邊(包括多邊形邊和窗口邊)及其走向；并在圖1(f)中用實線繪出最后裁剪結(jié)果。圖 1(c)p7p. -P8 1P3

9、p51/心廠-P2P4圖 1(d)圖 1(e)P9 fLXP4P2圖 1(f)7 簡述多邊形掃描填充算法基本原理和大致步驟，并以具體例子說明邊分類表內(nèi)容、掃描 過程中活化邊表的信息變化。（1）原理：在直角坐標系中，假設有一條從左至右的掃描線穿過多邊形，從左至右開始計數(shù)， 與多邊形交點為奇數(shù)時，開始進入多邊形，與多邊形交點為偶數(shù)時，走出多邊形。這樣在這相鄰配對 的奇偶交點間的所有象素都在多邊形內(nèi)。如圖，奇數(shù)交點a, c,都是入多邊形，偶數(shù)交點 b，d都是走出多邊形，相鄰的奇偶交點配對，a，b之間，c，d之間的象素都多邊形內(nèi)，可見一條掃描線上，與多邊形交點個數(shù)需要為偶數(shù)。依據(jù)這樣的思路，掃描線從上

10、到下從左到右依次掃過多邊形即可求得多邊形所占據(jù)的象素。（注意退化情況的處理，也就是掃描線剛好經(jīng)過頂點或者多邊形的邊本身就是水平的情況）步驟：1）輸入多邊形的頂點的坐標2）建立邊表（ET3）初始化Y值4）初始化活性邊表（AEL）,設置為空5）每個掃描線從底部到頂部，做以下步驟直到ET和AEL是空的:建立AEL設置顏色更新AEL：當Y= YMAX時刪除邊X = X + ? X返回AEL例子:S （8）多邊形與掃描線示意圖I1.2.:、11.02.0A圖（刀掃描線疋的活動邊表圖（3）掃描線了的活動邊裘10 > L1.410P5P4P2F3圖(9)各掃描線的新邊表& 由坐標A(0,0,0

11、), B(1,0,0), C(0,1,0), D(0,01)確定的錐體繞直線L旋轉(zhuǎn)45°,其中L的方向為V=J+K ,且通過點C(0,1,0)。寫出錐體旋轉(zhuǎn)后的坐標。329. 設3次參數(shù)多項式函數(shù) P(u)=au+bu+cu+d,求出滿足下列邊界條件的3次Hermite插值曲線(用矩陣表示):P(0) = PkP(1) = Pk+1P'(0) = DP kIP(I) = DP k+110. Cohen-Sutherland直線段裁剪算法和 Liang-Barsky直線段裁剪算法是直線段裁剪的兩種 基本算法，試述兩種算法的基本原理，并分析它們的優(yōu)點和不足。(1) 通過一個矩形的

12、裁剪區(qū)域?qū)⒄麄€屏幕分成9個部分，并為每一個部分賦予相應的區(qū)域碼，然后根據(jù)端點的位置確定這個端點的區(qū)域碼。先判斷能否完全接受或者完全排除一條線段，若以上2個判斷無法直接得出，則逐步裁剪，選取一個位于裁剪區(qū)外的端點，把端點的區(qū)域碼和裁剪邊界的區(qū)域碼進行邏輯與運算，若結(jié)果為真，則端點在該裁剪邊界外部，這時將端點移向線段和該邊界的交點處，如此循環(huán)，直到裁剪結(jié)束。(2) 利用線段的參數(shù)表達形式直接判別落在窗口內(nèi)的部分線段大體上有以下幾步，有些步驟依據(jù)中間的判斷結(jié)果可以省略或跳轉(zhuǎn)第一步：計算出 Pk和qk(k=1,2,3,4)第二步：看Pki的符號進行判斷第三步：計算 u1=max(0,qkpk),u2=

13、mi n(1,qkpk)如果,u2>u1,則線段是可見的第四步：利用Ul和u2計算端點坐標(3) 比較：Cohe n-Sutherla nd :直觀方便，速度較快多次重復計算線段與裁剪窗口邊界的交點，計算量大采用位邏輯乘，在有些高級語言中不便進行全部舍棄的判斷僅適用于那些僅在窗口的線段，不適合跨越三個區(qū)域的線段，就不能一次做出判別Liang-Barsky :所需計算量小，更有效可以擴展成三維裁剪算法 只能應用于矩陣窗口的情形10. 簡述BeZier曲線與B-SPIine曲線的異同點，指出他們的特點和不足。11. DDA算法和BreSenham算法是兩種直線生成的基本算法，試述兩種算法的基

14、本原理， 并分析它們的優(yōu)點和不足。(1) DDA 算法：選定x2-x1和y2 y1中較大者作為步進方向(假設x2-x1較大),取該方向上的增量為一 個象素單位( x=1),禾U用式(2- 1)計算另一個方向的增量( y= xm=m)。通過遞推公式(2 - 2)至(2- 5),把每 次計算出的(xi+1 , yi+1)經(jīng)取整后送到顯示器輸出，則得到掃描轉(zhuǎn)換后的直線。之所以取x2- x1和y2- y1中較大者作為步進方向，是考慮沿著線段分布的象素應均勻， 這在下圖中可看出。另外，算法實現(xiàn)中還應注意直線的生成方向，以決定X及y是取正值還是負值。(2) BreSenham 算法：假定直線斜率k在01之

15、間。此時，只需考慮X方向每次遞增1個單位，決定y方向每次遞增O或1。設：直線當前點為(xi,y)直線當前光柵點為(xi,yi)則：下一個直線的點應為 (xi+1,y+k)下一個直線的光柵點為右光柵點 (xi+1,yi) (y方向遞增量0)或為右上光柵點(xi+1,yi+1) (y方向遞增量1)(3) 優(yōu)缺點：DDA算法：算法簡單，實現(xiàn)容易由于在循環(huán)中涉及實型數(shù)的運算，因此生成直線的速度較慢。 浮點數(shù)運算不易硬件實現(xiàn)BreSenham算法：不必計算直線之斜率，因此不做除法；不用浮點數(shù)，只用整數(shù)； 只做整數(shù)加減法和乘 2運算,而乘2運算可以用硬件移位實現(xiàn). 算法速度很快，并適于用硬件實現(xiàn)12. 簡

16、述直線段裁剪與多邊形裁剪的異同點。多邊形的剪裁比直線剪裁復雜。 如果按照直線剪裁算法對多邊形的邊作剪裁， 剪裁后的 多邊形的邊就會成為一組彼此不連貫的折線， 從而給填色帶來困難。 多邊形剪裁算法的關鍵 在于，通過剪裁， 不僅要保持窗口內(nèi)多邊形的邊界部分， 而且要將窗框的有關部分按一定次 序插入多邊形的保留邊界之間， 從而使剪裁后的多邊形的邊仍然保持封閉狀態(tài)， 以便填色算 法得以正確實現(xiàn)13. 在計算機輔助設計與圖形學中，樣條曲線通常采用 3 次多項式參數(shù)表示，請說明理由。14. 圖形學中消隱算法有兩大類， z 緩沖器 (z-buffer )算法屬于哪一類？請闡述它的基本原理 和特點。(1)屬于

17、圖像空間消隱(2) 基本原理：Z 緩沖器中每個單元的值是對應象素點所反映對象的 z 坐標值。 Z 緩沖器中每個單元的初值 取成Z的極小值，幀緩沖器每個單元的初值可放對應背景顏色的值。圖形消隱的過程就是給幀緩沖器和 Z 緩沖器中相應單元填值的過程。在把顯示對象的每個面上每一點的屬性(顏 色或灰度) 值填入幀緩沖器相應單元前， 要把這點的 Z 坐標值和 Z 緩沖器中相應單元的值進 行比較。只有前者大于后者時才改變幀緩沖器的那一單元的值，同時Z緩沖器中相應單元的值也要改成這點的 Z 坐標值。 如果這點的 Z 坐標值小于 Z 緩沖器中的值， 則說明對應象素已 經(jīng)顯示了對象上一個點的屬性， 該點要比考慮

18、的點更接近觀察點。 對顯示對象的每個面上的 每個點都做了上述處理后，便可得到消除了隱藏面的圖(3) 特點： 優(yōu)點：(1) 算法復雜度 (O(nN) ：對于給定的圖像空間， N 是固定的，所以算法復雜度只會隨著場 景的復雜度線性地增加(2) 無須排序：場景中的物體是按任意順序?qū)懭霂彌_器和Z緩沖器的，無須對物體進行排序，從而節(jié)省了排序的時間( 3 )適合于任何幾何物體：能夠計算與直線交點( 4 )適合于并行實現(xiàn) (硬件加速 )不足：(1) Z 緩沖器需要占用大量的存儲單元：一個大規(guī)模復雜場景中： 深度范圍可能為 106 ，一個像素需要 24bit 來存儲其深度信息。 如果顯示分辨率為 1280×1024 ，那么深度緩沖器需要 4MB 存儲空間(2) 深度的采樣與量