Matrix major & multiplication

Motivation

 

개인적으로 진행하는 프로젝트에서 double 수학이 필요한 상황이 되었습니다. 그래서 UE4 가 가지고 있는 수학 라이브러리를 미믹( mimic )해서 double 수학 라이브러리를 플러그인에서 구현하고 있었죠.

 

그런데 이 작업을 하다가 보니 matrix-matrix 곱에서 막히게 되었습니다. UE4 는 SSE 를 사용한다는 가정하에서 matrix-matrix, matrix-vector 곱을 SSE 로 구현해 놨습니다. 문제는 double 은 single( single-precision floating point )와는 SSE 구현 방식이 다르다는 거죠.

 

간단하게 예를 들면 Intel CPU 는 16 개의 mmx 레지스터를 제공하는데, 이것을 __m128 로 접근하죠. 128 비트를 가지고 있으니 이걸 32 로 나누면 4 가 됩니다. 즉 4 개의 single 을 하나의 레지스터에 저장할 수 있다는 것이죠. 하지만 double 을 사용하기 위해서는 __m128d 를 사용해야 하며, 그것의 크기는 256 비트입니다. 즉 2 개의 mmx 레지스터를 사용해 single 을 위해 했던 작업을 에뮬레이션해야 한다는 이야기입니다.

 

이런 작업이 좋은 경험이 될 것 같기는 하지만 귀찮아서 그냥 non-SSE 코드를 구현하기로 했습니다. 하지만 시작부터 벽에 부딪히게 되었습니다. 일단 UE4 는 matrix 에 다음과 같은 주석을 달았습니다.

 

/** * 4x4 matrix of floating point values. * Matrix-matrix multiplication happens with a pre-multiple of the transpose -- * in other words, Res = Mat1.operator*(Mat2) means Res = Mat2^T * Mat1, as * opposed to Res = Mat1 * Mat2. * Matrix elements are accessed with M[RowIndex][ColumnIndex]. */ struct FMatrix

 

여기에서 몇 가지 고민해 볼 지점이 발생합니다.

• pre-multiplication 이란 무엇인가?
• 이 행렬의 major 는 무엇인가?
• 계산 후에 행렬의 major 는 유지되는가?

 

이 때문에 어떤 식으로 계산해야 하는지 혼란이 왔고, 제가 생각하는 것보다 행렬 구현이 쉽지 않다는 것을 깨닫게 되었습니다. 역시 단순히 사용하는 것과 그것을 이해하고 구현하는 것은 다른 법이더군요.

 

이 문서에서는 그런 구현을 하는 데 있어서 필요한 배경 지식들을 정리하고자 합니다.

 

Basic rules & major

 

일단 기본을 점검해 보기로 했습니다. 수학에서 M X N 행렬과 N X K 행렬을 곱하면 M X K 행렬이 나옵니다. 그리고 앞의 행렬의 "행"과 뒤의 행렬의 "열"의 내적이 새로운 행렬의 행과 열이 되죠. [ 4 ] 에서는 다음과 같이 도식화해서 설명하고 있습니다.

 

그림1. Matrix multiplication rule. 출처 : [ 4 ]

 

그림 2 : Dot product rule. 출처 : [ 4 ].

 

수학적으로 볼 때 이런 규칙들은 반드시 지켜져야 합니다. 물론 프로그래밍 언어에서 구현할 때는 여러 가지 이유때문에 우리가 수학에서 보는 것과는 다른 순서로 데이터가 저장되어 있을 수 있습니다. 여기에서 major 라는 것이 중요해지죠.

 

[ 1 ] 에 의하면 row-major 와 column-major 를 구분하는 것은 메모리 상에서의 연속성이 행렬의 어느 방향을 향하고 있느냐를 의미한다고 합니다.

 

그림3. row-major 와 column-major 의 순서. 출처 : [ 1 ]

 

그림3 에서 볼 수 있듯이 실제 메모리에 행을 저장하느냐 열을 저장하느냐 에 따라 row-major 와 column-major 가 결정됩니다. [ 1 ] 에 의하면 row-major 를 택한 언어들은 C, C++, Objecttive-C, PLI, Pascal, Speakeasy, SAS, Rasdaman 등이고, column-major 를 택한 언어들은 Fortran, MATLAB, GNU Octave, S-Plus, R, Julia, Scilab 등이라고 합니다. OpenGL 과 OpenGL ES 의 경우에는 row 에다가 vector 를 저장함에도 불구하고 그것을 column 으로 취급합니다. 그리고 이도 저도 아닌 Java, C#, CLI, .NET, Scala, Swift, Python, Lua 같은 언어들도 있다고 하네요.

 

