Syoyo Fujita's Blog

raytracing monte carlo

Month: February, 2005

シェーダのインポータンスサンプリング

大域照明レンダラにおいて、
シェーダをシェーダ言語で処理するようにする上で
難点となりそうなのが、シェーダの
インポータンスサンプリングです。

インポータンスサンプリングは、大域照明においては
ほぼどの部分でも用いられていますが、
既存のシェーダ言語には、インポータンスサンプリングの
概念がないため、たとえば illuminance() ループで光積分を
行うときに、BRDF 定義がシェーダで行われるときに、
BRDF ベースのインポータンスサンプリングを
行おうとなると、シェーダを解析して BRDF を抽出するなどの処理が必要になります。

この問題に対して、vision では、あらかじめ illuminance() ループへの
パラメータとしてインポータンスを与える方法を提案しています。

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

とはいえ、この方法はユーザがそのようなシェーダを書く必要があるので
大変です。

PRMan(RI spec 3.3)では、この問題のためであろうか、
フォトンマップ用の材質設定には、いくつかの BRDF のモデルのプリセットが
定義されているようです。レンダラはこのプリセットを元にインポータンス
サンプリングを行っているのかな?

既存のシェーダの枠組みのまま、レンダラ側が自動でインポータンス
の計算に必要な情報を抽出できると便利です。

というわけで、いくつか案は思いついているのでちょっと実装することを考え中。
このために(?)、自前のシェーダコンパイラを作っているのですからね。

月間化

再開されるというのに…..

う、うおおおおおおおおおおおおおおおおおおおお
おおおおおおおおおおおおおおおおおおおおおお
おおおおおおおおおおおおおおおおおおおおおお
おおおおおおおおおおおおおおおおおおおおおお
おおおおおおおおおおおおおおおおおおおおおお
おおおおおおおおおおおおおおおおおおおおおお
おおおおおおおおおおおおおおおおおおおおお!!

なぜだッ!!!! なぜなんだぁッ!!!

というわけで、本日記も月ごとに更新になってしまう
やもしれません。

Irradiance Filtering for Monte Carlo Ray Tracing 2

さて、前回 412 万レイ/秒と書いてしまいましたが、
どうもよくよく論文を見てみると、結果の表の数値を
読み間違っていたようです。

なんか数値にスペースがあるので、単に「.」が抜けている
だけかと思いましたが、どうも total 時間との整合性を
考えると、「,」と読み取るのが正しいようだ….

というわけで、結局ヘリコプターのシーンでは、
5, 531 秒(irradiance filtering)かかっているようです。

irradiance filtering の equal quality である irradiance cache
にいたっては、約 3 万秒…

フォトンマッピングや放射照度推定も考えれば、
この時間は標準的なものと捉えてよさそうです。

いずれにせよ、コントロールが難しく、
かつしみのようなアーティファクトを消すのも困難な
放射照度キャッシュに比べれば、
論文の提案する放射照度フィルタリングのほうが
実装しやすいし、既存の MC レイトレに組み込みやすいと思います。

というわけで….

K 場: 間接照明におけるグローバルイルミネーションの I.Q. その 1 !!
放射照度キャッシュの弱さを知れ!!

それを克服する最強の手法が、

放射照度フィルタリング(IF)だ!!!

O 田: 放射照度キャッシュを克服する手法…
放射照度フィルタリングかあ!

M 浦: ちくしょー 早く使ってみてぇー!!!

AGP readback の怪

GPU Jackpot での講演スライドに、不可解な数字がある。


ftp://download.nvidia.com/developer/presentations/2004/GPU_Jackpot/GeForce_6800_Performance.pdf

Increased Read Back Performance の項目によると、
GeForce 6800 では、AGP におけるリードバックのパフォーマンス
が 600MB/sec – 1.0GB/sec に向上しているとのこと。

PCI-Express(Quadro FX 4400)でのリードバックが 1.0GB/s ですから、
PCI-Express 並みのパフォーマンスということになります。

AGP x8 の帯域は 266MB/sec ですから、

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

普通に考えると 600MB/sec – 1.0GB/sec というのはありえない数字です。

AGP チップセットによる、とありますので、考えられるのは、
チップセットか GPU 内にリアルタイム圧縮転送機能でもあるのかな?

そういえば、NV の特許にカラー圧縮というのがあった気がします
ので、少し調べてみようかな?

ついでに、GeForce 6800 を gpubench にかけると、
ADD と MUL だけほかのインストラクション(たとえば SUB や MAD)
よりも 2 倍のパフォーマンスになります。

