Syoyo Fujita's Blog

raytracing monte carlo

Month: May, 2008

Gelato deads!

http://blogs.nvidia.com/gelato/

Gelato deads and it goes to free.

[Ja]

あ、やっと発表されましたね.
ひとつまた、GPGPU は使えないということが証明されたと思います.

そんでもって、ヤツはあそこにいったのかー.
最近あそこはひとを集めまくっているなぁ.

Advertisements

SOHO: Orthogonal and Symmetric Haar Wavelets on the Sphere

http://www.dgp.toronto.edu/~lessig/soho/index.html

Quite impressing!

One of long-standing unresolved problem, (effcient analytic) rotation in wavelet space, seems now soved!

RSL to LLVM project proposal

I’ve made and uploaded on-going rsl2llvm project proposal.
Please check it out.

Here’s the discussion forum for rsl2llvm

http://lucille.lefora.com/2008/05/06/rsl-llvm-compiler-project-started/

Recently published rendering related books

As Shinji posted some recently publised rendering books,
I’d like to make up for the list of recently published rendering related books which could be benefitical for renderer writer.

Monte Carlo and Quasi-Monte Carlo Methods 2006

http://www.amazon.com/Monte-Carlo-Quasi-Monte-Methods-2006/dp/3540744959

mcqmc2006

A lot of rank-1 lattice method in this volume!.

You shouldn’t miss to read this volume if you are MC-based renderer writer since there’s quite interesting methods described in this volume, for example SFMT: SIMD-Friendly Mersenne Twister which could accelerate your MC renderer.

Geometric Algebra for Computer Graphics

http://www.amazon.com/Geometric-Algebra-Computer-Graphics-Vince/dp/1846289963

GAforGraphics

This is a easy introduction of geometric algebra.
I think this book is a good introduction for beginners who are intested in GA.

Geometric Algebra for Computer Science:
An Object-Oriented Approach to Geometry (The Morgan Kaufmann Series in Computer Graphics)

http://www.amazon.com/Geometric-Algebra-Computer-Science-Object-Oriented/dp/0123694655

GAforCS

Another GA book for graphics guys.
It describes ray tracing in GA space, which is the same one published in 2003.
I think GA could be used for efficient beam-based real time raytracing.

—-

And more,


Pactical introduction to how to write Global Illumination renderer with Python or Haskell:

From ray tracing to MLT and beyond
(by Syoyo, not yet published 🙂 )

I’ll definitely write this one, but who knows when will.

NVDA acquires ray scale, ray tracing start-up company

(via ompf.org)

http://www.pcper.com/comments.php?nid=5674

Hmm… How they will do then?

At least, current GPU architecture(especially G80) is completely not suited for practical realtime raytracing as evidenced by many researchers and ray scale’s demo performance.

Doing RT raytracing from GPGPU approach as said by Kirk is completely wrong.
They(NVDA and Ray scale) are trying to do raytracing with almost brute force manner, but this is BAD.

GPU maker needs a innovation, for example

– Invent highly efficient realtime raytracing algorithm(for coherent & incoherent rays)
– Implements some HW acceleated feature for raytracing
(for example binary search in HW, beam tracing in HW or AABB isect in HW).
– Describe raytracing as a domain specific language, then optimize raytracing in DSL level.
– etc.

NVDA 1Q/09 Form-10Q

NVDA の 1Q/09 の Form-10Q が filing されましたので、
投資家としての素養をつけるために、早速読んでみました.

そのまえに

NVIDIA、2009年第1四半期は42%増のGPU出荷で増収増益

今期の Form-10Q が filing される前には、このようなプレスリリースがありましたが、
このようなプレスリリースはまあ参考になりませんね.

「今期は過去最高の第1四半期だった」

うーん、そうですね、たしかに第一四半期だけみれば過去最高だなぁ

…投資家として、このようなリップサービス?にだまされないようにならないといけません。
きちんと SEC filings をチェックして、財務を確認するようにしましょう。

過去 2Q の結果との比較を作ってみました.


                 Q1/09       Q4/08       Q3/08
                 =========   =========   =========
Revenue          1,153,388   1,202,730   1,115,597
Cost of revenue    638,545     653,133     600,044
Net income         176,805     256,993     235,661

売上げは Q4/08 に比べて落ちていることがわかります.
また、Q1/09 の(課税後)利益は Q3/08 よりも低い.

まあ製品のサイクルなど、季節的な要因はありますし、
それにサブプライムショックもありますから、
まあそれを考慮すると今期はがんばったと言えるかもしれません.
株価もちょっと戻してますしね.

Ageia の買収価格は 30 億円

さて、今期の form 10Q には、Ageia と Mental images の
買収価格が記述されています.

– Ageia は、およそ $30 M(30 億円)
– Mental Images は、およそ $90 M(90 億円)

