|
|
|
|
|
||
|
||
髪の毛のレンダリングにおいて前回までの円柱＋球ではなく、カーブとしてレンダリングしてみた。
カーブのレンダリングの手法はRAY TRACING FOR CURVES PRIMITIVEを実装することで解決した。
また、髪の毛の一本一本をカーブとみなすために、点列間をcatmull-romカーブでつなぎそれを動的にベジェカーブに変換する仕組みを入れた。
以上により髪の毛が形状も陰影もなめらかに変異するようになった。
以上では、どこが変わったかわからないので、一部を拡大した画像を置く。
上が前回まで円柱＋球、下が今回のカーブ
速度は前回までの円柱＋球での画像が2400*2400で３０秒程度だったのに対し、今回の手法では約９０秒ほどの速度になった。
自作レンダラにおいて髪の毛のレンダリングに取り掛かっている。
具体的にどうするべきか、実験中であるが、とりあえずここ（HAIR Model Files - Cem Yuksel）からhairモデルを取得して単純なレイトレースにてレンダリングしてみた。
物体形状としては髪の毛一本一本を円柱と球をつなげたものを使った。
シェーディングモデルにはKajiya-Kayの物*1をそのまま使った。
以下は2400*2400でレンダリングして800*800に縮小したもの。
などが挙げられるだろう。
速度に関しては、レイトレーシング、スポットライト１灯、解像度2400*2400でそれぞれ１分程度である。
今後どうするかだが、透明度を考慮して、シェーディング＆影付けすればリアリティが増すものと思われる。
*1：Rendering fur with three dimensional textures
空間構造の一種であるQBVH(Quad-tree Bounding Volume Hierarchy)を実装した。
元の論文はhttp://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.100/institut/Papers/QBVH.pdf
以前syoyoさんがイイヨとおっしゃっていたので実装してみた。
この論文で語られるQBVHの要点は以下。
１．４分木構造
一つ一つのノードがそのAABBを持つのではなくその親が４ついっぺんにもつ
３．SIMDによる判定
４つの子ノードのAABBの交差判定をSIMD演算を利用していっぺんに行う
面情報を格納するノードは実際には作らない。その代わり、ノードの子が枝ノードなのか面なのかをインデクッスの一部をフラグとし格納する。
■実装
普通BVHといえば２分木構造を用いるがQBVHでは４分木構造を用いる。これはSIMD(インテルCPUではSSE)ではfloat*4の演算を一度にすることができるため、４分木であることが最適であるからだ。
木構造のあるノードのAABBはそのノード自身が持つのではなく、その親のノードが持つ。ゆえにひとつのノードはその子の４つのAABBを持つ。
枝ノードはSSEでの実装では以下のような構造体で記述できる。
struct SIMDBVHNode{ __m128 bboxes[2][3];//4 float min-max xyz size_t children[4]; //4 children int axis_top; //top axis int axis_left; //left axis int axis_right; //right axis int reserved; //padding };
SIMDによる判定はAABBに対して行う。
今回はその先の面の交差には用いない。（論文では実装はしてるようなのだ・・・けど・・・the original triangle layout is left untouched.となってるがはてはて・・・）
inline int test_AABB( const __m128 bboxes[2][3], //4boxes : min-max[2] of xyz[3] of boxes[4] const __m128 org[3], //ray origin const __m128 idir[3], //ray inveresed direction const int sign[3], //ray xyz direction -> +:0,-:1 __m128 tmin, __m128 tmax //ray range tmin-tmax ) { // x coordinate tmin = _mm_max_ps( tmin, _mm_mul_ps(_mm_sub_ps(bboxes[sign[0]][0],org[0]), idir[0]) ); tmax = _mm_min_ps( tmax, _mm_mul_ps(_mm_sub_ps(bboxes[1 - sign[0]][0], org[0]), idir[0]) ); // y coordinate tmin = _mm_max_ps( tmin, _mm_mul_ps(_mm_sub_ps(bboxes[sign[1]][1],org[1]), idir[1]) ); tmax = _mm_min_ps( tmax, _mm_mul_ps(_mm_sub_ps(bboxes[1 - sign[1]][1], org[1]), idir[1]) ); // z coordinate tmin = _mm_max_ps( tmin, _mm_mul_ps(_mm_sub_ps(bboxes[sign[2]][2],org[2]), idir[2]) ); tmax = _mm_min_ps( tmax, _mm_mul_ps(_mm_sub_ps(bboxes[1 - sign[2]][2], org[2]), idir[2]) ); return _mm_movemask_ps(_mm_cmpge_ps(tmax, tmin));//tmin<tmaxとなれば交差 }
これで各枝ノードでの判定は終わり、面との交差判定となる。面と枝ノードはインデックスの一部をフラグとする。
今回の実装では最上位ビットのみフラグとし、面の数はインデックスに含めないこととした。その代わり、面の最後にNULLを置くレイアウトとした。
以上のように実装した。
■性能
QVBHの性能を以下に示す。交差判定をSSEを使うもの(SIMD)とそうでないもの(SISD)をそれぞれ実装した。またQBVHではfloat*4なのでdouble*2のBBVHも実装してみた。
比較対象として、通常のBVH（ノード自身がAABBを持つ）,BIH,KD-Tree,Octreeを用意した。
構築時間
交差判定時間(1000000rays)
消費メモリー
グラフも示す。
QBVHを含め、BVH系構築時間は長めになっている。これは今回の実装が構築するとき空間で振り分けたのではなく、sortで並べることによるものだ。
QBVHでは他の構造と比べ消費メモリーも少なく、肝心の交差判定も非常に速いことがわかる。自分の環境(Core2Duo T8100 2.1GHzh)で約300000rays/sec程度処理できている。
SIMDとSISDではQBVHで約2倍、BBVHで約1.5倍の高速化が実現できていることがわかる。
QBVHではfloat精度なのだが、今回のQBVHではAABBの交差判定のみSIMD化を行った。そのため、最終的な精度は面での交差判定が行うため、こちらがdouble精度の場合、AABBには適切なマージン（最低でもstd::numeric_limits<float>::epsilon()*2）分膨らませてあげれば精度については問題なくなるはずだ。（マージンより狭い範囲に面が集中するようなメッシュだと交差判定が遅くなることはあるがまあ到底考えなくていいだろう）
■結論
QBVHのSIMD化はメッシュの空間構造のみ手を入れればいいため、既存のシステムにマージしやすい。
交差判定スピードは非常に速いため、SSEのようなSIMD命令が使える環境では実装してみる価値はあるはずだ。
■追記
以前実装したときそんなに速くないと吹聴しましたが、参考にした実装(lux render-qbvhaccel.cpp)が間違っていました。
具体的にはAABBの交差判定後、交差するノードをスタックに積む順番が逆になっていました。
■ソース等
以下のURLからソース等の一部をダウンロードできるようにしておきました。参考になるかどうかはわかりませんが。
http://kaze-renderer.googlecode.com/files/acc_test20090925.zip
ヒルベルト曲線は空間充填曲線のひとつだ。このヒルベルト曲線でより高次の空間をたどるとキャッシュ効率がよくなるらしい。
さっそく３次元のモデルの面をヒルベルト曲線順で並び替えてみる。
以下はstanford bunnyのそれぞれの面の順番をHSVのH（色相）に対応させて表示させたものだ。
デフォルトの順番は次のようになる。
かなりめちゃくちゃだ。位置が近ければ近い色に表示されるのが望ましい。
コレを３次元空間をヒルベルト曲線順でたどってみると次のようになる。
だいぶ位置が近い順になった。ただ境目（順番が飛ぶ場所）が結構多い。そこでヒルベルト曲線の階層を１階層にとどめると次のようになる。
なんだか僕にはこちらの方が自然に思える・・・
ヒルベルト曲線順がどういう効果をもたらすか２次元画像をヒルベルト曲線順で色付けして確認してみよう。
どうやらヒルベルト曲線順にすると
これは大きく順番が飛ぶ場所を無くす変わりに順番が飛ぶ場所を増やして分散させるといった効果があるようだ。
でキャッシュ効率なんだけど、どうもいまひとつ効果の違いを見出す実験が発見できなかった。自作レイトレーサとOpenGLレンダラでやってみたんだけれども。
そんなわけでここには結果は載せない。
ただ、キャッシュ効率なんてのはプラットフォームしだいで全然変わってくるものだから、プラットフォームが変わるたびに実験して計測してみるといいかもしれない。
以下にソースを示す。
圧縮検索で使われる技術wavelet treeをテンプレートライブラリとして書いてみました。
→を参考にしてみました。高速かつ省メモリで文字列を扱うデータ構造「wavelet tree」
元となる記事が大変興味深かったのだけど、どうもサンプルコードが複雑すぎるのと、僕の解釈が悪いのか、記事中の説明がコードとつじつまが合わないところがあったので、自分で実装してみたしだい。
記事中ではハフマンコード化の話があるのだけど、あくまでそれは最適な圧縮率を出すための理論にしか過ぎなくて、
頻度の順番で文字をソートしておいて、文字ごとにその文字を１にしたビット列を格納していったほうが素直だろう。(元記事中は該当文字を0としたが1としたほうが操作しやすいと思う)
たとえば、文字列T = "abccbbabca"があったときその頻度は'b','c','a'の順番になる。このとき各文字ごとにビット列を作っていけばいい。
該当する文字を１、それ以外を０とする。すでに使用した文字はビット列に含まない。
b:0100110100->0100110100
c:0X11XX0X10->011010
a:1XXXXX1XX1->111
wavelet treeで文字に対してrank,selectを行うには、各ビット列をrankは上から下へ、selectは下から上へたどって、葉のときは１を、それ以外は０をrank,selectしてあげる。
たとえば、rank(3,'a')とする。rankでは上から下つまり根から葉の方へたどってあげる。
ちょっとrankの定義がよろしくないのでrank(n,1)=less(n+1,1)となるような関数を用意してあげる。（これはrankでは０から数えてn番目を含んでn+1個のビットを検査する定義のため）
| rank(3,'a')->less(4,'a') | rankは上から下へとたどる |
| (0100110100).less(4,0)=3 | 前から４つのビットの０を調べる |
| (011010).less(3,0)=1 | 前から３つのビットの０を調べる |
| (111).less(1,1)=1 | 前から１つのビットの１を調べる |
葉までたどり着いたので最終的な結果１がrank(3,'a')の答えとなる。
select(1,'a')もやってみよう。今度は下から上つまり葉から根の方へたどってあげる。
| select(1,'a') | selectは下から上へとたどる |
| (111).select(1,1)=1 | （０から数えて）１番目の１のインデックスを調べる |
| (011010).select(1,0)=3 | （０から数えて）１番目の０のインデックスを調べる |
| (0100110100).select(3,0)=6 | （０から数えて）３番目の０のインデックスを調べる |
根まで数えたので最終的な結果６がselect(1,'a')の答えとなる。
2008/11/29 修正 struct pair_type{T ch;T count;};→struct pair_type{T ch;size_t count;};
C++で何らかの型を定義して、その型を文字列に変換したいとき、演算子"<<" をストリームに対し定義してやると便利だ。
class Hoge{ public: //たとえば配列のような型だったとする size_t size()const{/*略*/} int operator[](size_t i)const{/*略*/} /*略*/ }; Hoge hoge; std::cout << hoge << std::endl;
よくありがちな失敗は
std::ostream& operator<<(std::ostream& os, const Hoge& rhs){ //クラスをstringstreamに対し文字列化する for(size_t i = 0;i<rhs.size();i++){ os << hoge[i] } return os; }
のような形だろう。これだと、
でこの定義の正しいやり方は以下のようになる
template<typename _CharT, class _Traits> std::basic_ostream<_CharT, _Traits>& operator<<(std::basic_ostream<_CharT, _Traits>& os, const Hoge& rhs){ std::basic_ostringstream<_CharT, _Traits> s;//いったんstringstreamを宣言 //フラグ・ロケール・精度をコピー s.flags(os.flags()); s.imbue(os.getloc()); s.precision(os.precision()); //クラスをstringstreamに対し文字列化する for(size_t i = 0;i<rhs.size();i++){ s << hoge[i] } //文字列化し出力 return os << s.str(); }
テクスチャなどに使う画像は有限の大きさを持つが、これを無限平面として扱えるようになると便利だ。
たとえば画像の任意のピクセルを参照するときX,Yでその位置を指定するが、X,Yの範囲値はそれぞれ
0 <= X < Width, 0 <= Y < Height (Width:画像の幅,Height:画像の高さ)
になる。
画像を無限の空間を持つものとして処理できるようになれば、任意のX,Yでもアクセスできる。
これには任意のX,Yを画像の幅、高さに収める処理が必要となる。これをコレスポンダと呼ぶ。
コレスポンダには以下のようなものが挙げられる。
・リピート：繰り返す
・ミラー：端で折り返す
・クランプ：端を超えていたら端の値とする
