1万回のQuaternion * Vector3の処理速度を上げてみる

2022 3/30

2022年3月31日

Quaternion * Vector3をMultiplyPoint3x4()で計算するという記事です。

UnityでQuaternion * Vector3の掛け算をすると、Vector3をQuaternionで回転させた座標が得られます。
通常、Unityでこの計算をする時は以下のコードになります。

// X軸に90度回転させる四元数
Quaternion testQuaternion = Quaternion.Euler(90, 0, 0);

// ベクトル
Vector3 testVector3 = new Vector3(10, 10, 10);

// X軸に90度回転した後のベクトル
Vector3 rotatedVector = testQuaternion * testVector3;

クォータニオンなら数学関数を使わずにベクトルを求められるので、処理速度が速いです。
しかし、それでも1フレームの中で何万回も実行するような作りをするとパフォーマンス悪化の原因になります。

同じベクトルを上記とは異なる方法で求めることもできます。

// X軸に90度回転させる四元数
Quaternion testQuaternion = Quaternion.Euler(90, 0, 0);

// ベクトル
Vector3 testVector3 = new Vector3(10, 10, 10);

// 変換行列を作成
Matrix4x4 testMatrix4x4 = Matrix4x4.Rotate(testQuaternion);

// X軸に90度回転した後のベクトル
Vector3 rotatedVector = testMatrix4x4.MultiplyPoint3x4(testVector3);

通常であれば前者の方が処理速度は速いです。
ですが、以下の条件に当てはまる場合であれば、Matrix4x4構造体のMultiplyPoint3x4メソッドで処理速度を向上させることができます。

同じQuaternionを使用してベクトルを計算している
計算回数が7500回以上

ベンチマーク

ベンチマーク用のコードは以下です。

Quaternion * Vector3

int n = 10000; // 計算回数

Quaternion testQuaternion = new Quaternion(1, 0, 0, 1);
Vector3 testVector3 = new Vector3(1, 2, 3);

Vector3 vt1 = Vector3.zero;
var sw1 = new System.Diagnostics.Stopwatch();
sw1.Start();

for (int i = 0; i < n; i++)
{
    vt1 = testQuaternion * testVector3;
}

sw1.Stop();
UnityEngine.Debug.Log(vt1);
UnityEngine.Debug.Log(sw1.Elapsed);

vt1をログに出力しているのはコンパイラによる最適化防止です。

MultiplyPoint3x4(Vector3)

int n = 10000; // 計算回数

Quaternion testQuaternion = new Quaternion(1, 0, 0, 1);
Vector3 testVector3 = new Vector3(1, 2, 3);

Vector3 vt2 = Vector3.zero;
var sw2 = new System.Diagnostics.Stopwatch();
sw2.Start();

Matrix4x4 testMatrix4x4 = Matrix4x4.Rotate(testQuaternion);
for (int i = 0; i < n; i++)
{
    vt2 = testMatrix4x4.MultiplyPoint3x4(testVector3);
}

sw2.Stop();
UnityEngine.Debug.Log(vt2);
UnityEngine.Debug.Log(sw2.Elapsed);

vt2については同上。
Matrix4x4構造体を生成する処理も含めないと不公平なので計測に含めています。

ベンチマーク結果

計算回数	Quaternion * Vector3	MultiplyPoint3x4(Vector3)
n=1000	0.0359ms	0.1265ms
n=7500	0.2377ms	0.2374ms
n=10000	0.3125ms	0.2777ms
n=1000000	31.0942ms	16.7268ms

PC (Core i7-8700Bでの計測。参考程度にどうぞ)

n=1000000など実際に計算することはないでしょうが、参考用として載せました。
n=7500辺りからMultiplyPoint3x4が処理速度で上回ります。

ベンチマーク用のコードでは同じベクトルを計算させましたが、実際には異なるベクトルを求めるでしょう。
MultiplyPoint3x4()に計算させたいVector3を与えればそのクォータニオンで計算したVector3が返ってくるので心配はありません。

計算を7500回以上実行しない場合は逆にパフォーマンスが落ちるところが難点ですね。

なんで速くなるの？

Quaternion * Vector3は乗算演算子をオーバーロードして実装されており、Unityのソースコードから実際の処理を見れます。

// Rotates the point /point/ with /rotation/.
public static Vector3 operator*(Quaternion rotation, Vector3 point)
{
    float x = rotation.x * 2F;
    float y = rotation.y * 2F;
    float z = rotation.z * 2F;
    float xx = rotation.x * x;
    float yy = rotation.y * y;
    float zz = rotation.z * z;
    float xy = rotation.x * y;
    float xz = rotation.x * z;
    float yz = rotation.y * z;
    float wx = rotation.w * x;
    float wy = rotation.w * y;
    float wz = rotation.w * z;

    Vector3 res;
    res.x = (1F - (yy + zz)) * point.x + (xy - wz) * point.y + (xz + wy) * point.z;
    res.y = (xy + wz) * point.x + (1F - (xx + zz)) * point.y + (yz - wx) * point.z;
    res.z = (xz - wy) * point.x + (yz + wx) * point.y + (1F - (xx + yy)) * point.z;
    return res;
}

n=10000なら上記の処理が10000回動くわけですね。

Matrix4x4.Rotate()もほぼ同じ処理を行っていますが、大事なのは最初の1回だけ行うということです。
以降は以下の処理でベクトルを計算します。

