05計(jì)算機(jī)圖形學(xué)雙語(yǔ)課程i

1、Implementation I原著Ed AngelProfessor of Computer Science, Electrical and Computer Engineering, and Media ArtsUniversity of New Mexico編輯 武漢大學(xué)計(jì)算機(jī)學(xué)院圖形學(xué)課程組ObjectivesIntroduce basic implementation strategies介紹繪制實(shí)現(xiàn)的基本策略和框架Clipping裁剪問(wèn)題Outline7.1 Basic implementation strategies基本繪制框架7.2 Four required tasks四個(gè)

2、主要任務(wù)7.3 Clipping 裁剪7.4 Line-segment 線段裁剪7.7 Clipping in three dimensions三維裁剪7.1 Basic implementation strategies繪制框架(Overview)At end of the geometric pipeline, vertices have been assembled into primitives幾何階段之后，頂點(diǎn)裝配成圖元Must clip out primitives that are outside the view frustum必須對(duì)視見(jiàn)體之外的圖元進(jìn)行裁剪Algorithms

3、 based on representing primitives by lists of vertices算法是基于頂點(diǎn)表示的圖元Must find which pixels can be affected by each primitive找到每個(gè)圖元所對(duì)應(yīng)的像素Fragment generation產(chǎn)生片元Rasterization or scan conversion進(jìn)行光柵化和掃描轉(zhuǎn)換7.1 Basic implementation strategies繪制框架(圖形處理過(guò)程)計(jì)算機(jī)圖形系統(tǒng)可看作一個(gè)黑盒子輸入：程序中定義的頂點(diǎn)和狀態(tài)量-幾何對(duì)象、屬性和照相機(jī)設(shè)置輸出：幀緩沖區(qū)里的彩

4、色像素陣列內(nèi)部：變換、裁剪、明暗處理、隱藏面消除和光柵化對(duì)每個(gè)幾何對(duì)象進(jìn)行處理給顏色緩沖區(qū)的每個(gè)像素賦顏色值7.1 Basic implementation strategies繪制框架(Rasterization Meta Algorithms基本算法)Consider two approaches to rendering a scene with opaque objects考慮繪制由不透明對(duì)象構(gòu)成的場(chǎng)景的兩種方法For every pixel, determine which object that projects on the pixel is closest to the vie

5、wer and compute the shade of this pixel對(duì)于每個(gè)像素，確定投影到這個(gè)像素的離觀察者最近的那個(gè)對(duì)象，從而基于該對(duì)象計(jì)算像素的明暗值Ray tracing paradigm光線跟蹤框架for (each_pixel) assign_a_color(pixel)7.1 Basic implementation strategies繪制框架(Rasterization Meta Algorithms基本算法)For every object, determine which pixels it covers and shade these pixels對(duì)于每個(gè)對(duì)象

6、，確定它所覆蓋的像素，并用對(duì)象的狀態(tài)確定像素的明暗值Pipeline approach流水線方法Must keep track of depths必須跟蹤深度值for (each_object) render(object)7.1 Basic implementation strategies繪制框架(算法類型)這兩種方法分別稱為面向圖像(image-oriented)的方法面向?qū)ο?object-oriented)的方法也分別稱為先排序(sort-first)后排序(sort-last)方法基于隱藏面消除發(fā)生的地方進(jìn)行命名的7.1 Basic implementation strategie

7、s繪制框架(面向?qū)ο蠓椒?A polygon might flow through the steps7.1 Basic implementation strategies繪制框架(面向?qū)ο蠓椒▋?yōu)缺點(diǎn))優(yōu)點(diǎn)：處理速度快，運(yùn)行成本低缺點(diǎn)：過(guò)去需要占用大量?jī)?nèi)存，每個(gè)對(duì)象單獨(dú)處理的代價(jià)較大。由于低價(jià)大容量?jī)?nèi)存，以及專用硬件芯片的出現(xiàn)，已不再是問(wèn)題不能得到大多數(shù)全局效果，例如涉及多個(gè)對(duì)象的復(fù)雜光照隱藏面消除例外，Z buffer全局深度信息7.1 Basic implementation strategies繪制框架(面向圖像方法優(yōu)缺點(diǎn))優(yōu)點(diǎn)：任何時(shí)刻只需有限的顯示內(nèi)存，且可以按顯示器的刷新速度和次序

