미국에서 꽤나 유명한 프로그래밍 인터뷰 관련 책이 있다. 심심해사 잠시 들쳐보다 맘에 들지 않는 문제 풀이가 있어 이 글에서 이야기 좀 하고자 한다. 그래픽스에 관련된 건데 간단한 문제다.

반지름 값이 주어졌을 때 (0, 0)을 중심으로 하는 8분의 1원을 그리는 함수를 만들어보라. 8분의 1원이란 12시 방향에서 1시 30분 방향까지만 그리는 것을 말한다. 픽셀은 setPixel(x, y) 함수로 그리는 것으로 가정한다.

그냥 위 그림처럼 동그라미 일부, 즉 호를 그리면 된다. 그런데 문제 풀이를 보니 좀 고되게 풀고 있었다. 바로 원을 음함수로 표현하고 있었다 (수식은 여기서 그렸음).

모 이건 고등학교 1학년 때 배우는 산수다. 여기서 우리는 1사 분면에서 그림을 그리기 때문에 음수인 경우를 무시하면 되겠다. 그래서 이 수식을 가지고 픽셀을 찍고 있다. 이것만 해도 좀 삽질스러운데 더 못 마땅한 것은 8분의 1만큼의 호를 그리기 위한 구간 계산이었다. 어떻게 보면 센스있는 발견이라고 할 수도 있겠지만, (0, r) 부터 점을 찍기 시작해서 “y가 x보다 작아질 때까지” 그리도록 하였다. 1/8 원은 기울기 45도인 직선 (y=x) 위에서 끝나기 때문이다. 그래서 최종적으로 책에서 제시하고 있는 답변은:

void drawEighthOfCircle(int radius){ 
  int x = 0, y = radius; 
  while( y <= x ){ 
    y = Math.sqrt((radius * radius) - (x * x)) + 0.5; 
    setPixel( x, y ); 
    x++; 
}

대충 이러하다. 여기서 또 반올림까지 고려해서 0.5까지 더 하고 있다. 썩 맘에 들지 않는다. 특히 구간 설정이 너무 맘에 안든다. 만약 1/17 원을 그리라면? 그 땐 “y <= x” 이런 것으로는 안되고 직접 x, y 좌표를 구해야만 하는 번거로움이 추가된다. 더 나가 1, 4사 분면에 원이 걸친다면 음수인 경우를 따로 처리해야 할 것이다.

그런데 극형식을 빌어 표현하면 코드는 매우 간단해진다.

얼마나 깔끔한가? 이 문제가 요구하는 답은 단순히 theta를 45도에서 90도까지 바꿔주며 점 찍으면 끝난다. 더 나가 극형식을 쓰면 속도 및 가속도 구하는 것도 매우 간단해진다.

void drawEighthOfCircle(int radius){
  static const double PI = 3.141592654;
  static const double RESOLUTION = PI/180;
  for (double theta = PI/4; theta <= PI/2; theta += RESOLUTION)
    setPixel(r*cos(theta), r*sin(theta));
}

그러나 생각해보면 극형식을 이용한 코드는 몇 가지 문제점을 가지고 있다.

그리는 범위가 상당히 직관적으로 표현이 되지만 화면 해상도를 고려해 적절한 스텝을 결정해야 한다는 문제가 있다. 내가 쓴 코드는 단순히 1도(=pi/180) 만큼 스텝을 줘서 그렸기 때문에 루프는 45번 정도 순회할 것이다. 그런데 확대된 화면을 그린다고 하자. 그러면 이 코드는 듬성듬성 점만 찍고 말 것이다. 그래서 이 점들 사이를 선분으로 이어주는 코드를 넣거나 아니면 더 잘게 점을 찍어야 할 것이다. 반면 내가 삽질스럽다고 욕한 코드는 이 점에 있어서는 좋다. 정확하게 x 좌표를 하나씩 증가 시키기 때문에 해상도 문제를 고려할 필요가 없어 보인다.

계산량을 생각하면 cos, sin 같은 초월함수는 x87 명령어에 있기도 하지만 이런 경우는 미리 테이블을 만들어 놓을 수 있다. 또, cos, sin 입력 단위를 도로 한다면 루프 순회도 double이 아닌 정수로도 표현 가능하다. 실제 그래픽카드 드라이버에서 어떤 방식으로 원의 호를 그리는지는 잘 모르겠다. 거기서는 최대한 정수 연산으로 바꿔야 하기 때문에 sqrt 만 회피한다면 책에서 제시한 방식이 더 나을지도 모르겠다.

여러분은 어느 코드가 더 나아 보입니까? 저는 컴퓨터 그래픽스 전문가는 아닙니다.

(추가) 1/8 원을 그리는 것은 원을 그리는 기본 연산 중 하나입니다. 일반적으로 이런 문제는 2차원 픽셀 화면에 선분을 그리는 것과 같은 스캔 컨버전 문제인데 픽셀 단위로 그려야 한다면 원래 책에 있는 방식이 합리적입니다. 제가 생각한 극형식은 표현이 매우 간단하고 복잡한 곡선(음함수로 표현이 불가능한)을 그리기에 매우 편리합니다만 지적했듯이 픽셀 단위가 아닙니다. 목적에 따라 적절하게 선택하시면 되겠습니다.

참고: http://mrl.snu.ac.kr/courses/CourseGraphics/OutputPrimitives.ppt