Chapter 9. Visible-Surface Detection Methods 2010-1학기 Chapter 9. Visible-Surface Detection Methods

Classification of Visible-Surface Detection Algorithms object-space methods와 image-space methods가 있음 object-space methods: object와 object의 일부분을 scene definition으로부터 비교하여 어느 surface가 visible한지를 결정 image-space methods: projection plane상의 pixel position으로 visibility를 결정함 sorting (depth comparison을 쉽게 함)과 coherence methods (scene 의 regularity)를 이용하여 알고리즘의 성능 향상 2010-1학기 Chapter 9. Visible-Surface Detection Methods

Chapter 9. Visible-Surface Detection Methods Back-Face Detection object-space method이며 inside-outside tests를 이용 Ax + By + Cz + D < 0 이면 점(x, y, z)은 inside N : 한 polygon surface에 대한 normal vector V : 눈(카메라)으로부터의 viewing direction vector V N > 0 이면 그 polygon은 back face임 object description이 projection coordinates로 변환되고 viewing direction이 viewing zv axis와 평행하면 V = (0, 0, vz)이고, N = (A, B, C)이므로 V N = Vz C가 됨 normal vector N의 z component인 C의 부호에 따라 V N의 부호가 결정됨 viewing direction이 negative zv axis 방향인 right-handed viewing system에서 C <= 0 이면 그 polygon이 back face가 됨 2010-1학기 Chapter 9. Visible-Surface Detection Methods

Vector V in the viewing direction and a back-face normal vector N N = (A, B, C) V 2010-1학기 Chapter 9. Visible-Surface Detection Methods

Chapter 9. Visible-Surface Detection Methods A polygon surface with plane parameter C < 0 in a right-handed viewing coordinate system identified as a back face. Yv N = (A, B, C) Xv V Zv 2010-1학기 Chapter 9. Visible-Surface Detection Methods

Chapter 9. Visible-Surface Detection Methods Depth-Buffer method image-space approach projection plane의 pixel position에서 surface의 depth를 비교 z-buffer method라고도 함 xv yv view plane의 (x, y)로부터 orthographic projection line상에서 surfaces의 거리를 비교함 2개의 buffer가 필요: 하나는 (x, y) position에 대한 각 surface의 depth value를 저장하고 다른 하나는 refresh buffer로서 각 position에 대한 intensity value를 저장함 depth value의 초기치는 0 (minimum depth)이고 refresh buffer의 초기치는 background의 intensity 2010-1학기 Chapter 9. Visible-Surface Detection Methods

Chapter 9. Visible-Surface Detection Methods At view-plane position(x, y), surface S1 is the smallest depth from the view plane and so is visible at that position. Yv S3 S2 S1 Xv (x, y) Zv 2010-1학기 Chapter 9. Visible-Surface Detection Methods

Chapter 9. Visible-Surface Detection Methods Depth buffer algorithm depth buffer와 refresh buffer를 초기화 depth(x, y) = 1.0 /* depth values for visible surfaces */ refresh(x, y) = Ibackgnd /* intensity values */ 각 polygon의 pixel position에 대해 depth value (z)와 depth buffer 에 저장된 값과 비교하여 if z < depth(x, y) 이면 depth(x, y) = z, refresh(x, y) = Isurf(x, y) surface position (x, y)의 depth value는 plane equation 으로 부터 구해짐 -Ax – By - D z = C 2010-1학기 Chapter 9. Visible-Surface Detection Methods

Chapter 9. Visible-Surface Detection Methods z = (-Ax - By - D) / C <= Ax + By + Cz + D = 0 에서 (x, y)의 depth가 z이면 (x+1, y)의 depth z’는 z’ = {-A(x+1) - By - D} / C 혹은 z’ = z - A/C이 되고, scanline y값이 증가할 때는 x’ = x - 1/m이므로 z = (-Ax - By - D) / C에서 y+1에서의 z값은 z’ = {-A(x - 1/m) - B(y-1) - D} / C = z + (A/m + B)/C가 되며 vertical edge에 대해서는 기울기가 infinite와 마찬가지이므로 z’ = z + B/C 가 된다.   2010-1학기 Chapter 9. Visible-Surface Detection Methods

Chapter 9. Visible-Surface Detection Methods Intersection positions on successive scan lines along a left polygon edge y scan line y+1 scan line x x’ 2010-1학기 Chapter 9. Visible-Surface Detection Methods