8、生成像素利用相鄰像素間的連貫性可設(shè)計(jì)增量式算法適合處理全局效果缺點(diǎn)：需要復(fù)雜的幾何對(duì)象的數(shù)據(jù)結(jié)構(gòu)必須確定哪些圖元影響哪些像素繪制過(guò)程中需要隨時(shí)訪問(wèn)所有的幾何數(shù)據(jù)7.2 Four required Tasks四個(gè)主要任務(wù)Modeling建模Transformations幾何處理投影、圖元裝配、裁剪、明暗處理Rasterization or scan conversion光柵化Some tasks deferred until fragments processing片元處理Hidden surface removal隱藏面消除Anti-aliasing反走樣紋理映射、融合7.2 Required

9、 Tasks主要任務(wù)(建模)建模器可以認(rèn)為是一個(gè)黑盒子輸出幾何對(duì)象的頂點(diǎn)數(shù)據(jù)集工作在對(duì)象坐標(biāo)系Chapter 6 球體近似建模，網(wǎng)格模型Chapter 10 層次建模Chapter 11 過(guò)程建模7.2 Required Tasks主要任務(wù)(幾何處理)幾何處理的對(duì)象是頂點(diǎn)，目標(biāo)是確定顯示在屏幕上的幾何對(duì)象，并確定這些對(duì)象頂點(diǎn)的明暗值或顏色值投影圖元裝配裁剪明暗處理7.2 Required Tasks主要任務(wù)(投影)第一步：利用模型-視圖變換把幾何對(duì)象從對(duì)象坐標(biāo)系變換到照相機(jī)坐標(biāo)系或視點(diǎn)坐標(biāo)系第二步：利用投影變換把頂點(diǎn)變換到規(guī)范化視景體頂點(diǎn)表示為裁剪坐標(biāo)7.2 Required Tasks主要任

10、務(wù)(圖元裝配)變換是對(duì)頂點(diǎn)進(jìn)行的，在進(jìn)行后續(xù)操作需要組裝成幾何對(duì)象，稱為圖元裝配裁剪是針對(duì)圖元進(jìn)行的光柵器不能對(duì)頂點(diǎn)單獨(dú)進(jìn)行處理7.2 Required Tasks主要任務(wù)(裁剪)裁剪器確定哪些圖元或圖元的哪些部分會(huì)被傳送到光柵器，最終可能會(huì)顯示在屏幕上只有在視景體內(nèi)的對(duì)象經(jīng)過(guò)光柵化后能被顯示在屏幕上部分在視景體內(nèi)的圖元，裁剪后生成新的圖元沒(méi)被裁剪掉的頂點(diǎn)仍表示為四維齊次坐標(biāo)，通過(guò)透視除法轉(zhuǎn)換為三維的規(guī)范化設(shè)備坐標(biāo)7.2 Required Tasks主要任務(wù)(明暗處理)為每個(gè)頂點(diǎn)賦顏色，兩種方法第一種方法，由當(dāng)前繪制顏色決定，程序直接指定第二種方法，開(kāi)啟光照時(shí)，根據(jù)改進(jìn)的Phong模型計(jì)算得到

11、7.2 Required Tasks主要任務(wù)(光柵化)光柵化或掃描轉(zhuǎn)換：從裁剪后的對(duì)象生成片元（準(zhǔn)像素）對(duì)于線段，確定哪些像素可用來(lái)近似表示頂點(diǎn)間的線段對(duì)于多邊形，確定哪些像素位于多邊形頂點(diǎn)定義的二維區(qū)域的內(nèi)部片元的顏色取決于 系統(tǒng)顏色狀態(tài)值 或 由光照模型計(jì)算的頂點(diǎn)明暗值插值得到輸入：由規(guī)范化設(shè)備坐標(biāo)表示的頂點(diǎn)輸出：由三維窗口坐標(biāo)表示的片元7.2 Required Tasks主要任務(wù)(片元處理)最簡(jiǎn)單的情形下，片元的顏色由光柵器賦值，并且該值就是片元所對(duì)應(yīng)的幀緩沖區(qū)中像素的顏色值紋理貼圖 像素流水線隱藏面消除：確定可見(jiàn)對(duì)象的片元值可見(jiàn)對(duì)象指位于視景體內(nèi)，且沒(méi)有被其他更靠近照相機(jī)的不透明對(duì)象所

12、遮擋的對(duì)象融合：半透明效果，反走樣7.3 Clipping裁剪2D against clipping window二維相對(duì)于裁剪窗3D against clipping volume三維相對(duì)于裁剪體Easy for line segments polygons,hard for curves and text對(duì)線段和多邊形很容易進(jìn)行，對(duì)于曲線和文本很難進(jìn)行Convert to lines and polygons first首先轉(zhuǎn)化為線段和多邊形7.4 Clipping 2D Line Segments二維線段的裁剪Brute force approach: compute intersect

