Syoyo Fujita's Blog

raytracing monte carlo

Month: September, 2006

RT06 papers and presentations

RT06(リアルタイムレイトレ学会) の paper と presentation のスライドのいくつかが公開されています。

http://www.sci.utah.edu/~wald/RT06/papers/papers_presentations.html

Pixar ‘Cars’ で使われたレイトレ手法と、MLRTA のひとの Omnidirectional ~ が興味深いです。

Ray tracing for the movie ‘Cars’

‘Cars’ で使われたレイトレについての解説です。基本は講演者である Per. H. Christensen
(昔は彼が歩いた後にはフォトンマップの花が咲くと言われていた)
が EG 2003 にて発表したレイ微分と多重解像度メッシュを用いたレイトレ手法

Ray Differentials and Multiresolution Geometry Caching for Distribution Ray Tracing in Complex Scenes

を ‘Cars’ のレンダリングに導入しましたよ、というお話。
レンダリングは prman にて、スキャンラインとこのレイトレのハイブリッド。
レイ微分を計算するためには、レイを三本同時にトレースするのですが、いずれかがジオメトリの
境界をまたいでしまう場合(もしくは交点が見つからない場合)の処理をどうしたらいいものかなー、
と常々頭を悩ませています。オリジナルの EG ’03 の論文でもあまりそこらへんは突っ込まれて
解説されていません。実務で使う場合には、そこらへんの扱いが非常に重要になると思われますので、
その部分も解説されているとよかったかなぁと思います。
まだスライドしか見ていないのと、pdf の詳細な解説文章もあるので、そちらにもしかしたら
詳しく書かれているかもしれません。あとでよく読んでみます。

また、常に三本のレイをトレースするためレイトレのコストが増えてしまうのですが、
やはりそれよりもシェーディングのコストの方がかかるようです。

ところで、いくつかのプロダクションからは、
prman のレイトレは遅せーよ。しかも巨大シーンはレンダリングできねーし。
という話を聞きます。ここらへんは ‘Cars’ に使った prman のバージョンでは改善されているんでしょうかね。

いずれにせよ、Pixar に限らず多くのプロダクションレンダリングでもレイトレが確実に用いられてきていることを実感します。

Omnidirectional Ray Tracing Traversal Algorithm for kd-trees

二次レイ以降の反射、屈折などのコヒーレンスのないレイ群に対するレイトレをどうするか、ということのようです。
結果的には、「既存手法にくらべればそこそこ結果はいいけど、まだまだダメっす」… という感じです。
二次レイ以降のコヒーレンスのないレイ群を、どううまくあつかって高速なレイトレを実現するかは、
まだまだ open な問題とのこと。
手法は興味深いので、論文を読んでみたいですね。やはりスライドだけではよくわかりません。

おまけ

こ、これがうわさに聞く Philipp Slusallek 先生の総回診ですか!
http://www.sci.utah.edu/~wald/RT06/images/index.html

私もいずれ、、、登りつめてみせる、、、、

Advertisements

AMD simulation utilities

http://developer.amd.com/calinux.aspx

AMD simulation utilities は、

AMD Codeanalyst
http://lucille.atso-net.jp/blog/?p=188

から、パイプラインシミュレーションのみを抜き出したものです。linux ではコマンドラインで動作させることができます。細かくプログラムを変化させて調べたいときは linux 版、可視化して全体を確かめたい場合は win 版(Code Analyst)を使うとよいかもしれません。

Intel も AMD のようにこのようなパイプラインシミュレーションツールを出してくれれば、
x86 コードの Core 2 での実行解析をしてみたいとことですが、相変わらずそのような気配はないようです。

simulation utilities は、linux では以下のようにして使います。

$ tracegen --function ray_box_intersect --launch ./a.out
$ simulate --preload    // warm up cache
$ simreport

