Syoyo Fujita's Blog

raytracing monte carlo

Month: January, 2009

AO bench is evolving

AO bench is a small Ambient Occlusion renderer program which is suited for benchmarking processor/language’s floating point computing power.

AO bench was first appeared as a Proce55ing program to measure the performance of Proce55ing(more specifically, JVM).

Then it had been ported to C NativeClient JavaScript Flash10 iPhone

Recently, there’s two evolution.

AO bench on Android

aobench_android.png

takuma kindly ported AO bench to Android(DalvikVM), and found AO bench on DalvikVM is too slow because DalvikVM does not have JIT and the CPU running has no FP unit.

Even though AO bench is too slow on Android, takuma showed AO bench is runnable for mobile phone processor!

AO bench on GPU, and it’s 4K!

gpuao

Another interesting evolution of AO bench is GPUAO by kioku, A GLSL version of AO bench.
Since GPU has massive FPUs nowdays, GPUAO finishes 0 msec in his PC! (too fast to measure execution time).

More interestingly, kioku made his own 4K(4096 byte of the program) engine and AO bench was ported to that engine, not a naive GLSL program.
GPUAO occupies just 1.7K of 4K space!

[Ja]

AO bench が発展しています.

takuma さんによる、下は FPU なしの携帯プロセッサ(しかしでも動くだけでもすごい)から、
kioku さんによる、上は FPU モンスターの GPU にまでポーティングされています.

GPUAO, 速度が 0 msec ってすげー(早すぎて測定できない)

これで世の中に AO が知れ渡り、レンダラ書きが増えることを願います 🙂

Advertisements

Speed racer and Yatterman

speedracer.jpeg
Speed racer
http://www.apple.com/trailers/wb/speedracer/trailer1a/

yatterman.jpeg
Yatterman the movie
http://www.yatterman-movie.com/
(Click 4th red menu button to see the trailer)

Speed racer and Yatterman was both originally created by Tatsunoko production(in Japan),
and few decades later, one is recreated for the movie by Hollywood(as you know) and other is by Japanese production.

By watching both trailers, I convinced that Yatterman the movie is much more interesting and is much more faithfull to original animation version, although VFX for Yatterman is a bit cheap than Speed Racer.

I think it’d be better idea that Japanese studio makes the senario and do direction for the movie and Hollywood adds VFX to it 😉

[Ja]

The dark night が期間限定で再上映されているので、映画館で見てきました.
うーん、やっぱり DVD と比べると迫力が違いますねぇ.

で、そのときヤッターマンの実写映画版の予告編が流れてびっくり.

エッ!?ヤッターマン映画化すんの?

みたいな.
いやー、でも予告編を見る限りでは面白そうです. すくなくともスピードレーサーよりは.
以外と VFX も使われているし、それにヤッターマンの方が原作アニメにも近いし.

ドラゴンボールとかアストロボーイ(鉄腕アトム)とかも海外で実写化されることになっていますが、
予告編を見る限り、グローバルスタンダード? に迎合するためになんだか原作とまったく違ってますよね.
どれも多量の VFX を使っていますが(アストロボーイは full CG)、なんだか無駄に使っているという感じで、
スピードレーサーみたいにコケそうな予感がしています…

スピードレーサーとヤッターマン、
原作は同じ日本アニメでも、
映画化はハリウッド式がいいのか日本式がいいのか、
どちらが市場に受け入れられるのかのリトマス試験紙として、その動向に少し期待しています.

なんだかんだで日本はコンテンツは良いものを持っているはずはので、
ヤッターマンがヒットするようであれば、
これからは日本でシナリオ作って、ハリウッドが下請けで VFX 作る、
というような構図にしたほうが、ギョーカイ的には発展するんじゃないかなぁと思っています.

Haskell job hypothesis

(via Haskell-cafe ML)

ちょっくら今後いろいろ Haskeller に質問してみたいことがあるので、
ひとまず Haskell ML, Haskell-cafe ML に登録してみました.

…えッ!? Haskell-cafe ML, 一日 100 通くらい来るんですけど… 読み切れねーよ…

それはさておき、最近 Haskell-cafe に投稿された、Haskell 求職仮説(?)とその反応のひとつが面白かったので取り上げてみます.


http://www.haskell.org/pipermail/haskell-cafe/2009-January/054213.html

