Jeffrey Cross
Jeffrey Cross

Quakeの高速逆平方根

逆平方根関数(1 / sqrt(x))は、ゲームエンジンの描画ループ中に、ベクトルを長さ1の「単位」ベクトルに正規化するために頻繁に使用されます。それら(Ax * Bx + Ay * By + Az * Bz)では、結果は2つのベクトル間の角度の余弦です。

表面がどのように向いているかを表すベクトル(表面の法線)と、太陽光の方向を表す2番目のベクトルがあるとします。日光ベクトルがサーフェス法線と平行である場合、つまりサーフェスが太陽に向いている場合、2つの正規化ベクトルの内積は0の余弦、つまり1です。サーフェスが太陽から90度の場合、ドット積は90のコサイン、つまり0です。その間にあるものはすべて0から1の間の値になります。これにより、本質的に、その表面をどれだけ明るく照らすべきかを記述できます。

さて、あなたは3Dゲームで見えるすべての三角形に対してこの計算を実行します、そしてあなたは1秒間に30回以上のすべてを行い、そしてあなたは基本的な点光源照明効果を持っています!ただし、これらの各三角形の単位ベクトルを計算するには、その逆平方根関数が必要です。平方根演算は遅いです。ドロー・ループごとに数千回それをしなさい、そしてあなたはあなた自身が遅いゲームを持っている。

しかし、限界の精度を捨てることを気にしないのであれば、もっと早い方法があります。

多くのゲームエンジンが使用する逆平方根関数がありますが、これはNvidiaのプログラマー、Gary TarolliによってQuake IIIで生まれたと噂されています。それはこのように見えます:

float InvSqrt(float x){float xhalf = 0.5f * x; int i = *(int *)&x; //浮動小数点数i = 0x5f3759df - (i >> 1)のビットを取得する//初期推定値y0 x = *(float *)&i; //ビットをfloatに戻すx = x *(1.5f-xhalf * x * x); //ニュートンステップ、繰り返しは精度return xを向上させます。 }

待ってください、それは何でしたか。

それで昔のことに、ニュートンは逆平方根を近似する賢い方法を思いつきました。まず、元の数xを2で割ります。それを「xhalf」と呼びましょう。それでは、逆平方根を合理的に推測します。それをgと呼びましょう。次に、これら2つの変数を使用してこの計算を実行します(これはInvSqrt関数の最後のステップとして認識されます)。

g = g *(1.5 - xhalf * g * g)

あなたが何度も何度もそれをするならば、各反復で更新されたgを代入することで、gはすぐにxの逆平方根に集中するでしょう!実際、最初に適切なgを選択すると、1回か2回の繰り返しで正しい値に非常に近づきます。

問題は、最初のgに対する最初の推定値をどのようにして見つけることができるかということです。ゲームエンジンのコーダーは、浮動小数点数が2進数で表現される方法をうまく使い、指数と仮数は科学表記法と同様に分解されます。 32ビット浮動小数点数では、左端のビットは符号ビットで、正の数の場合は0です。その後に8ビットの指数(負と正の指数を表すために127でバイアスされています)が続き、最後の23ビットは仮数を表します。

逆平方根を計算するには、基本的に指数に-1/2を掛ける必要があります。これらのビットを右にシフトすると(非常に速い操作)、指数に影響を与えるのは2で除算することです。ただし、符号を変更するには、指数を0から引く必要があります。ビットシフト演算でも影響を受けた仮数?

0x5f3759dfというマジックナンバーが出てきます。絶対にばかげていますが、0x5f3759dfからビットシフトの結果を引くと仮数は元の状態に近い値にリセットされ、指数は0から引かれます(127のバイアスを考慮して)。 。

結果は逆平方根に非常に近いです。ニュートンの方程式を1回通過するのに十分近い値で、実用的な目的のために十分正確な値になります。

QuakeのFast Inverse Square Rootを理解するFast Inverse Square Root - マジックナンバーの裏にある詳細と数学(PDF)

シェア

コメントを残します