이 글은 조만간 출판될 Game Programming Gems 3 한국어판(류광 역, 정보문화사)의 일부입니다. 이 글에 대한 모든 권리는 정보문화사가 가지고 있으며, 사전 허락 없이는 웹 사이트 게시를 비롯한 어떠한 형태의 재배포도 금지되어 있습니다.

이 글은 최종 교정 전의 상태이므로 오타나 오역이 있을 수 있습니다. 또한 웹 페이지의 한계 상, 실제로 종이에 인쇄된 형태와는 다를 수 있습니다. 실제 책에서는 표나 수식이 좀 더 정확한 형태로 표시될 것이며 그림/도표 안의 영문도 적절히 한글화될 것입니다.

Game Programming Gem 3 한국어판에 대한 정보는 GPG 스터디(http://www.gpgstudy.com/)에서 얻을 수 있습니다.

2.4 사원수의 압축

Mark Zarb-Adami, Muckyfoot Productions
mark_at_muckyfoot.com

오늘날의 컴퓨터 게임들은 많은 양의 애니메이션 데이터를 사용하며, 각 애니메이션 프레임에 쓰이는 메모리 중 많은 부분이 뼈대의 회전에 소비된다. 회전 데이터는 일반적으로 사원수(quaternion, 四元數) 형태로 저장되는데, 이 글에서는 float 네 개짜리 사원수를 하나의 32 비트 값으로 압축하는 방법들이 제시, 비교된다.

사원수

하나의 사원수 Q(x, y, z, w)로 하나의 회전 행렬을 표현할 수 있다. 모든 회전 행렬들이 축 A(X, Y, Z)에 대한 각도 θ의 회전을 의미한다고 할 때, 그 회전에 대한 사원수는 다음과 같다.

여기서,

사원수 Q(x, y, z, w)와 사원수 Q'(-x, -y, -z, -w)는 동일한 회전을 의미한다는 점도 주의해야 할 것이다. 이는 축 A에 대한 각도 θ의 회전이 축 -A에 대한 각도 -θ의 회전과 동일하기 때문이다. 그리고, 이 글에서는 모든 사원수들이 정규화된 것이라고 간주한다. 즉, 이 글의 모든 사원수 Q(x, y, z, w)는 다음을 만족한다.

최소삼법

사원수의 각 성분을 하나의 바이트로 줄일 수 있다면 사원수를 32 비트로 압축할 수 있다. 물론 무작정 그렇게 하면 정밀도는 떨어질 수밖에 없다. 그러나 사원수가 정규화되어 있다는 점을 이용해서 네 성분 중 하나를 제거한다면 정밀도를 올릴 수 있다(작은 성분 세 개만 남긴다고 해서 최소삼법(smallest three)이라고 부른다). 세 개의 성분들이 주어지면 나머지 한 성분을 계산할 수 있다. 그렇다면 어떤 성분을 제거해야 할까? 절대값이 가장 큰 성분을 제거하면 저장할 값들도 더 작아진다. 실제로, 하나의 사원수에서 가장 큰 것을 제외한 나머지 세 성분들 중 1/sqrt(2)를 넘는 것은 존재하지 않는다. 다음과 같은 식으로 생각해보면 그 이유를 이해할 수 있을 것이다. 정규화된 사원수에서 두 성분이 같고 나머지 둘은 0이라고 하면(예를 들어 Q(v, v, 0, 0)) 두 번째로 큰 성분은 곧 가장 큰 성분이다. 그런 사원수를 정규화하면 0이 아닌 성분, 즉 가장 큰 성분은 1/sqrt(2)가 되며, 따라서 나머지 세 개 중 1/sqrt(2)를 넘는 성분은 존재하지 않는다.

가장 큰 성분의 부호는 저장할 필요가 없다. 항상 0보다 크다고 가정하면 되기 때문이다. 가장 큰 성분이 음인 경우에는 압축 과정 이전에 사원수 전체의 부호를 바꾸면 된다.

극법

방향 벡터 (x, y, z)는 두 개의 각도 요(yaw)와 피치(pitch)만으로 표현할 수 있다. 따라서 그에 해당하는 사원수도 (요, 피치, w)로 줄일 수 있다. (x, y, z)를 요와 피치로 저장하면 길이에 대한 정보가 사라지나, 사원수가 정규화되었다고 가정하므로 w를 통해서 길이를 복구하는 것이 가능하다. w가 항상 양이라고 가정한다면 w의 부호 역시 저장할 필요가 없다. 만일 양이 아니라면, 역시 압축 과정 이전에 사원수 전체의 부호를 뒤집고 시작하면 된다.

방향 벡터를 요와 피치로 저장할 때 한 가지 문제는, 변환된 벡터들이 구면에 대해 균등하게 분산되지 않고 양 극에 몰리는 경향을 보인다는 점이다. 벡터의 피치가 π/2이고 벡터가 극 쪽을 바로 가리키고 있다면, 요는 저장하지 않아도 된다. 그러나 벡터의 피치가 0이고 벡터가 적도를 따라 놓여 있다면, 여러 개의 요 값들을 저장해야 한다. 방향 벡터를 n 비트로 압축한다고 하자. 한 가지 방법은 점들을 구면에 균등하게 분포시키고, 각 점의 (x, y, z) 또는 (요, 피치)를 참조 테이블에 저장하고, 그 테이블에 대한 n 비트 색인을 저장하는 것이다. 이러한 방법은 n이 작을 때에는 유효하나, n이 커질수록 테이블도 커진다는 단점을 가지고 있다.

다행히 참조 테이블 없이 방향 벡터를 인코딩하는 효과적인 방법이 존재한다. 우선 x, y, z의 부호들을 개별적으로 저장해두고, 그 후부터는 x, y, z가 모두 양이라고 가정한다. 이렇게 하면 문제 공간을 구면의 8분의 1로 축소할 수 있다. 다음으로는, 그 8분구의 점들에 번호를 매긴다(그림 2.4.1).

그림 2.4.1 8분구면의 점들에 번호를 매긴다.

그림 2.4.1을 보면, 왼쪽 가장자리의 수들이 제곱수임을 알 수 있다. 이러한 특징을 이용하면 인코딩된 번호 e에 해당하는 행(row)과 열(column)을 알아낼 수 있다.

 row = floor(sqrt(e));
 column = e - row*row;

이제 벡터의 피치를 행번호로, 요를 열번호로 해서 e를 구하면 결과적으로 하나의 방향 벡터를 하나의 n 비트 값으로 압축할 수 있다. 이러한 방법에서 주목할 것은, 극에서는 어떠한 요 값들도 낭비되지 않으며 적도에서는 가능한 요 값들이 대단히 많아진다는 점이다.

구현

그럼 지금까지 이야기한 방법들의 구현에 대해 이야기해보자.

최소삼법

최소삼법은 하나의 사원수를 32 비트에 깔끔하게 저장한다. 32 비트 중 두 비트는 제외된(가장 큰) 성분의 색인으로 사용하고, 각각의 10 비트에는 나머지 세 성분들을 저장한다. 저장된 성분들 모두 범위 [-1/sqrt(2), 1/sqrt(2)] 안에 들어가므로, 그 범위를 [0, 1023]으로 보간해서 각 성분의 값을 정수로 저장하면 된다.

극법

다양한 비트 할당 방식들을 시험해 본 결과, w에 11 비트를 할당하는 경우 가장 잘 압축됨을 알 수 있었다. x, y, z의 부호들을 총 3 비트에 저장하고, 나머지 18 비트에 요와 피치를 저장한다. 요와 피치를 하나의 값으로 변환한다면 512개의 값들을 저장할 수 있다. 아니면, 요와 피치를 각각 9 비트씩 저장할 수도 있다. 요와 피치 모두 범위가 [0, π/2]이므로 그 범위를 [0, 511]로 보간해서 정수로 저장하면 된다.

요와 피치를 다시 벡터로 복원하려면 둘 모두에 대해 사인과 코사인 계산이 필요하다. 이 때 [Edwards00]에 나온 빠른 다항식 근사를 사용하면 속도를 올릴 수 있을 것이다. 또한, 요와 피치는 항상 [0, π/2]에 속하므로 그 범위에 맞게 근사를 최적화하는 것도 좋은 생각이다. 테일러(Taylor) 급수를 π/4에 대해(0이 아니라) 전개하고 [0, π/4] 사이의 값들을 라그랑쥬(Lagrange) 급수를 위한 표본 값들로 사용할 수도 있다. 5차까지의 테일러 급수나 4, 5차까지의 라그랑쥬 급수면 충분하다. 4차 라그랑쥬 급수가 조금 더 빠르긴 하지만 정밀도가 상당히 떨어지게 된다. 그리고 5차 라그랑주 급수는 5차 테일러 급수보다 더 정밀하다.

필자가 관여한 게임 Blade II의 애니메이션 데이터는 계통적으로 저장되어 있으므로 대부분의 사원수들은 오직 작은 각도의 회전을 표현한다. 회전각을 θ라 할 때 사원수의 스칼라 성분 w는 cos(θ/2)이므로, θ가 작을 때 w는 1에 매우 가깝다. 이는 사원수가 무작위적인 회전각을 가지는 경우에도 어느 정도 참이다(코사인 함수의 성질 때문에). 1에 가까운 값들을 좀더 세밀하게 구분하기 위해 사용한 방법은, w 대신 sqrt(1-w)를 저장하고 압축을 풀 때 w를 다시 복구하는 것이다.

성능

각 압축 방법의 품질을 측정하기 위해, Blade II의 사원수들을 자료로 사용했다. 측정 방법은 이렇다. 자료의 각 사원수 Q를 압축해서 또 다른 사원수 Q'를 얻고, Q와 Q'를 행렬들로 변환한 후 Q로 변환된 점과 Q'로 변환된 점 사이의 거리를 계산한다. 계산된 거리는 압축 방법의 오차로 간주한다. 또한 각 방법의 압축 해제 속도도 측정한다. 그림 5.4.2는 Blade II의 계통적 자료에 대한 각 압축 방법의 상대적 성능을 보여주고 있다. 극법에 쓰인 근사 방법은 5차 라그랑쥬 다항식이다.

해제 시간

                                           극법으로 인코딩된 (요, 피치)와 w
최대 오차                                  극으로 표현된 (요, 피치, w)     
                                           최소삼법                        

평균 오차

그림 2.4.2 Blade II 사원수 자료를 이용한 압축 방법들의 상대적인 성능

결론

수치 자료보다는 게임 안의 캐릭터들을 실제로 관찰하는 것이 이런 압축 방법들에 대한 좀 더 실질적인 평가 방법일 것이다. Blade II의 경우 오차들이 뼈대를 따라 누적되는 상황이 벌어지기도 했다. 특히 캐릭터가 긴 막대(샷건 등)를 쥐고 있는 경우 오차가 매우 컸다. 최소삼법에 비해 극법을 사용할 때 눈에 보일 정도의 개선이 있다.

감사의 말

이 글의 아이디어를 전개하는 데 도움을 준 Jan Svarovsky와 Mike Diskett에게 감사의 뜻을 전한다.

참고자료