Syoyo Fujita's Blog

raytracing monte carlo

Month: February, 2009

レンダリスト面接時の技術的な質問事項(レンダラ財団版)

(via philo 式)

philo 式で取り上げられていた
プログラマー面接時の技術的な質問事項(アプレッソ版)
をレンダラ野郎向けにもじってみました.

■ 開発実績編
まず、Maya を知っている•RenderMan を知っているなどよりも、どんなものを作れるか、どんなことができるか、という質問。

– hair のレイトレを高速化したいんだけど、良いアイデア無い?
– レイトレでモーションブラー早くしたいんだけどさ、もっといいモーションブラー高速化のためのデータ構造ない?

ここで強烈な回答が来る人は、まあ即採用ですよね.

■ 光輸送方程式導出編
次に、言語に依存しない光輸送方程式導出の基本の部分で、分かっていないとクリティカルなバグが混入する可能性があるような内容についての確認。

– LS+DS+E 経路の解法における潜在的な困難点は?
(実際、これが原因でパフォーマンスが数倍遅くなっていた事例を見たことがある)
– 光輸送方程式を Kajiya のレンダリング方程式として定式化する場合、これは第二種フレッドホルム型積分と見なせることを示し, そこからエネルギー保存則により operator norm が 1 以下であると仮定できるためノイマン展開することができることを示てください.
– 光積分の weak singularity の対処.


■ レイトレ指向編

次に、固有の言語に依存しないレイトレ指向の理解の確認。
ごく基本的な内容だが、現実問題として、「レンダリストを5年やってます」というような人でもこの手の質問にきちんと答えられないことがたまにある。

– 放射輝度(radiance)と放射照度(irradiance)の違いの説明
– ラスタライズとレイトレをどんな基準で使い分けているか
– Ingo Wald と Phillip Slusallek をどんな基準で使い分けているか

■ レンダラパターン編
レンダラパターンは基本的にはコミュニケーションツール(一言で説明できてすぐ伝わる)としての位置づけが重要だと思っているので、すべて知っていないとNG、ということはまったくないが、普段普通に使っている、という人の場合には、お互いのレベルを見るのにもってこいのディスカッション材料なので、よく面接の時に話題に上る。

– Whitted パターン
– Shinya パターン
– Path Tracing パターン(Kajiya パターン)で next event estimation が重要な理由を説明してください
– Metropolis パターンで acceptance rate or rejection rate が多くなりすぎてきたときにどのような工夫をしますか
– QMC sampling パターンを使うべき場合と、MC sampling で対処する場合とを、どのように使い分けますか
– Photon mapping パターンが時として「大域照明解法的に気持ち悪く」なるのは何故ですか

■ 数学編
次に、レンダラ数学経験者の場合に質問する、レンダラ数学関係の質問。
基本的なものからトリッキーなものまで、ここでは下記のような内容を思いつくままにランダムに質問してみることにしている。

– sup と maxの違い
– Ω の定義域は?

– 次の式を解け:

– BRDF は で示すことがありますが、この r の元々の意味は?
– Koksma-Hlawka を発音してください.

■ その他
その他、できるだけ相手の得意分野に合わせて都度レンダリング面接。

—-

さて、ここで取り上げたネタ、どれくらいの方が判るでしょうか 🙂

CG やレンダリストには興味があるけど、な、何のことだかさっぱり… というアナタ、
じつはここで取り上げた内容の多くは GI 本で取り上げる予定でいます.
(GI レンダリング理論、数学、レンダラプログラミングが一式詰まって,
しかしなるべく中学数学レベルで理解できるようにして誰でも理解できるように仕立てています)

というわけで、GI 本(まだ未完成)を読めば, ここで取り上げたネタも「なんだそういう事か」となって、
立派なレンダリストになれること間違いなし!?

おまけ

小野さんのブログにはこんなのもありますね.

読み書きそろばんはすべての基礎
開発環境を最新のものにするとか、新しい言語の学習を始めるとか、
これらのことは、それ自体何も悪いことではない。

ただ、やはり、少なくとも一つの言語で、
読み書きそろばんの基礎を作ることが最優先だと思う。

へへへ、まあ考えることは皆同じというか、じつはこれも GI 本で実現しようとしていることなんですよね.
GI レンダラの読み書きプログラミング(in Proce55ing).

