다각형 채우기

다각형(Polygon)은 꼭지점(vertex)과 그들을 잇는 모서리(edge)로 이루어져 있습니다. 꼭지점과 모서리를 이용해 다각형의 모서리 안쪽을 채우는 몇가지 알고리즘들이 존재합니다. 예를 들어 플러드 필(flood fill) 알고리즘은 다각형의 모서리가 그려져 있을 때 다각형 안쪽의 한 점부터 시작해 모서리를 만날 때까지 반복적으로 채워나가는 방법입니다. 이 글에서는 다각형을 색칠하는 또 다른 방법인 스캔라인 알고리즘을 알아보겠습니다.

스캔라인 채우기

아래 그림과 같이 $x$ , $y$ 좌표 평면에 다각형을 그린다고 하겠습니다.

이 때 다각형의 높이 범위에 포함되는 $y$ 를 scan line 이라 한다면 다각형의 4개의 모서리가 scan line 과 만납니다.

이 때 색칠해야할 부분은 scan line 이 만나는 첫번째 모서리와 두번째 모서리 사이, 세번째 모서리와 네번째 모서리 사이입니다.

스캔라인 알고리즘은 이 원리를 이용해 $y$ 값을 늘려가며 다각형의 안쪽을 채워나갑니다.

알고리즘의 순서

global edge table 초기화

scan line 초기화

active edge table 에 현재 scan line 에 대응하는 모서리 저장, 수정

현재 scan line 에 대해 픽셀 채우기

global edge table 과 scan line 초기화

스캔라인 알고리즘의 원리는 간단하지만 전처리 과정이 필요합니다. 우선 채우기의 판단의 기준이 될 모서리들을 저장해두어야 합니다. 이 때 전체 모서리들을 저장할 global edge table 과 현재 scan line 이 만나는 모서리들만을 저장할 active edge table 을 따로 두겠습니다. scan line 이 변경될 때마다 global edge table 에서 scan line 과 만나는 모서리들을 꺼내 active edge table 에 넣는 식입니다.

한편 scan line 과 평행한 모서리들은 저장하지 않습니다.(모서리의 두 꼭지점의 $y$ 값이 같은 경우를 말합니다.) 아래 그림과 같이 scan line 에 평행한 모서리는 채우기의 판단에 영향을 미치지 않기 때문입니다.

모서리는 각 꼭지점의 $x$ , $y$ 성분을 이용해 다음과 같이 저장됩니다.

min $y$	모서리의 두 꼭지점 중 $y$ 값이 더 작은 점의 $y$
max $y$	다른 한 점의 $y$ 값
$x$	$y$ 값이 더 작은 점의 $x$ 값
slope	모서리의 기울기의 역수 $\frac{dx}{dy}$

모서리의 기울기가 아닌 그 역수를 저장하는 이유는 이후 알아볼 예정입니다.

global edge table 은 저장된 모서리들을 min $y$ 의 오름차순, min $y$ 의 값이 같을 경우 x 에 대해 오름차순으로 정렬합니다. 이는 현재 scan line 에 대해 global edge table 에서 active edge table 로 모서리들을 이동시킬 때의 효율을 위함입니다.

알고리즘은 scan line 값을 global edge table 의 첫번째 모서리의 min $y$ 값으로 초기화 합니다. global edge table 의 정렬을 고려하면 scan line 의 초기값은 모든 모서리를 통틀어 가장 작은 min $y$ 값입니다. 이후 scan line 의 값을 1씩 늘려가며 나머지 알고리즘의 프로세스를 반복합니다.

active edge table

scan line 이 설정되면 global edge table 에서 min $y$ 가 scan line 과 같은 모서리들을 꺼내 active edge table 에 저장합니다. 그리고 max $y$ 가 scan line 과 같은 모서리들은 제거합니다. active edge table 의 추가와 삭제 과정이 끝나면 모서리들은 $x$ 에 대해 다시 정렬됩니다. $x$ 값이 오른쪽으로 갈수록 증가한다고 할 때 scan line 과 모서리들의 만나는 순서가 중요하기 때문입니다. 앞서 global edge table 을 정렬할 때와 다른 점이 있다면 active edge table 은 scan line 과 만나는 모서리만을 포함하므로 min $y$ 에 대해서는 신경쓰지 않습니다.

