직선 

브렌센헴 알고리즘의 가장 핵심이 되는 것은
에러텀이라는 것입니다. 오차이지요.
무한대의 해상도를 갖는 CRT는
존재하지 않으므로 CRT에 선을 그리려면
어쩔 수 없이 오차가 생기기 마련입니다.
이 오차를 이용하는 것입니다.

이 오차가 어느 일정 한도 이상이 되면
점을 찍는 위치를 증가시킵니다.
이해를 돕기위해 좌표계는 컴퓨터가 아니라
일반적인 스퀘어 좌표계를 쓰겠습니다.

     │
    3│            ???
    2│      ???
    1│???
     └───────────
    0  1 2 3 4 5 6 7 8 9
     
위의 그림은 (1,1)에서 (9,3)까지 선을 긋는
모습입니다. 당연히 매끈한 직선이 아니라
정수의 좌표를 갖는 점들의 집합이 되었죠.
설명을 돕기 위해 위의 좌표를 일반화하지
않았습니다. 그냥 가로가 x좌표고 세로가 y좌표
라고 해 두었습니다. 이것을 일반화시키면
설명이 복잡해지거든요.

자~ 이론 설명에 앞서, 선이 그려지는 과정부터
말씀드리죠.
우선 첫번째 점은 1,1에 찍습니다. 그 다음에
x좌표를 증가시킵니다. 그래서 에러텀을 살피고
만약 에러텀이 일정 한도 이하라면 그냥 넘어갑니다.
이렇게 진행하다가 보면 에러텀은 갈수록 커져가고,
나중에는 그 일정 한도라는 값을 넘어서게 됩니다.
그럼 y좌표를 증가시킵니다.
물론 y를 증가시켰으니 에러텀은 어느정도
줄어들겠죠. 에러텀에서 어느 값을 빼면 됩니다.
이 과정을 x좌표가 9가 될 때까지 반복하면 됩니다.
별로 어렵지 않게 이 방법이 실수의 가상좌표상의
점의 정수화와 거의 일치한다는 것을 증명할 수는
있지만 설명하기도 귀찮고, 또 설명한다고 해도
재미가 없어서 생략합니다. (흐-)

브렌센헴 알고리즘을 개략적으로 예를 들어 설명하자면,
그러니까... 무식한 예를 들죠.
만약 점이 0 아니면 1... 식의 정수값을 갖고,
그 증가율이 0.1이라면 어떻게 하겠습니까?
0.1, 0.2, 0.3, 0.4 까지는 그냥 0이라고 하고,
0.5부터 1이라고 하면 되겠죠?
그럼 이것을 아까의 과정으로 설명하죠.

우선 증가율이 0.1이므로...
처음 점은 0.
그 다음엔..
거기에 0.1을 더하면 0.1. 이것은 0.5보다 작으므로
오차는 0.1인채로 넘어가죠.
또 0.1을 더하면 0.2, 이것도 0.5보다 작으므로
오차는 0.2 ...
이런식으로 오차는 계속 늘어갑니다.
이러다가 0.5가 되는 순간 점의 값은 1로 뛰게 됩니다.
그럼 이제 오차는 -0.4가 되죠.
즉 에러에서 0.9를 뺀 것입니다.
이제 또 0.1을 더하면 -0.3으로 아직 0.5보다 작습니다.
또 더하고... 이렇게 하다가 보면 다시 에러텀은
0.5보다 커지고 점의 값은 또한번 증가하게 됩니다.

그렇다면 이것의 스케일을 좀 넓혀보죠.
왜냐하면 당연한 얘기지만 비록 곱셈 없이 덧셈뺄셈만
썼다지만 위의 것은 실수를 썼잖아요.
이것을 정수화 하기 위해선 약간의 연산을 해야 합니다.
그러기 위해선 아주 기초적인 미분식이 들어가는데...
생략하고 결론을 말하죠.
위의 것을 정수화 하고, 다음에 주어진 인수에 따라
재구성하면,

처음의 에러텀은 당연히 0이고,
증가율은 End_X - Start_X ... 즉 X의 변화량,
에러텀의 한계는 X의 변화량을 2로 나눈 값,
에러텀이 한계를 넘었을 때 빼주는 수는 Y의 변화량.

