Syoyo Fujita's Blog

raytracing monte carlo

Month: April, 2009

GADTs and Type Variables

最近は、RSL(RenderMan Shading Language)や、 lucille GI 言語のために、型システムを調べています.

RSL はほとんど C に近い静的言語なのですが、多相型の関数があるのがちょっと違う点なので、既存の C 言語向けの型システム(ってあるのかな?)や関数型に対する型システムの作法とはまた別のやり方で処理しなければなりません.

型システム(type system)を調べていると、ファントム型(Phantom types, 幽霊型?)やより一般的には GADTs(Generalized Algebraic Data Types, 一般化代数データ型?)というのがよく出てきます.

GADTs

GADTs は、型の定義をパラメータ化したもの、もしくは型を変数化したもの(型変数, type variable, と呼ばれる)の手法の近年の総称のようです. アイデア自体は昔から存在して、guarded recursive data types, first-class phantom types, equality-qualified types などとも呼ばれてきたらしい.

型変数

で、GADTs の元になる(であろう)型変数について、自分なりにおさらいしてみます.
よくある、関数型言語(でも宣言型言語でもいいですが)のコンパイラ作成においては、
コンパイル(パースする)対象の言語の「型」の情報なるものを定義するときには,


data CType
  = CInt
  | CFloat
  | CDouble
  | ...

とやったりします.

しかしここで問題なのは、関数型だと自分で型を定義できたりするということ. もちろん C でも typedef で定義できたりしますね.
たとえば、「half 型を定義したい」となると、上記のやり方では CType の定義に CHalf を付け加えなければならないが、
それは実行時には行うことができなくて、あらかじめコンパイラ側が知っていなくてはならない(コンパイラ側に定義を付け加える必要がある). つまりランタイム時の型定義にとても制約がでてきていろいろと不便になる.

そこで考えられた(?)のが、「型そのものも変数にしちゃえ」という概念.
すごく簡単に説明すると、型の定義をパラメータ化して,


data CType
  = CTy String

TyInt = CTy "int"
TyFloat = CTy "float"

という風にしちゃう. こうすると、型の定義というのはより自由になって、
たとえば変数を eval するのと同じようにして評価することで抽出できるようになる.


eval (CTy "int") = Int
eval (CTy "float") = Float
eval _ = error "Unknown type"

このように型を変数化することで、型の定義の自由度が上がってうれしいねー、実行時でも型を自由に生成できるよ!というのが GADTs につながる型変数の基本的な考え方のようです.

最も、言語屋さんやそのスジの教科書(Types & Programing Languages など)は、
もう少しさらにこの型変数の定義のしかたを抽象化して、ラムダ式で表現したりしています.

ただ、私のように実務的なコンパイラ作成をしたいひとには、メンテナンスや可読性を考えると、
型システムをラムダ式で表現するのは不必要に抽象化されすぎている感があるので、
RSL のように C 言語的な言語のコンパイラを作るときは、
現実的には上記のような string を取るパラメータ + アルファ程度の表現方法でいいんじゃないかなぁと思っています.

Kind

ちなみに、型変数にも、その型変数の「型」という概念があって(たとえば CTy “int” は整数型、とか)、それは変数の「型」と区別するために Kind(日本語だと「種」という訳が妥当なのかなぁ…)と呼ばれています.

型(Type) <- 変数(Variable)
Kind <- 型変数(Type Variable)

という関係ですね.

Advertisements

We are preparing the new era: multicore, raytracing and GI.

paradigm_shift.jpg

It’s now the time that we frontier new era: multicore, raytracing and GI.
I definitely could feel existing old era(singlecore, rasterizer) slumps, and we are entering new era.

Fortunately, there are many ideas, business chances, projects and collaborators around me.
More will be described in later. Just keep your eyes on my blog 😉

[Ja]

だんだんと、準備は整いつつあります.

