렌더기의 구현 최 수 미 smchoi@sejong.ac.kr http://www.sejong.ac.kr/~smchoi

렌더기의 구현 직선이 화면에서 어떻게 그려지는지? 다각형은 어떻게 채워지는지? 관측공간 밖의 기본 요소들은 어떻게 될지? 그래픽스 시스템의 어느 부분이 쉽거나 부담스러운지? 텍스처 사상과 알파 채널 사용과 같은 프레임 버퍼를 사용하는 새로운 기능

네 가지 주요 작업 프로그램 내의 기본요소의 정의에서 디스플레이까지 모델링 (다각형의 생성) 기하학적 처리 (다각형에 대한 처리) 정규화 절단 은면 제거 음영처리 투영 3D, 부동 소수점 수 래스터화(화소에 대한 처리) 2D, 고정 소수점 수 디스플레이

파이프라인 구현

파이프라인의 구현전략 (1) 객체지향적 for (each object) render (object); 전향적 (2) 영상지향적 for (each pixel) assign_color (pixel); 후향적 효과적 자료구조를 필요로 한다

객체지향 접근

변환의 구현 모델-관측 변환 투영 변환 등가적 접근 객체좌표, 카메라좌표, 절단좌표, 정규화 장치,윈도우좌표 변환 순서

객체 좌표계에서 모델관측행렬에 의해서 눈 좌표계로 변환됨. 관측자가 원점에 있음 정규화 과정에 의해서 객체는 사전 왜곡. 왜곡된 객체들의 등가적 직교 투영을 위해서 투시관측에서는 절두체, 평행관측에서는 평행육면체의 관측공간을 갖게 됨 – 절단공간 정규화 장치 좌표계 (normalized device coordinate) : 절단된 정점의 w 성분이 1이 아니라면, 동차 좌표에서 정규 삼차원 좌표로 변환하기 위해 투시제산. 절단이 이루어지면 절단되지 않은 점들이 정규화 장치 좌표계에 표현됨. 깊이정보는 은면 제거를 위해 유지됨 화면 좌표계로의 변환

시역 변환

선분 절단 Cohen-Sutherland 절단 기본개념 선분의 끝점들을 부호화한다 선분들이 모두 윈도우 안에만 있든지 윈도우 밖에만 있을 때까지 계속해서 분할한다 분할은 윈도우 경계에서 일어난다 이차원 절단

대부분의 부동소수점 곱셈과 나눗셈을 부동소수점 감산과 비트연산으로 대치함 외각부호(outcode)를 사용 좌 우 하 상

outcode1 = outcode2 = 0000 : 수용 (AB) 네 가지 경우 outcode1 = outcode2 = 0000 : 수용 (AB) outcode1 != 0000 , outcode2 = 0000 (또는 그 반대) : 단축 (CD) (outcode1 & outcode2) != 0000 : 제거 (EF) 같은 변의 외부에 놓여 있음 (outcode1 & outcode2) = 0000 : 제거 또는 단축 (GH, IJ) 다른 변의 외부에 놓여 있음