이렇게 됩니다.
그럼 방금 위의 인수를 바탕으로 알고리즘을 설명하면,

 "X의 값을 증가시킨 다음에 에러텀에 Delta_X를 더해준다.
 그 결과 에러텀이 Delta_X / 2 의 값보다 크거나 같으면
 Y의 값을 증가시키고 에러텀에선 Delta_Y를 빼준다.
 이 과정을 X가 선을 긋는 끝 좌표에 도달할 때까지 한다."
 
하나 주의해야 할 것은 위의 경우는 X의 기울기가 Y의
기울기보다 컸을 때의 얘기라는 것입니다.
만약 그 반대라면 진행 과정도 반대가 됩니다.

이해가 가시나요? 제딴엔 최대한 자세히 설명한 것입니다.
아래에 실제 소스를 싣죠.

void line2( int x1, int y1, int x2, int y2, char color )
{
  int x, y, temp;
  int delta_x, delta_y, half, error = 0;
  
  /* 한상 x2 >= x1, y2 > y1 이 되도록 한다. */
  if( x1 > x2 ){
    temp = x1;
    x1 = x2;
    x2 = temp;
   }
  if( y1 > y2 ){
    temp = y1;
    y1 = y2;
    y2 = temp;
   }
      
  /* x, y의 변화량?구한다. */
  delta_x = x2 - x1;
  delta_y = y2 - y1;
  
  /* 처음 시작점을 찍는다. */
  put_pixel( x1, y1, color );

  /* 각 좌표의 기울에 따라 선을 긋는다. */
  if( delta_x > delta_y ){
    y = y1;
    half = (int)( delta_x / 2 );

    for( x = x1+1; x <= x2; x ++ ){
      error += delta_y;
      if( error > half ){
        y ++;
        error -= delta_x;
       }
      put_pixel( x, y, color );
     }
   } else {
    x = x1;
    half = (int)( delta_y / 2 );

    for( y = y1+1; y <= y2; y ++ ){
      error += delta_x;
      if( error > half ){
        x ++;
        error -= delta_y;
       }
      put_pixel( x, y, color );
     }
   }
}

이해가 가셨나 모르겠군요.
위의 예제는 Game13h에서 직접 실행할 수 있도록
만든 것입니다. 함수명을 line2()로 한 것도
Game13h하고 충돌하지 말라고 한 것입니다.
하지만 점찍는 함수를 가진 어떠한 라이브러리에서도
사용하실 수 있습니다.
소스를 보시면 호출한 함수라곤 put_pixel()밖에
없다는 것을 알 수 있을 것입니다.
이 함수의 용도는 지정한 화면상의 위치에 정해진
색으로 점을 찍는 함수입니다.
그러니 이 함수만 만드신다면 어떤 스크린 모드에서도
사용하실 수 있습니다.
만약 기회가 난다면 브렌센헴 알고리즘을 보완한
알고리즘을 올리도록 하고, 지금은 이것으로 끝냅니다.
다음엔 원 그리는 부분을 올리도록 하겠습니다.


       

원 

저번 강좌에 이어 이번엔 브렌센헴 알고리즘으로
원을 그리는 방법을 살펴 보겠습니다.
아시는 분은 다 아시다시피 이 브렌센헴 알고리즘은
구현이 쉽고 빠른 대신에 그 질이 좋지 못하다는
단점을 갖고 있습니다.
이것은 직선보다 원이 더 심합니다.
특히 타원의 경우엔 별도의 보완책 없이 쓰면
더욱 엉망이 되고 맙니다.
또한 여기선 화면의 종횡비는 계산에 넣지
않기로 하겠습니다.
모두 아시다시피 그래픽 모드마다 화면의 종횡비는
조금씩 다릅니다. 오직 몇가지 모드만이 정사각형
픽셀을 제공하는데, 모드 12h가 대표적인 예이죠.
그래픽 종횡비 보정을 해야 그래픽 모드에 상관없이
제대로 된 원을 그릴 수 있으나,
이번 강좌에선 그 부분을 빼기로 하겠습니다.
물론 그 부분이 어려워서는 아닙니다.
하지만 이 강좌는 브렌센헴 알고리즘만을 설명하기
위한 강좌이므로 주제에서 벋어난 부분의 설명은
가능한 한 줄일 생각입니다.

