大三05計算機圖形學(xué)-ii

1、Implementation II繪制實現(xiàn)II原著Ed AngelProfessor of Computer Science, Electrical and Computer Engineering, and Media ArtsUniversity of New Mexico編輯 武漢大學(xué)計算機學(xué)院圖形學(xué)課程組ObjectivesIntroduce clipping algorithms for polygons介紹多邊形裁剪Survey hidden-surface algorithms介紹隱藏面消除Outline7.5 Polygon Clipping多邊形裁剪7.6.1 Boundin

2、g Boxes and Volumes包圍盒與包圍體7.11 Hidden Surface Removal隱藏面消除7.5 Polygon Clipping多邊形裁剪Not as simple as line segment clipping并不像線段裁剪那樣簡單Clipping a line segment yields at most one line segment裁剪一條線段最多得到一條線段Clipping a polygon can yield multiple polygons裁剪一個多邊形可以得到多個多邊形However, clipping a convex polygon ca

3、n yield at most one other polygon然而，裁剪凸多邊形最多得到一個多邊形Figure 7.10 Clipping of a concave polygon (a) Before clipping (b) After clipping7.5 Polygon Clipping多邊形裁剪(Tessellation and Convexity劃分與凸性)One strategy is to replace non-convex (concave) polygons with a set of triangular polygons (a tessellation)一種方法

4、就是把非凸(凹)多邊形用一組三角形代替，這個過程稱為劃分(tessellation)Also makes fill easier這同樣也使得填充變得簡單Tessellation code in GLU library在GLU庫中有劃分代碼，但最好的方法就是由用戶自己進行Figure 7.12 Tessellation of a concave polygon 7.5 Polygon Clipping多邊形裁剪(Sutherland-Hodgeman算法) Clipping as a Black BoxCan consider line segment clipping as a process

5、 that takes in two vertices and produces either no vertices or the vertices of a clipped line segment 裁剪器(Clipper)是一個黑盒子可以認為線段的裁剪就是從兩個頂點出發(fā)，得到的結(jié)果為：沒有頂點 或者 裁剪后線段的頂點Figure 7.10 Clipping against top (a) Graphically (b) Black-box viewClipping against each side of window is independent of other sides對窗口一邊

6、進行裁剪時，與其它邊無關(guān)Can use four independent clippers in a pipeline在流水線中要用到四個獨立的裁剪器7.5 Polygon Clipping多邊形裁剪(Pipeline Clipping of Line Segments)線段裁剪的流水線體系Figure 7.16 Pipeline Clipping(a) Clipping problem (b) Pipeline7.5 Polygon Clipping多邊形裁剪(Pipeline Clipping of Polygons)多邊形裁剪的流水線體系Three dimensions: add fro

7、nt and back clippers 三維：增加前與后裁剪器Strategy used in SGI Geometry Engine SGI Geometry Engine中應(yīng)用這種策略Small increase in latency在等待時間方面有很小的增長Figure 7.17 Example of Pipeline clipping 7.6.1 Bounding Boxes and Volumes包圍盒與包圍體Rather than doing clipping on a complex polygon, we can use an axis-aligned bounding bo

8、x or extent不是直接對復(fù)雜多邊形進行裁剪，而是先用一個方向與坐標(biāo)軸平行的長方體或其它形狀包圍多邊形Smallest rectangle aligned with axes that encloses the polygon包圍盒應(yīng)盡可能得小Simple to compute: max and min of x and y容易計算出坐標(biāo)的最大值與最小值7.6.1 Bounding Boxes and Volumes Bounding boxes應(yīng)用包圍盒Can usually determine accept/reject based only on bounding box通過直接基

9、于包圍盒確定多邊形的接受與拒絕reject拒絕accept接受requires detailed clipping需要更仔細的裁剪處理Figure 7.19 Clipping with bounding boxes 7.11 Hidden Surface Removal隱藏面消除(Clipping and Visibility裁剪與可見性)Clipping has much in common with hidden-surface removal裁剪和隱藏面消除有許多共同點In both cases, we are trying to remove objects that are not

