明日ではないから このページをアンテナに追加 RSSフィード

 

2011/05/31 (Tue)

[][]ヘアーレンダリング

marschner hairモデルを実装しシェーディングしてみた。

パラメータの調整がうまくできなくてとりあえず黒髪だけど、以下のようになる。

f:id:ototoi:20110531231121j:image

以下はdiffuse項をkajiya-kayを用い、specular項を今回のmarschnerモデルで置き換えた画像

f:id:ototoi:20110604221541j:image

f:id:ototoi:20110604221540j:image

f:id:ototoi:20110604222231j:image

2011/05/15 (Sun)

[][]ヘアーレンダリング

髪の毛のレンダリングにおいて前回までの円柱+球ではなく、カーブとしてレンダリングしてみた。

カーブレンダリングの手法はRAY TRACING FOR CURVES PRIMITIVEを実装することで解決した。

また、髪の毛の一本一本をカーブとみなすために、点列間をcatmull-romカーブでつなぎそれを動的にベジェカーブに変換する仕組みを入れた。

以上により髪の毛が形状も陰影もなめらかに変異するようになった。

差し当たり結果画像のみアップしておく。

f:id:ototoi:20110516015918j:image

f:id:ototoi:20110516015917j:image

f:id:ototoi:20110516015919j:image

以上では、どこが変わったかからないので、一部を拡大した画像を置く。

上が前回まで円柱+球、下が今回のカーブ

f:id:ototoi:20110516222944j:image

f:id:ototoi:20110516222943j:image


速度は前回までの円柱+球での画像が2400*2400で30秒程度だったのに対し、今回の手法では約90秒ほどの速度になった。

2011/03/29 (Tue)

[][]ヘアーレンダリング

前回のシーンの影を半透明にしてレンダリングしてみた。

f:id:ototoi:20110329230658j:image

f:id:ototoi:20110329230657j:image

f:id:ototoi:20110329230659j:image

あと今後できることは以下のようなことが考えられる。

  1. もっと複雑なシェーディングモデル採用
  2. 半透明シャドウ高速化
  3. ヘアーセグメントのスプライン曲線による補間・細分化
  4. GIへの対応

2011/03/21 (Mon)

[][]ヘアーレンダリング

自作レンダラにおいて髪の毛のレンダリングに取り掛かっている。

具体的にどうするべきか、実験であるが、とりあえずここ(HAIR Model Files - Cem Yukselからhairモデルを取得して単純なレイトレースにてレンダリングしてみた。

物体形状としては髪の毛一本一本を円柱と球をつなげたものを使った。

f:id:ototoi:20110321174700p:image

シェーディングモデルにはKajiya-Kayの物*1をそのまま使った。

以下は2400*2400でレンダリングして800*800に縮小したもの。

いまいち体感に欠けるのは、

  1. 明度考慮していない。
  2. 影がレイトレーシングシャドウ
  3. 内部散乱を考慮していない。
  4. サンプル数が足りない。

などが挙げられるだろう。

速度に関しては、レイトレーシングスポットライト1灯、解像度2400*2400でそれぞれ1分程度である

今後どうするかだが、透明度考慮して、シェーディング&影付けすればリアリティが増すものと思われる。

f:id:ototoi:20110321172040j:image

f:id:ototoi:20110321172039j:image

f:id:ototoi:20110321172041j:image

2011/3/23追記

影なしでシェーディングがすこしおかしかったところを改変。

f:id:ototoi:20110323002616j:image

f:id:ototoi:20110323002615j:image

f:id:ototoi:20110323002617j:image

*1:Rendering fur with three dimensional textures

2009/09/25 (Fri)

[][]QBVHを実装した


空間構造の一種であるQBVH(Quad-tree Bounding Volume Hierarchy)を実装した。

元の論文http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.100/institut/Papers/QBVH.pdf

QBVHはレイトレーサの交差判定を高速化する。

以前syoyoさんがイイヨとおっしゃっていたので実装してみた。

f:id:ototoi:20090925213845j:image


この論文で語られるQBVHの要点は以下。

1.4分木構造

木構造においてひとつノードに4つのノードを格納する。

2.ノードのAABB(バウンド)を親が持つ

一つ一つのノードがそのAABBを持つのではなくその親が4ついっぺんにもつ

3.SIMDによる判定

つのノードのAABBの交差判定をSIMD演算を利用していっぺんに行う

4.面情報を格納するノードは作らない

情報を格納するノードは実際には作らない。その代わり、ノードの子が枝ノードなのか面なのかをインデクッスの一部をフラグとし格納する。

■実装

普通BVHといえば2分木構造を用いるがQBVHでは4分木構造を用いる。これはSIMD(インテルCPUではSSE)ではfloat*4の演算を一度にすることができるため、4分木であることが最適であるからだ。

木構造のあるノードのAABBはそのノード自身が持つのではなく、その親のノードが持つ。ゆえにひとつノードはその子の4つの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.となってるがはてはて・・・)

