ママ、行列なんていらない

 (enkimute.github.io)
2 ポイント 投稿者 GN⁺ 2024-02-29 | 1件のコメント | WhatsAppで共有
  • 3Dグラフィックスで慣習的に使われてきた 4x4 行列の代わりに、Euclidean PGA を glTF 互換のフォワードレンダラーへ徹底的に適用してみる実験
  • 回転と移動は 8 個の float からなる PGA motor で表現され、一般的な motor 合成は 4x4 行列積の 64 乗算・48 加算より少ない 48 乗算・40 加算で処理できる
  • 点変換は単純展開だと行列より高コストだが、正規化条件を使った sandwich product により 21 乗算・18 加算まで削減でき、方向や基底方向の変換はさらに安価になる
  • tangent space normal mapping では normal と tangent を tangentRotor に置き換え、頂点データを 12 float から 9 float に削減しつつ、world-space 変換コストも行列方式に近い 47 乗算・38 加算程度に抑えている
  • 実際の glTF コンテンツと連携するには、ロード時に行列を motor に変換し、uniform scale は別の float として追跡する必要があり、non-uniform scale には制限付き処理か 4x4 行列の代替経路が必要になる

PGAで作る行列なしフォワードレンダラー

  • プロジェクトは Look, Ma, No Matrices で、行列なしフォワードレンダラー の実装を目指している
  • 2019 年の SIGGRAPH 以降、Geometric Algebra、とくに Euclidean PGA はグラフィックスや機械学習コミュニティで注目を集めてきたが、従来の 3D グラフィックスでは dual quaternion を PGA motor と呼び直す程度にとどまることが多かった
  • この実装では glTF 互換の 3D エンジンに PGA algebra を統合し、単なる代数名の言い換えではなく、グラフィックスパイプラインの複数の部分を PGA ベースで再構成している
  • 基準実装は Khronos glTF viewer であり、最適性能を狙った実装というより、妥協なく行列を置き換える実験に近い
    • 最終的には hybrid solution のほうがより良い選択になる可能性が高い

4x4 行列を疑う理由

  • 4x4 行列はグラフィックス API や GPU 固定機能パイプラインで長年中心的な役割を担ってきており、今でも一般的なフォワードレンダリングの基本ツールである
  • 現代の GPU は固定機能パイプラインというより プログラマブルなスカラープロセッサ に近く、行列中心の表現が必須とは限らない
  • 実際の 3D エンジンでは、多くの行列が回転と移動だけを含む 直交行列 である
  • PGA motor manifold は Euclidean motion 全体をより低い計算・メモリコストで表現でき、quaternion や dual quaternion も変換なしに内包できる

PGA のデータ表現と基本演算

  • PGA algebra は 4 つの基底ベクトル e0〜e3 から生成される
    • e1, e2, e3 はそれぞれ x=0, y=0, z=0 平面に対応する
    • 特殊な退化ベクトル e0 は無限遠平面を表す
  • シェーダーでは GLSL の組み込み型を使い、演算子オーバーロードなしで加算、減算、スカラー倍を利用する
    • motor mat2x4
    • line mat2x3
    • point vec3
    • direction vec3
  • 一般的な PGA motor 合成は geometric product で行う
    • 4x4 行列積: 64 乗算、48 加算
    • 一般 motor 合成 gp_mm: 48 乗算、40 加算
  • 特殊な変換の組み合わせではさらに安価な演算が可能
    • gp_rr: 16 乗算、12 加算
    • gp_tt: 0 乗算、3 加算
    • gp_rt / gp_tr: 12 乗算、8 加算
    • gp_rm / gp_mr: 32 乗算、24 加算
    • gp_tm / gp_mt: 12 乗算、12 加算

