Syoyo Fujita's Blog

raytracing monte carlo

Month: May, 2007

antlr 3.0

antlr が 3.0 になっていつの間にかすごそーな感じになっている。

http://antlr.org/

ANTLRWorks というパーサビルダができているし、
C コード!を出力できるようになっているようです。
AST も勝手に作ってくれるみたい。

ここ最近、bison でちくちくと RenderMan SL の AST を書いているのですが、

http://lucille.atso-net.jp/svn/proj/lucille/branches/RB-0.2/src/sl/

なんか antlr 使えばそんなことする必要がなくなりそう。

シェーダコンパイラは、bison/flex でなくて antlr に変えることを考えることにします。

ちなみに、antlr(parser) + ruby(backend, optimizer) という組み合わせで RenderMan SL を
RPU(ray processing unit) アセンブラに変換するコンパイラを作ったひとがいます。

http://taw.chaosforge.org/rpu/

コンパイラ屋にとっては当たり前のことかもしれませんが、ソースも公開されていて、
私のようなコンパイラ初学者には勉強になります。

ここの antlr grammer を利用して、あとは AST から LLVM コードを吐く walker を書けば
RSL -> LLVM トランスレータが完成できそう。

antlr + LLVM の組み合わせでコンパイラ + 実行環境作成が、(性能、手抜きの両方の面で)最強か?…

Advertisements

Ray Tracing Dynamic Scenes using Selective Restructuring

Ray Tracing Dynamic Scenes using Selective Restructuring
Sung-Eui Yoon, Sean Curtis, Dinesh Manocha,
EGSR 2007.
http://gamma.cs.unc.edu/SR/

[En]

Quite interesting dynamic realtime raytracing method is presented by GAMMA group.

They proposed selective reconstruction of pair of BVH nodes for dynamic raytracing.
Spatial structure they are using is BVH, and updating BVH requires only up to ~1% of total rendering time for each frame.

Which pair of BVH nodes is reconstructed is determined by their new cost model(CM-IQ and RM-IQ),
whose calculation is rather complexed.

Anyway, after I read this paper, I think now it should be proven that realtime raytraing with BVH can handle dynamic scene quite efficiently!
(Whereas KD-tree is not yet… I think KD-tree based realtime raytracing will be dead sooner or later).

A Real-time Beam Tracer with Application to Exact Soft Shadows

A Real-time Beam Tracer with Application to Exact Soft Shadows
Ryan Overbeck, Ravi Ramamoorthi, and William R. Mark,
Eurographics Symposium on Rendering, 2007.
http://www.cs.columbia.edu/cg/publications.php

[En]

This paper presents CPU realtime beam tracing method based on clipping(yeah, it is idential to Sutherland clipper used in traditional polygon rasterizer).

The method is much faster than previous beam like raytracing which is capable of soft shadow calculation.

Spatial structures used in this beam tracer is kd-tree, but I think it could be easily adapted to use BVH or grid.

Advantage of present beam tracer.

– Fast raytracing on flat surface.
– Exact soft shadow(no monte carlo noise for area light!)
– Naturally calculates derivative(ray differentials)

Disadvantage of present beam tracer.

– Slower raytracing for highly complexed scenes(e.g. polygon is smaller than pixel)

For now, beam tracer’s disadvantage is critical for offline massive rendering.
But I think once any more better spatial structures/traverser for beam tracing is found,
beam tracing might be widely used for CPU online/ofline raytracing.

LLVM 2.0 & gcc 4.2

[En]

(Feb 14, 2008 Updated: Here is an updated version LLVM 2.2 v.s. gcc 4.2)

LLVM 2.0 and gcc 4.2 are now just released.

http://llvm.org/
http://gcc.gnu.org/

I did a benchmark comparison with them.
I chose himeno bench for the bench mark program since it is portable, small and simple to compile and run.

http://w3cic.riken.go.jp/HPC/HimenoBMT/index_e.html

The himeno bench was compiled on my Core 2 Duo Intel Mac with
gcc-4.0.1(apple), gcc-4.2 and llvm-2.0 & llvm-gcc4-2.0.

Here is the result graph.

llvm_gcc_bench.png

And here is the procedures and outputs correspond to above graph.

gcc 4.0.1(apple) (latest gcc from Xcode Tools)


$ gcc -o bmt -O3 -DSMALL himenoBMTxps.c
$ ./bmt
...
 Gosa : 1.167853e-04
 MFLOPS measured : 544.017453   cpu : 56.726971
 Score based on Pentium III 600MHz : 6.634359

gcc 4.2


