Syoyo Fujita's Blog

raytracing monte carlo

Month: November, 2005

ゼロから学ぶベクトル解析

レンダリング処理において、
レイ微分やパス微分、テクスチャマッピングなどをやろうとすると、

ベクトル解析の知識が必要になります。

レンダラを習得といえば pbr book があるように、
ベクトル解析にも同じように必携の書があります。

西野友年
ゼロから学ぶベクトル解析


http://www.amazon.co.jp/exec/obidos/ASIN/4061546627

いやー、この西野本は私にベクトル解析のすべてを教えてくれました。

西野先生にはひれ伏します。

まさが△がラプラス星人(Laplacian)だったとは、
ウルトラマンも思わなかったでしょうに。

Portal Rendering(Potentially Visible Sets)

最近はシーン全体をひとつの kd-tree や voxel
で表現するのは
効率がよくないような気がしてきているため、
ゲームの世界でよく使われている
ポータルレンダリング(PVS, Potentially Visible
Set などとも呼ばれている)
について調べています。

ポータルレンダリングでは、シーンをセル(部屋などの空間)と
ポータル(窓や扉などの、部屋と部屋をつなぐ 2D 空間)にわけます。

セル内のジオメトリがポータル以外では閉じている
(ポータルの部分を通してのみほかが見える)
のであれば、ポータルから見えるセルのみをたどればカリングが行えます。

ポータルは基本的には Doom のような屋内系に向いていますが、

がんばれば屋外系にも適用できるはず。

ここで、ポータルのデータ構造があったとして、
今いる視点から、
いかにしてポータルから見える(描画しなければならない)セル
を判定するかが、ポータルレンダリング(PVS)で重要になります。

前計算で正確に判定するものやプリュッカー座標を使うものなど
いくつもの手法が論文で提案されています。

しかし、まずはとっかかりとして、PVS
判定でたぶんもっとも簡単で
それなりに効率のよいがこれ。

David P. Luebke and Chris
Georges
Portals and Mirrors:
Simple, Fast Evaluation of
Potentially Visible
Sets
SIGGRAPH
1995.

http://www.cs.virginia.edu/~luebke/publications/portals.html

やっていることは、
各セルのポータルのバウンディングボックスをスクリーン空間に投影し、

自分の今いるセルのバウンディングボックスとほかのセルのバウンディングボックス
が交差するか判定し、交差するやつだけ処理するというだけです。

とてもお手軽。実際論文も SIGGRAPH 論文なのに
contribution の
部分は 1/4 ページくらいだけ。

とりあえずポータルを実装してみたいというのにいいですね。

さらに、
判定をバウンディングボックスではなくバウンディング球で
やってしまってもっと簡単にしちゃったのがこれ。

T. Roden and I.
Parberry,
Portholes
and Planes: Faster Dynamic
Evaluation of Potentially
Visible
Sets
“,
ACM Computers In
Entertainment,
(Proceedings of the
Second Annual International
Workshop
in Computer Game Design and
Technology)
Volume 3, Issue 2, April/June
2005.

http://www.cacs.louisiana.edu/~troden/

ポータルってむずかしそうと思っていましたが、
ここまで簡素になってしまっていいんでしょうか。

ただポータルの欠点は、どれがセルでどれがポータルかを
レベルエディタなどで手作業で指定する必要があるということですね。

(ここらへん自動で最適に見つけ出すアルゴリズムってあるのかな?)

この点において、
入力ジオメトリから自動で空間データ構造を作らなければならない
レンダラに、ポータルを導入するというのはまだまだ難しい気がします。

Sun Studio Compilers for the Linux OS Alpha

いろいろ調べていたら、実は Sun 謹製 C/C++ コンパイラ
for linux がありました。


http://developers.sun.com/prodtech/cc/linux_index.html

無償ですが、ただしアルファ版とのこと。

