Syoyo Fujita's Blog

raytracing monte carlo

Month: June, 2005

Hexagonal Storage Scheme for Interleaved Frame Buffers and Textures

Bando 先生のところで公開させました。

Hexagonal Storage Scheme for Interleaved Frame Buffers and
Textures
http://nis-lab.is.s.u-tokyo.ac.jp/~ybando/hexagon/index.html

そのうち詳しく解説したいと思います。

簡単に言ってしまえば、

o 六角形というパターンが自然界で最適である
o そのパターンを論理演算のみで求める式を導出(ルックアップテーブルも使わない)
o 結果としてメモリアクセスが分散されてパフォーマンスが向上する

という感じです。

Advertisements

GLSL Mandelbrot on geforce 6800 ultra

前回 geforce 6800 (GT) では 3dlabs の glsldemo でマンデルブローが動かなかったと
書きましたが、geforce 6800 ultra に換装したら動きました。
結構 saku saku。Julia set も saku saku。

あれ? 6800 GT で動かしたときは動かなかったのに?
なぜだろう。

そういえば、換装ついでにコンパネで描画クオリティの設定を、
高パフォーマンス(低品質)に設定したのですが、それが原因だったのかな?

Importance Resampling for Global Illumination

Justin Talbot, David Cline, and Parris Egbert.
Importance Resampling for Global
Illumination

Eurographics Symposium on Rendering 2005

http://students.cs.byu.edu/~jtalbot/justin/papers/resampling_egsr2005.php

つ、ついに、、、、
いわゆる逐次モンテカルロ法、パーティクルフィルタ
と呼ばれるたぐいの手法を大域照明へ適用した論文の出現です。
今年の SIGGRAPH 2005 採択論文である ERPT と同じ大学(BYU)からです。

本論文では、インポータンスリサンプリング(論文では Resampled Importance Sampling(RIS)
と呼んでいる)の大域照明への応用です。

基本はインポータンスサンプリングですが、近年はやっている(注目されている)
逐次モンテカルロ法(パーティクルフィルタ)の考えを基にしています。

概要としては、求めたい分布 g に近い(近くなくてもいいのかもしれない)、
ソース分布 p から M 個のサンプル点を抽出し、
それらサンプル点に重みをつけてそこからさらに N 個のサンプリング点を
抽出して(リサンプリング) g と同じ分布を得るという、二段階の手法です。

この最初のステップの M 個が、分布を調べるためにとりあえずテストで
放出してみるパーティクルで、そこから”フィルタ”をかけて最終的な N 個の
サンプル点を得る、という感じで捉えてみるとわかりやすいかもしれないです。

これをたとえば時間軸で繰り返ていくと、
いわゆる画像解析や実時間画像認識で使われる
パーティクルフィルタと言えるのかな?

RIS の一番の特徴は、インポータンスサンプリングが出来ない
(たとえば累積密度関数(Cumulative Density Function, CDF)が求められない関数など)
状況でも、インポータンスサンプリングをやっちゃうというなんとも
シュゴーな性質です。

シェーダのインポータンスサンプリングに逐次モンテカルロ法が使えないかなーと
思っていましたが、まさにこの手法が適用できそうな感じです。

また、既存のレンダリングフレームワークにインポータンスサンプリングを
実装するには、通常フレームワークを修正する必要がありますが、
RIS では特別な修正を加えることなく実装できるとのこと。

すでに RIS の考えは、Peter Sirley や、SIGGRAPH 2004 の Skech で発表され、
EGSR 2005 にも採択されている David Burke
Bidirectional Importance Sampling for
Illumination from Environment Map でも提案されていますが、本論文は、
よりその理論を一般化し、また最適なパラメータの求めかたを提案しているとのこと。

論文では、RIS は通常のインポータンスサンプリングよりも、
同じレンダリング時間でも分散を 10 – 70 % 程度減らす効果があるとのこと。
(実際に論文の figure を見てみるとそれほどでもない感じですが)
 
メトロポリス 光輸送につづく、 21 世紀初の新たなレンダリングアルゴリズム
の出現の始まりといえるのではないでしょうか?
(モンテカルロ法の範疇にとどまってはいるけれども)

うーむ、ERPT に加えて、このインポータンスリサンプリングも
実装してみたいですね。

ちなみに、逐次モンテカルロ法のバイブルは、

