Bresenham's line algorithm

Bresenham's line algorithm - Wikipedia

Bresenham's line algorithm - Wikipedia

브레젠험 직선 알고리즘(Bresenham's line algorithm) (velog.io)

velog

 

이득우의 게임수학 하위 게시글임

---

Bresenham's line algorithm is a line drawing algorithm that determines the points of an n-dimensional raster that should be selected in order to form a close approximation to a straight line between two points. It is commonly used to draw line primitives in a bitmap image (e.g. on a computer screen), as it uses only integer addition, subtraction, and bit shifting, all of which are very cheap operations in historically common computer architectures. 

 

---

 

1962년도에 발표된 브레젠험 알고리즘은 정수만을 사용해 효율적으로 화면에 선분을 그려낼 수 있다. 브레젠험 알고리즘은 아래 그림과 같이 화면을 Octant-8등분 영역으로 구분한 후 각 영역별로 그려내는 방식을 사용한다.  스크린 좌표계에서는 y축이 아래로 향했으므로 회전의 방향은 시계 방향이 된다.

https://sulinep.blogspot.com/2020/06/blog-post.html

 

1 팔분면은 [0, $\frac{\pi}{2}$]의 범위를 가지는데 이 영역에서 직선을 그려보자

 

직선 그리기 ((0<|기울기|<=1))

위 그림과 같이 임의의 두 점을 지나는 직선의 방정식은 다음과 같다.

$$y = \frac{\Delta y}{\Delta x}x +b$$

 

위 식에 한 점을 대입해 b를 구하면 최종인 식은 다음과 같다.

$$y = \frac{\Delta y}{\Delta x}x + y_{1} - \frac{\Delta y}{\Delta x} x_{1}$$

 

 

$(x_{1}, y_{1})$ 에서 $(x_{2}, y_{2})$ 으로 가기 위해서 $(x_{1}, y_{1})$에서 수평((E))으로 이동하거나 한 칸 내려가는지((NE))를 판별해야 한다. 이 때 다음 픽셀의 위치를 판별하기 위해서 점A와 점B의 중단점인 $(x_{1} + 1, y_{1} + 0.5)$를 기준으로 한다. 그래서 브레젠험 알고리즘을 MIdpoint algorithm이라고도 부른다.

 

중단점인 $(x_{1} + 1, y_{1} + 0.5)$가 앞서 구한 직선의 방정식 $y = \frac{\Delta y}{\Delta x}x + y_{1} - \frac{\Delta y}{\Delta x} x_{1}$ 보다 아래에 있는지 아닌지를 판별하면 된다. 

$$\frac{\Delta y}{\Delta x}x + y_{1} - \frac{\Delta y}{\Delta x} x_{1} < y_{1} + 0.5$$

 

새로 구한 중단점이 직선보다 아래 있으면 수평으로 이동하고 같거나 위에 있다면 한칸 내려간다.

 

새로 얻은 픽셀에서 또다시 중단점을 구해 이 중단점의 위치를 직선의 방정식과 비교하여 픽셀을 구하는 과정을 $x_{1}$에서 $x_{2}$까지 반복하면 직선을 그려낼 수 있다. 이 과정을 좀 더 효율적으로 해보자.

 

$$\frac{\Delta y}{\Delta x}x + y_{1} - \frac{\Delta y}{\Delta x} x_{1} < y_{1} + 0.5$$

컴퓨터 계산에서 실수형 계산보다 정수형 계산이 더 값 싼 연산이므로 -cheap operations- 위 식을 이항시켜서 소수점을 없애고 단순화 해보자. 처음의 중단점 $(x_{1} + 1, y_{1} + 0.5)$ 을 통해 다음과 같은 초기 판별식을 얻을 수 있다.

$$D1 = 2\Delta y - \Delta x < 0$$

판별식이 0보다 크거나 같으면 수평이동하고 0보다 작다면 한 칸 내려가면 된다.

 

이때 중단점이 이동하는 경우는 두 가지 case가 있다.

1. 수평으로 이동$(1,0)$만큼 이동
2. 한 칸 내려감 $(1,1)$만큼 이동

초기 중단점에서 x좌표 m, y좌표가 n만큼 움직인다고 할 때  초기 판별식은 다음과 같아진다.

$$\frac{\Delta y}{\Delta x}(x_{1} + m) + y_{1} - \frac{\Delta y}{\Delta x} x_{1} < y_{1} + 0.5 + n$$

$$ \Delta y(x_{1} + m) - \Delta y \cdot x_{1} < ( 0.5 + n )\Delta x$$

$$m \Delta y < ( 0.5 + n )\Delta x$$

$$D(m, n) = 2m \Delta y - ( 1 + 2n )\Delta x < 0$$

 

case 1 인 경우 m += 1, n += 0 이다.

$D(2, 1) = 4 \Delta  y - \Delta x$

case 2 인 경우 m+= 1, n += 1 이다.

$D(2, 2) = 4 \Delta  y - 3\Delta x$

 

위 식들을 통해 우리는 수평으로 이동하면 초기 판별식에 $2 \Delta  y$만큼 더하고, 한 칸 내려간다면 초기 판별식에 $ 2\Delta  y - 2 \Delta  x$만큼 더한 다음 이 판별식을 다음에 찍을 점에 사용하면 된다는 것을 알 수 있다.

 

순서도로 나타내면 다음과 같다.

 

그렇다면 1팔분면을 벗어나 기울기의 크기가 1보다 큰 경우는 어떨까?

직선 그리기 ((|기울기| > 1))

기울기의 크기가 1보다 클 경우에는 앞서 1팔분면에서 그린 방법에서 x와 y를 반대로 하여 하면 된다. 앞선 경우에서는 x 값이 꾸준히 1씩 증가하는 반면 y 값은 1 이상 증가할 수 없었지만 이번 경우에는 반대로 y가 꾸준히 1씩 증가하는 반면 x 값은 1 이상 증가할 수 없다. 증가하는 변화량이 반대가 된 것이다. //기울기 역수로 생각하면 편함

따라서 이번 경우에서의 판별식은 다음과 같다.

$$D(m, n) = 2m \Delta x - ( 1 + 2n )\Delta y < 0$$ 

변화량이 서로 반대가 되면 된다. 따라서 최종적인 순서도는 다음과 같다.

이후 등장하는 팔분면에서의 기울기를 가지는 선분은 진행 반대만 반대일 뿐 기본 원리는 동일하다. 이러한 규칙을 파악하면 8분면에 모두 대응되는 알고리즘을 완성할 수 있다.