2차원 그래픽스 다각형 영역과 채우기

영역 및 다각형 채우기

영역의 특성과 채우기 방식

영역은 같은 색상값을 갖는 이웃한(adjacent) 픽셀들의 집합으로 정의됩니다. 이 때  이웃한 픽셀간의 연결방식에는 두 가지가 있습니다. 4방향 연결방식에서는 상하좌우 4방향으로 이웃한 픽셀들만 연결 되었다고 간주하며 8방향 연결방식에서는 한 필셀로부터 8방향으로 이웃한 모든 픽셀을 연결되었다고 간주합니다.

왼쪽을 4방향 연결방식 오른쪽을 8방향 연결방식이라 하는데 이러한 영역의 연결방식에 따라서 실제 영역에 대한 판이 달라질 수 있습니다. 래스터 출력에서 영역의 경계 픽셀과 영역 내부의 픽셀을 구분해야 하는 경우에는 연결 방식을 각각 서로 다르게 적용해야 합니다. 즉 경계 픽셀을 8방향 연결 방식으로 그리면 내부 영역 픽셀은 반드시 4방향 연결 방식으로 채우기를 해야하며 경계 픽셀을 4방향 연결 방식 으로 그릴 경우에는 일반적으로 내부 픽셀은 8방향 연결 방식의 채우기를 수행하게됩니다.

경계 픽셀을 8방향 연결방식으로 그리면 내부 영역 픽셀은 반드시 4방향 연결 방식으로 채우기를 해야하며, 경계 픽셀을 4방향 연결 방식으로 그릴 경우에는 일반적으로 내부 픽셀은 8방향 연결방식의 채우기를 수행합니다.

위와 같은 그림에서 Start Position 위치에서 채워 나간다고 했을때 위 그림의 검은색은 4방향 연결 방식의 경계로 되어있습니다. 저기서 만약 4경계 방향으로 채우게 된다면 오른쪽 위쪽에 공간을 인지하지를 못하게 됩니다. 따라서 8방향 연결 방식으로 채워나가야 합니다. 영역 및 다각형 채우기 알고리즘은 시드(Seed) 채우기 방식의 알고리즘과 사각형 주사변환 방식의 알고리즘으로 구분합니다.

시드채우기(Seed Fill) 방식

범람채우기(Flood Fill)은 알고리즘에서 이웃 픽셀들을 찾아나갈 때 시드 픽셀과 같은 색상의 값을 가지는 픽셀을 내부 픽셀로 판단하고 채웁니다. 또 경계채우기 (Boundary Fill) 방식은 이웃 픽셀을 검사할 때 별도로 주어진 경계 픽셀의 값이 나올 때 까지 채워나가게됩니다.

다각형 내부 판단 규칙

다각형  주사변환 방식에서 다각형에 대한 표현이 벡터 데이터로 주어지면 내부를 판단 할 수 있습니다. 하지만 하나일때는 간단하지만 여러개 이거나 복잡한 도형이 주어졌을 때 문제가 생기게 되는 데 이 때 다각형 내부 영역에 대한 판단 규칙중 가장 간단한 방법으로 홀짝 규칙(Even-Odd Rule)이 있습니다.

가로선을 그엇을 때 짝수번째(0도 짝수) 만나는 면을 외부로 홀수 번째 만나는 면을 내부로 판단하게 됩니다. 이 규칙은 간단하게 구현은 되지만 겹친부분이 항상 외부로 되어버리는 문제가 있습니다. 이를 해결하기 위한것이 다각형에서 엣지의 방향을 고려한 접기 횟수 규칙(Nonzero Winding Rule)입니다.

선을 하나 그은 다음 0부터 카운트를 시작합니다. 그리고 처음 통과한 곳은 1을 더해지고 바로 이전에 통과한 엣지의 벡터와 방향이 같으면 1을 증가 방향이 다르면 1을 감소 시켜서 0인 부분을 외부로 1이상인 부분을 내부로 보게됩니다. 따라서 왼쪽의 경우는 가운데가 비어지며 오른쪽은 가운데가 내부로 판단되게 됩니다.

다각형 주사변환(Polygon Scan-Conversion) 방식

일반적으로 대표적으로 사용되는 Y-X 다각형 주사선 알고리즘입니다.

• 용어
  
  
1. AEL(Ative Edge Line) : 알고리즘 내에서 이를 활성화된 에지의 목록
2. EL(Edge Line) : 다각형의 전체 에지의 목록

X-Y 다각형 주사선 알고리즘은 다음과 같은 방법을 가지게 됩니다.

1) 초기화

각 에지들을 y 좌표의 최소값 순서로 정렬하여 Edge Line(EL)을 구성합니다.

Edge List의 데이터는 의 형태로 구성됩니다.

이며, 초기 의 값은 이고 입니다.

dir은 에지의 방향으로 up 또는 down으로 표현합니다.

2) 매 주사선 에서 다음을 수행합니다.

2-1) AEL을 갱신합니다.
       AEL에서 인 에지를 삭제하고 EL에서 인 에지를 AEL로 이동합니다.

단, AEL과 EL에 더 이상의 에지가 없으면 종료합니다.

2-2) AEL에서 각 에지의 교차점을 계산합니다.

2-3)교차점 x값을 정렬한 후 한 쌍을 결정하여 그 사이를 채웁니다. 방향을 고려하지 않는 경우는 x 좌표값 순서대로 짝을 결정합니다. 방향을 고려하는 경우는 dir 값이 up과 down의 쌍이 되도록 짝을 결정합니다.