PBRT, RRT(Realistic Ray Tracing) に代わる、GI 世代のための、
レンダラ野郎必携のデファクトスタンダードなリファレンス GI レンダラ実装.
まあ要するに SICP の GI レンダラ版みたいなものね.

海外も一見進んでいるように見えて、じつは「これ!」といった GI レンダラの教本みたいなものってないのですよね.
すくなくとも私の知る限り.
(PBRT が一応あるけど、これはあまり教本的なものではないし、ボリュームがでかすぎるし、呪うべき C++ を実装言語に選んでいる)
なので GI 本が英訳されるようならあちらの大学でも普及が見込まれます 🙂

Advertisements

Appcelerator’s Titanium = Cross platform beautiful GUI framework?

長年のクロスプラットフォーム GUI ツール探しの旅が、ようやく一つの終わりになりそうだ.

fltk, wx, gtk, etc いろいろ試してきたが、
クロスプラットフォームで open source で, beautiful でカスタマイズ可能なルックも実現できる GUI ツールキットには
なかなか出会えませんでした(かといって自作するのはまたそれですごい労力)

Qt4.5 が LGPL になるということで、おお、これは Qt かな、と思っていましたが、
ここに来て超期待の新人が現れました.

その名も Titanium

http://titaniumapp.com/

まあまずはデモビデオを見てほしい.

Titanium Developer: Getting Started from Appcelerator Video Channel on Vimeo.

あとは demo. まだアルファレベルなので demo も少ないですが、それでも結構イケてる感じ.

http://titaniumapp.com/demos

要は Adobe AIR のオープンソースクローンです. Titanium 自体は RubyOnRails で作ってあるみたい.
GUI 系は webkit や javascript を使って美しくカスタマイズ可能にデザインできて、
ネイティブデスクトップの機能や、ネイティブプロセスの起動などもできる.

推薦には、「wxWidgets や .NET, Qt とか使って来たが、Titanium こそオレの求めていたものだ!早速乗り換えることを検討するぜ!」とかあったりして期待度は高い.

で、こいつがすごいのは, C/C++ や Ruby, Python など各種言語でモジュールを書いて拡張できるようになっていること.

Kroll

C/C++, Ruby, Python, JS… などでモジュールを記述できる、という特徴はこの Titanium でどう実現しているか,
ちょっとソースを覗いて調べてみました.

各種言語のサポートの実現には、 Kroll と呼ばれるモジュール間のメッセージ通信を hub するようなデーモンサーバ(?)を使ってやっているらしい.
Kroll の README にはこんな風に書いてある.

Kroll is a compact microkernel written in C++ for running pluggable
modules. Kroll supports a cross-language, cross-platform “binding”
and invocation framework which supports mixing and matching
code within the Kroll kernel.

マイクロカーネルとあるが、いくつかのコード例を見るとどうも Kroll サーバ(?) に各モジュールはメッセージを投げて値をセットしたり、
クエリメッセージを投げて Kroll から値を取得したり, という感じでクロスランゲージなバインディングを実現しているように見える.

確かにメッセージ通信ベースで各モジュールとやりとりすれば、言語のバインディングの自由度は高くなりますね.
(TCP/IP でつなぐようなものだし)

Titanium は聖杯か?

そんなわけで、これで CG アプリ(lucille GUI フロントエンドとかシェーダエディタとか)書いたら、
モデリングやレンダリングはネイティブモジュールで行い、
GUI は html + javascript で、
と結構イマドキで Web2.0 な見た目を備えた魅力的な GUI アプリが作れそうだ.

そして web と統合していることを生かして、
レンダリングした画像はボタン一発で Flickr に上げて、Twitter で報告して、
マニュアルは web で見て、アップデートは自動でネットワークダウンロード、とかね.

ただもちろん、Titanium が完全な解というわけではありません.

メッセージ通信(のようなもの?)でネイティブモジュールとやり取りをするため、
たとえば CG 系の用途ですと画像を頻繁に更新することが要求されるわけですが、
ネイティブモジュールで生成した画像を html の世界で表示するには、
単純に考えると画像をメッセージとして送らなければならず、
パフォーマンス上の懸念があります. なにかしらうまい仕組みがないかどうか探す必要があります.
もちろん、ネイティブモジュール側のウィンドウに表示するのであれば、このような懸念はありませんが.