というわけで、ここから GF6 の FP unit の構成が見えてきたりするわけ
ですが…

Irradiance Filtering for Monte Carlo Ray Tracing

Janne Kontkanen, Jussi Rasaen and Alexander Keller
Irradiance Filtering for Monte Carlo Ray
Tracing

MC2QMC 2004
http://www.tml.hut.fi/~janne/irradiancefiltering/

疎な(ノイズのある)サンプリングから、サンプルに応じて
フィルタの幅を数学的に正しく設定してフィルタリング
を行うことで、(結果画像を見る限り)ノイズのない
きれいなレンダリング結果を効率的に得るという手法。

Ambient Occlusion Fields とおなじ著者ですね。

放射照度キャッシュ(Irradiance Cache)にくらべて、
同品質であれば 5 倍高速、
同レンダリング時間であれば放射照度キャッシュに
特有のしみのない結果を得ることができるとのこと。

基本的には、普通に各ピクセルごとにサンプリングレイ
を飛ばすのですが、dependent test を利用することで、
各サンプリング点における放射照度の積分は
16 サンプル以下で済まし
(放射照度キャッシュは 256-4096 サンプル程度必要)、
あとはうまく近傍とのフィルタリングを行うというのが
特徴のようです。

フィルタリングでうまくモンテカルロレンダリング画像の
ノイズを減らそうというのは、論文でも cite されている
ように、Jensen や Suykens や McCool などによって
すでに提案されていますが、いずれもなんらかの
欠点があるとのこと。

http://lucille.sourceforge.net/blog/archives/000378.html
http://lucille.sourceforge.net/blog/archives/000086.html
http://lucille.sourceforge.net/blog/archives/000050.html

しかし、各サンプル毎に 16 サンプルレイと少ない
レイを飛ばすとしても、アンチエイリアシングを
行う場合はそれに比例して増大することになります。

結果の表を見ても、画像サイズが 640×480 か 1024×768 の
いずれかはわからないのですが(本手法は画像サイズに比例
して処理が増える)、
ヘリコプターのシーンでは、
総サンプル数が 1566 万に対して、サンプリング時間が
3.8 秒、フィルタリングを含めて全部で 5.5 秒とありえない
くらい早い(Pentium4 2.8GHz)…

純粋にサンプリングがレイトレだとすると、

1566/3.8 = 412 万レイ / 秒

のパフォーマンスです。いったいどんな最適化しているんだ…

ともあれ、放射照度キャッシュと同程度の時間で、
かつ放射照度キャッシュによくみられるしみのような
アーティファクトが出ないし
(たとえば論文だと、ちょっと見にくいですが、うさぎと
部屋のシーンにおけるランプ台とか)、
マックスプランク像の結果画像を見る感じでもかなりよさげです。

ただ、ぼやけないできれいなフィルタリングができるのが
特徴なのに、なぜヘリコプターのシーンでは変にブルームを
かけているのでしょう?

クリッパー

クリッパー(clipper)を angelina に実装してみました。
(バイナリは windows 用)

http://lucille.atso-net.jp/svn/angelina/geom/clipper/

クリッパーとは、クリップ処理を行うルーチンです。

lucille では、レイトレのための空間データ構造として、kd-tree や一様グリッドを用いています。
もし分割面やグリッドをまたぐようなポリゴンがある場合は、クリッピング処理はせずに、
同じポリゴンの情報を分割されうるすべての領域に登録しています。

とはいえ、この場合だと、kd-tree の場合は最適な解に達することができずに
うまく効率的に分割できないことがあったり
(cornell box のような至極単純なシーンで起こりやすいのでたちが悪い)、
また一様グリッドの場合でも、
ヒットしたポリゴンが実際に現在のグリッド内にあるかどうか
をチェックする必要が生じます。

前々からクリッピングの必要性は感じていましたが、なんかめんどくさそうだなー、
と思って手をつけずにいました。

今回クリッパーを実装しようと思い立ったきっかけは、
BSP を使わずとも、どの視点からもすでにソート済みのポリゴンリストを取り出せるという
なんともシュゴーな手法をグラキャドで
聴講したのがきっかけでした。

福重 真一、鈴木宏正
ポリゴン間のプライオリティ決定のための円環型データ構造
第 118 回 情報処理学会 グラフィクスとCAD研究発表会
http://www.okada-lab.org/GCAD/Sched/2004/prog118.txt

