Syoyo Fujita's Blog

raytracing monte carlo

Month: May, 2006

Sequential Sampling for Dynamic Environment Map illumination

ESGR2006 の program を見てると、EGSR2006 も熱いです。
今年はホント、レンダリング関係は豊作ですね。

その EGSR2006 から、注目の論文をひとつ。

Abhijeet Ghosh, Arnaud Doucet, Wolfgang Heidrich
Sequential Sampling for Dynamic Environment Map illumination
http://www.cs.ubc.ca/~ghosh/publications.html

動的な環境マップからのライティングに逐次モンテカルロ法(SMC)を利用することで
アニメーションも考慮したシーンの効率的にサンプリングを行うとのこと。

著者にはなんと逐次モンテカルロ法で有名な Arnaud Doucet の名前がッ!!

やはり統数研ですれちがったときにサインをもらっておくべきだったか…
http://lucille.atso-net.jp/blog/?p=69

あと、逐次モンテカルロ法については、伊庭大先生の「計算統計II」が
非常に役に立ちます。

http://lucille.atso-net.jp/blog/?p=105

論文 Abstract 日本語訳

コンピュータグラフィックスにおいて、環境マップからの複雑な照明をサンプリングする方法については多くの興味がもたれてきました。
この分野の最近の研究により、光源と BRDF 積の直積からのサンプルを引き出す方法が、ほかのサンプリング戦略よりもよりよい結果を得られることが示されてきました。
しかし、この分野における既存の手法は、独立したフレームのみを考えており、アニメーションでのコヒーレンスの利点を利用してはいません。
本論文では、動的環境マップ照明のために逐次サンプリング法(sequential sampling)のアプローチを導入します。
我々のアルゴリズムは、時間的なコヒーレンスを利用しながら、照明と BRDF の直積から効率的にサンプリングを行います。
既存の研究よりも劇的なパフォーマンスが得られることを示します。

Efficient Wavelet Rotation for Environment Map Rendering

Ke-Sen Huang 大先生のところで、EGSR 2006 の論文リストが公開されはじめています。

http://myweb.hinet.net/home7/hks/Papers2006/egsr2006Papers.htm

いまのところは

Efficient Wavelet Rotation for Environment Map Rendering
http://www.cs.virginia.edu/~gfx/pubs/wrt_egsr/

くらいしかありませんが、これはついに PRT 問題のひとつである
wavelet 空間での「回転」を解決しています。
しかし、残念ながら解析解ではなく、数値計算による前計算テーブルを brute force に引くようで、
また結構なデータ量を使います(それって Efficient って言えるのかな?…)。

Wavelet を使う PRT(前計算放射輝度伝達)では、SH(球面調和関数) を使う PRT に比べて
高周波数を扱えるという利点がありましたが、逆に SH では容易な SH 空間
での回転が wavelet では(wavelet 空間で)できないという欠点がありました。

wavelet 空間での「回転」はまだまだ研究の余地がありますね。
「穏やかさ」を与える「回転」も研究しなくてはなりません。

Recusive Wang tiles sampler for importance sampling HDR image 2

インポータンスマップを作るときに、値を正規化していないというアホみたいなミスをしていましたので、修正しました。

http://lucille.atso-net.jp/svn/angelina/sampling/recursive_wang_tiles/
http://lucille.atso-net.jp/svn/angelina/sampling/recursive_wang_tiles/rec_wang_tile.zip
(windows バイナリ)

rwt_galileo.png

rwt_grace.png

インポータンスを正規化したら、ちゃんとサンプル点がインポータンスサンプルされるようになりました。
ほぼ満足な分布だと思います。

サンプル点の制御ですが、オンライン用途では厳しいかもしれませんが、オフライン用途なら、
生成時間が高速な利点を生かし、
トーンスケール(サンプル点を生成するパラメータ)を二分検索で変化させて試して、
生成されたサンプル数が求めたいサンプル数に近くなるまで探すというようにするとよいでしょう。

HDRI マップからの照明積分の誤差を最小にする EIHDRI

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

との比較も行ってみたいところです。

Recusive Wang tiles sampler for importance sampling HDR image

Recursive Wang Tiles を使って HDR 画像のインポータンスサンプリングを行ってみました。
基本のコードは Recursive Wang Tiles の author のページにあるので、
私が実装したのは HDR 画像を読み込むのくらいを追加しただけです。

http://lucille.atso-net.jp/svn/angelina/sampling/recursive_wang_tiles/
http://lucille.atso-net.jp/svn/angelina/sampling/recursive_wang_tiles/rec_wang_tile.zip
(Windows バイナリ)

rec_wang_tile_128.png
128 samples

rec_wang_tile_3422.png
3400 samples

rec_wang_tile_galileo.png
窓の部分の輝度が高いので、そこを重点的にサンプリングしてほしいのですが、
まんべんなくサンプリングしてしまっている。

比較のために、SBR 2004 で実装した Penrose tile sampler の結果です。

