Scan Conversion (스캔 변환)

이번 포스트에서는 컴퓨터 그래픽스의 Scan Conversion의 여러 기법에 대해 다루고자 합니다.

Scan Conversion이란?

Scan Conversion, 우리나라 말로 "주사 변환"은 연속적인 그래픽스 기본 객체를 픽셀의 모음으로 표현하는 프로세스입니다. 즉, 쉽게 말해 아날로그 형태의 어떠한 도형을 디지털 형태의 도형으로 바꿔주는 프로세스라고 생각하면 됩니다.

그러면 우리는 위와 같은 Scan Conversion을 어떻게 해야지 가능하게 할 수 있을까? 바로 Scan Conversion Algorithm을 통해서 할 수 있습니다. 오늘은 그중 "Scan Converting Lines"와 "Scan Converting Circles"의 알고리즘에 대해 다룰 예정입니다. 그러나 Scan Conversion Algorithm을 다루기 앞서, 먼저 컴퓨터 그래픽 도형으로서 선분이 만족해야할 3가지의 조건에 대해서 소개하겠습니다.

그래픽 도형 선분로서의 조건

• 양 끝점을 지난 직선이면서 끝이 있어야 함
• 주어진 점의 순서와 무관하게 정의되어야 함
• 기울기와 상관없이 시각적으로 동일한 밝기를 가져야 함

위에 제시된 3가지의 조건을 반드시 충족시켜야 한다. 이어서 Scan Converting Lines의 알고리즘에 대해서 다루겠습니다.

Scan Converting Lines's Algorithm

그래픽 상에서 선을 그릴 때에는 가능한 최고의 근사값을 생성해낼 수 있도록 해야 합니다. 즉, 선분의 기울기와 가능한 가까운 점을 선택하여 선을 표시해야 한다고 생각하면 됩니다.

위에 제시된 그림과 같이 선분을 그려주는 대표적인 Scan Converting Lines Algorithm은 바로 "Midpoint Line Algorithm"입니다.

Midpoint Line Algorithm

Midpoint Line Algorithm(중간점 라인 알고리즘)은 이전 픽셀의 주어진 선택 가능한 2가지의 다음 픽셀의 중간점을 이용해서 어떤 픽셀을 선택해야 할지에 대해서 정해주는 알고리즘입니다. 다음 그림을 살펴 보겠습니다.

이전 픽셀의 좌표는 P(xp, yp)라고 하면, 좌표 P의 다음 후보 좌표는 NE와 E가 있습니다. 일반적으로 그래픽스 상의 좌표는 정수값이기 때문에 좌표 NE는(xp+1, yp+1)라 할 수 있고(x축 방향으로 + 1, y축 방향으로 +1 움직였으니까), 좌표 E는 (xp+1, yp)라 할 수 있습니다. 그리고 NE와 E의 중간점 M(midpoint)는 M(xp+1, yp+1/2)이라 할 수 있습니다. 이때 직선의 Q가 M보다 위에 있으면 NE, M보다 아래에 있으면 E를 선택하면 됩니다. M을 직선의 방정식에 대입하여 표현한 식은 다음과 같습니다.

d(결정 변수) = a(xp + 1) + b(yp + 1/2) + c

이 식을 통해서 얻어낸 d의 부호에 의해 우리는 다음 픽셀을 어디에다가 그려야 할지를 쉽게 계산할 수 있습니다.

• d > 0일 때, NE 선택
• d < 0일 때, E 선택
• d = 0일 때, 아무거나 선택

이어서 Scan Converting Circles의 알고리즘에 대해 다루겠습니다.

Scan Converting Circles's Algorithm

원에 대한 선분 변화의 방법과 개념은 앞서 설명한 선에 대한 선분 변화와 똑같습니다. 다만 원을 정의하는 방정식이 2차 방정식이므로 스캔 변환 시 고려해야 할 사항이 조금 다를 뿐입니다.

원의 방정식이 2차식이므로 픽셀을 계산할 때는 선분 보다 훨씬 많은 시간을 소요하기 때문에 일반적인 방식으로 계산하면 다소 효율적이지 않습니다. 또한 계산된 원의 간격이 일정하지 않는 상황이 발생할 수 있습니다.

따라서 나온 것이 바로 "Eight-Way Symmetry" 방식입니다. Eight-Way Symmetry 방식은 원의 대칭 특성을 이용해서 원을 8등분 하여 픽셀을 계산하는 방식입니다. 이 방식을 활용하면 우리는 그저 8개의 부채꼴 중 하나의 픽셀만을 구한 다음에 원의 특성을 이용하여 나머지 7개의 픽셀을 쉽게 구할 수 있습니다. 이는 기존의 방식보다 시간적 차원에서 훨씬 우월한다. 다음 그림을 보면 이해하는 데 도움이 될 것이다.

Midpoint Circle Algorithm

Midpoint Circle Algorithm(중간점 원형 알고리즘)은 Midpoint Line Algorithm과 똑같이 이전 픽셀의 주어진 선택 가능한 2가지의 다음 픽셀의 중간점을 이용해서 어떤 픽셀을 선택해야 할지에 대해서 정해주는 알고리즘입니다. 다음 그림을 살펴 보겠습니다.

이전 픽셀의 좌표는 P(xp, yp)라고 하면, 좌표 P의 다음 후보 좌표는 E와 SE가 있습니다. 일반적으로 그래픽스 상의 좌표는 정수값이기 때문에 좌표 E는(xp+1, yp)라 할 수 있고(x축 방향으로 + 1, y축 방향으로 안 움직였으니까), 좌표 SE는 (xp+1, yp-2)라 할 수 있습니다. 그리고 SE와 E의 중간점 M(midpoint)는 M(xp+1, yp-1/2)이라 할 수 있습니다. 이때 원이 M보다 위에 있으면 E, 아래에 있으면 SE를 선택하면 됩니다. M을 원의 방정식에 대입하여 표현한 식은 다음과 같습니다.

d(결정 변수) = (xp + 1) ^ 2 + (yp - 1/2) ^ 2 - R ^ 2

이 식을 통해서 얻어낸 d의 부호에 의해 우리는 다음 픽셀을 어디에다가 그려야 할지를 쉽게 계산할 수 있습니다.

• d ≥ 0일 때, SE 선택
• d < 0일 때, E선택

[그림 자료 출처: Introduction to Computer Graphics, Foley]