2010 年を境に、我々は新しいコンピュータグラフィックスの世代に入っていくことになるでしょう.
今までは、シングルスレッドのプログラム、ラスタライザベースのグラフィックスの時代でした.
この時代は衰退期であり、そろそろ終わろうとしています.

新しい時代は、マルチコア、(リアルタイム)レイトレーシング、そして GI(大域照明)に他なりません.
lucille で GI レンダラを制覇、リアルタイムレイトレでインタラクティブグラフィックスを制覇し、
「国語算数理科 GI」となるよう大域照明を普及させ、
新しい世界の開拓者となるべく我々は今動き出そうとしています.

100 年に一度の不況と言われる昨今ですが、
我々、新しいことをやろうとする人々にとっては最大のチャンスでもあります.
このような最高のタイミングは、私が死ぬまでにはたぶんもう訪れないでしょう.

幸運にも、面白いプロジェクトがあり、世の中の流れは私の思う方向に向かっており、一緒にやってくれる仲間、パートナー、コラボレーターができ、役者や舞台はいままさに揃いつつあります.

もちろん、これだけの好条件がそろったとしても、必ずしも成功するとは限りません.
ま、うまく行かなかったら GI ニートということで 🙂

「syoyo 先生のこれからにご期待ください」

[CG Tech] Cloudy with a chance of meatballs

cloudy.png

trailer

おぉ!
モーションブラー!
さらにヘアー!

つ、ついにモーションブラー搭載か?!

が、しかし、trailer をよーく観てみましょう.
なにか気になる点はありませんか?
え、よくわからない? ではコマ送りで鑑賞してみましょう.



見えますねー、
見えますねー、
えぇ、見て取れます、

モーションブラーするオブジェクトに MC ノイズがッ!

MC ノイズも、シーンごとにばらつきがあります.
ノイズが細かかったり粗かったり、2D blur をかけたような感じのところも.
あと、42 秒あたりのモーションブラーはなんかおかしい気がします.

ま、でもアニメーションするとほとんど MC ノイズもモーションブラーのおかしさも、気にならないですね.
(MacBook のディスプレイでなくて、もっと質の良いディスプレイで観ると気づくのかもしれませんが)

私が思っているほど、モーションブラーはきちんと計算して低ノイズにしなければ!
というのはなくて、案外杞憂に思っているだけなのかもしれません.

ちなみに、RenderMan(PRMan) でもサンプル数が少なければモーションブラーにノイズが出ます.

Elevated, 4K demo

(via BreakPoint 2009 report by kioku)

elevated.jpg
(elevated at pouet.net)

http://www.nicovideo.jp/watch/sm6772038

(movie)

ぎゃぼー! なんぞこれスゲぇ…

奥さん、いいですか、これでなんとたったのファイルサイズは 4K!(じゃぱネット風に)
いやースゲーなー. しかもリアルタイムかよ(GPU 使っているけど).
あー作ったのは iq か、そりゃまあありえなくは無くねーか.

kioku さんのレポートも熱い! 単身ドイツに乗り込むとは!
我がドイツのデモシーン作成能力はァアアアア… 世界一ィイイイイ!!!
な気分になりました 🙂

SystemK もしっかりエントリー!

http://www.pouet.net/prod.php?which=53033

# が、残念ながら、家の環境では movie も exe もうまく再生できませんでしたのでどんな物か分からず…

Only 7 minites of VFX was used in Jurassic Park

from Wikipedia

ちなみにCG使用シーンの合計時間はわずか7分で、それ以外の大部分の恐竜のシーンはアニマトロニクスを使用して製作されている。

な、なんだってー!!衝撃の事実!

雨の中、ジープと恐竜が戯れる(?)シーンがあって、まだ私が CG も知らぬ○学生だったころ、
Jurassic Park が CG で恐竜を再現した映画だということで観て、
「あー、すげーなー、最近の CG はこんな雨の条件の実写シーンとも合成できるほど発展してんのかー」
と思って CG に興味を持ったクチだったのですが、
今思えばたしかに当時としてはよく出来すぎているので :-)、
あれは実は恐竜部分はアニマトロニクスだったんだろーなー.