SSEでは以下のような関数となる。


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となれば交差
}

これで各枝ノードでの判定は終わり、面との交差判定となる。面と枝ノードインデックスの一部をフラグとする。

元の論文では以下のようにレイアウトしている。

f:id:ototoi:20090925201103p:image

今回の実装では最上ビットのみフラグとし、面の数はインデックスに含めないこととした。その代わり、面の最後にNULLを置くレイアウトとした。

f:id:ototoi:20090925201900p:image

f:id:ototoi:20090925203554p:image

以上のように実装した。

■性能

QVBHの性能を以下に示す。交差判定をSSEを使うもの(SIMD)とそうでないもの(SISD)をそれぞれ実装した。またQBVHではfloat*4なのでdouble*2のBBVHも実装してみた。

比較対象として、通常のBVH(ノード自身がAABBを持つ),BIH,KD-Tree,Octreeを用意した。

構築時間

f:id:ototoi:20090925221543p:image

交差判定時間(1000000rays)

f:id:ototoi:20090925221544p:image

消費メモリ

f:id:ototoi:20090925221545p:image


グラフも示す。

f:id:ototoi:20090925211357p:image

f:id:ototoi:20090925211358p:image

f:id:ototoi:20090925211359p:image

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

また全ソースは以下のURLホスティングしてあります

http://code.google.com/p/kaze-renderer/

2009/03/15 (Sun)

[][]ヒルベルト曲線順

ヒルベルト曲線は空間充填曲線のひとつだ。このヒルベルト曲線でより高次の空間をたどるとキャッシュ効率がよくなるらしい。

f:id:ototoi:20090315213432j:image

さっそく3次元モデルの面をヒルベルト曲線順で並び替えてみる。

以下はstanford bunnyのそれぞれの面の順番をHSVのH(色相)に対応させて表示させたものだ。

デフォルトの順番は次のようになる。

f:id:ototoi:20090315205905j:image

かなりめちゃくちゃだ。位置が近ければ近い色に表示されるのが望ましい。

コレを3次元空間をヒルベルト曲線順でたどってみると次のようになる。

f:id:ototoi:20090315205906j:image

だいぶ位置が近い順になった。ただ境目(順番が飛ぶ場所)が結構多い。そこでヒルベルト曲線の階層を1階層にとどめると次のようになる。

f:id:ototoi:20090315205907j:image

なんだか僕にはこちらの方が自然に思える・・・

ヒルベルト曲線順がどういう効果をもたらすか2次元画像ヒルベルト曲線順で色付けして確認してみよう。

f:id:ototoi:20090315211019j:image

どうやらヒルベルト曲線順にすると

  • 大きな境目は少なくなる
  • 境目の数は多くなる

これは大きく順番が飛ぶ場所を無くす変わりに順番が飛ぶ場所を増やして分散させるといった効果があるようだ。

キャッシュ効率なんだけど、どうもいまひとつ効果の違いを見出す実験発見できなかった。自作レイトレーサとOpenGLレンダラでやってみたんだけれども。

そんなわけでここには結果は載せない。

ただ、キャッシュ効率なんてのはプラットフォームしだいで全然変わってくるものだから、プラットフォームが変わるたびに実験して計測してみるといいかもしれない。

以下にソースを示す。

続きを読む

2009/03/08 (Sun)

[][][]AOBenchをF#で実装した。

http://lucille.atso-net.jp/aobench/ で開催されているAOBenchをF#にて実装しました。

f:id:ototoi:20090309023406j:image

実装としてはC#版からの多くを拝借して移植

あんまり関数型言語っぽくしてない。画像処理のような大きな配列を書き換える(リストから別のリストを作るのはやりやすいんだけどね)作業は、手続き型的に書いたほうがいいと思う。