브렌센헴의 알고리즘은 직선이든 원이든 
그 전개 과정은 거의 흡사합니다.
어차피 에러텀에 일정 수를 더하고 그것이
일정 한도가 될 때까지 진행하다가 다음 순간
y의 값이 증가하고...
실제 그 과정에 대한 설명은 전 강좌를 봐 주시기
바랍니다.
그럼 직선과 원이 뭐가 달라지느냐...
이제 그것을 설명할까 합니다.

우선 원은 모든 방향이 대칭이 됩니다.
원을 그릴 때는 기본 4방향 대칭을 이용합니다.
그러나 이럴 경우엔 약간의 문제가 생깁니다.
처음 45도는 제대로 그려지다가 나중엔
X의 좌표 변화율에 비해 Y좌표 변화율이
너무 커져서 점이 떨어지게 됩니다.
그래서 45도씩 그려서 그것을 다시 대칭시킵니다.
이것은 원이 모든 방향으로 대칭된다는
성질로 쉽게 증명이 됩니다.
그러니 실제론 원이라기 보다 곡선으로 이루어진
8각형이라고 하는 것이 낫겠군요.

실제로 원을 그릴 때는 45도 각도만 그리고
그것을 8방향으로 대칭 시킵니다.
그러니 기울기에 따라 그리는 루틴이 갈릴
필요도 없겠죠.
무조건 증가 성분만 있는 부분을 그린 다음에
8방향으로 대칭 시키면 되니까요.
그럼에도 불구하고 원을 그리는 알고리즘은
직선에 비해 신경써줘야 할 부분이 좀 있습니다.

우선 대칭이 되는 네 점을 나열해 보겠습니다.
만약 원점이 (0,0)이라면 임의의 원상의 점 (x,y)는
각각 (y,x), (x,-y), (y,-x), (-x,y), (-y,x), (-x,-y),
(-y,-x)와 대칭됩니다.
만약 원점이 (x0, y0)라면, 이것은 알고리즘에 의해
구해진 (x,y)에 대해,
(x0+x, y0+y), (x0+x, y0-y), (x0+y, y0+x),
(x0+y, y0-x), (x0-x, y0+y), (x0-y, y0+x),
(x0-x, y0-y), (x0-y, y0-x) 의 팔방향으로
대칭된 점들이 구해집니다.

이제 원을 그리는 알고리즘을 위해 실제
원의 방정식에서 각 점의 위치를 구하는 식을
분석해 보기로 하겠습니다.
설명을 쉽게 하기 위해 원점을 (0,0)이라고
하겠습니다. 실제로 이렇게 구해진 x,y는
위의 방법을 사용해 실제 점으로 환원할 수
있습니다. 반지름은 ratio라고 합니다.

우선 원상의 점중에 1/8만을 구합니다.
어느 방향을 하든 상관없지만 이왕이면
x는 증가, y는 감소하는 원의 우상단 부분을
사용합니다. 그럼 x는 0부터 시작해서 y까지
한다고 하면 됩니다.
왜냐하면 x와 y의 반지름에 관한 관계는
서로 동등하므로 만약 이 두값이 같다면 1/8의
지점에 도달한 것이기 때문입니다.
(이런 것까지 증명해줄 필요는 없겠죠?)
물론 y값도 상수가 아닙니다. 그러니 루프의
횟수는 처음부터 정해진 것이 아닙니다.
루프가 진행되어 감에 따라 일정한 규칙에
따라 y좌표도 감소하므로 대체로 처음 정한
y값보다 작은 횟수로 루프가 끝나기 마련입니다.

출발좌표가 (0, ratio)이므로 다음 점의 좌표는
(1, ratio) 이든가 (1, ratio-1)이 될 것입니다.
이 둘중에 어느것인지 판단하는 것은 전 강좌의
직선의 에러텀을 연상하십시요.
다음 점을 구하면 이것이 무엇이든간에 이론적인
원의 점에서 보면 오차가 있습니다.
이 오차의 절대값을 d라고 놓으면,

         d = |(x² + y²) - ratio²|