あと、UNIX も、3D でぐりぐりできるなんかスゲーシステムなんだなぁと当時思ったり.
(まだ UNIX も知らなかったころ)

劇中にて「Unixなら分かるわ!」とレックスが操作するコンピュータは、SGIの実在するファイルナビゲーターソフト・fsnの画面である。なおCGを作成するのに利用されたコンピュータもSGI製だった。ちなみにパークのコントロールセンターにあるコンピュータはほとんどがMacintosh。クライトン自身がMacユーザーである

さてそんな SGI も、この前二度目の Chapter 11…

今思うと、いろいろと感慨深いですねぇ.

GI 検定

「国語算数理科 GI」の時代が来ると思っているので、
国民皆 GI を学ばねばならぬようになるでしょう.

で、そこでレンダラ財団で GI 検定をやるのもアリかもしれない.

んで、

– GI 検定のテキストや書籍は出版会社「GI 出版」に業務委託
– 検定の採点、受付作業は「日本 GI 事務センター」に業務委託
– GI 検定の広告は広告会社「メディア GI」に業務委託
– GI 検定のための問題ネタの調査には調査会社「GI 光学研究所」に業務委託

おお、ちょっと考えた(元ネタをパクった)だけでも GI でもこんなビジネス展開が可能に!

—–

… いや、まあアレのもじりなんですけど、
それにしてもオリジナルとなるビジネスモデルのスキームはすごいなぁ.ちょっと法に触れてしまったけど…
ビジネスモデルとしては学ぶところがあります.
「GI」というネタでもやりようによっては莫大なマーケットを開拓できる可能性を示してくれた気がします 🙂

[Paper, PGV09] Wait-Free Shared-Memory Irradiance Cache

Wait-Free Shared-Memory Irradiance Cache
Piotr Dubla , Kurt Debattista , Luís Paulo Santos and Alan Chalmers.
http://www.cgv.tugraz.at/CGV/People/people/behnke/PGV09/057-064.pdf

放射照度キャッシュ(irradiance cache)の計算をマルチスレッドで行うときに, キャッシュデータの一貫性を保つために同期処理に単純なロックベースの手法を使うのではなくて wait-free(lock-free) な手法を使うことで、スケーラブルに処理できるようになったよ、という論文.

放射照度キャッシュ自体はあまり好きではないのですが、lock free 系と CG 系の技術が融合した良い例だと思って取り上げてみることにしました.

放射照度キャッシュは間接照明の計算を近似でアクセラレートする手法です. 最近では vray や PRMan などにも放射照度キャッシュが搭載されていますね.

モノによっては 10x ~ 100x の速度アップになるという魅惑の手法なのですが, しかし、その一方で本質的にキャッシュシステムなので分散レンダリングをするときに難しいことになったり、もっと切実な欠点としてはしみのようなアーティファクトが出やすいという問題があります.

元々の実装も面倒くさいし、アーティファクトを消すために品質も上げようとするとこれまた実装が難しくなるので、個人的には好きな手法ではありません.

元々の放射照度キャッシュの技法を発案したひととこの前話す機会があったのですが、彼も「ああ GI 計算に使う目的で発案したもんじゃねーし(意訳)」なんてのたまってましたしね. 🙂

さておき, 本論文は, 放射照度キャッシュデータの共有化(複数スレッドからアクセスされても一貫性を保つ)の問題を lock free の手法を用いて解決した最初の技法であると述べています.

そして, たしかに wait-free 手法では lock ベースの手法に比べてスレッド数に対してスケーラブルにパフォーマンスが向上しているのですが… しかし lock ベースでは, 放射照度キャッシュデータへの read と write の度に毎度ロックをかけるという恐ろしい実装になっています(ええ、read のたびにです!). いや、さすがにそれはパフォーマンスが出ねーのはそうだろうよ、とツッコミたくなります.