わざわざ Sun 製コンパイラを使いたがいが為に Solaris
をインストールする
必要はなかったのですね…

Sun のコンパイラ cc はデフォルトでは 32bit
のコードを吐くようで、
64bit kernel な amd64
ではリンクの部分でコンパイルがコケました。
amd64 の場合は明示的に 64bit
コードを吐くようにアーキティクチャの
オプションを指定する必要があります。

$ cc -xarch=amd64 muda.c

SSE 対応度は?…

gcc や icc 、 vc で SSE
拡張命令を使う場合は、xmmintrin.h
をインクルードすれば C 関数のインターフェイスが使えましたが、

Sun の cc ではこれが sunmedia_intrin.h
になっています。

しかし、なぜか整数演算系しか提供されていません。fp
演算を使う場合は
(インライン)アセンブラを使ってねということのようです。
Sun の Niagara が 8 core なのに fp
演算器がないことを見ると、
あまり Sun は fp
を使うメディア系処理には力を入れていないのでしょうか?

なので


http://developers.sun.com/solaris/articles/x86_assembly_lang.html

らへんを見てアセンブラコードを書いていく必要がありそうです。

sun のアセンブラである fbe では、gcc
のインラインアセンブラのように
自動でレジスタと変数の割り当てをしてくれるようではないようです。

なので明示的にスタック上の変数へのオフセットを記述する必要があります。

うーん、めんどいなぁ…

AMD64 linux の場合、 32bit code は
native には実行できないので、
上記例での add3 を書いてみましたが、エラーが出てしまいました。

amd64 の場合はインラインアセンブラでは 64bit
ニーモニックで記述する必要があるようです。

Solaris 10 & Sun’s C/C++ compiler

Sun Studio 11 が無償公開されています。


http://www.itmedia.co.jp/enterprise/articles/0511/17/news025.html

注目すべきは、なんとこの統合開発環境、 Solaris
版には
sun 謹製の
C/C++コンパイラやパフォーマンスツールまで無償で付いてくるということ。

しかも C/C++ コンパイラは OpenMP
対応(勝手にスレッド化してくれる機能)です。
これって無償で使えるコンパイラとしては、Intel C/C++
Compiler(非商用版)と
並ぶほどすごい気が…

linux 版は残念ながらコンパイラは gcc を使うことを前提で、

ライブラリ群やパフォーマンスツールだけのようです。

というわけで、Sun のコンパイラを試すべく、
前々から興味のあったこともあり、
Solaris 10(x86 版) を Athlon64 Dual
Core マシンにインストールしてみました。
(OS もコンパイラも無償(しかも商用利用まで OK っぽい)で、
Sun は大丈夫なのだろうか…)

キューブベアボーンの ST20G5 では、SATA
ドライブは認識されないようでしたので、
通常の ATA ドライブにインストールしました。

またネットワークカード(Broadcom
BCM57xx)もデフォルトでは認識されませんでしたので、
下記ベンダーのサイトからダウンロードしてインストールしました。


http://ja.broadcom.com/drivers/downloaddrivers.php

カーネルは自動的に 64bit 版になっていたり、Dual Core
もきちんと検出されているようで、
とくに今のところ問題はないようです。

pkg-get

Solaris では、 gcc
などのある程度のソフトは(オプションで)インストールされますが、

それ以外の Solaris
でのオープンソースソフトウェアのパッケージ管理は、
pkg-get を使うと簡単にできます。
autoconf や subversion
とかはこれを利用してインストールしました。


http://www.bolthole.com/solaris/pkg-get.html

apt や rpm のように、
自動的に依存関係を調べてネットからダウンロードしたりしてくれます。

感想

Solaris ですが、やはり設定ファイルとか ps の引数とか、
 
linux とはちょっと使い勝手が違いますね。
とはいえ、安定している感じがあるので、
debian みたいに長く使うにはよさそうな気がしました。