Chapter 9. Visible-Surface Detection Methods A-Buffer Method depth-buffer method의 확장 개념으로 A-buffer method는 antialiased, area-averaged, accumulation-buffer method를 나타냄 depth-buffer method의 단점: 각 pixel position에 대해 one visible surface만 찾을 수 있다는 것, 즉 불투명한 표면만 처리할 수 있어서 여러 면의 intensity values를 축적시켜서 투명한 면을 표현하지 못한다. A-buffer method depth-buffer를 확장시켜서 buffer 내 각 position이 a linked list of surfaces를 참조할 수 있도록 함 A-buffer내 각 position은 depth field와 intensity field를 가짐 depth field: a positive or negative real number 저장 intensity field: surface-intensity information혹은 pointer value 저장 2010-1학기 Chapter 9. Visible-Surface Detection Methods

Chapter 9. Visible-Surface Detection Methods depth field가 양수이면 a single surface의 depth를 나타내고, intensity field는 surface color의 RGB 값을 저장 depth field가 음수이면 pixel intensity를 위한 multiple-surface contributions를 의미하며 intensity field는 surface data의 linked list의 포인터를 저장, 각 surface를 위한 데이터로는 RGB intensity components Opacity parameter Depth Percent of area coverage Surface identifier Other surface-rendering parameters Pointer to next surface 2010-1학기 Chapter 9. Visible-Surface Detection Methods

Chapter 9. Visible-Surface Detection Methods Scan-line method image-space method polygon 내부를 채우는 scan-line algorithm을 확장 scan line을 진행하면서 scan line과 교차하는 모든 polygon surface가 visible한지를 조사한다. 각 scan line에 대해 겹치는 모든 surface의 depth를 계산하여 view plane에 가장 가까운 면을 찾아 그 면의 intensity value를 refresh buffer에 넣는다. edge table 및 polygon table을 포함해서 면들을 위한 여러 tables 이 준비되어 있다고 가정 edge table은 각 line의 끝 점들, 기울기, polygon table의 포인터 등을 포함하며, polygon table은 각 면의 평면 방정식, 면에 대한 intensity 정보, edge table에 대한 포인터 등을 포함 2010-1학기 Chapter 9. Visible-Surface Detection Methods

Chapter 9. Visible-Surface Detection Methods Scan lines crossing the projection of two surfaces, S1 and S2, in the view plane. Xv Yv S1 S2 A B C D E F G H Scan Line 1 Scan Line 2 Scan Line 3 2010-1학기 Chapter 9. Visible-Surface Detection Methods

Chapter 9. Visible-Surface Detection Methods 주어진 scan line이 통과하는 면들에 대한 검색을 쉽게 하기 위해, edge table에 있는 정보로부터 active list of edges를 준비. 이 active list 는 현재 scan line을 통과하는 edge 들만을 포함하며 x 순으로 정렬되도록 한다. 각 면에 대해 flag를 정의하여 scan line이 통과하는 지점이 면의 inside인가 outside인가를 구분하도록 하고, scan line 들은 왼쪽에서 오른쪽으로 처리된다. 면의 가장 왼편에서 flag가 on 이 되며 가장 오른편에서 flag가 off 된다. 그림에서 scan line 1에 대한 active list에는 AB, BC, EH, FG 를 위한 edge table로부터의 정보를 포함하고 있다. AB, BC 사이에서 이 scan line을 따라 면 S1 에 대한 flag 만이 on 이므로, depth calculation을 할 필요 없이 면 S1에 대한 intensity 정보가 polygon table 로부터 refresh buffer로 들어간다. Xv Yv S1 S2 A B C D E F G H Scan Line 1 Scan Line 2 Scan Line 3 2010-1학기 Chapter 9. Visible-Surface Detection Methods

Chapter 9. Visible-Surface Detection Methods 마찬가지로, EF, FG 사이에서는 S2 의 flag만이 on 이며 scan line 1을 따라 교차되는 면들이 없으므로 다른 면들의 intensity 값은 background intensity로 설정된다. scan line 2, 3에 대해서는 active list가 AD, EH, BC, FG를 포함하며, AD, EH 사이에서 scan line 2를 따라서는 S1 에 대한 flag 만이 on 이다. EH, BC 사이에서는 양 면들의 flag 들이 on 이 된다. 이 구간에서 두 면들의 계수를 이용하여 depth calculation 이 이루어진다. BC를 만나기 전까지는 s1의 depth가 s2의 depth보다 작기 때문에 s1의 intensity가 refresh buffer에 load 된다. 그리고 나서, S1에 대한 flag 는 off가 되고, FG를 만날 때 까지 S2의 intensity가 저장된다. Xv Yv S1 S2 A B C D E F G H Scan Line 1 Scan Line 2 Scan Line 3 2010-1학기 Chapter 9. Visible-Surface Detection Methods

