YLog

陰的に定義された曲面の漸進的レイトレーシング

陰的に定義された任意の曲面を高速に描画できる、インタラクティブアプリケーション用のレンダリング手法を思い付いたので試しに実装してみました。 ShaderToyでデモをご覧になれます。

背景

レイトレーシング

レイトレーシングは、出力画像を仮想カメラの受像面に対応させ、各画素に入射する光の伝播経路を追跡することで、三次元画像の描画を行う手法です。

厳密に説明するとレンダリング方程式などを利用することになりますが、本記事の主題ではなく、あと僕自身が詳しくない為省くことにして、レイトレーシングによるレンダリングは単純な場合は次のプロセスで構成されます。

  1. レイキャスティング: 各画素から仮想的な光線(レイ)を発射し、レイが衝突する物体を探索する処理。レイの方向は実際の光とは逆方向である点がポイントです。
  2. シェーディング: 光が物体に当たると光は様々な方向に反射します。1で見付けた物体上の点において、反射した光がどの程度カメラの方向に飛来してくるかを求める処理がシェーディングです。
  3. 再帰: 物体に入射する光は別のもう一つの物体から来た光かもしれないので、シェーディングを行う際に再帰的にレイトレーシングを行うことがあります。この際に発射するレイは二次レイと呼びます。

この中のレイキャスティングが本記事のメインテーマです。

レイキャスティング

レイトレーシングを行う際、光線と物体の衝突地点を探索する処理がレイキャスティングです。 数学的には、連続関数 $f(\vec{x})$ について、対象とする物体 $f(\vec{x}) = 0$ と、光線 $\vec{x} = \vec{s} + t\vec{d}$ (ただし $\left\Vert \vec{d} \right\Vert = 1$) を連立した $t$ に関する連立方程式、すなわち $t$ に関する方程式

の解の最小値を探索する処理として表されます。

レイキャスティングは、対象とする物体の表し方によって、異なるアルゴリズムを使い分ける必要があります。

物体が平面、三角形、あるいは球体のように簡単な式で表せる場合、衝突地点を直接計算できることがあります。例えば、球 $f(\vec{x}) = \left\Vert \vec{x} - \vec{c} \right\Vert - r$ の場合、これと光線の方程式を連立して得られる二次方程式 $t^2+(2(\vec{s} - \vec{c})\cdot\vec{d})t+((\vec{s} - \vec{c})^2-r^2)=0$ を解の公式で解くことにより、$t$を計算することができます。

しかし、$t$を解析的に計算するのが難しい場合、反復的な手法を用いざるを得なくなります。 単純な反復手法は、ステップサイズ $s_n$ に基いて $t$ の推定値を次の式により更新していき、$f_t(t_n)$の符号が変化した (すなわち、物体の表面を交差した)、あるいは何らかの尺度により、物体にある程度近づいたと判断できた時点で計算を打ち切ります。

ステップサイズ $s_n$ が小さすぎると収束までのステップ数が増大してしまいますが、一方で大きすぎると物体との交点を見逃して光線が物体を突き抜けてしまい、誤った結果を得てしまいます。

突き抜けが発生しない $s_n$ の上界は物体までの距離により変化するので、固定値を用いた場合は突き抜けが発生する可能性があることは明らかです。 物体を突き抜けないようにステップサイズを動的に定める方法として、距離場によるレイマーチングが挙げられます。 このレイマーチングはアルゴリズムが単純で理解しやすく、また物体の距離関数の近似値としていくつかの条件を満たす距離場関数さえ与えられば実現でき、さらに、その距離場に対し様々な幾何変換を適用したり、複数の距離場をブーリアン演算により結合したりする簡単な方法が知られているため、最近のデモシーンでは人気の手法です。

しかし、この方法でも適切なステップサイズの上界を決定できないことあります。 例として、アプリケーションのユーザが $f(\vec{x})$ を自由に指定できる場合、距離関数の計算が出来ないため、物体の突き抜けを避けることは出来ません。

