Chapter11. 래스터 변환

래스터 그래픽과 벡터그래픽

• Vector Graphic : 두 좌표를 기준으로 연결된 선을 그리는 방식으로, 옛날 혹은 디스플레이에 선만 그려도되는 시스템에 사용된다디화소의 개념이 없어 해상도가 무한이다. 따라서 엘리어싱 문제(픽셀이 소실되는 문제), 프레임 버퍼 등이 없다.

• Raster Graphic :  래스터(Raster)는 그래픽스 시스템 안의 프레임 버퍼에서 화소(Pixel)의 2차원 배열(Array)을 의미한다. 한 픽셀들은 단일 색을 가지고 있고 이 픽셀을 채워나감으로써 하나의 그림이 완성되는 것.

그럼,  지난 시간까지 우리가 한 것은 뭘까? 가상의 3차원 공간 상에 그리고자 하는 물체를 놓았다. 그리고 그 물체에 기하변환을 가하여 원하는 모습으로 변환시켰다(모델 변환). 그리고 카메라의 위치나 방향을 지정하여 물체를 촬영하였다.(시점 변환). 카메라를 기준으로 투영방식을 정해주어 투영하고자 하는 가시범위를 지정하여 가시성을 판단하였다.(투영 변환), 마지막으로 윈도우 상에 실질적으로 물체가 투영될 공간을 지정해주었다.(뷰포트 변환). 그런데, 생각해보면 우리가 코딩을 할때 가상의 3차원 공간 상의 좌표를 이용했었다. 그런데 그 좌표는 과연 우리가 실질적으로 보고있는 모니터 화면의 좌표일까? 아니다. 우리가 지금까지 GL-Viewing PipeLine에서 사용했던 좌표는 가상의 3차원 공간상의 좌표였고 뷰포트 변환 이후에 만들어진 이미지는 벡터 그래픽 상태이다. 이를 실질적으로 2차원 모니터 좌표와 픽셀에 표현해주어야 한다. 이 과정이 주사 변환, 레스터 변환(Rasterization)이다.

래스터 변환

• 이 래스터 변환은 뷰포트  변환 이후, 은면 제거와 동시에 진행한다.
• 깊이와 색을 보간
• 정점의 z 값으로부터 선분 및 내부면의 깊이를 보간
• 정점의 색으로부터 선분 및 내부면의 색을 보간
• 화면에 보이는 모든 것은 래스터 변환 결과이다
• 최대의 연산속도, 최대의 정확성이 요구된다.

화소좌표

• 픽셀 좌표계 상에서 각 픽셀이 좌표축 상에서 어디에 위치할 것인가를 결정한다.
• 아래의 그림처럼 좌표의 원점을 픽셀의 중간으로 결정할 것인가, 모서리에 위치하게 할 것인가(보통은 (b))

• 일반적으로는 (b)의 방식으로 왼쪽 하단부나 오른쪽 상단의 모서리로부터 출발한다.

선분의 래스터 변환

• x축 또는 y축 중 한쪽 기준으로 선택할 때 -> 끊어짐 발생
• 아래 그림의 빨간색 직선이 있는데 이것을 픽셀 단위로 그리고자 한다고 가정하고, x축을 기준으로 색을 칠해나간다. x축을 좌표로 색을 칠해나가니까 색칠이 연결되지 않고 뚝뚝 끊키는 문제가 발생한다.

• 그래서 이제 y축을 기준으로 그려나갔더니 선을 표현할 수 있게되었다. 하지만, 연산량이 너무 많아진다는 문제가 발생한다. 래스터 변환은 빠른 연산이 매우 중요하다고 하였다.

• 이 문제점들을 해결하고자 사람들은 DDA(Digital Differential Analyzer)알고리즘을 개발하였다. 
• 이는 변화량을 계산하는 것이다. 예를들어 x축 기준의 래스터 변환을 한다고 했을때  x좌표가 1만큼 증가하면 어디쯤에 찍힐 것인지 계산을 하는 것이다. 이는 당연히 오차라는 문제점에 직면하게된다.

• 그래서 등장한 것이 브래스넘 알고리즘이다.
• 선을 그려내기 위해 선택되는 화소들을 오차가 적게 최대한 잘 선택하기 위한 것으로, 화소 중심과 선분간의 수직 거리에 의해 판단하는 방법이다.

수직 거리가 B에 가까움

다각형의 래스터 변환

• 다각형은 우선 선분을 정의하고, 선분의 상하지정을 통해 다각형을 정의한다.
• 선분의 상하지정은 선분의 일차 방정식(Ax+By+C = 0)을 기준으로 2차원 정점의 좌표를 대입했을 때, 0보다 크면 선분의 안쪽에 위치할 것이고 0보다 작으면 바깥쪽에 위치하게된다.

