# 1.4節　光輸送アルゴリズム

コンピュータグラフィックスの分野では、光輸送問題を解決するために多くの異なるアルゴリズムが提案されてきた。この論文では、偏りのないビュー依存のモンテカルロアルゴリズムに焦点を当てることにしました。まず、提案されているさまざまな種類のアルゴリズムに言及し、次に選択した選択肢について説明します。

## 1.4.1 簡潔な歴史

光輸送アルゴリズムは、モンテカルロ法と有限要素法の2つのグループに大別することができます。
モンテカルロ法は1950年代から中性子輸送問題に使用され[Albert 1956]、そこで広く研究されてきた[Spanier＆Gelbard 1969]。グラフィックでは、ランダム粒子追跡を使用して画像を計算したAppel [1968]から始めて、モンテカルロ法が独立して生まれました。 Whitted [1980]はレイトレーシング（表面外観の再帰的評価）を導入し、また観察光線をランダムに乱すという考えを提案した。クック等。 [1984]はこの考えを実行して、それを光源、レンズと時間の無作為抽出に拡張しました。これにより、Kajiya [1986]によって提案された最初の完全で不偏モンテカルロ変換アルゴリズムが導き出され、問題は積分方程式として書くことができ、サンプリングパスによって評価することができると認識されました。それ以来、彼の軌跡追跡技術に対する多くの改良が粒子輸送理論から適応されてきた[Arvo＆Kirk 1990]。
偏りのあるモンテカルロアルゴリズムについても多くの研究がなされてきました。それはしばしば経路追跡より効率的です。これらは[Ward et al. 1988]の放射照度キャッシングアルゴリズムを含む。[Shirley et al. 1995]、および[Jensen 1995]のフォトンマップアプローチ。
光輸送のための有限要素法はもともと放射熱伝達の文献から採用された。 [Goral et al. 1984]はこれらのメソッドをグラフィックスコミュニティに導入しました。そこで、それらは一般的にラジオシティアルゴリズムとして知られています。部分構造化を含む基本的なラジオシティ法に対して多くの改良がなされてきた [Cohen et al. 1986]、進歩的改良[Cohen et al. 1988]、階層基底関数[Hanrahan et al. 1991]、重要性主導の改良[Smits et al. 1992]、不連続メッシュ[Lischinski et al. 1992]、ウェーブレット法[Gortler et al. 1993]、およびクラスタリング[Smits et al. 1994]。他の例としては、関与する媒体の取り扱い[Rushmeier＆Torrance 1987]、および非拡散表面に対する有限要素法 [Immel et al. 1986, Sillion et al. 1991, Aup- perle & Hanrahan 1993, Schro ̈der & Hanrahan 1994]。
モンテカルロの特徴と有限要素法を組み合わせた方法も提案されています。典型的には、これらは、より一般的なシーンモデルを扱うためにラジオシティパスとレイトレーシングパスとを組み合わせるマルチパス方法の形をとる[Wallace et al. 1987, Sillion & Puech 1989, Chen et al. 1991]。他のアプローチはモンテカルロラジオシティであり、ここで解は基底関数の線形結合として表される（有限要素法と同様に）が、係数はランダムな軽い粒子を追跡することによって推定される[Shirley 1990b、Pattanaik＆Mudur 1993、Pattanaik＆Mudur 1995]。

## 1.4.2 モンテカルロ　vs. 決定論的アプローチ