BSP に比べて、ソート時間がとても早くなる(というかそもそもソートの必要がない)
のですが、より多くのメモリ消費量の問題、
視点の制限、必ず正確なソートになるかなど、いくつかまだ問題はありそうですが、なかなか興味深い。

提案されているのはアルファのあるポリゴンレンダリングのための BSP の代案手法が
メインなのですが、これをレイトレに適した空間データ構造として実現するとなると…
と考えてみて、やはりまずはともあれクリッピングは必須だなという結論に達したのです。

とはいえ、実際にクリッパーを実装してみると、以外にも思っていたより
美しく処理できることができることがわかり、ちょっと感動。
やっぱ昔のひとはすげーよ。

今回実装したのは、有名な Sutherland-Hodgeman クリッピングアルゴリズムです。

Ivan E. Sutherland and Gary W. Hodgman,
Reentrant polygon clipping
Commun. ACM,
17(1), pp. 32-42, 1974
http://doi.acm.org/10.1145/360767.360802

詳細は Foley 本(邦訳「コンピュータグラフィックス 理論と実践」) にあります。

Foley 本では実装のアウトラインを示しているだけですが、
それでもコードを自分で補間するのは簡単にできるでしょう。

クリッピングといっても、凸ポリゴンか凹ポリゴンかでまた微妙に処理が異なるらしいのですが、

今回は、

o 入力ポリゴンは三角形に限定
o kd-tree の場合は 1 つの平面でクリップ
o 一様グリッドの場合は軸並行ボリュームの 6 平面でクリップ

という条件での三次元ポリゴンのクリップになります。

この場合ですと、入力される三角形ポリゴンは、最大でも 6
角形ポリゴン(全部の辺がクリップされる)までとなる(はず?)ので、
あらかじめ出力のバッファには二倍のポリゴンを保持するメモリを割り当てておけば十分になります。

クリップ処理部はこんなかんじになります。

typedef struct _vertex_t
{
      float x, y, z;
} vertex_t;

typedef struct _plane_t
{
      float x, y, z;
      float nx, ny, nz;       // normal
} plane_t;