라는 식이 성립합니다.
이제 위에서 얘기한 (1, ratio)와 (1, ratio-1)
를 사용해 오차를 각각 구할 수 있습니다.
그럼 이 오차가 작은 경우가 우리가 구하고자
하는 점이겠죠?
편이상 (1, ratio)의 오차를 d(S₁),
(1, ratio-1)의 오차를 d(D₁)라고 놓겠습니다.
그럼 d(D₁) - d(S₁)의 값이 0보다 작으면
점이 감소한 것이고, 그렇지 않으면 점은 감소하지
않은 것입니다. 점이 감소했다면 그 오차에서
일정 값을 빼 줍니다. 이것은 전 강좌에서도
언급한 적이 있으니 설명은 생략합니다.
이런 과정을 x를 증가시켜가며 진행해서 원의
1/8의 정도를 그릴 때까지 반복합니다.
x가 언제 1/8지점까지 왔는가는 곧 설명합니다.

이정도 했으면 원 그리기 알고리즘의 대략적인
설명이 되었다고 생각합니다.
브렌센헴 알고리즘을 설명하기 위해 약간
바람을 잡은 셈이죠.
이제부터가 진짜 브렌센헴 알고리즘입니다.
위의 대략적인 이해가 끝났다면 스스로
브렌센헴 알고리즘의 구조를 머릿속에
떠올릴 수 있을 것입니다.
수학이 골치아프시다는 분은 그냥 아래 설명과
소스를 보십시요.
저도 수학과지만 수학은 무지 골치아픕니다.

원의 방정식에서 브렌센헴 알고리즘을
이끌어 내는 과정은 생략합니다.
솔직히 말하면 저도 하라면 헛갈려서
못해요. 유도식을 보고서야 할 수 있죠.
흐흐- 이해는 하지만 하라면 못하는 것...
이것이 우리나라 교육의 문제랄까?
얘기가 잠깐 옆으로 샜는데...
간단히 말씀드리죠.

우선 초기값으로 x, y, thres를 설정합니다.
여기서 thres는 에러텀 비슷한 것인데
아주 약간 다릅니다. 어떻게 다른가는
설명이 애매하니 생략합니다.(생략 투성이군...)
x의 초기값은 0, y의 초기값은 반지름, thres는
3에서 지름을 뺀 값으로 합니다.
그리고 루프를 시작하는데...
그 종결조건은 x가 y보다 커지는 경우입니다.
만약 thres가 0보다 작으면 thres를
6 + x * 4만큼 증가시킵니다. 그렇지 않다면
thres는 10 + (x - y) * 4만큼 증가시키고
y를 하나 감소시킵니다.
이렇게 하면 x와 y의 값이 모두 구해지므로
원점을 중심으로 8방향으로 점을 모두 찍습니다.
여기까지가 루프이며, 이제 x를 증가시키면 되죠.

하나 예외적인 상황이 있는데,
반지름이 0인 경우죠. 이럴 경우엔 점 하나만을 찍은
채 함수를 종결합니다.
자, 아래 소스가 있습니다.

void circle2( int x0, int y0, word ratio, byte color )
{
   int x, y, thres;

   if( ratio == 0 ){
     put_pixel( x0, y0, color );
     return;
    }

   y = ratio;
   thres = 3 - (ratio + ratio);

   for( x = 0; x < y; x ++ ){
     if( thres < 0 )
       thres += 6 + (x << 2);
      else{
       thres += 10 + ((x - y) << 2);
       y --;
      }

     put_pixel( x0+x, y0+y, color ); put_pixel( x0+y, y0+x, color );
     put_pixel( x0-x, y0+y, color ); put_pixel( x0-y, y0+x, color );
     put_pixel( x0+x, y0-y, color ); put_pixel( x0+y, y0-x, color );
     put_pixel( x0-x, y0-y, color ); put_pixel( x0-y, y0-x, color );
    }
}