Y! とか facebook が兆円の単位で M&A 合戦が行われていたり、
ビスケットの会社が $25 Bn で買収とか、
そのような額になれちゃってしまっていると、
どうも安い感想を受けてしまいますね.

うーん、Ageia が $30M ねぇ、まあそれだけの価値が付いた
と言っていいのかな.

ただ、Ageia みたいに? 最終的に誰かに買収されることを期待して
会社を作ろうとする場合を考えると、買収価格が $30 M にしかならないのであれば、
グラフィックスで起業するのはおいしくなさそうだ.
(web 2.0 系のほうが”売れ”そう)

しかし、Ageia の価値が MI の 1/3 あるのはなんだか納得できないなぁ.

ちなみに、Havok は $110 M だった模様.

http://www.gamesindustry.biz/articles/havok-acquisition-cost-intel-110-million

こっちはちょっと高過ぎな気がする.
MI よりも高いのか…

まあ MI はいろいろとアレだったらしいですけど.

セグメント別売上げ

NVDA は、主たるビジネスのセグメントを 4 つに分けてレポートしています.

GPU : ノートおよびデスクトップ PC 向け GPU ビジネス
PSB : ハイエンド(Quadro など)むけ GPU ビジネス
MCP : チップセットむけ GPU ビジネス
CPB : ハンドヘルド、ゲーム機むけ GPU ビジネス

1Q/09
nvda_q109.png

4Q/08 はなんか探してもなかったので、3Q/08 のやつ.
nvda_q308.png

ハイエンド向けである PSB 以外は、売り上げは微増か減、
利益についても PSB は伸びましたが他はすべて減(CPB は赤字)
であることが分かります.

PSB は利益率も大きいですから(およそ50%!)、
今異様に CUDA とか Tesla を盛り上げようとしているのは、
これが原因なのかもしれません.

まとめ

というわけで form-10Q を読んでみました.
情報は、あるところにはあるわけです.

もっと財務分析能力を付けて読み進めれば、
NVDA があと何年生きられるか 🙂 分かったりするんでしょうね.
まだまだ企業財務を勉強していかないといけなぁと思いました.

Investing online gaming sector seems a good idea

(via いちカイにヤリ 投資世代)

第129回 中国のオンライン・ゲーム市場の近況

ここ とも関連しますが、ゲームセクタへの投資はやはりうまみがありそうですね。
(今は資源セクタへの投資がぶっちぎりではありますが)

少なからず我々の身近なものであるビデオゲームというセクタが、
ゲームをプレイ(消費)する立場から、見方を変えて投資対象として見てみると、
こうもうまみがあったのかと、ちょっと感動。

たしかにすこし考えてみると、

– 人口が多い
–> 収益源が幅広い

– インフラ,プラットフォームとしてのオンラインゲーム
–> トランザクションが増えるほどお金が湧いてくる

– 第三次産業(サービス)である
–> 物理的に価値のないものに価値がでる(強いて言うなら時間に価値がつく)
–> 刷るようにお金が湧いてくる

となかなか魅力的な投資対象だ.
うまくマネーのフローが回ればだけどね.

著者の言うように、一端市場を牛耳る企業がでてくれば、
大きな躍進が期待できそう.
(第二の Akamai のようなリターンが期待できるかもしれない)

—-

ついでに、eendex を久しぶりにのぞいてみました。

http://www.eendex.com/

940 ですか、結構戻してきていますね.

EGSR 2008 papers

(via private communication)

http://kesen.huang.googlepages.com/egsr2008Papers.htm

There are interesting papers this year!
Especially,

Shallow Bounding Volume Hierarchies for Fast SIMD Ray Tracing of Incoherent Rays
Holger Dammertz, Johannes Hanika, Alexander Keller
http://www.uni-ulm.de/in/mi/mitarbeiter/holger-dammertz.html

QBVH

They makes QBVH, quad-tree BVH which is applicable for SIMD processing.
In QBVH it tests 4 bounding box simultaneously by SIMD, while traversal is done in single mono ray.

They reports QBVH is about 2x faster than BVH for path tracing setting.

Using n-ary BVH for RT raytracing is already proposed in Japan by Kimura[1]. They tested up to 16-ary BVH.
Dammertz et al. have to cite Kimura’s paper 😉

entry point caching

The paper also proposes entry point caching to speed up shadow ray tracing, which is somethat similar approach introduced by Reshetov’s MLRTA[SIGGRAPH 2005].

Performance gain using entry point cache for tracing shadow ray is not so significant, up to about 60% faster when the scene has complex visibility.

[Ja]

なんか今年の EGSR はすごそうだ。
SIGGRAPH が年々論文の質が落ちているのにたいして、
EGSR はじょじょにクオリティがあがっています。
(タイトルを見ればクオリティが大体わかる)
学術界はそういう風に流れをつろうとしているのだろうか。

