From Vertices to Fragments Geometric Pipeline 기하파이프라인 (geometric pipeline) 정점처리 (vertex processing) 클리핑과기본요소로조립 (clipping and primitive assembl 래스터화 (rasterization) 단편처리 (fragment processing) 응용프로그램 9 8년봄학기 6/9/8 박경신 ( 정점 ) 그래픽스시스템 ( 픽셀 ) 프레임버퍼 Four Major Tasks 모델링 (modeling) 기하학적객체들의집합생성 기하학적처리 (geometric processing) 변환 (transformation) 음영 (shading) 기본요소조립 (primitive assembl, 클리핑 (clipping) 은면처리 (hidden surface removal) 래스터화 (rasterization) 주사변환 (scan conversion) 알고리즘 단편처리 (fragment processing) 앤티앨리어싱 (anti-aliasing) Geometric Processing Object model Eye coordinates ( 눈좌표계 ) Clip coordinates ( 클리핑좌표계 ) Vertex ( y, z) ( 객체좌표계 ) ModelView Transformation Projection Transformation Projective Division Normalized device coordinates ( 정규화된장치좌표계 ) Viewport Transformation ( 모델관측변환 ) ( 투영변환 ) ( 투영정규화 ) ( 뷰포트변환 ) Screen window coordinate (x s, y s ) ( 스크린윈도우좌표계 ) Rasterization
Clipping 차원클리핑윈도우 (clipping window) 차원클리핑경계입체 (clipping volume) 곡선과텍스트는먼저선과다각형으로바꿔줄것 Clipping 선분클리핑알고리즘 Cohen-Sutherland 클리핑알고리즘 선분의끝점에외곽부호 (outcode) 를사용 많은수의선분이있지만실제로몇개만디스플레이되는경우에가장잘작동함 알고리즘이간단하며, 차원클리핑알고리즘으로확장이쉬움 Liang-Barsky 클리핑알고리즘 직선의매개변수형식을사용 Cohen-Sutherland 방식과비교하여선분줄임 ( 즉, 교차점의계산 ) 의여러번반복을줄여줌 차원클리핑알고리즘으로확장이쉬움 다각형클리핑알고리즘 Sutherland-Hodgeman 클리핑알고리즘 다각형의정점을클리핑윈도우의각경계면에대해차례로처리함 D Line-Segment Clipping Cohen-Sutherland Algorithm 선분클리핑 (clipping D line segments) 절단기 (clipper) 는어떤기본요소또는그일부가화면에나타나야되고래스터화기로보내져야하는지를결정 수용 (accepted): 지정한관측공간에들어온기본요소는수용 거부 (rejected) 또는선별 (culled): 화면에나타날수없는기본요소는제거됨 Cohen-Sutherland 클리핑알고리즘. 클리핑윈도우의 4개의변무한대로확장하고, 공간을 9개의영역으로분할 y = y max x = x min x = x max. 각영역에고유의외곽부호 (outcode), b b b b 를다음과같이할당 if y > ymax if y < ymin b b b otherwise otherwise y = y min. 외곽부호에기초하여 4 가지경우를판단 if x > xmax otherwise if x < xmin b otherwise
Cohen-Sutherland Algorithm 선분 AB 의경우 : A s outcode = B s outcode = 선분의양끝점이클리핑윈도우내부에있는경우, accepted 선분 CD 의경우 : C s outcode AND D s outcode 선분의양끝점이클리핑윈도우의같은변의외부에있는경우, rejected A s outcode = B s outcode = x = x min A y = y max B y = y min x = x max C D C s outcode = D s outcode = C AND D = Cohen-Sutherland Algorithm 선분 EF 의경우 : E s outcode, F s outcode = 선분의한끝점은클리핑윈도우내부에있고, 다른하나는외부에있는경우, subdivide 개교차점 (intersection) 을찾아야함 선분 GH, 선분 IJ 의경우 : G s outcode AND H s outcode = 선분의양끝점이모두외부에있는경우, subdivide. 선분 GH경우선분의일부가클리핑윈도우내부에있음 적어도윈도우한변과교차계산하고그결과점의외곽부호를점검할것 J E s outcode = F s outcode = I G x = x min H y = y max E y = y min F x = x max G s outcode = H s outcode = G AND H = I s outcode = J s outcode = I AND J = Liang-Barsky Algorithm Polygon Clipping Liang-Barsky 클리핑알고리즘. 매개변수형직선공식 P( = ( P + αp, α x( = ( x + αx y( = ( y + αy. 선분이클리핑윈도우의확장된변과교차하는 4 점을계산 y x max min = ( α ) y = ( α ) x ymax y α = y y xmin x α = x x + α y + α x 4 > > α > α > α > α > α > α > α > α 4 > 선분절단선분전부가거부됨 오목한다각형 (concave polygon) 의클리핑 방법: 클리핑후하나의다각형으로묶는방법 방법: 오목한다각형의집합으로나누고 (tessellate), 클리핑 하나의다각형생성클리핑후클리핑전분할 (Tessellation)
Pipeline Clipping of Line Segments Sutherland-Hodgeman 알고리즘 절단기를각각윈도우의한변에대해서클리핑하는더간단한절단기의파이프라인으로세분함 = x + ( ymax x y = y max x x y y x = x min y = y max x = x max Pipeline Clipping of Polygons Sutherland-Hodgeman 알고리즘 Input: 다각형 ( 정점리스트 ) 과클리핑면 Output: 새로운클리핑이된다각형 ( 정점리스트 ) 차원다각형에대한연속적인절단기 (pipeline clipping of polygons) 차원의경우, 전변 (front) 과후변 (back) 클리핑을추가함 y = y min Bounding Boxes 다각형의축정렬경계상자 (axis-aligned bounding box) 또는범위 (extent) 를클리핑에사용 많은변을가진복잡한다각형의경우 경계상자는다각형을포함하는윈도우에정렬된가장작은사각형 경계상자는다각형정점 x 와 y 값의최소값 (min) 과최대값 (max) 를계산하여얻어짐 Bounding boxes 경계상자를사용하여간단한클리핑수행 Accept 윈도우안에있으므로내부에있는것으로수용 Reject 윈도우밖에있으므로클리핑이필요없음 Requires detailed clipping 다각형의모든변을사용하여상세한클리핑을수행
Cohen-Sutherland Algorithm in D Liang-Barsky Algorithm in D 차원에서는평면에서의경계영역이아닌경계공간 (bounding volume) 에대하여클리핑 Cohen-Sutherland 클리핑알고리즘 클리핑공간에대한 4 비트외곽부호를 6 비트외곽부호로대체하고 차원의경우와같이계산함 if z > zmax b4 otherwise if z < zmin b5 otherwise Liang-Barsky 클리핑알고리즘 선분의 차원매개변수표현 P( = ( P + αp, α x( = ( x + αx y( = ( y + αy z( = ( z + αz 평면 (P, n) 의공식으로부터 α 유도 P( = ( P + αp n ( P( P ) = α = n ( P n ( P P ) P ) Rasterization 래스터화 (rasterization) 또는스캔변환 (scan conversion) 프레임버퍼에서단편의형성에이르는과정의마지막단계 물체를표현하기위해어떤화소를밝힐것인지를결정하는작업 정규화가시부피 (normalized device coordinates) 에서뷰포트 (viewport) 로의사상 정점좌표를화면좌표로변환한결과를기준으로 선분을화면좌표로변환 내부면을화면좌표로변환 아래그림에서 A, B, C 으로둘러싸인곳에서어떤화소를칠해야삼각형 ABC 를가장잘표현할수있는가? Rasterization 실수 (float) 좌표를정수 (int) 좌표로변환 때로는반올림이필요 예를들어, 정점의뷰포트좌표가 (.95,.4) 화소 (, ) 로변환됨 화소경계선내부 (.5 <= x <.5) 이고 (.5 <= y <.5) 인모든정점은 (, ) 로사상됨 A B A, B 는모두같은선분으로사상됨
Line Scan-Conversion 래스터변환알고리즘이적용되는가장기본적인객체가선분 (line segment) 임 일단선분양끝정점이화면의어떤화소로사상되는지를결정한후에나머지화소부분을처리 기울기를기준으로샘플링 보다크면 y 좌표를증가 보다작으면 x 좌표를증가 기울기가음수라면절대값이용 Line Scan-Conversion 교차점계산에의한변환은부동소수곱셈으로인해속도저하 void LineDraw(int int y, int int { ( float y, m; int d dy; dx = x - x; dy = y - y; ( m = dy / dx; for (x = x; x <= x; x++) { y = m*(x - x) + y; DrawPixel( round(); Δx 두점 ( ( 을지나는직선방정식 y y y = ( x x) + y x x Δy DDA (Digital Differential Analyzer) 부동소수곱셈을부동소수덧셈으로변환 void LineDraw(int int y, int int { ( float m, y; int d dy; dx = x - x; dy = y - y; m = dy / dx; ( y = y; for (int x = x; x <= x; x++) { y y Δy y += m; y = mx + h where m = = x x Δx DrawPixel( round(); Δy = mδx Δy = m (x가 씩증가할때) DDA (Digital Differential Analyzer) DDA 알고리즘에의한연산 x ( 반올림결과 x = (,.) (, ) x = (,.) (, ) x = (,.66) (, ) x = (,.99) (, ) x = 4 (4,.) (4, ) x = 5 (5,.65) (5, ) x = 6 (6,.98) (6, )
DDA (Digital Differential Analyzer) DDA 단점 부동소수연산 부동소수덧셈이정수연산에비해느림 반올림연산 round( ) 함수실행에걸리는시간 연산결과의정확도 부동소수의경우뒷자리가잘려나감 연속적인덧셈에의한오류누적 선택된화소가실제선분에서점차멀어져서표류 (Drift) 중점알고리즘 (Midpoint Algorithm) 라고도불림 모든부동소수점계산을피하고정수계산만이용 현재래스터기의표준알고리즘이된직선래스터화알고리즘 ( (x+,y+) (x+,y+½) ( ( (x+, A ( 선택 다음화소는 B (x+,, C (x+, y+) 중하나 화소중심과선분간의수직거리에의해판단 선분이중점 M 의아래에있으면화소 B, 위에있으면화소 C 를선택 화소 A=( 이라하면화소 B, C 의중점 M 의좌표는 (x +, y + ½) 이되는데, 이를 F 에대입해보면 dy y = mx + h, m = dx dy y = x + h dx ydx = xdy + hdx = xdy ydx + hdx F( = xdy ydx + hdx F( = F x +, y + = ( x + ) dy y + dx + hdx = xdy ydx + hdx + dy dx = F( + dy dx F( = xdy ydx + hdx = F( = dy dx 결정변수 (decision variable) F( 에의해중점이선분의위인지아래인지를판단 만약 F( < 이라면, 중점이선분위에있고따라서동쪽화소를선택 만약 F( > 이라면, 동북쪽화소를선택 F( = dy dx if ( F( < ) else select NE select E // 동쪽화소선택 // 동북쪽화소선택 d d d>d => F( <
현재고려되고있는화소의좌표를 ( 라고하고만약동쪽화소가선택되었다면다음단계의중점위치는 (x +,, 동북쪽화소가선택되었다면다음단계의중점위치는 (x +, y + ) 이된다 다음단계의결정변수와현단계의결정변수의차이는다음과같이계산 incre = F( x +, F( = = dy ( ( x + ) dy ydx + hdx) ( xdy ydx + hdx) incrne = F( x +, y + ) F( = ( ( x + ) dy ( y + ) dx + hdx) ( xdy ydx + hdx) = dy dx void MidpointLineDraw(int int y, int int m { int d dy, incre, incrne, D, y=y; dx = x - x; dy = y - y; D = *dy - dx; // 결정변수값을초기화 incre = *dy; // 동쪽화소선택시증가분 incrne = *dy - *dx; // 동북쪽화소선택시증가분 for (x=x; x <= x; x++) { if (D <= ) { // 결정변수가음수. 동쪽화소선택 D += incre; // 결정변수증가 else { // 결정변수가양수. 동북쪽화소선택 D += incrne; // 결정변수증가 y++; // 다음화소는동북쪽 DrawPixel ( ; // 화소그리기 m >. x 와 y 를바꿔서계산함 y 방향으로증가시키면서, x 값을결정함 그외에, 특수한경우는따로처리함 Δy = (horizontal line) Δx = (vertical line) Δx = Δy (diagonal lines) x<x - m x<x m y<y - < m < - y y<y < m < x<x m x x<x - m 예를들어 (, ) 과 (6, 4) 를연결하는선분 (, ) D > (,) D < (, ) (6, 4) y<y < m < y<y - < m < -
정수연산에의한속도증가 + 하드웨어로구현 첫 8분면에서만정의 다른선분은이동, 반사하여적용 Polygon Scan-Conversion 다각형의래스터화 = 다각형채우기 (polygon filling) 점이다각형의내부에있다면그것을내부색으로칠함 다각형내부의판단규칙 홀짝규칙 (even-odd rule) 주사선별로경계가홀수 (odd) 번째교차하면내부, 짝수 (even) 번째교차하면외부가시작된다고판단 접기횟수규칙 (non-zero winding rule) 주사선별로아래쪽경계와교차하면접기횟수를 증가, 위쪽방향의경계와교차하면 감소 이때접기횟수가 보다큰구간은다각형의내부영역으로판단 원생성알고리즘 선분생성알고리즘과유사 Flood Fill 범람채우기 (flood fill) 내부로정의된영역채우기 다각형내부의시작점 (seed point) 에서시작하여, 순환적으로이웃을살펴보고, 만약이들이변의점이아니라면채우기색으로칠함 void flood_fill(int int { // 다각형내부초기점 ( 에서시작 if(read_pixel(= = WHITE) { // 현재픽셀이배경색 (white) 이면 write_pixel(y,black); // 채우기색 (black) 으로칠함 flood_fill(x+, ; // 오른쪽으로반복 flood_fill(x-, ; // 왼쪽으로반복 flood_fill( y+); // 아래로반복 flood_fill( y-); // 위로반복 Scan Line Fill 주사선채우기 (scan line fill) Y-X 다각형주사선알고리즘 : 4 5 6 7 8 9 전체 edge 를 Y 값순서로정렬하여 Edge List (EL) 를구성 매주사선이새로교차하는에지를 EL 에서꺼내어 Active Edge List (AEL) 로이동 해당주사선과각 edge 와교차점을 개씩짝을지어사이를채움 e e e Edge List e e e Active Edge List y= y= y=.. y=6.. y=9 e e e e
Aliasing 계단 (Stair-step, Jaggies) 모양의거친경계선 비트맵표현에서는화소단위로근사화할수밖에없기때문 무한해상도를지닌물체를유한해상도를지닌화소면적단위로근사화할때필연적으로일어나는현상 Anti-Aliasing 수퍼샘플링 (Super-Sampling) 부분화소에서샘플링. 사후필터링 부분화소의평균값을반영 지터 (jitter) 에의한수퍼샘플링 물체자체가불규칙이라면불규칙샘플링이유리 Anti-Aliasing Aliasing Anti-aliased Magnified