전번 강좌와 마찬가지로 점찍는 함수를 갖춘 다른 모든
프로그램에서 사용이 가능합니다.
이번에도 어제처럼 날림으로 강좌를 끝냈는데,
이유는(핑계는) 전산학도나 수학도를 위한 공식 유도가
아니라 브렌센헴 알고리즘이 이렇다 싶은 정도만
얘기하고 실제로 컴퓨터로 옮기는 것만을 설명하는 것이
이 강좌의 목적이기 때문입니다.
아마 다음 강좌인 타원 그리기 알고리즘은 더욱 날림이
될 것입니다. 원 그리기보다 배는 복잡하니까요.
그리고 제가 브렌센헴 알고리즘을 공부하기 시작한 것도
그렇게 오래되지 않았으니 강좌에서 틀린 부분도 있을
것입니다. 만약 그렇다면 아주 마음 놓고 씹어주세요.
언제든 칼맞을 준비가 되어 있습니다. (헤-)
그럼 조금이라도 도움이 되었기를...

타원

안녕하세요?
제가 개강 때문에 좀 바빠서 강좌가
늦어졌습니다. 원래 계획으론 하루에
하나씩 3일에 다 끝낼려고 했는데...
이번엔 브리슨헴 알고리즘 강좌
마지막인 타원 그리기입니다.
하나 미리 얘기해 둘 것은,
비록 여기에 브렌센헴 알고리즘의
강좌라지만 이 타원 그리기 알고리즘은
브렌센헴 알고리즘이 아닙니다.
실제 그 구현을 보면 브렌센헴 알고리즘과
유사하지만 어느 참고서적에서도 이것을
브렌센헴 알고리즘이라고 하지 않습니다.
하지만 연관관계도 있고, 그 구현면에서도
유사하니까 이 강좌에선 같은 계열에서
취급하는 것입니다.
이점 착오 없으시기 바랍니다.

척 보기에도 알 수 있듯이, 타원의 방정식은
원의 방정식보다 어렵습니다.
그리고 속도도 더 늦고요.
하지만 약간 변형을 하면 상당히 빠른 속도를
낼 수도 있습니다. 이 알고리즘의 이름은
모르겠지만 구현 방법면에선 할 하드베르그의
알고리즘과 유사하므로 그쪽 계통이 아닌가
생각됩니다. 속도는 무척 빠르지만
여기서는 다루지 않겠습니다.
만약 얘기를 하자면 원그리기까지
또다시 거슬러 올라가야 하기 때문입니다.

타원은 원의 경우와는 달리 4방향이 대칭됩니다.
그리고 단순 증가방식만을 쓰지 않습니다.
타원의 경우엔 선그리기처럼 45도를
기점으로 그 기울기(?)가 다르므로 구현할 때도
이 두경우를 나누어서 해 주어야 합니다.
그러니 실제론 4분의 1만을 그리고 나머지는
대칭으로 찍으면 되고, 또 이 1/4도 두가지로
나누어서 그려야 합니다.

이 알고리즘을 위한 설명은 따로 존재하지 않고
앞에서 한 설명을 바탕으로 유도식만을
보입니다. 실력이 있는 분들은 이해하실 수 있을
것입니다. 만약 이해가 안된다면 다른 참고서적들을
참고하세요. 아마 많은 그래픽 서적에서 이것을
다루고 있을 것입니다.

유도식이 긴 관계로 초기항과 결과만을 쓰기로
하겠습니다.
우선 타운의 방정식이

  (x0 - x)?  (y0 - y)?
  ────  - ────  = 1
     a?         b?

이라는 것은 후진 중학교 안나온 이상 다 아는
사실. 이것을 약간 변형시켜서,

  b?x? + a?y?- a?b? = 0
  
이라고 놓고 이것을 앞의 방법을 통해 d를 구하면

  d = b?(x+1)?+a?(y-1/2)?-a?b?
  
이고, 각각 d₁,d₂, d₃... 에 대해 
d₂-d₁, d₃- d₂... 등을 구하면

 d₂- d₁= -2a²y₁
 d₃- d₂= -2a²y₂
 .
 .
 .
 
