브레즌햄 알고리즘

우리가 스크린에 직선을 그릴때 그리게 될 점의 좌표는 정수기 때문에 계산량이 많은 실수 보다는 비교적 계산량이 적은 정수를 이용해 계산하는게 합리적이다.

실수를 이용한 직선의 방정식을 정수만 이용해 계산하게 만든 알고리즘이 브레즌햄 알고리즘이다.

 

먼저 두 점을 지나는 직선의 방정식을 보면 아래와 같다 : 

y=a * x+b

a는 기울기 b는 절편이다.

예를 들어 (2, 1) 과 (6, 4)를 지나는 직선의 점들 중 x가 4일때 y의 값은 :

y = 3/4 * 4 + 0.5

y = 2.5

이걸 브레즌햄 알고리즘에 적용시켜보자. 

브레즌 햄 알고리즘을 1사분면의 아랫쪽 기준으로 설명해보겠다.

(말이 좀 이상하니 그림을 첨부한다.)

 

 

빨간색이 내가 말하고있는 1사분면의 아랫쪽이다.

(이렇게 나누는 이유는 직접 만들어 보면 깨닫게 될거라 생각한다.)

f = height * 2 - width

f1 = 2 * hieght

f2 = 2 * (hieght - width) 를 구한뒤

x를 1씩 증가시키며

f가 0보다 작아지면 f1을 더해주고

f가 0보다 커지면 y를 1 증가시키고 f2를 더해주는걸

x값이 EndposX에 도달할 때까지 반복시켜 직선을 그리는 알고리즘이다.

---

(2, 1) 과 (6, 4)를 넣었을 때 

  //(2, 1) 과 (6, 4)를 넣었을 때
 int w = InEndPos.X - InStartPos.X;//4 = 6 - 2
 int h = InEndPos.Y - InStartPos.Y;//3 = 1 - 4
 if (w < 0 || h < 0)
 {
  return;
 }
 
 int f = h * 2 - w; // 2 = 3 * 2 - 4
 int f1 = 2 * h;    // 6 = 2 * 3
 int f2 = 2 * (h - w);// -2 = 2 * (3 - 4)
 int x = InStartPos.X;
 int y = InStartPos.Y;
 
 while (x <= InEndPos.X)
 {
  SetPixel(ScreenPoint(x, y), LinearColor(1.f, 0.f, 1.f).ToColor32());
 
  if (f < 0)
  {
   f += f1;
  }
  else
  {
   f += f2;
   y++;
  }
  x++;
 }

처음은

(2,1)에 좌표를 찍고

---

f가 2고 0보다 크니 f2을 더해주고 y와 x를 둘다 증가시킨다.

f=2 -> f = 0  |  x=2 -> x=3 | y=1 -> y=2

(3,2)에 좌표를 찍는다.

---

f=0이 되었다 아직 0보다 크니 f2를 더해주고 x와 y를 둘다 증가시킨다.

f=0 -> f = -2  | x=3 -> x=4 | y=2 -> y=3

(4,3)에 좌표를 찍는다.

---

f=-2가 되었으니 이제 f1을 더해주고 x만 증가시켜준다.

f=-2 -> f= 4 | x=4 -> x=5 | y=3 -> y=3

(5,3)에 좌표를 찍는다.

---

f가 4고 0보다 크니 f2를 더해주고 x와 y를 둘다 증가시킨다.

f= 4 -> f = 2 | x=5 -> x=6 | y=3 -> y=4

(6,4)에 좌표를 찍는다.

끝에 도달했으니 종료.

---

이런식으로 흐름이 흘러가게 되고

x가 4일때는 y=3 이 나오게 된다. (if문에서 조건을 f<=0으로 뒀다면 2가 나왔을 것이다.)

(y=2.5라 예제를 잘 못 든것 같지만 이게 브레즌햄 알고리즘이다.)  

 

8분면 소스코드 : https://gist.github.com/madomagi/77cba1f6ee444bdcd2e662ac7fafefec