ヴァリアントマッチをうまくつかうと素直な流れで書くことができますね。

速度はCore2Duo T8100 2.1GHzで約9.4秒でした。

以下ソース

続きを読む

追記

上のコードはortho_basisで基底ベクトルの組を、配列をヒープで作って返しているんだけどこれはタプルで十分ですね。

受け側ではmatch〜withでバインドする。

この変更を行ったところ約9.4秒→約8.3秒程度と高速化しました。

以下変更部分ソース

続きを読む

2008/11/16 (Sun)

[][]wavelet tree

圧縮検索で使われる技術wavelet treeテンプレートライブラリとして書いてみました。

→を参考にしてみました。高速かつ省メモリで文字列を扱うデータ構造「wavelet tree」

元となる記事が大変興味深かったのだけど、どうもサンプルコードが複雑すぎるのと、僕の解釈が悪いのか、記事中の説明がコードとつじつまが合わないところがあったので、自分で実装してみたしだい。

記事中ではハフマンコード化の話があるのだけど、あくまでそれは最適な圧縮率を出すための理論にしか過ぎなくて、

頻度の順番で文字をソートしておいて、文字ごとにその文字を1にしたビット列を格納していったほうが素直だろう。(元記事中は該当文字を0としたが1としたほうが操作しやすいと思う)

たとえば、文字列T = "abccbbabca"があったときその頻度は'b','c','a'の順番になる。このとき各文字ごとにビット列を作っていけばいい。

該当する文字を1、それ以外を0とする。すでに使用した文字はビット列に含まない。

b:0100110100->0100110100

c:0X11XX0X10->011010

a:1XXXXX1XX1->111

以上でビット配列ができた。

wavelet treeで文字に対してrank,selectを行うには、各ビット列をrankは上から下へ、selectは下から上へたどって、葉のときは1を、それ以外は0をrank,selectしてあげる。


たとえば、rank(3,'a')とする。rankでは上から下つまり根から葉の方へたどってあげる。

ちょっとrankの定義がよろしくないのでrank(n,1)=less(n+1,1)となるような関数を用意してあげる。(これはrankでは0から数えてn番目を含んでn+1個のビット検査する定義のため)

rank(3,'a')->less(4,'a') rankは上から下へとたどる
(0100110100).less(4,0)=3 前から4つのビットの0を調べる
(011010).less(3,0)=1 前から3つのビットの0を調べる
(111).less(1,1)=1 前から1つのビットの1を調べる

葉までたどり着いたので最終的な結果1がrank(3,'a')の答えとなる。

select(1,'a')もやってみよう。今度は下から上つまり葉から根の方へたどってあげる。

select(1,'a') selectは下から上へとたどる
(111).select(1,1)=1(0から数えて)1番目の1のインデックスを調べる
(011010).select(1,0)=3(0から数えて)1番目の0のインデックスを調べる
(0100110100).select(3,0)=6(0から数えて)3番目の0のインデックスを調べる

根まで数えたので最終的な結果6がselect(1,'a')の答えとなる。



2008/11/29 修正 struct pair_type{T ch;T count;};→struct pair_type{T ch;size_t count;};


続きを読む

2008/11/09 (Sun)

[][]正しい 演算子"<<" の定義の仕方

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();
}

2008/05/15 (Thu)

[][]画像無限平面化

テクスチャなどに使う画像は有限の大きさを持つが、これを無限平面として扱えるようになると便利だ。

たとえば画像の任意のピクセルを参照するときX,Yでその位置を指定するが、X,Yの範囲値はそれぞれ

0 <= X < Width, 0 <= Y < Height (Width:画像の幅,Height:画像の高さ)

になる。

この範囲を超えてアクセスした場合、エラーとなってしまう。

f:id:ototoi:20080515205019p:image

画像無限の空間を持つものとして処理できるようになれば、任意のX,Yでもアクセスできる。

これには任意のX,Yを画像の幅、高さに収める処理が必要となる。これをコレスポンダと呼ぶ。

レスポンダには以下のようなものが挙げられる。

リピート:繰り返す

f:id:ototoi:20080515204514j:image

ミラー:端で折り返す

f:id:ototoi:20080515204513j:image

クランプ:端を超えていたら端の値とする

f:id:ototoi:20080515204512j:image

続きを読む