브레젠험 알고리즘

* 이득우의 게임수학 책 내용을 바탕으로 작성된 글입니다.

 

브레젠험 알고리즘이란?

정수만 사용해 효율적으로 화면에 선분을 그리는 알고리즘이다.

 

브레젠험 알고리즘 원리

위 그림은 스크린 좌표계를 8등분한 화면이다.

1팔분면은 [0,45]도의 범위를 가지며 해당영역에 포함된 선분은 기울기가 1을 넘어설 수 없다.

비슷한 특징으로 1, 4, 5, 8팔분면에 포함된 선분의 기울기 절대값은 1을 넘어설 수 없다.

 

주어진 선분이 1팔분면 영역에 존재할 때를 시각화해보면 아래와 같다.

각각의 정사각형을 픽셀로 생각하여 $\overline{P1P2}$가 포함된 픽셀을 채워주면 된다.

각각의 픽셀들의 좌표를 중점으로 설정하고, P1이 포함된 픽셀로부터 진행방향을 분석해보자.

1) P1이 포함된 픽셀$(x_{0},y_{0})$를 채우고 선분이 포함된 다음 픽셀을 이동해야 한다.

2) 해당 선분은 1팔분면 영역에 존재하는 선분으로 진행방향은 현재 픽셀좌표가 $(x,y)$ 일때 $(x+1,y)$ 이거나 $(x+1,y+1)$이다.  

3) 2번에서 알 수 있는 사실은 1팔분면 영역에서 선분을 표현하는 픽셀의 진행방향에서 x는 항상 1씩 증가하고 y는 유지되거나 1이 증가됨을 알 수 있다.

4) 위 그림에서 $(x_{0},y_{0})$ 픽셀은 어디로 이동해야할까? 정답은 다음픽셀의 후보인 두 픽셀의 중점(그림에서 보라색 X표시)을 설정하고, 판별식을 통해 다음픽셀을 알아낼 수 있다.

5) 4번에서 설명한 초기 판별식은 직선의 방정식을 활용하여 유도할 수 있다. 

$y = \frac{h}{w}x+b$ 이 식에서 $b=y_{0}-\frac{h}{w}x_{0}$ 임으로 $y=\frac{h}{w}x+y_{0}-\frac{h}{w}x_{0}$이 성립한다.

위 직선의 방정식에 설정한 중점의 x를 대입하여 나온 y값이 중점의 y값 미만일 경우(이상일 경우는 아래픽셀로 이동) 오른쪽으로 수평이동함을 알 수 있다.

6) 5번에서 설명한 초기 픽셀$(x_0,y_0)$에서 오른쪽 수평이동해야하는 수식을 정리하면 아래와 같다.

$\begin{align} 
&\frac{h}{w}x+y_0-\frac{h}{w}x_0 < y_0+0.5 \\
&hx+wy_0-hx_0 < wy_0+0.5w \\ 
&h(x-x_0)-0.5w < 0 \\ 
&2h(x-x_0)-w < 0, x에\,중점의\,x값(x_0+1)대입\\ 
&2h-w<0
\end{align}$

그림으로 표현하면 회색직선이 두 점(초기 픽셀, 다음 픽셀후보인 두 픽셀의 중점)을 지나는 직선이다.

$\overline{P1P2}$가 중점(보라색 X표시)의 x값일때 y값이 중점의 y값 미만임으로 회색으로 색칠된 영역에 존재하며, 선분을 표현하기위해 현재픽셀은 오른쪽으로 수평이동해야 함을 알 수 있다.

7) 현재 픽셀에서 다음픽셀로 이동할 때 판별식도 변한다.

우선 오른쪽으로 수평이동(dy=0, dx=1)할 때 다음 판별식은 현재 판별식에 +2h가 되는 사실은 6번에서 정리한

$2h(x-x_0)-w < 0$ 을 통해 쉽게 이해할 수 있다.

오른쪽 아래로 이동할 때의 다음 판별식은 +2h 뿐만이 아니라 -2w가 추가 되는데 이는 6번 수식 우항에 +1을 추가후 식정리를 해봄으로 알아 낼 수 있다.

8) 1팔분면뿐만이 아니라 4, 5, 8팔분면에서도 진행방향만 다를뿐 알고리즘은 동일하게 작동한다. 2,3,6,7 팔분면은 x,y축을 뒤집어 적용하면 된다.

9) $\overline{P1P2}$에서 $P1=(x_1,y_1), P2=(x_2,y_2)$일때 시간복잡도를 분석해보면 픽셀이동횟수$max(\left|x_1-x_2 \right|,\left|y_1-y_2 \right|)$이고, 다음픽셀 판별연산은 상수시간이 소요되니 $O(max(h,w))$인 것 같다.

 

느낀점

기하 알고리즘은 실수연산으로 인해 정밀도, 분수꼴로 나타낼 때 오버플로우 등등 골치가 아픈경험이 많았으나 해당 알고리즘은 정수연산으로 인해 간단명료 한 것이 장점인 것 같다. 연산시간 자체도 선형시간이라 고해상도에서도 끄닥없을 것 같다(?)