確かに、interval arithmeticを使用して突き抜けが起こらないようにできる方法は存在します。 Interval arithmeticは、関数の入力値の区間が与えられた時に、出力が取りうる値を区間として求めるものです。 しかし、interval arithmeticは複雑な処理が必要(JavaScript実装を見ると分かります)で計算が低速であり、さらに、$f(\vec{x})$ が任意のプログラムとして表される場合は適用できません。 このほかに、interval arithmeticは出力される範囲を過大評価してしまうという問題があります。 これを解決するためにaffine arithmeticを用いた手法も研究されています。

インタラクティブ性

インタラクティブなアプリケーションでは、ユーザの操作に対し、迅速に結果が得られることが重要となります。 このため、最初の段階では不正確だが高速に計算できる手法で結果を表示し、徐々に正確な情報に更新できる方法が好まれます。

そこで、ステップサイズを大きくすることで高速に結果を得られ、最初は不正確であるが前フレームの情報を利用することで次第に正確な結果(光線の突き抜けが少ない画像)を得られるレンダリング手法について検討し、実際にGLSLでの実装を試みました。

手法

本手法では、各画素$\vec{p}$について以下の処理を行います。

  1. 初期化: 距離の推定値を $t’(\vec{p}) := d_f$ ($d_f$ はカメラからfar平面までの距離) として初期化する。
  2. 各フレームで以下の処理行う。
    1. レイキャスティング: レイキャスティングの最大ステップ数を $N$ とする。ステップサイズ $s_i$ を $s_i = t’(\vec{p})/N\ (i > 0), s_0 = s_1R$ ($R$ は $[0, 1]$ の一様乱数) として $t \in [0, t’(\vec{p})]$ の範囲でレイキャスティングを行う(すなわち、物体が$[0, t]$の範囲にあると仮定している)。この際、追加で、$t = (1 + \varepsilon) t’(\vec{p})$ の点でもサンプリングを行うようにする。
    2. 推定値の無効化: 物体との交点が見付からなかった場合、$t’(\vec{p}) := d_f$ として再度レイキャスティングを行う。それでも見付からなかった場合、その画素を透明色とし、当該フレームでの処理を打ち切る。
    3. 絞込み: レイと交差する物体が見つかった場合、二分法を用いて、交差点のより正確な $t$ の値を見付ける。
    4. シェーディング: シェーディングを行い、画素の色を設定する。
    5. 距離推定値の保存: $t$ を $t’(\vec{p}) := t$ として保存する。

レイキャスティング

本手法では、各 $t_i$ について $f_t(t_i)$ をサンプリングし、符号がはじめて変化したときに、あるいはもっと単純に、負になったとき、すなわち $f_t(t_i) \geq 0, f_t(t_{i + 1}) < 0$ となったときに $t \in [t_i, t_{i + 1]}]$ の範囲に物体との交点があると判定します。

本手法でレイキャステングを行う際、距離の推定値 $t’(\vec{p})$ をヒントとして用います。 この値は以下の不変条件を満たします。

$t’(\vec{p})$ は、当該画素に対応するレイと物体の交点のうち、現時点で発見されている交点の $t$ の最小値である。 ただし、交点が未発見の場合は $d_f$ である。

$t \in [0, t’(\vec{p})]$ の範囲でレイキャスティングを行うため、ほとんどの場合新たに見つかる交点は $t < t’(\vec{p})$ となるため、 $t’(\vec{p})$ は段々と小さな値に更新されます。 レイキャスティングの目標は $t$ が最小となる交点を発見することですので、本アルゴリズムのプロセスを反復することにより真値に近づいていくので、$t’(\vec{p})$ は交点の $t$ の近似値 (あるいは推定値) となる訳です。

サンプリング点は $s_0 = s_1R$ ($R$ は $[0, 1]$ の一様乱数) としてランダムに変化させます。 これは、サンプリング点を変化させないと、点と点の間にある交点を見逃す可能性がある為です。

シーンが変化(物体が変化、あるいは視点が移動等)した場合、上の不変条件が満たさなくなるかもしれません。 そこで、このような状況を検出するために、レイキャスティングの際に追加で $t = (1 + \varepsilon) t’(\vec{p})$ の位置 ($\varepsilon$ は、サンプリング点が物体の内側になるようにするための小さな値)でサンプリングを行います。 他の ($t \in [0, t’(\vec{p})]$ の) サンプリング点で交点が見付からなくても、上の不変条件が満たされていれば、$t’(\vec{p})$ 周辺で交点が見つかるはずです。