さて、早速タイトルに興味をひかれて、

Shallow Bounding Volume Hierarchies for Fast SIMD Ray Tracing of Incoherent Rays

を読んでみました。

レイトレのデータ構造を 4 分木 BVH(QBVH)にして,
bounding box の交差判定を SIMD で同時にやる手法。

ただしレイのトラバースはパケットではなくて、
シングルで行っている。
パケットでやると分岐のコストが大きくなるから、というのと、
シングルのほうが incoherent rays にそのまま使えるからという
判断のようだ。

パストレのレンダリングにおいて、BVH を使うよりも QBVH を
使ったときのほうが、最大でレイトレ時間は 1/2 に
高速化できたことを報告している。
(かつ、メモリ使用量も少なくなる)

QBVH の利点は、パケットレイトレをしているわけでないので、
既存レンダラに組込みやすいということ
(パケットにも対応できるでしょうけどね)

ちなみに、空間データ構造を4分木で持つというのは
すでに日本では先行例があります [1]。
彼らはこの文献も cite すべきだよなぁ。

うーん、これが「あのお方」が言っていた、
「incoherent ray の効率的な処理方法を近々発表するよ」
のやつなのかなぁ、、、たぶん違う気がする。
今回のは非リアルタイム系で、
「あのお方」はリアルタイムレイトレ系の方を意味していたはず。
でもラストオーサーは「あの」会社だしなぁ…
やっぱこれなのかなぁ…

References

[1] 並列演算に適したバウンディングボリューム階層によるレイトレーシングの高速化
木村秀敬.
http://www.jaist.ac.jp/library/thesis/ks-master-2007/paper/h-kimura/paper.pdf

ABI を決めるには?…

rsl2llvm もそろそろ C/LLVM/SL との境界の ABI をデザインするフェーズに入ってきたのだけれど、いまいち ABI ってどうデザインすればよいのかわからない。

ここでの ABI って言っているのは、最下層のアセンブラレベルの関数呼出規約、
たとえばレジスタ $1 には戻り先のアドレスをいれて、
スタックポインタはどーのこーので、
というところまではいかなくて、
C、LLVM 中間言語, SL(シェーディング言語)間の
関数呼出のインターフェイスのデザインを
どうするか、という話。

ベクタ型は 4xfloat にするとか、
スカラは値渡しだけどベクタ型はポインタで渡すとか、
スタックベースでやるとか、
いやいや引数はすべて opaque pointer ひとつで隠してしまうとか。

たとえば SWIG で C と python の組合せでの
グルーコードを見てもらえればわかるけど、
インターフェイスをあわせるためにすげーめんどい処理しているのね。
そーゆーのは避けたいなぁと。

ポータブルでシンプルで、かつ LLVM(or compiler)にとって specialize や LTO
しやすい形にできるというのが理想。

で、そーゆーのを自分でうんうん考えたり、
海外のコンパイラ野郎らと discussion してというのでも
いいんだけど、なんか時間が無駄になりそうなんだよね。

(たぶんいるであろう)日本で ABI に詳しいひとが
身近にいるといろいろ手軽に相談できていいんだけど。

もしくはコンパイラ分野における、
「こいつに聞けばあいつがよく知っているからあいつに聞け」
とすぐに紹介してくれる、コミュニティを掌握しているひととか。
# ちなみにグラフィックス、特に大域照明だったら、私に聞いてくれれば
# 「〜したいんだけど」とお問い合わせがあればなんでもお答えできると思います。

コンパイラコミュニティは私にとってはまだまだアウェーなわけで、
正直(日本において)だれがプレイヤーなのかかよくわからない。

「オレ知っている」
「あいつに聞くといいよ」
「あなたのそのコンパイラの悩み、聞いて解決してあげます」
とかあったらぜひ御連絡ください。

Falling in love with Python

DSL(Domain Specific Language) というやり方を取り入れていこうと考えたあたりから、

Load to MUDA. SIMD code generation, domain specific language, automatic optimization, functional programming, etc.

いろいろなコード自動生成や、テスト環境、かんたんなコンパイラ/トランスレータなどを作っていく
上で、Python をかなり使うようになってきました。

使いこなすにつれ、Python はいい言語だなぁと感じるようになりました。
C に比べてとても生産性が高いです。コンパイル時間もかからないし。
パフォーマンスさえ問題でなければ、もうぜんぶ Python でいいんじゃねと最近は思います。
(関数型言語はまた別腹ね)

私が Python を始めた理由は、
数年前に Blender のエクスポータを Python で書いたことがきっかけでした。
それからすると、最近は Maya や Houdini などの 3D modeling パッケージのほとんどが
スクリプティング環境として Python を搭載するようになってきています。
グラフィックス野郎はこれからは Python が必須になるかもしれませんね。

