1장 – 그래픽스 시스템과 모델 2장 – 그래픽스 프로그래밍 3장 – 입력과 상호작용 4장 – 기하학적 객체와 변환 7장 구현 1장 – 그래픽스 시스템과 모델 2장 – 그래픽스 프로그래밍 3장 – 입력과 상호작용 4장 – 기하학적 객체와 변환 5장 – 관측 6장 – 음영 객체가 입체적으로 보이도록 음영을 가하는 방법 광-재질 상호작용의 종류들 단순한 반사모델(Phong 모델)-실시간 그래픽스 하드웨어에 사용 OpenGL 음영함수들 다각형 음영 - 평면 음영, Gouraud 음영, Phong 음영
7장 구현 학습목표 클리핑 래스터화 은면제거
기본 구현전략 두 가지의 구현 전략 객체 중심적 2) 영상 중심적 for(each_object) render(object); 전향적 파이프라인 렌더기에 적합 2) 영상 중심적 for(each_pixel) assign_a_color(pixel); 후향적 광선추적 렌더기에 적합
네 가지 주요 작업 1. 모델링(Modeling) – 다각형의 생성 2. 기하학적 처리(Geometric processing) – 다각형에 대한 처리 3. 래스터화(Rasterization) – 화소에 대한 처리 4. 단편처리(Fragment processing)
모델좌표 → 세계좌표 → 카메라좌표 → 절단좌표 → 정규화 장치좌표 → 화면좌표 정규화 투시제산 기하학적 처리 기하학적 처리 정규화 클리핑 은면제거 음영 모델좌표 → 세계좌표 → 카메라좌표 → 절단좌표 → 정규화 장치좌표 → 화면좌표 정규화 투시제산
래스터화
클리핑 클리핑 윈도우에 대한 2D 클리핑 클리핑 입체에 대한 3D 클리핑 선분, 다각형에 대해 용이 곡선과 텍스트에 대해서 어려움 먼저 선분과 다각형으로 변환함
마구잡이 접근법: 클리핑 윈도우의 모든 변들에 대해서 교점을 계산 2D 선분의 클리핑 마구잡이 접근법: 클리핑 윈도우의 모든 변들에 대해서 교점을 계산 비효율적: 매 교점 당 하나의 나눗셈
Cohen-Sutherland 알고리즘 아이디어: 가능한 한 많은 경우를 교점 계산 없이 제거 선분의 끝점들을 부호화한다 선분들이 모두 윈도우 안에만 있든지 윈도우 밖에만 있을 때까지 계속해서 분할한다 분할은 윈도우 경계에서 일어난다 클리핑 윈도우의 변들을 결정하는 네 개의 직선으로부터 시작
Cohen-Sutherland 알고리즘 대부분의 부동소수점 곱셈과 나눗셈을 부동소수점 감산과 비트연산으로 대치함 외각부호(outcode)를 사용 좌 우 하 상 b0 b1 b2 b3 b0 = 1 if y > ymax, 0 otherwise b1 = 1 if y < ymin, 0 otherwise b2 = 1 if x > xmax, 0 otherwise b3 = 1 if x < xmin, 0 otherwise
Cohen-Sutherland 알고리즘 네 가지 경우 outcode1 = outcode2 = 0000 : 수용 outcode1 != 0000 , outcode2 = 0000 (또는 그 반대) : 단축 outcode1 & outcode2 != 0000 : 제거 outcode1 & outcode2 = 0000 : 제거 또는 단축
예제
예제
예제
예제
예제
많은 응용에서, 클리핑 윈도우는 전체의 데이터베이스에 비해서 작은 크기이다 효율성 많은 응용에서, 클리핑 윈도우는 전체의 데이터베이스에 비해서 작은 크기이다 대부분의 선분들은 하나 이상의 윈도우 변의 외부에 있고 외곽부호에 의해서 제거될 수 있다 여러 단계에 걸쳐 단축되어야 하는 선분에 대해서 알고리즘이 재실행 될 때 비효율적
Liang-Barsky 클리핑 선분 선분이 속한 직선과 윈도우를 결정하는 직선들과의 교점에서 α 값의 순서를 살펴봄으로써 경우들을 판별할 수 있다 p2 p1
(a)의 경우: a4 > a3 > a2 > a1 Liang-Barsky 클리핑 (a)의 경우: a4 > a3 > a2 > a1 우, 상, 좌, 하 순으로 교차 : 단축 (b)의 경우: a4 > a2 > a3 > a1 우, 좌, 상, 하 순으로 교차: 기각
장점 Cohen-Sutherland 방식과 마찬가지로 쉽게 수용/기각을 결정 a 값을 사용함으로써, C-S 방식에서처럼 재귀적 알고리즘을 사용할 필요가 없다 3D로 확장
그러나, 볼록 다각형을 클리핑하면 많아야 하나의 다각형이 된다 다각형 클리핑 선분 클리핑처럼 단순하지는 않다 선분을 클리핑하면 많아야 하나의 선분이 된다 다각형을 클리핑하면 여러 개의 다각형이 될 수 있다 그러나, 볼록 다각형을 클리핑하면 많아야 하나의 다각형이 된다
분할과 볼록함 하나의 전략은 비볼록 다각형을 삼각형들로 나누는 것이다(분할) 채우기도 쉬워진다 분할 코드가 GLU 라이브러리에 있다
블랙박스로서의 클리핑 선분 클리핑을 두 개의 정점을 받아들여서 아무 정점도 출력하지 않거나 클리핑된 선분의 정점들을 출력하는 프로세스로 간주함
윈도우의 각 변에 대한 클리핑은 다른 변들에 대해서 독립적이다 선분의 파이프라인 클리핑 윈도우의 각 변에 대한 클리핑은 다른 변들에 대해서 독립적이다 네 개의 독립적인 클리퍼로 된 파이프라인의 사용가능
다각형의 파이프라인 클리핑 3차원: 전면 클리퍼와 후면 클리퍼 추가 SGI Geometry Engine에서 사용되는 전략 약간의 지연만을 초래
복잡한 다각형에 대해서 클리핑 하기 보다는 축과 정렬된 한정 사각형을 사용할 수 있다 다각형을 포함하는 축과 정렬된 가장 작은 사각형 계산 용이: x 와 y의 max와 min계산만 필요
한정 사각형 많은 경우한정 사각형만을 이용하여 수용/기각을 결정할 수 있다 기각 수용 상세한 클리핑 필요
3D에서의 Cohen Sutherland 6-비트 외곽부호 사용 필요한 경우, 면에 대해서 선분을 절단
클리핑과 정규화 3D에서의 일반적 클리핑에서는 임의의 평면과 선분간의 교점계산이 필요하다 예: 경사관측
평면과 직선의 교점
정규화된 형식 정규화 이전 정규화 이후 top view 정규화는 관측의 한 부분이지만 정규화 이후에는, 직육면체의 변에 대한 클리핑이 된다 교점의 계산에 실수 뺄셈만 필요하다, x > xmax ?
음영값은 컬러, 텍스처, 음영 모델에 의해서 정해진다 정점들로부터 올바른 픽셀을 결정하는 알고리즘들을 공부한다 래스터화 래스터화 (주사 변환) 정점들의 집합으로 지정된 객체의 내부에 있는 픽셀에 음영값을 줌 선분 다각형: 주사 변환 = 채우기 음영값은 컬러, 텍스처, 음영 모델에 의해서 정해진다 정점들로부터 올바른 픽셀을 결정하는 알고리즘들을 공부한다
윈도우 좌표계에서 양 끝점의 위치가 정수인 선분에서 시작 구현에 write_pixel 함수가 있다고 가정 선분의 주사변환 윈도우 좌표계에서 양 끝점의 위치가 정수인 선분에서 시작 구현에 write_pixel 함수가 있다고 가정 write_pixel(int ix, int iy, int value);
Digital Differential Analyzer DDA 알고리즘 Digital Differential Analyzer DDA 는 미분방정식의 수치적 해를 위한 기계적 장치였다 직선 y=mx+ h 는 다음 방정식을 만족한다 dy/dx = m = Dy/Dx = y2-y1/x2-x1 직선을 따라서 Dx = 1, Dy=m for(ix=x1; ix<=x2,ix++) { y+=m; write_pixel(x, round(y), line_color); }
문제 DDA = 각 x 에 대해서 가장 가까운 y를 그림 가파른 직선에서 문제
대칭을 이용 0 m 1 이라고 가정 m > 1인 경우, x와 y의 역할을 바꿈 각 y에 대해, 가장 가까운 x를 그림
Bresenham 알고리즘으로 모든 실수연산을 없앨 수 있다 0 m 1 경우만 고려 DDA는 매 스텝마다 하나의 실수덧셈을 요구 Bresenham 알고리즘으로 모든 실수연산을 없앨 수 있다 0 m 1 경우만 고려 다른 경우는 대칭으로 해결 픽셀의 중심이 정수의 중간에 있다고 가정 그려진 픽셀에서 시작한다면 프레임 버퍼 상에서 다음에 그려질 픽셀 후보는 둘 밖에 없다
후보 픽셀들 마지막 픽셀 후보들 직선이 이 픽셀의 임의의 부분을 통과할 수 있었다
결정변수 d 는 정수 d < 0 위의 픽셀 사용 d > 0 아래 픽셀 사용
dk+1= dk –2(Dy- Dx), otherwise 증분 형식 x = k에서의 결정변수의 값 dk를 이용해서 보다 효율적인 형식을 얻는다 dk+1= dk –2Dy, if dk > 0 dk+1= dk –2(Dy- Dx), otherwise 매 x 마다, 정수 덧셈과 검사만 필요 그래픽스 칩에서 하나의 명령
증분 형식
다각형의 주사변환 주사변환 = 채우기 다각형의 내부검사 홀수-짝수 채우기 감음수 볼록 다각형은 쉽다 비 단순의 경우 어려움 홀수 짝수 검사 변과의 교차를 검사 감음수 홀수-짝수 채우기
감음수 시계 방향으로 점을 감는 수를 센다 내부 점의 다른 정의: 감음수 0이면 내부 감음수 = 1 감음수 = 2
프레임 버퍼에서 채우기 파이프라인의 끝에서 채우기 볼록 다각형만 채운다 비 볼록 다각형은 분할 된 것으로 가정한다 음영(컬러)가 정점들에 대해서 계산되었다 (Gouraud 음영) z-버퍼 알고리즘과 결합 음영을 보간하며 주사선을 따라 진행함 증분적 작업은 적다
보간의 사용 C1 C2 C3 는 glColor 나 정점음영으로부터 주어진다 C4 는 C1 과 C3 를 보간함으로 결정된다 C5 는 C2 와 C3 를 보간함으로 결정된다 C4 와 C5 구간 사이에서 보간 C1 C4 C2 주사선 C5 구간 C3
내부의 한 점(시드 포인트)을 알고 있으면 (WHITE) 채우기가 재귀적으로 실행될 수 있다 범람 채우기 내부의 한 점(시드 포인트)을 알고 있으면 (WHITE) 채우기가 재귀적으로 실행될 수 있다 에지를 버퍼 내에 변/내부 컬러(BLACK)로 변환 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); } }
다각형들과 주사선과의 모든 교점들의 자료구조를 유지함으로써 채우기를 할 수 있다 주사선 채우기 다각형들과 주사선과의 모든 교점들의 자료구조를 유지함으로써 채우기를 할 수 있다 주사선에 의한 정렬 각 구간을 채우기 정점 리스트에 의해서 생성된 정점 순서 원하는 순서
자료 구조 y-x 알고리즘에 대한 자료구조
은면 제거 객체-공간 접근법: 다각형을 쌍으로 검사함 n 개의 다각형에 대해 최악의 경우 복잡성은 O(n2) 부분적으로 가림 독립적으로 그릴 수 있음
영상-공간 접근법 각각의 투영선에 대해 (n x m 프레임 버퍼에서 nm 개) k 개의 다각형 중 가장 가까운 것을 선택 복잡성 O(nmk) 광선추적 z-버퍼
후면제거 (Culling) 면이 보이는 조건은 90 -90, 또는 cos 0, 또는 v • n 0 평면의 식은 ax + by +cz +d =0 n = ( a b c 0)T 정규화 이후에 v = ( 0 0 1 0)T 이므로 c의 부호 검사만 필요 OpenGL에서 간단히 culling을 인에이블 할 수 있지만 비볼록 객체가 있으면 올바로 동작하지 않을 수 있다
Z-버퍼 알고리즘 z 버퍼 또는 깊이 버퍼라고 부르는 버퍼를 사용하여 각 픽셀에 대해서 지금까지 발견된 가장 가까운 객체의 깊이를 저장 다각형을 그릴 때, 각 픽셀의 깊이를 z 버퍼의 깊이와 비교 만일 작으면, 픽셀의 음영을 컬러버퍼에 그리고, z 버퍼의 내용을 갱신
y = 0 z = - x 증분적 Z-버퍼 알고리즘 주사선 단위로 작업할 때, 깊이의 변화는 다음을 만족한다 ax+by+cz=0 주사선을 따라서 y = 0 z = - x 화면 공간에서 x = 1
화가 알고리즘 다각형을 멀리 있는 것부터 그림으로써 뒤에 있는 다각형이 가리워지도록 한다 B,A 순으로 그림 관측자에게 B는 A 뒤에 있다
다각형들의 순서를 정렬하고 쉬운 것은 먼저하고 어려운 것은 나중에 한다 깊이 정렬 먼저 다각형들의 순서정렬이 필요하다 O(n log n) 계산 모든 다각형들이 다른 다각형의 앞이나 뒤에 있는 것은 아니다 다각형들의 순서를 정렬하고 쉬운 것은 먼저하고 어려운 것은 나중에 한다 COP로부터의 거리에 의해 정렬된 다각형들
다각형들이 z 방향에서는 겹치지만 x 나 y 방향으로는 겹치지 않는 경우 쉬운 경우 A가 다른 모든 다각형들 뒤에 있다 그릴 수 있다 다각형들이 z 방향에서는 겹치지만 x 나 y 방향으로는 겹치지 않는 경우 독립적으로 그릴 수 있다
어려운 경우 순환적 겹침 모든 방향으로 겹치지만 하나가 다른 것의 한쪽 방향에 있는 경우 관통
앨리어싱 래스터화된 이상적인 직선의 폭은 한 픽셀 매 x 마다 가장 좋은 y 를 선택 (또는 그 역) 앨리어싱된 래스터 직선을 생성한다
면적평균에 의한 앤티앨리어싱 이상적 직선에 의해서 커버되는 면적에 따라서 여러 픽셀에 컬러 값을 준다 앤티앨리어싱 원래 magnified
다각형 앨리어싱 다각형에 대해서 앨리어싱이 심각할 수 있다 세 개의 다각형이 색을 결정 울퉁불퉁한 변 작은 다각형이 무시됨 한 다각형의 색이 픽셀의 색을 전적으로 결정하지 않도록 합성이 필요 세 개의 다각형이 색을 결정