[Diary]
[Log]
[Projects]
[Articles]
[Parthenon]
[BBS]
[Profile]
[Mail]

卒論のため（13日発表）に
Nguyenらの"Physically Based Modeling and Animation of Fire"を実装しました．



2次元かつレンダリングは適当（black body radiationは考慮していない）ですが…
青い部分がgaseous fuelで，赤い部分がhot gaseous productsで，
緑の部分がgaseous fuelが流入している部分です．

ちなみにこの程度の解像度（128^2）なら余裕でリ（以下略）．

卒論のため（初稿の締め切りが明日）に，物凄い勢いで
Fattalらの"Target Driven Smoke Animation"を実装しました．
わりと簡単に面白い結果が出ます．



ちなみにこの程度の解像度（128^2）なら余裕でリアルタイムに動きます．

…卒論は計画的にやりましょう（投稿論文も）．

最近思いついたモノ．
（等高線無しのモノ）

レベルセットで計算していますが，再初期化を一切行っていません．
（それでもきちんと距離関数の性質を保っています）
ちなみに，"Level Set Evolution Without Re-initialization: A New Variational Formulation"
とは全く違います．上の計算では文字通り，再初期化をしていません．

The above animation was calculated by Level Set Methods WITHOUT reinitialization.
（However, the property of the signed distance function is certainly preserved.)
Its method is completely different from "Level Set Evolution Without Re-initialization:
A New Variational Formulation". It was literally calculated without reinitialization.

…これを含めるのは無理だろうなぁ

Projectsを少し更新．

今年度は無理だと思います．やらないと死ぬ事が他にあるので．
（そのわりには更新する暇があるんだね，というツッコミは無しでお願いします）

Parthenon Rendererをアップデートしました．
下記の「ライトマップの焼きこみ」をサポートしています．

しかし気がついたら，1年以上も放置していたんですね…
僕にとって去年は激動の１年だったので，あまり余裕がなかったせいも
あるかもしれません．今現在もかなり余裕ありませんが，
もう少しして環境が好転すれば，色々とやる時間が取れそうです．
（好転するかどうかは，かなり怪しいのですが）

好きなことを続けられる環境に居る，というのはそれだけで
物凄く幸せなことだったとつくづく感じます．
そういう意味で，今はあまり幸せには感じません．
もしかしたら，環境のせいにしているだけかもしれませんが．

…まあ愚痴は置いといて，
この更新ように，別にParthenonの開発を停止したわけではないので，
何か要望や意見などがあればBBSやメールなどで教えてください．

今回のライトマップのサンプルとして「ふり素」のBackGroundにある，
Paraboraを使わせてもらいました．きちっと作りこんであるおかげで
遮蔽が多いモデルなので，ライトマップが栄えますね．


Metasequoiaでのプレビュー

しかし，ライトマップのUV展開はやはりまだまだ問題がある事を再確認しました．
現在，3D Studio Maxなんかでは手作業でのboundary指定＋conformal mappingが
実装されたようですが，上のParaboraみたいに細かい部品に分かれている
モデルの場合には，やはりかなりの手作業が必要になると思われます．

かといって，自動化の一手段として全ての三角形をばらばらにして
配置すると，今度は編集不可能になる上にMIP Mapがほとんど使えなくなります．
（それぞれの解像度に合わせて作成すれば問題ありませんが）
MIP Mapが使えるように上手く展開する手法もありますが，
計算時間がかなりかかったような記憶があります．

あと，本来は影が出る部分（上の例だとアンテナ中心部分）には
大きな領域を割り当てたいわけで，計算結果に対してアダプティブに
UVを割り当てる方法が望ましいのに，現状はほとんど決め打ちで
やっている状況だと思います．

ずっと昔から存在するのに，未だに職人（デザイナー）の手作業に
頼る部分が多く，ソフトウェア側に改善の余地がある問題の一つだと思います．
何らかの基準で自動で分解する方法は，ほとんどの場合デザイナーの
手作業に負けるでしょう．彼らの職人技（と言うべきだと思います）は凄いのです．

この調子でPRTのSHによる係数を計算する機能もつけたいところですが，
アルゴリズムはそのまま使えるものの，ソフトウェアとして大きな変更が必要なので，
ちょっと気乗りしません．あれば面白い機能だとは思いますし，
実はちょっと需要もありそうな気がするのですが…

実は現状でも，ライトマップ機能が付いたことで，ある工夫によって
Parthenon RendererそのままでPRTのSHによる係数が計算できたりします．
気が向いたらその方法をそのうち書こうかと思います．
（鋭い方は既にお気づきでしょう）

今年の目標：生き残る

前々から要望があって，自分としても実装をしたかった
「ライトマップの焼きこみ」をParthenonに実装してみました．
まだテスト中ですが，とりあえず出来ているようです．


レンダリングしたライトマップ

もちろんGIを考慮していて，普通のレンダリングと
まったく変らない速度でレンダリングできます．

また，よく問題になる「テクスチャのつなぎ目」問題を
解決するために，背景を埋める処理を自動で行ってます．
そのおかげで512^2でレンダリングしたものを
128^2とかに縮小してもほぼ問題なく使えます．
その処理もGPU上で行ってます．


Metasequoiaでのプレビュー結果

まとまったら公開します．

PRTの係数（SH, Wavelet）も同じ枠組みで
計算して出力したら面白そうですが，データ量が多くなって，
単純に処理が面倒になるので，あまりやる気ありません．

SHだったら負の値を書き出せるフォーマットにすれば
今の枠組みでもできない事はありませんが，
その場合，係数の個数ぶんだけレンダリングしなければ
ならないのでオーバーヘッドが大きすぎます．

あと，
> 「accelerationのための構造体を前計算しない」という発想ッ！
は冗談ではありません．あるアイデアを考え中です．
（なんとなく駄目になる予感がしますが…）

サイトを整理しました．

あと，昔やった事も羅列しておきました．
まだいくつかありますが，とりあえず目についたものだけ．

ところで，GPU Raytracingでちょっと発見があったかもしれません…
それは「accelerationのための構造体を前計算しない」という発想ッ！

CGの分野は客観的にも成熟しているように見えるらしくて，
多くの人に，「CGってもうやる事無いよね？」と聞かれますが，
僕は決まって「いやいや，まだ沢山ありますよ！」と答えています．

具体的に何があるかは飯の種になる可能性があるので，
あまり大っぴらには書けませんが，その中で気になるトピックの
一つとして，モーションブラーのレンダリングがあります．

syoyoさんもlucille開発日記で同じような事を述べていますが，
現時点でモーションブラーを正確にレンダリングする
唯一の方法は，簡単に言うと違う時間での計算を
何度も行って，最終的な結果を求める方法しかありません．
しかも，どの時間で計算すれば効率的か？という事は
ほとんど考慮されておらず，「適当」に決められています．

これは率直に考えてもムダです．

例えば，高速に動く物体にモーションブラーがかかると，
細かいdetailはほとんど見えなくなりますから，
この点でも計算にムダがあると考えられます．

light transport problem（いわゆるGIの計算）についての
計算方法は，多くの研究者が様々なアプローチを
提案していますが，不思議なことに，モーションブラーについては
ほぼ手付かずのまま残っているといっても，
言い過ぎではない状況にあります．

同じような理由でDOF（Depth Of Field）も
効率の良いレンダリング方法は未解決だと思います．

たぶん，これらについて何か良い方法が出来れば，
リアルタイムへの応用も可能になるはずです．
もしくは，リアルタイムレンダリングの分野で
使われている手法に基づいて，何か新しいアプローチが
構築できる可能性もあります．