Arnaud Doucet, Nando De Freitas, Neil Gordon
Sequential Monte Carlo Methods in Practice
http://www.amazon.co.jp/exec/obidos/ASIN/0387951466

です。

とりあえず買ってはみたのですが、あまり読んでいませんでした。
これからいろいろ読んでみようかな。

第一著者の Doucet というひとは、逐次モンテカルロ法でとても有名らしいです。
少し前に日本の統数研に来ていて、
私が統数研に遊びに言ったときにたまたますれ違ったみたいです。
(あとであのひとが Doucet だよと教えてもらった)
めっちゃ若い人でした。

ソフトウェア GLSL 対応状況

ソフトウェアモードでの GLSL の対応状況、
つまりは OpenGL ソフトウェアラスタライザのパフォーマンスを調べてみました。
GLSL をハードウェアの制限なしに走らせたい場合を考えてみたかったので。

NVIDIA(windows)
最新のドライバで 2.0 に対応したので、3dlabs の glsldemo が動く。
geforce 6800 でもマンデルブローは動かないので nvemulate.exe
でソフトウェアモードにしてみた。絵が 1 枚出てくるのに 4, 5 分くらいかかる。
むちゃんこ重い、、、、  
ちなみに NVIDIA が公開している OpenGL 2.0 のノートを見ると、
noise() 関数は実装されていないとのこと。まああたりまえといえば当たり前。

ATI(windows)
同じく 3dlabs の glsldemo を動かしてみる。
マンデルブローを実行すると強制ソフトウェアモードになるみたい(X800 でも)。
でもこれも NV と同じくむちゃんこ重い、、、、
しかもマンデルブローの結果はなんか変。
ところで、ATI ではユーザがソフトウェアモードに切り替えられるようにできる
ツールとかあるんでしょうか?

Mac OS X
Developer Tools でインストールされる GLSLshowpiece デモを動かす。
結構早い。マンデルブローも 3, 4 fps くらいでうごく(PowerBook G4)。
noise() も動く。

総評

NV, ATI のソフトウェア OpenGL レンダラはむちゃくちゃ重くて使い物にならない。
これは結構残念。
まあ本来であればリファレンスのためにつくってあるものでしょうから、
速度よりも精度を重視しているのでしょう。

Mac OS X のソフトウェア OpenGL はそこそこ動く。AltiVec にも最適化されているらしい。
きっとハードで対応できない、もしくは古いハードでやるより CPU のほうが効率的な場合
の第二の OpenGL レンダラとしてソフトウェアレンダラを
使うという位置づけなのでしょう。速度 > 精度か?

というわけで、GLSL をハードウェアの制限なしにそれなりに快適に動かして
ひととおり Orange book のシェーダを試したいのなら、Mac OS X でしょうか。

shader builder で一文字打つたびに構文チェック & コンパイルもしてくれるし。

もうひとつの選択肢は、 GLSL を実装中の Mesa 待ちですね。早く来いこい Mesa。

Spherical Q2-tree for Sampling Dynamic Environment Sequences

Liang Wan, Tien-Tsin Wong and Chi-Sing Leung,
Spherical Q2-tree for Sampling Dynamic Environment
Sequences
in Proceedings of Eurographics
Symposium on Rendering 2005
http://www.cse.cuhk.edu.hk/~ttwong/papers/q2tree/q2tree.html

動的環境マップにも対応して時間軸でのポッピングを軽減し、かつサンプル点の生成が効率よく行える手法のようです。

abstract と video しかまだ見ていませんが、サンプルの生成は、まず球面をいくつかの四角形で構成された fish view
と呼ばれる 2D 平面に展開し、あとはおのおのの四角形を再帰的に分割していくことでインポータンスサンプリングを行うようです。

時間軸でも照明のポッピングが少なく、また静的シーンでも既存手法と品質はほぼ変わらず、
かつサンプル点の生成にはほどんど時間がかからないといういいところいっぱいの手法のことです。今年の Wavelet Importance
Samping と並び、HDRI 環境マップからの効率的なインポータンスサンプリングに関する興味深い論文のひとつとなりそうです。

Abstract 日本語訳

環境マップをサンプリングする既存の手法では、動的に環境マップが変化する場合というのはほとんど考慮されてきていませんでした。