しかし、日本ではどうもあまり流行っている気がしません。
やはりこれが原因なのでしょうか?

Python がイマイチ人気にならないたった一つの理由

^^)

それはともかく、Python は、基本的な使い方は書籍などにありますが、
実務的に使うときに、たとえば使える外部パッケージとかの、
開発環境としての Python という感じの包括的な案内というのはあまりみかけません。

そこで、私が主に使っている、もしくはとても注目している Python ライブラリについて紹介したいと思います。

– setuptools
http://peak.telecommunity.com/DevCenter/setuptools

デファクト?のパッケージングシステム.
Python にはデフォルトで distutils というのがあるが、
こちらはそれをもうちょっと拡張して、
ネットからパッケージをダウンロードできたり、
.egg 形式のパッケージを扱えたりできる.


$ easy_install 

とすることでパッケージのインストールができる.
BSD の ports, ruby の gems みたいなものか.
パッケージの形式は .egg 形式となっている.

名前に統一感( setuptools, ez_setup.py, easy_install, .egg) がなくて非常に分かりづらい.
しかも .egg 形式は、 Python の言う「ディレクトリがパッケージ名になる」、
というルールに沿っていなくてインポートのやり方がどうなっているのか不明。とても混乱する。
そのせいでいまだに構成がよくわからないパッケージシステム.
とはいえ、これがないとまずは始まらない。

– Psyco
http://psyco.sourceforge.net/

Python コードを JIT コンパイルして高速実行してくれるモジュール.

スクリプトの先頭に


import psyco
psyco.full()

と書くだけでスクリプトが JIT 実行される。
速度が気になる場合にお試しあれ。ただし x86 限定。

– pypy
http://codespeak.net/pypy/dist/pypy/doc/home.html

Psyco の後継プロジェクト。
Python コードからいろいろな言語に変換したり、JIT 実行してくれる。
LLVM コードに変換も可能。

ひとまず素の Python でラピッドプロトタイピングして、
完成したら pypy で変換して高速実行するみたいな用途に向いている。

最近は adobe flex バックエンドであるpypy-flex というのもあり、
web アプリも python で書けるようになるかも。

pypy は、内部では型推論、specialize などかなり高度なことをやっているようだ。
動的言語もこれからは静的言語と同じくらい効率良く実行できるかもしれないという
期待を感じさせてくれる、今一番注目のプロジェクト。

– PLY
http://www.dabeaz.com/ply/

Python 版 Yacc/Lex.
自分言語を書くときなどに.
rsl2llvm でも使っている.

2.3 は lex の初期化に optimize=1 を指定するとバギーなレキサが出来るので注意
(rsl2llvm を書いているときにこれにハマった)

– wxPython
http://wxpython.org/

クロスプラットフォーム GUI ライブラリである wxWidgets の Python バインディング.

GUI 画面デザインには wxformbuilder が使える.
wxPython で使う場合は、XRC リソース形式で export するようにすればよい.

– PyOpenGL
http://pyopengl.sourceforge.net/

OpenGL の Python バインディング.

– ctypes(標準ライブラリ)
http://python.net/crew/theller/ctypes/

Python から、直接シェアードライブラリの関数を呼び出すことができるライブラリ.
既存 C/C++ 資産を Python で使うときに便利.

– nose
http://www.somethingaboutorange.com/mrl/projects/nose/

Unit test の記述を簡単にしてくれるテスティングフレームワーク.
ファイル名, ディレクトリ名やメソッド名に test が付いているものを自動で実行してくれる.

– Twisted
http://twistedmatrix.com/trac/

TCP/IP 非同期通信など、イベントベースのネットワーク処理ライブラリ.
Twisted 利用アプリの一覧がすごい.

– Buildbot
http://buildbot.net/trac

自動ビルドツール。
デイリービルドや継続的インテグレーションなどに.

– Pyrex
http://www.cosc.canterbury.ac.nz/greg.ewing/python/Pyrex/

C での Python 拡張モジュールを Python っぽく書けるツール。
構文は型付き Python という感じ。

http://www.scipy.org/PerformancePython

を見ると、ほぼ C と同じパフォーマンスを実現できるようだ.

– Sphinx
http://sphinx.pocoo.org/

reST(reStructuredText)形式から、html/latex 形式のドキュメントを生成するツール。
最近では Python 自身のドキュメントページにも使われている.

– llvm-py
http://mdevan.nfshost.com/llvm-py.html

LLVM API の Python バインディング.
自分言語作成や、コンパイラ研究に。

– tinypy
http://www.tinypy.org/

Python の小さな実装。lua みたいな組み込み用途にも使えるのかな?
ただし batteries not included なので、
既存ライブラリがすべて使えるわけではないことに注意。

—-

ひとまずはこんな感じです.