[CG] 컴퓨터그래픽스 02. Rasterization

2020/04/06 - [CSE] - [CG] 컴퓨터그래픽스 01.기본개념

2020/04/06 - [CSE] - [CG] 컴퓨터그래픽스 02. Rasterization

2020/04/07 - [CSE] - [CG]컴퓨터 그래픽스 03. 기하 변환 Geometric Transformation

3. 선 그리기. 다각형 채우기 Line Drawing, Polygon Filling

앞서 살펴본 그래픽스 파이프라인에서, 최종 프로젝션을 한 후, 디스플레이에서 픽셀화 하는 과정을 래스터화Rasterization이라고 설명드린 바 있습니다. 즉, 모델의 좌표데이터를 받아서 픽셀의 색상값을 결정하는 것입니다. 각 픽셀의 색상값은 2D 배열로 이루어진 프레임 버퍼에 저장하였다가 화면에 송출하는데, 연속적인 좌표데이터를 이산적인 픽셀값으로 변환하는 방법을 살펴보려고 합니다.

Scan conversion

모델을 구성하는 2가지 기본 primitives(line, polygon)의 Rasterization 방법입니다.
선분Line의 경우 아래 방법을 이용해 그리며,

• DDA, Ditigal differntial analyzer
• Bresenham's algorithm

다각형 polygon의 경우 아래 방법을 이용해 다각형내부를 채웁니다.

• Inside/outside test: odd/even parity check, winding rule

선분의 Scan Conversion - DDA

래스터화는 프로젝션 이후에 하는 일입니다. 즉 이미 2D 좌표값이기 떄문에 선분도 2차원상의 선분입니다. 다만 프로젝션후의 좌표값은 실수값으로 연속되어있기 떄문에, 몇가지 가정을 하고 설명을 해보겠습니다.

• 선분의 끝점은 정수 좌표값 상에 있다.
• setPixel(x,y) 함수가 구현되어있다고 가정한다. (x, y 좌표가 주어지면 해당 좌표의 픽셀값이 저장되는 함수)

DDA란 미분방적식의 수치적인 해를 구하는 것을 의미합니다. 아주 간단히 말하면, 선분이 지나가는 픽셀을 찾아내는 것입니다.
우리는 기울기가 a인 직선 y=0.5x 을 픽셀상에 그리려고 한다면. 첫번째 픽셀 x=1일때 y=0.5, x=2일때 y=1, x=3일때 y=1.5일 것입니다. 픽셀의 좌표는 정수로만 이루어져있으므로, 함수의 y 값을 반올림해서 2D 픽셀에 나타내면 아래와 같이 나타낼 수 있을 것입니다. (@: 색칠된 픽셀, _ :색칠 안된 픽셀)

_ _ _ _ @ @
_ _ @ @ _ _
@ @ _ _ _ _

그런데 만약 기울기가 가파르다면, 예를들어 y=3x라면 x값에 따라 y 값을 결정하면 다음처럼 띄엄띄엄 그려지게 될 겁니다.

_ _ _ @
_ _ _ _
_ _ _ _
_ _ @ _
_ _ _ _
_ _ _ _
_ @ _ _
_ _ _ _
_ _ _ _
@ _ _ _

이때는 y 값을 1씩 증가시키면서 그에 따른 x 값을 구하는게 낫겠죠.
_ _ _ @
_ _ @ _
_ _ @ _
_ _ @ _
_ @ _ _
_ @ _ _
_ @ _ _
@ _ _ _
@ _ _ _
@ _ _ _

즉 기울기의 절대값이 1이하인 경우는 x 값을 1씩, 기울기 절대값이 1 이상인 경우는 y값을 1씩 증가시키면서 해당되는 픽셀을 찾아내는 방법입니다.

float m= (y2-y1)/(x2-x1)
float mInv = 1/m;
int x = 0;
int y = 0;
if(abs(m) < 1)
{
    for( x=x1; x<=x2;++x){
     y+=m;
     setPixel(x, round(y));
    }
}else{
for( y=y1; y<=y2; ++y){
     x+=mInv;
     setPixel(round(x), y);
    }
}

선분의 Scan Conversion - Bresenham's algorithm