既存手法で動的環境マップのシーケンスに対して生成されたサンプリングパターンは、時間的な照明の一貫性を保持しないこともあり、
波立つ(choppy)ようなアニメーションになってしまうこともあります。

本論文では、この一貫性の問題を解決する、球面 Q2-tree(spherial Q2-tree)という新しいアプローチを提案します。

提案する手法は局所的で適応的な性質を持ち、時間軸で生成されるサンプリングパターンは急に変化しないように抑制されます。

したがって、なめらかで一貫した照光処理を可能にします。

球面をシンプルな曲線方程式で分割することにより、四辺形を基本とした四分木(quadtree)を構築します。

Q2-tree はインポータンスのメトリックに応じて環境マップを適応的にサンプルし、
食い違い量が低い(low-discrepancy)サンプリングパターンを生成することが可能になります。
時間のかかる緩和処理(relaxation)などは必要ありません。

動的なシーケンスのサンプリングパターンは、範囲総和テーブル(summed area table)を用い、
また後続のフレームのコヒーレンスを利用することですばやく生成されれます。

われわれの実験結果では、静的な環境マップに対する本手法のサンプリングパターンのレンダリングの品質は、既存手法とほぼ同等でした。

しかし、本手法は動的環境マップのよりなめらかで一貫したアニメーションシーケンスを生成し、
またサンプルの数は時間軸で一定に保つことができます。

最近は spherical code などの、球面上のサンプリングパターンやら性質などに興味が湧いていたので、
今回のこの論文が目に止まりました。一見、球面は非常に単純そうに見えますが、2D 球面でさえ、
じつはとてつもなく奥深い性質や未解決の問題が存在するとのことです。球面調和関数もこの球面上の性質の問題として取りあつかうことができます。

next-gen internet-based massively parallel renderer

最近、おとくいさん?から以下のような案件をもらいました。

o 映画レベルの品質に耐える高品質レンダラ
o グリッドコンピューティングやセルコンピューティングのように、家庭の PC や AV
機器での分散レンダリングを見据えている
o つまり一極集中のレンダーファームから、インターネット規模のレンダラ網
o デザイナからみるとやっぱシェーディング言語はほしいので RenderMan ベース
o できたレンダラは GPL などでソース公開します
o GI ほしいよー
o できればフルタイムで参加してほしいよー

なんとも kilauea の果たせなかった夢を実現するような、大規模レンダラ作成プロジェクトです。

実際にはプロジェクトはすでに走り始めているのですが、やはり、レンダラ野郎が足りなくて、、、という
ことでした。RenderMan ベースということもあり、lucille をこのレンダラのベースにしてもよい、、、という話も。

(まあ現在の lucille はそんなに特徴のないレンダラだし、RenderMan API フルサポートでないから
あまり使えないですよ、とお返しするしかありませんでしたが…)

残念ながらタイミングが合わないのと、私のキャパシティもあり、快諾には至らなかったのですが、
個人的に技術的なやりとりを行っていこうかとおもいます。
lucille の実装を通じて得た技術的な知識はまだまだ役に立ちそうです。
また、それらプロジェクトの成果から、 lucille のほうにもフィードバックができればと思います。

最近は ERPT などでまったく lucille は更新していませんが、
ERPT が実装できて使い物になりそうだと感じたら、シェーダの皮をかぶせて
lucille を Maxwell Render with RenderMan SL な感じにしていきたいと予定しています。
 

それにしても、今回のできごとで、改めて 国語算数理科
GI
 化は切実だと思いました。
はやく GI 本(大域照明本)を完成させて GI 教の布教をしていく必要がありますね。

Catalyst 5.6

ATI の GPU ドライバである Catalyst の最新版 5.6 がリリースされています。

http://www.ati.com/

特にゲームなどにおいて大きくパフォーマンスがアップしているとのこと。

Doom3 以降、ATI は OpenGL ドライバを書き直しているとのことで、

http://www.chipzilla.com/?article=17528

今回もそれによる改善があったようです。

nVIDIA の OpenGL 2.0 ドライバといい、すでに GLSL 対応のドライバは
両社とも出していますが、さらなる OpenGL 対応度の向上がここ最近
図られていると思います。

Mac OS X では、ソフトウェアドライバになりますが、Tiger から GLSL に対応
しました。