• 위와 같이 다각형을 정의했다면 이제 그 다각형을 채워야할 것이다.
• 다각형 채움 알고리즘(주사선 채움 알고리즘)
• 참고해야할 것은 컴퓨터 그래픽스 세계에서는 선은 곧 픽셀로 이루어져있기 때문에 선을 많이 그리면 결국 면이 만들어지게 된다.
• 0번째 줄에서 레이져(주사선)를 쭉 긋는다고 상상하면 어떠한 선분과도 만나지 않기 때문에 그리지 않는다
• 1번줄을 레이져로 쭉 긋게되면 선분과 한번만나고 조금만 더 그으면 두번째 선분과 만난다. 그러면 선분과 만난 지점과 지점 사이의 픽셀을 색칠하는 방식이다.
• 아래의 그림을 보면 각 레이져마다 존재하는 홀수번째 교차점부터 짝수번째 교차점 사이를 색칠하게 된다.

• 이 때 예외적으로 극대점들은 교차하지 않는 것으로 간주해야한다.(HF)
• 극소점들은 각각 교차한 것으로 간주해야한다.
• 주사선과 평행한 선분은 없는 것으로 간주한다(DE)이는 CD와 FE에 의해 처리된다.

• 복잡한 도형들에 대해서는 다각형 내부 확인 알고리즘이 필요하다.
• 내부에서 외부를 향한 직선은, 다각형과 홀수번 교차한다. 반대로, 외부에서 내부를 향한 직선은 다각형과 짝수번 교차한다.

• 씨앗채움 알고리즘(경계 채움 알고리즘, 홍수채움 알고리즘)
• 경계채움 알고리즘
• 씨앗을 하나 놓고 해당 화소의 색을 인근으로 번져 나가게 하는 방식으로, 경계화소 색을 만날때까지 4방 또는 8방향으로 번져나감

• 그리고 4방향 연결과 8방향 연결을 통해 다각형이 만들어지게 됌

• 홍수채움 알고리즘
• 경계채움 알고리즘은 경계화소의 색일 동일하다는 가정하에, 씨앗에서부터 번져나가는 색깔과 비교하여 다를 경우에 다각형을 만들어내는 것이지만, 경계화소의 색은 상이할 수도 있으므로, 삼각형 내부의 현재 색을 백색으로 지정하고 백색을 만날때까지 4방 또는 8방으로 진행하는 방식이다.

보간법

보간법이란 알려진 데이터 지점의 고립점 내에서 새로운 데이터 지점을 구성하는 방식이다. 즉 원래 존재하는 좌표값으로 새로운 좌표값을 추려내는 방식이다. 대표적으로 무게중심 좌표와 양방향 선형보간이 존재한다.

선분의 무게중심 좌표

• V의 색을 구한다고 가정했을 경우, P와 Q의 색을 보간하여 구할 수 있다.
• 점 P는 원점 O에서 점P로 가는 벡터 P로 취급할 수 있다. 여기서 원점은 임의 위치로 아무데나 설정할 수 있다.
• 점 V는 원점 O에서 선분PQ로 가는 벡터로 표시할 수 있다.
• 만약 점 V가 선분의 중심점이라면 P에서 V로 가는 벡터는 P에서 Q로가는 벡터와 방향만 같고 길이만 절반이므로 PV = (1/2)*(P-Q)이다.
• 그런데, 벡터의 덧셈규칙에 의해서 OV벡터는 OP벡터 + PV벡터이다. 따라서 V = P + (1/2)*(Q-P)이다.
• 여기서 V가 꼭 PQ의 중심점이라고 가정할 필요는 없고 그냥 PQ선분상의 임의의 점이라고 한다면  V = P + t*(Q-P)이다.
• 결국 V = (1-t)P + tQ = αP + βQ이다.
• 결국 정점 P와 Q로부터의 무게중심을 구했으므로 두 정점 색상의 평균으로 V의 색이 결정됌

삼각형의 무게중심 좌표(양방향 선형보간)

• 이번엔 선분들을 통해 만들어진 다각형 중, 삼각형을 고려해보겠다
• 정점 P,Q,R 좌표를 이용해서 무게중심 V'를 추려내고 색상을 보간할 수 있게된다.
• 선분의 무게중심을 구했듯이 정점은 아무데나 있다고 가정한다
• 일단 삼각형의 무게중심 좌표는 항상 2:1의 비율을 갖고 있다.
• PQ 선분의 임의의 점 V는 선분의 무게중심인 V = P+t(Q-P)좌표에 존재한다.
• 그리고 V'는 RV선분 사이의 중간점이라고 본다면 (1/2)*(R-V)이다. 어차피 임의의 점이라고 치니까 s라고보자
• 여기서 벡터의 덧셈 공식에 의해서, V' = V + s(R-V)가  되니까 V' = P+t(Q-P) + s(R-(P+t(Q-P)))이 된다
• 이를 정리하면 V' = αP + βQ+γR이 된다.

• 실질적으로 알파,베타,감마 값을 대입하여 보간은 다음과 같이 이루어진다.(위를 이해하면 아래는 바로 이해된다)