あと、放射照度キャッシュの品質については言及されていないのが気になりますね. Wait-free になってスケーラブルになったとしても、各スレッドの計算順序はバラバラなので、キャッシュの作り方に影響が出て(insertion のタイミングなど)、レンダリングする度に結果が変わるということになるはずです(通常の放射照度キャッシュでもピクセルのスキャンの方法によって結果が変わるのと同じ). そのような条件の考察もあるとうれしかった.

ちなみに、論文の画像を拡大するとやっぱり放射照度キャッシュらしいアーティファクトが見て取れます.これでアーティファクトも出ないような技法なら、最強になると思うのですが.

[Lang] Haxe

http://haxe.org/

– 静的型付け(型推論あり)
– JavaScript ライクな文法
– クロージャとかもあり
– Ocaml で書かれている(コンパイラのソースは 1 万行ほど)

んー、js2llvm とか作るより、もうこれで良い気がしてきた.

Haxe はバックエンドはいろいろ切り替えることができて、JS に吐いたり Neko VM に吐いたりできる.
作者は Neko VM や MTASC も作っていたりする. すげー.

Renderist should use Kinesis keyborad?

kb_adv-blk720×471.jpg

Many renderist(renderer writer) around me uses Kinesis keyboard.
Fortunately, I got a chance to borrow Kinesis keyborad from Kinesis master, who has 4 Kinesis keyboards 🙂

Kinesis master said,

“Use Kinesis 12 hours per day!”

[Ja]

レンダラ野郎はキネシスキーボードをすべからく使うらしい.
少なくとも私の周りの真のレンダラ野郎はすべからくキネシスを使っている.

幸運なことに、キネシスマスター(キネシスキーボードを 4 個所有!)から、
ひとつキネシスキーボードを借りる機会がありました.

以下、キネシスマスターとの会話.

「いやー、Kinesis 頑張って使って慣れ始めているけど、一日 5 分が限界ですわ」
「少なッ!一日 12 時間は Kinesis と過ごしてください」
「ひえぇー…」

しかし真のレンダラ野郎を目指すには Kinesis をマスターするしかないと思うと、
避けられない道か… やはりレンダラ野郎になるのは険しい道のりだ…

lucille v.s. PRMan v.s. 3Delight: continued.

soichi_h pointed out that RIB setting


Attribute "cull" "hidden" 0
Attribute "cull" "backfacing" 0

in previous benchmark scene makes PRMan and 3Delight significantly slower,
because in this setting PRMan and 3Delight traces&shades geometry which is hidden or back-facing.

Thus I’ve changed the setting into


Attribute "cull" "hidden" 1
Attribute "cull" "backfacing" 1

to make the situation same to lucille.

Here’s the new benchmark result with new scene(1M polys).

lucille_1×1_52s_txt.png
(52 sec, lucille)

prman_armadillo_1×1.png
(1m14s, PRMan)

3delight_armadilo_cull.png
(3m42s, 3Delight)

armadillo_graph.png

Hmm, lucille is not so faster(just 1.4x) than PRMan… I have to optimize lucille!

[Ja]

soichi_h さんから、カリングの設定が無効になっているので、
PRMan と 3Delight では裏面や不可視面でもレイトレとシェーディングが行われ、レンダリング時間がとても遅くなっていると指摘をいただきました.
たしかに 3Delight のドキュメントを見るとそのような記述がありました.
(カリングが on/off できるのは point cloud 生成のためのようだ)

というわけで、カリングを on にして、lucille でやっている処理となるべく同じにして、
ベンチマークを取り直してみました(こんどは Armadillo x 4 の 100 万ポリゴンシーンで).
PRMan の結果は soichi_h さんからいただきました.

んー、差が縮まってしまいましたね…
PRMan とは 1.4 倍(クロック比を考えると 1.7x ほど)しか速くありません.
3Delight とはまだ 5 倍くらい速いですが.

レイトレ最適化の優先度を上げますかね 🙂