Introduction
Hamming という有名な数学者，計算機科学者がいる．彼は Digital Filter という本を書いており，最近私はこれを読んでいる．この本を読んでわかったことをちょっと書いてみようと思う．
まずはeigenvalue と transfer function というものに関して話をしてみたいと思う．しかしいきなりこんな eigen なんとかと言われても困るだろうから，まずは目的から話をしよう．なんでこんなものを考えるのか．という部分である．私が論文を読んだ後の通常の感想は，「わかならいなあ」あるいは「だから何なんだ」である．しかし，できれば「これはすごい」と言いたいのだ．「これはすごい」と言う時はたいてい何がやりたいのかがわかっていて，それができた時である．高校数学のレベルでなんとか説明したいが，しかし，一つステップが必要なようだ．それはスカラ，ベクトル，そして関数の関係である．まずはこれらが実は抽象的には同じものとして扱えるという話をしたい．多分，高校生でもベクトルはスカラの拡張である，あるいは，スカラはベクトルの特殊な場合であるということはわかっているだろう．でも，関数がベクトルの拡張であるという話は聞いたことがないかもしれないのでそこからはじめよう．
Overview idea of Bidirectional path tracing
Forward path tracing では，光が来る方向が実際にはわかっていないので，サンプルして確かめるしかない．しかし，光源は通常わかっているのだから，光源から光がどのように伝わるのかを計算して，光が伝播している場所を視点からサンプルすると効率がよい．ここでまた bias がかからないようにするにはどうするかという話があり，論文ではそれについて述べられている．
たとえば，forward path tracing で難点のある場合は，プロジェクタから光が壁に投影されているような場合である．forward 法では視点から壁にパスがある時，プロジェクタの方向はより高い可能性で見ることはできるが，プロジェクタが投影している画像をサンプルするのは大変難しいことが想像できる．プロジェクタのレンズをかなりの密度でサンプルする必要があるからだ．これは forward 法ではまったく不可能な場合というわけではないが，実質的には投影されている画像の内容がはっきりわかるということいはまずないだろう．
このような場合，プロジェクタから画像を投影し，壁に写ったその結果をサンプルする方が効率良くできそうだということは予測できるかと思う．Bidirectional path tracing の基本的考えはこのようなものでそんなに間違いではないと思う．
Overview idea of Metropolis sampling algorithm
Bidirectional path tracing 法でも難しいパスというものがある．論文の例では隣の部屋に光源があり，ドアがわずかに開いているという状況である．光源からサンプルする場合にも bias がかかってはいけないので，特定の方向にだけサンプルするというわけにはいかない．そうすると計算できないパスができてしまう．そこで最初になんらかの方法で難しいパスみつけることができたら，それを元に重点的に適応的にサンプルできないかというのが Metropolis 法のアイデアである．(Metropolis は提唱者の名前)
ドアがわずかに開いて，そこからほのかに光が漏れているような状況を考える．論文で提案されている方法では，最初のパス探しは Bidirectional pathtracing 法を使う．そしてもし光が来る方法がわずかでもみつかったら，ある確率でそのパスを摂動させる．
ところで，私は Geometry 計算に Variational な手法を使うことが多かった．それは問題をエネルギーの形で解釈して解くという手法である．ただ，どんなエネルギでもいいわけではなく，そのデザインが難しい．しかし，基本的な考えは，エネルギ関数がよくわからないので，それを摂動させて，もしエネルギが低くなるような場合にはそちらの解を探索する．というのが variational 法の基本である．サンプリングの場合には gradient を求めることが容易ではないが，基本的な考えが同じであることには驚く．
Veach の論文を読んでみて思ったのは，特に奇をてらった方法ではなく，基本的で一般的な手法，ある意味，正統な手法を使って述べられていることがうれしい．正統な手法というものは様々な分野で試され，考えぬかれたものであるから，それを基礎としているということもとてもすばらしいと思う．
さて，一通り Veach の論文を見ることができた．とても楽しかった．私のVeach 論文への annotation の話もここでひとまず終える．さて次は何を読もうかな．
Forward path tracing では，光が来る方向が実際にはわかっていないので，サンプルして確かめるしかない．しかし，光源は通常わかっているのだから，光源から光がどのように伝わるのかを計算して，光が伝播している場所を視点からサンプルすると効率がよい．ここでまた bias がかからないようにするにはどうするかという話があり，論文ではそれについて述べられている．
たとえば，forward path tracing で難点のある場合は，プロジェクタから光が壁に投影されているような場合である．forward 法では視点から壁にパスがある時，プロジェクタの方向はより高い可能性で見ることはできるが，プロジェクタが投影している画像をサンプルするのは大変難しいことが想像できる．プロジェクタのレンズをかなりの密度でサンプルする必要があるからだ．これは forward 法ではまったく不可能な場合というわけではないが，実質的には投影されている画像の内容がはっきりわかるということいはまずないだろう．
このような場合，プロジェクタから画像を投影し，壁に写ったその結果をサンプルする方が効率良くできそうだということは予測できるかと思う．Bidirectional path tracing の基本的考えはこのようなものでそんなに間違いではないと思う．
Overview idea of Metropolis sampling algorithm
Bidirectional path tracing 法でも難しいパスというものがある．論文の例では隣の部屋に光源があり，ドアがわずかに開いているという状況である．光源からサンプルする場合にも bias がかかってはいけないので，特定の方向にだけサンプルするというわけにはいかない．そうすると計算できないパスができてしまう．そこで最初になんらかの方法で難しいパスみつけることができたら，それを元に重点的に適応的にサンプルできないかというのが Metropolis 法のアイデアである．(Metropolis は提唱者の名前)
ドアがわずかに開いて，そこからほのかに光が漏れているような状況を考える．論文で提案されている方法では，最初のパス探しは Bidirectional pathtracing 法を使う．そしてもし光が来る方法がわずかでもみつかったら，ある確率でそのパスを摂動させる．
ところで，私は Geometry 計算に Variational な手法を使うことが多かった．それは問題をエネルギーの形で解釈して解くという手法である．ただ，どんなエネルギでもいいわけではなく，そのデザインが難しい．しかし，基本的な考えは，エネルギ関数がよくわからないので，それを摂動させて，もしエネルギが低くなるような場合にはそちらの解を探索する．というのが variational 法の基本である．サンプリングの場合には gradient を求めることが容易ではないが，基本的な考えが同じであることには驚く．
Veach の論文を読んでみて思ったのは，特に奇をてらった方法ではなく，基本的で一般的な手法，ある意味，正統な手法を使って述べられていることがうれしい．正統な手法というものは様々な分野で試され，考えぬかれたものであるから，それを基礎としているということもとてもすばらしいと思う．
さて，一通り Veach の論文を見ることができた．とても楽しかった．私のVeach 論文への annotation の話もここでひとまず終える．さて次は何を読もうかな．
Bidirectional path tracing
Bidirectional path tracing においてどのように vertex を接続するのかに関して尋ねたところ，様々な方法があるが，生成したパスの組に関してそれぞれのvertex を接続する方法がおすすめということであった．生成されたパス全ての組合せを考えるとこれは組合せになって手に負えなくなるが，光源からのもの一つと視点からのもの一つの組で考えることで効率良く contribution を計算できる．
図1 Connect vertices in Bidirectional path tracing
図1にあるように，(この場合は occlusion がないが)計算した ray の数とcontribution を見ると，効率良く contribution が計算できている．
Overview idea of multiple importance sampling method
この論文には様々な重要なアイデアが含まれている．簡単に 9 章からあとのアイデアをまとめておこう．
環境を一様に無限にサンプルすることができればよいが，限られた計算資源ではそうもいかない．そのために，いくつかの異なる sampling 手法を用いる．しかしそれぞれの sampling 手法には得手，不得手が存在する．Multiple importance sampling method 法はそれぞれの良い点をいかに組合せることができるか，しかも unbias のままで組合せることができることがすばらしい．また，この手法は特に光輸送に限ったことではないことも注意すること．
ここで提案されている sampling 法は，光源の方向に着目してサンプルする手法と material の BRDF に基づいたサンプル法を例にとっている．光がどこからくるのか，あるいは来ないのかがわかればより効率良く計算できる．たとえば，光が来ない方向がわかっているなら，そちらをサンプルしても結果に関係がない．だから光源方向を見ることは意味がある．また，BRDF はどういう分布で光が反射するのかを示しているので，よく反射する方向を見ることにも意味がある．あるいは可視性なども考えられる．
Thanks to Daniel, Leo, and Carsten.
Bidirectional path tracing においてどのように vertex を接続するのかに関して尋ねたところ，様々な方法があるが，生成したパスの組に関してそれぞれのvertex を接続する方法がおすすめということであった．生成されたパス全ての組合せを考えるとこれは組合せになって手に負えなくなるが，光源からのもの一つと視点からのもの一つの組で考えることで効率良く contribution を計算できる．
図1 Connect vertices in Bidirectional path tracing
図1にあるように，(この場合は occlusion がないが)計算した ray の数とcontribution を見ると，効率良く contribution が計算できている．
Overview idea of multiple importance sampling method
この論文には様々な重要なアイデアが含まれている．簡単に 9 章からあとのアイデアをまとめておこう．
環境を一様に無限にサンプルすることができればよいが，限られた計算資源ではそうもいかない．そのために，いくつかの異なる sampling 手法を用いる．しかしそれぞれの sampling 手法には得手，不得手が存在する．Multiple importance sampling method 法はそれぞれの良い点をいかに組合せることができるか，しかも unbias のままで組合せることができることがすばらしい．また，この手法は特に光輸送に限ったことではないことも注意すること．
ここで提案されている sampling 法は，光源の方向に着目してサンプルする手法と material の BRDF に基づいたサンプル法を例にとっている．光がどこからくるのか，あるいは来ないのかがわかればより効率良く計算できる．たとえば，光が来ない方向がわかっているなら，そちらをサンプルしても結果に関係がない．だから光源方向を見ることは意味がある．また，BRDF はどういう分布で光が反射するのかを示しているので，よく反射する方向を見ることにも意味がある．あるいは可視性なども考えられる．
Thanks to Daniel, Leo, and Carsten.