브레젠험 직선 알고리즘

**브레젠험 직선 알고리즘**(Bresenham's line algorithm)은 래스터의 n차원 직선이 두 점 사이의 직선에 대한 근사값을 형성하기 위해 선택되어야 하는 점들을 결정하는 선 그리기 알고리즘이다. 이는 역사적으로 일반적인 컴퓨터 아키텍처에서 매우 저렴한 연산인 정수 덧셈, 뺄셈, 비트 시프팅만을 사용하기 때문에 비트맵 이미지(예: 컴퓨터 화면)에 선 기본 도형을 그리는 데 일반적으로 사용된다. 이는 점진적 오류 알고리즘이며, 컴퓨터 그래픽스 분야에서 개발된 초기 알고리즘 중 하나이다. 원래 알고리즘을 확장한 중점 원 알고리즘은 원을 그리는 데 사용할 수 있다.

우 알고리즘과 같은 알고리즘은 계단 현상 제거를 지원할 수 있기 때문에 최신 컴퓨터 그래픽스에서 자주 사용되지만, 브레젠험 직선 알고리즘은 속도와 단순성 때문에 여전히 중요하다. 이 알고리즘은 플로터와 같은 하드웨어와 최신 그래픽 카드의 그래픽 처리 장치에 사용된다. 또한 많은 소프트웨어 그래픽스 라이브러리에서도 찾을 수 있다. 알고리즘이 매우 간단하기 때문에 최신 그래픽 카드의 펌웨어 또는 그래픽 하드웨어에 자주 구현된다.

오늘날 "브레젠험"이라는 명칭은 브레젠험의 원래 알고리즘을 확장하거나 수정한 알고리즘 계열에 사용된다.

## 역사
브레젠험 직선 알고리즘은 1962년 IBM에서 이 알고리즘을 개발한 잭 엘턴 브레젠험의 이름을 따서 명명되었다. 2001년에 브레젠험은 다음과 같이 썼다.

## 방법
right|300px|섬네일|브레젠험 직선 알고리즘 결과의 그림. (0,0)은 격자의 왼쪽 상단 모서리이고, (1,1)은 직선의 왼쪽 상단 끝이고, (11, 5)는 직선의 오른쪽 하단 끝이다.
다음 규칙이 적용된다.
* 왼쪽 상단은 (0,0)으로, 픽셀 좌표는 오른쪽 및 아래쪽 방향으로 증가한다 (예를 들어, (7,4)의 픽셀은 (7,5)의 픽셀 바로 위에 있다).
* 픽셀 중심은 정수 좌표를 갖는다.
선의 끝점은 (x_0,y_0) 및 (x_1,y_1)의 픽셀이며, 쌍의 첫 번째 좌표는 열이고 두 번째 좌표는 행이다.

알고리즘은 처음에 선분이 아래쪽과 오른쪽으로 가는 팔분원(x_0 \leq x_1 및 y_0 \leq y_1)에 대해서만 제시되며, 그 수평 투영 x_1-x_0은 수직 투영 y_1-y_0보다 길다(선은 1보다 작은 양의 기울기를 갖는다).
이 팔분원에서 x_0과 x_1 사이의 각 열 x에 대해 선의 픽셀을 포함하는 행 y(알고리즘으로 계산됨)가 정확히 하나 있는 반면, y_0과 y_1 사이의 각 행은 여러 래스터화된 픽셀을 포함할 수 있다.

브레젠험 알고리즘은 동일한 x에 대한 이상적인(분수) y에 가장 가까운 픽셀 중심에 해당하는 정수 y를 선택한다. 연속적인 열에서 y는 동일하게 유지되거나 1만큼 증가할 수 있다.
끝점을 통과하는 선의 일반 방정식은 다음과 같다.
:\frac{y - y_0}{y_1-y_0} = \frac{x-x_0}{x_1-x_0}.

열 x를 알고 있으므로 픽셀의 행 y는 이 양을 가장 가까운 정수로 반올림하여 구할 수 있다.

:y = \frac{y_1-y_0}{x_1-x_0} (x-x_0) + y_0.

기울기 (y_1-y_0)/(x_1-x_0)는 끝점 좌표에만 의존하며 미리 계산할 수 있으며, y_0에서 시작하여 반복적으로 기울기를 더하여 연속적인 정수 x 값에 대한 이상적인 y를 계산할 수 있다.

실제적으로 알고리즘은 y 좌표를 추적하지 않는데, 이는 x가 1씩 증가할 때마다 m = ∆y/∆x씩 증가한다. 알고리즘은 각 단계에서 오류 경계를 유지하며, 이는 (a) 선이 픽셀을 벗어나는 지점부터 (b) 픽셀의 상단 가장자리까지의 거리의 음수 값을 나타낸다.
이 값은 처음에 y_0-0.5로 설정되며(픽셀의 중심 좌표를 사용하기 때문에), x 좌표가 1씩 증가할 때마다 m만큼 증가한다. 오류가 0.5보다 커지면 선이 위쪽으로 한 픽셀 이동했고 y 좌표를 증가시키고 새 픽셀 상단으로부터의 거리를 나타내도록 오류를 조정해야 한다는 것을 알 수 있다. 이는 오류에서 1을 빼서 수행한다.

## 도출
브레젠험 알고리즘을 도출하기 위해서는 두 단계를 거쳐야 한다. 첫 번째 단계는 선의 방정식을 전형적인 기울기-절편 형태에서 다른 형태로 변환하는 것이고, 그 다음에는 이 새로운 방정식을 사용하여 오류 누적 아이디어를 기반으로 선을 그리는 것이다.

### 선 방정식
300px|섬네일|y=f(x)=.5x+1 또는 f(x,y)=x-2y+2=0
300px|섬네일|양수 및 음수 반평면

선의 기울기-절편 형태는 다음과 같이 쓰여진다.

:y = f(x) = mx + b

여기서 m은 기울기이고 b는 y 절편이다. 이것은 x만의 함수이기 때문에 수직선을 표현할 수 없다. 따라서 이 방정식을 x와 y 모두의 함수로 작성하여 어떤 각도의 선도 그릴 수 있도록 하는 것이 유용할 것이다. 선의 각도(또는 기울기)는 "rise over run" 또는 \Delta y/\Delta x로 표현될 수 있다. 그런 다음 대수적 조작을 사용하여

:
\begin{align}
y & = mx + b \\
y & = \frac{\Delta y}{\Delta x} x + b \\
(\Delta x) y & = (\Delta y) x + (\Delta x) b \\
0 & = (\Delta y) x - (\Delta x) y + (\Delta x) b
\end{align}


이 마지막 방정식을 x와 y의 함수로 만들면 다음과 같이 쓸 수 있다.

:f(x,y) := Ax + By + C = 0

여기서 상수는 다음과 같다.
* A = \Delta y = y_1 - y_0
* B = - \Delta x = - (x_1 - x_0)
* C = (\Delta x) b = (x_1 - x_0) b

그러면 선은 f(x,y) = 0인 곳에서 어떤 상수 A, B, C에 대해 정의된다. 즉, 선 위에 있지 않은 모든 (x,y)에 대해 f(x,y) \ne 0이다. 이 형태는 x와 y가 정수인 경우 정수만 포함한다. 왜냐하면 상수 A, B, C는 정수로 정의되기 때문이다.

예를 들어, 선 y=\frac{1}{2}x + 1은 f(x,y) = x - 2y + 2로 쓸 수 있다. 점 (2,2)는 선 위에 있다.

:f(2,2) = x - 2y + 2 = (2) - 2(2) + 2 = 2 - 4 + 2 = 0

그리고 점 (2,3)은 선 위에 있지 않다.

:f(2,3) = (2) - 2(3) + 2 = 2 - 6 + 2 = -2

그리고 점 (2,1)도 마찬가지이다.

:f(2,1) = (2) - 2(1) + 2 = 2 - 2 + 2 = 2

(2,1)과 (2,3)은 선의 반대편에 있으며 f(x,y)는 양수 또는 음수로 평가된다는 점에 유의하라. 선은 평면을 반으로 나누며, f(x,y)가 음수인 반평면을 음수 반평면, 다른 반평면을 양수 반평면이라고 할 수 있다. 이 관찰은 나머지 도출에서 매우 중요하다.

### 알고리즘
시작점은 선 위에 있다.

:f(x_0, y_0) = 0

이는 선이 정수 좌표에서 시작하고 끝나는 것으로 정의되기 때문만은 아니다(비정수 끝점을 갖는 선을 그리려는 것도 전적으로 합리적이다).

300px|섬네일|파란색으로 표시된 후보 점 (2,2)과 녹색으로 표시된 두 후보 점 (3,2) 및 (3,3)

기울기가 최대 1이라는 점을 염두에 두고, 이제 다음 점이 (x_0 + 1, y_0)이 되어야 하는지 또는 (x_0 + 1, y_0 + 1)이 되어야 하는지에 대한 문제가 제기된다. 아마도 직관적으로 점은 x_0 + 1에서 선에 더 가까운 점에 따라 선택되어야 할 것이다. 전자에 더 가깝다면 전자를 선에 포함시키고, 후자라면 후자를 포함시킨다. 이를 답하기 위해 이 두 점 사이의 중간점에서 선 함수를 평가한다.

:f(x_0 + 1, y_0 + \tfrac 1 2)

이 값의 값이 양수이면 이상적인 선은 중간점 아래에 있고 후보 점 (x_0+1,y_0+1)에 더 가깝다. 즉, y 좌표는 증가해야 한다. 그렇지 않으면 이상적인 선이 중간점을 통과하거나 그 위에 있으며 y 좌표는 동일하게 유지되어야 한다. 이 경우 점 (x_0+1,y_0)이 선택된다. 이 중간점에서 선 함수 값은 어떤 점을 선택해야 하는지를 결정하는 유일한 요소이다.

인접한 이미지는 파란색 점 (2,2)이 녹색 후보 점 (3,2) 및 (3,3)과 함께 선 위에 있는 것으로 선택되었음을 보여준다. 검은색 점 (3, 2.5)는 두 후보 점 사이의 중간점이다.

### 정수 산술을 위한 알고리즘
대신, 중간점에서 f(x,y)를 평가하는 대신 점 간의 차이를 사용할 수 있다. 이 대안 방법은 정수 전용 산술을 허용하며, 이는 일반적으로 부동 소수점 산술보다 빠르다. 다른 방법을 도출하기 위해 차이를 다음과 같이 정의한다.
:
D_i = f(x_i+1,y_i+\tfrac 1 2) - f(x_0,y_0)

첫 번째 결정에 대해 이 공식화는 시작점에서 f(x_0,y_0)=0이므로 중간점 방법과 동일하다. 이 표현을 단순화하면 다음과 같다.
:\begin{array}{rclcl}
D_0 & = & \left[ A(x_0+1) + B \left(y_0+\frac{1}{2}\right) + C \right] & - & \left[ A x_0 + B y_0 + C \right] \\
& = & \left[ Ax_0 + B y_0+ C + A + \frac {1}{2} B\right]  & - & \left[ A x_0 + B y_0 + C \right] \\
& = & A + \frac{1}{2} B = \Delta y - \frac{1}{2} \Delta x
\end{array}

중간점 방법과 마찬가지로 D_0가 양수이면 (x_0+1,y_0+1)를 선택하고, 그렇지 않으면 (x_0+1,y_0)를 선택한다.

만약 (x_0+1,y_0)가 선택되면 D_i의 변화는 다음과 같다.
:\begin{array}{lclcl}
\Delta D &=& f(x_0+2,y_0+\tfrac 1 2) - f(x_0+1,y_0+\tfrac 1 2) &=& A &=& \Delta y \\
\end{array}
만약 (x_0+1,y_0+1)가 선택되면 D_i의 변화는 다음과 같다.
:\begin{array}{lclcl}
\Delta D &=& f(x_0+2,y_0+\tfrac 3 2) - f(x_0+1,y_0+\tfrac 1 2) &=& A+B &=& \Delta y - \Delta x
\end{array}

새로운 D가 양수이면 (x_0+2,y_0+1)가 선택되고, 그렇지 않으면 (x_0+2,y_0)가 선택된다. 이 결정은 각 후속 지점에 오류를 누적함으로써 일반화될 수 있다.

300px|섬네일|선을 그리는 모습 (0,1)에서 (6,4)까지 격자선과 픽셀을 보여준다.

알고리즘의 모든 도출이 완료되었다. 한 가지 성능 문제는 D의 초기 값에 1/2 요인이 있다는 것이다. 이 모든 것이 누적된 차이의 부호에 관한 것이므로 모든 것을 2로 곱해도 아무런 결과가 없다.

그 결과 정수 산술만 사용하는 알고리즘이 만들어진다.

 plotLine(x0, y0, x1, y1)
     dx = x1 - x0
     dy = y1 - y0
     D = 2*dy - dx
     y = y0

     **for** x from x0 to x1
         plot(x, y)
         **if** D > 0
             y = y + 1
             D = D - 2*dx
         **end if**
         D = D + 2*dy

f(x,y) = x-2y+2를 (0,1)에서 (6,4)까지 이 알고리즘을 실행하면 dx=6 및 dy=3으로 다음과 같은 차이가 발생한다.

 D=2*3-6=0
 Loop from 0 to 6
  * x=0: **plot(0, 1)**, D≤0: D=0+6=6
  * x=1: **plot(1, 1)**, D>0: D=6-12=-6, y=1+1=2, D=-6+6=0
  * x=2: **plot(2, 2)**, D≤0: D=0+6=6
  * x=3: **plot(3, 2)**, D>0: D=6-12=-6, y=2+1=3, D=-6+6=0
  * x=4: **plot(4, 3)**, D≤0: D=0+6=6
  * x=5: **plot(5, 3)**, D>0: D=6-12=-6, y=3+1=4, D=-6+6=0
  * x=6: **plot(6, 4)**, D≤0: D=0+6=6

이 플롯의 결과는 오른쪽에 표시된다. 플롯은 선 교차점(파란색 원)에 플롯하거나 픽셀 상자(노란색 사각형)를 채워서 볼 수 있다. 상관없이 플롯은 동일하다.

### 모든 경우
그러나 위에서 언급했듯이 이것은 팔분원 0, 즉 원점에서 시작하여 기울기가 0에서 1 사이이며 x가 반복당 정확히 1씩 증가하고 y가 0 또는 1씩 증가하는 선에만 작동한다.

알고리즘은 y가 증가해야 하는지 감소해야 하는지(즉, dy  0
             y = y + yi
             D = D + (2 * (dy - dx))
         **else**
             D = D + 2*dy
         **end if**

x 및 y 축을 전환함으로써 양수 또는 음수의 가파른 기울기에 대한 구현은 다음과 같이 작성할 수 있다.

 plotLineHigh(x0, y0, x1, y1)
     dx = x1 - x0
     dy = y1 - y0
     xi = 1
     **if** dx  0
             x = x + xi
             D = D + (2 * (dx - dy))
         **else**
             D = D + 2*dx
         **end if**

완전한 솔루션은 x1 > x0 또는 y1 > y0인지 감지하고 그리기 전에 입력 좌표를 역전시켜야 한다.

 plotLine(x0, y0, x1, y1)
     **if** abs(y1 - y0)  x1
             plotLineLow(x1, y1, x0, y0)
         **else**
             plotLineLow(x0, y0, x1, y1)
         **end if**
     **else**
         **if** y0 > y1
             plotLineHigh(x1, y1, x0, y0)
         **else**
             plotLineHigh(x0, y0, x1, y1)
         **end if**
     **end if**

비디오 메모리에 직접 액세스하는 저수준 구현에서는 수직 및 수평선의 특수한 경우를 별도로 처리하는 것이 일반적이다. 매우 최적화될 수 있기 때문이다.

일부 버전은 브레젠험의 정수 증분 오류 원리를 사용하여 x 및 y 좌표 사이의 양수 및 음수 오류 균형을 맞춰 모든 팔분 선 그리기를 수행한다.

 plotLine(x0, y0, x1, y1)
     dx = abs(x1 - x0)
     sx = x0 = dy
             **if** x0 == x1 **break**
             error = error + dy
             x0 = x0 + sx
         **end if**
         **if** e2 <= dx
             **if** y0 == y1 **break**
             error = error + dx
             y0 = y0 + sy
         **end if**
     **end while**

## 유사 알고리즘
브레젠험 알고리즘은 약간 수정된 디지털 미분 분석기(겹치지 않는 다각형 래스터링에 필요한 0 대신 0.5를 오류 임계값으로 사용)로 해석될 수 있다.

나눗셈 연산 대신 점진적 오류를 사용하는 원리는 그래픽스에서 다른 응용 프로그램을 갖는다. 이 기술을 사용하여 텍스처 매핑된 다각형의 래스터 스캔 동안 UV 좌표를 계산하는 것이 가능하다. 일부 PC 게임에서 볼 수 있는 복셀 높이맵 소프트웨어 렌더링 엔진도 이 원리를 사용했다.

브레젠험은 또한 실행 슬라이스 계산 알고리즘을 발표했다. 위에 설명된 실행 길이 알고리즘이 주축에서 루프를 실행하는 동안, 실행 슬라이스 변형은 다른 방식으로 루프를 실행한다. 이 방법은 여러 미국 특허로 대표되었다.
* 
* 
* 
* 
* 
* 
* 
* 
* 

이 알고리즘은 다음으로 확장되었다.
* 임의 두께의 선 그리기: IBM의 Alan Murphy가 만든 알고리즘.
* 다양한 종류의 곡선(원, 타원, 3차, 2차, 유리 베지에 곡선) 및 안티앨리어싱 처리된 선과 곡선 그리기: Alois Zingl이 만든 일련의 알고리즘.

## 같이 보기
* 디지털 미분 분석기 (그래픽스 알고리즘), 선과 삼각형을 래스터화하는 간단하고 일반적인 방법
* 샤오린 우의 선 알고리즘, 안티앨리어싱으로 선을 그리는 비슷한 빠른 방법
* 중점 원 알고리즘, 원을 그리는 유사 알고리즘

## 각주

## 참고 문헌
* 
* "The Bresenham Line-Drawing Algorithm", by Colin Flanagan
*  게임에서 사용하기 위한 C 및 어셈블리로 작성된 알고리즘의 매우 최적화된 버전과 내부 작동 방식에 대한 완전한 세부 정보 포함
* , The Beauty of Bresenham's Algorithms

## 더 읽어보기
* Patrick-Gillesbanda 논문, 3D 은선 제거를 수행하기 위한 브레젠험 직선 그리기 알고리즘의 확장 포함
** MICAD '87 CAD/CAM 및 컴퓨터 그래픽스 회의록, 591페이지 - .
* 브레젠험 알고리즘 수정을 통한 선 굵기화, A.S. Murphy, IBM Technical Disclosure Bulletin, Vol. 20, No. 12, May 1978.
*  &ndash; 또한 Technical Report 1964 Jan-27 -11- Circle Algorithm TR-02-286 IBM San Jose Lab

## 외부 링크

* Michael Abrash's Graphics Programming Black Book Special Edition: Chapter 35: Bresenham Is Fast, and Fast Is Good
* The Bresenham Line-Drawing Algorithm by Colin Flanagan
* 브레젠험 알고리즘에 대한 미국 국립표준기술연구소 페이지
* Calcomp 563 증분 플로터 정보
* 여러 프로그래밍 언어로 된 브레젠험 알고리즘
* 브레젠험 알고리즘의 아름다움 — 선, 원, 타원 및 베지에 곡선을 그리는 간단한 구현

분류:디지털 기하학
분류:컴퓨터 그래픽스 알고리즘