[Graphics] 02. 디스플레이와 그리기 방정식

디스플레이는 다양하다. CRT, LCD/LED, Plasma panel 등등이 있다.

이러한 장비에 어떻게 그래픽적인 디테일을 담을 수 있을까를 고민해보자. 기본적으로 모니터는 픽셀들의 집합으로 장면, 도형 등을 표현한다. 이 러한 픽셀들의 집합으로 그림을 그리는 것을 래스터 그래픽스라고도 한다.

 

래스터 그래픽스상에서 직선을 표현하는 방식은 두 가지이다.

두 영상의 차이를 알겠는가? 그렇다. 왼쪽은 픽셀이 적고 이러한 방식은 축소하면 선의 연결도가 약하며, 오른쪽은 픽셀이 많고 선이 선명하다. 왼쪽과 같은 방식을 Simple DDA(Digital Diffrential(적분) Analyzer)이라고 하며, 오른쪽을 Symmetric DDA이라 부른다. 그리고 보통 용량이 적으며, 표현할 수 있는 것들은 왠만해선 다 표현할 수 있기 때문에 Simple DDA를 더 많이 사용한다.

 

1. 직선 그리기

그렇다면 이러한 것이 DDA 알고리즘인 것은 알았으니 어떻게 programming을 하면 이를 재현할 수 있을 지 생각해보자.

우리에게 필요한 정보는 일단 두 개이다. P1(x1, y1)의 좌표와 P2(x2, y2)의 좌표가 필요하며, 이 두 점만 Accurate ending이며, 동시에 straight하고 even thickness한 굵기를 가지며, continuous해야 한다는 조건이 붙는다. 그리고 또 x1 < x2 & y1 < y2하다는 조건 또한 붙여둔다.

즉 dx = x2 - x1 > 0이며 dy = y2 - y1 > 0이고 dx > dy이다.

 

일단 기본형 알고리즘을 적어보도록 하겠다.

int x = x1;
int y = y1;
plot(x, y);   // 일단 하나 그린다.

while(x < x2) {
   x = x + 1;   // x값을 하나 증가한다.
   y = mx + b   // x에 해당되는 하나의 y값을 찾는다.
   plot(x, <y>);  // x, y를 정수화하여 그린다.
}

 

단 위의 방식은 문제가 있는데 y가 실수(정수 연산보다 심하게 수백~수천배 느리다.)이기 때문에 이 y가 실수가 아닌 정수형으로도 그릴 수 있는 방법을 찾아야한다.

 

브래즈넘 알고리즘(Midpoint algorithm - 중점의 위치를 놓고 y를 가만히 냅둘껀가 한 칸 증가할 건가를 제어하기에 붙여진 이름)

c1 = (dy << 1) - dx;
c2 = (dy << 1) - (dx << 1);
c3 = (dy << 1);

int x = x1;
int y = y1;
plot(x, y);   // 일단 하나 그린다.
int e = c1;

while(x < x2) {
   x = x + 1;
   if(e > 0) {
      y = y + 1;
      e = e + c2;
   } else {
      e = e + c3;
   }
   plot(x, y);
}

 

이 알고리즘은 정수 연산만으로 속도가 향상되었다. 하지만 실수와 정수의 차이가 그렇듯 덧셈과 곱셈의 연산 또한 속도가 크게 차이가 난다. 이를 해결하기 위해 shift 연산을 사용한다.

그럼 잠깐, c1~c3, 그리고 e는 대체 어디서 온 것일까

 

다음과 같이 벡터가 좌표계를 지나가는 경우가 있다. 이 때 만약 x + 1상에서 y 값이 0.5보다 큰 경우 y + 1 이보다 작은 경우 y에 그리게 된다 즉, 이 0.5보다 큰 지 작은지는 체크하기 위해 만들어진 변수가 바로 e이며, x의 e 값과 x + 1의 e값을 비교하기 위해 나온 변수가 m이다.

 

 

즉 이를 다시 코드로 옮기면 다음과 같다.

int x = x1;
int y = y1;
plot(x, y);   // 일단 하나 그린다.
int e = c1;

while(x < x2) {
   x = x + 1;
   e = e + m;  // m = dy / dx;
   if(e > 0.5) {
      y = y + 1;
      e = e + c2;
   }
   plot(x, y);
}

 

이 코드는 또 문제가 if에 실수가 생겨버린다! 이건 느리다. 고로 또 전체적으로 바꿀 필요가 있다. 이는 위보다 해결법은 단순하다. e에 2dx만 곱해주면 실수가 제거가 된다.

