Syoyo Fujita's Blog

raytracing monte carlo

Month: August, 2005

お詫び

いまさら気がついたのですが、lucille 開発ノートと、SBR 2004 のページが、
sourceforge.net の Perl のバージョンが変わったのか、
更新しようとするとエラーが出るようになっていました。
いろいろ調べてみましたが、どうにも原因がわかりません。

そのため、SBR 2004 は閲覧用に残すとして、
lucille 開発ノートは内容を RenderNote(wiki) のほうへ移管して、ページを閉じようと思います。

lucille 開発ノートに二点質問をいただいていたのですが、最近まったく見ていなくて気がつきませんでした。
ごめんなさい。回答は以下の通りです。

Q. 準モンテカルロのところが画像見れないですけど。
A. 画像のバックアップはあるのですが、リンクが絶対リンクのため、直すのが億劫になっていています、、、
準モンテカルロについては、幾人の方からご質問のメールをいただいています。
結構興味をもたれる方が多いようです。

準モンテカルロについては、時間を見つけて、

http://lucille.atso-net.jp/wiki/index.php?%C4%E3%BF%A9%A4%A4%B0%E3%A4%A4%CE%CC%CE%F3

のページに、リンク切れの画像も含めて、まとめていきたいと思います。

Q. MQOtoRIBのリンクが切れています。もう公開しないのですか。
A. 作成していただいた作者の方のページでもう公開していないようです。
lucille のソースコードツリーには、昔私が書いた MQOoRIB のコード

http://lucille.atso-net.jp/svn/lucille/tools/mqo2rib/

もあるのですが、もう古いのであまり役にたたないかもしれません。
最近はクロスプラットフォームの blender のほうに惹かれていますので、
blender のエクスポータを書くほうがプライオリティが高くなっています。
とはいえ、mqo も人気がありますので、 lucille が安定してきて
気が向いたら書くかもしれません。

Advertisements

wavelet noise and modified noise 1

ことしは、SIGGRAPH 2005 ではエイリアシングを低減する wavelet noise が、
Graphics Hardware 2005 では GPU での実装に適した modified noise for
evaluation on graphics hardware
が提案されました。

wavelet noise は低周波数を含まなく、
かつ完全に帯域制限(周波数があるレンジ内にある)されたノイズを生成することができます。
このノイズ関数を用いることで、エイリアシング問題が緩和されます。
Pixar の PhotoRealistic RenderMan では、これからはノイズ関数の実装には
この wavelet noise が用いられるとのことです。

Olano’s mofied noise は、2D テクスチャから 3D ノイズを生成でき、またハッシュのルックアップを
必要としないため、GPU での処理に適しています。
これからの GPU 上でのシェーダによるノイズの生成には、
このノイズ生成手法が用いられていくでしょう。

今年はノイズの当たり年といってもよいかもしれません。

ノイズは Perlin ノイズ使っとけばいいんじゃない?
と思っていましたが、今回これら二編の論文を通じて、
レンダラ書きとして、もっとノイズに関して学ぶ必要があると痛感しました。
Texturing and Modeling や、Lewis の solid noise の論文もこれから詳しく読んでいこうと思います。

Wavelet noise


左: 通常の Perlin ノイズ。右: ウェーブレットノイズ。
ウェーブレットノイズのほうは、遠方でもディテールがつぶれていないことに注目。

ウェーブレットノイズを簡単に説明すると、
元のノイズ画像を、一回縮小して拡大しなおして(つまり”ぼかす”)、
その結果を元のノイズから引くと、
低周波数成分を含まないノイズができる、ということです。

このような考えかたは、すでにいくつかの分野で用いられています。

フォトショップなどでの画像処理のテクニックで、
元画像を一度ぼかし(縮小フィルタリングと同じ)、
元画像からそのぼかした画像との差分を取ると、
よりディテールの向上した画像が生成できたりします。
デザイナの方はこの手法をよく知っているのではないでしょうか。

また、逆の操作となる考えかたで、テクスチャ圧縮への応用があります。

これは低ディテール(低周波成分)のテクスチャと、
変異成分(高周波数、だけどそれほど解像度は高くない)から、
もとのテクスチャを復元します。
低ディテールテクスチャなどは圧縮に適していますので、圧縮率が向上します。