어쨌든 column-major 냐 row-major 냐는 것은 해석과 구현의 문제입니다. [ 3 ] 에서는 view matrix 를 다음과 같이 표현합니다.

 

그림4. View Matrix. 출처 : [ 3 ].

 

 

그리고 나서 열을 하나의 vector 로 보고 matrix 배열의 한 행에 넣습니다.

 

float right[4] = { 1, 0, 0, 0 }; float up[4] = { 0, 1, 0, 0 }; float forward[4] = { 0, 0, 1, 0 }; float position[4] = { 0, 0, 0, 1 }; float matrix[4][4] = { { right[0], right[1], right[2], right[3] }, // First column { up[0], up[1], up[2], up[3] }, // Second column { forward[0], forward[1], forward[2], forward[3] }, // Third column {position[0], position[1], position[2], position[3] } // Forth column };

 

한 행에 벡터들이 들어 가고 있으므로, 즉 column 들이 연속적인 메모리 공간에서 이어지고 있으므로 이는 column-major 라고 할 수 있습니다. 메모리에서의 저장순서는 아래와 같습니다.

 

 

Pre/Post-Multiplication

 

이 챕터는 [ 2 ] 의 [ The Matrix Chapter ] 의 번역입니다.

 

행렬곱은 두 행렬들에 대한 곱셈입니다. 행렬곱에는 결합법칙( associative law )이 적용되지만 교환법칙( communitative law )은 적용되지 않습니다.

 

결합법칙이 허용되면 다음과 같이 됩니다:

 

 

하지만 교환법칙이 허용되지 않으면 다음과 같이 됩니다:

 

 

행렬곱은 pre-multiplication 이나 post-multiplication 을 사용하여 계산될 수 있습니다. 이것은 벡터가 matrix 의 왼쪽( 혹은 "앞" )에 있어야 하는지 아니면 오른쪽( 혹은 "뒤")에 있어야 하는지를 가리킵니다.

 

 

행렬곱에는 교환법칙이 적용되지 않기 때문에 행렬 곱을 계산할 때 벡터가 행렬의 어느쪽에 있느냐에 따라 완전히 다른 결과가 발생됩니다. 그래픽 API 가 pre 혹은 post multiplication 을 사용하기로 선택하면, 동일한 결과 벡터를 얻으려면 전치된( transoposed ) 행렬을 사용해야합니다.

 

수학 문서에서는 post-multiplicaiton 이 일반적입니다. 이것은 행렬곱이 다음과 같이 계산된다는 것을 의미합니다. 주어진 행 R 과 열 C 에서 결과의 각 구성 요소는 왼쪽 행 행 R 과 오른쪽 열 C 의 내적으로 계산됩니다. 예를 들어 :

 

 

일 때, post-multiplication 을 사용하면, C 행렬의 1 행 2 열의 컴포넌트 b 의 결과를 계산하기 위해, A 의 1 행과 B 의 2 열을 내적합니다( 이것을 row-major 표기법이라 합니다 ). 모든 결과는 다음과 같습니다.

 

 

그러므로 그 결과는 다음과 같습니다:

 

 

이어지는 글에서는 별도의 표기가 없다면 row-major 표기법을 사용합니다.

 

하지만 이것은 정방 행렬을 곱하지 않을 때는 조금 더 까다로워 집니다. 3x3 행렬에 3x1 행렬( 3 행 1 열 벡터 )을 곱하면 3x1 행렬이 됩니다. 4x2 행렬에 2x3 행렬을 곱하면 4x3 행렬이 됩니다. 첫 번째 행렬의 행과 두 번째 행렬의 열에 대한 내적을 취하기 때문에, 첫 번째 행렬에는 두 번째 행렬의 행 수와 동일한 개수의 열이 있어야 합니다. 첫 번째 행렬의 각 행과 두 번째 행렬의 각 열에 대해 이 작업을 수행하므로, 결과 행렬의 행 개수는 첫 번째 행렬의 행의 개수와 같고 열 개수는 두 번째 행렬의 열 개수와 같습니다.

 

일반적으로, 서로 옆에 쓰여진 두 행렬의 차원을 취합니다. 내부의 두 값은 같아야하고 결과 행렬은 외부 값의 크기를가집니다. 4x3 * 3x2 = 4x2. 2x4 * 4x1 = 2x1. 4x3 및 2x4 행렬을 곱할 수는 없습니다. 왜냐하면 3 은 2 와 같지 않기 때문입니다.

 

자, 이제 pre-multiplication 에 대해서 이야기해 보도록 하겠습니다.

 

Pre-multiplication 을 사용하면 이제 행 벡터를 사용해야합니다. 열 벡터는 4x1 행렬이지만, 4x1 행렬에 4x4 행렬을 곱할 수는 없습니다. 대신 1x4 행 벡터를 사용해 1x4 행렬에 4x4 행렬 곱하기( 내부/가장 가까운 두 값의 일치 )의 결과로 1x4 행렬을 만들 수 있습니다( 바깥 쪽 두 값은 1 과 4 입니다 ).

 

그러나 pre-multiplication 을 사용하면 연산이 달라집니다. post-multiplicatin 의 4x4 행렬에 4x1 행 벡터를 곱한 결과 행렬의 각 행에 벡터가 포함됩니다. 이제 pre-multiplication 을 통한 내적은 ( 행렬이 곱셈 연산자의 오른쪽에 있기 때문에 ) 벡터와 행렬의 각 열을 사용해 연산을 합니다.

 

고맙게도, 이것은 쉽게 수정할 수 있습니다. Pre-multiplication 을 위해 행렬을 계산할 때, 단순히 post-multiplicatin 을 위해 사용했던 행렬을 전치하기만 하면 됩니다. 이것은 벡터를 4x1 열 벡터에서 1x4 행 벡터로 변환하기 때문에 의미가 있습니다.

 

2x2 행렬과 2x1 벡터에 대한 post-multiplication 은 다음과 같습니다:

 

 

1x2 벡터와 전치된 2x2 에 대한 pre-multiplication 은 다음과 같습니다:

 

 

결과는 동일하지만 전치된 벡터입니다:

 

 

OpenGL에서 일반적으로 사용하는 것처럼, column-major 표기법으로 post-multiplication 을 사용하면 어떻게 될까요. 수학적 결과는 같지만 행렬 크기의 순서는 바뀝니다. 따라서 column-major 4x3 행렬에 3x2 행렬을 곱할 수는 없지만, 2x4 및 1x2의 곱을 취하면 4x1 행렬(4 행 행 벡터)이 됩니다. 결과와 작동 방식은 모두 동일합니다. 표기법 만 다를 뿐입니다.

 

The Tricky Part

 

중요한 것은 pre-multiplication 이 사용되었는지 post-multiplication 이 사용되었는지의 여부입니다. D3DX 수학 라이브러리는 pre-multiplication 을 사용하고 OpenGL의 표준 행렬 스택은 post-multiplication 을 사용합니다. 그것은 일반적으로 행렬이 전치되어야 한다는 것을 의미합니다.

 

그러나 D3DX 는 row-major 행렬을 사용하고 OpenGL은 column-major 행렬을 사용한다는 점을 기억하십시오. 따라서 그들은 이미 전치되어 있습니다. 다음의 간단한 3x3 변환 행렬을 살펴 보죠. 2 의 uniform scale 과 (10, -5) 의 translation 을 표현합니다.

 

다음의 3x3 행렬은 row-vector 와 pre-multiplication 을 위해 사용되도록 의도되었습니다:

 

 

이것의 row-major 메모리 레이아웃은 다음과 같습니다:

 

 

다음의 3x3 행렬은 column-vector 와 post-multiplication 을 위해 사용되도록 의도되었습니다:

 

 

이것의 column-major 메모리 레이아웃은 다음과 같습니다 :

 

 

행렬은 특정 개념으로 작성되면 전치됩니다. 하지만 메모리에 저장되면 똑같습니다.

 

그것은 까다로우면서 멋진 부분입니다. 여러분의 코드들은 서로 다른 표기법과 서로 다른 행렬곱 순서 때문에 다르게 느껴질 겁니다. 하지만 실제 행렬값은 서로 교환가능합니다.

 

결과적으로 Direct3D 및 OpenGL 스타일을 모두 처리하는 단일 행렬 클래스를 쉽게 작성할 수 있습니다. Column-major 와 post-multiplication 을 사용하거나, row-major 와 pre-multiplication 을 사용하면, 그 데이터는 완전히 호환됩니다.

 

이것을 다시 강조하기 위해서 : 손으로 하는 일은 이것과 아무 상관이 없습니다! 왼손 좌표계 행렬이나 오른손 좌표계 행렬이라는 것은 존재하지 않습니다. 좌표계는 완전히 별도의 이슈입니다.

 

References

 

[ 1 ] Row- and column-major order, Wikipedia.

 

[ 2 ] Matrices, Handedness, Pre and Post Multiplication, Row vs Column Major, and Notations, Game Development by Sean.

 

[ 3 ] Understanding the View Matrix, 3D Game Engine Programming.

 

[ 4 ] Linear Algebra, Artifical Inteligence.