http://lucille.atso-net.jp/svn/angelina/sampling/penrose_tile/
http://lucille.atso-net.jp/svn/angelina/sampling/penrose_tile/penrose.zip
(windows バイナリ)

ちょっと見づらいですが、緑色の点がサンプル点です。

penrose_grace.png

penrose_galileo.png

Penrose tile sampler だと、輝度の高い部分を重点的にサンプリングしています。

Recursive Wang tiles の subdivision は元のコードをそのまま使いましたが、
HDR 画像のインポータンスサンプリングを効率的に行うには向いていないようです。
これは少ないサンプル数で積分誤差を最小にするという意味です。
(RWT の持つ progressive 性は、Animated HDR image のインポータンスサンプリング
を行うときには役に立つでしょう) 
よって、しっかりとインポータンスサンプリングを行うためには、
subdivision の refinement 基準などをうまくやらないとかもしれません。

subdivision 後の tile が占める領域のピクセルの輝度を積分するなりして
threshold をうまく決めるなどでしょうか。

また、 galileo 画像のように高い輝度部分が小さい画像面積
しか覆っていない場合、precomputed されたサンプル点がちょうど輝度の高いピクセル
の位置をサンプルするようでないと、これもうまくいかなくなる原因なのかなと思います。

Guided Visibility Sampling

Peter Wonka, Michael Wimmer, Kaichi Zhou, Stefan Maierhofer, Gerd Hesina, Alexander Reshetov,
Guided Visibility Sampling
SIGGRAPH 2006

ビジビリティ(visibility, 可視判定)の高速かつより効率的な計算手法。

ビジビリティ計算の問題というと、いわゆる、ある領域から(from region)見える物体はどれか?ということを研究する分野です。これが結構ちゃんとやろうとすると難しい問題で、既存研究ではフランス人とかがプリュッカー座標や visibility skeleton などすんげー数学理論や幾何理論を用いて問題を解決していました。
また、そのような複雑な理論になると、使用するメモリ量が膨大になってしまっていたりしました。

本論文では、シンプルかつメモリ消費なしで、(複雑な理論を使う)既存研究より 100 倍効率のよいビジビリティ計算を行える手法を提案しています。

abstract 日本語訳

本論文では、空間のある領域から見える三角形を計算するという問題を解決します。
提案するアグレッシブなビジビリティ解法(visibility solution)は、確率的レイシューティング(stochastic ray shooting)に基づいており、また任意の三角形モデルを入力として扱うことができます。

接続情報、ボリューム遮蔽物(volumetric occluders)、大サイズな遮蔽物などには依存しないため、それゆえどんな入力シーンも扱うことができます。

提案するアルゴリズムはメモリを必要としないため、広く利用されているいくつかの既存研究が持っている、膨大なメモリを消費してしまうという問題を緩和することができます。

本アルゴリズムの戦略は、レイ空間(ray space)でのレイ変異(ray mutation)を用いることで、新しい三角形をサンプルしやすくするようにレイをキャスト(cast, 放つ)することです。

本アルゴリズムは、既存研究と比較して 100 倍以上のサンプリング効率を達成することが可能です。

AMD CodeAnalyst

http://developer.amd.com/downloads.aspx

AMD のサイトには、パフォーマンスアナライザ CodeAnalyst というのがあります。
たぶんできることは VTune や Mac の Shark と同じなのですが、
ひとつそれらと違う特徴として、パイプラインシミュレーションの解析結果の視覚化ができます。

下記は、レイトレーシングのレイと三角形の交差判定部分のコードの
Athlon X2 上でのパイプライン結果です。

codeanalyst_thumb

fld でのロード待ちで、fcomip がストールしているのが見て取れます。
よってこの部分を最適化できれば高速化が期待できることが分かります。

現在の CPU はアウトオブオーダー実行、マイクロコード実行など複雑なことを行うようになっているので、
このパイプライン結果にその結果が含まれていたとしてもいなかったとしても、
そこから中身の実行の詳細を緻密に解析するのはちょっと骨の折れる作業になりますね。
(このインストラクションはあのインストラクションの結果待ちでストールしているとか)

Linux の方にはこのシミュレーション機能だけ抜き出したであろう、 Simulation Utilities があり、
個人的にはこのようなツールはコマンドラインで実行したほうが使いやすいので(それに Win版はすぐ落ちますし…)
こちらを使おうと試みたのですが、 Debian AMD64 な環境では残念ながらうまく動きませんでした…

PowerPC Mac には simg4 や simg5 というシミュレータがあり、
こちらもパイプラインシミュレーション結果を出力してくれます(テキスト出力ですが)。
Intel の場合は、少し探してみた感じではパイプラインシミュレータやソフトウェアシミュレータは提供していないようです。

Wald 先生はどうか分かりませんが、
MLRTLA の人は、きっとこのようなパイプライン解析まで行って、ガチガチに最適化しているんだろうなぁ。