void clip(vertex_t *in, vertex_t *out, int inLen, int *outLen,
    plane_t *clipPlane)
{
    int j;
    vertex_t *s, *p, i;
    vertex_t newv;
    *outLen = 0;
    s = &in[inLen - 1];     // start with last vertex.
    for (j = 0; j < inLen; j++) {
    p = &in[j];     // current vertex
    if (inside(p, clipPlane)) {
            if (inside(s, clipPlane)) {
                    output(p, outLen, out);
            } else {
                    intersect(&newv, s, p, clipPlane);
                    output(&newv, outLen, out);
                    output(p, outLen, out);
            }
    } else {
            if (inside(s, clipPlane)) {
                    intersect(&newv, s, p, clipPlane);
                    output(&newv, outLen, out);
            }
    }
    s = p;
}

bool inside(vertex_t *p, plane_t *b)
{
      vertex_t pb;
      float d;

      pb.x = p->x - b->x;
      pb.y = p->y - b->y;
      pb.z = p->z - b->z;

      // if ((p - b.pos) dot b.normal) >= 0, then p is inside
      d = pb.x * b->nx + pb.y * b->ny + pb.z * b->nz;

      if (d >= 0) return true;

      return false;           // not inside
}

void intersect(vertex_t *i, vertex_t *s, vertex_t *p, plane_t *b)
{
      vertex_t v;
      double vdotn;
      double sdotn;
      double d;

      double t;

      // direction
      v.x = p->x - s->x;
      v.y = p->y - s->y;
      v.z = p->z - s->z;

      vdotn = v.x * b->nx + v.y * b->ny + v.z * b->nz;
      if (fabs(vdotn) < 0.0001) {
              printf("error: vdotn is too small!\n");
              printf("  vdotn = %f\n", vdotn);
              exit(-1);
      }

      // d = plane equation
      d = -(b->x * b->nx + b->y * b->ny + b->z * b->nz);

      sdotn = s->x * b->nx + s->y * b->ny + s->z * b->nz;

      // t = ray parameter of intersection point.
      t = -(sdotn + d) / vdotn;
      assert(t >= 0.0);

      i->x = s->x + t * v.x;
      i->y = s->y + t * v.y;
      i->z = s->z + t * v.z;
}

void output(vertex_t *p, int *outLen, vertex_t *out)
{
        out[(*outLen)].x = p->x;
        out[(*outLen)].y = p->y;
        out[(*outLen)].z = p->z;
        // increment index
        (*outLen)++;
}

クリップ面が複数ある場合(たとえば軸並行ボリュームでクリップ)は、
以下のようにダブルバッファ構成にすればいいでしょうか。


static plane_t clipPlanes[6] = {
  { 0.0, 1.0, 0.0, 0.0, -1.0, 0.0 },      // top
  { -1.0, 0.0, 0.0, 1.0, 0.0, 0.0 },      // left
  { 0.0, -1.0, 0.0, 0.0, 1.0, 0.0 },      // bottom
  { 1.0, 0.0, 0.0, -1.0, 0.0, 0.0 },      // right
  { 0.0, 0.0, -1.0, 0.0, 0.0, 1.0 },      // back
  { 0.0, 0.0, 1.0, 0.0, 0.0, -1.0 },      // front
};

void volumeClip()
{
    int i;
    vertex_t *tmp;
    int bufLen;
    plane_t clipPlane;
    in = &(bufTri[0]);
    out = &(outTri[0]);
    bufLen = inLen;
    for (i = 0; i < 6; i++) {
        // clip!
        clip(in, out, bufLen, &outLen, &clipPlanes[i]);
        tmp = in;
        in = out;
        out = tmp;
        bufLen = outLen;
    }
    out = in;
}

あとは、クリップ面がポリゴンのエッジや面とほぼ重なりつつも平行になっている場合とか、
クリップされるばあいの交点の計算および交点位置の頂点パラメータの補間処理
などにおける数値演算誤差へのロバストな対応が必要になりそうです。

とところで、GPU に載っているハードウェアクリッパーって、どうなっているのかぁ。
最近の NV とかの GPU では、同時座標ラスタライズでクリッパーは不要になっているみたいですね。
ハードウェアでの実装云々は、論文を読むより特許を読んだほうが早いかな?

VaraTerm, .NET Terminal Emulaor

VaraTerm は、 .NET なターミナルエミュレータです。

http://www.routrek.co.jp/product/varaterm/

Varaterm がオープンソースになるというニュースを知り、
その存在を初めて知りました。

TeraTerm に対する特徴としては、

o タブ機能
o CygTerm のように、Cygwin のシェル(bash など)と直結させることができる。

があげられます。

現状、TeraTerm と CygTerm でそこそこ不満もありつつも、
putty での直結やデフォルトの cygwin ウィンドウに比べれば
使いやすいので愛用していたのですが、VaraTerm は
CygTerm よりも使いやすそう(真ん中マウススクロールが使えたり)。

日本語関連とかを除けば、ほぼ不満のない操作のできです。

CELL でグローバルイルミネーション

CELL チップが ISSCC で発表されました。
まあなんかいろんなところで、発表された内容は取り上げられているので、
もうとくに(公開されている範囲で)チップ性能に関して取り上げることはないかな。

ほんで、スタンド攻撃に会わない程度で、公表内容の範囲で、
G.I.Q.
の能力を使い、グローバルイルミネーションレンダラを
CELL に実装するにはなにがいいかなーと想いを馳せてみました。

まず、やはり大きなアドバンテージになり、同時にアルゴリズムを実装
する上での悩みのタネになりそうなのが、8 個の
SPU(Synergistic Processing Unit) でしょう。

機能的には、SPU は AltiVec, SSE のような SIMD 演算を行います。
EE に対する VU が 8 個付いたようなもんですね。
除算もテーブルベースのものがあるようなので、
よくある逆数推定命令 + ニュートンラフソン法で求められるのでしょう。

また、SPU は独立して動き、DMA も含むので、
主メモリやいろんなところからデータを引っ張ってこれたり、
書き込んだりできるらしい。
(ここが、基本的に決まった場所にしかアクセスできず、同じ処理を行う
GPU の並列ピクセルパイプとは異なるアーキティクチャですね。
まあピクセルパイプは、いかにして高速にピクセル処理をするかが
重要ですので異なるといえば当たり前ですね)

とはいえ、SPU は、おのおのに搭載された 256kb とのローカルメモリとしか
いろいろ楽しいことができないらしい。
このローカルメモリには、インストラクションの保存領域も含まれているでしょう
から、256 kb 以上のプログラムを SPU では実行できないということになるで
しょうか。

とはいえ、レイトレベースの GI レンダラで SPU を使うとなると、
空間トラバース処理、レイトレ交差判定の 2 つくらいになりそうなので、
定型処理だしプログラムもそれほど長くなりそうにならないので問題ないかな。

結局のところ、やはり既存の GI レンダラにおけるランダムメモリアクセス
がそのまま CELL で実現するときにも問題になるのは変わりなさそう。

キラウェアのようにシーン分散を考えても、256×8 = 2MB ぶんのシーンしか
扱えないし。

幅優先レイトレをするとしても、レイのデータを 256 kb に収めるのは
それほどシーンを大きくできないだろうし。

バスの速さを生かして、kd-木などのトラバーサル処理時に
常にノードデータを DMA で転送してきて処理するとか、
常に交差判定時にノード内のポリゴンを DMA でつど転送して処理するとか、
やはりストリーミング的に処理するのが一番の解かもしれません。

結局のところ、いかにしてメモリアクセスを局所化して
SPU で一度に処理するデータを減らし、かつ DMA 転送も減らすかになりそう。

うーむ、やっぱり実際に実装してためしてみんとわからん。

ZP+: correct Z-pass stencil shadows

opengl.org より。

Samuel Hornus, Jared Hoberock, Sylvain Lefebvre, John C. Hart
ZP+: correct Z-pass stencil shadows

ACM Symposium on Interactive 3D Graphics and
Games – April 2005
http://artis.inrialpes.fr/Publications/2005/HHLH05/
 
通常の Z-pass 法によるステンシルシャドウボユームの欠点を補正した手法。
よりロバストな方法として、 Z-fail 法がありますが、Z-fail 法は Z-pass 法に比べて
80% ほど低速になるとのこと。しかし提案される ZP+ 法は、Z-pass 法に比べて
10% 程度の性能低下にとどまるとのこと。しかも ZP+ 法であれば、Z-fail 法では
扱えないトライアングルストリップによるジオメトリも扱えるとのこと。
(Z-fail 法でもトライアングルストリップを扱う手法が提案されていた気がしないでもないけど
忘れてしまいました)

また、Z-fail 法が Z-pass 法より高速になることがあるときの、その場合の条件
についても考察しているようです。

そろそろ次世代のシャドウアルゴリズムは、シャドウマッピングなどのイメージ手法が
復権しそうな気もするのですが、どうでしょうかね。

あと、おなじく I3D に採択されているものとして、
アンビエントオクルージョンを動的なシーンにも対応した

Ambient Occlusion Fields
http://www.tml.hut.fi/~janne/aofields/

も気になります。PDF はまだ未公開のようです。

G.I.Q

O田: ねえ、K場センセー
そんなに GI(グローバルイルミネーション) がはやっているのに、どうしてみんなは GI をやってないんですか?

Y木: レンダリング時間が長いからだ

O田: え?

Y木: GI は写実的な絵を作れる反面、レンダリング時間が下がって損をする場合だって当然ある。。。
まあ、時間との兼ね合いみたいなもんだからね

K場: 。。。それもある。。。 だが、もっと云えるのは —-
知らないからだ

M 浦: え!?

Y木: し、知らないだと?

K場: ああ。。。今のレンダラ書きもお前たちとおなじで、GI については誰からも
一回も教えてもらったコトがない!

GI
なんてとんでもない ポリゴンレンダラのレンダリング品質が低くてもしょうがない 地味でもいいからマジメにレンダリングしていれば 歳とってラクできる。
。。

だが何度も云うがルールは変わった!

陰面消去問題を解けばよい古いルールから
光輸送方程式を解かなければならないルールにな!

これまでは知識の “I.Q.” が重視された。。。。

——が

これからは
グローバルイルミネーションの I.Q. だ

O田: グローバルイルミネーションの。。。アイ。。キュー。。

Y木:

M浦: G. 。。。 I. 。。 Q. 。。

(中略)

K場: お前たちが GI のことを考えるのなんて面倒だと思っているのは単なる偶然じゃない
レンダラのビジネスや研究をやっている連中にとってはその方が都合がいいんだ!

グローバルイルミネーションの I.Q が低ければ—-
安っぽいスキャンラインレンダラがレンダラのすべてと思わせる
ことができるからだ

外野1: えっ!?

外野2: な。。なんだよそれ—-!?

外野3: チョーズルいじゃん! なんかムカツク — !

K場: 学校や職場で GI の話をするのがタブーみたいになっているのも まあ奴らの陰謀みたいなモンだな

お前たちはそれに乗せられ まんまと洗脳されてるってワケさ

どうだ? そんなレンダラ書き連中を出し抜きたいと思わねーか !?

—- もしこの中で GI レンダラの書き方を知りたい奴は….

…to be continued.