Solaris + gcc では、リンクするライブラリを修正する程度で
lucille の
コンパイルは成功しました。これから sun の compiler
でもコンパイルできるように
修正していこうと思います。

sun のコンパイラ性能以外にも、もともと Solaris OS
は商用ですから、
デュアルコア構成やスレッド利用時、高負荷時などの
カーネルパフォーマンスが linux よりもよいかも、、、
と期待できます。
これも実際にレンダリングをしてみて比較していきたいと思います。

レイ微分(ray differentials for mipmaping)

さて、
実際にテクスチャマッピングをしてテクスチャキャッシュの実装を
進めようかなーと思っていたのですが、
レイトレでミップマップをするには
微分値(フットプリント推定)が必要ということにいまさらながら気づきました。

というわけで、レイ微分を実装しました。

Homan Igehy, “Tracing Ray
Differentials”, SIGGRAPH
1999.

http://graphics.stanford.edu/papers/trd/

レイ微分について数式が多いので、RenderNote
のほうに詳しく解説しています。


http://lucille.atso-net.jp/wiki/index.php?%A5%EC%A5%A4%C8%F9%CA%AC

とりあえずは、
一次レイ(transfer)におけるレイ微分を実装しました。

angelina に実装したコードは以下にあります。


http://lucille.atso-net.jp/svn/angelina/texturing/mapping/

 

レイ微分により、テクスチャ空間での (s, t)
のフットプリントを元に LOD を計算し、
LOD 値を視覚化したものです。赤が lod = 0, 緑が 1,
青が 2 です。

 
上図の lod
によりミップマップしてテクスチャを貼り付けた結果
(トライリニア補間により 2
レベルのミップマップを線形補間しています)。
左: ミップマッピング有効。 右: ミップマップなし。
1 ピクセルあたり 2×2 サブサンプル。

 
テクスチャの異なるバージョン。左: ミップマッピング有効。 右:
ミップマップなし。

感想

正直なところ、
ミップマップ有効とミップマップ無効では、
今回の平面に貼り付けの場合ではほとんど結果に差がありませんでした。

とはいえ、1×1
サブサンプリングだとミップマップ有効のほうがちょっとよい結果のようでした。

逆を言うと 2×2
サブサンプリングでミップマップなしでも十分な品質が出ました。

もちろん、品質に違いがなくとも、
メモリアクセスの観点からはミップマップしたほうが
アドバンテージがあるはずです。
(メモリアクセス(キャッシュミス)コスト > LOD
算出コストであることが前提ですが…)

かなり傾けてレンダリングしてみたときは、思ったより小さい LOD
しか算出されなかったので、
これが正しいのか実装が間違っているのか検証する必要があります。

また、
現在はミップマップを作るときに単純なボックスフィルタでダウンサンプルしているので、

あまりミップマップの品質が高くありません。
遠くにポリゴンを置いてレンダリング(lod
値を上げる)すると
張られるテクスチャがぼやけた感じになってしまい、
ミップマップしないでテクスチャマッピングしたほうが品質が高くなる場合もありました。

ミップマッピングも、現在の実装は等方性ですが、
やはり異方性にする必要もあります。

まあとりあえずレイ微分の基礎部分はうまく動いているようなので、

これからいろいろなジオメトリにぺたぺたテクスチャを張って試していき、

機能を追加、また間違いがあれば修正していこうと思います。

OpenGL on Mac OS X 10.4.3

Mac OS X が 10.4.3 にアップデートされ、ついに
GLSL がハードウェア対応
されています(GL_ARB_shading_language_100)。
ただし OpenGL 自体のバージョンは 1.5 です。
ついでに EXT_framebuffer_object
もいくつかのビデオカードでサポートされています。

OpenGL の対応状況は、


http://homepage.mac.com/arekkusu/bugs/GLInfo.html

で確認することができます。

これでほぼ windows や linux の OpenGL
ドライバの機能と同等になりました。