// Transforms a position by this matrix, without a perspective divide. (fast)
public Vector3 MultiplyPoint3x4(Vector3 point)
{
    Vector3 res;
    res.x = this.m00 * point.x + this.m01 * point.y + this.m02 * point.z + this.m03;
    res.y = this.m10 * point.x + this.m11 * point.y + this.m12 * point.z + this.m13;
    res.z = this.m20 * point.x + this.m21 * point.y + this.m22 * point.z + this.m23;
    return res;
}

こちらの方が明らかに速く計算できることが分かります。
3～4回呼び出すだけでパフォーマンスが逆転しそうなものですが、構造体を作るコストの関係などで、計算回数が7500回とかなり多くなければパフォーマンスが逆転しないようです。
（コスト重くない……？）

MultiplyPoint()じゃなくていいの？

MultiplyPoint3x4()の他にMultiplyPoint()もあります。

あわせて読みたい

Matrix4x4-MultiplyPoint - Unity スクリプトリファレンスこの行列で位置を変換します (一般)。

Unityのドキュメントを見ると「MultiplyPoint()は速度が遅いが射影変換を扱うことができる」と書いてあります。

Matrix4x4.Rotate()を使って変換行列を作る場合はMultiplyPoint3x4()でOKです。

コードから紐解いてみましょう。
まずはMatrix4x4.Rotateの処理を見てみます。

public static Matrix4x4 Rotate(Quaternion q)
{
    // Precalculate coordinate products
    float x = q.x * 2.0F;
    float y = q.y * 2.0F;
    float z = q.z * 2.0F;
    float xx = q.x * x;
    float yy = q.y * y;
    float zz = q.z * z;
    float xy = q.x * y;
    float xz = q.x * z;
    float yz = q.y * z;
    float wx = q.w * x;
    float wy = q.w * y;
    float wz = q.w * z;

    // Calculate 3x3 matrix from orthonormal basis
    Matrix4x4 m;
    m.m00 = 1.0f - (yy + zz); m.m10 = xy + wz; m.m20 = xz - wy; m.m30 = 0.0F;
    m.m01 = xy - wz; m.m11 = 1.0f - (xx + zz); m.m21 = yz + wx; m.m31 = 0.0F;
    m.m02 = xz + wy; m.m12 = yz - wx; m.m22 = 1.0f - (xx + yy); m.m32 = 0.0F;
    m.m03 = 0.0F; m.m13 = 0.0F; m.m23 = 0.0F; m.m33 = 1.0F;
    return m;
}

注目すべきは19-22行目のそれぞれの最後の代入です。
次にMatrix4x4.MultiplyPointの処理を見てみます。

// Transforms a position by this matrix, with a perspective divide. (generic)
public Vector3 MultiplyPoint(Vector3 point)
{
    Vector3 res;
    float w;
    res.x = this.m00 * point.x + this.m01 * point.y + this.m02 * point.z + this.m03;
    res.y = this.m10 * point.x + this.m11 * point.y + this.m12 * point.z + this.m13;
    res.z = this.m20 * point.x + this.m21 * point.y + this.m22 * point.z + this.m23;
    w = this.m30 * point.x + this.m31 * point.y + this.m32 * point.z + this.m33;

    w = 1F / w;
    res.x *= w;
    res.y *= w;
    res.z *= w;
    return res;
}

this.m30とthis.m31とthis.m32は0、this.m33は1です。なので9行目の変数wの結果は必ず1になります。
ということは、11行目は1÷1なので変数wの結果は必ず1になります。

1に何を掛けても意味がないので、以降の計算は行わなくても戻り値が同じになることが分かります。
この計算を省いたのがMultiplyPoint3x4()です。

// Transforms a position by this matrix, without a perspective divide. (fast)
public Vector3 MultiplyPoint3x4(Vector3 point)
{
    Vector3 res;
    res.x = this.m00 * point.x + this.m01 * point.y + this.m02 * point.z + this.m03;
    res.y = this.m10 * point.x + this.m11 * point.y + this.m12 * point.z + this.m13;
    res.z = this.m20 * point.x + this.m21 * point.y + this.m22 * point.z + this.m23;
    return res;
}

つまりMultiplyPoint()を使おうがMultiplyPoint3x4()を使おうが結果は変わらない、ということです。
（あくまで今回のケースでは、ですが）

また、MultiplyPoint()に対してMultiplyPoint3x4()は2倍近く高速です。
乗算・除算の回数がほぼ半減することからも分かります。
ドキュメントでも言及されていますし、わざわざMultiplyPoint3x4()メソッドが用意されているということはこういうニーズに目を向けているのでしょうね。

ちなみにMultiplyPoint3x4()ではなくMultiplyPoint()を使った場合、n=10000の条件で計測すると0.4032msでした。
0.3125msを下回っていないので1万回同じQuaternionで計算しても元よりパフォーマンスが悪化する始末です。
素直にMultiplyPoint3x4()を使いましょう。

最後に

計算量がO(n^2)な処理でQuaternion * Vector3を行っていて「結構処理に時間かかっているなぁ」と思ったので色々調査した時のメモです。

せっかく調査したので書きましたが、私が作っているものでは効果がありませんでした。
（n=20程度でパフォーマンスが逆転してくれないと割に合わなかったため。だってソース読む限りではちょっと期待しちゃうじゃん……）

限られたパフォーマンスチューニングですが、何かの役に立つかもしれませんので、備忘録として残しておきます。