また、ネイティブモジュールのデバッグも困難になります.
gdb などで追いかけたいときは、モジュール呼び出し側にはメッセージ通信だけをダミーで応答するような
アプリを建てたりしないといけなくなるかもしれません
(これは TCP/IP 通信をするアプリを作るときにも言える問題ですね).

lucille + JIT shader + ???

JIT shader もコアな部分はだいたい出来てきたので、シェーダ編集やレンダリングのインタラクティビティをアピールするためにもモデラとの統合、それも密接な統合が必要だなぁと思っています.

要求としては,

– 視点移動などシーンの変更ごとにレンダラ(シェーダ)をトリガする仕組みがモデラにある
– モデラのレンダリング画面にアクセスできる
– シェーダエディタ(テキストエディタ)などと連携が取れる
– シェーダパラメータの GUI コントロールが容易に作れる
– まあ要は SDK でいろいろいじりやすい.
– モデリング機能はそこそこでいい(ただ、多量のジオメトリを容易に編集できること)

あたりでしょうか.なんともプログラマ寄りな視点です 🙂
そんなわけでモデラもプログラマ寄りなものが適していそう.

いくつか検討してみました.

LightWave CORE

なんともプログラマが好きそうな文言が並んでいますね.
今なら $395 !、まー、どーせ製品版なんて使わねーし、これは即決じゃね?
と思いましたが lightwave 持っていないとダメなのですね.

新規ユーザは lightwave も付いて(core だけでいいんだけど…) $895 とのこと.
うーむ、試すだけの目的なのにいらない lightwave も付いて $895 は微妙だ.

modo

UI はいい感じですね. ただプラグインをどう書けるのは不明.

houdini

Apprentice 版でいろいろできるのはいいのだけれど、Apprentice 版だと外部プログラムとは python を介さないといろいろできないので、不便だし簡単にはインタラクティブにはできない.

blender

我らが blender! 機能は悪くないんだけどねぇ、UI が絶望的すぎて長時間の利用に耐えられない…

まとめ

うーん、結局やりたいことを考えるとモデラー自作が確実なのですが、そこまで労力をかけるのもできない.
というわけで、今の所の候補は「LightWave CORE の出来次第」ですかねぇ.

第二回 LLVM 勉強会

3/22(日) に第二回 LLVM 勉強会開催の運びとなります.

告知&参加管理サイト 
http://atnd.org/events/381

google グループ
http://groups.google.com/group/llvm_study/web/第二回+llvm+勉強会

今回から、だんだんといかに動的言語やオレ言語を JIT して高速化したり、実行時最適化を自動化して自動最適化を実現するには、という方向に向かっていきます.
LLVM はそのための最適化を実現するための一つのツールという位置づけです.

第二回はなんと! miura さんによる、LLVM を使って ruby の実行を早くしてしまおうという yarv2llvm の世界初の講演をしていただくことになりました. ruby 野郎は要注目です.

私の方からはこの前の RenderMan シェーダの JIT 実行の仕組みについて解説します(これも世界初).

まだ時間と講演(勉強)内容には空きがありますので、オレ様の LLVM を使った成果を見せつけたい!というひとがあればぜひお知らせください.
(x86toLLVM についても何かデモできるレベルまで作れるといいのだけれど、間に合うかどうか…)

Two peaks

さて問題、このチャートは何でしょう?

gold_1000.jpg
 
 

正解: gold の価格. 2008 年 3 月に大台(?)の 1,000 ドルを付けたのち、最近また 1,000 ドルを付けてきています.

http://www.the-privateer.com/chart/gold-pf.html

 
 
 
さて、ではこのチャートは? これも最近また久しぶりにピークを付けています. gold になんだか似ていますね.
nk_200902.jpg
 
 
 
 
 
正解: 日経平均を反転したチャートです 🙂 1990 年のバブルのピークあたりからのチャートになっています.
(つまりバブル後空売りしていればとても儲かったというわけ)

http://finance.yahoo.com/echarts?s=%5EN225#chart1:symbol=^n225;range=5y

日経平均はまた最近バブル後最安値を更新しようとしています.
… まあ、まだまだ下落するでしょうね.
しかしだからと言って空売り(or put オプション買い)しまっくっていれば儲かるかというと、
なかなかそうならないのがマーケットなのですよねぇ.

JIT & specialization of RenderMan shading language.

JIT-ed RenderMan Shader Execution Engine demo from Syoyo Fujita on Vimeo.