Chapter 9. Visible-Surface Detection Methods depth-sorting method image-space and object-space operation을 이용 surface들을 decreasing depth로 sort surface들을 가장 큰 depth를 갖는 surface부터 시작하여 scan conversion painter’s algorithm이라고도 함 – oil painting시에 background color를 먼저 칠한 뒤에 먼 거리의 물체를 칠한 뒤에 가까운 거리에 있는 물체를 칠하고 마지막으로 가장 앞에 있는 물체를 그리는 것과 비슷함 surfaces를 view plane으로부터의 거리로 sort하여 가장 먼 거리에 있는 surface의 intensity value를 refresh buffer에 넣는다. Decreasing depth순서대로 차례로 surface의 intensity를 frame buffer에 더해나간다. 2010-1학기 Chapter 9. Visible-Surface Detection Methods

Chapter 9. Visible-Surface Detection Methods depth-sorting method surface들을 z value로 sort하여 가장 큰 depth와 리스트 내 다른 surface들과 비교하여 depth overlap이 없으면 scan conversion을 계속한다. Depth overlap이 발견되면 surface들의 순서를 조정하기 위해 추가적인 비교가 필요 i) 두 surfaces의 xy plane에서의 bounding rectangles이 overlap 하지 않는지를 테스트 ii) surface S 가 viewing position에 비교해 overlapping surface에 completely behind인지를 테스트 iii) overlapping surface가 S에 completely front에 있는지 테스트 iv) 두 surfaces의 view plane로의 projection이 overlap 하는지 테스트 2010-1학기 Chapter 9. Visible-Surface Detection Methods

Chapter 9. Visible-Surface Detection Methods xmin xmax xmin’ xmax’ xmin xmax xmin’ xmax’ (Fig. 9-14) Surface S is completely behind the overlapping surface S’. (Fig. 9-15) Overlapping surface S’ is completely in front of surface S. (Fig. 9-13) Two surfaces with depth overlap but no overlap in the x direction. 2010-1학기 Chapter 9. Visible-Surface Detection Methods

Chapter 9. Visible-Surface Detection Methods Test i) i번 테스트는 두 부분으로 나누어져서 첫 번째는 x 방향으로 overlap을 첵크하고 다음에 y 방향으로 첵크한다. 양 방향중 어느 하나에서 overlap이 없으면 두 면들이 서로를 가리지는 않는다. Test ii)와 iii)은 inside-outside polygon test로 수행한다. S 의 모든 vertices의 좌표치를 교차하는 면의 평면 방정식에 대입하여 sign을 조사한다. 면의 outside가 viewing position으로 향해있도록 plane equations가 설정되어 있을 경우, S의 모든 점들이 S’의 inside이면 S가 S’의 behind에 있으며 S 의 모든 점들이 S’의 outside 이면 S’는 S 의 completely front 에 있게 된다. Test iv)는 xy plane에서 line equations를 이용하여 intersection을 첵크한다. 2010-1학기 Chapter 9. Visible-Surface Detection Methods

BSP-Tree Method (Binary Space Partitioning Tree) painter’s algorithm에서와 같이 surfaces를 back부터 front까지 칠해나가는 방법으로 object visibility를 결정 view reference point는 변하나 scene내 물체는 고정 위치에 있는 경우에 유용. viewing direction에 대한 각 space subdivision단계에서 surfaces가 space 를 분할하는 평면에 대해 inside인지 outside인지를 판별하는 과정이 필요 (그림9-19)에서 먼저 plane P1으로 공간을 분할하여 viewing direction에 따라 물체들이 back 혹은 front로 나눈다. 한 물체가 평면과 교차되는 경우엔 그 물체를 두개 별도 물체로 분리한다. A, C는 P1의 front에 있고, B, D는 P1의 back에 있음 2010-1학기 Chapter 9. Visible-Surface Detection Methods

Chapter 9. Visible-Surface Detection Methods A region of space (a) is partitioned with two planes P1 and P2 to form the BSP tree representation in (b) P2 C P1 P1 front back D P2 P2 A front back front back back A C B D front B back front (a) (b) 2010-1학기 Chapter 9. Visible-Surface Detection Methods