Monte Carlo and Quasi-Monte Carlo Methods proceedings

Monte Carlo
and Quasi-Monte Carlo Methods
2002

http://www.amazon.co.jp/exec/obidos/ASIN/3540204660

Monte Carlo And Quasi-monte Carlo
Methods 2004

http://www.amazon.co.jp/exec/obidos/ASIN/3540255419

2 年に一回開催されているらしい、
モンテカルロ法界隈(ファイナンスなどが主なる応用分野?)では
有名な同名のカンファレンスのプロシーディングです。

2002 には、Statification by Lank 1
Lattices が、
2004 には Illumination in the
Presense of Week Singularities と、

モンテカルロ法のコンピュータグラフィックスへの応用で有名な
Alexander Keller 博士と Thomas Kollig
先生による論文も収録されています。

Statification by Lank 1 Lattices
が読みたかったので、2002 出ないかなーと
その昔待ちわびていましたが、いつの間にやら 2004
まで出版されています。
時の流れるのは早いですね。
しかし 18,000 円ですか、、、この前 Principles of
Digital Image Synthesis を
購入したばかりですので、しばらくは手が出そうにないです。
(現在円安ですので、
しばらくしたら円高になってもう少し安くなるかもしれないし)

そういえば、擬似乱数で有名な Pierre L’ecuyer 先生も
WELL 以降、
最近いろいろ論文を出しているみたいですね。


http://www.iro.umontreal.ca/~lecuyer/papers.html

今年は Randomized Quasi-Monte Carlo 法の
Markov Chain への応用が興味深そうです。
論文の中身をスッ飛ばして結果だけみただけですが、
どうも既存の RQMC 法よりも 5 – 10
倍くらい収束がいいらしい。
ただこれは Asian option
のプライシング問題のシミュレーションの場合のようです。
ファイナンス系の問題にはそれほど大きな discontinuity
は現われないと思うので、
discontinuity
バリバリのコンピュータグラフィックスの問題へ応用したときの結果も
同じようなパフォーマンスになるといいんですけどね。

時間を見つけてゆっくり読めればと思います。

(その前にブラックショールズ微分方程式などのオプションプライシング理論をきちんと学んだほうがいいかも)

Principles of Digital Image Synthesis

 

Andrew S. Glassne
Principles of Digital Image
Synthesis
http://www.amazon.co.jp/exec/obidos/ASIN/1558602763 (amazon.co.jp)

http://www.glassner.com/andrew/writing/books/podis.htm
 (著者のページ)

存在や内容は以前から知っていたのですが、2 万円近くすることで、

ちょっと購入をためらっていました。

しかし、良書は一生モノであるし、
ちょうど適応的サンプリングについていろいろ調べたいときに、
本書が適応的サンプリングについてかなり詳しく解説されているのもあって、

やはり手元においておきたいということで、購入することにしました。

3D CG についての理論がかなり網羅的に記述されています。

ただ、入門書ではなく、
どちらかというと研究者が自身の研究に対する
既存研究のリストアップなどに使うという色合いが濃いかもしれません。

(もちろん、各内容は基礎から解説しています)

とはいえ、特に、
アンチエイリアシング(サンプリング)と光輸送の章については、

ここまで詳しく書かれている書籍はほかにはないでしょう。

本書は、上下巻セットで販売されているようです。
合計のページは 1200 ページ!にも及びます。
しかし、上下巻構成になっているので、同じく一巻で 1000
ページ近くある PBRT book よりは、
持ち運びやページを開くのが楽になっています。

一生モノと考えれば、2 万円でも、50 年使うとして計算すると、

一年 400 円、一日なんと 1 円で購入できます。

(コーヒー代より安い)
そう考えると、先人たちの英知をその値段で得られるのですから、
なんともお得ですね。
逆に私もこれら書籍や論文から得た知識を、
いろいろ還元していかないとなぁと思います。