10、visible to the camera實際上，對于裁剪與隱藏面消除，都是希望把看不到的對象從視野中去掉Often we can use visibility or occlusion testing early in the process to eliminate as many polygons as possible before going through the entire pipeline通過可以在處理過程中提早應(yīng)用可見性或者遮擋檢測，從而在進入流水線體系之前消去盡可能多的多邊形7.11 Hidden Surface Removal隱藏面消除(流水線中的位置)在頂點經(jīng)過幾何變

11、換后，其所定義的幾何對象經(jīng)過了裝配與裁剪得到的是一組點、線段和多邊形在最終的投影后，其中所有的都有可能出現(xiàn)在顯示設(shè)備上此時需要進行隱藏面消除具有各種不同的出發(fā)點7.11.1 Object-space and Image-space approach(對象空間方法)考慮由k個三維不透明多邊形構(gòu)成的場景每個多邊形認為是單獨的一個對象Object-space approach: use pairwise testing between polygons (objects)對象空間方法：兩兩比較，檢測多邊形相互之間的位置Worst case complexity O(k2) for k polygon

12、s最糟糕的情形：k個多邊形時間復(fù)雜度為O(k2),partially obscuring部分遮擋can draw independently可以獨立繪制Figure 7.29 Two polygons7.11.1 Object-space and Image-space approach(圖象空間方法)Look at each projector (nm for an n*m frame buffer) and find closest of k polygons對每條投影線(對于n*m分辨率的幀緩沖區(qū)，共有nm條投影線)，找到與k個多邊形最近的那個交點，執(zhí)行nmk次運算Complexity復(fù)

13、雜度O(nmk)Ray tracing光線跟蹤中用到 z-buffer z緩沖區(qū)算法與圖象分辨率有關(guān)，有誤差7.11.1 Object-space and Image-space approach對象空間方法( Object-space approach ) 畫家算法與深度排序背面剔除圖像空間算法(Image-space approach)z緩沖區(qū)算法7.11.7 Painters Algorithm and Depth Sort畫家算法與深度排序 以Z buffer算法為代表的圖象空間方法，在立即模式圖形系統(tǒng)和硬件系統(tǒng)中廣泛應(yīng)用但是，保留模式的圖形系統(tǒng)和應(yīng)用程序中，通過對象空間方法，可以減少

14、發(fā)送到硬件系統(tǒng)的多邊形的數(shù)量 畫家算法與深度排序7.11.7 Painters Algorithm and Depth Sort畫家算法與深度排序 Render polygons a back to front order so that polygons behind others are simply painted over假設(shè)場景內(nèi)的多邊形已按離觀察者的距離排序，按從后到前的順序把每個多邊形完全繪制出來B behind A as seen by viewer從觀察者的角度來說，B在A后面Fill B then A先畫B，再畫A7.11.7 Painters Algorithm and

15、Depth Sort 深度排序Requires ordering of polygons first需要首先對多邊形進行排序O (k log k) calculation for ordering排序的復(fù)雜度為O(k log k)Not every polygon is either in front or behind all other polygons并不是所有的多邊形都完全在其它多邊形的前面或后面Order polygons and deal with easy cases first, harder later進行排序時，先處理簡單情形，再處理困難情形Polygons sorted

16、by distance from COP多邊形按到COP的距離進行排序7.11.7 Painters Algorithm and Depth Sort Depth Sort(Easy Cases簡單情形)A lies behind all other polygons多邊形A位于所有其它多邊形后面Can render可以繪制出來Polygons overlap in z but not in either x or y多邊形在z方向有重疊，但在x或y方向沒有重疊Can render independently可以分別繪制出來Figure 7.53 Test for overlap in x a

