Bresenham - KimTaebin-ai/study_posts GitHub Wiki

1. 직선 방정식 이해하기

직선은 두 점을 연결한 가장 짧은 경로이다. 예를 들어, 두 점 (0,0)과 (5,3)을 잇는 선을 생각해보자.

직선 방정식: y = mx + b

• y: y 좌표, 즉 세로 위치이다.
• x: x 좌표, 즉 가로 위치이다.
• m: 기울기라고 하는 값인데, 직선이 얼마나 가파른지를 나타낸다.
  • 
  • 예를 들어, (0,0)에서 (5,3)으로 가는 경우 세로 변화량은 3, 가로 변화량은 5이므로, ( m = \frac{3}{5} ).
• b: y 절편으로, x=0일 때 y의 값입니다. 예를 들어 시작점이 (0, 0)일 때는 b = 0입니다.

2. 직선을 그릴 때 문제점

컴퓨터 화면에 선을 그릴 때는 픽셀 단위로 표시되기 때문에, 아무리 작은 이동이라도 좌표가 1씩 증가합니다. 즉, 컴퓨터는 선을 한 픽셀씩 옮겨가며 그려야 하므로 부드럽게 그리기 위해서는 점을 올바르게 찍는 알고리즘이 필요합니다.

• 예를 들어, 기울기가 ( m = \frac{3}{5} )인 경우, x가 1씩 증가할 때마다 y는 정확히 0.6씩 증가해야 합니다.
• 그러나 컴퓨터는 0.6픽셀을 그릴 수 없고, y는 반드시 정수 값으로만 표현됩니다.
• 따라서 정수로 y 값을 근사해서 한 픽셀씩 옮겨가며 그리는 알고리즘이 필요합니다.

3. 브레젠험 알고리즘의 기본 개념

브레젠험 알고리즘은 어떤 픽셀을 선택해야 하는지 계산하여 직선을 그리는 방법입니다. x 값이 증가할 때마다 y가 얼마만큼 증가할지 잘 계산해서, 정수 좌표로 근사하면서 직선에 최대한 가깝게 그립니다.

알고리즘의 핵심 아이디어

1. 오차 계산:

   • 브레젠험 알고리즘에서는 x 좌표를 한 픽셀씩 증가시키며 y의 이동을 결정합니다.
   • 초기 오차 값을 설정하고, x가 움직일 때마다 이 오차를 더하면서 어느 방향의 픽셀로 갈지 결정합니다.

2. 오차 값 업데이트:

   • x가 1 증가할 때, y가 얼마나 움직여야 직선에 가까운지를 오차 값(error)으로 판단합니다.
   • 오차가 특정 값보다 크면 y를 1 증가시키고, 아니면 그대로 y는 유지합니다.
   • 이렇게 함으로써 가능한 한 직선에 가까운 픽셀을 선택하게 됩니다.

4. 브레젠험 알고리즘으로 선을 그리는 방법

예를 들어, 시작점이 (0,0)이고 끝점이 (5,3)인 직선을 그려볼게요.

1. 초기 설정:

   • x = 0, y = 0, dx = 5 (가로 이동량), dy = 3 (세로 이동량).
   • 오차 값 error = dx - dy = 5 - 3 = 2.

2. 좌표를 한 픽셀씩 이동하면서 점 찍기:

   • x를 1씩 증가시키며, error를 계산해가면서 y의 움직임을 결정합니다.
   • error가 0보다 크면 y를 1 증가시키고, error 값에서 dy를 빼줍니다.
   • error가 0보다 작거나 같으면 x만 이동하고, error에 dx를 더해줍니다.

3. 과정 반복:

   • 이 과정을 반복하면서 각 단계마다 (x, y) 좌표를 그림에 찍어 선을 이어갑니다.

5. 브레젠험 알고리즘 예시

• 시작점: (0,0)
• 끝점: (5,3)
• error = 2

• 결과: 점들을 이어 (0,0), (1,1), (2,1), (3,2), (4,2), (5,3)에 점이 찍히며, (0,0)에서 (5,3)으로 이어지는 선이 됩니다.

이렇게 브레젠험 알고리즘은 error 값으로 x, y 좌표의 변화를 결정하여 직선을 그립니다.