なのでそろそろ GLSL のチュートリアルとかも解説していきたい
なぁと感じています。

これで Mesa が GLSL をサポートしてくれれば完璧なのですが、
今のところ cvs 版には 3dlabs のフロントエンドコンパイラまで
取り込まれているようですが、まだ mesa 側との結合までは
実装が完了していないようです。

ちなみに次期の Mesa のリリースでは、OpenGL 2.0 対応に
なるものと思われます。

mesa などのソフトウェア OpenGL ドライバは、動作が遅いですが、
ハードウェアの制限をそれほど受けないので、
フラグメント処理でバリバリループしまくりテクスチャ引きまくりの
ようなシェーダもちゃんと実行してくれるはずです。

そのため、GLSL の習得の観点からすれば、
機能の低い GPU ではうごかないということがなく、
どの環境でも確実に動作するのでリファレンスとして用いる
ことができるという利点があります。

特に、Mac OS X のソフトウェアドライバの GLSL コンパイラは、
orange book のサンプルや 3dlabs の shader validation test も
全部 pass するようなので、それなりに品質が高いようです。

ERPT 実装: コースティクス摂動

LDE の三頂点経路のみであるが、コースティクス摂動により
経路を変異させるところまでコーディングできました。

赤が元の経路、緑が光源からの方向をちょっとずらしてトレースしなおした、変異された経路です。
画面左の外側に視点位置があります。

手続きとしては、まず通常のパストレで変異させたい経路を作成しておく。
(今回はもっとも単純な LDE 経路のみを変異させることを考える)

– 光源の頂点から、 L -> D の方向を摂動させる。
– 摂動した方向へレイを飛ばして交点を求める。
— このとき、面に当たらず背景に飛んでいかないようにチェック
— さらに、異なる BRDF にヒットしていないかチェック(元がディフューズ面だったのに、摂動したらスペキュラー面にヒットしたなど)
– 交点(ディフューズ面を確認しておく)から、視点へレイを飛ばす
— このとき、遮蔽されないかチェック

で変異経路が出来上がる。

まとめると、ERPT では、変異されて新しく生成された経路は、
o 経路の長さは変わらない。
o 各頂点間の経路が遮蔽されていない。
o 各頂点の面の BRDF が変異前と同じである。
o 視点への経路が画像面内にあること。
を満たす必要がある。これが満たされないは変異に失敗とみなし、
もう一度変異をやり直せばよい。

次は、さらなる経路のタイプへの変異処理と、相対経路密度(relative path density)の計算です。

to be continued…

OpenGL 2.0 対応 NVIDIA linux driver

linux 版ですが、nvidia が OpenGL 2.0 に対応したドライバを公開しています。

http://www.nvidia.com/object/linux_display_ia32_1.0-7664.html

windows 版はβもまだ OpenGL 1.5 までの対応のようですので、
linux 版が一番最新となるでしょうか。

GLSL も含まれているでしょうから、GLSL のコンパイラの出来が気になります。

そういえば、nvidia が新しい GPU の発表のときに披露する最新デモは
(NV40 以降はちがうかもしれないけど)
常に OpenGL を使ってきているそうです(from N 社の人より)。
デモチームには SGI 出身者が多かったりするし、GL のほうが先に拡張させやすいかららしい。

もしかしてデモプログラムの一番最初の実装は linux だったりするのかな?

Graphics Hardware 2005 papers

Graphics Hardware 2005 の論文リストが公開されています。

http://www.cs.brown.edu/~tor/gh2005.html

注目はこれ。

Fully Procedural Graphics
Turner Whitted and
James T. Kajiya

う、おおおおおおおおおおおおおおおおおおおおおおおおおおおおおおお
おおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおお
おおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおお
おおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおお
おおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおお
おおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおお!

あ、ありえねぇー!!!
レイトレの元祖とパストレ(+レンダリング方程式)の元祖
がなぜゆえに!?、、、、

SIGGRAPH 2005 論文の Jim Blinn といい、
ことしは MSR は何かあったのでしょうか?
「オラオラ~、そろそろ論文書いてノルマ達成しろよオラ!」
と MSR の経営者(?) から催促でもされたのでしょうか?

ちなみに某 S 社(メリケン支部)からの、

Optimal Automatic Multi-pass Shader Partitioning by Dynamic
Programming
Alan Heirich

も興味深そうです。