まず、tracegen にて、測定したいコード区間のインストラクションを抜き出します。測定区間の指定はいろいろできるようですが、関数単位が一番わかりやすいでしょう。–function でどの関数のコード部分を測定するか指定できます(インライン化で関数が”無くなっていないか”注意しておきましょう。objdump などであらかじめ測定したい関数が存在するかどうかチェックするとよいです)。–launch で測定対象のアプリ名を指定します。

tracegen を実行すると、インストラクションのトレースデータがファイルに保存されます。これに実際にシミュレーションをかけてインストラクション実行解析を行うのが simulate です。

ここで、キャッシュの warm up を考慮するかどうかを指定できます。
warm up を考慮しないと、まずはじめにキャッシュミスが生じる状態からシミュレーションが行われます。
たとえば 10 インストラクション程度の処理でも、はじめに 1000 サイクルとかのキャッシュリフィルが
考慮されてしまったりします。
関数を複数回呼び出したり、正確に測定したい場合は warm up なしがよいでしょうが、
(たとえば関数呼び出しの二回目、三回目は in cache になっているかどうか確かめる)
今回のように多くの場合は関数を一回実行させてその実行解析を行うのが主になるかと思います。

その場合は、すでにデータが in cache である状態でシミュレーションさせたほうが、
インストラクション依存解析などコードそのもの解析ができて便利です。

このようにすでにデータが in cache の状態からシミュレーションをスタートさせるには、
simulate に –preload オプションを指定します。

最後に、シミュレーション結果を simreport を用いてレポートさせます。
といってもテキストがずらずらと出てくるだけですが…

今回、レイとボックスの交差判定を行う SIMD コードをテストコードとしてシミュレーションにかけてみました。

元々 flipcode にあるもの
http://www.flipcode.com/cgi-bin/fcarticles.cgi?show=65014

を C 言語に書き直し、icc でもコンパイルが通るように変更したものです。

http://lucille.atso-net.jp/svn/angelina/simd/raybox_intersection/

実行は AMD64 環境で行いました。

ray_box_intersect() 関数をトレースしたところ、43 インストラクションがトレースされました。

objdump による ray_box_intersect のアセンブラリストは以下の通り。

—–

  400500:       0f 28 0e                movaps (%rsi),%xmm1
  400503:       31 c0                   xor    %eax,%eax
  400505:       0f 28 57 10             movaps 0x10(%rdi),%xmm2
  400509:       0f 28 07                movaps (%rdi),%xmm0
  40050c:       0f 5c d1                subps  %xmm1,%xmm2
  40050f:       0f 28 6e 10             movaps 0x10(%rsi),%xmm5
  400513:       0f 5c c1                subps  %xmm1,%xmm0
  400516:       f3 0f 10 1d ee 06 10    movss  1050350(%rip),%xmm3       
  40051d:       00
  40051e:       f3 0f 10 25 ea 06 10    movss  1050346(%rip),%xmm4       
  400525:       00
  400526:       0f c6 db 00             shufps $0x0,%xmm3,%xmm3
  40052a:       0f 59 d5                mulps  %xmm5,%xmm2
  40052d:       0f 59 c5                mulps  %xmm5,%xmm0
  400530:       0f c6 e4 00             shufps $0x0,%xmm4,%xmm4
  400534:       0f 28 ea                movaps %xmm2,%xmm5
  400537:       0f 28 c8                movaps %xmm0,%xmm1
  40053a:       0f 5d eb                minps  %xmm3,%xmm5
  40053d:       0f 5f d4                maxps  %xmm4,%xmm2
  400540:       0f 5f c4                maxps  %xmm4,%xmm0
  400543:       0f 5d c2                minps  %xmm2,%xmm0
  400546:       0f 5d cb                minps  %xmm3,%xmm1
  400549:       0f 5f cd                maxps  %xmm5,%xmm1
  40054c:       0f 28 d1                movaps %xmm1,%xmm2
  40054f:       0f 28 d8                movaps %xmm0,%xmm3
  400552:       0f c6 d1 39             shufps $0x39,%xmm1,%xmm2
  400556:       0f c6 d8 39             shufps $0x39,%xmm0,%xmm3
  40055a:       f3 0f 5d ca             minss  %xmm2,%xmm1
  40055e:       0f 28 d1                movaps %xmm1,%xmm2
  400561:       f3 0f 5f c3             maxss  %xmm3,%xmm0
  400565:       0f 28 d8                movaps %xmm0,%xmm3
  400568:       0f 12 d1                movhlps %xmm1,%xmm2
  40056b:       0f 12 d8                movhlps %xmm0,%xmm3
  40056e:       f3 0f 5d ca             minss  %xmm2,%xmm1
  400572:       0f 57 d2                xorps  %xmm2,%xmm2
  400575:       f3 0f 5f c3             maxss  %xmm3,%xmm0
  400579:       0f 29 4a 10             movaps %xmm1,0x10(%rdx)
  40057d:       0f 2f ca                comiss %xmm2,%xmm1
  400580:       0f 93 c0                setae  %al
  400583:       31 c9                   xor    %ecx,%ecx
  400585:       0f 2f c8                comiss %xmm0,%xmm1
  400588:       0f 93 c1                setae  %cl
  40058b:       21 c8                   and    %ecx,%eax
  40058d:       0f 29 02                movaps %xmm0,(%rdx)
  400590:       c3                      retq  

