Syoyo Fujita's Blog

raytracing monte carlo

Month: October, 2005

ワンダと巨像

ちょっとだけやりました。

いやー、スゲー

ポリゴン数が少なかったり、ミップマップすら切り詰めている感じがしますが、

エフェクト効果がすごいです。

これがもし PS3 で出たらもっと表現がきれいになるんでしょうね。

しかし、剣でザックザクは生々しすぎです…

Advertisements

Tiled and mip-mapped texture data structure.

レンダラでテクスチャキャッシュを使うにあたって、
まずは、jpeg などの画像をタイル(64×64
などのピクセルブロックで持つ)化し、
またミップマップを事前計算してファイルにテクスチャデータを保存するフレームワークを
angelina に書いてみました。
(prman の texmake
とかもこれと同じような処理をしているはず)
書き出すときには、zlib でデータを圧縮するようにしています。


http://lucille.atso-net.jp/svn/angelina/texturing/tiledmipmap/

ただ、このままではまったくまだまだ使い物にはなりません。
(実際、
ファイルからテクスチャデータを読み出して貼り付けるというとこまでまだ実装していない)

ここから、異方性テクスチャリングのために Rip-map にも対応、

単純な平均和でないミップマップフィルタ処理、
ミップマップ時のボーダーの処理、
non-power-of-two な大きさの画像サイズへの対応、

テクスチャ時のフィルタを考えて、
あらかじめタイルにフィルタ幅ぶん
余分にピクセルを取っておくかとか、
実際に使えるものにするにはいろいろと
こまごました処理が追加で必要になります。

とりあえずは初期テストとして、8192 * 8192
の解像度くらいあれば十分だろうと思い、
8192 * 8192 の jpeg ファイルを作成して、
このフレームワークを使ってテクスチャを作ってみましたが、、、、

アホにみたいにスワップファイルにガリガリアクセスし、5
分くらいコンバートに
時間がかかってしまいました。

よく考えたら、内部では色は fp32x4 で持つようにしているので、
単純に考えてテクスチャだけで
8192 * 8192 * 16 = 1GB
も使っていることに気がつきました。mipmap
用や作業用にさらにメモリを確保しており、
実行中にシステムモニタを見ていたら、最大の時には メモリ +
スワップで 3 GB くらいも使っていました。
( 64bit kernel な linux で実行したので、問題なく
2GB 以上の仮想メモリ量も使えたようです)

うーん、コンバートするときも、

o 画像ファイルをまず一部だけ読み込み
o タイル化・ミップマップ化して書き出し
o 繰り返す

するようにして、メモリ使用量を減らす必要がありそうです。

Generation of Stratified Samples for B-Spline Pixel Filtering

Stark, M., Shirley, P., Ashikhmin,
M
Generation of Stratified
Samples for B-Spline Pixel
Filtering
Journal of
Graphics Tools, v.10 no. 1 (2005),
pp. 61-70
http://www.cs.sunysb.edu/~ash/

B-spline 関数の分布に従って、層別サンプル点を生成する手法。

テーブルルックアップではなく、
解析的な生成手法を提案しています
(三次の B-Spline 関数まで)。

B-Spline をピクセルフィルタ関数に選ぶ一番の理由として、

論文では、ピクセル中心に B-Spline
カーネル関数の中心をおいたときに、
各カーネルからの重みの総和が画像面のどこでもちょうど 1
になることを挙げています。

三次 B-Spline でも、
層別サンプルのための解析式は高々 四次関数になります。

実際には、マジメに解析解を計算するよりは、
ニュートン法を用いた数値解のほうが
効率がよくまた精度よく解が求まるそうです。

見た感じでは、サンプルはなかなかきれいに分布しているようです。

計算式も簡単ですので、試してみる価値があると思います。

ここからさらに Adaptive sampling にも使えるように、

stratified な progressive
性も出せるようだとさらにうれしいのですが、
そのようなサンプリングスキームは無いものかなぁ…

論文 abstract
日本語訳

B-spline フィルタカーネルは、
ピクセルサンプリングの各種応用において
有益であることが知られています。

特に、4 ピクセル幅の 三次 B-spline
フィルタカーネルが効果的です。

分散レイトレーシングにおいて、
サンプリング密度がフィルタ値に比例するように
ピクセルフィルタが暗に評価されています。

本研究では、B-spline
密度関数に従うようにランダムなサンプルを生成する、
シンプルな手法を提案します。

誤差を減らすためには、一様サンプリングのためのジッタリングと同様に、

サンプルを層別化させることが重要になります。

1, 2, および 3 階の B-spline
カーネルに対してのこのようなことを行う、
代数的および数値的手法を提案します。

黄金比と素数とハッシュと

最近は linux
のソースコード、ひいては OS のしくみなんかを
ちょくちょくと調べるようになっています。