点・方向変換の最適化

  • PGA で motor M によって点 p を変換するときは sandwich product M p M̃ を使う
  • 単純展開では 33 乗算・29 加算となり、行列-ベクトル積の 16 乗算・12 加算より高コストになる
  • 正規化された motor が M M̃ = 1 を満たすことを利用して式を変形すると、点変換を 21 乗算・18 加算 まで削減できる
  • 方向、つまり無限遠点は暗黙の e123 係数が 0 なのでさらに安価になる
    • 一般的な方向変換: 18 乗算、12 加算
    • 基底方向変換は、たとえば x 軸変換を 6 乗算、4 加算まで落とせる
  • この基底方向最適化は、後の tangent frame 処理において「行列が常に最速」という通念を揺さぶる根拠にもなる

正規化、平方根、指数・対数写像

  • PGA motor の squared pseudonorm は M M̃ = a + b e0123 という形の Study Number になる
  • 正規化は単純なベクトル正規化ではなく、結果の motor が orthonormal transformation になることを保証する手順である
    • 一般 motor 正規化の実装コスト: 21 乗算、5 加算
    • 純粋な translation や rotation ではさらに効率的な版を使える
  • 2 点・2 線・2 平面 a, b の間の rigid transformation は M = sqrt(b / a) で表現される
    • 同種の 2 要素に対する geometric product ba は、a から b へ至る変換の 2 倍に相当する motor を作る
    • sqrt M = normalize(1 + M) の形で計算できる
  • PGA motor の logarithm は scaled line であり、scaled line は exponentiation によって回転 motor を生成できる
  • 一般的な 4x4 行列の exponential map は数値的に高コストだが、PGA motor manifold では 効率的な closed form が可能である

逆元と motor の factorization

  • Geometric Algebra では、正規化されたオブジェクトの逆元を効率よく計算できる
    • plane inverse: 自分自身
    • line inverse: 符号反転
    • point inverse: 符号反転
    • motor inverse: reversion
  • 一般の bivector が Plücker condition を満たさず単一の line を表さない場合は、Study Number inverse を用いて逆元を計算する
  • レンダリング実装では 2 種類の factorization が使われる
    • Euclidean factorization: motor を原点まわりの回転の後に平行移動する形へ分解する
    • Invariant factorization: motor を互いに可換な translation と rotation に分解するもので、3D では Mozzi-Chasles theorem として知られる形
  • tangent frame と object-to-world motor を合成する際には、translation に対して不変な frame の性質により Euclidean factorization が有用である

glTF 行列と scale 処理

  • 既存の glTF コンテンツと相互運用するには、ロード時点で行列を PGA motor に変換する必要がある
  • 4x4 orthogonal matrix は quaternion との同型性を利用して motor へ変換する
    • import されたすべての matrix と transformation はロード時に変換される
  • PGA motor は rigid body transformation を扱うため、scaling は含まない
  • uniform scaling は rotation と translation に対して不変なので、各ノードごとに float 1 つで追跡する
    • 各要素の total scale は、自身の scale と parent scale の積で計算する
    • vertex にはロード時、または vertex shader の最初の段階で total scale を適用する
    • translation には load time と animation update 時に parent scale を適用する
  • 約 400 件のランダムな glTF ファイルサンプルでは、scale animation があるケースは 0.5% 未満で、固定の uniform scale はかなり多かった
  • non-uniform scaling は rotation に対して不変ではないため、より厄介である
    • 一般的な non-uniform scale の処理には 4x4 matrix の代替経路が避けられない
    • サンプル glTF では non-uniform scale が leaf node にのみ適用された例が見つかっており、この場合は animation key に影響させず、ほかの変換の前に別途 scale を適用する

Model-View-Projection の置き換え

  • フォワードレンダラーは object space の mesh geometry を screen space に変換し、各 triangle が覆う pixel を決定する
  • 一般的なパイプラインの model、view、projection matrix のうち、model と view を PGA motor に置き換える
    • vertex position は sw_mp
    • normal と tangent 方向は sw_md
  • projection matrix は通常 non-zero entry が 5 個しかないため、PGA へ無理に置き換えず、直接 projection expression を使う
  • CPU 側の scene graph hierarchy update では、matrix composition の代わりに motor composition を使うことで計算量が減る
  • GPU 側の vertex 変換は単純比較では motor が不利に見えるが、tangent frame の表現を変えると結果は変わる