——————

レポートは以下のようになりました。

だいたい実行には 45 cycles + α を消費するということでしょうか?
(CPI とかもオプションで表示されるようです)

サイクルがリタイアでのサイクルなので、どのサイクルから開始と見たらいいのかよくわかっていませんが、
最初のリタイアサイクル -10~20 サイクルが最初のサイクルと考えてよいのでは、と思います。
(レポートでは最初にいきなり RETQ インストラクションが出てきていますが、これはなぜでしょうね)

SimReport option summary
The simulation data file is : trace.sim
The execution option is on
**********************************************************************
   Simulation Time: Sat Jul 15 01:20:19 2006

   Target Application and arguments: ./a.out
   Target Module: ./a.out
   Target Module Base: 0x0000000000000000
   Target Module Loading Address: 0x0000000000000000
   Simulation Processor type: Opteron
   Simulation Processor Multiplier: 0
   Preload Cache option is On
   There are 2 breakpoint
   BreakPoint-0
      Address: 0x0000000000400500,Type: Start Simulation, Iteration: 1
   BreakPoint-1
      Address: 0x0000000000400590,Type: Stop Simulation, Iteration: 1
**********************************************************************
File: File symbol not available
      Function name: ray_box_intersect   Source line: 0
      Instruction address: 0x0000000000400590    Retire Cycle: 900
      RETQ
      Delta completion cycles: 0
      Statistics summary:
        ( 1 ) Reference missed in data TLB L0
        ( 1 ) Reference missed in DC
      —————————————-
File: File symbol not available
      Function name: ray_box_intersect   Source line: 127
      Instruction address: 0x0000000000400500    Retire Cycle: 920
      MOVAPS (%RSI),%XMM1
      Delta completion cycles: 20
      Statistics summary:
      —————————————-
      Instruction address: 0x0000000000400503    Retire Cycle: 919
      XOR %EAX,%EAX
      Delta completion cycles: 0
      Statistics summary:
      —————————————-
      Instruction address: 0x0000000000400505    Retire Cycle: 924
      MOVAPS +0X10(%RDI),%XMM2
      Delta completion cycles: 10
      Statistics summary:

