Rasterization

 

Rasterization

 

 

 

Rasterization

Primitive Assembly 과정에서 Primitive을 그리는데, 이 때 어떤 pixel이 Primitive에 속하는지 계산하는 것.

(OpenGL 에서는 이 과정을 알아서 해준다)

그래서 pixel에 들어가는 Fragment의 list를 뽑아낼 수 있다.

 

 

 

 

Line Algorithm

 

그렇다면 Line에 속해있는 pixel들은 어떻게 계산되어질까?

Line을 Rasterization하는 알고리즘이 존재한다.

 

 

1. DDA Algorithm

x가 1만큼 변할 때마다 y는 m만큼 변화시켜준다.

그러면 x는 정수단위이고, y는 부동소수점단위이기 때문에 반올림 시켜준다.

이를 수도코드로 표현하면 다음과 같다.

for(ix = x1; ix <= x2; ix++){
    y += m;
    write_pixel(x, round(y), line_color);
}

 

그런데 문제는 m이 1보다 크면 x가 1증가할 때 y는 더 많이 증가해버린다.

그래서 m이 1보다 클 때, x와 y의 규칙을 바꿔준다.

y가 1증가할 때, x는 1/m 증가시켜준다.

이렇게 Line을 Rasterization했다.

 

 

2. Bresenham Algorithm

그런데 DDA 알고리즘은 각 pixel에 float 연산을 사용해야 한다. 옛날에는 정수연산보다 10~100배 정도 느렸다고 한다.  float 연산말고 정수연산을 고려한 것이 Bresenham 알고리즘이다.

 

기울기가 0 <= m <= 1 라고 하자.

그러면 현재 pixel은 (i+1/2, j+1/2) 이라면, 다음 pixel은 (i+3/2, j+1/2) 또는 (i+3/2, j+3/2) pixel을 선택하면 된다.

그래서 오른쪽의 두 pixel 중에 어떤 것을 선택할 지 정해줘야 한다.

 

여기서 a+b=1 이고,

Δx(b-a) = d 라고 하고,

d > 0 => 위 pixel 로.

d < 0 => 아래 pixel 로.

이렇게 다음 pixel을 정해준다.

(직선의 방정식과 a와 b를 치환해서 계산해보면 d는 정수임을 알 수 있음)

a = j+3/2 - y

b = y - j+1/2

 

여기서 a와 b는 float 인데, Δx(b-a) 에서 b-a 연산을 어떻게 정수연산으로 할까?

x축에서 k번째 d를 가정했을 때, 다음과 같이 정리할 수 있다. (자세한 계산과정은 생략)

dk+1 = dk + 2Δy, if dk < 0

dk+1 = dk + 2(Δy - Δx), otherwise

 

정리하면 d를 음수인지 양수인지 계속 검사하면서 올라갈지 그대로 갈지 정하는 것이다. 이렇게 다음 d도 계산해 나가면서 pixel에 line을 그려나가는 것이다.

 

 

(참고)

이 line 알고리즘은 두께가 1인 line에서 사용된다. 그런데 요즘엔 두께가 1이 아닌 line을 많이 그려서 잘 사용되지 않는다고 한다.

 

 

 

 

 

Fill

색을 칠해주기 위해 frame buffer의 pixel들을 다각형 내부인지 외부인지 검사할 필요가 있다.

odd-Even fill, scan-line fill, flood fill 등의 방법이 있다.

 

 

1. odd-Even fill

odd-Even fill은 Winding Number를 이용한다.

 

왼쪽에서 점까지 가는데, 부딪힌 edge가 올라가는 것이면 +1, 내려가는 것이면 -1을 해준다.

점에 도달했을 때, 0이 아니면 도형 안에 포함되어 있음을 알 수 있다.

이 때, odd-Even fill은 홀수인 것만 칠해주는 등의 방법으로 색을 넣는다.

 

삼각형이 아닌 다각형에서는 더 복잡해진다. 되도록 내각이 항상 180˚보다 작은 convex한 것을 사용하자.

만약 nonconvex 다각형이라면 삼각형으로 만들자.

 

 

2. Scan Line fill

scan line과 edge들의 교점들을 찾아준다.

 

교점들을 scan line 기준으로 sort.

1~2 색칠

3~4 색칠

5~6 색칠

...

이런 식으로 삼각형 내부를 칠해준다. (삼각형 이외의 다각형은 더 복잡해진다. 삼각형 쓰자.)

 

그리고 삼각형 내부에서도 서서히 어두워지는 부분이 존재해야 한다.

즉, 끝에 세 점에 대한 정보로 중간 점에 대한 정보를 얻어야 할 경우가 많다.

그럴 땐 두 점들의 비례식으로 삼각형 내부의 점들의 색을 정해주면 된다.

 

 

3. Flood fill

색을 칠하는 방법 중 제일 단순한 방법이다.

색을 칠할 영역이 주어지면 그 영역을 칠하는 것이다.

즉, 어떤 다각형의 edge가 정해지면은 edge 내부를 칠하는 것이다.

 

배경색(white) 과 그리는 색(black) 이 있다고 하자. 

이 때 안쪽 pixel의 시작점(seed point)을 찾을 수 있다면 이웃한 점들을 찾아가면 된다.

수도코드는 다음과 같다.

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);
    }
}

 

 

 

 

 

 

 

[참고]

Interactive Computer Graphics: A Top-Down Approach with Shader-based OpenGL 6th edition / 저자: Edward Angel, Dave Shreiner / 출판사: Pearson Education