tangent space normal mapping の最適化

  • 一般的な tangent space normal-mapped mesh の vertex shader では、position、normal、tangent を変換しなければならない
  • normal、tangent、bitangent は orthonormal frame を成すため、PGA では canonical basis frame から目的の tangent frame へ至る tangentRotor で表現できる
  • この方式は vertex descriptor を縮小する
    • 従来: position 3 + normal 3 + tangent 4 + uv 2 = 12 floats
    • PGA 方式: position 3 + tangentRotor 4 + uv 2 = 9 floats
    • 頂点あたりの float 数は 25% 減少する
  • tangentRotor は double cover を持ち、scalar coefficient の符号を古典的な handedness flag と対応させて even/odd k-reflection を区別する
    • signed zero に依存し、vertex shader では sign(1/tangentRotor.x) で handedness を取り出す
  • position、normal、tangent を 4x4 matrix で変換すると、合計 48 乗算、36 加算が必要になる
  • PGA 方式では、tangent frame 全体を一度に変換してから normal と tangent を抽出する
    • tangent frame 合成: 16 乗算、12 加算
    • normal/tangent 抽出: 9 乗算、8 加算
    • position 変換: 21 乗算、18 加算
    • handedness 抽出用の乗算 1 回
    • 合計 47 乗算、38 加算
  • 頂点変換コストは行列方式とほぼ同じで、transform の保存は 32 floats から 8 floats に減る

fragment shader と baked texture の制約

  • 既存コンテンツを読み込むには、fragment shader 段階で再び TBN matrix が必要になる
  • baking tool は high-detail mesh を low-detail mesh に焼き込む過程で、vertex normal と tangent を triangle face 上で補間し、各 fragment で直交 TBN matrix を構成して tangent space normal texture を作る
  • basis vector の補間は行列方式特有の典型的な誤差を生み、その誤差はすでに texture に baked されている
  • そのため、この実装では tangentRotor から normal と tangent vector を明示的に抽出する
  • baking tool まで制御できるなら、tangentRotor をそのまま fragment shader へ渡し、正規化して sampled normal の変換に使える
    • TBN matrix を作る必要がない
    • vertex shader での normal/tangent 抽出が不要になる
    • varying parameter を 1 つ減らせる
    • fragment shader の高コストな orthogonalization も取り除ける

motor skinning と animation blending

  • PGA motor は dual quaternion と同型なので、skinning に自然に適用できる
  • inverse bind matrix を motor に変換したあと、dual quaternion skinning と同じパターンで bone motor を blend する
  • blend される transformation は shortest arc をたどるよう符号を揃え、結果の transformation を再び正規化する
  • animation blending も同様の方法で、CPU 上で PGA motor を直接 blend してから正規化する

行列置換実験の結果

  • glTF 互換フォワードレンダラーで PGA だけを使って行列を置き換える実装は可能である
  • 変換コストがより高くなるという予想は、tangent frame 表現と sandwich product 最適化を適用すると単純ではなくなる
  • tangent space normal mapping の一般的なケースでは、PGA motor 方式は vertex shader コストを行列方式とほぼ同等に保ちながら、vertex memory footprint を大きく削減する
  • 同じ保存容量で約 33% 多くの vertices を格納できるというメモリ改善がとくに大きい
  • この技法は vertex shader コストをほとんど増やさず、パイプラインの残り部分を変更しない drop-in replacement として既存の 3D エンジンへ適用できる

関連記事