Chapter 9. Visible-Surface Detection Methods 다시 plane P2로 공간을 분할하여 binary tree 를 구성하여 모든 물체들이 terminal nodes로 표시되도록한다. Front objects는 왼쪽 노드에 back objects는 오른쪽 노드로 한다. BSP Tree가 완성되면 surfaces를 back에서 front의 순서로 칠해나간다. 즉 background objects를 칠한 뒤에 foreground objects를 칠함 2010-1학기 Chapter 9. Visible-Surface Detection Methods

Area-Subdivision Method image-space method이나 surface의 depth ordering을 위해 object-space operation을 이용 scene의 area coherence 성질을 이용 total viewing area를 점점 작은 사각형으로 분할해나가서 각 작은 사각형 하나가 a single visible surface가 투영되었거나 혹은 투영된 surface가 없는 경우가 되도록 한다 지정된 area에 대한 a single surface의 visibility 결정은 surface와 area boundary를 비교하는 테스트로 이루어진다. surface와 area boundary와 관계 surrounding surface overlapping surface inside surface outside surface 2010-1학기 Chapter 9. Visible-Surface Detection Methods

Dividing a square area into equal-sized quadrants at each step 2010-1학기 Chapter 9. Visible-Surface Detection Methods

Possible relationships between polygon surfaces and a rectangular area Surrounding surface Overlapping surface Inside surface Ouside surface 2010-1학기 Chapter 9. Visible-Surface Detection Methods

Chapter 9. Visible-Surface Detection Methods area에 대한 surface visibility 테스트: 다음의 조건 중 하나가 true이면 subdisivion을 더 이상 하지않는다. area에 대한 모든 surfaces가 outside 에 있는 경우 only one inside, overlapping, or surrounding surface 만 area에 있는 경우 a surrounding surface가 area boundary내에서 다른 모든 surfaces를 가리는 경우 2010-1학기 Chapter 9. Visible-Surface Detection Methods

Chapter 9. Visible-Surface Detection Methods Octree Methods viewing volume에 octree를 이용하는 경우에는 octree node를 front-to-back order로 viewing surface에 투영시켜서 hidden-surface elimination을 실행함 back octants (4, 5, 6, 7)은 front octants에 의해 가려지므로 back surfaces는 제거함 마찬가지로 octant 0의 4개 front suboctants를 처리해간다. 계속하여 각 octant에 위의 처리를 계속해간다. an octree node가 a color value로 나타나면 이 노드에 해당하는 frame buffer내 pixel area에 그 color value를 지정한다. octree를 display하는 방법은 octree nodes를 front에서 back으로 recursive하게 조사해서 보이는 영역의 octree를 quadtree로 매핑시킨 후, quadtree 표현을 frame buffer에 load 2010-1학기 Chapter 9. Visible-Surface Detection Methods

Chapter 9. Visible-Surface Detection Methods Objects in octants 0, 1, 2, and 3 obscure objects in the back octants (4, 5, 6, 7) 6 5 4 1 3 7 2 Numbered octants of a region Viewing direction 2010-1학기 Chapter 9. Visible-Surface Detection Methods

Chapter 9. Visible-Surface Detection Methods Ray-Casting Method view plane의 a pixel position에서 물체를 통과하는 광선과 surface의 교차점 중 가장 가까이에 있는 교차점으로 surface의 visibility를 정하는 방법 ray casting procedure 이용 광선의 경로를 추적하는 geometric optic method curved surfaces로 표현된 scene의 visibility detection에 효과적이다. ray casting은 multiple ray paths를 추적하여 multiple objects로부터 반사와 굴절을 취하는 ray tracing algorithm의 특별한 경우이다. ray casting에서는 각 픽셀로부터 가장 가까운 물체로의 하나의 광선을 따른다. 2010-1학기 Chapter 9. Visible-Surface Detection Methods

Chapter 9. Visible-Surface Detection Methods Curved Surfaces 곡면으로 구성된 물체의 visibility 를 결정하는 효과적 방법으로 ray-casting 과 octree 방법이 있음 ray-casting: ray-surface intersection을 계산해야 하고 pixel ray를 따라 가장 작은 교차 거리를 정한다. Octree: 물체에 대한 입력이 정의되면 모든 visible surface들은 같은 방법으로 구해질 수 있음 curved surface를 plane polygon 들로 정의하는 경우엔 각 curved surface를 polygon mesh로 바꾸고 앞에서의 hidden-surface methods를 사용 Curved surface representations Implicit equation인 f(x, y, z) = 0 혹은 parametric representation 사용 때로는 explicit equation 사용이 편리한 경우가 있다. Xy ground plane에 대한 높이 함수로 다음의 식 사용 z = f(x, y) 2010-1학기 Chapter 9. Visible-Surface Detection Methods