あと一つ，常々気になっている事なのですが，
例えば動的な反射をCubeMapsで行うときに，
何らかの点を基準としてCubeMapsを作成すると思います．

しかしながら，その点の位置は誰が決めているでしょうか？
「人間」が決めていませんか？もしくは，何らかの適当な
位置（重心とか）を選んでいませんか？

たぶん，動的な反射を行いたい物体が複数あった場合に，
どの点で・いくつの点で作成すると，この程度の誤差が出る
といった解析が可能だと思うのですが，
僕はそれを行っている論文を見たことがありません．
（PRTの論文でそれらしきものがあった気もしますが…）

ある物体の周りの環境をCubeMapsに落とし込んで
何らかの処理を行う，という手法は非常に沢山あるのに，
何故だかそのCubeMapsを作成する点の位置は
適当に決めていると思われるのが，気になっていました．

実は何か良い方法があったりするのでしょうか？
もしあったら教えてください．

よく「研究するなら論文は読むな」と言う人がいて，
正直何を言っているのやらさっぱりわかりませんでしたが，
その真意は「論文は読むべきだが，それに毒されるな」
という事のようです．

ただ，オリジナルな（独創的なという意味ではなくて，
基礎となるという意味）研究をやるとすると，
研究内容については(直接は)過去の成果が無いはずなので
「読む論文が無いぐらいのテーマで研究しろ」
という意味にもとれますね．ところが，既存のどんな成果にも
依存しない研究などは，もはやあり得ないので
テーマについて文献探しをするなという意味ではないようです．

日本語って難しいですね．

ところで，NEETの危機(?)はたぶん逃れたようです．
お騒がせしました > 関係者の方々

夏風邪で寝込んだりしつつも，Geometry Imagesの別バージョン(?)である，
"Spherical Parametrization and Remeshing"を実装してみました．

メッシュデータは前回と同じくベートーベン先生です．
Geometry Imagesでは平面上にパラメータ化していましたが，
今回は球面上にパラメータ化します．



実はこれは単純に平面での処理を球面に拡張するだけでは
上手く実装できません．どのようにして僕が実装したかは機会があれば書きます．
ただ基本的には，今年のSIGGRAPHのSketchで発表された
"Unconstrained Spherical Parameterization"の理論を元にしています．
本当はそのまま実装できたらよかったのですが，このSketchは聞き逃したため，
pdfのabstractを元に推測で実装しています．

ともかく，球面上でのパラメータ化が出来たら，結果を正八面体に
投影して，それを展開すると以下のような結果が得られます．


(クリックでTIFFをダウンロード）

見てのとおり，かなりの部分がほとんど同じ色，
つまりほとんど同じ座標値で占められていて，無駄が多いことが
わかります．これは論文で実装されているstretchを元にした
実装ではないからなのですが…細かい点はまた後で．
今回は513^2で作成してみました．

メッシュの構築は，この手法ではGeometry Imagesと
同じ処理を使うことが出来ます．実際に，今回の結果は，前回作った
Geometry Imageからメッシュを構築する処理を使って得られたものです．


（クラック無し！）

案の定，メッシュの下の部分でサンプリングが足りていないようです．
ただ，カットが常に一定なのでGeometry Imagesよりも
綺麗な（異方性の少ない）結果が得られるような気がします．
ポリゴンの流れが綺麗な結果になります．

…しかし今更ですけど，Geometry Images共々，使い道が謎です．
面白いから別に使い道なんてどうでもいいとも言えますが，
昨今はそうも言い続けてはいられないようなので，誰か有効な使い道を教えてください．

< 夏休みの工作 課題：Real Cornell Box >

今日は実際にCornell Boxを作りました．
既にネットでは何人か作っている人が居ますが，
面白そうなのでやってみました．

まだ完成していませんが（天井を貼ってない，壁がゆがんでいる），
とりあえず初期テストです．


（クリックで拡大）

こうして見てみると，反射率が低いせいなのか
color bleedingはほとんど目立たない程度でしか出ていません．
ともかく，これから色々置いて撮影してみますよー．

ちなみに材料費の関係で15[cm^3]の大きさなので，
中に入って撮影は出来ません．

「鉄は熱い内に打て」ということで，SIGGRAPH 2005のPoster原稿をuploadしました．
英語は自前チェック（しかも適当）なので，間違っているところがあったらこっそり教えてください．

ポスターを印刷する直前になって，もっとわかりやすい考え方で説明できることに
気が付いたのですが，時既に遅し，わかりづらい説明でそのまま印刷する事に
なってしまいました．来年度の学会でPaperにするか，論文誌に投稿するか
どんな形かはわかりませんが，もっとちゃんとした説明を書く予定です．

another GIと称して，Geometry Imagesを少しづつ実装していました．
（SIGGRAPH中もホテルに戻った後に実装していたり）

まだまだ出来ていないので，公開はもう少し後になりますが
現時点ではとりあえずgenus0のメッシュを不安定ながらも
展開できるようになっています．ただ，結構処理が重いので
ローポリじゃないとかなり時間がかかります．

僕はメッシュ系のプログラムを組んだことがなかったので，
メッシュのカットやらパラメータ化を一から組んだため，
試行錯誤でかなり時間がかかりました．この経験を踏まえて，
Geometry Imagesを安定して使えるレベルで組める人は，
かなりできるメッシュ野郎である，と推測します．

それで今のところの結果ですが，まずこんなメッシュが
（約1万ポリゴン，MQO）


Geometry Images変換のプロセスを経て
（インタラクティブに操作，処理時間約2分@PentiumM_1G）


こういうGeometry Imageに変換されて
（256^2のfloating point TIFF，RGBにXYZ座標値)

（クリックでTIFFをダウンロード）

それを元にしてこのようなメッシュが構築できます．
（約13万ポリゴン，バグでクラックが残っています…）


Geometry Imagesの特徴はいくつかあって，
・テクスチャ座標不要
・メッシュ圧縮（これは微妙な気が…）
・画像処理によるメッシュの操作（縮小によるLOD含む）
なんかがすぐに思いつく特徴です．そんなわけで結構面白い
特徴を持っているのですが，上にも書いたとおり，まず実装が大変です．
あと変換後のメッシュが結構汚いので，そのままレンダリングに使うのは厳しいです．
normal mapを加えてもかなり粗が目立つレベルです．

他にも実装中に気が付いた解決すべき問題がたくさんあって，
Geometry Imagesそれ自体は完成されたものではなく，
基礎となる研究であることが実感できました．

いやー，本当はこんな事やってる場合じゃないんだけどなぁ…

この計算では拡散項を入れていないので，ジャギーが発生するのが正しい計算のはずです．
好き嫌いの問題じゃないんですけどね…

The jaggies at injection by mouse are correct results in this case because the calculation
does not contain diffusion term. It is not the problem like "which one do you like?",
even if you dislike the jaggies.

（画像クリックでダウンロード）
(Click the above image to download the demo.)

SIGGRAPH2005のPosterの手法でインタラクティブなGPU上での
流体シミュレーションを作成しました．
左が従来のsemi-lagrangian法で，右が今回のPosterで提案する手法です．

この計算には拡散項や粘性項を含んでいないため，密度場や速度場は
全くぼけないのが正しいのですが，従来の手法では移流項に含まれる
数値拡散によって，すぐに移流する場がぼけてしまい，
細かい流れが計算できないという問題がありました．
ほかにも，数値拡散は水の計算で質量損失を引き起こします．

今回の手法では，その数値拡散を大幅に抑えることが出来るため，
同じ解像度の同じ計算であっても，より細かい流れを計算できます．
上のスクリーンショットではわかりづらいですが，実際に動作させて見ると
その「拡散をさせない」効果がわかりやすいかと思います．