もしあなたが Haskell 開発者募集の求人を出したら、20 人の応募があるだろう.
彼らは皆、自身の手腕を改善たり自らの才能を伸ばさんとするため新しい言語を学んでいるような開発者たちだ.
なぜなら誰もまだ職を得るためだけに Haskell を学ぶようなことはしていないのだから.

もしあなたが Java 開発者募集の求人を出したら、200 人の応募があるだろう.
彼らの多くは、Java の求職が世の中に多くあるから Java を学んだような開発者だ.
そして Java 職で十分食っていけると分かっている間は、彼らは他になにも学ぼうとしない.

これに対する反応その 1

我が社は Haskell プログラマに求人を出し、そして彼らが面接にやってきたときに、
実際は我が社のコードベースは Perl であると伝える.
我が社には何人かの Haskeller もいるけどね.
もしあなたが気にしているのが開発者の質であって、彼らの生産性でないのであれば、
面接が終わったあと、彼らに Haskell を使わせる必要はないわけだ.

↑に対する反応

ひ、ひどい… 鬼だ…

要は Haskell の求人を出す = 質の高い開発者を得られるという, Haskell が “ふるい” として作用しているというわけですね.
なんかこれと似たような話がほかにもどこかであった気がしますが.

おまけ

言語ネタ繋がりということで.
Linus さんは C++ をボロクソに批判してますなぁ…

http://tabesugi.net/memo/2009/1a.html#152154

lucille は C で書かれているわけですが、その理由は Linus さんの主張とほぼ同じですね.

Haskell job hypothesis のように、C は C++ プログラマを追っ払うための”ふるい”と考えることもできるわけですね 🙂

C を選ぶ理由が C++ プログラマーを
追っぱらうため *だけ* だったとしても、それ自体、C を使う強力な理由になりうる。

もちろん、単なる “ふるい” ではなくて、きちんと

C でコーディングしてある = ポータブルで、効率がよくて、保守性があって、クリーンである

というような正しい認識が市場間に生まれてほしいところですが.
とはいえ全部 C で、というのもやはり面倒な時があるわけなので、アプリに応じて DSL などを絡めて、ですかね.

Scrap your boilerplate

Scrap your boilerplate
http://www.cs.vu.nl/boilerplate/

“Scrap your boilerplate” と呼ばれる、Haskell 向けのジェネリックプログラミングライブラリを知りました. Haskell におけるデザインパターンとも言えるでしょうか.

Haskell で RSL(RenderMan Shading Language) コンパイラを書いていると、AST(抽象構文木) などのツリー構造なデータ型の一部にだけ作用させたいコードが必要なときがよくあるのですが、この scrap your boilerplate がまさにそれを解決してくれることが分かりました.

たとえば、以下ような例を考えます.

replaceConst 関数は Expr の Const ノードを Var ノードに置き換えます.

Expr や Stmt は Main クラスに属しています.
Main クラスのインスタンスにたいして replaceConst 関数を作用させるためには, Expr, Stmt の両方にたいして replaceConst を実装する必要があります.
しかし、Stmt のほうは、実際には Expr を見つけて”トラバースするだけ”の画一的でつまらないコードです. つまり、Stmt に対する replaceConst は、本質的には必要ないものなのです.

Boilerplate とは、ボイラー版という意味もありますが、辞書を調べると「画一的なもの」「共通事項」という意味もあります.
“Scrap your boilerplate(SYB)”とは、Stmt に対する replaceConst の実装コードに見られるような、画一的で共通なコーディングをなくそう!というような意味のようです.

Data.Generics

SYB では Data.Generics というものが提供され、データ型の deriving に Typeable, Data を付加すれば、無駄なコーディングを省き必要な部分のコードを書くだけでよくなるという、なんとも素晴らしい機構です.
(もちろん、SYB の論文を見るとそれ以上にいろいろできる仕組みのようです)

SYB で書き換えると、こんな感じでとてもすっきりします.

まず、SYB(Data.Generics) を使うには、コンパイラに、拡張として DeriveDataTypeable を指定する必要があります.

そして、Data.Generics を使うことで、Stmt に対する replaceConst のコード、つまり “boilerplate” なコードを記述する必要が無くなっています.

boilerplate な処理であるトラバースのコードは

everywhere (mkT a) b

で代用されます. これは、a を、b のそれぞれのコンストラクタに対してトラバースして適用する、ということをしてくれるようです(a, b はどちらも Typeable, Data を derive しているとする).