1件のコメント

 
GN⁺ 2024-02-29
Hacker News のコメント

  • 好きな数学／グラフィックス系 YouTube クリエイターの一人である Freya Holmér が、少し前に幾何代数の入門動画をとてもよく作っていた: https://www.youtube.com/watch?v=htYh-Tq7ZBI&ab_channel=Freya...
    3D グラフィックス、特にスプライン／ベジェ曲線に興味があるなら、この人の動画は全部見る価値がある
    個人的には線形代数はずっと難しく感じていたが、こういう Clifford 代数アプローチはずっと直感的に感じる

    • 本当に良い発表で、https://enkimute.github.io/ganja.js/ を思い出した
      このライブラリは原文の著者である enkimute が作ったもので、単一ファイル・ビルド不要のスクリプトでありながら、N 次元代数とレンダリング支援まで提供する、かなり驚くべきライブラリ
    • この記事はその人の話だと思っていた。スプラインとベジェの動画もあわせて楽しく見たし、発表は決して急いでいる感じがなく、要点にうまく入っていく
    • YouTube のコメントにも、意外と良い補足説明や質問がある
      例えば積の非可換性のように、Freya が少し早く流したり省略したりした部分についての説明がかなり良い

  • 幾何代数はしばらく完全に謎だったが、最終的にこう理解したら腑に落ちた。単なる多項式の掛け算で、掛ける順序が重要な量があり、掛け算表が変なだけ。例えば i*i = 1, i*j = -j*i
    たいていの入門資料は、2 つのベクトルの幾何積 (x1*i + y1*j) * (x2*i + y2*j) を深遠で神秘的なものに見せるが、実際には新入生の代数で習う FOIL 展開と同じ:
    (x1*i + y1*i)(x2*i+y2*j) = x1*x2*i*i + x1*y2*i*j + y1*x2*j*i + y1*y2*j*j = (x1*x2 + y1*y2) + (x1*y2 - y2*x1)*i*j
    最初の括弧内の値はおなじみの内積で、2 番目の括弧内の値はおなじみの外積に相当するが、i*j という新しい次元の基底で表される。そして外積と違って任意次元に一般化でき、幾何代数ではこれを**外積（wedge product）**と呼ぶ
    これを理解すると、回転公式の導出なども簡単になる。代数で身につけた技法を、幾何の問題解決にそのまま適用できるから

    • 別のコメントに出ていた https://youtu.be/htYh-Tq7ZBI?si=lOmsCL2DoqUCQgh1&t=1540 で、Freya が公理を 1 つに減らす説明を見事にしていた
      ベクトルをそれ自身と掛けた値を、そのベクトルの長さの二乗と定義すれば、残りは単純な多項式の掛け算からすべて導かれる。かなり美しい
    • この説明は興味深い対比を示している。数日前、誰かが数学の授業はなぜ演算の方法と理由を教えず、公式だけ渡して計算させるのかと尋ねていたが、ここでは演算がなぜ成り立つのかよりも、何をしているのかに焦点を当てている
      「どう動くのか？」と「なぜ動くのか？」は、数学教師がバランスを取るべき 2 つの問いであり、1 つの講座で常に両方にうまく答えるのは難しい
    • 2 番目の項は外積ではなく、外代数の積、またはバイベクトル。外積は 3 次元でしか動かないが、外代数の積はより高い任意次元でも可能
      3 次元ベクトル 2 つの外積は、その 2 つのベクトルが作る平面に垂直な別のベクトル。一方、外代数の積は 2 つのベクトルの間の平行四辺形を掃く 2-ベクトル、つまりバイベクトルであり、2 つのベクトルが載っている平面上にある。3 次元では、外積ベクトルがこのバイベクトル平面に垂直になる
    • 数学を学ぶうえで最も時間がかかることの一つは、ほとんどのものが可能な限り最も単純な方法で定義されている、という事実
      特にベクトル空間 V 上で双線形積 m:V x V -> V を定義するには、基底ベクトルの組についてだけ m を定めることと正確に同じ。これを「テンソル積の普遍性」と呼べば、たぶんただ「ああ、なるほど」と言うことになる

  • 回転補間には幾何代数、クォータニオン、さらには行列全体の補間まで複数のアプローチがあって興味深い: https://www.gamedev.net/tutorials/programming/math-and-physi...
    ただしコードを手で最適化してしまうと、最終的なコードはほとんどのアプローチでかなり似たものになる。違いは、規則と可能性をどう理解するかにある
    少し知っている範囲では、幾何代数が最も一貫していて有能なアプローチに見える。なじみがなく、最初に受け入れるにはかなり大変だが、その壁を越えた人たちは気に入っている
    逆に、みんなクォータニオンを使いながらも理解できないと不満を言い、可視化するには本が 1 冊必要だと言う。Andrew J. Hanson と Steve Cunningham の『Visualizing Quaternions』のような本のこと

    • 数学者ではないし仕事でも幾何をそれほど使わないが、趣味で幾何代数を学んでいて、以前はクォータニオンも学ぼうとしたことがある
      幾何代数は面白く、クォータニオンは面白くない。幾何代数は理解できた気がするが、クォータニオンは講義や問題を追っても理解できていないことだけは確かだった。今は幾何代数を少し知ったので、ようやくクォータニオンもある程度わかった気がする
    • 『Naive Lie Theory』はすばらしい本で、第 1 章でクォータニオンを教えている
      https://www.goodreads.com/en/book/show/4419538

  • このテーマに興味があるなら、Grassman/Clifford/幾何代数の概念を概観する良いスライドがある: http://www.terathon.com/gdc12_lengyel.pdf
    もう一つ良いサイトもある: https://mattferraro.dev/posts/geometric-algebra

  • Sudgy のすばらしい「A swift introduction to projective geometric algebra」も外せない: https://www.youtube.com/watch?v=0i3ocLhbxJ4
    そして代表的な参考サイトは https://bivector.net
    教授、研究者、愛好家が1000人以上いる bivector Discord にも参加できる: https://discord.gg/vGY6pPk

    • その発表の著者である Eric Lengyel は『Foundations of Game Engine Development, Volume 1: Mathematics』も書いており、第4章が同じテーマを扱っている

  • 正直、幾何代数は何に何を掛けるのかに注意しないと、あらゆる 混合要素 が生まれる仕組みがあまり好きではなかった
    n 次元空間だったものに対して最大 2^n 個の項が必要になるのも扱いにくく感じる
    幾何、つまり内積をよりうまく扱えるはずだと思うが、単に外積と Hodge 星作用素、または musical isomorphism を使ってはいけない理由について、納得できる説明を見たことがない
    バイベクトル u^v をその平面での回転 e^(u^v)t に変える「魔法」のようなものも、本質的には musical isomorphism によって 2-形式 u^v を線形自己同型に変え、e^(u^v)t を行列指数として理解させるものだ
    また、よく出てくる例として Maxwell 方程式を1つの方程式にできるという点があるが、微分形式を使えば、すでに別々の理由で成り立つ2つの方程式に要約できるので、それを1つにまとめる効用が理解できなかった

    • 「n 次元空間だったものに対して最大 2^n 個の項が必要になる」という節約は、ときには錯覚だ
      例えば法線ベクトルは位置ベクトルとは違う変換を受ける。両方を同じデータ構造で表現することはできるが、その中にどの種類のベクトルが入っているのかを追跡し、コードのあちこちにそれぞれ異なる扱いをする特殊ケースを入れなければならない
      幾何代数はこれに正面から向き合い、ベクトルには (i,j,k) という基底を使い、別の種類には (j*k, k*i, i*j) という別の基底を使う
      1つの方程式が2つや4つより優れているという意味で、より高次元の空間が低次元よりもむしろ保存面で効率的になる良い例だ
      電場は磁場と、ベクトルがバイベクトルと異なるのとかなり似た形で異なる。電場と磁場を別々の方程式で特殊扱いすることもできるし、1つの方法で均一に扱うこともできる
    • 混合要素こそが重要な部分だ
      w=1, x,y,z=0 のクォータニオンは恒等であり、w=0, x=1 や w=0, x=y=0.7 のようなクォータニオンは180度回転にしか対応しない
      任意の回転がほしければ、その2つの組み合わせが必要だ。「この直線の周りの180度回転を少し、そして0度回転/恒等を少し」混ぜるということだ。スカラーとバイベクトルを一緒に持つというのは、まさにこれを意味する
      外積と内積で「注意深く」混合を避けようとしているなら、それは使い方を間違えている。幾何積 が主役であり、非常に優れた混合を作り出す
    • 混乱がすでに存在しているという点には同意する。従来のアプローチは、その混乱をただ敷物の下に掃き込んでいるだけだ
      例えば法線を扱うなら、互いにかなり異なる変換を受ける n 次元空間を少なくとも2つは追跡しなければならない
      点、平面、直線、法線、平行移動、回転をすべて1つの multivector 型と一貫した規則で表現するのは、理解してしまうとかなり解放感がある。まだ自分も習得中ではあるが

  • 下の方のアニメーション補間は本当に見事だが、ページの他の部分のモデルはもう少し おとなしかったら いいのにと思う
    数学は小さな象のチアリーダーがいなくても十分難しい

    • むしろ逆だ。あの象のような応援がなかったら、ページの最後までたどり着けなかったはずだ

  • 書き手が見ているなら、PGA という略語を初めて使うときに定義してほしい

    • 気になる人のために言うと、PGA は projective geometric algebra、つまり 射影幾何代数 だ
      作業対象の空間の基底ベクトルに零基底ベクトルを1つ追加する。これにより、原点を通らない幾何オブジェクトも代数で表現できる
    • 特に「Fast PGA」を FPGA と書いていた箇所はかなり紛らわしかった
    • 修正した。mea maxima culpa

  • こうしたアルゴリズムは GPU を考慮しても効率的なのだろうか？
    GPU は行列演算にうまく適合しているという漠然とした印象があるが、幾何代数の定式化を使うとその利点を失い、実際には先行できないのではないかと気になる
    よく分かっていない推測なので、間違っていたら訂正してほしい

    • GPU 標準に行列-行列積と行列-ベクトル積があるからといって、GPU 企業が必ずそれを高速化していると思うのは非常によくある誤解だ
      実際にはシェーダーコア全体がすでに SIMD なので、必ずしもそうできるわけではない。そうする GPU もあれば、そうしない GPU もある
    • プログラミングするときは2つのことを見極める必要がある。計算したい量は何か、そしてそれを計算する最も効率的な方法は何か
      PGA は理解するうえで少なからず負担があるが、1つ目を扱うには非常に良い方法だ。いずれにせよ普通は、最も単純で実装しやすい方法を先に試すのがよい
      PGA で1つ目を解決して得られた実装は、プログラムの残りをプロトタイプ化し、ベンチマークして本当のボトルネックを見つけるには十分だ。幸い、ほとんどの場合それが最速の計算法であるか、ボトルネックにならない程度には十分速い
      たとえボトルネックになっても、解こうとしている問題を深く理解させてくれる。十分速くなることを願ってサイクル削減を始める前に、そうした理解を備えておく方がよいと思う
    • この記事はまさにその内容を扱っている。要約すると、おおむね同程度になり得る

  • これは進歩の先端で起きている微差の争いのように見える
    3D スケルタルアニメーションがいまだに GPU で 4x4 行列 を使っているということは、Half-Life 1 の頃に CPU でこの用途のために開発された数学が今なお最前線だということだ。1998年から2024年まで26年だ
    1000年後も 3D アニメーションはそのままだろう

  • この記事は理解の範囲を超えているが、タイトルを見て、簡単な 3D レンダラー を作っていた実験を思い出した
    線形代数を学ぼうとして何度も失敗したあと、シャワー中に 3D 回転は単に3つの 2D 回転で、それならすでに知っていると思いついた。1時間ほど後には、遠近法まで備えたワイヤーフレームの 3D レンダラーができていた
    みんな一度試してみることを勧める