Implementation of a Renderer
Implementation graphics system을구현하는방법? 핵심은 algorithm 현재는대부분 hardware 구현가능 그러나, 아직도 software 구현필요 algorithms theoretical versus practical performance hardware versus software implementations specific characteristics of an application 1
7.1 Four Major Tasks
Major Implementation Tasks input : geometric entity (polygon) output : 화면상의 display 전체과정에서필요한 step들 modeling geometric processing rasterization display 3
Major Implementation Tasks Modeling ( 보통, user program) a set of vertices that specifies a set of geometric objects Geometric Processing normalization clipping hidden-surface removal shading Rasterization (= scan conversion) generate a set of pixel values for graphics primitives Display display quality : jaggedness aliasing 4
Basic Implementation Strategies object-oriented approach for each object render(object) image-oriented approach for each pixel assign_a_color(pixel) OpenGL approach ray-tracing approach 5
7.2 Implementation of Transformations
Coordinate Systems object / world coordinate system eye / camera / view coordinate system clip coordinate system canonical view volume에서 clipping NDC / normalized device coordinate system viewport mapping 으로화면출력 window / screen coordinate system 7
Viewport Transformation NDC screen 으로의 mapping window size 가변해도같은화면이나오도록 x y v v = x = y v min v min NDC screen coordinate + ( x x + ( y y max ) max ) x v max x y max v max y max x x v min min y y v min min 8
7.3 Line Segment Clipping
Cohen-Sutherland Clipping I. E. Sutherland, Sketchpad, A Man-Machine Graphical Communication System, (1963). 2D line segment clipping window 를벗어난부분을없애는 algorithm 3D 로쉽게확장가능 clip 전 clip 후 10
Cohen-Sutherland Line Clipping 기본아이디어 #1 : 4 bit code line 의끝점들을 code 화 아예벗어난것들은미리처리가능 1001 1000 1010 0000, 0000 : window 내부 0001 0000 0010 0101 0100 0110 0100 & 0010 = 0000 : 경계에걸릴수도있다 left right below above 1001 & 0101 = 0001 : left 11
Cohen-Sutherland Line Clipping line segment with endpoints (x 1, y 1 ), (x 2, y 2 ) Let o 1 = outcode(x 1, y 1 ) o 2 = outcode(x 2, y 2 ) o 1 = o 2 = 0 : display both endpoints are inside the clipping window o 1 0, o 2 = 0; or vice versa intersection 계산필요 o 1 AND o 2 0 : ignore both endpoints lie on the same outside side of the window. o 1 AND o 2 = 0 intersection 계산필요 12
Cohen-Sutherland Line Clipping 기본아이디어 #2 경계에걸릴수있는것들은경계를기준으로분할 다시벗어난것들을제거 P 3 Window P 2 P 2 ( x, y 1 1) x = xw min ( x, y) y = y m x y y x = x1 + m y2 y1 m = x x 1 + ( 1) 2 1 1 x P 3 P 1 ( x, y 2 2) P 1 P 4 13
Cohen-Sutherland Line Clipping 분할후의예제 Window P 2 P 2 Window P P 2 P 2 P 3 P 3 P 3 P 4 P 1 P 1 P 3 P 4 P 1 P 1 각각을 code 화해서다시검사 14
Liang-Barsky Clipping Y. Liang and B. Barsky, A new concept and method for line clipping, ACM Trans. on Graphics, 3(1):1 22, (1984). use the parametric form for lines p 1 = (x 1, y 1 ), p 2 = (x 2, y 2 ) p(α) = (1 α) p 1 + α p 2 (0 α 1) or, equivalently, x(α) = (1 α) x 1 + α x 2 y(α) = (1 α) y 1 + α y 2 window 의각경계에서, parameter 값 α 1, α 2, α 3, α 4 계산 15
Liang-Barsky Clipping Sort the parameters and determine the topological relationships 1 > α 4 > α 3 > α 2 > α 1 > 0 : clipped line segment [α 2, α 3 ] 1 > α 4 > α 2 > α 3 > α 1 > 0 : outside line segment 16
7.4 Polygon Clipping
Polygon clipping line clipping 의단순확장은아님 Before Clipping After Clipping Before Clipping After Clipping line clipping polygon clipping 18
Sutherland-Hodgeman polygon clipping I. E. Sutherland and G. W. Hodgeman, Reentrant Polygon Clipping, Comm. ACM, 17:32 42, (1974). 기본아이디어 : 문제를쉽게분할 window 의각변에서한번씩 clipping 총 4 번 line 에대한 polygon clipping 수행 Original Polygon Clip Left Clip Right Clip Bottom Clip Top 19
Sutherland-Hodgeman polygon clipping line 에대한 polygon clipping 은? 경계를따라가면서 line clipping, 내부만남긴다 S D S I D D D I S S Save D (a) Save I (b) No Points Saved (c) Save I, D (d) 20
Sutherland-Hodgeman polygon clipping 경우에따라서는 2 개이상의 polygon 이나올수도 convex polygon 만처리하면반드시 1 개의 polygon 만생긴다. concave polygon : 분할해서 convex polygon 으로 21
7.5 Clipping of Other Primitives
Bounding Box the smallest rectangle, aligned with the window, that contains the polygon clipping 이불필요한경우를미리제거 23
Clipping of Other Primitives curves, surfaces complicated to process them directly approximate with line segments and planar polygons texts bitmap characters : pixel 단위로 clipping stroke(outline) characters : polygon으로취급 clipping in the frame buffer geometric clipping 이효과적 raster objects 는어쩔수없이 frame buffer 에서 clip 24
7.6 Clipping in Three Dimensions
2D and 3D clipping 2D clipping window : clipping rectangle 3D clipping view volume : clipping volume 26
3D clipping algorithms 대부분, 2D clipping algorithm을확장 Cohen-Sutherland line clipping algorithm use 6-bit outcode in parallelepiped view volume 그이후는사실상동일 27
3D clipping algorithms Liang-Barsky line clipping algorithm add the parametric equation for z-axis z(α) = (1 α) z 1 + α z 2 find 6 α values Sutherland-Hodgeman polygon clipping algorithm add extra two clippers for the z-axis components 28
3D clipping algorithms view volume normalization 대부분의 clipping algorithm 들은 view volume 이 normalize 되어야작동 reduce the computation in clipping clipping 이까다로움 normalize 후에 clipping 가능 29
7.7 Hidden-Surface Removal
Hidden Surface Removal viewer 가볼수없는 face 를제거하는 algorithm 물체를화면에표시할때, 어느쪽? 해결책? hidden-surface elimination algorithm 물체의숨은면을제거 = visible-surface detection algorithm 31
Hidden Surface Removal object-space approaches 3D 에서 face 간의순서를부여 painter s algorithm image-space approaches pixel 마다보이는물체를찾음 z-buffer algorithm 32
Back-face Removal front face : camera 쪽으로향한 face 90 θ 90 화면에나와야한다 Nfront V < 0 back face : camera 반대쪽을향한 face θ < 90, θ > 90 화면에나오면안된다 Nback V > 0 θ V : view vector N front N back 33
Back-face Removal view coordinate system 에서는 back-face 를화면에표시할필요가없다 다른면에의해서가려지므로 back face front face y v x v z v 34
Z-buffer Algorithm E. Catmull, A hidden-surface algorithm with antialiasing, Computer Graphics, 12(3):6 11, (1975). 기본아이디어 화면상의 pixel 하나를그릴때마다 z 좌표도함께기억 y v x v z 1 z v 35
Z-buffer Algorithm 초기 : 모든 pixel 의 z- 좌표는 pixel 을그릴필요가있으면, if (z pixel < z object ) then pixel update, z pixel = z object else ignore z background = zobject1 = 100 zobject3 = 80 zobject2 = 50 z pixel = zpixel = 100 zpixel = 50 zpixel = 50 36
Z-buffer Algorithm coherence 의이용 pixel 단위처리일때, 매번다시계산하지않음 two points on a polygon (x 1, y 1, z 1 ), (x 2, y 2, z 2 ) a x + b y + c z + d = 0 plane equation x = x 2 x 1, y = y 2 y 1, z = z 2 z 1 a x + b y + c z = 0 바로옆 pixel 로이동시, x = 1, y = 0 z = (c/a) x 37
Z-buffer Algorithm image space algorithm 모든물체는일단화면까지 projection 된다 simple & efficient 대부분의 video card 가채택 OpenGL에서도사용 단점 : 메모리가많이필요 pixel 하나마다 (R, G, B, Z) 로저장 Z 좌표를저장하기위한메모리필요 38
Painter s Algorithm 모든물체를카메라에서먼것부터정렬 view coordinate system 에서정렬 멀리있는것부터그린다. 가려진부분은자동적으로지워진다 y C sorting -z C A B x (C,B,A) painting A B x z 39
Painter s Algorithm = list priority algorithm = depth sorting algorithm 유화그림그리는것과동일한순서 배경부터그린후에, 가까운것을그리면, 가려진부분은자동으로사라진다. object space algorithm 물체를화면에가져오기전에미리처리 40
Depth sorting Algorithm 문제점 순서대로정렬할수없는경우도있다 해결책 : 물체를 2 개이상으로분리 B B A C A (C, A, B) 순서 41
Scan-line Algorithm rasterize the polygon scan line by scan line determine the visible polygon by incremental depth calculation used by Macintosh 3D video cards 42
7.8 Scan Conversion
Scan Conversion geometric object 를실제화면에출력하는과정 최종출력단계는 pixel 하나단위 write_pixel(int ix, int iy, int value) 좌표 (ix, iy) 에색상 value 를갖는 pixel 출력 line segment 의 scan conversion DDA algorithm Brensenham s algorithm 44
Line Segment line segment (x 1, y 1 ) (x 2, y 2 ) 사이를연결하는선분 raster system : 두끝점사이의 pixel들을 on 문제점! frame buffer는 array 형태 두끝점을잇다가소수점이나오면? round-off 시킴 ( 반올림 ) 원하는선분 raster system 45
Intuitive Method line equation y = m x + b line(x a, y a, x b, y b ) 라면, y m = = x y x b b y x a a b = for x i = x a to x b y i = ROUND(m x i + b) setpixel(x i, y i ) y m a x a y b (x a, y a ) m (x b, y b ) x 문제점은? 더효과적인방법은? 46
Intuitive Method m 1 m 1 하나의 x 에여러개의 y 값이필요 끊어진 line! 해결책 x, y 역할을바꾼다 출력은잘나옴 한 pixel을찍기위해, y i = ROUND(m x i + b) 너무복잡한연산필요! 47
DDA Algorithm digital differential analyzer 1 m 1, x a < x b 인경우 y k = m x k + b x k+1 = x k + 1 y k+1 = m x k+1 + b y k+1 y k = m (x k+1 x k ) y k+1 = y k + m algorithm int x i = x a float y i = y a setpixel(x i, ROUND(y i ) ) for x i = x a +1 to x b y i = y i + m setpixel(x i, ROUND(y i ) ) ROUND(...) 는반올림연산 48
DDA Algorithm m > 1, x a < x b 인경우 y i = m x i + b b xi = 1 yi m m y k+1 = y k + 1 x k+1 = (1 / m) y k+1 (b / m) x k = (1 / m) y k (b / m) x k+1 x k = (1 / m) (y k+1 y k ) x k+1 = x k + (1 / m) algorithm float minverse = 1 / m float x i = x a int y i = y a setpixel(round(x i ), y i ) for y i = y a +1 to y b x i = x i + minverse setpixel(round(x i ), y i ) 49
DDA Algorithm 장점 조금빠르다 ( 곱하기가불필요 ) 단점 m 값이정확하지않을수있다 실수 (float) 의정밀도문제 ( 예 : 1/3) 길이가길면, 끝점이빗나간다 round-off 연산은비싸다 실수 (float) 연산도비싸다 50
7.9 Bresenham s Algorithm
Bresenham s Line Algorithm J. E. Bresenham, Algorithm for computer control for a digital plotter, IBM Sys. J., January:25 30, (1965). symmetry ( 대칭성 ) 를이용해서, x a < x b, 0 m < 1 인경우만따짐 x, y 역할을바꿈 시작점, 끝점을바꿈 기준! x 축대칭 x 축대칭, x, y 역할을바꿈 52
Bresenham s Line Algorithm (x k, y k ) 를출력한후에는, (x k+1, y k ) 또는 (x k+1, y k +1) 을출력해야 integer( 정수 ) 연산만으로선택할수있다! 53
Bresenham s Line Algorithm x k + 1 y k +1 d 2 = (y k + 1) y = y k + 1 m (x k + 1) b d 1 = y y k = m (x k + 1) + b y k d 1 d 2 이면, d 1 d 2 0 y k+1 = y k + 1 d 1 < d 2 이면, d 1 d 2 < 0 y k+1 = y k y = m (x k + 1) + b y k 54
Bresenham s Line Algorithm d 1 = y y k = m (x k + 1) + b y k d 2 = (y k + 1) y = y k + 1 m (x k + 1) b d 1 d 2 = 2 m (x k + 1) 2 y k + 2 b 1 = 2 m x k 2 y k + (2 m + 2 b 1) m = y / x 이므로, p k = x (d 1 d 2 ) = 2 y x k 2 x y k + c c = x (2 m + 2 b 1) = 2 y + x (2 b 1) p k 0 이면, x (d 1 d 2 ) 0 y k+1 = y k + 1 p k < 0 이면, x (d 1 d 2 ) < 0 y k+1 = y k 55
Bresenham s Line Algorithm p k+1 = 2 y x k+1 2 x y k +1 + c p k = 2 y x k 2 x y k + c p k+1 p k = 2 y (x k+1 x k ) 2 x (y k +1 y k ) x k+1 x k = 1 이므로, p k+1 = p k + 2 y 2 x (y k +1 y k) y k+1 은 y k (p k < 0) 또는 y k + 1 (p k 0) p k < 0 : p k+1 = p k + 2 y p k 0 : 초기값 p 0 는? p 0 = 2 y x 0 2 x y 0 + c p k+1 = p k + 2 y 2 x c = x (2 m + 2 b 1) = 2 y + x (2 b 1) 정리하면, p 0 = 2 y x 56
Bresenham s Line Algorithm Rough Algorithm x 0 = x a, y 0 = y a x = x b x a, y = y b y a setpixel(x 0, y 0 ) p 0 = 2 y x 0 for (k = 0; k < x ; k++) x k+1 = x k + 1 if p k < 0, y k+1 = y k p k+1 = p k + 2 y if p k 0, y k+1 = y k + 1 p k+1 = p k + 2 y 2 x setpixel(x k, y k ) 57
Bresenham s Line Algorithm Algorithm ( 불필요한첨자를없애면 ) x = x a, y = y a x = x b x a, y = y b y a setpixel(x, y) p = 2 y x for (k = 0; k < x ; k++) { x = x + 1 if (p < 0) p = p + 2 y else { y = y + 1, p = p + 2 ( y x ) } setpixel(x, y) } 58
Bresenham s Line Algorithm 완전한알고리즘은? x a < x b, 0 m < 1 인경우만설명했음 나머지경우모두에대한알고리즘필요 Bresenham s Line Algorithm 은 single processor 에서는가장빠르다 고급 video card 에서는 H/W chip 으로구현 더빠른방법은? parallel algorithm multi-processor 사용 59
7.10 Scan Conversion of Polygons
Jordan Theorem polygon vs. line polygon 외부에서출발한직선은 polygon 과반드시짝수번교차 61
Scan-line Polygon Filling Algorithm 기본아이디어 polygon vs. scan-line 교차점을계산 교차점사이의 pixel 을출력 polygon 시작끝시작끝 scan-line 62
Scan-line Polygon Filling Algorithm degenerate cases 특별한처리가필요한경우 변들이같은쪽 시작, 끝, 시작, 끝 시작, 끝, 시작, 끝 변들이서로다른쪽 63
Coherence 의이용 전체 polygon fill 시에는 coherence 로빠르게처리가능 coherence : 응집성 현재 scan-line 을처리한후에는, 다음 scan-line 은조금만변한다. scan-line y k + 1 scan-line y k Bresenham s line algorithm! 64
Inside-outside Test polygon의내부 / 외부구별 왜? 내부를구별해야 fill 가능 Jordan theorem! 해석방법 odd-even rule = odd parity rule, even-odd rule nonzero winding number rule 65
Inside-outside test odd-even rule 홀수번교차 : 내부 짝수번교차 : 외부 non-zero winding rule 위에서아래로 : +1 아래에서위로 : 1 합이 0일때만외부 1 1 +1 +1 66
Boundary-Fill Algorithm 정해진도형의내부를정해진색깔로채우기 내부점 : an interior point (x, y) 경계색 :a boundary color 채움색 :a fill color boundary color fill color interior point (x, y) 67
Boundary-Fill Algorithm 기본아이디어 interior point 부터인접한 pixel 들을 fill color 로바꾼다. boundary color 를만날때까지 인접한 pixel? 4-connected 8-connected 68
4-connected vs. 8-connected 4-connected 8-connected start point 69
Boundary-Fill Algorithm rough algorithm for 4-connected case void boundaryfill4(int x, int y, Color fill, Color boundary) { Color current = getpixel(x, y); if (current boundary && current fill) { setpixel(x, y, fill); boundaryfill4(x+1, y, fill, boundary); // recursion! boundaryfill4(x 1, y, fill, boundary); boundaryfill4(x, y+1, fill, boundary); boundaryfill4(x, y 1, fill, boundary); } 70
Flood-Fill Algorithm boundary fill 의변형 start point 와같은색인 pixel 들을바꾼다 start point 71
7.11 Anti-aliasing
Anti-aliasing aliasing information loss due to low-frequency sampling jagged or stair-step appearance anti-aliasing aliasing 제거방법 aliasing anti-aliasing 73
Anti-aliasing 기법들 area 계산법 pixel 에걸리는면적을직접계산 pixel 값= blue 70% + red 30% filter 법 면적을다시가중치로적분 면적 : 30% pixel 값 = Gaussian( x, y) Value( x, y) dx dy super-sampling 한 pixel 의여러군데를 sample 10 6 pixel 값 = blue + red 16 16 74
7.12 Display Considerations
Half-toning and Dithering Half-toning ( 신문의사진들 ) technique to simulate gray levels by creating patterns of black dots of varying size Dithering (= digital half-toning) use digital halftone to simulate halftoning with fixed sized pixels 76
요약 77