休載

ド.. ドドド..  ドドド…. ドドドドド….   ドド… ドドドド… ド…    ドド   ドド     ド… ドド… ド…  ド…    ド… ド… ド…    ド…   ドド… 2/16 あたりまで、休載します。   ドドド… ドド… ド…    ド… ドド…     ドド….   ドド… ドド.. ド…    ド…

Green’s intersection method

Green の交差判定法というのは以下のようです。 Simple, Fast Triangle Intersection, by Chris Green http://www.acm.org/tog/resources/RTNews/html/rtnv6n1.html#art6   ちなみに Green の交差判定法を含め、各種交差判定法の reference が載っている論文が J. Amanatides and K. Choi, “Ray Tracing Triangular Meshes”, Proceedings of the Eighth Western Computer Graphics Symposium, April 1997, pp 43-52. にあります。本論文では、プリュッカー座標系(Pluecker coordinate)による交差判定が各種交差判定法より 25 % 程度高速であると述べています。プリュッカー座標系は、レイが三角形の内部にあるかのテストが内積のみでできるので、 非常に数値計算がロバストであるという利点があるものの、プリュッカー座標では 6×3 = 18 floats のストレージコストがかかるのと、t までの計算は効率的ですが、u, v まで求めるとなるとより extra な計算量が必要になりそうなのが欠点でしょうか。 to beContinue reading “Green’s intersection method”

SIMD ray intersection, SIMD BSP traversal

リアルタイムレイトレの鬼と呼ばれる Ingo Wald 博士の博士論文が公開されている。 Ingo Wald, Realtime Ray Tracing and Interactive Global Illumination Ph.D. Thesis. http://www.mpi-sb.mpg.de/~wald/PhD/index.html 氏がかかわってきたリアルタイムレイトレプロジェクト RTRT(Real Time Ray Tracing) や SaarCOR の集大成でもありますが、とくに第七章では、それらのコアとなる SIMD ray/triangle 交差判定や SIMD BSP トラバーサルのコードつきでの詳細な解説があります。 SIMD ray intersection レイと三角形の交差判定には、重心座標をベースとした射影法(Projection Method)を採用しています。射影法は、 三角形の法線ベクトルの xyz 要素のうち、もっとも大きい平面へと三角形を射影することで、問題を 2 次元に落とし込んで処理を効率的に行うというものです。また、射影する平面は法線ベクトルの要素がもっとも大きい方向となるので、 determinant の計算でゼロ割が生じることもないため、より計算はロバストになります。 射影法はまた、各種係数を前計算しておくことができるため、交差判定計算も単純になります。博士論文では、 各三角形毎に交差判定に必要な前計算の係数データは 48 byte(キャッシュラインにのせるためにパディングを含む)となっています。 struct TriAccel { // first 16 byte half cacheContinue reading “SIMD ray intersection, SIMD BSP traversal”

Solid Harmonics

さて、今となっては球面調和関数を調べることは ほとんどなくなってしまったのだが、有益な変換式をいまさらながら 見つけました。 通常球面調和関数は球面座標で与えられますが、 デカルト座標での (x, y, z) による解析的な式で表現することができる ことはよく知られています。 http://www.cs.princeton.edu/~ah/publications/multipole/html/node30.html リアルタイムグラフィックスでの利用を考えると、 評価が容易なデカルト座標での解析的な式が好まれるでしょう。 んで、実は 5 次以上とかになるとあまりネットや文献ではこの デカルト座標での解析式は載っていないので、 (高次になると数値誤差も問題になりますしね) 当時はもんもんとしながらどこかに無いものかと探し回っていたのですが、 なんと Mathematica でお手軽に計算する方法がッ!! http://mathforum.org/epigone/comp.soft-sys.math.mathematica/kigruzhon 虚数部は単に捨てて実数部だけ使えばいいはず。 ヤベー、マジすげーよ。Mathematica。ひれ伏します。 まあ、今となっては生真面目に p+q+s=l and p-q=m となるような (p, q, s) の組を総当りで探すプログラムを書くのでもよかったんだなぁと 思いを馳せる日々であった。

SIMD ray/box intesection 2

前回 SIMD でレイとボックスの交差判定を行うコードを紹介しましたが、 http://lucille.sourceforge.net/blog/archives/000372.html flipcode のほうで、 Inf となるコーナーケースの問題にも対応したよりロバストなバージョンが公開されていました。 http://www.flipcode.com/cgi-bin/fcarticles.cgi?show=65014 しかし、このコードは SSE では動くが( min(NaN, Inf) = Inf ), altivec に移植しようとなると altivec は java モードであるため、 min(NaN, Inf) = NaN となってしまうので注意が必要である。   http://www.simdtech.org/apps/group_public/email/altivec/200412/msg00006.html というわけで、AltiVec 版に書き直してみた。 #include <stdio.h> #include <math.h> // AtiVec version of ray/box intersection from flipcode static vector float vplus_inf; static vector float vminus_inf; static vector float vzero; staticContinue reading “SIMD ray/box intesection 2”

