こんこよー。Pocolです。
今日は…
[Peters 2015] Christoph Peters, Reinhard Klein, “Moment Shadow Mapping”, I3D 2015.
を読んでみようと思います。
いつもながら、誤字・誤訳があるかと思いますので，ご指摘頂ける場合は正しい翻訳例と共に指摘して頂けるとありがたいです。
Abstract
我々は、高速でフィルタリングされたハードシャドウのための新しい技術であるモーメントシャドウマッピングを紹介します。分散シャドウマッピングのように、モーメントシャドウマップにあらゆる種類の効率的なテクスチャフィルタリングとアンチエイリアシングを適用することができます。しかし、シャドウマップはフィルタカーネル内に深度の4つのモーメントを保存します。この情報を用いて、我々の効率的なアルゴリズムは、シャドウ強度の近似として、可能な限りシャープな下界を計算します。4つのモーメントを使用してこのような境界を計算する選択は、何千もの選択肢の自動評価に基づいており、したがって最適であることが知られています。メモリと帯域幅の要件を減らすために、モーメントシャドウマップの16ビット量子化を可能にする最適化された量子化スキームを提示します。我々の評価では、シャドウマップテクセルあたり64ビットを使用し、フラグメントあたり1つのシャドウマップサンプルで、モーメントシャドウマッピングが高品質な結果を生成することを実証しています。
1 Introduction
完全にダイナミックなハードシャドウの忠実なレンダリングは、インタラクティブな3Dグラフィックスで非常に重要な機能です。影はシーンの構造の理解を助け、知覚されるリアルさに大きく貢献します。一方、シャドウ計算は、使用可能なフレームタイム予算の大部分を費やす可能性があり、それにもかかわらず結果はエイリアシングを示すことがよくあります。これは、シャドウマッピング [Williams 1978] に基づく手法に特に当てはまります。これは、優れたハードウェアサポートと予測可能な実行時間のために一般的なアプローチです。
近傍比率フィルタリング[Reeves et al. 1987]は、適切な再構成フィルタを適用することによってエイリアシングの問題を軽減し、影の境界を平滑化します。シャドウはシャドウマップ空間の深度に依存するため、このフィルタリングはシャドウフラグメントごとにしか行うことができず、フィルタカーネルの事前計算のための効率的な技術を適用することができません。このため、フラグメントごとに何十ものシャドウマップサンプルが必要となり、実行時間は不十分になります。
この問題を克服するために、様々な発見的手法が開発されてきました [Donnelly and Lauritzen 2006; Annen et al. 2007; Salvi 2008; Annen et al. 2008; Lauritzen and McCool 2008］ これらはすべて、シャドウマップに一般的に格納されている深度値を、深度に依存した低次元のベクトルで置き換えます。このような修正されたシャドウマップから1つのフィルタリングされたサンプルを取ることで，深度依存のシャドウ強度を近似的に再構成することができます。これらの手法はすべて、いくつかの特徴的なアーティファクトに悩まされ、一般的に品質、メモリフットプリント、および実行時間の間で異なるトレードオフを提供します。
この背景から、我々の主な貢献は、モーメントシャドウマッピングであり、大幅な品質向上をもたらす新しい発見的手法です。これは、\(z\)、\(z^2\)、\(z^3\)、そして\(z^4\)を格納する4つのチャンネルを持つシャドウマップを用いて達成されます。セクション4.1と4.2で紹介する我々の効率的なアルゴリズムは、影を過大評価することなく、可能な限り暗く計算するために、このようなシャドウマップから単一のフィルタリングされたサンプルを使用します。必要なメモリを削減するために、セクション4.3では、シャドウマップのチャンネルに16ビット整数を使用できるように最適化された量子化スキームについて説明します。
この特定のデータをシャドウマップに保存するという選択は、セクション3で何千もの選択肢を系統的に分析したことに由来します。我々は、どのようなデータの選択も、すぐに明確に定義されたヒューリスティックにつながることを示します。これらの候補のほとんどは効率的なリアルタイムアルゴリズムにつながりませんが、テストデータセット上でそれらを評価するのに十分効率的な数値的方法を紹介します。
セクション3.2での評価では、多くの候補者が同じようにうまく機能していることが明らかになり、モーメントシャドウマッピングは、私たちが三角モーメントシャドウマップと呼んでいる最高の発見された技術よりもわずかに悪いだけです。この手法は中程度に効率的なリアルタイムアルゴリズムとなりますが，安定性と実行時間の点でモーメントシャドウマッピングと比較して有利ではありません。
図1とセクション5の評価からわかるように、モーメントシャドウマッピングは、フィルタカーネルの事前計算を可能にする他のシャドウマッピング技術のすべての良い特徴を継承しながら、高品質の結果を提供します。これは、シャドウマップテクセルあたり64ビットという適度なメモリ消費で達成されます。
2 Related Work
ダイナミックシャドウをレンダリングするための一般的な技術は、モンテカルロレイトレーシング[Cook et al 1984]、シャドウボリューム[Crow 1977]、シャドウマッピング[Willams 1978]のいずれかに基づいています。リアルタイムでシャドウをレンダリングするための多くの側面に関する優れた概要は、[Eisemann et al. 2011］で見つけることができます。この研究では、シャドウマッピングで生成されたハードシャドウの効率的なフィルタリングとその応用に焦点を当てます。
シャドウマッピングは、光が当たっている面が光源から見えることを利用して、ハードシャドウを生成します。光源を視点として、シーンは画像空間の深度値を格納するシャドウマップにレンダリングされます。シャドウマップをシーンに投影し、保存された深度値を実際の深度値と比較することで、効率的なシャドウテストが可能になります。しかし、この画像ベースのアプローチは、エイリアシングや、サーフェスアクネとして知られる離散化アーティファクトが発生しやすいです。後者は、シーンに依存した深度値のバイアスによって打ち消すことができます[Dou et al. 2014］。
エイリアシングの中で特に問題となるのは、シャドウの境界がギザギザになるアンダーサンプリングです。さまざまな手法により、シャドウマップのさまざまな部分をさまざまな解像度でインテリジェントにサンプリングすることで、この問題を軽減できます。台形シャドウマップ [Martin and Tan 2004] は単一の投影行列を最適化します。サンプル分布シャドウマップ[Lauritzenら2011]は、画面空間深度バッファーからの情報を活用してビューフレームを分割し、可視フラグメントのバウンディングボックスを計算して、各分割に対してタイトなシャドウマップフレームを取得します。多光源に対する仮想シャドウマップ[Olssonら2014]は、各フレームでどの全方向シャドウマップのどの部分をどの解像度でレンダリングする必要があるかを決定します。
それでも、エイリアシングアーティファクトの除去にはフィルタリングが必要です。近傍比率フィルタリング(PCF)[Reeves et al. 1987]は、適切なフィルタカーネル内でシャドウマップをサンプリングし、各サンプルに対してシャドウテストを実行し、結果として生じるシャドウ強度をフィルタリングすることによって、これを実現します。シャドウテストは深度に依存する操作であるため、これはシェーディングされたフラグメントごとにのみ行うことができます。
分散シャドウマッピング(VSM)[Donnelly and Lauritzen 2006]は、深度と2乗深度を含む修正シャドウマップを使用します。フィルタリングされたサンプルが与えられると、フィルタカーネル内の深度の平均と分散が導かれます。これによってチェビシェフの不等式を評価することができ、フラグメントに近い深度値の割合の下界が得られます。この境界はPCFの近似として使われます。
同様に、畳み込みシャドウマッピング (CSM) [Annenら2007]は、シャドウテストに使用されるシフト単位ステップ関数の\(M\)複素フーリエ係数を格納します。フィルタリングされたサンプルは、フィルタカーネル内の深度依存影強度のフーリエ係数を提供し、切り捨てられたフーリエ級数を使用して近似することができます。この手法は、非常に高いメモリ要件を犠牲にして、任意に良好な結果を生成できます。
指数シャドウマッピング (ESM) [Salvi 2008; Annen et al. 2008]は、\(c \gg 1\)を定数とし、\(z\)をオクルーダーの深さとして、\({\rm exp}(c \cdot z)\)を格納します。マルコフ不等式はPCFの結果の近似下界を計算するのに使われます。様々な失敗ケースに対して、PCFへのフォールバックが提案される。
ESMは一般に、部分的な影の最後尾のレシーバーや完全に影になった領域では高い品質を生成しますが、影のレシーバーの境界では不安定な挙動を示します。逆にVSMは、フィルターカーネル内の分散が大きい場合、完全に影になった領域でライトリークを生じます（図1）。両者の長所を組み合わせるために、指数分散シャドウマップ(EVSM)[Lauritzen 2008]は、VSMを\({\rm exp}(c \cdot z)\), \({\rm exp}(c \cdot z)^2\)だけでなく\({\rm exp}(-c \cdot z)\), \({\rm exp}(-c \cdot z)^2\)でも使用し、より暗いシャドウを使用します。
複雑なシーンでVSMのライトリークを減らすために、レイヤー化分散シャドウマップ(VSM)[Lauritzen and McCool 2008]は、賢く深度区間を分割し、各区間に別々の分散シャドウマップを使用します。
ヒューリスティックなアプローチとメモリフットプリントの増大は、PCFと比較して明らかな欠点ですが、これらの技術はすべて、いくつかの利点も共有しています。最も重要なのは、対応するシャドウマップに任意の線形フィルタリング演算を適用できることです。これには、マルチサンプルアンチエイリアシング、ミップマッピング、異方性フィルタリング、2パス・ガウスなどのローパスフィルタが含まれます[Donnelly and Lauritzen 2006]。こうすることで、単一のフィルタリングされたサンプルを効率的に得ることができ、PCFのコストのかかるサンプリング手順を回避することができます。
アルファブレンディングも線形演算であるため、PCFの不透明シャドウキャスターに対する制限を克服することができます。フーリエ不透明度マッピング[Jansen and Bavoil 2010]は，CSMをベースにして，煙のような関与媒質の影を生成します。このアプローチは、VSMや我々の新しい技術のような他の技術とも互換性があります。
また、ハードシャドウを効率的にフィルタリングすることで、適度な広さのエリアライトで発生するソフトシャドウを近似的に再現することができます。近傍比率ソフトシャドウ [Fernando 2005]は、まず、オクルーダーとレシーバの間の平均距離を決定するために、シャドウマップでブロッカー検索を実行します。これを用いて半影の大きさを推定し、対応するカーネル半径でPCFを行います。分散ソフトシャドウマップ[Yang et al. 2010]は、分散シャドウマップに対して面積和テーブルを生成します。これにより、ヒューリスティックなブロッカー探索とシャドウフィルタリングを一定時間で行うことができます。VSMの欠点を克服するために、階層的シャドウマップからの知識を用いた適応的サンプリングスキームが提案されています。
Volumetric obscurance [Loos and Sloan 2010]は、分散シャドウマッピングのアプローチがスクリーン空間のアンビエントオクルージョンの領域にも移行できることを示しています。
3 Filterable Shadow Maps
フィルタリングされたハードシャドウのための新しいヒューリスティックを系統的に探索するためには、まず、既存の技術についていくつかの一般化された観察を行う必要があります。これらのテクニックの多くは、確率的な枠組みで有用な解釈ができることが知られています[Donnelly and Lauritzen 2006; Salvi 2008]。以下では、このフレームワークに基づいて説明するので、このフレームワークの詳細を紹介します。
あらゆるシャドウマップは、シャドウマップ空間におけるオクルーダーの深度から直接計算されたデータを格納しています。一般に、\(m \in {\mathbb N}\)チャンネルを持つシャドウマップはマップ\({\mathbf b}: [0, 1] \rightarrow {\mathbb R}^m\)で使用され、1つのシャドウマップテクセルにおけるオクルーダーの深度\(z \in [0, 1]\)を、シャドウマップに格納されたあるベクトル\({\mathbf b}(z)\)に割り当てます。シャドウマッピングは、\({\mathbf b}(z) := {\mathbf z}(z) := z\)を使った最も単純なケースを表しています。フィルタリングは関係ないので、\(z\)はシャドウマップから取得することができ、\(z \lt z_f\)の比較によって、深度\(z_f \in [0, 1]\)のフラグメントがシャドウにあるかどうかがわかります。
PCFでは、単一のオクルーダーの深度は、あるフィルターカーネルに従って重み付けされた多数の深度サンプルに置き換えられます。概念的には、これはカーネルからランダムに深度値を選んでいると解釈でき、各深度の確率を示す\([0, 1]\)上の確率分布\(Z\)によって適切にモデル化されます。この確率はフィルタの重みを反映しています。この定式化において\(Z({\mathbf z} \lt z_f)\)は、ランダムに選ばれた深度がフラグメントの深度より小さい確率であり、これはまさにPCFによって計算されたフィルタリングされた影の強度となります。
式\(Z({\mathbf z} \lt z_f)\)の難しさは、\(z_f\)への依存性にあります。分布\(Z\)は、その左連続累積分布関数\(F_z(z_f) := Z({\mathbf z} \lt z_f)\)によって一意に識別されます。実関数である以上、それは無限次元空間に由来します。フィルタリング可能なシャドウマップでは、この関数の圧縮表現が数バイトのみしか必要ありません。
\(z\)の代わりに\({\mathbf b}(z)\)を格納したシャドウ・マップが、以前PCFに使われたカーネルを使ってフィルタリングされたとします。フィルタリングとは、カーネルをランダムに選ぶことと理解できます。選ばれたベクトルの期待値がフィルタリングされたベクトルとなります：
\begin{eqnarray}
b := {\mathbb E}_Z ({\mathbf b}) \in {\mathbb R}^m
\end{eqnarray}
これは\(Z\)の圧縮表現として機能します。\({\mathbf b}(z)\)は\(z\)に関する冗長な情報を提供しますが、\(Z\)は\(b\)の知識によって強く過小評価されます。この線形圧縮方式の利点は、ハードウェア加速テクスチャフィルタリングと互換性があることです。シャドウマップはフィルタリング可能です。
ここでの課題は、\(b\)のみを知っていて\(Z\)を分からない\(F_Z(z_f)\)を近似することです。この近似を\(G(b, z_f) \in [0, 1]\)と呼びます。その導出には、\({\mathbf b}\)とドメイン固有のヒューリスティクスの聡明な選択が必要です。VSMは\({\mathbf b}(z) := (z, z^2)^{\top}\)を使用し、ESMは\({\mathbf b} := e^{c \cdot z}\)を使用し、CSM \({\mathbf b}\)は\(m=2 \cdot M\)のフーリエ基底関数で構成されます。VSM、ESM、EVSM、およびLVSMは、\(F_Z(z_f)\)の下限、つまり\(G(b, z_f) \leq F_Z(z_f)\)を計算することによって近似を実装します。生成されるシャドウは暗すぎることはありません。CSMはまた、その再構成が下限を提供するような方法で一般的にバイアスされます。
このようにどこにでもあるような下界を選択する理由は、図2に示されています。\(z_f\)がオクルーダーの深度を通り過ぎると、\(F_Z(z_f)\)が即座に増加するため、一般にサーフェイスアクネが発生します。アーティファクトのない結果を得るためには、この増加はオクルーダーの最大深度とレシーバーの最小深度の間で生じなければならなりません。\(F_Z(z_f)\)の下界を使用することで、この要件を明確に説明することができます。
従って、我々は下界を保証するテクニックを追求します。その一方で、ライトリークが少ないこと、つまり下界が可能な限りシャープであることも求めます。これら2つの要件は、直ちによく定義された問題 [Kemperman 1968] を導きます。
問題 1(一般化モーメント問題). \(I \subseteq {\mathbb R}\), \(b \in {\mathbb R}^m\), \(z_f \in I\)と\({\mathbf b}: I \rightarrow {\mathbb R}^m\)が与えられたとき，圧縮表現として\(b\)を持つ\(I\)上の確率分布\(S\)の探索空間
\begin{eqnarray}
{\mathfrak S}(b) := \{ S \in {\mathfrak B}(I) \, | \, {\mathbb E}_S({\mathbf b}) = b \}
\end{eqnarray}
を考えます。我々はシャープな下界
\begin{eqnarray}
G(b, z_f) := \underset{S \in {\mathfrak S}(b) }{\rm inf} F_S(z_f)
\end{eqnarray}
を計算するよう努めます。
\({\mathbb E}_Z({\mathbf b}) = b\)は\(Z \in {\mathfrak S}(b)\)を意味するため、\(Z\)がどのように選択されても、\(G(b, z_f)\)は実際に\(F_Z(z_f)\)の下限となります。同時に、\(Z\)は\({\mathfrak S} (b)\) の分布のいずれであっても、我々の知識に違反することはありません。最大下界の定義では、\(G(b, z_f)\)は可能な限りシャープな下限を提供することを意味します。したがって,一般モーメント問題の解は最適なシャドウマッピング技術を提供します。\(I\)を選択すると、深度値の許容領域に関する事前知識を含めることができることに注意してください。
上記の\(I = {\mathbb R}\)と\({\mathbf b}\)について、VSMとESMはどちらも問題1の解を提供します。 LVSMは、深度方向の重なりを無視すれば問題1を解決します。EVSMは下界を計算しますが、上のシーンではシャープではありません。CSMが下界を計算するように設定されている場合、この下界もシャープではありません。結論として問題1は、VSMとESMの精神に基づくシャドウマッピング技法の導出のための一般的な枠組みを提供します。
一般的なモーメント問題はよく研究されており、分布を最小化する構造に関する一般的な記述も存在します[Kemperman 1968]。しかし、任意の\({\mathbf b}\)の選択に対して効率的な閉形式の解を得ることは不可能です。我々は、効率的な解を可能にしながら、シャドウマッピングの目的によく合う単一の\({\mathbf b}\)を特定する必要があります。
3.1 Numerical Solution
中間段階として、問題1の厳密解に対して任意のケースで任意に良い近似を計算する方法について述べます。この解は、リアルタイムアプリケーションにおける影の強度の計算には効率が悪すぎますが、その一般性により、\({\mathbf b}\)の選択の評価に有用です。
問題1に対するアルゴリズムアプローチの大きな難点は、無限次元の探索空間\({\mathfrak S}(b)\)です。明らかに，これは考慮される分布の離散化によって，つまり\(I \subset [0, 1]\)を有限集合として選択することによって打開することができます。\(I\)のサンプル数が増えるにつれて，\(I = [0, 1]\)に対する良い近似が得られます。
\({\mathfrak S}(b)\)は凸であり、線形制約\(S(I)=1\)と\({\mathbb E}_S({\mathbf b}) = b\)に従います。この探索空間内で線形関数\(F_S(z_f)\)を最適化する必要があります。有限集合\(I\)の場合、集合\({\mathfrak S}(b)\)は有限次元であり、問題1は線形計画法を用いて解くことができます。線形計画法は[Prékopa 1990]において，問題1の特殊な場合にすでに用いられています。これを一般化したのがアルゴリズム1です。
命題 2. アルゴリズム1は問題を解く。
証明スケッチ。ステップ4の制約が\(S \in {\mathfrak S}(b)\)と等価であることを簡単に検証できます。さらに、\(p^{\top} \cdot w = F_s(z_f)\)および正しい関数は最小化されます。 □
3.2 Choosing Shadow Map Data
以下では,アルゴリズム1を用いて\({\mathbf b} : [0, 1] \rightarrow {\mathbb R}^m\)の可能な選択肢を評価するための完全に自動化されたフレームワークを開発します。フィルタリングされたハードシャドウに興味があるので，\(\sigma=2.4\)テクセルの\(9 \cdot 9\) Gaussフィルタカーネルと洗練されたバイアスを持つPCFが参照解です。したがって, PCFとの類似性を測定する誤差項が必要となります。
最終的に、影の計算では、1つの光源からの直接照明によって受ける放射照度が得られます。定義上、問題1を解決する技術は、影の強度を過大評価することがないため，さまざまな形のライトリークをアーティファクトとして生成することしかできません。このライトリークを定量化する簡単で意味のある方法は、放射照度フィールドに\({\mathcal L}^1\)-メトリックを使用することです。
シーン全体の性能を評価するために、単一指向性ライトを使用します。この場合，サーフェイスが受ける放射強度は、シャドウマップでカバーされる面積に正比例します（影は無視されます）。これにより、画像に基づく誤差の簡便な評価が可能になります。
まず、ステンシルバッファを使って、最前面だけでなくすべてのサーフェイスを表示する一連のシャドウマップをレンダリングします。次に，アルゴリズム1を使用して、このシャドウマップのスタックで見られる各フラグメントのシャドウ強度を計算します。これらの値とPCFによって生成されたシャドウ強度との平均差を計算することで、誤差項が得られます。シャドウマップの離散化によってもたらされる小さな歪みを無視すれば、この誤差項は放射照度フィールドの\({\mathcal L}^1\)-誤差を全放射強度で割ったものと一致します。同時に、影強度の加重平均誤差と理解することもできます。
我々は、3つの異なるシーンの4つの異なるビューで評価し、挑戦的だが現実的なテストケースを提供します（補足資料参照）。VSMやESMよりも大幅に高い品質を目指すため、多少の余分なメモリを使っても構わないと思っています。図3は、4つのチャンネルを持つシャドウマップを使用する技術が、2つまたは3つのチャンネルを持つ技術よりも明らかに優れていることを示しています。したがって、\(m:=4\)に固定します。
\({\mathbf b} : [0, 1] \rightarrow {\mathbb R}^4\)のコンポーネント関数を選択する必要があります。先験的に、どの関数群がうまく機能するかは不明です。これは結局私たちが気にしている問題です。閉じた形式で問題1を解く希望を持つために,有理数関数から指数関数および三角関数までの範囲の37の比較的初歩的で滑らかな関数のセットに焦点を当てました。それらのすべては、我々の結果の再現に必要な詳細を含む補足資料に記載されています。これらの関数のあらゆる可能な組み合わせを評価し, \(\dbinom{ 37 }{ 4 } = 66045\)候補テクニックを導きました。
我々の評価では、アルゴリズム1の評価回数が3,920億回必要であり、これを数週間かけてコンピュータのクラスタ上で実行しました。候補の数が多いため、現時点では結果の完全なレビューは不可能です。幸いなことに、このデータから簡単な結論を得ることができます。図4は、数千のテクニックが最良のテクニックよりわずかに悪いパフォーマンスしか示さないことを示しています。したがって、有望な候補の中から選ぶことができる大きなプールが存在します。
直感的には、驚くほど小さな品質のばらつきは、多くの滑らかな関数が区間\([0, 1]\)上の次数\(m=4\)の多項式でうまく近似できるという事実で説明できます。最初の4つのモーメントがわかれば、そのような多項式の期待値を計算することができます。したがって、4つの平滑関数の期待値の知識は、4つのモーメントと同様の情報量をもたらします。
あとは、問題1の閉形式解を可能にする誤差の少ない候補を選ぶだけです。この点で、2つの\({\mathbf b}\)の選択はよく研究されており、特に興味深いのは：
\begin{eqnarray}
{\mathbf b}_{\rm MSM}(z) &:=& (z, z^2, z^3, z^4)^{\top} \\
{\mathbf b}_{\rm TMSM}(z) &:=& (\sin (2\pi z), \cos(2\pi z), \sin(4\pi z), \cos(4\pi z))^{\top} \tag{1}
\end{eqnarray}
です。
これらの選択肢の問題1は、それぞれモーメント問題および三角モーメント問題として知られています。モーメント問題を解くと、エラー値は2.19%になります。三角モーメント問題は,実際には1.93%の最小測定誤差を実現します。どちらのエラー値も最小値であるため、この2つの選択肢に焦点を当てて説明します。
4 Moment Shadow Mapping
残りの候補の中から最適な解を見つけるために、我々は3つの異なるシャドウマッピング技術について効率的なアルゴリズムを開発しました。ここでは、3つの技法すべてについて得られた知見を簡単に説明しますが、その後、最も効果的な技法に焦点を当てます。他の2つの技法については、関連する命題の証明とともに補足資料でさらに説明します。
Hamburger four moment shadow shadow mapping (Hamburger 4MSM) は、我々の主要なアルゴリズムです。他の2つの手法と区別する必要がない場合は、モーメントシャドウマッピング（MSM）とも呼びます。最も高速でロバストなアルゴリズムを使用しているため、この手法を好んで使用しています。\(I={\mathbb R}\)、\({\mathbf b}={\mathbf b}_{\rm MSM}\)の問題1を解きますが、これは4つのモーメントを持つ Hamburger モーメント問題として知られています。
他の2つの技法と比較して有利であることに加え、この技法にはユニークな性質があり、開発者やデザイナーにとって使い勝手がよくなっています。シャドウマップがレンダリングされるときは常に、近景と遠景の平面を固定する必要があります。ESMやCSMのようないくつかのアルゴリズムでは、これらの平面間の距離が大きくなるにつれて結果が悪化するため、コンテンツ制作者はこれらを厳密に選択する負担を負うことになります。補足文書では、Hamburger 4MSMが、この選択が結果にまったく影響しない、問題1で説明された唯一の手法であることを証明します。
Hausdorff four moment shadow mapping (Hausdorff 4MSM) は、\(I=[0,1]\)を使用すること、つまり深度値がこの区間内になければならないという事前知識を組み込むことを除けば、Hamburger 4MSMとほぼ同じです。これにより、再構成アルゴリズムに分岐が追加され、短距離の影に対して若干暗い結果が得られます。残念ながら、これは16ビット量子化を使用する場合に量子化アーティファクトを増幅する可能性があり、これが我々がHamburger 4MSMを好む主な理由です。それでも、Hausdorff 4MSMは有効な選択肢です。
三角法モーメントシャドウマッピング (TMSM) は、セクション3.2で66045の候補の中で最も性能が良いことが示されたので、我々は興味を持っています。これは、\(I=[0, 1]\)、\({\mathbf b}={\mathbf b}_{\rm TMSM}\)に対して問題1を解きます。この問題は、他の2つのケースで遭遇した問題よりもかなり難しく、部分的な問題しか解かれていません。本稿では、この問題を完全に解く新しいアルゴリズムを開発しました。この問題では、コストがかかり、不安定になりやすい4次方程式を解く必要があります。それにもかかわらず、これはセクション5での直接比較に有用であり、セクション3.2で予測されたように、MSMと比較してライトリークの減少が小さいことを示しています。
4.1 Our Main Algorithm
ここで、\(I={\mathbb R}\)、\({\mathbf b}={\mathbf b}_{\rm MSM}\)の問題1を解くHamburger 4MSMのアルゴリズムを紹介し、解析します。このアルゴリズムの実用的な実装と使用法についてはセクション4.2で述べます。本問題に対する閉形式解は既知であり[[Krein and Nudel’main 1977]、対応するアルゴリズムも設計されています[Tari 2005]。任意の偶数モーメント\(m \in 2 \cdot {\mathbb N}\)に一般化することもできます。しかし、既存のアルゴリズムは全く異なるシナリオに最適化されています。現在のリアルタイムアプリケーションに適したアルゴリズムを提案します。これはVSMにおけるチェビシェフの不等式に取って代わります。実際には, VSMは\(m=2\)に対する最も単純な特殊ケースとして現れますが, 我々がより関心があるのは\(m=4\)です。
求められる解は、\(n := \frac{m}{2} + 1\)個のDirac-\(\delta\)分布の線形結合\(S \in {\mathfrak S}(b)\)によって実現されることが知られています。\(F_S(z_f)\)を最小化するためには、Dirac-\(\delta\)分布の1つが\(z_f\)において関数の台を持たななければなりません。残りのDirac-\(\delta\)分布は、特殊な多項式の根に位置しなければならないことが示されます。これらの根が計算されると、線形結合の重みは連立一次方程式\({\mathbb E}_S({\mathbf b}) = b\)によって決定され、\(G(b, z_f) = F_S(z_f)\)を評価することができます。これらすべてはアルゴリズム2によって行われます。
命題 3. アルゴリズム2が正定値\(B\)と\(c_n \neq 0\)を生成する場合、問題1は正しく解かれます。正定値\(B \in {\mathbb R}^{n \times n}\)が固定されている場合、\(z_f\)の異なる値が\(n-1\)以下の場合は\(c_n=0\)になります。
明らかに、命題3の2つの条件にはさらなる注意が必要です。\(c_n=0\)の場合は未定義の結果をもたらしますが、\(z_f\)の孤立した値に対してのみ起こるので、実際には全く問題ありません。このケースを避ける最もエレガントな方法は、Hamburger 4MSMの代わりにHausdorff 4MSMを使うことですが、そうすることによる利益はほとんどありません。
\(B\)の条件は見た目ほど強くありません。実際に解析してみると、Hamburger 4MSM [Krein and Nudel’man 1977, p.64, p.78]の強さがわかります。
命題 4. \({\mathbb R}\)上の確率分布\(Z\)を\(b = {\mathbb E}_Z({\mathbf b})\)とすると、行列\(B\)は対称で正の半定値となる。さらに、次のステートメントと同等です：
- \({\rm det} B = 0\)
- \(Z\)は\({\mathbb E}_Z({\mathbf b}) = b\)を持つ分布のみである。
- \(Z\)は最大\(\frac{m}{2}\)個のDirac-\(\delta\)分布の線形結合である。
この特別なケースは大いに関係があります。シャドウマップのフィルターカーネルは、少数の異なるサーフェスしか含まないのが一般的で、これらのサーフェスの深度はほぼ一定であることが多いです。この状況は、サーフェイスごとに1つのDirac-\(\delta\)分布の線形結合によってよく近似されます。シャドウマップ上のフィルターカーネルの大部分は、2つ以下のDirac-\(\delta\)分布で近似することができます。命題4は、\(Z\)が方程式\({\mathbb E}_Z({\mathbf b}) = b\)によって一意に決定されるため、Hamburger 4MSMがこの場合に完全な再構成を達成できることを教えてくれます。
この場合の別の分岐をアルゴリズム2に追加することは難しくありません。本質的には, \(c\)を\(B\)のカーネル内のベクトルに置き換えるだけで十分ですが，このような解は, 2つの場合を区別することが困難であるため，ロバストに動作しないことが分かりました。代わりに、ほぼ特異\(B\)に対してもロバストに動作するようにアルゴリズムを実装することをお勧めします。\(B\)が特異性に近づくにつれて、再構成\(G\)はグランドトゥルース\(F_Z\)によりよく近似します。
4.2 Implementation
Hamburger 4 MSMの実装は、VSMとよく似た2ステップの手順です。まず、モーメントシャドウマップをレンダリングする必要があります。これは、一般的なシャドウのレンダリングとほぼ同じように機能しますが、4チャネルモーメントシャドウマップでは、深度\(z\)のみを格納するのではなく、深度\(z\)の4つのモーメント\(z\)、\(z^2\)、\(z^3\)、\(z^4\)をシャドウマップ空間に格納します。この冗長情報の利点は、2パスガウスブラーやミップマップの生成などの線形フィルタリング操作を、あまり多くの情報を失うことなくモーメントシャドウマップに適用できることです。
次に、モーメントシャドウマップからフィルタリングされたサンプルと、シャドウマップ空間におけるフラグメントの深度が、このフラグメントのフィルタリングされたシャドウ強度を計算するためにアルゴリズム2に供給される必要があります。数値的に安定した方法でこの計算を実行することは、以前、モーメントシャドウマッピングの開発の失敗についてのブログ記事[Salvi 2007]で説明したように、非自明なことです。以下では、\(m=4\)に対するアルゴリズム2の数値的に安定な実装を導出し、それをアルゴリズム3にまとめます。
\(m=4\)の場合、アルゴリズム2では、式\(B \cdot c = (1, z_1, {z_1}^2)^{\top}\)および\({\hat A} \cdot w = {\hat b}\)の3 x 3線形システムの解と、2次式\(c_3 \cdot z^2 + c_2 \cdot z + c_1 = 0\)の解が必要です。後者は、2次式で問題なく解くことができます。\({\hat A} \cdot w = {\hat b}\)系を完全に解く必要はありません。
\(z_2\)および\(z_3\)に対する\(z_f\)の位置に依存して、影の強度\(G\)は、\(0\)、\(w_2\)または\(1-w_1\)に評価されます（\(z_2 \leq z_3\)と仮定）。対応する閉形式はアルゴリズム3で与えられます。命題4から、\(B\)は対称で正の半定値であることがわかる。したがって、\(B = L \cdot D \cdot L^{\top}\)の形のコレスキー分解を用いることができ、\(L \in {\mathbb R}^{3 \times 3}\)は下三角形、\(D \in {\mathbb R}^{3 \times 3}\)は対角です。この分解は、ほぼ特異な行列に対してもロバストな振る舞いをすることが知られています[Trefethen and Bau 1997, p.176]。\(B\)の特殊な構造は、さらなる最適化のために利用することができます。
このようにアルゴリズム2を実装し、倍精度モーメントを与えると、アルゴリズム1で生成された結果と一致する結果が生成されます。しかし、入力モーメントを単精度で保存するとすぐに数値ノイズが発生します。これは命題4を通して説明できます。関連する場合には、\(B\)はほぼ特異的ですが、依然として正の準確定です。量子化誤差は負の固有値を生じ、問題1を解けなくします。
モーメントシャドウマップに倍精度でモーメントを保存することは、許容できないメモリフットプリントを課すことになります。量子化によって失われる情報を補う方法が必要です。この方法は何よりもロバストな結果を保証しなければなりません。この点では、入力に単純なバイアスをかけるのが最も効果的であることがわかりました。
バイアスモーメントベクトル\(b’ := (1 – \alpha) \cdot + b + \alpha \cdot b^{\ast}\)を用い, \(b \in {\mathbb R}^m\)はバイアスなしで量子化モーメントベクトル, \(0 \lt a \ll 1\)はバイアスの強さ, \(b^{\ast}\)は適切に選択された定数ベクトルです。このバイアスモーメントベクトルは、バイアス分布\(Z’ := (1 – \alpha) \cdot Z + \alpha \cdot Z^{\ast}\)に対応します。ここで、\({\mathbb E}_{z^{\ast}}({\mathbf b}) = b^{\ast}\)、したがって\(G(b’, z_f)\)は\(F_{z’}(z_f)\)の下限です。小さい\(\alpha\)の場合、これは大きなエラーを引き起こすことはありません。
あとは\(b^{\ast}\)を選ぶだけです。理想的には、\({\rm det} B\)は\(a \ll 1\)が増加するにつれてできるだけ早く成長します。\(b\)の特定の分布を仮定すると、この要件は閉形式で最適化することができ、\(b^{\ast} = (\frac{1}{2}, \frac{1}{2}, \frac{1}{2}, \frac{1}{2})^{\top}\)または同等に\(Z^{\ast} = \frac{1}{2} \cdot (\delta_0 + \delta_1)\)を導きます。
アルゴリズム3は、パイプライン全体で\(\alpha = 2 \cdot 10^{-6}\)のバイアスと単精度を用いてロバストな結果を生み出します。このバイアスはシーンに依存しないことに注意してください。状況によっては，個々のピクセルが区間[0, 1]の外側で誤ったシャドウ強度を得るという稀なアーチファクトが発生することがあります。これは\(c_3\)がゼロに近づくことに関係しています。これは、\(G\)をクランプすることで悪意をなくすことができ、Hausdorff 4MSMを使用することで完全になくすことができます。
4.3 Optimized Moment Quantization
真に効率的な4MSMの実装は、1モーメントあたり16ビット以下であるべきです。正準アプローチでは、これは受け入れがたいアーティファクトにつながります。情報理論は、この状況を改善するための自然なフレームワークを提供します。これを採用するために、フィルタリングされたモーメントシャドウマップ内のモーメントベクトル\(b\)の分布をモデル化する\([0, 1]^m\)上の確率変数\({\mathbb x}_b\)を定義し、その微分エントロピーを解析します[Cover and Thomas 2001, p.13, p.229]。
定義 5. \(p_b : {\mathbb R}^m \rightarrow {\mathbb R}_{\geq 0}\)を\({\mathbf x}_b\)の確率密度関数とします。\({\mathbf x}_b\)の微分エントロピーは次式で与えられます。
\begin{eqnarray}
h({\mathbf x}_b) := – \int_{{\mathbb R}^m} p_b(b) \cdot \log_2 p_b(b) {\rm d}b.
\end{eqnarray}
微分エントロピー\(h({\mathbf x}_b)\)は、\({\mathbf x}_b\)の分布が一様でないために、\({\mathbf x}_b\)の一様量子化バージョンで失われるエントロピーの量を測定します[Cover and Thomas 2001, p.229]。より具体的には、単位四次元\([0, 1]^4\)を表現するために4つの16ビット整数を用いて量子化された\({\mathbf x}_b\)は、約\(4 \cdot 16 + h({\mathbf x}_b)\)ビットのエントロピーを持ちます。この場合、\(h({\mathbf x}_b)\)は常に負であることに注意してください。
低いエントロピーでデータを保存すると、使用可能なメモリが非効率的に使用されます。したがって、格納する前に\(b\)を変換して\(h({\mathbf x}_b)\)を最大化する必要があります。変換されたデータは、直線的にフィルタリングできることが望ましいです。この要件は、選択をアフィン変換\(\theta_m : {\mathbb R}^m \rightarrow {\mathbb R}^m\)最大化\(h(\theta_m({\mathbf x}_b))\)に制限します。\(\theta_m({\mathbf b}(z))\)をモーメントシャドウマップに格納すると、フィルタリングされたサンプルを取得し、\({\theta_m}^{-1}\)を使用して\(b\)を再構成できます。この方法で得られるエントロピーの量は、体積\(|{\rm det}\theta_m|\)の伸長に直接関係します。
命題 6. 正の\(\theta_m\)について
\begin{eqnarray}
h(\theta_m({\mathbf x}_b)) = h({\mathbf x}_b) + \log_2 | {\rm det}\theta_m |.
\end{eqnarray}
同時に\(\theta_m\)は\({\mathbf b}([0, 1])\)を表現可能なベクトル集合\([0, 1]^m\)に写像しなければなりません。任意のアフィン変換の場合、これは、\(\theta_m\)を、その軸平行バウンディングボックスが\([0, 1]^m\)となるように拡大縮小し、平行移動することによって強制することができます。このようにして、数値最適化によって最適な\(\theta_m\)を見つけることができます。結果として得られる変換\(m=4\)は
\begin{eqnarray}
\theta_4(b) = (0.0359558848, 0, 0, 0)^{\top} + \\
\begin{bmatrix}
-2.07224649 & 32.2370378 & -68.5710746 & 39.3703274 \\
13.7948857 & -59.4683976 & 82.035975 & -35.3649032 \\
0.105877704 & -1.90774663 & 9.34965551 & -6.65434907 \\
9.79240621 & -33.76521106 & 47.9456097 & -23.9728048
\end{bmatrix} \cdot b
\end{eqnarray}
で，\(m = 2\)について（すなわち VSM)は次を得ます。
\begin{eqnarray}
\theta_2(b) = \begin{bmatrix} 1 & 0 \\ 4 & -4 \end{bmatrix} \cdot b
\end{eqnarray}
こうすることで、それぞれ12.3ビットと2ビットのエントロピーを得ることができます。4MSMの場合、この改善により16ビットの量子化が可能になる。我々の実験では、より強いバイアス\(\alpha = 3 \cdot 10 ^{-5}\)が必要であり、短距離シャドウはわずかな量子化ノイズに悩まされますが、メモリと帯域幅の要件が半分になったことで、これらの欠点は簡単に補われます。VSMでは、最適化された量子化により、量子化アーティファクトが顕著に減少しました。
視覚化の目的で、3次元のケース\(m=3\)も考えることができます。この場合、6.2ビットの微分エントロピーが得られ、3次元曲線と凸包を視覚化することができます（図5参照）。元の凸包は非常に平坦であるのに対して、拡張された凸包は単位立方体をきれいに埋めていることに注意してください。
5 Results and Conclusion
4MSMSは、図6に示すように、PCFの優れた近似を提供し、他のフィルタリング可能なシャドウマップよりもアーティファクトが少ないです。極端に短い範囲に投影された影は、わずかな量子化ノイズとライトリークに悩まされることがあります（図6e、6f）。16ビット量子化に必要なより強いバイアス\(\alpha\)は、ライトリークをわずかに強めます（図6e）。TMSMはHausdorff 4MSMSと同程度のライトリークを生じますが、ロバスト性の問題と実行時間の短さに苦しみます（図6d）。
16ビット量子化では、Hausdorff 4MSMSはHamburger 4MSMよりわずかに遅く、短い範囲ではわずかに暗いシャドウを生成します。しかし、これは量子化アーティファクトを増幅する可能性もあります。したがって、我々はHamburger 4MSMSが望ましいと考えています。図1と図8に、この手法の結果をさらに示します。さらに、補足ビデオを見ることを推奨します。特に、モーメントシャドウマップに適用されたマルチサンプル・アンチエイリアシング（MSAA）の絶大な効果を示しています。このハードウェア機能はPCFには適用できません[Donnelly and Lauritzen 2006]。
図7の実行時間の比較では、nVidia GeForce GTX 780とDirect3D 11を使用し、1つの指向性ライトとシーン全体を一様に覆うシャドウマップを持つシーンで比較しました。フィルタリング可能なシャドウマップのフレームタイムは、テクセルあたりのメモリに支配されていることがわかります。32ビット量子化のVSMと16ビット量子化の4MSMSは、アルゴリズム3がより複雑であるにもかかわらず、ほぼ同じパフォーマンスを示します。16ビット量子化のVSM（図示せず）は、EMSと同じ性能です。Hamburger 4MSMは、大きな出力解像度、大きなフィルターカーネル、小さなシャドウマップにおいてPCFを凌駕します。PCFはハードウェアサポートを使用してタップ数を4分の1にし、ESMはPCFへのフォールバックなしで実装されていることに注意してください。
結論として、4MSMは、1テクセルあたり64ビットという適度なコストで、これまでにない品質のフィルタリング可能なシャドウマップを提供します。おそらく、4MSMは、このメモリ量を使用する可能な限り最良のシャドウマッピング技術です。4MSMは、高品質なフィルタリングハードシャドウを必要とする多くのアプリケーションに良いソリューションを提供するはずであり、新しいアプリケーションを可能にすることを期待しています。4Kレンダリングに関しては、より高い出力解像度でのモーメントシャドウマッピングの償却が実証されたことは有望です。我々の知る限り、4MSMはモーメントの理論をグラフィックスに応用した最初のものです。この強力な理論は、リアルタイムグラフィックスのための多くの効率的なヒューリスティックスを提供することが期待されます。
Acknowledgements
著者らは、有益な議論とフィードバックをくれたPaul MüllerとDominik Michels、本論文の説明に対するコメントをくれたすべての査読者、セクション3.2で使用したクラスタのインストールをサポートしてくれたRalf Sarlette、使用したモデルを提供してくれたBlendSwap.comのユーザーEnrico SteffenとZoltan Miklosiに感謝したい。
References