….

      —————————————-
      Instruction address: 0x000000000040057d    Retire Cycle: 961
      COMISS %XMM2,%XMM1
      Delta completion cycles: 0
      Statistics summary:
      —————————————-
      Instruction address: 0x0000000000400580    Retire Cycle: 961
      SETNB %AL
      Delta completion cycles: 0
      Number of dependents: 2
      dependent 0 : ip = 0x0000000000400503 cycle = 919
      dependent 1 : ip = 0x000000000040057d cycle = 961
      Statistics summary:
      —————————————-
      Instruction address: 0x0000000000400583    Retire Cycle: 961
      XOR %ECX,%ECX
      Delta completion cycles: 0
      Statistics summary:
      —————————————-
      Instruction address: 0x0000000000400585    Retire Cycle: 963
      COMISS %XMM0,%XMM1
      Delta completion cycles: 17
      Statistics summary:
      —————————————-
      Instruction address: 0x0000000000400588    Retire Cycle: 963
      SETNB %CL
      Delta completion cycles: 0
      Number of dependents: 2
      dependent 0 : ip = 0x0000000000400583 cycle = 961
      dependent 1 : ip = 0x0000000000400585 cycle = 963
      Statistics summary:
      —————————————-
      Instruction address: 0x000000000040058b    Retire Cycle: 963
      AND %ECX,%EAX
      Delta completion cycles: 1
      Number of dependents: 2
      dependent 0 : ip = 0x0000000000400580 cycle = 961
      dependent 1 : ip = 0x0000000000400588 cycle = 963
      Statistics summary:
      —————————————-
      Instruction address: 0x000000000040058d    Retire Cycle: 965
      MOVAPS %XMM0,(%RDX)
      Delta completion cycles: 13
      Statistics summary:
      —————————————-

オフラインレンダリングでも早いに越したことはないので、
これでバリバリ lucille を最適化していったらリアルタイムレイトレの 1/10 くらいの速度には達する
ことができるかな?

Fast and Efficient Compression of Floating-Point Data

floatzip.jpg

Peter Lindstrom and Martin Isenburg.
Fast and Efficient Compression of Floating-Point Data
IEEE Visualization 2006.
http://www-static.cc.gatech.edu/~lindstro/

メッシュ簡略化野郎 Peter Lindstrom とメッシュ圧縮野郎 Martin Isenberg による、
fp データのリアルタイムロスレス圧縮に関する論文です。

range coder をベースとしたシンプルな圧縮器(coder)を提案し、
高速、かつ既存のロスレス fp 圧縮とほぼ同じな圧縮率を達成しています。
圧縮率は、平均して 1/3 ほど(32bit float)になるとのこと。
64bit double の場合はそれよりも圧縮率は落ちて、1/1.5 から 1/2 ほどのようです。 

すでに同著者らは、メッシュデータに対する fp ロスレス圧縮

http://lucille.sourceforge.net/blog/archives/000383.html

を提案していますが、今回のは特に圧縮の対象となるデータに制限はなく、
ボクセルデータでも点データでもなんでも OK というのが特徴となります。

レンダリングデータの多くは浮動小数点ですから、並列レンダリング時の
各ノードへのレンダリングデータの分配のときなどに使えますね。
実装も簡単なようですから、応用例は多くありそうです。

SBR 2006 観覧会 2

ゴゴゴ….   ゴゴ….   ゴゴゴゴゴゴ…..   ゴ…..
   ゴゴ….   ゴ….   ゴゴゴゴ….   ゴ….   ゴ….

10/1(日曜) に開催します。

詳細は SBR 2006 のページをご参照ください。
http://lucille.atso-net.jp/sbr2006/

SBR 2006 観覧会

ゴゴゴ….   ゴゴ….   ゴゴゴゴゴゴ…..   ゴ…..
   ゴゴ….   ゴ….   ゴゴゴゴ….   ゴ….   ゴ….

今年も、SIGGRAPH 論文の実装を披露する、SBR 2006 観覧会を開かせていただきます。

日時: 9/30(土曜)
場所: 東京・恵比寿

詳細は SBR 2006 のページで随時お知らせします。

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