이다. 이것은 기울기, 즉 dy/dx가 -1 이상일
때이고, 만약 그 이하라면

 d₂- d₁= -2a²y₁+ a²
 .
 .
 
으로 바뀝니다.
또한 생각해 줘야 할 것이 한두개 더 있지만
설명을 생략하기로 합니다.

이렇게 생각해 줘야 할 경우가 두가지인데다가
그 성격이 다르기 때문에 타원을 그리는 데엔
크게 나누어 두개의 다른 루프를 돌려야 합니다.
게다가 루프 내에서 당연히 판단 루프가
들어가죠. 총 4가지의 다른 상황을 처리하는
함수로 타원 그리는 함수는 구성되어 있습니다.

대략적으로 설명한대다가 알고리즘을 구현하기
위해 충분한 자료를 다 제시하지 못했습니다.
이유는 앞서 말했듯이 알고리즘 자체에
대한 강좌라기 보다는 소개와 실제 그 소스를
공개하는 데에 그 목적을 두기 때문입니다.

void ellipse2( int x0, int y0, word a0, word b0, byte color )
{
  int x = 0, y = b0;
  long a = a0, b = b0;
  long a_squ = a * a;
  long two_a_squ = a_squ << 1;
  long b_squ = b * b;
  long two_b_squ = b_squ << 1;
  long d, dx, dy;

  d = b_squ - a_squ*b + (a_squ >> 2);
  dx = 0;
  dy = two_a_squ * b;

  while( dx < dy ){
    put_pixel( x0+x, y0+y, color );
    put_pixel( x0-x, y0+y, color );
    put_pixel( x0+x, y0-y, color );
    put_pixel( x0-x, y0-y, color );
    if( d > 0 ){
      y --;
      dy -= two_a_squ;
      d -= dy;
     }
    x ++;
    dx += two_b_squ;
    d += b_squ + dx;
   }

  d += ( 3*(a_squ - b_squ)/2 - (dx+dy)/2 );

  while( y >= 0 ){
    put_pixel( x0+x, y0+y, color );
    put_pixel( x0-x, y0+y, color );
    put_pixel( x0+x, y0-y, color );
    put_pixel( x0-x, y0-y, color );
    if( d < 0 ){
      x ++;
      dx += two_b_squ;
      d += dx;
     }
    y --;
    dy -= two_a_squ;
    d += a_squ - dy;
   }
}

앞의 두 강좌와 마찬가지로 점찍는 기능을 가진 다른
모든 프로그램에서 실행이 됩니다.
아마 설명이 그다지 잘 되지 못했을테고,
게다가 알고리즘 구현에 필요한 것을 전부
설명하지 못했기 때문에 설명 자체만으로 프로그램을
짤 수는 없을 것입니다. 설명이 미흡하다고 생각하면
다른 참고서적을 살피고, 실력이 있으시다면
소스와 앞에서 설명한 몇가지 자료만으로 직접 분석해
보시기 바랍니다.

미흡한 강좌, 끝까지 봐 주신 여러분께 감사드립니다.
한번 그래픽 이론을 알고 싶다고 생각하고 보신
분들은 실망이 크시겠지만 그냥 한번 어떤 것인가
맛만 보겠다고 생각하시고 강좌를 보신 분들은
약간 도음이 되셨을 것입니다.

요즘 게임들이 테크닉 위주로 많이 나가는데,
이제는 테크닉보다 탄탄한 자료 구조와 이론을
바탕으로 그곳의 위에 화려한 테크닉의 옷을
입힌 알찬 게임이 뮌?나왔으면 좋겠습니다.
특히 3차원 게임에 관한 관심이 높아지는데
조금 아는 듯 싶다 하는 분들이 자신의 소스를
공개하길 꺼리는 것 같군요.
저도 좀 많이 배우고 싶은데...
아무쪼록 혹시나 3차원 그래픽 쪽으로 지식이
조금 있는 분께서 이 글을 읽으신다면
우리나라 게임의 발전을 위해서도
소스를 팍팍 공개하시고, 강좌도 하시면서
자신의 지식을 아낌없이 나누어 주시길 바랍니다.
그럼...