動作にはDirectXで浮動小数点数テクスチャが使えて，
DirectXのShaderの2.0以降に対応しているGPUが必要です．


I have implemented an interactive fluid simulator by using the method
which I'll make a presentation at this SIGGRAPH's poster program.
The left image is the result of the previous semi-lagrangian method,
and the right image is the result of the method to be presented.

This fluid calculation does not include diffusion term and
viscosity term. In this calculation, both the density field and the
velocity field should not be blurred during calculation. However,
numerical diffusion caused by previous semi-lagrangian method
incorrectly blurs the advected fields, so the error filters out the
small scale details of the fluid. Numerical diffusion also causes
mass dissipation at simulations of water.

The new method largely reduces numerical diffusion, so it can
calculate more detailed fluid motion and appearance.
I think actually running the interactive demo is straightforward
way to understand the impact of the method.
The above image is not so good :-<

You need a GPU that supports floating-point textures and
shader version 2.0 or higher to execute the demo.

（画像クリックでダウンロード）

SIGGRAPH2005のPosterの手法は，GPUでも容易に実装できるはずなので，
その前準備としてGPUを使った流体シミュレータを作ってみました．
ナビエストークス方程式の全ての計算がGPU上で行われています．
512^2でもリアルタイムインタラクティブに動くとは…GPU恐るべし．

上記のソフトウェアでは，マウスの左ボタンを押しながらドラッグすると，
密度とマウスの速度に応じた力とが流体に加わります．
F1キーを押すと密度，F2キーを押すと速度の絶対値（赤がx方向，緑がy方向），
F3キーを押すと圧力の絶対値が表示されます．

Pixel Shader 2.0に対応していて，浮動小数点数テクスチャがDirectXで
使えるGPUならば動作すると思います．Radeon9700Proでは動作しました．

次はPosterの手法を実装しなければ…
ちなみにCPUではもちろん出来ていますので，そのうちデモとして公開します．

Importance Resampling for Global Illumination

なにやら簡単そうだったので寝る前にちょっとコーディングしてみました．
といっても，単純なテストでCos減衰に沿ったサンプリング
（Geometry項）をpによるサンプリングとして，
gではHDRIの環境マップの値を考慮するという簡単なものです．

つまり，単なるpによるサンプリングでは環境マップはuniformに
サンプリングされますが，importance resamplingでは
環境マップをimportance samplingしなくても，
それと同様の効果が出る事になります．
というわけで，とりあえず実験したのが以下の画像です．


（リンク先に元画像）

タイトルの数値が処理時間[ms]で，中央がRISの結果です．
左の画像はRISとほぼ同じ処理時間になるようにサンプル数を調整した結果です．
RISは1ピクセル16サンプルで，左の通常のサンプリングでは38サンプルです．
右の画像は通常のサンプリングによる256サンプルのリファレンス画像です．
ちなみに，RISではM=16, N=16と適当に決めているので，
この論文の主旨とは若干違うかもしれません．

見た目ではっきりわかるように，RISはたった16サンプルでも
リファレンスに近い画像が得られていますし，処理時間もリファレンスと
比較して 1/7程度です．うーん，なるほど…

(追加)


RISでM=16, N=256（つまり256サンプル）で計算してみました．
M=16なので計算時間は16倍かというとそうではなくて，
gには評価が楽なものを使う（この場合visibilityなしでの評価）ので，
僕の実装では3倍程度に抑えられているのがわかります．
（256サンプルの上記のリファレンスと比較した場合）

まだノイジーじゃないか，と思われるかもしれませんが，重要なのは
「環境マップのimportance samplingを全く行っていない」
という点です．なかなか面白いです．

ply2mqo2.zip

講義がつまらないので，講義中に以前に公開していたply2mqoを
ここのplyフォーマットに対応させました．使い方は，

ply2mqo plyfile.ply

でplyfile.mqoが生成されます．
tristripsじゃないbinary（big/little）については気が向いたら．

# 変換できないファイルもあります．

"Combined Lagrangian-Eulerian Approach for Accurate Advection"
Toshiya Hachisuka
ACM SIGGRAPH 2005 Posters, Los Angeles, August 2005.
[Abstract(PDF)]


(left:previous method, right:proposed method)

< Abstract >
In this poster, we propose a new algorithm to accurately calculate
advection equations. Even the latest fluid simulations have been
suffering from the numerical errors in advection equations.
These numerical errors cause mass dissipation and motion damping of
fluid, as a result, the detail of fluid animation is filtered out.
Unlike some previous methods, the proposed method can deal with not
only fields with sharp boundaries but also blurry fields (i.e.no boundaries)
very accurately. Calculating the advection of blurry fields is important
because many physical quantities have blurry distributions.
The proposed method mainly consists of the advection
phase and the non-advection phase. In the advection phase, the method
calculates the current field from the initial field by using the combined
method of lagrangian method and eulerian method. In the non-advection
phase, influences of non-advection terms are added back to the initial
field by using the mapping functions of advection equations.
The proposed method can calculate highly detailed fluid animation using
a relatively coarse grid.

このポスターでは，移流方程式を精度良く解く新たなアルゴリズムを提案します．
最新の流体シミュレーションであっても，移流方程式での誤差から悪影響を
受けています．この誤差は質量の損失や動きの減衰を引き起こすため，
結果として，流体アニメーションのディテールが失われる事になります．
提案手法はいくつかの従来の方法とは違って，明確な境界だけでなく，
境界を持たないような値の場も非常に精度よく扱うことが出来ます．
多くの物理量はそのような境界をもたない場であるため，
それらの移流の計算は重要です．提案手法は，主に移流段階と
非移流段階とから構成されています．移流段階では，
オイラー的な見方とラグランジュ的な見方を組み合わせた方法によって，
初期値の場から現在の移流後の場を計算することを行います．
非移流段階では，移流方程式の写像関数を用いることで，
非移流項の影響を，初期値の場に時間をさかのぼって加算します．
提案手法では，比較的粗いグリッドを用いて，非常に高精細な
流体アニメーションを計算することが出来ます．

もしかしたら（個人的な都合で）今年度が最後の機会に
なるかもしれないと思って，IPA X 2005で再びParthenonを展示する事にしました．

5/18は無人（それどころか何もない可能性が）ですが，
19, 20は終日居る予定です．たぶん，暇を持て余して
現地コーディングしていると思いますので，見かけたら話しかけてやってください．

日程としては，例によってビジネスシヨウと併設なので，
一般公開日の20日に来ると色々面白いかもしれません．

東京ビッグサイトで僕と握手！

# これも勉強のために英語でも書こうと思ったけど，意味無いので中止

突然ですが，以前にrend-algoでちょっと言っていた
Ray Classificationを使ったGPU ray-tracingについて説明を書こうと思います．

Web上にはどうも同じようなネタが無いようなので，車輪の再発明(?)を
防ぐためにも，とりあえず方法だけでも説明しておこうと考えました．
なお，多くの人に知ってもらうため，英語・日本語ハイブリッドで
書いていきます（ただ，面倒になったらやめるかも…）．
ツッコミ大歓迎なので，何かあればBBSにどうぞ．

１．GPU上でのray-tracing
皆さんもご存知のように，もはやGPU上でray-tracingを行う事は，珍しい事では
無くなりつつあります．ところが，その実装には多くの困難な問題があります．
その一つが，交点計算を高速化させるためのデータ構造（空間分割）の実現です．

最近の商用レンダラーなどで，CPU上でray-tracingを実装する時には，
BSP-treeやkD-treeなどの木構造を用いて，空間を分割する方法が
一般的です．しかし木構造は，スタックの無いGPUでの実装は，決して
不可能ではありませんが，困難であると考えられています．