$ gcc-4.2 -o bmt -O3 -DSMALL himenoBMTxps.c
$ ./bmt
 ...
 Gosa : 1.753087e-05
 MFLOPS measured : 953.891485   cpu : 54.242544
 Score based on Pentium III 600MHz : 11.632823

Emit LLVM code with llvm-gcc-4-2.0, then exec it with LLVM JIT.


$ ~/src/llvm-gcc4-2.0-x86-darwin8/bin/llvm-gcc -emit-llvm \\
  -O3 -DSMALL -c himenoBMTxps.c
$ ~/src/llvm-2.0/Release/bin/lli himenoBMTxps.o

 Gosa : 2.229028e-05
 MFLOPS measured : 1147.841139  cpu : 42.767418
 Score based on Pentium III 600MHz : 13.998063

The result tells me that LLVM JIT does good job(20% faster than natively geneted code by gcc-4.2),
altough we must pay attention that “Gosa”(which means computational error in Japanese) is a bit higher than gcc-4.2’s result.

gcc-4.0.1 is fairly bad… I don’t know why…

Although I just did comparison for one benchmark program,
still I think LLVM’s JIT might generate efficient and optimized native codes than gcc’s backend.
It would be worth to use LLVM for your perfomance oriented program.

Yes, I know for fair comparison we must investigate each assembly codes generated by gcc and llvm,
and do pipeline simulation for it using profiler such like AMD’s simulation utilities…

[Ja]

LLVM 2.0 と gcc 4.2 がリリースされています。

gcc 4.2 は、このリリースから正式に OpenMP がサポートされています。

lucille をより multi-thread 対応にすべく、
lock-free 同期とか試してみましたが、下手に multi-thread のコードを書くよりは、
OpenMP に任せるほうが費用対効果は高いかもと考えています。

さて、ふと、LLVM の JIT 性能はどんなものかと思い、
ベンチマークを取って gcc のコードと比較してみました。

手っ取り早く動いて、コンパクトですぐにお試せれるようなグラフィックス系のベンチマークを探したのですが、
あまりよいのがないので、姫野ベンチ(small 版)をベンチマークプログラムに選ぶことにしました。

LLVM JIT のほうは誤差が大きくなっているのが気になりますが、
gcc の吐いたバイナリより 20 % ほど高速な結果になっています。

中間言語や JIT コンパイルは遅い印象があったので、
中間言語 -> JIT コンパイルのほうが native コードへのコンパイルよりも
高速に動作したのは意外でした。
(プログラムは 1 つしか試していないので、
これがすべてに当てはまるとはかぎりませんが)

以外と LLVM の(JIT)性能はいいのかもしれません。

より fair な比較が必要であれば、
LLVM の llc を使えばネイティブのアセンブラを出力してくれますので、
Shark(PowerPC Mac) や amd simulation utilites [1] で
プロファイル解析やパイプライン解析をして比較してみるのも手ですね。

LLVM とシェーディング言語

今年の SIGGRAPH 2007 ではリライティング技術の
lightspeed という論文が採択されていますが、
これは RenderMan SL の AST を作り、
automatic specialization などを行っています。

specialization など、これらを自分で一から書くのはめんどくさそうなので、
RenderMan SL -> LLVM に変換して、
LLVM に最適化やプロファイル解析などいろいろやらせると
いうのでも、なかなか良さそうな結果が得られそうな気がします。

RSL -> LLVM に変換するコンパイラを書いてみようかな?…

[1] http://lucille.atso-net.jp/blog/?p=233

Sampling with Polyominoes

SIGGRAPH07_thumbnail_SamplingWithPolyominoes.png

Victor Ostromoukhov,
Sampling with Polyominoes,
Proceedings of ACM SIGGRAPH 2007, ACM Transactions on Graphics, 26(3), 2007.
http://www.iro.umontreal.ca/~ostrom/SamplingWithPolyominoes/

[En]

It is fast and has good spectral distribution againt Recursive Wang Tiles. Cool!
I think this is one of the best (2D) sampler in the world!

[Ja]

Penrose tile sampler で有名な Ostromoukhov 先生がやってくれました。

RWT(Recursive Wang Tiles) と同じくらい高速、deterministic(非 deterministic も可能)、RWTよりも良いブルーノイズ特性。
RWT を抜いて、また新たな世界最強のサンプラーが生まれました。すげー。
SIGGRAPH 2007 でもっとも注目に値する論文の一つだと思います。

基本となる考え方は Penrose tile sampler と同じで、
Penrose tile をポリオミノ(テトリスみたいなやつ)で置き換えるという感じです。

http://ja.wikipedia.org/wiki/ポリオミノ

ポリオミノからサンプリングとは、よく思いつくものです(ペンローズもそうですが)。
サンプリングの道は奥が深いです。