Syoyo Fujita's Blog

raytracing monte carlo

Month: February, 2006

Bresenham noise

Kameya and J.C. Hart,
“Bresenham Noise”,
Proc. Western Computer Graphics Symposium. Mar. 2000
http://www.tricity.wsu.edu/~mkameya/research.html

Evaluating noise with forward differenting such like scanline rendering.

ピクセルごとに毎回きちんとノイズ関数を計算するのではなく、スキャンラインやポリゴンレンダリングのように、差分計算でノイズ関数を効率的に計算しようという論文。 論文の実装では 10 % ほどの向上しかレポートされていませんが、今年提案された wavelet noise はタイリングなし版できちんと計算させると結構な計算量になるので、wavelet noise とかと組み合わせたりできると、wavelet noise のノイズ計算が早くなったりしないかなと思います。

参考

Flash sort

http://www.neubert.net/FSOIntro.html

I think flash sort algorithm( O(N) time complexity ) is one of the fastest sorting algorithm in the world.

Flash sort というソートアルゴリズムが、なかなかよさげです。

紹介文には、『クヌースは「その場での(in-situ, つまり extra なメモリ領域がいらない)ソートアルゴリズムは、平均して O(n log n) 時間を要するだろう」という予測をしたが、しかしこれはもうハズレである。新しいアルゴリズムであるこのフラッシュソートは、 O(n) 時間のその場でのアルゴリズムである』とあるくらいですから、なんとも”スゴ味”が伝わってきます。

ソートのアルゴリズムといえば、
 o クイックソート(+ 挿入ソート)
 o 基数ソート
 o bitonic merge sort( GPU とか向け )
がたぶんよく知られている効率的なソートアルゴリズムだと思いますが、
フラッシュソートはこれらよりもより効率よくソートができるソートアルゴリズムではないかと思います。

実際にちょっと試したところ、ランダム値のソートでは、フラッシュソートがもっとも高速でした(もちろん、本来でしたら、ロバスト性を考えるためにいろいろな種類の数値列に対してソートアルゴリズムを試してみる必要があります)。

オフラインレンダリングでは、ほとんどソートが必要になる処理はありませんが、
リアルタイムですと、アルファポリゴンの並べ替え、衝突判定での sweep-and-prune、動的 kd-tree の構築などで良質かつ高速なソートアルゴリズムを必要とするでしょうから、このフラッシュソートを試してみる価値はあるかと思います。 

genre: Overdrive action

ジャンル: 波紋疾走(オーバードライブ)アクション
今夏発売予定

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

今夏までは、私も今以上にがんばろうと思いました。
ぜひ対戦モードがほしい….

Justin Talbot’s thesis

Justin F. Talbot,
Importance Resampling for Global Illumination
Master’s Thesis, Brigham Young University, 2005.
http://www.justintalbot.org/

Justin Talbot is known as a first person who introduced importance resampling(sequential monte carlo method) to the global illumination problem.

インポータンスリサンプリング(逐次モンテカルロ法)の大域照明への適用を提案した BYU のひとの修士論文が公開されていました。今年の SIGGRAPH 2006 あたりでは、同じ人たちからかは判りませんが、ここらへんの手法の発展版が発表されそうだと個人的には予想しています。ERPT といい、理論 GI 屋としては、 BYU から出る論文はこれからは要チェックです。

Automatic Light System for POV-Ray

Clipi, of Kerkythea team, told me lightsys, a spectral and physically-based extension of povray.

http://www.ignorancia.org/lightsys.php

Also check out SU2POV, SketchUp to Pov-Ray.

http://amazone.crai.archi.fr/Ruby/su2pov.htm


The spectral data of commercial light used in these system is valuable for me to implement spectral-based rendering in lucille.
By seeing such system, I feel that I should study more on spectral-rendering…

Clipi さんという、Kerkythea レンダラや SketchUp モデラのユーザとして有名な方から、
lightsys や SU2POV を教えていただきました。すでに商用光源のスペクトルデータなどを使って
スペクトルレンダリングを実現しています。シュゴー….
私も精進しなければなりません。

いくつか光源のスペクトルデータをいただいたので、
(たぶんデータ自体はどこかでちらばりちらばりに公開されていると思います)
sunsky の次は、これら光源のスペクトルデータを使ったスペクトルレンダリングの実装に進もうと
思います。その次はマテリアル(BRDF)のスペクトル対応かな。

High Dynamic Range Imaging

hdr tm

High Dynamic Range Imaging

http://www.amazon.co.jp/exec/obidos/ASIN/0125852630/
http://books.elsevier.com/companions/0125852630/hdri/html/hdri.html

トーンマップを調べているときにちょうどよく発売されていました。
通称 HDR 本。

付録の dvd-rom にはいろいろデータが入っているのですが、
特に貴重なリソースとして、 20 種ほどのトーンマッパーのソースコードが収録されています。
というか今までに発表されたトーンマッパーの論文のすべての手法が実装されているのでは?…
これは役立ちそうです。

HDR book の名に負けず、前頁カラーです。

実はこの本、 HDR 印刷されていて、適切にトーンマップされたメガネを通して見ると、
通常は余白に見える(白飛びしている)部分にいろいろ文字が浮かび上がってくるらしいです。