このような背景により，GPU上でray-tracingを行う場合には，
Uniform gridを使った空間分割が主流になっています[Purcell2002]．
Uniform gridでは，空間は均一なボクセルに分割されていて，
レイと交差するボクセルについて，そのボクセルに含まれるポリゴンのみと
交点計算を行う事で，高速にレイと三角形の交点計算を行います．
この場合，各レイについて現在の状態のみを保持すればよいので，
スタックは必要ありません．

確かに，このようにしてGPUにより適した形で，ray-tracingを行う事が
可能ですが，どちらの（tree, grid）方法でもトラバース処理（レイが空間を辿る処理）が
必要になります．実はこのトラバース処理というのは，レイと三角形の
交点計算よりも，一般に計算コストが高い処理で[Wald2001]，
特に，GPU上でのトラバース処理というのは，GPUではレイと三角形の
交点計算が非常に高速に行えるだけに[Nathan2002]，ボトルネックとなりがちで，
トラバース処理の高速化は重要な課題です．

ところがなんと，今回使用するRay Classificationは，トラバース処理が
そもそも必要ありません．Ray Classificationには様々な特徴がありますが，
もっとも特徴的なのは，あるレイに対して，（レイの方向と原点の位置を用いた）
五次元空間上でのデータを得る事で，レイと交差する三角形のリストを
即座に得る事が出来る点です．
この特性により，トラバース処理を行うことなく，ray-tracingを高速化できます．
さらにその実装は，これらから示すように実はGPUに非常に適しているのです．
次回は，GPUでの実装に入る前に，Ray Classificationの概要を説明します．

It's a little sudden, but I'll write the article about Ray Classification for
GPU ray-tracing, which I stated very briefly at rend-alog ML.

I didn't find any article about this topic, so I write the article to prevent
reinvention of the wheel though I haven't implemented the algorithm yet.
In passing, this article is written in both English and Japanese to let
many people know the algorithm (as far as I don't feel it's a pain...).
Any comments on the article are always welcome.
Please write your comments on the BBS.

１．Ray-tracing on GPU
As you know, implementing ray-tracing on GPU is getting more and
more usual in these days. However, its implementation still contains
many practical problems. One of the problems is implementation of
the acceleration structures for reducing the intersection calculations.

Recent CPU based commercial renderers usually use tree data
structures, such as BSP-tree or kD-tree. These tree-type acceleration
structures can be implemented on GPU somehow, but they simply
aren't suitable for GPU because GPU doesn't have stack architecture.

For this reason, a uniform grid is the primary data structure for
GPU ray-tracing now [Purcell2002]. By using a uniform grid, the bounding
box of a scene is subdivided into small voxels, and then ray-triangle
intersections are performed only for the triangles in the voxels
which are intersected by the ray. In this case stack architecture
is not necessary because the algorithm only uses current states of each ray.

Both of acceleration structures can be certainly implemented on
GPU, but they have a ray-traversal process phase, which is actually
more costly than ray-intersection process phase in general [Wald2001].
This process often become a bottleneck for GPU ray-tracing
because ray-triangle intersections can be calculated very efficiently
on GPU [Nathan2002]. That is, the efficient implementation for
traversal processes is important for fast ray-tracing on GPU.

Ray Classification, which this article utilizes, is one of the algorithm
that doesn't need to perform traversal process!
There are many features in Ray Classification, but the key feature is
that lists of intersection candidate triangles can be promptly
obtained by querying a 5D subdivided space with the parameters of rays
(the position of the origin and the ray direction). This feature makes
the algorithm possible to accelerate ray-tracing without traversal processes.
Moreover, its implementation is actually very suitable for GPU as I'll explain.
In the next article, I'll give you the overview of Ray Classification before
starting to implement it on GPU.

ぬおお，スゴク面倒だ．既にくじけそう．:-<
GAA, it's already painful. I'm feeling myself weakening. :-<

今更ながら，ソフトウェアラスタライザを書いています．
せっかくだから俺はこの赤い扉…じゃなくて，
エッジ関数を基本としたラスタライザにしようかと思ってます．
そんなものがCPU上でまともな速度で動くのか
正直少し不安ですが，まあ面白いので良しとします．

ところで，よく，「GPU Gems 2の記事を書いてから何かありましたか？」
と聞かれるのですが，これが実は何もないのです．

記事についてのメールは来ますけど，特に分量には
（記事を書く前と後とで）変化が無いので，本当に何もありません．
自己満足も，自分の書いた記事はもう読み返したく
ないので，全くありません．

と思いましたが一つありました．
学校の単位に少しだけ振り替えてもらえました．
そう，本当に少しだけ…

今学期は，これまで忙しかった分，講義に時間的余裕があるので，
また学校が忙しくなる前に，少し腰をすえて「自分プロジェクト」を
やりたいところです．

もちろん，今やっている事は継続するのは前提で，
何か新しいことがしたいなぁと思うわけです．

うーん，何がいいかなぁ…

やっと，ここ4ヶ月ぐらい関わっていたある事が＊とりあえず＊終わりました．
正直もうだめかと思いましたが，終わってみると
何だかんだで少し自分がパワーアップした感じがします．

何をやったかはしばらく秘密ということで．
（知っている人は黙っていてくださいね）

まあ，何かが終わったといっても，今までそのせいで止まっていた事が
再開するので，自分への負荷量はあまり変わらないのですけど…

ところで，やらなければいけない事が多いと，
どうも自分の趣味は優先順位が低くなりがちじゃないでしょうか．
誰かが言っていましたが，もしその趣味が自分にとって重要なら，
やらなければならない事よりも，優先順位を高くしたっていいのです．
というか，僕はそうしますのでよろしくお願いします＞誰か

やらなければならない事も，そうでない事も，
全てはいい意味で自分のためなのですから．

さー，論文読むぞー．

世の中にはポエムを作り続ける人達がいる．

彼らは，自分達が作ったポエムを持ち寄り，
「そのポエムの雰囲気が良いね」とか「この言葉を変えたらもっと良いポエムになるよ」
とお互いに言い合っている．

それだけなら別に何の問題もない．
しかし，彼らはそのポエムを外部の人に無理やり読ませては，
「このポエムは（私達の中で）高い評価を受けたポエムです」
と言って認めさせようとするから，迷惑に思う人もいる．

そもそも彼らは，外部に受け入れられるポエムを作りたがっているようには見えない．
なぜなら，彼らは「本当に良いポエムとは何か」を，知ろうとすらしないからだ．
例えば，彼らに「どうしてポエムのなかでその言葉を使ったのか」と尋ねると，
「私が良いと思ったからです」
と平気で答える．そこに真の意味での理想を追求する姿勢は見られない．

彼らに言わせれば，それをしない理由は，
「本当に良いポエムなんて無い．人によって評価は違う．
だからそんなものを追求するのは無意味だ．」
という事のようだ．

でもそれは，真実だろうか？
それは単に，良いものとは何かを考えるのを停止しているように見える．
仮にそれが真実だとしても，「人によって評価は違う」ポエムを
多くの人に無理やり認めさせようとするのは，いかがなものか？
自己表現の場にしたいなら，他人に認めさせる必要は無いはずだ．

もちろん，彼らの中には，時々外部の人にも
受け入れられるようなポエムを作る人も居る．
だけど，彼らはそれが何故受け入れられたのか，考えない．
そして，仮に考えて何かがわかったとしても，それは他人には教えない．

そうして，彼らは，今日もポエムを作り続けている…

誰も止めないので延々と妄想

自然言語処理とGIは…