本論文では、そのような処理が、ウェーブレット理論で説明できることを
示しています。
また、ダウンサンプリング -> アップサンプリング(つまり “ぼかす”)の操作において、
高周波成分を含まなくなるように、
ウェーブレット理論に従って最適なダウンサンプルフィルタカーネル(B-スプライン)の提案を行っています。
(つまり元のノイズ(高周波 + 低周波)から、
ダウンサンプリング -> アップサンプリングによるノイズ(低周波)を引くことで、
ウェーブレットノイズ(高周波)ができるように)

論文によれば、Perlin ノイズをフーリエ変換して解析してみると、
低周波と高周波の成分は含まず、周波数帯域は制限されています。


左: Perlin ノイズの画像  右: Perlin ノイズのフーリエ像

フーリエ像において、画像中心付近にプロット値があるのは低周波成分があることを示します。
画像外側にプロット値があるのは高周波成分があることを示します。

理論的には、この 0.5 より小さい部分、
つまり x^2 + y^2 < 1 の円内には周波数成分がない、
つまり黒色に なっているべきです。
(これは後述のノイズバンドに関連します)

さて、上図の Perlin ノイズは、帯域制限(band-limited)になっているとはいえども、
0.5 より小さい部分にも、
それなりに低周波成分が含まれてしまっています。

それに対して、ウェーブレットノイズでは、0.5 以下の部分の
低周波数成分はまったく含んでいません。


左: Wavelet ノイズの画像  右: Wavelet ノイズのフーリエ像

右のフーリエ像が四角く穴(銭形?)が開いているのは、
フィルタカーネルが非対称であるためとのことです。

Noise band

ノイズを使ってプロシージャルシェーディングを行うときには、ご存知の通り、
ノイズは 1 回だけ使われるのではなく、
しばしば複数の周期のことなるノイズに重みをつけて重ね合わせて用いられます。
たとえば turbulance や fBm などですね。つまり、

w0 * noise(x) + w1 * noise(2 * x) + w2 * noise(4 * x) + …

という感じです。右の項になるほど、ノイズの周波数は高くなります。
このときの各ノイズを、論文やコミュニティではバンド(band)と読んでいます。

ここで、やっとPerlin ノイズの問題が明確になってきます。

各バンドの周波数成分は、解像度が半分になればおおよそ周波数成分も半分になります。
これはつまり、一段低い解像度(1/2 倍)の Perlin ノイズは、
そのフーリエ像も大体 1/2 に縮小することになります。
(必ずしもこれは成り立たないのかもしれません。
Wavelet ノイズでは、なるべくこのようになるようにフィルタカーネルを設定しているようです)

つまり、ノイズ関数のフーリエ像では、 0.5 以下の部分には周波数がないことが望まれます。
その一段下の解像度のノイズの周波数が、0.0 – 0.5 の部分の部分に埋め込まれるようにできるからです。

下の論文に掲載の図は、3 つのバンド(1/4, 1/2, 1 の解像度)
の合成で出来た関数のフーリエ像です。


左: Perlin ノイズのフーリエ像  右: wavelet ノイズのフーリエ像
3 つのノイズバンドに個別に色付けしてあります。
黄(低周波ノイズバンド)、紫(中)、青(高)です。

黄、紫、青の順で円環が大きくなり、またお互い重なりがないのが理想です。
(つまりおのおののノイズバンドが真に帯域制限されており、直交している)
wavelet ノイズはほぼこの要求を満たしていますが、
Perlin ノイズは、もともとの各バンドでのフーリエ像に 0.5 以下の部分にも
周波数が存在するため、複数のバンドを合成すると、
周波数が重なりあってしまって白くなってしまっているのがわかります。

Wavelet ノイズは、そのフーリエ像において、
青で色付けされたバンドは円の中に四角形の形をし、
そのひとつ下の解像度である紫のバンドは四角形の中に円、
そしてそのまたひとつ下の解像度である黄色のバンドは円の中に四角形、
というかたちとなっています。
一段ダウンサンプルすると形が変わるのは、
これはダウンサンプルに用いる B スプライン関数のフィルタによるもののようです。

ディテールの消失(loss-of-detail)とエイリアシング(aliasing)