bit interleaving 3

以前、Hacker’s Delight(ハッカーのたのしみ) において、 ビットインターリーブ(bit interleave)がグラフィックスに応用があるがその元ネタはどこ? と述べましたが、 http://lucille.sourceforge.net/blog/archives/000384.html http://lucille.sourceforge.net/blog/archives/000365.html 実は Graphics Gems I でちゃんと取り上げられていました。 Hacker’s Delight において、ヒルベルト曲線のグラフィックスへの応用 の部分の解説部分で引用されていたのが Graphics Gems II であったので、 その時点でもしや? と気づくべきでした。 Graphics Gems I でのビットインターリーブは、 クアッドツリー(四分木)とオクツリー(八分木)のアドレッシングへの応用であり、 私の Z 曲線順のなんかよりもはるかに詳細に解説されています。 それにしても、やはり Graphics Gems はすごいなぁ、なんか大体思いつくと だいたいはすでにそこに載っているようなものだったりする。 今でも内容は色あせていないし。 Graphics Gems は「こりゃスゲーよ。Graphics Gems にはッ!!、 全巻買わなければ!! と思わせる『スゴ味』があるッ!」 という感じでとりあえず全巻所有しているのだが、 その正統なる後継である? Game Programming Gems や GPU Geoms には日本語版があるにもかかわらず、 まったく持って食指が動かないのはなぜだろうか? さらにそのContinue reading “bit interleaving 3”

valgrind, x86 linux プログラムデバッガ & プロファイラ

==1278== Use of uninitialised value of size 4 ==1278== at 0x806D014: ri_vector_mul (in /home/syoyo/work/lucille/src/lsh/lsh ) ==1278== by 0x4242C99E: ??? Matt Pharr 大先生も御用達? の valgrind というツールがあります。 http://valgrind.kde.org/ このツールは、メモリリークの検出、スレッドエラーの検出、 キャッシュのプロファイル、ヒープのプロファイルなどと、 非常に高性能かつ多機能なメモリ関連ツールです。 本ツールの大きな特徴としては、 たとえば dmalloc のように特別になんらかのライブラリとリンクしたり、 ソースコードを書き換える必要はなく、すでにコンパイルされたプログラムを そのまま処理できる点でしょう。 もちろん、デバッグ情報付きでコンパイルされていれば、 たとえばメモリエラーが起きたときには、 そのエラーの起きた関数名と行番号が出力されます。 x86 linux 限定であるという制約はあるものの、 Mac OS X の malloc_history, leaks と並び非常に使えるツールです。 (PowerPC/linux への移植版も行われているようです) Windows でも、colinux で動かせば問題なく使えます。 ためしに lucilleContinue reading “valgrind, x86 linux プログラムデバッガ & プロファイラ”

Thai Statue

Thai Statue も lucille でレンダリングしてみました。512×512 ピクセル、2×2 アンチエイリアシング、Structured Importance Sampling を用いてシェーディング点あたり 300 サンプル。メッシュデータは簡略化せずに元の 1000 万三角形です。 うーん、やはり 512×512 じゃ 1000 万三角形の細かさは見えませんね。やはり最小でも 1024×1024 でレンダリングしないといけませんね。

Jim Blinn’s Corner 日本語版

  Jim Blinn のコラム本が日本語となって出版されている。 Jim Blinn’s Corner 日本語版 (1) A Trip Down the Graphics Pipeline http://www.amazon.co.jp/exec/obidos/ASIN/4274065367 Jim Blinn’s Corner日本語版 (2) Durty Pixels http://www.amazon.co.jp/exec/obidos/ASIN/4274065650 Jim Blinn’ Corner といえば、今回日本語版を読むまでは、 SIGGRAPH 2002 のときに無償で配られていた IEEE Computer Graphics and Applications 誌でちらりと見たきりである。 (その号での記事は “Visualize Whired 2×2 Matrix”) 今読み返して見ると、この号には、 Andrew Glassner’s Note (これは Jim Blinn’s Corner と同じく、Andrew Glassner により 長らく連載されているコラムである)  と GeometricContinue reading “Jim Blinn’s Corner 日本語版”

Xorshift RNGs

G. Marsaglia. Xorshift RNGs. Journal of Statistical Software, 8(14) :1 6, 2003 http://www.jstatsoft.org/v08/i14/xorshift.pdf George Marsaglia 氏により 2003 年に考案された、xor とシフトを使うだけの超高速な擬似乱数生成器(Random Number Generator, RNG)です。周期は 2^k-1(k = 32, 64, 96, 128, 160, 192)。ランダム性のテストにも十分合格するとのこと。たとえば、周期が 2^128-1 の場合のルーチンは以下のようになり、乱数値の計算部分はわずか 1 行である。 unsigned long xor128(){ static unsigned long x=123456789,y=362436069,z=521288629,w=88675123; unsigned long t; t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) ); } Xorshift 法については、擬似乱数研究で有名な Pierre L’Ecuyer 氏によりその理論の解析が行われている。 F.Continue reading “Xorshift RNGs”