まとめ

RSL コンパイラを書く上で、AST に対してなにか処理をさせたいときに、AST を構成するデータ型それぞれにたいしてトラバースするコード(boilerplate なコード)を書かなければならないのはなんとかならないものかと思っていたので、SYB はちょうどよい発見でした.
が、こんな良い手法(デザインパターン)があるのであれば、願わくば RSL コンパイラを書き始める前に知っておきたかったですね.

うーむ、Simon P. Jones(偉大なる Haskell 野郎) の文献をまずは一通り眺めたほうがいいのかも.

https://research.microsoft.com/en-us/um/people/simonpj/papers/papers.html

… と思ったけど、これはちょっと文献多すぎですぐには読みこなせないですね…
一日 3 本くらいをノルマとして読んだとしても、1, 2 ヶ月はかかりそうだ.

hjs: Javascript Parser in Haskell + Parsec

hjs: Javascript Parser
http://www.haskell.org/haskellwiki/Libraries_and_tools/HJS

JavaScript 実装、始め…るかも… と書き、あーそろそろぼちぼち手を付けてみんべかな、ここはやっぱりコンパイラは Haskell + Parsec で書くべかな, と思ってちらりとリサーチしたところ、
やはり世界は広い. すでに Haskell による JS のパーサがありました. しかも Parsec を利用!
Interpreter も用意されているみたいなので、あとはこれに LLVM codegen を作ってくっつければ完成かッ!?

ところで、この hjs が実装の参考にしている,

Monad Transformers and Modular Interpreters
http://web.cecs.pdx.edu/~mpj/pubs/modinterp.html

は知らなかったのですが、これ、Haskell でコンパイラのたぐいを書くときの設計流儀として非常に参考になりますね.
Write yourself a Scheme in 48 hours もこのような感じでコンパイラ実装が設計されているような気がしています.
Haskeller にとっては, このような設計流儀でコンパイラを書くのがデファクトスタンダードなのかな?

Monad Transformers and Modular Interpreters のような、
「Haskell でのコンパイラを作るときは、こう書けば簡潔で美しいしモジュラーになるしメンテしやすくなるよ」
みたいな流儀作法をもっと知りたいところです.

Etymology of “normal”

surface_normal.png
(image from Wikipedia)

「法線ベクトルとは、面に垂直な方向を指すベクトルである」

よくある 3D CG の教科書に見られる、法線(normal)に間する説明の記述ですね.

でも、「法線」の「法」ってナニ?
normal って「普通」という意味なんだから、「普通のベクトル」じゃないの?なぜ CG だとこれが「法線」というという意味になるの?

CG を習い初めたひとにとっては, こんな疑問をいだきつつも、「まあこのギョーカイではそんなことになっているんだな」と妙に理解したことにしてしまって今に至るひとが多いのではないでしょうか?

私自身もまだ右も左も分からぬレンダラ一年生だったとき, なぜ normal が面に垂直なベクトルを意味し、そしてそれが法線と訳されるのか疑問でした.

そこで、ちょうど GI 本を執筆するに当たっていろいろ資料や語彙の由来などについて調査していたので、normal = 法線の謎も追ってみましたところ、結構おもしろい語源の由来だったので取り上げてみることにします.

normal の語源

まずは辞典で normal の意味を調べてみます.

http://dictionary.reference.com/browse/normal

によれば、normal とは、「通常」、「標準」、などに加え、数学においては「直角、垂直」という意味もあります. つまり normal にはそもそも垂直という意味も存在していることが分かりました.

さて、normal の語源はラテン語の norm-, normalis であり、それは carpenter’s square に由来するものとかかれています.

carpenter’s square(大工さんの四角形)って何でしょう?
じつは carpenter’s square とは直角定規のことです.
↓これです.

carpenterssquare.jpg
(image from wikipedia)

というわけで、もともとは normal は直角(垂直)というような意味だったような気がしてきます.

さらに、norma-, normalis あたりの言葉の語源を調べるたところ、以下の語源サイトがヒット.

The etymological background of the term, “normal”

http://www.wordinfo.info/words/index/info/view_unit/4403/?letter=N&spage=4

そしてついに normal の語源の由来にたどり着きます.