active edge table 모서리들의 $x$ 값은 매 scan line 마다 변경됩니다. 따라서 매번 재정렬이 필요합니다. $x$ 값이 바뀌는 것에 대해서는 직선의 방정식을 이용합니다.

\begin{aligned} y - y_0 = \frac{dy}{dx}(x - x_0) \\ x = \frac{dx}{dy}(y - y_0) + x_0 \end{aligned}

위 식에서 $y - y_0 = 1$ 이므로 $x = x_0 + \frac{dx}{dy}$ 입니다. 따라서 x += slope 와 같이 $x$ 에 기울기의 역수를 더해 현재 scan line 에 대응하는 $x$ 를 구해줍니다.

픽셀 채우기

매 scan line 마다 업데이트되는 active edge table 를 이용해 픽셀을 쉽게 칠할 수 있게 되었습니다. 이제 홀수번째와 짝수번째 모서리 사이의 픽셀만을 채우는 것을 고려해 보겠습니다. 여러 방법이 있지만 간단하게 플래그 역할을 할 변수를 하나 두겠습니다. active edge table 의 모서리들에 대해 루프를 만들고 홀수번째 모서리에 플래그를 1로 설정, 짝수번째에 0으로 설정해 오직 홀수번째와 짝수번째 모서리 사이에서만 픽셀을 칠합니다. 예를 들면 아래와 같습니다.

void     fill_line(active_edge_list, edge_count, scanline)
{
    int	flag;
	int		x;
    edge	cur;
    edge	next;

    cur = 가장 처음 모서리;
    next = 두번째 모서리;
    flag = 1;
    while (edge_count--)
    {
        if (flag)
        {
            scanline 이 홀수번째 모서리와 만나는 지점에 대해 픽셀 채우기

			x = cur.x;
            while (x < next.x)
			{
				짝수번째 모서리와 만나는 지점 이전까지 픽셀 채우기
                x++;
			}
        }
        cur = cur 의 다음 모서리;
        next = next 의 다음 모서리;
        flag ^= 1; (flag 에 대해 XOR 연산)
    }
}

스캔라인 채우기의 특징

스캔라인 채우기는 알고리즘의 특성상 다음과 같은 특징을 보여줍니다.

위와 같은 꼭지점에 대해서 픽셀은 채워지지 않습니다. 꼭지점의 $y$ 값과 같은 scan line 에 대해 두 모서리의 max $y$ 가 scan line 과 같으므로 두 모서리는 active edge table 에서 제거됩니다.

위와 같은 꼭지점에 대해서 픽셀은 채워집니다. 꼭지점의 $y$ 값과 같은 scan line 에 대해 두 모서리의 min $y$ 값이 scan line 과 같습니다. 픽셀은 홀수번째 모서리의 $x$ 이상, 짝수번째 모서리의 $x$ 미만까지 채워지므로 위와 같은 꼭지점에 대해서 픽셀은 채워집니다.

위와 같은 꼭지점에 대해서 픽셀은 채워지지 않습니다. 두 모서리 중 아랫 모서리의 경우 max $y$ 가 scan line 과 같으므로 active edge table 에서 제거됩니다. 윗 모서리는 active edge table 에 포함되지만 윗 모서리의 $x$ 값 미만까지만 픽셀이 채워집니다.

위와 같은 꼭지점에 대해서 픽셀은 채워집니다. 두 모서리 중 아랫 모서리의 경우 max $y$ 가 scan line 과 같으므로 active edge table 에서 제거됩니다. 윗 모서리는 active edge table 에 포함되고 $x$ 값 이상의 픽셀은 모두 채워집니다.

출처

hooni.net

스캔라인 채우기 (Scanline Fill)

다각형의 픽셀에 대해 색을 칠할지 여부를 판단하는 법

2019년 05월 26일

다각형 채우기