論文では、通常の Perlin ノイズを用いた場合、
上記のバンド間での周波数の重なりの問題により、
シェーディング時にディテールの消失とエイリアシングのトレードオフ問題が生じることを指摘しています。

Perlin ノイズの各バンドは、それなりに周波数の帯域が広いため、
あるサンプリングレートで十分に表現可能な低周波成分と、
エイリアシングを引き起こしてしまうような高周波成分の両方が含まれていることになります。

これはつまり、あるノイズバンドが含んでいる周波数帯が、
シェーディングのサンプリングレートの基準からみてナイキスト周波数付近にあるとき、
(論文では 1 ピクセル幅を基準にしているようです)
このノイズバンドを切り捨ててしまうと、
ディテールが消失(サンプリングレートで十分に表現可能な低周波領域がなくなるため)してしまい、
逆にこのバンドを含ませるようにすると、
エイリアシングが生じてしまう(サンプリングレートで表現不可能な高周波領域が入り込む)、
というトレードオフの問題が生じるのです。

3D -> 2Dノイズの問題

さらにひどく、Perlin ノイズ、ウェーブレットノイズともに解決できない本質的な問題として、
3D ノイズを 2D 面に用いるときの問題を論文では提示しています。

たとえば、3D ノイズを使って、2D のサーフェスにシェーディングを施すことは
プロシージャルシェーディングではよく用いられます。この場合、
サーフェスの法線と垂直方向の平面で 3D ノイズを切り取り、
その平面(2D)のノイズを利用することになります。

このとき、3D ノイズが完全に帯域制限されていたとしても、
一般的にはそれを 2D 面に貼り付けたとき、
結果は帯域制限されません
(つまり任意の周波数成分が含まれてしまう)


3D Perlin ノイズから 2D 面を切り出したノイズ
フーリエ像では帯域制限性を示さず、低周波成分も含まれてしまっている


3D ウェーブレットノイズから 2D 面を切り出したノイズ
フーリエ像では Perlin ノイズと同様に帯域制限性を示さず、低周波成分が含まれてしまっている。
(わずかに銭形を示してはいるが)

この理由は、フーリエスライス理論により説明できます。
(フーリエスライスは、今年の SIGGRAPH 2005 の論文でも、
私が知る限りほかに 2 つの論文でも取り上げられています。
Fourier Slice Photography, A Frequency Analysis of Light
Transport)

射影ウェーブレットノイズ

本論文では、さらにこのような 3D -> 2D ノイズの問題を解決する、
射影ウェーブレットノイズ(Projected wavelet noise)の提案も行っています。

射影ウェーブレットノイズを使うことにより、帯域制限の性質を保ちつつ、
3D -> 2D ノイズを作成することができます。

To be continued…

pthread + gcc + sse 問題解決

以前、linux + gcc にて SSE と pthread を同時に使うと、
スレッド関数内での SSE ローカル変数が 16 byte アラインされないという問題

http://lucille.sourceforge.net/blog/archives/000308.html

がありましたが、これは実際には glibc のバグで、最新の glibc では fix されています。

たぶん bug ID 723 のバグです。
http://sources.redhat.com/bugzilla/show_bug.cgi?id=723

glibc 2.3 系では修正されているようです。
ためしに glibc 2.3.2 の環境で再度テストプログラムを実行してみましたが、
ちゃんと 16 byte アラインされていました。問題なさそうです。

SSE 演算に使うローカル変数は全部動的確保かスタティック領域に
作るように書き直さないといけないのかなー、めんどうだなー、と
思っていたのですが、時が解決してくれました。

SSE と pthread(実際には clone() or linuxthread) を同時に使う場合は、
glibc 2.3 以上を使うほうがよさそうです。

最近ついにデュアルコアのプロセッサが市場に出回りはじめました。
これからのパソコンのトレンドである多数コアプロセッサ
の始まりではないでしょうか( +64 bit 化も)。

これからはレンダラもそうですが、プログラムのマルチスレッド化
がより重要になってくると思います。

大域照明機能をつかわなければ、バケット単位で十分な並列度が
出ていると思われる prman でさえ、時期パージョン(version 13)では
ついに(というかやっと?)マルチスレッド化になるとのことです。

lucille の方向性

長期取材旅行では、数多くのレンダラ野郎と出会いました。