もし交点が見付からなければ、すなわち不変条件が破られたことを意味します。 このような場合、もしかすると $t’(\vec{p})$ は実際に存在する全ての交点よりもカメラに近い位置にある、すなわち交点は $t \in [0, t’(\vec{p})]$ には全く存在せず、$t \in [t’(\vec{p}), d_f]$ には存在する可能性があるので、推定値 $t’(\vec{p})$ はもはや有効ではありません。 このため、 $t’(\vec{p}) := d_f$ として推定値を初期状態に戻します。

二分法による絞込み

各 $t_i$ について関数をサンプリングすることで、物体との交点が存在しうる区間 $t \in [t_i, t_{i + 1]}]$ を発見することができます。 しかし、シェーディングを正確に行うためには、$t$ をもう少し正確に求めたいです。

この区間において $f_t(t) = 0$ を二分法で解くことにより、この区間を更に狭めることができます。区間内に交点が複数ある場合はそのうちのいずれか、1つある場合(両端で符号が異なるので、少なくとも一つは存在する)はその交点の $t$ の近似値を求めることができます。

シェーディング

シェーディングを行うためには交点における物体の法線を求める必要がありますが、法線は数値的または解析的に $\mathrm{grad} f(\vec{x})$ を求めることにより計算できます。

残りの処理は本記事の範囲外になると思われるので省略は省きますが、各光源の寄与をDisney principled BRDF等で求めて合計したり、その他お好きなアルゴリズムと組み合わせれば良いと思います。

結果

Shadertoyにて動作例をご覧になれます。本記事のアルゴリズムと微妙に異なりますが、原理はほとんど同じはずです(記事はShadertoyを元にして整理しながら書いたので、記事のほうがもっと洗練されているかも…)。

  • 初期版
  • バージョン2 - 見栄えを良くするためにPBRシェーディング + ポストプロセスを追加してみました

本記事の方法を使用した場合と、使用せず同じステップサイズでレイキャスティングを行った場合の結果がこちらになります。 右側は本記事の手法を使用していないため、一部のレイが薄い物体を突き抜け、透けて見えてしまっています。

補足

二次レイ

レイトレーシングの一般的な長所は、光線が当たった点から二次レイを発生することにより、反射や屈折などの物理現象を忠実にシミュレートできる点です。 しかし、時間の都合上、今回は二次レイを使用せずに、環境マップで反射を表現する実装に留めています。 二次レイに対しても本手法を適用する場合、二次レイ用にもう一つ $t’$ のバッファを持たせる必要があります。

アンチエイリアシング

デモではアンチエイリアリングを実装していませんが、実装する場合、いくつかのアプローチが考えられます。

単純な方法は、スーパサンプリングによるアンチエイリアシングです。 内部的に最終出力よりも高い解像度でレンダリングし、出力時にダウンサンプリングを行います。

もう一つの方法として、最近のゲームエンジンでよく用いられているように、TXAA (テンポラルアンチエイリアシング) という、以前のフレームの情報を利用する手法が考えられます。 TXAAを行う際は描画されるポリゴンの画面上の位置をサブピクセル単位でランダムに動かし、最近のフレームのレンダリング結果の重み付き平均を取ることで、実質的なピクセル当たりのサンプル数を増加させ、アンチエイリアシングを行います。単純に相対時刻に応じた重みによる重み付き平均を使用するとシーンに動きがあるときにモーションブラーのようなアーティファクトが生じてしまうため、各オブジェクトの速度ベクトルを利用して直前のフレームの情報の再投影を行ったり、各出力ピクセルのカラー値が想定範囲を超えた時に過去フレームの重みを減らしたりします。

本手法でTXAAを利用する場合、物体のシルエット境界周辺で品質が低下すると思われます。 TXAAでは画像を小刻みに動かすため、境界付近のピクセルは物体の内側に入ったり外側に出たりします。 本手法のアルゴリズムはピクセル単位で処理をしますが、各ピクセルについて物体までの距離はほとんど変化しないというのが本手法の前提なので、この前提が破られることになるため、境界付近では推定値の無効化が頻繁に発生し、本手法による品質の改善効果が期待できなくなります。