The basic sense of the noun norm is “an authoritative standard or model”. This is derived from the Latin norma which means “rule or pattern” as well as “a carpenter’s square”, because a square provides a standard or rule which ensures that a carpenter can regularly reproduce corners and edges that are straight and that form right angles.

norm の基本的な意味は、「信ずるべき標準やモデル」である.
norm はラテン語の norma に由来し、これは「ルールや規則」そしてまた「carpenter’s square(直角定規)」を意味する.
なぜなら四角形は、直線でありまた垂直な角をもつ「かど」や辺を規則的に作り出すことを可能にする標準やルールを大工に与えるからである.
(ちなみに、square = 直角定規なのは、直角定規があれば四角形を描画できることから)

そして、

norm-, normo- +

Latin: rule, pattern; normalis, “right angled, made according to a carpenter’s square”; then, “conforming to common standards, usual” came into English usage in about 1828

normalis: 垂直で、直角三角形により作られたもの. 転じて標準を成す、通常.

まとめ

というわけで、normal(ラテン語の norma, normalis) というのは元々は大工の垂直定規を意味しており、それがルールや規則という意味となり、転じて「通常」(規則に従っている)という意味になったわけでした.

normal は、CG で使う「法線」という意味のほうが、より語源に近かったわけですね.

あ、しかし結局日本語における法線の「法」がなにを意味するのかはまだ調べきってません. ただ、英語の normal の語源における意味の一つである rule に由来して「法」という字が当たっているのかなと推測しています.

おまけ

垂直 -> 通常

に限らず、数学的な概念から転じて意味を作り出した例は他にもあります.

回転 -> やすらぎを与える
黄金長方形(黄金比) -> なんだか無限にパワーがわいてくるぞ!
素数 -> 数えると落ち着く
じゃんけん -> うおおおおおおおおお!ガラスの破片のシャワーを浴びてもガラスが当たらないほどの強運っ!

BOE cuts rates to record low of 1.5%

英中銀が50bp追加利下げ、過去最低水準の1.50%
http://jp.reuters.com/article/topNews/idJPJAPAN-35772320090108

うぉおおおおおお!
おおおおおおお!
キ、キングー!!!(<- BOE(英中銀)の総裁です)

1694年の英中銀設立以来の最低水準となった。
1694年の英中銀設立以来の最低水準となった。
1694年の英中銀設立以来の最低水準となった。

いやー、およそ 300 年の BOE の歴史の中で 1.5% という低金利は史上初、ということですか.
すごいなー、ってかまあまだ BOE は利率を下げると思いますけどね(記事に書いてあるように).
先進国各国が我先に、とゼロ金利政策を取ろうとしていますから.

一転していずれ円が(先進国中で)高金利になる可能性も無きにしもあらず、かもしれません.

レンダラファンド設立にむけてのお勉強: 対日投資、ファンド経由を非課税に

対日投資、ファンド経由を非課税に 政府、促進へ税制改正
http://www.nikkei.co.jp/news/main/20090107AT3S0601C06012009.html

おぉっ!! ってかいままで海外から日本に対する投資の場合は租税条約で日本での課税免除(海外の投資元の国で課税される)ではなかったのか.

むぅ、しかし日本国民が国内に投資するばあいも非課税にしてほしい…
(それから、一般社団法人で資産運用ビークルを作っても結局、株式会社と同じで法人税 40% がかかることがわかりました)

まあ、いずれにせよ、レンダラファンドの設立の方にもいい追い風が吹いてきていると感じています.

Approximating Dynamic Global Illumination in Image Space

ssdo.png
(image from “Approximating Dynamic Global Illumination in Image Space”)

Approximating Dynamic Global Illumination in Image Space
Tobias Ritschel, Thorsten Grosch, Hans-Peter Seidel
Proceedings ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games (I3D) 2009
http://www.uni-koblenz.de/~ritschel/

うぉっ! これはすげー!

– スクリーンスペースなのでジオメトリの複雑さと無縁
– 動的ジオメトリ可
– 前計算なし
– GPU に容易に実装可能

で近似的に GI (1 回の indirect diffuse) をリアルタイムでやってしまっています.

手法としては、基本的には既存研究である SSAO(Screen Space Ambient Occlusion) と似ています.
各シェーディング点において周りのピクセルに対してサンプリング点を生成してそのサンプリング点のオクルージョンをチェックして光の寄与を求めます.