やはり「レンダラ野郎同士は惹かれあう」というのは本当だったのか…

とりあえず、世の中では結構なひとたちが(オフラインの)レンダラ野郎を欲している
ことがわかりました。

レンダラを書いていれば、とりあえず 10 年は食いっぱぐれる心配はなさそうです。

レンダラ野郎たちからのご助言をいただき、
これからの lucille の方向性を考えてまとめてみました。

レンダラ側
– モーションブラー
– アンチエイリアシング(マルチサンプリング)
– ERPT などの大域照明
– メモリに入らないようなシーン(やテクスチャ)を扱えるようにするためのメモリ管理機構(MMU)
– 空間データ構造
シェーダ側
– 任意の Du, Dv 関数の実装

モーションブラー

モーションブラーは、特にプロダクションにおいては必須の機能です。
やはりモーションブラーがないと使い物にならないとのこと(プロダクションにおいては)
レイトレベースのレンダラで分散レイトレなどではなく、効率よくモーションブラー
を実現する手法はまだまだ open な問題だと思います。

たとえば 1 フレーム内で画面の端から端まで移動する物体でも
きれいに効率的にモーションブラーがかかるなど。

なにかひらめかないかなぁ…

アンチエイリアシング(マルチサンプリング)

これはとくにピクセルジャギーを減らすためのアンチエイリアシング(マルチ/スーパーサンプリング)と、
シェーダのアンチエイリアシングになります。
やはりプロダクションのものはよく出来ているだけあって、物体のふちなどの
ジャギーもまったく見えません。

結局のところ、シェーダアンチエイリアシングを除くと、
一次レイがヒットする(つまりカメラから直接見える)物体のふちの
ジャギーが一番目に付く要素であるので、これらのアンチエイリアシングには、
一次処理はスキャンラインなどでジオメトリックにアンチエイリアシングする
のが結果画像が一番きれいに出そうです。

もちろんスキャンライン + 2 次反射以降はレイトレというハイブリッドではなく、
できれば純粋なレイトレで一次レイもうまくアンチエイリアシングできないものかな
と思ったりもしますが、8×8 のsupersample/jitter sampling でも物体のふちの部分に見た目で
ジャギーが見えてしまうくらいなので、A-buffer やポリゴンのプレフィルタリングの
ほうが正確でコストがかからずに処理できそうに思えています。

ERPT などの大域照明

個人的には、そろそろフォトンマップ + final gather はやめて、
ERPT や MLT などのように純粋な
パストレーシングベースの大域照明をやりたいと思っています。
フォトンマップ系はすでに多くの実装がありますし、
もちろん(パラメータがうまく調整されていれば)見た目の品質が非常に高いのですが、
レンダラ側の実装者からすると、
density estimation +  final gather というのはあまりエレガントではなく、
けっこう、既存のほかのレンダリング機能(たとえばアンチエイリアシングなど)
との組み合わせが面倒になってしまうという問題があります。

最近は ERPT もそうですが、Importance Resampling も提案されてきていますので、
よりシンプルかつ効率的な大域照明のサンプリング手法が見つかりそうな感じがします。
もちろん、ノイズはまだまだ消せそうにありませんが。

「一次レイはスキャンラインのハイブリッド方法がいい」
と言っているのでこれとちょっと矛盾する点ができてしまいますけどね。

メモリ管理機構(MMU)

えてしてシーン作成者は、レンダリング時のメモリ使用量のことなど考えずに
シーンを作ります。テクスチャも馬鹿でかいです。とくに 2k とかの画面サイズになると、
テクスチャ一枚でもすんげー詳細で容量が大きくなります。
ジオメトリ、テクスチャともに、 OS のスワップファイルのような感じで、
処理する分だけメモリに読み込み、必要がなくなったら HDD に退避、
というようにして一度にメモリに入りきらないようなシーンでもレンダリングできるように
していかなくてはなりません。

こちらは OS や Linux の教科書に書いてあるような単純なもので十分でしょう。
ちょっと懸念するのは、メモリにアクセスする場合に、
常にアドレス変換 & キャッシュのチェックをしなければならなくなるという
ことでしょうか。

