9 장. 래스터변환 학습목표 래스터변환이필요한이유를이해한다. 지- 버퍼알고리즘에의한은면제거가래스터변환과병행되어야하는이유를이해한다. 선분의래스터변환에있어서브레스넘알고리즘의장점을이해한다. 주사선채움알고리즘및활성화선분리스트의사용법을이해한다. 경계채움알고리즘과홍수채움알고리즘의차이점을이해한다. 선형보간방법을이해한다. 비트맵과포스트스크립트의개념상차이점및저장방식의차이점을이해한다. 에일리어싱이발생하는이유와앤티-에일리어싱기법에대해이해한다. 1 래스터변환 (Rasterization) 래스터변환또는스캔변환 (Scan Conversion) Raster = 화소 물체를표현하기위해어떤화소를밝힐것인지를결정하는작업 정규화가시부피에서뷰포트로의사상 정점좌표를화면좌표로변환한결과를기준으로 선분을화면좌표로변환 내부면을화면좌표로변환 2 1
지엘의래스터변환 은면제거와동시에진행 깊이와색을보간 정점의 z 값으로부터선분및내부면의깊이를보간 정점의색으로부터선분및내부면의색을보간 화면에보이는모든것은래스터변환결과 최대의연산속도, 최대의정확성이요구됨 3 기울기를기준으로샘플링 1 보다크면 y 좌표를증가 1 보다작으면 x 좌표를증가 선분의래스터변환 4 2
교차점계산에의한변환 void LineDraw(int x1, int y1, int x2, int y2){ float y, m; int dx, dy; dx = x2 - x1; dy = y2 - y1; m = dy / dx; for (x = x1; x <= x2; x++) { y = m*(x - x1) + y1; DrawPixel(x, round(y)); } } : 부동소수곱셈으로인한속도저하 5 DDA(Digital Differential Analyzer) void LineDraw(int x1, int y1, int x2, int y2) { float m, y; int dx, dy; dx = x2 - x1; dy = y2 - y1; m = dy / dx; y = y1; for (int x = x1; x <= x2; x++) { DrawPixel(x, round(y)); y += m; } } 6 3
DDA 문제점 부동소수연산 부동소수덧셈. 따라서부동소수곱셈보다는빠름 그러나정수연산에비해느림 반올림연산 round( ) 함수실행에걸리는시간 연산결과의정확도 부동소수의경우뒷자리가잘려나감 연속적인덧셈에의한오류누적 선택된화소가실제선분에서점차멀어져서표류 (Drift) 7 브래스넘알고리즘 브레스넘알고리즘 (Bresenham Algorithm) 또는중점알고리즘 ( 中點, Midpoint Algorithm) A 선택 다음화소는 B, C 중하나 화소중심과선분간의수직거리에의해판단 선분이중점 M의아래에있으면화소 B, 위에있으면화소 C를선택 8 4
브래스넘알고리즘 A= (x 1, y 1 ) 이면화소 B, C 경계선의중점 M= (x 1 +1, y 1 +1/2) 결정변수 F(x, y) 에의해중점이선분의위인지아래인지를판단 9 다음결정변수와현결정변수의차이 브래스넘알고리즘 void MidpointLine(int x1, int y1, int x2, int y2){ int dx, dy, incre, incrne, D, x, y; dx = x2 - x1; dy = y2 - y1; D = 2*dy - dx; 결정변수값을초기화 incre = 2*dy; 동쪽화소선택시증가분 incrne = 2*dy - 2*dx; 동북쪽화소선택시증가분 x = x1; y = y1; 첫화소 DrawPixel(x, y) 첫화소그리기 while (x < x2) { if (D <= 0) { 결정변수가음수. 동쪽화소선택 D += incre; 결정변수증가 x++; 다음화소는동쪽 } else{ 결정변수가양수. 동북쪽화소선택 D += incrne; 결정변수증가 x++; y++; 다음화소는동북쪽 } DrawPixel (x, y); 화소그리기 } } 10 5
브래스넘알고리즘 정수연산에의한속도증가 + 하드웨어로구현첫팔분면에서만정의 다른선분은이동, 반사하여적용 원생성알고리즘 선분생성알고리즘과유사 11 화소좌표 화소의좌하단을기준으로부여하는것 ((b) 방식 ) 이일반적 선분길이조정을위해마지막화소는제외시킴 면적조정을위해외곽화소는제외시킴 12 6
그래픽수식표현 현시적표현 (Explicit Representation) y = 2x + 4 묵시적표현 (Implicit Representation) f(x,y) y)=y y - 2x - 4=0( ( 직선 ) f(x,y) = -y + 2x + 4 = 0 ( 직선 ) f(x,y) = 2y - 4x - 8 = 0 ( 직선 ) f(x,y) = x 2 + y 2-1 = 0 ( 원 ) 파라미터표현 (Parametric Representation) (t, 2t+4) 또는 (t 2 + 1, 2(t 2 + 1) + 4) 등 단일하지않음 원의경우 : x 2 + y 2-1 = 0 => (cosθ, sinθ) 13 상하및내외판단 먼저정의된정점 : (x 1, y 1 ), 나중에정의된정점 : (x 2, y 2 ) (5, 0) 를대입하면결과는 f(x, y) = 4 5 + 8 0 = 20 > 0 으로서양수, 따라서선분의위쪽선분의식이 x = 2 와같은경우, 상하판단이어려움 14 7
삼각형의래스터변환 주어진화소가삼각형의내부인지를판단 다각형의모든정점을항상반시계방향으로정의 먼저정의된정점을 (x 1, y 1 ) 으로, 나중정의된정점을 (x 2, y 2 ) 로 선분은반시계방향으로진행할때진행방향의 왼쪽에대해서는 f(x, y) > 0 오른쪽에대해서는 f(x, y) < 0 15 주사선채움알고리즘 (Scan Line Fill Algorithm) 홀수규칙 (Odd Parity Rule, Even-Odd Rule) 홀수번째교차화소부터짝수번째교차화소직전까지채움 짝수번째를포함하지않는이유 : 길이보존 14번 : 1 x < 2, 3 x < 4 8번 : 1 x < 2 4번 : 1 x < 2, 3 x < 4 16 8
특수경우처리 길이보존 극대점 : 교차하지않은것으로간주 (H, F, C) 극소점 : 각각교차한것으로간주 : 2 번 (G, A) 극대극소 : 1번교차 (B): 2개의선분으로분할주사선과평행 선분이없는것으로간주 (DE) CD, FE에의해서처리됨 17 공간적응집성 (Spatial Coherence) 내부채움 인접화소끼리는같은색이칠해질확률이높다. 선분 주사선 0번이선분 AC와만났다면바로위주사선 1번도선분 AC와만날확률이높다. 18 9
선분리스트 ( 선분테이블 ) 선분위쪽끝점의 y 좌표 (Yend), 아래쪽시작점의 x 좌표 (Xstart), 선분기울기의역수 (1/m) 주사선 1 번 : (7, 1), 2 번 : (7+(-5/2), 2) = (9/2, 2), 3 번 : (9/2+(-5/2), 3) = (4/2, 3) Yend 와일치할때까지계속 19 활성화선분리스트 (Active Edge List) 주사선 2번으로증가할경우교차점의 x 선분 AB: 7+(-5/2) = 9/2, 선분 BC: 7+(6/4) = 34/4 오름차순으로정렬 => (9/2, 34/4). 그사이의화소가칠해짐주사선 3번으로증가할경우현재의주사선번호가 Yend(=3) 에도달 AB 는비활성화되어리스트에서제거 선분 FA가활성화되어활성화선분리스트에삽입 20 10
내외부판정 (Inside Outside Test) 진행방향의왼쪽이내부 볼록다각형에서만성립 오목다각형의경우다각형분할 (Tessellation) 에의해볼록다각형의집합으로변형 진행방향의오른쪽에다각형의임의정점이존재하면오목다각형 홀수규칙 (Odd Parity Rule, Even-Odd Rule) 볼록, 오목에무관하게내외부판정 내부점으로부터외부를향한직선은다각형과반드시홀수번교차 21 내외부판정 (Inside Outside Test) 넌제로와인딩규칙 (Non-Zero Winding Rule): 선분의방향을고려 감싸기수 (Winding Number) 선분이반시계방향으로그점을몇번이나감싸는가? 0으로초기화 선분의오른쪽에서왼쪽으로건너가면 +1 왼쪽에서오른쪽으로건너가면 -1 최종감싸기수가 0이아니면내부점으로간주 22 11
씨앗채움알고리즘 (Seed Fill Algorithm) 어떤화소가다각형내부임이확인된후 이를씨앗으로해당화소의색을인근으로번져나가게함 경계채움알고리즘, 홍수채움알고리즘 경계채움알고리즘 (Boundary Fill Algorithm) 경계화소색을만날때까지 4방또는8방으로번짐 4방향경계채움, 8방향경계채움 23 경계채움알고리즘 (Boundary Fill Algorithm) 경계채움알고리즘코드 void BoundaryFill4(int x, int y, color FillColor, color BoundaryColor){ color CurrentColor = ReadPixel(x, y); if(currentcolor!= BoundaryColor && CurrentColor!= FillColor){ SetPixel(x, e y, FillColor); o BoundaryFill4(x+1, y, FillColor, BoundaryColor); 동쪽화소 BoundaryFill4(x-1, y, FillColor, BoundaryColor); 서쪽화소 BoundaryFill4(x, y-1, FillColor, BoundaryColor); 남쪽화소 BoundaryFill4(x, y+1, FillColor, BoundaryColor); 북쪽화소 } } 24 12
경계채움알고리즘 ( 계속 ) 다각형의연결 4 방연결 (4-Connectedness), 8 방연결 (8-Connectedness) 4 방연결시에 8 방향경계채움을적용하면오류 8 방연결시에 4 방향경계채움을적용하면완전히채워지지않음 25 홍수채움알고리즘 (Flood Fill Algorithm) 경계화소색이상이해도됨 (cf. 경계채움 : 경계화소의색이동일한것으로가정 ) 다각형내부색이완전히동일한것으로가정예 ( 아래 ): 백색을만나는동안에는계속 4 방또는 8 방으로진행 4-방향홍수채움알고리즘코드 void FloodFill4(int x, int y, color FillColor, color OldColor){ if(readpixel(x, y) == OldColor){ FloodFill4(x+1, y, FillColor, OldColor); FloodFill4(x-1, y, FillColor, OldColor); FloodFill4(x, y-1, FillColor, OldColor); FloodFill4(x, y+1, FillColor, OldColor); } } 26 13
무게중심좌표 (Barycentric Coordinates) 선분의무게중심좌표 (α, β) 27 무게중심좌표 (Barycentric Coordinates) 삼각형의무게중심좌표 (α, β, ) α 의의미 28 14
컨벡스헐 (Convex Hull) 컨벡스헐 주어진점을모두포함하는가장작은볼록다각형컨벡스헐특성 (Convex Hull Property) 위식으로표현된정점 V는항상컨벡스헐내부에존재 29 무게중심좌표계산 2차원투상 30 15
무게중심좌표에의한보간 경계상자 (BB: Bounding Box) 다각형을둘러싼최소크기 4 각형 보간 경계부피내의모든화소에대해무게중심좌표를계산 해당화소가삼각형내부인지판단 색과깊이를보간 31 양방향선형보간 (Bilinear Interpolation) Y 방향보간에의해 S, T 를구함 X 방향보간에의해 V 를구함무게중심좌표와일치연산속도는더빠름 32 16
지엘의그래픽기본요소 (Primitives) 기본요소정의 : glbegin(type of the Primitive); glvertex3f(v1x, V1y, V1z); glvertex3f(v2x, V2y, V2z); glvertex3f(v3x, V3y, V3z); glvertex3f(v4x, V4y, V4z); glvertex3f(v5x, V5y, V5z); glvertex3f(v6x, V6y, V6z); glvertex3f(v7x, V7y, V7z); glvertex3f(v8x, V8y, V8z); glend( ); GL_POINTS, GL_LINES, GL_LINE_STRIP, GL_LINE_LOOP GL_TRIANGLES, GL_QUADS, GL_POLYGON 33 지엘의그래픽기본요소 (Primitives) GL_TRIANGLE_STRIP, GL_TRIANGLE_FAN, GL_QUAD_STRIP 지엘에서의다각형 (GL_POLYGON) 에대한세가지규칙 단순다각형 (Simple Polygon) 이어야한다. 볼록다각형 (Convex Polygon) 이어야한다. 평면다각형 (Flat Polygon) 이어야한다. 단순다각형과비단순다각형비교 34 17
기본요소의속성 (Attribute) 색 (Color), 크기 (Size), 두께 (Width), 패턴 (Stipple Pattern) 등 void glpointsize(glfloat size); void gllinewidth(glfloat width); void gllinestipple(glint factor, GLushort pattern); void glpolygonstipple(const GLubyte *mask); void glshademodel(mode); 드라이버지원값알아보기 glgetfloatv(gl_point_size_range); glgetfloatv(gl_line_width_range); gllinestipple 함수사용 glenable(gl_line_stipple); LINE gllinestipple(1, 0x3F07); // 0011 1111 0000 0111 ( 거꾸로 ) gldisable(gl_line_stipple); 지엘프로그램예 (pp. 460~464) [ 코드 9-10] 지엘의점그리기, [ 코드 9-11] 지엘의선그리기, [ 코드 9-12] 선분의색보간, [ 코드 9-13] 보간에의한다각형내부채움 35 비트맵 (Bitmap) 비트맵편집기 : Adobe Photoshop cf. 포스트스크립트편집기 : Adobe Illustrator 래스터모니터영상, 스캐너로읽은영상, 팩스에인쇄된영상, 페인트브러시로만든영상영상을구성하는개별화소의색을표현하고저장 예 : 7 9 = 63 개의화소배열 36 18
에일리어스 (Alias) 계단 (Stair-step, Jaggies) 모양의거친경계선 비트맵표현에서는화소단위로근사화할수밖에없기때문 무한해상도를지닌물체를유한해상도를지닌화소면적단위로근사화할때필연적으로일어나는현상 37 비트맵의확대 필연적으로에일리어싱을수반 추가의화소를채우기위한별도정보가없음 비트맵영상의확대 / 축소 38 19
포스트스크립트 (Postscript) 벡터그래픽장비로부터유래 화소라는개념이없음. 무한해상도실제로는영상을그려내는방식 영상을물체 ( 객체, Object) 단위로표현한것 영상을화소단위로표현하는대신정점좌표로표현 영상의표현방식을말하기때문에벡터그래픽장비는물론래스터장비에도적용할수있음 39 비트맵과포스트스크립트 비트맵그리기 = PAINTING, 포스트스크립트그리기 = DRAWING 영상선택 비트맵 : 비트단위, 포스트스크립트 : 물체 ( 객체 ) 단위 자석라소사용꽃잎선택 일러스트사용그린꽃 40 20
포스트스크립트글꼴 영상의윤곽선을수식으로표현 특징적인정점의좌표, 이를연결하는보간곡선의수식을명시 특징적인정점 = 제어점 (Control Point) 확대된정점위치에보간곡선을다시적용 비트맵보다매끄러운곡선 에일리어싱완화 포스트스크립트명령어 (PCL: Postscript Command Language) 를사용하여이러한보간작업수행 41 그래픽파일형식 영상압축 무손실압축 (Lossless Compression), 손실압축 (Lossy Compression) BMP(BitMapped Picture) 마이크로소프트윈도우즈운영체제의기본비트맵파일. 일반적으로압축을가하지않은파일 GIF(Graphic Interchange Format) 무손실압축을사용한비트맵파일. 8비트컬러, 즉 256 컬러로제한 256 컬러중하나를투명성을구현하는데사용. 특허가걸려있어유료 GIF 89a(Graphic Interchange Format 89a) 애니메이션을위한파일형식으로서하나의파일에일련의영상을저장 Moving GIF. 프레임재생률제어가능. 256 컬러. 사운드추가할수없음단순한웹애니메이션정도에유용 PNG (Portable Network Graphics) W3C( 웹표준단체 ) 에서추천파일형식. 향상된투명성제어기능. 무손실압축 JPEG(Joint Photographic Expert Group) JPEG은엄밀한의미에서일종의압축기법. 파일형식이아님 24비트컬러를지원. 손실압축 TIFF(Tagged Image File Format) 8비트, 24비트컬러지원. JPEG 및기타압축방법을수용 42 21
그래픽파일형식 그래픽파일저장방식 렌더링결과저장 : 비트맵파일 모델링결과와렌더링명령어저장 : 메타파일 ( 예 : 포스트스크립트파일 ) 동일한파일내부에포스트스크립트와비트맵동시저장가능메타파일예 PDF(Postscript Description File) 0 1 0 setrgbcolor 현재색을녹색으로설정 0 0 128 128 rectfill 외부사각형을채움 1 0 1 setrgbcolor 현재색을자홍으로설정 32 32 64 64 rectfill 내부사각형을채움 EPS(Extended PostScript), SWF(Shockwave Flash), WMF(Windows Meta File), SVG(Scaleable ab Vector Graphic), PICT(PICTure) 그래픽메타파일형식. 포스트스크립트, 비트맵, 텍스트동시저장가능 SWF: 플래시애니메이션을위한파일형식. 웹애니메이션에서사실상표준 WMF: 마이크로소프트윈도우즈에서사용하는메타파일형식 SVG: W3C에서추천하는그림파일형식 - XML(Extensible Markup Language) 에서자주사용 PICT: 매킨토시에서사용하는표준메타파일형식 43 언더샘플링으로인함 신호의복원 나이퀴스트주파수 : 원래신호가지닌최대주파수의 2배주파수 에일리어싱 Stroboscopic Effect 시간적에일리어싱 44 22
점샘플링으로인한에일리어싱 점샘플링과므와르패턴 므와르패턴 뒷부분의높은주파수를화소크기가수용하지못함 45 앤티에일리어싱 (Anti-Aliasing) 수퍼샘플링 (Super-Sampling) 부분화소에서샘플링. 사후필터링 부분화소의평균값을반영 지터에의한수퍼샘플링 물체자체가불규칙이라면불규칙샘플링이유리 46 23
수퍼샘플링 포인트샘플링 수퍼샘플링 4x4 수퍼샘플 수퍼샘플링예시 47 수퍼샘플링 포인트샘플링과수퍼샘플링 포인트샘플링 16x16 지터링 ( 수퍼샘플링 ) 48 24
영역샘플링 (Area-Sampling) 면적에비례. 미리계산한다는의미에서사전필터링 (Pre-Filtering) ( 백색 Area2 + 적색 Area1)/(Area1 + Area2) 포인트샘플링, 영역샘플링비교 ( 예 ) 49 영역샘플링 ( 가중치부여방법에따른분류 ) 동일가중치 피라미드가중치 원뿔가중치 50 25
영상필터링 화소그룹처리 (Pixel Group Processing) 어떤화소의색에인접화소의색이영향을주는것 Ex: 저역통과필터 (LPF: Low-Pass Filter) 또는블러링 (Blurring) 51 Blurring, Sharpening 컨볼루션마스크 (Convolution Mask) 52 26
모션블러 (Motion Blur) 컨볼루션마스크가중앙화소를중심으로방향성을지님물체가움직이는방향에있는화소들에대해서만가중치를적용 53 블러링에의한앤티 - 에일리어싱 수퍼샘플링에비해고속처리가능 수퍼샘플링은원래화면의해상도보다훨씬많은샘플링을요구 블러링은해상도를그대로둔채인접화소정보만을이용 블러링에서는마스크행렬과의곱셈을하드웨어화함으로써실행속도를더욱빠르게할수있음블러링은수퍼샘플링에비해실제해상도저하 수퍼샘플링은실제물체를기준으로더많은샘플링을가하는데비해블러링은실제물체가아니라인접화소를기준으로하기때문 원래물체영상이왜곡될위험성이있음 지엘의앤티-에일리어싱코드 (pp. 485~491) [ 코드 9-14] 지엘의앤티- 에일리어싱, [ 코드 9-15] 앤티-에일리어싱비교 54 27