これからレンダラをさらに頑健なものにしていったり、
メモリ効率よくレンダリングを
行うようにするにはどうしたらよいかを考えていくと、
レンダラがやっていることと
OS
のカーネルがやっていること(つまり資源の管理方法)との関連性が深いと感じているためです。

そこで、
今回はテクスチャのキャッシュ管理でタイルベース以外で良いものがないかと思い、

linux のメモリ管理の部分を読んでみました。

linux の実装では、キャッシュのタグ計算に黄金比で
ハッシュを計算するのが見受けられました。
該当のハッシュ関数のソースコードは

include/linux/hash.h

にあります。

ハッシュ関数は、32bit マシンでは 2^32 に、64bit
マシンでは
2^64
の黄金比に近い素数(GOLDEN_RATIO_PRIME)を乗するという、
非常にシンプルなものとなっています。

hash = GOLDEN_RATIO_PRIME *
val

この、
黄金比に近い素数がハッシュの計算に適している理由は、
Knuth
先生のライフワーク本の三巻で詳しく説明されているとこのことです。

The Art of Computer Programming:
Sorting and Searching (Art of
Computer Programming Volume
3)

http://www.amazon.co.jp/exec/obidos/ASIN/0201896850

さらに、この素数には、
乗算が遅いマシンでもシフト演算で計算できるような組み合わせが選ばれており、

32bit の場合は

/* 2^31 + 2^29 – 2^25 + 2^22 – 2^19
– 2^16 + 1 */
#define GOLDEN_RATIO_PRIME
0x9e370001UL

が設定されています。

ちなみに、黄金比といえば、
いとしさと切なさと心強さの黄金比の正確な計算は、
膨大な計算量が必要であり、スーパーコンピュータで計算しても 2, 3
年は
かかると言われています。

Viki

Viki――Vi使いの方へ

http://www.itmedia.co.jp/enterprise/articles/0510/10/news002.html

Vi(Vim) 上で動く Wiki とのことです。
ちょっと使ってみましたが、なかなかよさそうです。

Mac, Windows, Linux のどこでも vi
を常に使っている身としては、
極めればかなりすばらしい統一的なメモ帳、アイデア帳になりそうです。

また、別途 Deplate というコンバートツールを使えば、

Wiki の内容を HTML, LaTeX などにも
出力できるそうですから、原稿書きにも使えるかもしれません。

fiber(microthread)

シェーディング言語の Du(), Dv()
関数をどのように実装したらよいものかと
いろいろ調べています。

とあるプロダクションのレンダラでは、
シェーダコード(ネイティブコード)に Du()
が現れた時点で
カレントコンテキストを退避させるなどして微分値を計算しているとこのことでした。


http://lucille.atso-net.jp/blog/archives/2005/08/lucille.html

というわけで、まずは、そもそも OS
のコンテキストスイッチはどのように行われているのか
といろいろ調べていたところ、
fiber(micothread
などとも呼ばれている) というスレッドテクニック
があることを知りました。


http://d.hatena.ne.jp/shinichiro_h/20040106


http://www.sun-inet.or.jp/~yaneurao/yaneSDK3rd/chap0124.html
 (やねう先生)

基本的には、fiber とは、OS
のコンテキストスイッチがやっているような、
スタックの退避・復帰を自前で行う、
スレッドよりも軽量なしくみと捕らえることができます。

隣の(次の) fiber へ制御を移せたり、
任意場所でスレッドを止めたりなど、
Du() の実装にもっとも適していそうな気がします。

まだ実装にはトライしていませんが、fiber
を使っての実装は以下のようにできそうです。
微分計算のために、シェーディングの近隣点で 3 or 4 個の
fiber を走らせておき、
各スレッドで Du() が呼ばれた時点で、残りの Du()
が呼ばれるまでスレッド実行をサスペンド
(次の fiber へ処理を移す)、全部の fiber での Du()
の call が終わったところで、
数値微分で Du() への引数の微分値を計算、という手順です。

ただ、たとえば

if (oraora_desu_ka == yes) {
    N = x;
} else {
    N = Du(x);
}

のようなシェーダコードがあり、Du()
のコール回数が必ずしもすべての
シェーダ fiber
スレッドで一致しない場合があったりするときはどうするか、
というこを考えなくてはなりません。
(とはいえ、中間言語方式の prman や aqsis
でもこのことは問題になりそうなので、
aqsis や Pixie などでの Du()
自身の実装のしくみを調べてみる必要がありそうです)

スタックの退避・復帰

スタックの退避・復帰には、

o アセンブラで直接書く
o setjmp/longjmp を使う
o
getcontext()/setcontext()

を使う

などで実現可能のようです。setjmp を使うのが、
一番ポータビリティが高いようです。

__builtin_expect()

ところで、linux
のカーネルソースでコンテキストスイッチを行う部分を見ていたのですが、

結構コンテキストスイッチだけでも多くの処理が行われているのですね。
 

