Blue-noise Dithered Samplingの実験をしてみた

これはレイトレ合宿4!?のアドベントカレンダー記事です。

Blue-noise Dithered Sampling

先日開催されたSIGGRAPH2016には私も参加しましたが、興味深いものの実装が大変そうなものから何の役に立つのかわからない技術まで様々な知見を得ることができました。
その中でも割とさくっと実装できそうで、かつ効果もありそうな発表があり、それがBlue-noise Dithered Samplingです。これは、Roll the Diceというトークの中の発表の一つで、Arnoldという有名なレイトレーシング（パストレーシング）ベースのオフライン商用レンダラを開発しているSolid Angle社による成果ということになっています。
今回は、この発表を元に適当に実装して簡単な実験をしてみました。

実装は以下に置いてあります。

github.com

Blue-noise 

ブルーノイズについてはあまり深くは説明しませんが、以下の図のように各点間の距離がなんとなく等しくなるように平面上に散らばっている点群の性質をブルーノイズと呼んだりします。

(http://www.geometry.caltech.edu/BlueNoise/より)

二次元平面からのサンプリングはコンピュータグラフィックスにおいて様々な箇所で頻出の問題です。完全にランダムに行えば、それはホワイトノイズになります。周波数領域で周波数に偏りが無い（＝ランダム）だからです。ブルーノイズの場合、低周波成分が小さく、高周波成分が大きい、といった特性を持っています。人の網膜細胞もこのパターンらしいです。

さて、ブルーノイズはもともと画像の二値化などのディザリング処理において良くつかわれていました。今回の手法は、このアイディアをサンプリングに応用することでいい感じにディザリングされたレンダリング画像を少ないサンプル数で得る、という手法になります。

実装概要

まず、解きたいレンダリングの問題が何次元の積分なのかについて考えます。例えば、モーションブラーであれば時間方向に積分するため１次元の積分になり、アンビエントオクルージョンであれば半球上で積分するため２次元の積分になります。
このように、解きたい積分がd次元のとき、d次元分の乱数列（[0, 1)の範囲）を生成します。２次元の場合、（0.3152, 0.8611）みたいな感じになりますね。普通のレンダリングの場合、このような乱数列を各ピクセルごとに独立に複数回数生成してモンテカルロ積分のサンプルの生成に利用することで画像を得ます。

しかし、今回の場合は全ピクセルで同一の乱数列を使うとします。そして、それぞれの乱数列をピクセルごとに事前に決めておいたd次元の値（[0, 1)の範囲）でオフセットします。もし、事前に決めておいた値が以下の図のように完全にランダムなら、結局各ピクセルごとに独立の乱数列を生成するのとほとんど変わりません。

（128x128、[0, 1)の範囲の乱数列）

しかし、このオフセット値を以下の図のようにブルーノイズを用いればレンダリング結果はディザリングされたものになり、より望ましくなります。

これが今回の手法の要旨です。

ブルーノイズオフセットの生成

さて、それではブルーノイズオフセット値はどのようにして得るのでしょうか。これは、論文に詳しく解説されていますが、焼きなまし法による最適化によって得るようです。
まず、与えられたサイズのオフセットマスク画像をd次元、[0, 1)の範囲の乱数列で初期化します。そして、あるオフセット値と別のオフセット値の間で定義されるエネルギー関数の総和を最小化するように、適当に選んだ二つのオフセット値を入れ替える、ということを反復的に行えば良いらしいです。最小化したい式は以下のようになります。

（https://www.solidangle.com/research/dither_abstract.pdfより）

ここでpi, qiはマスク上の位置で、ps, qsは各サンプル、dはオフセットの次元です。分母のσは定数になります。

で、これを実装するわけですけど今回自分は焼きなまし法は特につかわず（パラメータチューニングとか面倒だし）エネルギー関数を事前に計算しておいて、適当にオフセット値を入れ替え、再計算したエネルギー関数が減少していれば入れ替えを採用、減少してなければ入れ替えは棄却、ということを指定された回数繰り返すようにしました。
さらに、エネルギー計算の再計算も自分以外の全オフセット値に対して実行していると重いため、自分の周囲にのみ着目するような近似計算にして高速化を行ってみました。

わりと適当でしたが、それなりにうまく生成されているように見えたので良しとします。（若干品質が低いような気もする）

実際のレンダリング

レンダリングするときは、既に解説したようにブルーノイズディザリングしたいモンテカルロ積分のサンプル生成にブルーノイズでオフセットした値を投入するだけです。
今回の実験ではモーションブラー（１次元）とアンビエントオクルージョン（２次元）の二つについて試してみました。

結果

それでは結果です。画像は全て512x512でレンダリングしています。オフセットマスクのサイズは128x128です。

以下はモーションブラーの結果です。

（ランダムオフセット / 1spp（1 sample per pixel））

（ブルーノイズ / 1spp）

ブルーノイズの方はランダムに比べてノイズが均等に分布していることがわかります。
ただ、サンプル数を１から９sppに上げると両者の差は小さくなりました。（ランダムオフセット / 9spp）

（ブルーノイズ / 9spp）

ちなみに、リファレンスとして256サンプリングすると以下のようになります。

次に二次元の積分、アンビエントオクルージョンの結果です。

（ランダムオフセット / 1spp）

（ブルーノイズ / 1spp）

モーションブラーほどではありませんが、ブルーノイズの方が良い結果を得られています。しかし、やはりサンプル数を増やすと以下のように、結果は似たようなものになりました。

（ランダムオフセット / 9spp）

（ブルーノイズ / 9spp）

ちなみに以下はリファレンスです。

アンビエントオクルージョンも設定によってはブルーノイズの方がかなり良い結果を出すこともあります。例えば以下。

（ランダムオフセット / 1spp）

（ブルーノイズ / 1spp）

（リファレンス）

まとめ

どうも高次元の積分になると効果が薄まっていくようです。この手のサンプリング手法は大体そういう傾向がありますね（Low Descrepancy Sequenceとか）。また、サンプル数を増やすと割とすぐ似たような結果になってしまいました。なんかバグってる可能性もありますが、元の論文のアブストの結果画像も1sppで比較してるのが多く、9sppで比較してるのはボリュームレンダリングだけだったので相性みたいなのがあるのかもしれません。

また、マスク画像のサイズも、今回は適当に128x128と決めましたが結果に影響あるかもしれません。

しかし、1sppで比較した時は間違いなく単純なランダムよりはいい結果になっています。オフラインで長時間レンダリングできるシチュエーションだとちょっと微妙かもしれませんが、むしろリアルタイムレンダリングで、サンプル数を出来る限り減らしたいような状況で活きてくる手法かもしれません。

おわり。