と思ったのですが，もうちょっと勉強してから書きます．

ちなみに，今まで書いた事は「数値流体力学からCG」ですが，
「CGから数値流体力学」という方向でも，個人的に面白い事が
いろいろとありました（単なる「物理シミュレーション+CG」じゃないですよ！）

僕は割とCGばっかり勉強して（というか遊んで）きたせいか，
「CG脳」になってしまったようで，他の分野の考え方の違いに戸惑う事があります．
たぶん，CGで遊んでる時は，脳波が全く出てないと思います…嘘です．

でもそれを利用して，勉強した事をCGという分野にむりやり持ってくると，
時々（ほんとうに時々）面白い事がわかったり，意外な共通性が見えたりします．

「もっと色々な分野を学ぶと，もっと面白い事が見つかるかもしれない…」
そう思うと，凄くわくわくします．勉強する事は本当に沢山ありますね．

全く関係ありませんが，エイプリルフールに嘘をついた人は，直後に嘘って
言わなければ，いけないと思います！やめて下さい！ （c)学級会

EulerianとLagrangianからさらに妄想

GI(Global Illumination)の計算では、例えばソフトシャドウを実現したい時は
シャドウレイを沢山飛ばすとか、Importance Samplingがいいらしいよとか、
関係する要素技術は非常に多岐にわたるわけですが、
その実態は何かというと、レンダリング方程式を解いているだけです。
(そうじゃない場合もありますが…）

レンダリング方程式がどんなものかはGoogle大先生に講義していただくとして、
実態が見えたことで、一つの疑問が浮かぶと思います。
それは、「今の計算方法（レイを沢山飛ばす、モンテカルロ法、ラジオシティ）」
って本当にこの形の方程式にとって最適な方法なのか？という事です。

レンダリング方程式とは、極論を言えば単なる積分方程式です。
例えばみなさんは、ある関数の積分を数値計算する時に、
レイを飛ばすとかそんな事は考えませんよね？

だから、その部分はCGに特有の積分方程式（ここではレンダリング方程式）の
解き方だと捉えることが出来ると思います。
モンテカルロ法にしたって、積分を計算する一手法に過ぎないわけで、
そこに色々くっついて今のデファクトスタンダードなアルゴリズムがあるわけです。

もちろん、レンダリング方程式中のある項はレイを飛ばすなどによって
得られる項ですし、モンテカルロ法が適している形の方程式であるのは理解できます。

しかし、みんながみんな、レイトレーシングだパストレーシングだフォトンマッピングだ
MLT（Metropolis Light Transport）だなんて揃って言っていると、
へそ曲がりな僕は、
「もうちょっと違う方向からアプローチしてやるッ」
とか思ったり思わなかったりするのです。

例えば最近の例だと（レンダリング方程式とはあまり関係ありませんが）、
Lattice-Boltzman Lighting
なんかは、僕も似た手法を考えていて、あーやられたなぁという感じでした。
たぶん同じことを考えている人は沢山居て、同じように
あーやられたなぁと思ったんじゃないでしょうか。

もうレンダリング技術は完成されたのでやる事が無いなんて
思っている人も居るかもしれませんが、まだまだ沢山の
「あーやられたなぁ」なネタが残っていると、僕は思います。たぶん。

色々大変に。悩み多き年頃(?)なのです。



流体力学などではLagrangianとEulerianという二つの見方があります。
大雑把に言えば、Lagrangianとは流れにのった座標系で考えるもので、
Eulerianとは固定された座標系で考えるものです。
具体的にはLagrangianはパーティクル、Eulerianはグリッドに対応すると
考えるとわかりやすいかもしれません。
（実際にはそうでない場合もありますし、この組み合わせである必然性もありませんけど…）

例えば、煙の動きを計算したいといった場合、
よく使われるようにパーティクルで表現する場合はLagrangianで、
Jos StamのStable Fluidsのように、グリッドを使う場合は
Eulerianであると見ることが出来ます。

このような視点からレンダリング手法を分類すると、
パストレーシングはある意味で光にのって光を追跡しているわけですから、
Lagrangianであると言えないでしょうか。
また、Radiosityはパッチという固定された面でエネルギーのやり取りを行っているので、
Eulerianであると言う事が出来ると思います。

これを踏まえると、現在の大域照明アルゴリズムはLagrangianなものに
偏っていると考える事が出来ます。細かい議論はしませんが、
一般にLagrangianな方法は複雑な計算条件に適用させやすく、
多次元化が容易であるという特徴があるのですが、計算点の分布にばらつきが出る事や、
計算結果にノイズが発生するといった欠点があります。

これらは正に、今の大域照明アルゴリズムが抱えている問題点と一致している事がわかります。
つまり、計算点の分布にばらつきが出るというのは、サンプリングが難しいパスが存在するという事
計算結果にノイズが発生するというのは、画像にノイズが発生するという事に対応しています。

これらの欠点が無いEulerianな手法は、いくつかの枝葉はあるものの、
Radiosityから発展が止まっているように見受けられます。
こんなに長々と書いておいて、つまり何が言いたいのかというと
もしEulerianな大域照明アルゴリズムが思いつけば、
新たなレンダリング手法の研究領域が
開拓できるかもしれない、と妄想中だという事です。

# ツッコミ希望

10時間寝ないと調子が悪い僕が、連日睡眠を3時間程度しかとれないほど忙しいんですが、
Articleに良さそうな内容を思いついたのでタイトルだけ…
本サイトの名のとおり、暇が出来たら書きます。

あ、皆さん本年もよろしくお付き合いください。今年も死なない程度にがんばります。

あまり更新しないのも何なので…

新しいGIレンダラーという事で何かと話題のMaxwell Renderですが、このレンダラーの大きな特徴は
"Unbiased Renderer"と"Spectral Calculus"の二つだと思います。

まずunbiasedなレンダリングとは何かというと、計算を行う前に定めたパラメータに
違いがあっても、最終的に正しい結果を出力するレンダリングの事です。unbiasedなレンダリング
アルゴリズムの代表例はPath-tracingです。これに対して、biasedなレンダリングでは
パラメータが違うと結果も変わります。現在最も普及しているGIの手法であるPhoton Mappingは
biasedなレンダリングアルゴリズムです。

biasedなアルゴリズムであるPhoton Mappingは、事前に定めるフォトンの数を変えると
同じシーンでもレンダリングの結果が変わります。ここで気が付いたかもしれませんが、
unbiasedなアルゴリズムであるPath-tracingでも、サンプリング数の違いで計算結果が変わります。
そのため、より広義には、サンプリング数さえ上げれば正しい結果が出るものがunbiasedな
レンダリングアルゴリズムであるという事のようです。

なぜ必ずしも正しい結果を出さないbiasedなPhoton Mappingが普及しているかと
いうと、biasedなレンダリングではエラー（ノイズなど）もbiasedになるからです。
つまり計算時間を大してかけなくても、十分に許容できる範囲のエラーでの
レンダリング結果を得られる可能性が高いということです。
この事は、フォトンの数が十分でないPhoton Mapを直接可視化すると
高周波な成分（鋭い影）が表現できないものの、それと同時にPath-tracingなどで
顕著に現れる高周波なピクセルごとのノイズは現れない事からも実感できます。

一方で、unbiasedなレンダリングではエラーがパラメータによって制限されないので、
エラーを減らすには単純にサンプリング数を上げるしかないということになります。
（だから"Very Few Paramters to Control the Render"なのでしょう）
どちらのアプローチがいいかは用途によると思いますが、
もし新しい手法を開発したのでなければ、unbiasedなレンダリングは非常に
計算時間がかかるので、レンダリング時間は他のGIレンダラーよりも長いでしょう。

次に"Spectral Calculus"ですが、これは光の周波数を考慮した計算を行うという事です。
多くのレンダラーはRGBでこれを代替していますが、これはある意味では周波数を3サンプルで
計算している事に等しくなります。実際の現象では、各周波数で相互に影響が出るような
場合があるので（例えば蛍光色では紫外領域の入射光が可視光になって反射しています）、
このような現象では周波数を考慮した（つまり多サンプルで周波数を表した）方が
容易に計算することが出来ます。あとは、プリズムによって分光される現象のような、
周波数に依存した光学現象でも違いが出る事が期待されます。

しかしながら、これも計算量としては増える事になりますし、もし何の工夫もしなければ
マテリアルの設定がかなり複雑になります。あと個人的にはスペクトル計算によって
計算量が増加しても再現したいような現象はあまり多くないと思うので、
通常の使用には少しoverkillな気もします。

何にせよ今までのGIレンダラーとは少し毛色が違ったものになりそうなので、
今からリリースが楽しみです。（これでフルCG映画作ったら凄そうだ…）

8.16.04

というわけでGP2とSIGGRAPH2004に行ってきました。
個人的な感想をメモ程度に書いていこうと思います。
勘違いなどが多々あると思いますので流し読みしてください。
（会場内撮影禁止だったので貧弱なメモですけど…）

＜8.7＞
お昼過ぎにLAX（ロサンゼルス国際空港）に到着。
この日はSIGGRAPH開催日前日で、普通は単にレジストレーションを行うだけで終わります。
しかし今回僕はGP2にも参加したので、レジストレーションは行わずにGP2が行われている
Wilshire Grand Hotelに直行しました。会場に到着したのは、Mark Seager氏の
"GPU Requirements for Large Scale Scientific Applications"がほぼ終わる頃でした。
実は正直に言うと、僕は公演にはあまり興味がありませんでした。というのも、公演の殆どが
「このような目的を考えるとGPUには何々が足りない」といった趣旨だったからです。
（実際そういう内容でしたし）これはGPUを作る側にとっては参考になる話かもしれませんが、
GP2でポスター発表している人たちやGP2に参加している人たちの殆どは使う側であって、
それぞれに「GPUにはこれが足りない」という考えを持っているので、公演者が考える
「足りないもの」を聞いたところで何に参考になるのか疑問が残ります。

そんな中でも一応参考になりそうな考え方はありました。（これは8.8日の公演だったと思いますが）
「GPUはStreaming Processorとは言えない」という考え方です。現状のGPUは
CPUとは違うアーキテクチャであるものの、Streaming Processorと呼ぶにはまだまだ
機能が足りないという、言ってしまえば中途半端な位置にあります。
したがって、単にStreaming Processor上でのアルゴリズムをGPU上で実装しても
あまり効率的ではないという事は言えると思います。例えば現状のGPUに足りない最も代表的な
処理としては、任意の位置に結果を書き込むScatterがあります。
これは頂点シェーダ上でのテクスチャフェッチを使えば間接的に実装可能ですが、
一度テクスチャのフェッチが入る上に（フラグメントシェーダより）遅い頂点シェーダ上での処理が
入るので、Streaming Processor上でのそれとは性質が違う事が予想されます。
GPUでは何が効率的に行えるのか、を常に考えながらアルゴリズムを研究していく
必要があるだろうなと実感しました。

まあ色々思うところはあったものの、僕は公演よりもポスター発表を楽しみにしていました。
この日のポスター発表は午前もあったのですが、到着が午後だったので午後から見ました。
まずはじめに面白いと思ったのは、William Baxter氏らによる"Simulation and Rendering
of Viscous Fluid Paint on GPUs"です。詳しい説明はWeb上で見られるので省きますが、
デモムービーではかなりリアリスティックな描画が可能になっているのが見られました。
シミュレーションの具体的な内容を聞いてみたところ、自由表面流れは
解いていないとの回答が返ってきました。絵の具の流れは空気の流れを無視できるので、
キャンバスの凹凸を固定境界に持つ自由表面流れになるはずです。自由表面流れを解かなければ
例えば水をはじくキャンバスで水滴になるといった表面張力に関わる現象が
再現できないと思われます。自由表面流れをGPU上で解くのはまだ難しいのでしょう。

次に興味を持ったのがIan Buck氏らによる"GPUBench: Evaluating GPU Performance
for Numerical and Scientifc Applications"です。GPUのベンチマークソフトは割と沢山ありますが、
これはGeneral Purposeな計算のためのベンチマークを目的としたものです。
このポスターの周りには人が結構集まっていて、僕は質問は出来なかったのですが、他の人の
Radeon系とGeForce系でReadback（GPUからCPU）の速度が大幅に違うのは何故かという
質問の中で、ベンチマークにはOpenGLを使っているという話が出てきました。
発表者も言っていましたが、これではOpenGLへのドライバの最適化の度合いによって
ベンチマーク結果に差が出てしまう事になります。シェーダーを使えるのはOpenGLだけでなく
DirectXもあるわけですから、このベンチマークによる結果が果たしてどれほど
実用的なものなのか、僕には疑問が残りました。（しかし、このポスターが後に大変な事に…）

他にも色々と面白そうなポスターがありましたが、どのポスターでも積極的に議論がされていて、
割り込む余地が無いほどでした。申し込み人数の多さに、人数が制限された事を考えると
GPGPUに対して強く興味を持っている人は多いと言えるのではないでしょうか。

この日はレセプションがあって参加者がテーブルを囲んで食事をしながら話をする事が出来ました。
僕と同じテーブルにはTim Purcell氏やMichael D. McCool氏が同席していましたが、
お二人とも同僚との会話に夢中で割り込みづらかったので、Michael D. McCool氏と
一緒に来ていたUniversity of Waterlooの学生二人と話してました。Michael D. McCool氏は
ShというGPU上でのプログラム言語の開発に関わっていて、彼ら（学生）もShに関わる
応用研究などを行っているようです。（後に再認識させられますが）組織的に研究しているところには
やはり個人では超える事の出来ない壁があるなと思いました。

ところで会場内は既にSIGGRAPHでも無いのに空調で寒かったのですが、
どういうわけか「暑い」といった輩がいたらしく、翌日からはさらに寒い部屋に移動する事に。
「感覚が違いすぎる…」と軽いめまいを覚えながら宿泊先のホテルに戻るのでした。

（続く　と思ったが続かなかった）

8.6.04

僕のキューに次々と割り込みでタスクが入ってくるので、優先順位の低いWebの更新
（というか他のものが相対的に高いのです）はどうしても後回しになってしまいます…

さて、BBSの方で書き込みがありましたがRTSSSとParthenonがGeForce6800で
動作するようになりました。依然としてNV30系では動作しませんが、やっとATI以外の
ビデオカードでも動作するようになったので、動作環境がある方は試してみてください。

それとParthenonのページにデモムービーを追加しておきました。
動作するビデオカードをお持ちで無い方も、どんな感じにレンダリングされるのかを
ムービーで確認する事が出来ます。ちなみに実時間でのキャプチャーです。

近日中にPublicationを公開予定なので興味のあるかたはしばらくお待ちください。

5.23.04

Subsurface Scattering Happy Buddha

左上：Skin1
左下：Potato
右上：Apple
右下：Skimmilk

さて、これからどうしようかな。

5.18.04

や、やる事が多すぎる…
落葉中の木の下で落ち葉をかき集めている気分です。

そういえば、最近新しいデモを公開していません。（個人的に）よくない傾向ですね。
なるべくオリジナルなものを作ろうと思っているからかもしれませんが、
論文を読んで実装して理解するというパターンは僕にとって重要なので
もっとプログラムを沢山作っていきたいです。

慣れてくれば論文を読むだけで深く理解できるのかもしれませんが、
実装しないと見えてこない利点や欠点などは多々あるものです。
それに実装したものをちゃんとした形で溜め込んでいけば、
新たな手法を考える時のテストベッドとして使えます。

やはり、理論と実践のどちらが欠けていても駄目なのです。

4.20.04

ParthenonのIBLの場合に極端に間接照明が明るくなってしまうバグを直しました。
あと現在、任意サイズの画像を計算するときの初期化にバグがあるらしく、
環境によってはサイズを大きく出来ない場合があるようです。

SoftwareにReal-time SSSをとりあえず追加しておきました。
nVidiaのパクリかと思われそうなのが微妙に悔しいですが、世の中そんなものでしょう。

Photon MappingとIBLの関係について書こうと思いましたが、
自分の中でまだ整理できてないので保留します。
Webで検索しても、誰も同じようなことを考えていない様子です。何故でしょうか…

4.19.04

NVIDIA社のGPUオフラインレンダラー、Gelatoが発表されました。（情報元：spin）
僕の予想に反して、現在のCPUネイティブなレンダラーとほぼ変わらない品質の
レンダリングが可能なようです。GPUがどのように使われているかについては、
"floating-point supercomputer on a chip"と書かれているだけなので、
何か新しくアルゴリズムを用意したわけではなく、単純にGPUを演算器として使っているようです。
そういう使い方でどの程度パフォーマンスが出るのか少し疑問なのですが、
実際のところはものを見てみないと何とも言えません。
もし驚くべきパフォーマンスが出ているとするなら、今までのGPUを使った研究は
ほとんど意味のないものになってしまいますけど…

あと、これまた僕の予想に反してわりとオープンな形で提供されるようです。
さらに評価版のダウンロードもそのうち可能になるようです。

まあ実際のところ、NVIDIA社には過去の功罪がいくつもあるので、
物が出るまでしばらくは生暖かい目で見守りましょう。

4.18.04

今気がついたんですけど、これって日記と言うか毎日コラムを
書いているだけのような気がします。
（その日起こった出来事とあまり関連なし、考えた事とは関連あります）

こんな状態では長くは続かないように思われるのですが、
具体的なネタが決まれば比較的書きやすかったりもします。
あと、文章にすることで自分の中でまとめることが出来るというのもあるかもしれません。
しかし、時間をかけて書いたものを検証をするわけでもなく、自分の中にあるものを
ただただ書き連ねているだけなので、コラムというにはおこがましく
やはり単なる日記と言った方が正しそうです。

まあこういう形もありかなと思うのですが、どうでしょうか？

4.17.04

GeForce6800ことNV40が発表されました。新たに追加された機能のなかでも
僕は特にvertex programからのテクスチャフェッチに注目しています。

ここ数年で、GPUを様々な計算に使うために、GPUをStreaming Processorとして捉える
考え方が出てきました。この考え方により、従来Streaming Processor用に研究されてきた
アルゴリズムが適用できるようになりますし、より高い視点からGPUの利用を
考えることが出来ます。ところが、様々な論文で言及されている問題の一つにGPUは
Scatterが出来ない（正確には出来るがCPUを通す必要がある）という事が挙げられます。

ScatterとはStreaming Processorのstream（データ）に対する基本的なOperationの一つで、
任意の位置に書き込む処理のことをいいます。
もう一つの基本的なOperationの一つにGatherというものがあり、
これは任意の位置から読み込む処理のことをいいます。
どちらの場合も複数の位置において書き込み・読み込みをする場合がほとんどです。

Streaming ProcessorとしてGPUを使う場合は、streamをテクスチャ、
kernel（プログラム）をfragment programとして扱うのですが、
上の二つの処理のうち、Gatherはfragment programにおける
依存テクスチャフェッチ（という呼び方はもはや古いかも）として既に実装されていました。
しかしながら、Scatterだけはfragment programで任意の位置に書き込むことが
出来ないため単純に実装することは出来ません。
そこで考えるのがvertex programで書き込む位置を変えてやるという方法ですが、
streamをkernelに通し、その結果をまたstreamとしてkernelに通すという
一連の動作を実装するため、fragment programの結果を何らかの形で
vertex programに渡さなければなりません。これは今までのGPUでは
出来なかった（もしくは限定的にしか出来なかった）のです。

回りくどくなりましたが実はこのfragment programからvertex programへ
データを渡す事が、vertex programからのテクスチャフェッチによって実現できるのです。
Scatterが実装できれば、今まで出来なかったことやパフォーマンスが落ちていた事などが
大幅に改善されます。GPUによるGeneral Purpose Computationの世界が
また一つ広がったと言えますね。まあ、それがいいものかどうかは別として…

# Parthenonの同類(?)としてNVIDIA Digital Film GroupのGelatoが気になります。

4.16.04

最近僕が注目をしているデータ構造にSuffix Arrayというものがあります。参考リンク（DO++）
僕はまだ詳しく勉強したわけではないので（聞きかじった程度）、一言でこういう物だ！とは
説明出来ないのですが、話を聞く限りではなかなか面白いことになっています。
その特徴としては、参考リンクにあるとおり、大規模データに対する情報の検索・抽出が
従来のデータ構造と比較してかなり高速にできるということです。
一度まじめに勉強する価値は十分にありそうです。もっとも、今は物凄い勢いで
発展しているらしいので、勉強すると抜けられなくなりそうですが：P

ここで考えるのはやはりCGへの応用なのですが、最近のCGでは
Precomputed Radiance Transferに代表されるように従来よりも高次の計算結果を
扱うことが多いので、データ量も規模が大きくなりつつあります。
Suffix Arrayは上の概念のデータ構造なので（具体的なデータに対するデータ構造ではない）、
ちょっと考えるだけでもCGに限らず活用できる部分は沢山あると思います。
研究としてのCGの分野は、客観的に見ればほぼ成熟しつつある分野でしょうから、
他の分野を一度勉強してからまた戻ってくるというのは
新たな概念を考える際の有効な手段になるのではないでしょうか。

4.15.04

ParthenonはGPUをGIレンダラーに使うという点で新しい要素を含んでいるつもりですが、
最近、あるきっかけでParthenonとは違った新しい要素を含むレンダラーを思いつきました。
詳しいことは妄想レベルなのでまだ言えませんが、商用レンダラーでもまだ実装しているものは
ないと思われます。というか商用では実現が事実上難しいレンダラーだと思います。
実際に作って公開に至るかどうかは不明ですが、僕がやらなくても誰かやりそうです。
ちなみにヒントは「協力」です。

ところで、商用で実現が難しいという点ではGPUを使ったレンダラーもその範疇に
入るのではないでしょうか。まず使用には当然ですがビデオカードが必要なので、
もしParthenonのようにビデオカードを使った処理しか出来ないレンダラーだと
使えるユーザーが限られてしまいます。ビデオカードも一緒に導入するようになれば
問題ないのですが、現状でGPUレンダラーにそこまでの価値があるかと言えば微妙でしょう。
何よりビデオカードやその周辺技術はまだまだ発展途上にあるので、
レンダラーを作っている会社がGPUレンダラーに十分な商品価値を
見出せるようになるのは、もう少し先の話なのではないかなと思ったりもします。
もしくはそういう事は永遠にありえないのかもしれませんが…

4.14.04

前からずっとやってみたいと思っていることの一つに、破壊のシミュレーションがあります。
CGの世界で破壊のシミュレーションといえばJames F. O'Brien氏やMatthias Muller氏が有名です。
破壊現象のシミュレーションでは、剛体や流体のシミュレーションとは違って物体のミクロな構造が
現象に大きな影響を及ぼすのが特徴です。例えばひびが形成されるというマクロな現象に、
物質の不均一さというミクロな性質が大きく影響します。
また、破壊はある特定の状況についてはよく定式化されていることが多いものの、
例え日常目にするような範囲であっても、統合的に使えるような式が存在しないようです。
さらに物体が高速に衝突した場合、物体表面を伝わる波によって衝突点とは違う場所から
破壊が起こることもあるため、数値解析的に難しい現象であるともいえます。

なぜ、剛体や流体などの他の力学シミュレーションと違って定式化がされてないかといえば
CGにとって重要なシチュエーション（コップを床に落としたときにどのように割れるかなど）と
破壊現象の工学的に重要なシチュエーション（飛行機の翼はどの程度の応力でひびが入るか）が
違うためではないでしょうか。現状で唯一の有効な方法は、あらかじめそれらしい形の破片群に
モデルを割っておいて、破壊を引き起こす衝突をした後にそれぞれの破片を剛体として
動きのシミュレーションをするという方法でしょう。
しかしこの方法では、もし壊れ始めるところを変えたくなったりするとまた一から破片を作り直す
必要がありますし、破片の大きさや形状による物体の材質感が表現しづらくなります。
今や剛体や流体、弾性体などのシミュレーションをCGに使うことは当たり前に
なりつつあるので、破壊現象などまだシミュレーションが深く入り込んでいない
分野を研究するのはとてもチャレンジングで面白そうです。

とかなんとか書いてしまいましたが、実際のところ僕はまだよく破壊というものが何なのか
はっきりと理解していません…。前述の理由からなのか、全く参考書が存在しないようで
なかなか勉強が進まないのです。ところが最近、学校である機会を得ることが出来そうなため
しばらくしたら（といっても数ヵ月後でしょう）このページで、破壊のシミュレーターを
なんらかの解説とともに公開することができるかもしれません。 期待しないでお待ちください：D

ちなみにずっとハードディスクにあったParthenonをアップロードしておきました。
前のバージョンよりはずっと使えるものになっているはずです。

4.13.04

今日はプログラミングの講義があったのですが、教官教員の発言に驚きました。
　「数行ごとに（コード中の行の）通し番号を出力するようにすると、デバッグが楽ですよ」
コーディングスタイルは人それぞれでしょうけど、デバッガを使ったほうが良いのでは…
もしそれが癖になって、コンソールにもの凄い数の通し番号をはきまくるプログラムを
書くプログラマが出来たらどうするのでしょうか：<

最近はコースティクス描画のための新しいアルゴリズムを構想しています。
コースティクスは現時点ではフォトンマップでレンダリングすることが多いようですが、
実はまだまだ多くの問題を含んでいます（と、僕は思っています）。

拡散反射による間接照明などは低周波成分が支配的なので、フォトンマップのように
ノイズがフィルタリングによって軽減される手法では十分に再現することが可能です。
実際、フォトンマップの後の段階で使われるファイナルギャザリングは、
拡散反射をする面では、入射してくるラディアンスの低周波成分が
十分に再現されていれば見た目にはほぼ影響が無いということを仮定していて、
（最近のSpherical Harmonics Functionを使った手法はこれが元になっています）
これはフォトンマップの性質（低周波成分が高速に再現できる）と一致しているので
全体として効率的なアルゴリズムになっています。

ところが影はそのように簡単にはいきません。影は物体と光源の関係によっては
照明分布は全ての周波数成分に渡って重要である場合があります。
例えば立方体を平面に置き、面光源を当ててやわらかい影（低周波成分）を作ったとしても、
立方体と平面との接地面でははっきりとした影の境界（高周波成分）も重要になります。
（Waveletを使ったIBLはこの点を踏まえて考え出されました）
このような場合、フォトンマップを直接使っても満足のいく結果は得られません。
フォトンマップのみでレンダリングした画像で、いわゆる「接地感」があまいのはこのためです。
これは一般的にはフォトンマップを直接光のレンダリングには使わないことで回避されます。
つまり、影の部分のみを従来のbrute forceの方法で計算するということです。

コースティクスは現象としては後者（影）にあたります。
それではなぜコースティクスをフォトンマップによって描画するレンダラーが多いのかと言うと、
他の手法（パストレーシングなど）では視覚的に非常に目立つノイズが発生するということと、
コースティクスは多くの場合フォトンが密集する傾向にあるので、
フォトンの密度を計算する際には十分な精度であると思われるからではないでしょうか。
しかしながら、現状ではコースティクスは（他の照明成分に比べて）それほど
正しく計算されているとは言えません。例えば、これはSquareのKilaueaの論文でも
指摘されていましたが、ガラス窓を通過した光は全てコースティクスになるので
車の中などをそのままレンダリングしようとすると、現在主流の方法では
フォトンマップを直接可視化するしかありません。
現状では、これを回避するためにフォトンのトレースの段階では窓を無視するということが
常套手段的に行われています（これで良いかどうかは意見が分かれるかもしれません）。

コースティクスのみに双方向パストレーシングやMetropolis Light Transportを使えば、
パストレーシングよりも遥かにノイズを少なくすることができますが、処理速度の点でみると
フォトンマップに軍配が上がるのでしょう（自分で実験したわけではありません）

そんなわけで色々と考察していて、ある程度良さそうな候補がいくつか出来たのですが、
まだ完全に手法を詰めているわけではありませんし、
実装もしていないので苦悩の日々は続きそうです。
（他に苦悩していることがいくつもあるのに…）

4.12.04

思えばここ一年ぐらいはやる事が沢山あって、ある意味充実した毎日を送っています。
(しかし忙しいとも言えます…）
昨日も書きましたが上のコンテンツは少しずつ作っていこうと思います。
あ、でも諸事情によりParthenonのページは早く作らねばなりませんが。

今日は数値流体力学の研究をしている研究室（なんか変な日本語ですが）に
見学に行きました。粒子法というパーティクルを使った流体計算をメインの
研究テーマにしています。D1の人にちょっとだけ質問してみましたが、
やはりパーティクル自体が計算点となることによる計算誤差や
等値面の構築における任意性が問題となってしまっているようです。

グリッドを使う方法と比べてよい点は、これも前から言われているように
複雑な形状における境界条件の適用が簡単だということですね。
グリッドを使う方法では、境界条件の与え方自体が一つの研究領域に
なっているぐらいですし、何らかの手法を考える必要があります。

質問に答えてくれた人いわく、
　「CIP（グリッドを使った方法）の方がいいような気がする…」
だそうです。そんなこと言わずにもうちょっと粒子法でがんばりましょうよ！

4.11.04

プロバイダに関するトラブルはもうウンザリなので、ドメイン取りました。

デザインを新しくしたはいいものの、これといって内容は変わっていません。
せっかくインターネットを使ってサイトを公開しているわけですから、
なんらかの役に立つ情報を載せた方がいいのでしょうけど。
まあ、時間があればちょっとずつコンテンツを増やしていこうと思います。
（ドメインを取ったことで少しは気合が入るかもしれません）

IFさんのt-potのように解説を載せてみたいという欲求はあるのですが、
僕にはIFさんみたいに継続して書くパワーは無さそうです。
本当にあのような事を出来る人を尊敬します。

ところで、僕はよく以前から
「どうでもいい個人的日記になってしまいそうなので日記は書かない」と
言っていたのですが、やはり後から読み返してみると面白いかも
しれないと思ったので、これからは（できるだけ）日記を書こうと思います。