17、nd y (a) non-overlapping x extents (b) non-overlapping y extends7.11.7 Painters Algorithm and Depth Sort Depth Sort(Hard Cases困難情形-1)Overlap in all directions but can one is fully on one side of the other在所有方向都有重疊(x方向、y方向、 z方向都重疊) ，但其中一個完全在另一個的一側(cè)(不相交)Figure 7.54 Ploygons with overlapping extends7.11

18、.7 Painters Algorithm and Depth Sort Depth Sort(Hard Cases困難情形-1的解決方法，頂點測試)P是否在Q的不可見一側(cè)：若P的所有頂點位于Q所在平面的不可見的一側(cè)，則P,Q關(guān)系正確 Q是否在P的可見一側(cè)：若Q的所有頂點位于P所在平面的可見的一側(cè)，則P,Q關(guān)系正確7.11.7 Painters Algorithm and Depth Sort Depth Sort7.11.7 Painters Algorithm and Depth Sort Depth Sort(Hard Cases困難情形-2)Figure 7.55 cyclic ove

19、rlap循環(huán)重疊解決方法：分割成新的多邊形集合7.11.7 Painters Algorithm and Depth Sort Depth Sort(Hard Cases困難情形-3)Figure 7.56 Penetration貫穿解決方法：求交運算（相當(dāng)于進行多邊形裁剪），得到新的多邊形7.11.4 Back-Face Removal (Culling)背面剔除face is visible iff 面是可見的，如果90 -90equivalently等價于cos 0 or或者v n 0plane of face has form平面具有形式ax + by +cz +d =0but aft

20、er normalization但對于規(guī)范化視線向量n = ( 0 0 1 0)T need only test the sign of只需要檢測符號cIn OpenGL we can simply enable culling在OpenGL中可以激活背面剔除功能but may not work correctly if we have non-convex objects 但是如果有非凸對象，結(jié)果可能不正確7.11.5 z-Buffer Algorithm深度緩存算法Use a buffer called the z or depth buffer to store the depth of

21、 the closest object at each pixel found so far用一個稱為z緩沖區(qū)或者深度緩沖區(qū)的地方存儲每個像素到目前為止找到的最近對象的深度As we render each polygon, compare the depth of each pixel to depth in z buffer當(dāng)繪制每個多邊形時，把它的深度與z緩沖區(qū)中存儲的深度進行比較If less, place shade of pixel in color buffer and update z buffer如果新值小的話，把新的亮度值放到顏色緩沖區(qū)中并且用新深度更新z緩沖區(qū)7.11.5

22、 z-Buffer Algorithm(Efficiency效率的提高)If we work scan line by scan line as we move across a scan line, the depth changes satisfy如果逐條掃描線遍歷，從左向右移動一條掃描線，那么深度的改變滿足ax+by+cz=0 (平面方程的差分形式)沿每條掃描線考察Along scan line y = 0z = - x常量In screen space在屏幕空間上 x = 1 Figure 7.59 Incremental z-buffer algorithm7.11.5 z-Buff

23、er Algorithm(Scan-Line Algorithm掃描線算法)Can combine shading and hsr through scan line algorithm在掃描線算法中把 明暗處理算法與隱藏面消除算法 結(jié)合在一起scan line i: no need for depth information, can only be in no or one polygon掃描線i:不需要深度信息，適合于沒有多邊形或者只有一個多邊形scan line j: need depth information only when in more than one polygon 掃描線j: 只有當(dāng)遇到多個多邊形時，才需要深度信息7.11.5 z-Buffer Algorithm(掃描線算法Implementation實現(xiàn))Need a data structure to store需要相應(yīng)的數(shù)據(jù)結(jié)構(gòu)存儲下述信息Flag for each polygon (inside/outside)每個多邊形的標(biāo)志(內(nèi)部或外部)Incremental structure for scan lines that stores which edges are encountered掃描線的增量結(jié)構(gòu)，存儲遇到的邊的信息Parame