ふぅ、苦節○ヶ月でしょうか、やっとこさ RenderMan シェーダの JIT コンパイルおよび specialization システムが出来てきました.
まあ要は JIT コンパイルで高速シェーダ実行し、Lpics, Lightspeed のような仕組みを取り入てさらに高速化すると言う感じ.

アンビエントオクルージョンシェーダでは、通常だと 4 秒のところを、specialization を行うとコンパイラがすっげー頑張って最適化して(?) 25 msec ほどで行っちゃいます. 実に 160 倍の高速化を実現しています. もちろん、同じ入力、同じ出力結果という条件で.

あ、もちろん GPU なんて使っていません. すべて CPU 上での処理です.
アルゴリズムが何よりにも勝るということのよいサンプルと言えるでしょう.

アーキテクチャ的にも、GI や DSO にも対応できるので、Lightspeed 以上のフレキシビリティがあります.
現状アーキテクチャだけ見れば, 最強のシェーダシステムと言えます.

詳細についてはのちほど解説したいと思います.

# しかしビデオのサムネイル画像が全くシェーダと関係ないものになっているのが残念です…

[M&A] GH + IRT -> High-Performance Graphics

学術会にも M&A の波が!?

http://www.highperformancegraphics.org/

GH(グラフィックスハードウェア学会) と IRT(リアルタイムレイトレ学会)がくっついて、High-Performance Graphics という学会になるそうです.

ompf.org には HPG 2009 chair のするざれっくからのコメントが.

http://ompf.org/forum/viewtopic.php?f=3&t=1221

もっと HW 屋と SW 屋(レイトレなどの CG アプリ)がくっついてシナジー発揮していこうよ, という感じらしい.

GH は, 昔はグーローシェーディングなどの固定シェーダをどう HW で効率的に実装するかというのが多かったけど、今はどうプログラマビリティを上げるか、いかに多様な CG アルゴリズム(レイトレや GI)を効率的に HW で処理するかに向かっている.

IRT は, 今後レイトレが一般的で実用的になるには HW ともっとフィットする必要がある.

なんで M&A して事業(?)シナジー向上をしてみました、みたいな.

たしかに、たとえば、レイトレについては、いまのアルゴリズムをベースにしていくなら ray-aabb の交差判定とトラバーサル処理(二分木探索など)はほぼ固定的に決まった計算処理とみなすことができますし、またこの部分が一番演算ネックになりやすい. なのでここを HW 化してアクセラレートされるだけでも結構効率的になって、レイトレベースゲームというのもぐんと実用的になります.

もう少し大きな視点としては、
「今は SW レンダリングがブーム(?)になってるみたいだけどさー、もう少し先を見てみようぜ.
そうするとまたこんどは HW レンダリングな世代になるだろきっと
(ラスタライズベース GPU ではなくてレイトレベース GPU とか)」、
という感じらしい.

まあそれに GPU メーカーとしてもこーゆーのをやっていかないと、今後レイトレ GPU などの新たな需要を作れないと CPU でいいじゃん、ということになるという危惧もあるのだろう.

おまけ

それにしてもこのところ、リアルタイム SW レイトレがこれからのトレンドだ!みたいなこと言うひとも増えてしましたね.

まあ現在の半導体技術やコンテンツ制作環境の問題などを見れば,
今後はラスタライザではなくてレイトレにならざるを得ないことは分かるわけですが、
以外に流れが早く進んできているという感じ.

AO bench evolution.

AO bench、サイトオープンからおよそ 1 週間が経過しましたが、おかげさまでいろいろな方に移植していただいています. 自分でもびっくりするくらい.
(オレ様の成果を見逃しているぞ、というのがあればお知らせください)

とりえあずこの手のネタ(?)が成功する条件をまとめてみました.

– コードがシンプルである.
– 結果が絵で出る(ので成果が確認しやすいし、モチベーションも湧く)
– 外部ライブラリが必要ない(ピクセルデータは ASCII ppm にすればいい)
– まとめサイトをつくる

さて、もちろんまだこれで終わりというわけではありません.
ここから先、AO bench の移植を試みようとしている方、実装が他者と被らないためにも移植言語はマイナー(?)な言語を選ぶのがオススメです 🙂
とりえあえずまだ未開拓で、これなら他と被らない!という言語を独断と偏見で選んでみました.

Factor
– Erlang ( 1 pixel 1 process! )
– sh(bash, csh, etc)
whitespace

挑戦者をお待ちしております.

