Filling Polygons

다각형 채우기.

 

다각형은 3가지 타입이 있다.

1. Simple Convex: 볼록 다각형

2. Simple Concave: 오목 다각형

3. Non-simple(self-intersection): 내부 교차된 다각형

 

이런 다각형들의 경계선의 내부를 채우는 알고리즘을 설계해 보자.

 

몇가지 문제들:

다각형의 윗쪽,오른쪽 경계선은 픽셀을 켜지 않는다.

만약 윗쪽,오른쪽 경계선의 픽셀을 키게되면, double-fill문제가 발생할 수 있는데,

예를들어 두 사각형이 변을 맞대고 붙어있을 때, ① 맞닿은 부분이 깜빡거리는 flicker현상이 발생할 수 있고,

②두번 그리는것 자체가 비효율적이기도 하다.

 

그러므로 공유엣지에 대한 룰로, 오른쪽 수직엣지, 윗쪽 수평엣지는 그리지 않는다.

---

다각형을 어떻게 채울까?

 

주사선(scan line)과 다각형의 경계선의 교차점은 짝수개로 생기게 되는데, 그 점들 사이를 칠하면 된다.

이 때, scan line상에서 이웃하는 픽셀의 모임을 span이라고 한다.

 

Coherence:

-Spatial coherence: 공간적 일관성. 한 span 내에서 픽셀들은 동일한 속성을 가진다.

-Edge coherence: scanline과 이웃한 scanline 은 일관성이 있음..

 

---

Filling the spans

 

span 채우기는 아래 세 스텝으로 이루어진다

1. 다각형의 edge와 scanline의 교차점을 찾는다.

2. 교차점의 x좌표 기준으로 sort 한다.

3. 다각형의 내부로 판정되는 pixel을 채운다.

 

여기서 몇가지 질문이 생긴다

1. 교차점을 어떻게 효율적으로 찾을것인데? => 일관성을 이용

2. 픽셀이 도형 내부인지 외부인지 어떻게 판별할건데?

=> Parity(Odd-Even) Rule을 사용한다.

 

scanline을 따라가면서, 교차점을 만나면 패리티값을 바꾼다.

예를들어, 패리티값을 even(0)으로 시작했을 때, 스캔라인을 따라가면서 교차점을 처음 만나면 odd(1)로 바뀌고,

또 교차점을 만나기 전까지는 odd(1)을 유지한다. 또 교차점을 만나면 다시 even(0)으로 바뀐다. 여기서 odd(1)인 부분이 도형 내부가 된다.

 

그런데, 교차점의 x좌표가 정수가 아니면.. 해당좌표의 왼쪽것을 택할것인가 오른쪽것을 택할것인가?

이 때는 완전히 도형 내부인 픽셀을 선택해야한다.

시작교차점이라면 round up, 끝 교차점이라면 round down 해야한다.

 

그런데, 꼭짓점은 어떻게 할까?

꼭짓점에는 두 선분이 존재하는데,

y라벨을 판별해야 한다.

각각 선분에 대하여 해당하는 꼭짓점이 Ymax인지, Ymin인지 확인하자.

Ymin일 때만 패리티를 갱신하면 된다.

이 때, 두 선분의 y 라벨이 모두 Ymin이라면 두번 패리티값이 갱신되어야 한다.

또한, 수평선인 경우에는 판별할 수 없으므로 나머지 한 선분만 보고 판별하면 된다.

---

scan line과 교차되는 엣지의 좌표를 얻기 위해서는

연립방정식을 풀어야 하는데,

엣지의 일관성: Edge Coherence를 이용하면 연립방정식을 풀지 않고도 좌표를 구할 수 있다.

 

Xi+1 = Xi + 1/m 

Yi+1 = Yi + 1;

 

x좌표는 기울기의 역수만큼 증가, y좌표는 1 증가한다.