論文では、スクリーンスペースでの Directional Occlusion と Indirect bounces の手法について解説し,
そしてそれらの手法に対して、よりアーティファクトを減らすためのテクニックを提案しています.

Directional Occlusion

ssdo_sample.png
(image from “Approximating Dynamic Global Illumination in Image Space”)

AO(ambient occlusion) では遮蔽率に応じてグレースケールでしか GI 効果を実現できないのですが、
DO(Directional Occlusion) では、サンプル点が見えれば(上図の左で点 C が該当)、
サンプル点が対応する方向からの環境マップの色を採用することでよりリアリスティックなシェーディングを可能にしています.
(手法としては遮蔽を求める計算自体は SSAO と基本的に同じなので、あとは環境マップをフェッチしてその色を寄与とするかどうかの違いだけ)

Indirect bounces

ssdo_indirect.png
(image from “Approximating Dynamic Global Illumination in Image Space”)

Indirect bounces では 1 回の間接反射を実現します. 2 パスの処理になっています.
1 パス目は DO による処理を行い、2 パス目では DO パスの結果を元にして、同じようにシェーディング点の周りのサンプル点からの寄与を求めます.
(2 番目の図の右側)

このとき, 周りのサンプル点は 1 回目の結果により直接光の結果をストアしているので、これを集めることで 1 回の間接反射が実現できるというわけです.

—-

さすがにオクルージョンが大きく変化するときはアーティファクトが見られますが、
(たとえば視点や物体が移動して見えない部分が見えるようになったり、見える部分が見えなくなったりするとき)
それ以外はもう十分すぎるほどのレンダリング品質だと思います.
(低周波数ライティング環境下における GI 効果という条件で、ではありますが)

効率的で、動的シーンでも OK な GI 手法が年とともに提案されて、どんどん GI が実用的になってきていると感じます.

How to optimize loop with floating point counter?

RSL(RenderMan Shading Language) では整数型が無いので(prman 拡張だと整数型はあるのかもしれません)、
たとえばループを記述するときのカウンタには float 型を使います.

こんな感じ.


float i;
for (i = 0; i < 1000; i += 1) {
    ...
}

float 型でも、2^24 までの整数は IEEE754 フォーマットで exact に表現できるので、
まあこの記述自体には問題ないのですが…

float 型のカウンタを使う場合、ループ最適化が効かない

で、問題は、このような float 変数をカウンタにしたループはなぜか LLVM や gcc では最適化されないのです.

たとえば、gcc(4.4) で試してみます
(gcc 4.3 からは mfpr と gmp の導入により、cos(2.4) というような式に対する定数展開の最適化がマシン非依存かつ正確に行われるようになったため, より float 演算に対する最適化が出来ていると推測する)

入力のプログラムは以下.
ループ内で何もしないので、ループが削除されることを期待します.


int
func() {
    float i;
    for (i = 0.0f; i < 1000.0f; i += 1.0f) {
    }
}


$ gcc-4.4 -O3 -S floop.c

残念ながら 1000 回ループするアセンブリにコンパイルされています.
(ループカウンタは整数型に変換されているのに. 不思議です)

LLVM で試してみます.


$ clang -emit-llvm-bc floop.c
$ opt -std-compile-opts floop.bc | llvm-dis

残念ながらこちらもループは DCE(Dead Code Elimination) されませんでした.
-licm (Loop-invariant Code Motion) とかループ展開とか、
それらしきループ最適化オプションを試しましたが結果は変わりませんでした.

float の演算の場合は、たとえば a + b + c という式を a + (b + c) と計算してしまうと丸めや精度の問題で計算結果が変わるので、
演算順序を変えたり演算をまとめるなどのアグレッシブな最適化は難しいことは分かるのですが、
(LLVM はそのためあまり IR レベルでは fp 最適化は行われないようです [1])
しかし、不変なループ処理くらいは最適化できてほしいところ.

さすがに? icc だと最適化してくれます.
(icc はバージョン 10.0 とちょっと古いですが)


$ icc -O3 -S floop.c

ret 命令だけになっています(期待する結果).

というわけで、どなたか、
「このオプションを指定すればループ最適化される!」とか
「最適化されないのはこれが原因だ」とか、
分かる方がいましたらご教示をお願いします.

参考

[1] Loop Invariant Code Motion and LLVM
http://stlab.adobe.com/wiki/index.php/Performance/Analysis/Example2