移植もそうですが、そろそろ CPU 別でのパフォーマンス比較も行っていきたいところですね.

おまけ

さて、移植してみた方はお分かりかと思いますが、
意図的に、 AO bench では AO(ambient occlusion)の詳細なアルゴリズムについて解説していません.
ソースを見ても特に「なぜこうなっているのか」についてもコメントは入れてありません.

実は、AO bench は今後の壮大な(?) GI 本計画のための布石なのです.
アルゴリズムの詳細については、GI 本を買えば分かる! ということで 🙂

LLVM JIT trouble with static function.

さらに追記: JIT シェーダエンジンがうまく動かない件、どうもこちら側のプログラムにメモリリークがあったから、が原因で LLVM 側に問題があるということではありませんでした. また、正しく動くプログラムで確認したところ、シンボル解決もモジュール内のシンボルがルックアップされます(下で書いてあるのは間違い).

追記: JIT シェーダエンジンがうまく動かない件、どうも下記が原因のようではないようです. こちらのプログラムでどこかでメモリリークが生じているからかもしれません. 原因はいまのところ不明.

LLVM JIT シェーダエンジンを書いていて, 半日くらいはまった LLVM のバグ? らしきものについて記録として残しておきます.

おかしくなる例はこんな感じ.

ここで、main.c は LLVM の JIT エンジンのコードが含まれたバイナリを構成するソースです.
JIT エンジンは muda.c の内容を(clang などで .c -> .bc としたあとに .bc を読み込み)JIT コンパイルし, muda.c:dora() を呼び出すものとします.

muda.c:dora() は muda.c 内で static 関数である func() を呼びます.
同様の名前の関数は main.c(JIT エンジンがリンクされているバイナリ側)にもあるとします.

このとき、muda.c モジュールの JIT コンパイル時では、dora() 内で呼んでいる func() は muda.c:func() ではなくて、main.c:func() であると間違って(?)シンボル解決してしまいます. そして dora() は main.c:func() を呼び出すわけではなく, seg fault してプログラムが終了してしまいます.

LLVM JIT エンジンは実は結構よくできていて、JIT コンパイルするモジュール内で解決できないシンボルがあると、デフォルト動作では JIT エンジンが含まれているバイナリ側のシンボルからマッチするものが無いか探すようになっているようです.
もしかしたらこの動作が悪く影響しているのかもしれません.

が、static で宣言されている関数であれば、なるべくモジュール内で定義されている関数(シンボル)を優先的に採用するのが期待されるような動作の気がします.

まあこれが LLVM のバグなのかどうか、単に C か elf バイナリの仕様では曖昧なので LLVM のバグではないのか、ちょっと llvm-dev にでも聞いてみますかね.

いずれにせよ、LLVM を使って JIT コンパイルするときは、なるべくファイルスコープを外れても被らないような関数名をつけるのが良いと言うことで.

AO bench web site opens!

aobench_site.jpeg

I’ve made AO bench web site for centerizing information on AO bench and its variants.
See it, and follow it!

http://lucille.atso-net.jp/aobench/

[Ja]

AO bench、いろいろなひとが移植してくれいているので、まとめサイトとして AO bench のサイトを作りました.

twitter というウェブサービスがあり、 これでフォローという操作をすると発言やコメントが出来るみたいです.
aobench というアカウントになります.

たとえば、Core i7 での速度とかのレポートとかをこれでいろいろな方から気軽にしてもらえるのでは、と踏んでいます.
いろいろ情報をいただければ都度サイトをアップデートします.

あと、各種言語でのパフォーマンスをグラフで表示することも準備中です.

おまけ

今回の AO bench のサイトは、webby という静的 HTML 生成ツールを使って構築しています.

http://webby.rubyforge.org/

CMS ほどのたいそうなツールを使うほどでもなく、wiki でオンラインで編集する必要がそう頻繁にあるわけでもなく、ちょっとしたテンプレートをベースにコンテンツを流してサイトを作りたいというときに便利です.

なんと LaTeX 数式も OK らしい. まあ今となっては formula があるのでこっちで十分だと思います.

あと、 webby autobuild とすると、独自 web サーバを立ち上げ、コンテンツを編集してセーブするたびにリビルドしてくれますので、出力 HTML の確認がとても楽になります
(ブラウザも自動リロードとかできればさらに楽になるのですが、さすがにそれは手動でやるしかないようです).