DDA의 문제점은 뭘까요?
DDA는 floating point operation이 들어갑니다. 계속해서 기울기 값을 더해주기 때문이죠. 컴퓨터상에서 floating point 계산이 많아지면 아주 작은 에러값이 계속 누적되어 의도치 않은 결과가 나오기도 합니다. 이런 단점을 해결하기 위한 방법이 Bresenham 알고리즘입니다.
기울기 m의 절대값이 1보다 작은 경우만 생각하기로 하겠습니다. 기울기가 1이상인 경우에는 대칭적symmetric으로 적용하면 됩니다. 그리고 모든 픽셀의 중심이 half integer라고 가정하겠습니다. 우리는 지금 선분을 그리고 있기 때문에, 만약 하나의 픽셀값(x,y)이 색칠하기로 결정된다면, 다음 픽셀은 둘 중에 하나로 결정됩니다. 같은 높이(x+1, y)의 픽셀을 색칠하거나, 그보다 위 픽셀(x+1,y+1)값을 색칠하거나.

모든 픽셀에 대해서 이를 결정하기 위해서 우리는 세가지를 알아야 합니다.
선분의 양 끝점을 (x1,y1)(x2,y2)라 하고, dx=x2-x1, dy=y2-y1이라 하면,

1. p_(k) 값에 따른 픽셀 선택 결과:
   • p_(k) < 0 이면 같은 높이의 픽셀을 색칠
   • p_(k) > 0 이면 다른 높이의 픽셀을 색칠
2. p_(k+1)값: p_(k)에 의해 결정됨.
   • p_(k) < 0 이면 p_(k+1)=p_(k)+2dy-2dx,
   • p_(k) > 0 이면 p_(k+1)=p_(k)+2dy
3. p_0 값: 위 규칙을 적용하기위한 첫번째 픽셀의 값
   • p_0= 2dy-dx

첫번째 픽셀을 계산하고나면 1,2번에 의해 연쇄적으로 다음 계산을 할 수 있게 되고, 이 계산들은 모두 정수값 계산으로만 이루어져있기 때문에 floating poing 연산을 피할 수 있습니다.

다각형의 Scan Conversion

다각형polynomial은 세개 이상의 정점vertices, 그를 연결하는 선분edge로 이루어져있습니다. 다각형은 여러 종류로 나눌 수 있습니다.

• 볼록 다각형 convex (e.g. 삼각형) vs 오목 다각형 non-convex (e.g. 별모양)
  이 둘의 구분은 다각형 내부에 임의로 두 점을 잡았을 때, 두 점을 연결하는 선분이 언제나 다각형 내부에 있다면 볼록 다각형이고, 그렇지 않은 경우가 하나라도 존재한다면 오목 다각형입니다.
• simple (겹치는 edge가 없는 경우) vs non-simple (edge가 서로 crossing 하는 경우)
• general vs degenerate (colinear: 같은 직선에 세개 이상의 정점이 있는 경우, duplicated vertices: 두개 이상의 정점이 겹쳐있는 경우)
  이런 degenerate 케이스들은 수치적 에러때문에 생기기도 합니다.

이런 다각형을 래스터화 하기 위해서는 어떻게 해야 할까요? 다각형의 안쪽과 바깥쪽을 구분해서 안쪽이라고 판단된 픽셀은 색칠하고, 바깥으로 판단된 픽셀은 색칠하지 않으면 됩니다. 즉 in/out 테스트가 필요합니다. 이 테스트는 두가지 방법으로 가능합니다.

• odd-even test : 임의의 픽셀에서 ray를 쏘아서 지나가는 edge가 홀수개면 내부, 짝수개면 외부. 정점의 순서sequence는 상관 없음.
• winding test(=non-zero): 각 정점의 순서를 매김. 임의의 픽셀에서 ray를 쏘았을 때, 지나가는 edge가 반시계방향이면 +1, 시계방향이면 -1을 해서, 최종 결과가 0이 아니면 내부.

지난 포스팅에서 간단히 설명드린 그래픽스 파이프라인 중에서 프로젝션 이후, 모델을 래스터화 하는 방법을 살펴보았습니다.

아래 내용은 차차 업로드 될 예정입니다.

4. 2D 기하변환, 2D Geometric Transformations

5. 3D 기하변환, 3D Geometric Transformations

6. 3D Viewing

7. Clipping Algorithm

8. Illumination Models and Surface-Rendering Methods

9. Ray Tracing

10. Texture Mapping

11. Visible Surface Determination

12. 3D Object Representation