また、カーネルソースのいたるところで unlikely() や
likely() という関数を分岐部分に使っているのに
気がつきました。実際には、この関数は
__builtin_expect() へのマクロとして定義されています。

この __builtin_expect() は、
静的(コンパイル時)に分岐へのヒントを与える gcc の拡張機能です。

(gcc 2.96 くらいから在るみたい)


http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#Other-Builtins

最近の CPU は分岐ミスによるペナルティが大きくなっていますから、
分岐するときの判定として、
あらかじめあまり評価が真にならないことが期待できる場合には、
unlikely() を使い分岐予測の
ヒントを与えることで、分岐のペナルティをを減らすことができます。

(gcc のドキュメントでは、-fprofile-arcs
にて実際に分岐のプロファイルを
あらかじめ取っておくことを推奨しています)

/* else 文が実行される確率が高い */
if (unlikely(ひ... ひと思いに右で... やってくれ)) {
  ...
} else {
  /* No! No! No! */
  ...
}

/* else 文が実行される確率が高い */
if (unlikely(ひ... 左?)) {
  ...
} else {
  /* No! No! No! */
  ...
}

/* if 文が実行される確率が高い */
if (likely(りょ... りょうほーですかあああ~)) {
  /* Yes! Yes! Yes! */
} else {
  ...
}

/* if 文が実行される確率が高い */
if (likely(もしかしてオラオラですかーッ!?)) {
  /* Retire... */
} else {
  ...
}

結構レンダラの内部でも分岐処理を行っている部分がありますので、
この __builtin_expect() を
使って、
ボトルネックになりそうな分岐の部分を書き直すとパフォーマンスがアップしそうな気がします。

 

A photon accurate model of the human eye

Michael F. Deering
A photon accurate model of the human
eye
SIGGRAPH 2005
http://doi.acm.org/10.1145/1073204.1073243

人間の目の光子正確なモデルの提案。
といっても、タイトルだけみてもちょっとよくわかりませんね。

この論文が提案しているのは、

o 網膜の錐体の分布を生成するアルゴリズム(retinal cone synthesizer)
o 光子の吸収をこの視細胞分布に対してどのように分配させるのか

の二点になります。

つまりは、人間の数百個もの視細胞(人間には錐体と杵体)がありますが、
光が入射してきたとき、これら個々の視細胞がどのように反応を起こすのか、
ということをモデル化してシミュレーションするというのが論文の提案になります。

アプローチとしては合成した網膜の錐体配置パターン上に、人間の目の性質も考慮してピクセル画像
や光の emission を投影させる(これは Point spread function で近似できるようです)とのことです。

Accompanying video にはビデオシーケンスの例があったりして、これには eye drift 現象
など人間の目の特質もシミュレーションで表現されているようなので見てみたいのですが、、、、
いつになったら SIGGRAPH 2005 の Proceedings DVD は届くのだろうか…

論文では、人間の目のしくみと光学的な性質についても詳細に解説されています。

網膜の視細胞分布(中心窩ほど密度が高く、離れるほど密度が低くなる)というのは、
昔から幾度となくコンピュータグラフィックスでも取り上げられてきましたが、
本論文が提案する Reinal cone synthesizer は既存のものよりも分布が良好だったり
物理的により正確だったりするのかな。

このような分布はアンチエイリアシングやサンプリングなど
いろいろな分野に応用できると思うので、いろいろ試してみたいと思います。

それにしても、人間の視細胞分布も六角形パターンが見られるのですよね。
やはり六角形は世界で一番美しいパターンに違いない。ビバ! Hexagon!

論文 abstract 日本語訳

デジタルディスプレイ上に画像を知覚させるように、
人間の個々の錐体の光子正確な(photon accurate)モデルを提案します。

ピクセルビデオのストリームの連続表示というのは、
各ディスプレイのピクセルの物理的な微細構造内における光子の放出イベントによりモデル化されます。

したがって、生成される電磁波は、人間の角膜(cornea)と水晶体の 4 つの表面モデルにより曲げられ、
瞳孔(pupil)で回折が生じます。

網膜にある 500 万個の視細胞(photoreceptor)の錐体(cone)の、位置・大きさ・形状・傾きを、
新しい網膜モデルで個々にモデリングします。

光子の吸収のイベントを、波面の消失を錐体での光子の検出イベントとして扱うことで、網膜錐体内の光子をカウントして画像を生成します。

これらの画像のシーケンスを生成するために用いたカスタムのレンダリングシステムは、画像の情報の光学的、物理的な性質を考慮しています。
目の細胞内における波長依存の吸収、あるフレームを見ている間にわずかに目が動くことにより生じるモーションブラーなども考慮しています。

本論文が示す新しいモデルの構築は、コンピュータグラフィックスのレンダリングアルゴリズムの変更や、画像表示デバイスの変更が、
どのように人間の観測者が見るアーティファクトに関連するか、を理解するための大きなフレームワークの一部になります。