Chapter 9. Visible-Surface Detection Methods Surface Contour plots 응용에 따라 한 surface function을 곡면의 모양을 보여주는 contour lines의 집합으로 나타내기도 함. 곡면이 하나의 식, 혹은 고도에 대한 지형 데이터나 인구밀도와 같은 데이터 테이블로 나타냄 Visible surface contour lines 로 나타내고 가려지는 contour sections 을 제거해간다. xy plane상의 곡선은 주어진 z 구간에서 z 값들에 대해 만들어진다. Surface를 xy 도면으로 나타내면 surface representation은 y = f(x, z) 로 표현 xy plane 상의 곡선은 z 의 정해진 범위(z)에서 그려진다. 가장 큰 z 값에서 시작하여 곡선을 front에서 back으로 curve를 그려나가고 hidden sections을 제거한다. 2010-1학기 Chapter 9. Visible-Surface Detection Methods

Chapter 9. Visible-Surface Detection Methods Surface에서 visible curve sections을 구분하는 방법은 pixel x 에 대해 ymin, ymax 값을 유지시켜서 얻는다. 한 pixel x 위치에서 시작해서 계산된 y 값을, 다음 픽셀의 ymin, ymax와 비교하여 ymin <= y <= ymax 이면 그 점은 not visible 하므로 그리지 않는다. 그 범위를 벗어난 점은 visible 하므로 그려주고 y 값의 범위를 갱신한다. Xz plane과 yz plane에 대해서도 비슷한 방법으로 contour plot을 얻는다. 2010-1학기 Chapter 9. Visible-Surface Detection Methods

Chapter 9. Visible-Surface Detection Methods Wireframe methods 물체의 outline만 디스플레이 할 때는 visibility test가 surface edges에 적용되어, visible edge sections은 디스플레이되고 hidden edge sections은 제거되거나 visible edges와는 다르게 디스플레이되도록 한다. object edges의 visibility 를 결정하는 프로시듀어를 wireframe visibility 라고 함. Visible line detection methods 혹은 hidden-line detection methods라고도 함. visible line을 구분하기 위한 직접적인 방법은 각 line을 각 surface와 비교하는 것 이 방법은 arbitrary window shapes에 대한 line clipping 와 유사. 일부 line은 surface에 가려짐 2010-1학기 Chapter 9. Visible-Surface Detection Methods

Chapter 9. Visible-Surface Detection Methods 각 line에 대해 어느 line section이 보이지 않는가를 결정하기 위해 surface와 depth values를 비교: 각 coordinate position을 테스트하지 않고 hidden line segments를 결정하기 위해 coherence methods 사용 가능 surface boundary의 projection과의 양쪽 line intersection이 surface보다 depth가 큰 경우는 line segment가 completely hidden (그림9-28a). line이 한 boundary intersection에서는 depth가 크고, 다른 boundary intersection에서는 depth가 작은 경우에는 line이 surface 내부를 관통함(그림9-28b). 2010-1학기 Chapter 9. Visible-Surface Detection Methods

Chapter 9. Visible-Surface Detection Methods Hidden-line sections (dashed) for a line that (a) passes behind a surface and (b) penetrates a surface (b) (a) 2010-1학기 Chapter 9. Visible-Surface Detection Methods

Wireframe Depth-Cueing Algorithm Visibility information 을 디스플레이하는 또 다른 방법 물체의 밝기를 viewing position 으로부터의 거리의 함수로 나타냄 d: viewing position 으로부터의 거리 dmin, dmax: minimum and maximum depth 혹은 normalized depth range (dmin = 0.0, dmax = 1.0) 각 픽셀의 위치가 처리될 때 픽셀 컬러에 fdepth (d)가 곱해진다. 가까운 점에 보다 큰 강도(intensity)가 주어지고, 최대 깊이에는 강도가 0 값을 갖는다. dmax - d fdepth (d) = dmax - dmin 2010-1학기 Chapter 9. Visible-Surface Detection Methods

Chapter 9. Visible-Surface Detection Methods 2010-1학기 Chapter 9. Visible-Surface Detection Methods