最も基本的なレベルでは、モンテカルロアルゴリズムは乱数を使用しますが、決定論的アルゴリズムは使用しません。しかしながら、実際にはアルゴリズムはしばしば技術の混合を使用し、そして容易に分類されない。この区別は、乱数自体とは無関係ではあるが、あるタイプのアルゴリズムや他のタイプのアルゴリズムに関連していることが多い問題によってさらにぼやけています。これらの違いのいくつかを以下で説明します。
まず、モンテカルロアルゴリズムは通常より一般的です。これは非常に重要な問題です。なぜなら、光輸送計算における最大の誤差の原因は、多くの場合、シーンモデル自体です。モンテカルロアプローチの主な利点は、事実上あらゆる環境を正確にモデル化できることです。一方、決定論的アルゴリズムでは、許容されるジオメトリ（たとえばポリゴンに限定される）および材質（たとえば理想的な拡散反射器に限定される）に厳しい制限があることが多い。2制限があると、それは困難であり不可能である。これらの方法を使用するには、通常、シーンモデルを修正することによって、異なる問題を解決することに頼らなければなりません。これらの状況下でのソリューションの「正確性」に関する主張は、せいぜい誤解を招くようなものです。
モンテカルロ法と決定論的手法は、それらがシーンモデルにアクセスする方法によっても区別されます。決定論的アルゴリズムは通常、シーンとそのプロパティの明示的な表現（たとえば、ポリゴンのリスト）を処理します。したがって、それらはシーン表現のサイズと複雑さによって強く影響されます。一方、モンテカルロアルゴリズムはサンプリングに基づいており、これはシーンモデルが少数のクエリセットを通してアクセスされることを意味する（例えば、所与の光線と交差する最初の表面点は何ですか？）。このインタフェースは、抽象化のレイヤの背後にあるシーンの複雑さを隠し、レンダリング時間がシーン表現に緩やかに結び付くだけであることを意味します（たとえば、シーンの複雑さはレイキャスティングに必要な時間に影響を与える可能性があります）。実際には、モンテカルロアルゴリズムはシーンをサンプリングして実際に必要な情報を決定することができますが、ほとんどの決定論的アルゴリズムは関連性があるかどうかにかかわらず、あらゆる詳細を調べるように設計されています。
これは、ロバスト性にとって特に重要な問題です。理想的には、光輸送アルゴリズムのパフォーマンスは、シーンの表現方法の詳細ではなく、シーンが表現するものだけに依存する必要があります。例えば、正方形領域の光源で照らされているシーンを考えてみましょう。この光源を10 x 10グリッドの点光源に置き換えると、視覚的な結果はほぼ同じになります。ただし、2番目のケースでは、多くの光輸送アルゴリズムのパフォーマンスがはるかに悪くなります。同様に、同じ光源を半透明のパネルで覆われた一対の蛍光灯で置き換えたとします。この場合、シーン全体が間接的に照らされるため、多くのアルゴリズムで問題が発生します。理想的には、レンダリングアルゴリズムはこの種の表面的な変化に敏感であるべきではありません。同じコメントが幾何学的な複雑さにも当てはまります。オブジェクトが1000ポリゴンとして表現されているのか、100万ベジェパッチとして表現されているのかに関係なく、レンダリング時間はできるだけ同じにすることを望みます。モンテカルロアルゴリズムは、サンプリングに基づいているため、少なくともこれらの状況に効果的に対処する可能性があります。
モンテカルロ法と決定論的方法との間の区別は、モンテカルロアルゴリズムがそれらが使用する数の「ランダムさ」に非常に弱い制限を課すという事実によって幾分ぼやけている（例えばしばしば唯一の要件はこれらの数が一様に分布することである）。同じ制限を満たす固定サンプリングパターンを設計することは通常可能であり、これはしばしばより良い性能をもたらす（これらは準モンテカルロ法と呼ばれる[Niederreiter 1992]）。モンテカルロ法の原理は、サンプルが真にランダムであるということではなく、ランダムサンプルを代わりに使用できるということです。

## 1.4.3 view依存　vs. view非依存アルゴリズム

コンピュータグラフィックスにおけるすべての光輸送アルゴリズムの目的は、モニタまたは印刷装置上に表示するのに適した画像、すなわち色値の矩形配列を生成することである。ビューに依存しないアルゴリズムは、ソリューションの中間表現を計算するもので、そこから任意のビューを非常に素早く生成することができます。他のアルゴリズムはビューに依存します。これは、いくつかあることの1つを意味します。重要度主導型の方法は、グローバルに定義されているが特定の観点に最適化されているソリューションを計算します。つまり、解決策はシーンの可視部分で詳しく説明されていますが、他の場所では非常に粗い可能性があります。マルチパス方法は、すべてのビューに有効であるが、画像を取得するための最終レンダリングステップが比較的遅い（例えば、それがレイトレーシングを必要とする）グローバル解を計算する。最後に、画像空間法は、いたるところで解を表現しようとせずに、シーンモデルから直接画像を計算します。このカテゴリには、パストレースなどのモンテカルロアルゴリズムが含まれます。
ビューに依存する方法とビューに依存しない方法を区別すると、興味深い問題が多数発生します。まず、これら2種類のアルゴリズムは一般的に目的が異なります。ビュー依存のメソッドは、シーンモデルがフレームごとに大きく変わる可能性があるアニメーションに役立ちます。静止画をレンダリングする場合にも自然な選択です。一方、ビューに依存しないソリューションは、アーキテクチャのウォークスルーやコンピュータゲームなどの対話型アプリケーションに役立ちます。
「ビューに依存しない」アルゴリズムの問題の1つは、特定のビューに対するエラーについて保証しないことです。理想的には、これらのアルゴリズムは全てのビューが小さなエラーを持つことを保証するでしょう。代わりに、エラーは通常グローバルに測定され（シーン全体の平均）、これはローカルエラーが依然として大きい可能性があることを意味します。これは、ビューに依存しない解決策が特に悪い領域の画像をレンダリングした場合、結果が完全に間違っている可能性があることを意味します。
ビューに依存しないソリューションのもう1つの問題は、完全なソリューションの表現を計算するため（本質的にすべてのビューを同時に解決するため）、ビューに依存するソリューションよりもコストがかかることが多いことです。非拡散マテリアルが許可されている場合、光沢のあるサーフェスの外観は視点によって急速に変化するので、これは単一のビューを計算するのに比べて非常に多くの余分な作業になります。
拡散面のみが許可されていても、ビュー依存アルゴリズムは、目的のソリューションの部分を計算するだけでよいため、多くの場合より効率的です。たとえば、シーンモデルが複雑で、それは目に見えるので、直接画像を計算する方がはるかに効率的です。重要性主導型の方法は複雑なシーンには対応できないため（ドメイン全体にわたって粗い解を計算するのは非常にコストがかかる可能性があるため）、イメージスペースアルゴリズムはここで最大の可能性を秘めています。
ビュー依存型アルゴリズムとビュー非依存型アルゴリズムの違いは、実際には最初に現れるほど大きくはありません。ビュー依存型アルゴリズムをビュー非依存型アルゴリズムに変換することが可能な場合が多いからです。類似点は、両方のタイプのアルゴリズムが、大域解の有限個の線形測定値を計算することです。ビューに依存するアルゴリズムの場合、これらの測定値はピクセル値です。各ピクセルは、画像平面の小さな領域に当たる光を積分することによって定義されます。これは、通常、解が基底関数の線形結合として表される、ビューに依存しないアプローチと密接に関係しています。視野依存アルゴリズムは、画像のピクセル値ではなく、これらの基底関数の係数を推定するようになっていることが多い。これらは両方とも線形測定値として定義されているからである。

