Filling Polygons (다각형 내부 채우기 알고리즘)

이번 포스트에서는 Filling Polygons Algorithm(다각형 내부 채우기 알고리즘)에 대해서 다루도록 하겠습니다.

 

먼저 다각형의 3가지 형태에 대해 소개하겠습니다.

• Simple Convex (단순 볼록형)
• Simple Concave (단순 오목형)
• Non-simple(self-intersection) (비단순-자기교차형)

다각형을 그릴 때 발생할 수 있는 대표적인 오류가 바로 "double-fill"입니다. 

double-fill란 무엇인가?

double-fill은 말그대로 두 번 채웠다는 의미입니다. 즉, 인접하는 다각형을 채울 때 그 인접하는 변이 서로 겹쳐 색을 두번 칠하게 되는 상황을 말합니다. 이는 비효율적이면서도 만약 두 다각형의 색상이 다르다면 이상한 색이 색칠될 수도 있습니다. 

 

따라서 위와 같은 경우를 방지하기 위해서 다각형을 컴퓨터 그래픽스 상에서 표현할 때에는 윗 픽셀 또는 우 픽섹을 제외해서 표현합니다.

이어서 Filling Polygons Algorithm에 대해서 살펴 보겠습니다.

 

Filling Polygons Algorithm

Filling Polygons, 즉 다각형 채우기 알고리즘은 단지 내부에 해당되는 픽셀의 위치를 찾아서 그것들을 채우기만 하면 됩니다. 그러기 위해서 먼저 경계선과 스캔라인의 교차점을 먼저 찾아야 합니다.(교차점은 항상 짝수) 그런 다음에 그 교차점의 내부 영역을 채우면 됩니다. 우리는 그 영역을 span이라 합니다.

또한 이러한 픽셀들은 서로 이웃한 픽셀과 일관된 성질(Coherence)을 가지고 있습니다. 여기에는 크게 2가지로 나눌 수 있습니다.

• Spatial coherence(공간적 일관성): 하나의 span 에서 존재한 모든 픽셀(서로 이웃)들의 성질은 같다.
• Edge coherence(엣지의 일관성): 서로 이웃하는 scan line에서 발생하는 교차점의 성질은 같다.

우리는 위에 제시된 성질을 이용해서 좀 더 최적화된 알고리즘을 작성할 수 있습니다. 그럼 이제 span을 어떤 식으로 채워야 할지에 대해 다루겠습니다.

 

span을 채우는 단계는 크게 3가지로 나뉠 수 있습니다.

1. 다각형의 모든 엣지와 스캔 라인의 교차점을 찾는다.
2. 교차점의 x좌표 기준으로 올림차순으로 정렬한다.
3. 다각형 내부에 있는 교차점 쌍 사이의 모든 픽셀을 채운다.

다각형의 픽셀이 교차점의 내부나 외부에 있는지를 판별하는 방법으로는 "Parity (Odd-Even) Rule"이 있습니다.

 

Parity (Odd-Even) Rule

Parity Rule은 bit를 이용해서 Parity가 가지는 값이 홀수인지 짝수인지를 바탕으로 내부 픽셀인지, 외부 픽셀인지 판별합니다. (odd이면 내부 픽셀, even이면 외부 픽셀)

[그림 자료 출처: Introduction to Computer Graphics, Foley]