13、ions with all sides of clipping window直觀方法: 計(jì)算線段與裁剪窗口邊界的交點(diǎn)Inefficient: one division per intersection低效：每次求交運(yùn)算需要一次除法7.4.1 Cohen-Sutherland Algorithm Cohen-Sutherland算法Idea: eliminate as many cases as possible without computing intersections想法：盡可能避免求交運(yùn)算就消除許多情形Start with four lines that determine the s

14、ides of the clipping window從確定裁剪窗口邊界的四條直線開(kāi)始x = xmaxx = xminy = ymaxy = ymin7.4.1 Cohen-Sutherland算法(The Cases各種情形-1)Case 1: both endpoints of line segment inside all four lines線段的兩個(gè)端點(diǎn)都在裁剪窗口內(nèi)Draw (accept) line segment as is原樣繪制直線，即接受Case 2: both endpoints outside all lines and on same side of a line兩

15、個(gè)端點(diǎn)都在窗口外，且在同一條直線的外側(cè)Discard (reject) the line segment 丟棄這條直線，即拒絕x = xmaxx = xminy = ymaxy = ymin7.4.1 Cohen-Sutherland算法(The Cases各種情形-2)Case 3: One endpoint inside, one outside一個(gè)端點(diǎn)在內(nèi)部，一個(gè)端點(diǎn)在外部Must do at least one intersection必須進(jìn)行至少一次求交Case 4: Both outside都在外部May have part inside仍可能部分在內(nèi)部Must do at lea

16、st one intersection必須進(jìn)行至少一次求交x = xmaxx = xminy = ymax7.4.1 Cohen-Sutherland算法(Defining Outcodes定義編碼)For each endpoint, define an outcode對(duì)于每個(gè)端點(diǎn)，定義一個(gè)編碼b0b1b2b3Outcodes divide space into 9 regions編碼把空間分成九個(gè)區(qū)域Computation of outcode requires at most 4 subtractions計(jì)算編碼最多需要四次減法b0 = 1 if y ymax, 0 otherwiseb

17、1 = 1 if y xmax, 0 otherwiseb3 = 1 if x a3 a2 a1Intersect right, top, left, bottom: shorten交點(diǎn)依次在右、頂、左、底：縮短In (b)情形(b): a4 a2 a3 a1 Intersect right, left, top, bottom: reject交點(diǎn)依次在右、左、頂、底：拋棄7.4.2 梁-Barsky Clipping(效率的考慮)交點(diǎn)的表示= (ymax y1)/(y2y1)需要浮點(diǎn)除法盡可能地避免交點(diǎn)計(jì)算交點(diǎn)方程的重寫：a (y2y1) = ay = (ymax y1) = ymax所需要

18、的測(cè)試可以對(duì)ymax和y以及其它類似項(xiàng)進(jìn)行全部在窗口外，直接拋棄的線段只有當(dāng)需要對(duì)直線進(jìn)行縮短時(shí)才計(jì)算交點(diǎn)部分在窗口內(nèi)，需要對(duì)長(zhǎng)度裁減7.4.2 梁-Barsky Clipping(Advantages優(yōu)勢(shì))Can accept/reject as easily as with Cohen-Sutherland 與Cohen-Sutherland 算法一樣很簡(jiǎn)單地接受或拒絕Using values of a, we do not have to use algorithm recursively as with C-S 應(yīng)用a值使得不必要像Cohen-Sutherland算法那樣重復(fù)應(yīng)用代碼E

19、xtends to 3D 也可以推廣到三維的情形 相比之下，一些高效的二維算法不能擴(kuò)展到三維情形7.7 Clipping in three dimensions三維裁剪把二維裁剪擴(kuò)展到三維，采用長(zhǎng)方形體作為裁剪體(clip against a bounded volume)Clipping algorithms in two-dimension can be extended to three-dimension二維裁剪算法都能擴(kuò)展到三維情況7.7 Clipping in three dimensions ( Cohen Sutherland in 3D) 三維空間中的Cohen-Sutherland算法Use 6-bit outcodes利用6位進(jìn)行編碼，27個(gè)區(qū)域When needed, clip line segment against planes 必要時(shí)，相對(duì)于平面裁剪線段7.7 Clipping in three dimensionsClipping and Normalizat