## 1.4.4 不偏　vs. 一貫性モンテカルロアルゴリズム

モンテカルロ推定量は、未知の量$Q$に近似すると思われる値$F_N(X_1,....X_N)$を計算します。一般に、$Q$は既知の密度関数$p$のパラメータで、$X$は$p$からの無作為標本です。量$F_N - Q$は誤差と呼ばれ,その期待値$\beta[F_N] = E[F_N-Q]$はバイアスと呼ばれます。すべてのサンプルサイズ$N$に対して$\beta[F_N] = 0$ならば推定量は不偏、それに対して、誤差$F_N - Q$が$N$を無限大に近づけた時、０に確率が１に近づく時それは一貫しています[Kalos＆Whitlock 1986]。
直感的に、偏りのない推定量は平均して正解を計算します。偏っている推定器は、平均して間違った答えを計算します。しかし、偏った推定量も一貫している場合は、サンプルサイズを増やすことで平均誤差を任意に小さくすることができます。
偏りのない推定量は、光輸送計算がロバストであるために不可欠であると主張します。グラフィックスで使用される多くのアルゴリズムは単に一貫性があるため、これは重要な点です。
不偏アルゴリズムを好む基本的な理由は、それらがソリューションのエラーを推定することをはるかに容易にするということです。計算結果に信頼性を持たせるためには、この誤差の推定値が必要です。不偏アルゴリズムの場合、これは単にサンプル分散の計算を伴います。これは、エラーがサンプル間のランダムな変動として現れることが保証されているためです。ただ一貫しているだけのアルゴリズムのために、しかし、我々はまたバイアスを制限しなければなりません。一般的にこれを行うのはとても難しいです。サンプルをもう少し引いてバイアスを推定することはできません。バイアスをかけると、ノイズが多くない結果になりますが、それでも正しくありません。グラフィックスアルゴリズムでは、このエラーは、不連続性、過度のぼやけ、または好ましくない表面シェーディングの形で、しばしば視覚的に顕著になります。
偏りのないアルゴリズムは、参照画像を生成するためによく使用され、それに対して他のレンダリングアルゴリズムを比較することができます。偏りのない方法は発生する可能性があるエラーの種類について強い保証をするので、近似によって導入されたアーティファクトの検出と測定に役立ちます。3現実的に複雑なシーンでは、偏りのないアルゴリズムが可能な唯一の実用的な方法です。自信を持って言うと正しいです。
他のものが同じである、それは私たちが公平なアルゴリズムを好むべきであることは明らかです。グラフィックスにおける従来の知恵は、偏りのない方法は「とても費用のかかる」こと、および近似を行うことによって許容可能な画像をより短い時間で達成することができることである。しかし、この主張を裏付ける研究はほとんどありません。グラフィックスにおける光伝送アルゴリズムについては多くの研究がなされてきましたが、そのほとんどが偏りのないアルゴリズムに向けられています。我々の見解では、我々がそれらの能力を判断することができる前にかなり多くの研究が必要です。この論文の目的の1つは、これらの疑問を解決するのを助けるために、未知の方法では達成できることと達成できないことを探ることです。