mental ray は、64 bit 化でレンダリング速度が 100 倍! と
謳っているようですが、64 bit 化で単純に演算速度がそんなに早くなるわけ
ないので、ここらへんのメモリ管理機構をソフトウェアでやっていたのを、
64 bit アドレッシングなのでする必要がなくなったことによるパフォーマンスアップが
主たる要因のような気がします。

空間データ構造

レイトレの空間データ構造をどうするかは、
主に現在グリッド(ハッシュ)教と kd-tree 教が激しいバトルを繰り広げているそうです。

Arnold やとあるプロダクションのインハウスレンダラでは、
グリッドハッシュ法を用いているとのことです。
Arnold では、グリッドのサイズは 500^3 くらいで分割しているとのこと。

kd-tree は構築などにおける精度的な問題があるとのことで、
結構グリッド(グリッドハッシュ)が用いられているようです。

平原などの巨大なシーンなどは、実制作では分割してレンダリングし、
コンポジットで結合することで、巨大な平原にとっても密で小さな物体が
ぽつんと存在するという、ひとつのセルに膨大なプリミティブが集中してしまう
グリッドの問題を回避しているとのことです。

lucille は一様グリッドですが、前々からハッシュベースのグリッドを試してみたいと
思っていました。今回はそのよい後押しになりそうです。

とはいえ、グリッド教の中にも、kd-tree よさそげ、という声も聞かれます。
特に新興のレンダラには kd-tree 教が多いようです。

任意の Du, Dv 関数の実装

RenderMan シェーディング言語には Du(), Dv(), ( Deriv() ) という、
任意の引数の微分を求めることができる関数があります。

RenderMan シェーディング言語の仕様において、 Du(), Dv() の微分関数を実装できるか
がシェーダ実装のアーキティクチャ設計におけるキモといえるでしょう。
それ以外は力技でだいたい出来るとのこと。

一番良い解は、シェーダの実行をスタックマシンで行い、
REYES 的なマイクロポリゴンベースの
レンダラアーキティクチャにすることです。

もっとも困難な条件(アーキティクチャ)は、シェーダの実行はネイティブコード(DLL)で行い、
レイトレをベースにしているレンダラアーキティクチャです。lucille がこれにあたります。

Du(), Dv() の実装が困難な理由は、この微分関数が任意の関数を引数に取る可能性が
あるからです。たとえば、

Du(x * x + normalize(I)b)

という関数の微分値を取ることができたりするのです。

レイトレは基本的にポイントサンプリングですから、
微分値を求めることは困難です。

レイ微分や 4 本のレイを同時に飛ばす(SIMD)などを
行えば微分値を取ることも出来ますが、
たとえばシェーダをネイティブコードで実行するアーキティクチャの場合、
Du() が呼ばれた時点で微分を計算するために

“どうやって”隣のレイトレのサンプル点におけるシェーダの情報を取得するのか?

という問題があります。

スタックマシンアーキティクチャであれば、
Du のインストラクションが呼ばれた時点での
情報を保持しておいてシェーダ実行を停止、
次のサンプルのシェーディングを行うようにすることで
解決させることができるでしょう。

レイトレ + ネイティブコードのアーキの場合、
現在ではたぶん二つの”解”というものを教えていただきました。
ヒントは pthread の実装および kilauea の spot エンジンです。
とはいえ、特に前者においてはネイティブコードのスタックを
退避させるという、あまりエレガントな解決方法ではないようです。
これについては、なにかしらのエレガントな手法を発見できれば、
きっと論文レベルのものになることでしょう。 
 

…と、結局まとめてみると、レンダラをプロダクションレベルで使うには、
どのような機能が必要か、ということになってしまいました。

とはいえ、プロダクションでの大規模、大容量、安定、高品質、そしてなおかつ
レンダリング時間が短い(1 フレーム 2, 3 時間が望ましいらしい)という要求は、
ある意味レンダラへの究極のストレステストともいえますので、
これがレイトレ + シェーダのアーキティクチャのレンダラで
クリアできるとなると、きっとすばらしい道が開けていけるのではないか
と思っています。

レンダラは突き詰めると奥が深いですね。
やることはいっぱいあって尽きることがありません。

個々最近はあまり昔ほど lucille 自体の実装も進めることができていませんが、
とはいえバージョン 1 の完成が 198 年後の予定ですので、
マイペースで続けていきたいと思っています。