int x = x1;
int y = y1;
plot(x, y);   // 일단 하나 그린다.
int e = 0;

while(x < x2) {
   x = x + 1;
   e = e + 2dy - dx;   //
   if(e > 0) {
      y = y + 1;
      e = e - dx;
   } else {
      e = e + dx;
   }
   plot(x, y);
}

 

더 빠르게 하려면 굉장히 low level하게 들어가자. e를 0과 비교하는 것이 정수와 비교하는 것 보다 더 빠르다. 즉 이를 e > 0으로 바꾸면 더 빨라진다는 뜻이다. 근데 저 방식은 계속 e를 업데이트를 해야한다는 손해가 발생한다. 고로 저 // 표시가 있는 e를 빼고 연산을 할 수 있게 바꾼다. 최종은 다음과 같다.

int x = x1;
int y = y1;
plot(x, y);   // 일단 하나 그린다.
int e = 2dx - x;

while(x < x2) {
   x = x + 1;
   if(e > 0) {
      e = e + 2dy - 2dx;
   } else {
      e = e + 2dy;
   }
   plot(x, y);
}

 

2. 원 그리기 알고리즘

원은 굉장히 그리기 까다로운 알고리즘이다. 일단 기본형을 작성해보도록 하겠다.

for(int i = 0; i < n; i++) {
   theta = 2 * pi * i / n;
   x = r * cos(theta);
   y = r * cos(theta);
   plot(<x>, <y>);
}

 

최악이다. 이는 모든 수가 실수이고 이 실수를 정수로 바꿔주는 과정이 필요하기 때문이다. 이를 위해서 대체적으로 theta 값에 대해 0도부터 90도까지 모든 테이블을 만들어서 사용하는 편이고, 이는 시간은 절약하지만 불편하다는 문제가 발생한다. 이러한 테이블의 의존성을 낮추기 위해서는 다음과 같은 방식으로 그림을 그리면 된다.

 

 

 

글쓴이는 포토샵이 없어서 그림판으로 그림을 그린다... 이 점 양해 부탁드립니다.

다음과 같이 일단 8분의 1만큼을 그린 뒤 이를 각 사분면으로 복사를 해주는 방식으로 그림을 그리면 어느 정도 해결이 가능하다. 그리고 이 점이 더 빠르다는 장점이 있다. 즉 코드 상에서 그림을 그릴 때 다음처럼 함수를 짜면 된다.

plot8(x, y) {
   plot(x, y);
   plot(x, -y);
   plot(-x, y);
   plot(-x, -y);
   plot(y, x);
   plot(y, -x);
   plot(-y, x);
   plot(-y, -x);
}

 

이제 plot도 완성했겠다. 함수를 짜자. 일단 기본형이다.

 

 

 

int x = 0;
int y = r;
plot8(x, y);

while(x < y) {
   x++;
   d = x * x + (y - 0.5) * (y - 0.5) - r * r;
   if(d > 0) {
      y--;
   }
   plot8(x, y);
}

 

딱 봐도 d는 굉장히 문제가 많은 편이다. 즉 제거해야 한다.

d = x * x + (y - 0.5) * (y - 0.5) - r * r => 1 + (r - 1/2) * (r - 1/2) - r * r => 1 - r + 1/4; (이 때 반경 r도 정수로 생각한다.)

int x = 0;
int y = r;
d = 1 - r; // 4분의 1을 뺀 이유는 짜피 1픽셀 차이다.
plot8(x, y);

while(x < y) {
   x++;
   if(d > 0) {
      d = d1;
      y--;
   } else {
      d = d2;
   }
   plot8(x, y);
}

 

여기서 d1은 x * x + ((y-1) - 0.5) * ((y-1) - 0.5) - r * r 이다. 그리고 d2은 x * x + (y - 0.5) * (y - 0.5) - r * r 이다.

이를 다시 고치면 d1 = d + dd1(델타d1), 그리고 d2 = d + dd2이다.

dd1 = d1 - d = 2x + 1 - 2(y - 1/2) + 1 = 2(x-y) + 3

dd2 = d2 - d = 2x + 1 로 정의가 된다.

 

최종본은 다음과 같다.

x = 0;
y = r;
d = 1 - r; // 4분의 1을 뺀 이유는 짜피 1픽셀 차이다.
plot8(x, y);

while(x < y) {
   x++;
   if(d > 0) {
      d = d + 2(x-y) + 3;
      y--;
   } else {
      d = d + 2x + 1;
   }
   plot8(x, y);
}