Cohen-Sutherland line clipper int ClipSegment (Point2& p1, Point2& p2, RealRect W) { do { if(trivial accept) return 1; // some portion services if(trivial reject) return 0; // no portion survives if(pl is outside) if(pl is to the left) chop against the left edge else if(pl is to the right) chop against the right edge else if(p1 is below) chop against the bottom edge else if(pl is above) chop against the top edge } else // p2 is outside if(p2 is to the left) chop against the left edge else if(p2 is to the right) chop against the right edge else if(p2 is below) chop against the bottom edge else if(p2 is above) chop against the top edge While (1);

많은 수의 선분이 있지만, 실제로 몇 개만 디스플레이되는 경우에 가장 잘 동작 대부분이 accept 이거나 reject 일 경우 적합 이 알고리즘은 삼차원으로 확장 가능

직선의 표현 명시적 표현 (explicit form) 매개변수 표현 (parametric form)  수직선 표현이 어려움  수평선, 수직선 표현 가능 (안정적)

Liang-Barsky 절단

Liang-Barsky 절단 윈도우 상변과(y=ymax)의 교차점

다각형 절단 다각형 절단을 선분 절단으로 볼 수 없다 절단의 결과 여러 개의 다각형이 생성될 수 있다 절단의 결과 다각형의 수가 증가하는 것이 바람직하지 않을 수 있다 볼록 다각형으로의 분할(tesselation) 오목한 다각형의 절단 객체의 수를 증가 구현상의 어려움

볼록한 다각형의 분할

Sutherland-Hodgeman 절단

다른 기본 요소의 절단 복잡한 객체의 절단 한정 사각형(bounding box) 다각형 정점들의 x와 y값의 최소값과 최대값 한정 사각형이 윈도우에 걸쳐 있을 때만, 다각형의 모든 모서리를 사용하여 자세한 절단 수행 다각형과 절단 윈도우

곡선, 곡면, 문자열 대단히 어렵다 두 가지 접근법 다각형으로 근사 프레임 버퍼에서 절단 래스터화 까지 절단이 지연될 수 있지만, 래스터화 전에 절단하는 것이 더 좋다 래스터 객체 (예> 화소블럭) 은 프레임 버퍼에서 절단될 수 있다

삼차원에서 절단

Cohen-Sutherland 절단 4비트 외곽부호를 6비트 외곽부호로 대체 추가된 2bit (절단 공간의 앞 또는 뒤)

Liang-Barsky 절단 선분의 삼차원 매개변수 표현 z 축에 대한 방정식 추가 파이프라인 절단기는 절단 공간의 앞과 뒤에 대해 절단하기 위하여 두 모듈 추가

Sutherland-Hodgeman 절단 파이프라인 절단기는 절단 공간의 앞과 뒤에 대해 절단하기 위하여 두 모듈 추가

이차원과 삼차원 절단의 차이 평면과 직선의 교차계산 교점

경사 투영 = 데이터를 밀림 변형 -> 직교 투영 정규화와 절단 직교 관측에 대한 절단 경사 관측에 대한 절단 경사 투영 = 데이터를 밀림 변형 -> 직교 투영 밀림 전의 평면도 밀림 후의 평면도

은면 제거 은면 제거(Hidden Surface Removal) 두 가지 접근법 객체를 래스터화 하기 전에 각 객체가 관측자에게 보이는지, 다른 객체에 의해 가려지는지 알기 위함 두 가지 접근법 객체공간적 방법 영상공간적 방법 4 가지 경우 K개의 다각형 중 하나 선택, 남은 k-1 개의 다각형과 비교 … 반복

영상공간적 방법 렌더링의 정확도를 높이기 위해 각 픽셀에서 하나 이상의 광선을 사용할 수 있음

후면 제거 후면제거 후향 다각형을 선별(culling) 은면 제거를 적용하기 전에 후향 다각형 제거 보이는 면에서

정규화 장치 좌표계로 변환 후에는 모든 관측은 투영의 방향이 z축인 직교관측 평면의 식이 c의 부호만 계산하면 됨 OpenGL의 후면 제거함수 : glCullFace 함수

Z-버퍼 알고리즘 Z 버퍼 알고리즘 영상-공간에서 동작 화소가 아닌 다각형에 대해서 루프 파이프라인 구조와 호환, 주사 변환처리의 일부로 간주 가능 하드웨어나 소프트웨어에서 구현 용이

예> 32bit 요소를 가진 1024*1280 z 버퍼 <초기화> Z 버퍼의 각 요소는 최대 거리로 초기화 프레임 버퍼는 배경색으로 초기화 <진행 순서> 다각형을 하나씩 래스터화 화소를 통한 광선과 다각형의 교차점에 대응하는 다각형 상의 점에 대해 투영 중심으로부터 거리 계산 계산된 값을 Z 버퍼의 값과 비교 Z 버퍼의 거리보다 크면, 이 점은 보이지 않고 거리보다 작으면 Z 버퍼의 거리를 갱신하고 프레임 버퍼의 대응점에 대하여 계산된 음영을 배치

증분적 Z-버퍼 알고리즘 주사선 별로 래스터화 하는 방식에 의해 다각형을 래스터화

깊이정렬과 화가 알고리즘 은면 제거에 대한 객체공간 알고리즘 알고리즘 다각형들을 정렬 전향 렌더링

x와 y 범위에서 겹침에 대한 검사 저장된 다각형의 z 범위

순환적 겹침 올바른 순서 없음 다각형을 분할하여 새로운 순서 찾기 시도 한 다각형의 모든 정점이 다른 다각형에 의해 결정되는 평면의 같은 편에 놓임 관통하는 다각형

주사선 알고리즘 한번에 하나의 다각형보다는 한번에 한 주사선에 대해 동작 증분적 깊이 계산을 사용

선분의 주사 변환 DDA(Digital Differential Algorithm) for(ix = x1; ix<=x2; ix++) { y +=m; write_pixel(x, round(y), line_color); }

큰 기울기와 작은 기울기를 갖는 직선들에 의해 생성된 화소들 기울기가 1보다 큰 경우, x와 y의 역할을 변경

Bresenham 알고리즘 DDA의 실수 덧셈을 정수덧셈과 부호검사로 대체 가장 보편적이며, 하드웨어로 구현

부동 소수점 연산 -> 고정 소수점 연산으로 대치 알고리즘을 증분으로 적용

다각형의 주사변환 내부-외부 검사 교차 검사 또는 홀수-짝수 검사 내부 : 홀수 개의 변과 교차 흔히, 점을 통과하는 직선을 주사선을 대치하고 내외부 결정을 위해 다각형의 변들과의 교차를 셈 홀수-짝수 검사에 의한 채우기

감음 검사 (winding test) 다각형을 점이나 직선 주위에 감겨지는 매듭으로 생각 (임의의 한 정점에서 시작해서 일정한 방향으로 돌아서 시작점으로 다시 돌아오는 순회를 생각) 감음수에 따라 채우기 방식을 변경 가능 2 1 감음수가 0 보다 크면 채우기

OpenGL과 오목한 다각형 볼록 다각형만이 올바르게 렌더링되는 것이 보장 다각형을 삼각형인 평면 볼록 다각형들로 분할 가능하면 삼각형 띠 또는 삼각형 부채꼴과 같이 성질이 좋은 삼각형들로 분할 GLU 라이브러리 안에 분할기 (구멍이 없는 단순한 다각형에 대해서 작동)

(with the vertex callback) 분할기 객체 (tessellator object) mytess = gluNewTess( ); gluTessBeginPolygon(mytess, NULL); gluTessBeginContour(mytess); for(i=0; i<nvertices; i++) gluTessVertex(mytess, vertex[i], vertex[i]); gluTessEndContour(); gluTessEndPolygon(mytess); location an opaque pointer (with the vertex callback)

z-버퍼를 이용한 주사변환 직교투영, 은면제거, 음영처리를 동시에 실행 정규화 장치좌표계 화면 좌표계

채우기와 정렬 범람 채우기 (flood fill) Bresenham 알고리즘을 사용하여 다각형의 변들을 프레임 버퍼로 래스터화 flood_fill(int x, int y) { if (read_pixel (x, y) == WHITE) write_pixel (x, y, BLACK); flood_fill (x-1, y); flood_fill (x+1, y); flood_fill (x, y-1); flood_fill (x, y+1); }

주사선 알고리즘 구간(span)이 표시된 다각형

주사선 알고리즘 (계속) 정점 리스트에 의해서 생성된 다각형 주사선에 의해 채우기를 할 때 정점들의 바람직한 순서 Y-X 알고리즘에 대한 자료 구조

특이성 (singularity) 해결 1> 처한 상황이 어느 경우인지를 판단한 후, 적절하게 변 교차 계산 함으로써 특이성 배제 예: 실제 프레임 버퍼의 2배 해상도를 갖는 가상 프레임 버퍼 (화소는 짝수 y, 정점은 홀수 y) OpenGL에서는 화소의 중심을 정수 사이의 중간에 둠 0번 또는 2번 교차 1변 교차

앤티엘리어싱 (Antialiasing) 이상적인 래스터 직선 엘리어싱된 선분 앤티엘리어싱된 선분 (a) 확대 (b) 확대 면적 평균에 의한 앤티엘리어싱

한 화소를 공유하는 다각형 : 공간 영역 엘리어싱 화소에 할당된 색 : 과측자에게 가장 가까운 다각형과 연관된 색 세 삼각형의 색의 면적 가중 평균에 기반한 색 할당 애니메이션 : 시간 영역 엘리어싱 화소당 하나 이상의 광선을 사용 앤티엘리어싱 참조 : 색그림판 1, 색그림판 2

디스플레이 고려 사항 색체계들 사이의 차이들을 삼자극 값을 표현하기 위한 다른 좌표계를 간주할 수 있음 색도좌표 (chromaticity coordinate) : RGB 색에 대한 삼자극 값(T1, T2, T3)이 주어질 때 색도 좌표

색도 좌표계에서 만들 수 있는 삼각형 볼 수 있는 색과 디스플레이의 색범위

HLS(hue-lightness-saturation) 색상 - 명도 - 채도

감마수정

흩뿌리기(Dithering)와 반명암법(Halftoning) 색 해상도와 공간 해상도를 교환 공간해상도를 4배 감소, 두단계 계조값이 아닌 17단계(검은 화소의 개수)로 디스플레이 glEnable(GL_DITHER)