2007-08-14

縮小サンプリング

CG programming

mipmapおよびripmap画像作成処理を書いた。

mipmap、ripmapはテクスチャマッピングにおける、縮小サンプリング時の処理だ。
つまり、出力画像のほうがテクスチャ画像より小さい（したがって出力画像の１ピクセルにテクスチャ画像の複数のピクセルが存在する）ときに出力画像にエイリアシングを抑える効果を持つ。
もちろんmipmap、ripmapの画像はただそれだけでは意味がなくて、これをピクセルごとの出力画像vsテクスチャ画像の解像度比率を求めて適切な解像度のピクセルをサンプリングしてあげる必要がある。
出力画像vsテクスチャ画像の解像度比率は出力画像の１ピクセル／テクスチャ画像の１ピクセルである。それぞれ縦横あるからdx/du、dy/dv、dx/du、dy/duとなる。この情報もとに適当な解像度を求めてやる。「適当な」としてるのは本当に適当にということで、解像度比率は４つ求められるのに対し、mipmapならひとつのレベルを、ripmapなら２つのレベルを求めるだけなので当然だ。
縦と横の解像度が同じよう縮小したmipmapに対し縦横別々に縮小したripmapは大きな平面の向こう側など縦と横で縮小率が大きく異なる場合に有効だ。
しかしripmapはメモリの消費率が大きく、また結局出力ピクセルがテクスチャ座標に対し斜めに投影された場合など適切な解像度レベルを求められない。その代わりmipmapを複数回サンプルすることにより、より適切なサンプリングを求めるのを異方向性サンプリングと呼ぶ。
異方向性サンプリングにおいて、サンプル分布に楕円を用いるものをEWAアルゴリズムと呼ぶ（らしい）。
縮小サンプリングにおいて、正確な値を求めたいのであれば範囲総和を用いる。
これは出力座標→テクスチャ座標の変換を行い出力画像の１ピクセルの四角形をテクスチャ座標に投影する。投影された四角形の内部に存在するすべてのテクスチャ画像のピクセルを平均したものをサンプルとする。
範囲総和は遠ければ遠いほど非常にたくさんのテクスチャ画像のピクセルを参照しなくてはならず重たい。
いっぽう投影された四角形を４分木で分割して複数レベルのmipmapを参照することで、範囲総和を高速化することができる。
ほかには範囲総和のサンプル数を固定化することで高速化する手法もある。（準最適化サンプリング参照：GPU Gems 27.2.2 エイリアシング）。

出力画像vsテクスチャ画像の関係は本来的に１次レイのときにしかありえない。
このため２次レイ以降での縮小サンプリングは非常に困難である。（ビームトレーシングを用いれば、「それなり」にはできるはずだが・・・）
またアルゴリズム的にレイトレースには向いていなく、スキャンライン・Zバッファーなどのラスタライズで求めるほうが素直な解決方法であるようだ。

疑問：
■mipmap、ripmapを求める際に非power of 2な解像度を持つ画像に対してはどう対処するのがいいのだろう？
　案１：power of 2に拡大する：拡大フィルタには何を使えばよいか？
　案２：ラップモードを考慮して仮想的にpower of 2にする
■mipmap、ripmap中のそれぞれのレベルの画像を参照するとき拡大フィルタ（bilinear,bicubic, etc...）は使うべきか否か？

いいわけ：
今回はまだ画像の縮小処理を作っただけで、テクスチャの貼り付けまで行えてない。
理由は縮小サンプリングにはラスタライザが必要となるためだ。
レイトレーサに今回の仕組みを実装することはあまり気持ちのいい仕事ではない。
一次レイのためだけに光線クラスに対し保存する情報を追加するべきではないと考えるからだ。

2007-03-05

ひとつはふくすうの部分集合

programming C++

デザインパターンってあるけれど、これは設計というより、内部の関数、構造体どうしのインターフェースのノウハウ・・・パターンだと考えられるんじゃないかと思う。
プログラムは大きく３つの要素・・・構造・アルゴリズム・インターフェースによって構築されると考えることができる。
いま、デザインパターンがもてはやされるのは、上記の３つの要素のうちインターフェースについてを明示的にノウハウとしてのまとめたものだからなんではないだろうか。
デザインパターンはGoFの２３のパターンのほかにもいろいろなものがあって、
たとえば僕なんかはNullObjectパターンなんかは多用するもののひとつだ。

プログラミングをしていると、独自のパターンを発見することがある。
もちろんそのほとんどはいわゆる再発見であり、すでに世の中に知られていて名前も付けられている。
ただし、いくつかは既知のパターンにうまくに当てはめられないものもある。
今日はそのうちのひとつ、単純だけど、非常に有用な（と僕は思ってる）パターンを紹介しよう。（長い前置きだな）

2006-08-06

オブジェクトレベルでの空間構造

レイトレーサにおいて、扱う対象が三角形の集合（メッシュ）だけならいいのだが、それ以外にも球や曲面を扱うとすると、シーン全体でひとつの空間分割構造に押しこめてしまうのは無理が出てくる。
ここでは、メッシュや球・曲面などのひとかたまりをオブジェクトと呼んで、これらの集合をトラバースするための空間構造について考える。

空間構造を考える上で、オブジェクトの集合では三角形のそれとは異なる。

オブジェクトは三角形に比べ、空間的に疎であり、オブジェクト同士のスケール比が大きいことがある
オブジェクトの正確な形状を要求できない
オブジェクトは一回のテストが高負荷である
オブジェクトは三角形に比べ、数はそれほど多くない

１．三角形の集合・メッシュでは三角形同士はつながっていて、空間として局所的だ。
いっぽうオブジェクトの集合ではオブジェクト同士は非常に密集していることも考えられるが、ある程度の距離離れているのが普通だ。さらに、非常に離れていることも考えられる。
またそれぞれのオブジェクトの比が大きいこともしばしばあるだろう。たとえば巨大なビルのオブジェクトとそこに立つ人物のオブジェクトのような場合だ。
以上より空間構造の分割軸はその分割位置がより自由が利くほうが好ましいだろう。たとえばUグリッドよりKDツリーのほうがこの点において優れているはずだ。

２．オブジェクトに正確な形状を要求し空間構造を構築することは難しい。たとえば曲面など同様にして考えるとわかるだろう。
そのため、空間構造を構築するための材料としてそのオブジェクトを包む球やAABB、OOBBなどを用いることになる。
だからオブジェクトの形状に左右されるアルゴリズムは採用できないことが多い。

３．ひとつのオブジェクトは一回のテストが非常に高負荷になることになることも考えなくてはならない。たとえばひとつのオブジェクトが数万ポリゴンのメッシュとなることも考えられる。このためトラバース時に複数回テストすることは必ず避けなければならない。
これには

空間構造中の複数のセルにひとつのオブジェクトをまたがせない
メールボックスをつかって一度テストしたら２度とテストさせない

が考えられる。
複数のセルにまたがせないようにするには、

３分木
BIH (B-KDTREE)

のような構造を遣うことになるだろう。
ここでいう３分木はKDツリーを拡張したもので、分割軸をまたがるオブジェクトは左・右セルとは別の中央セルに登録するようにしたもの。
メールボックスを用いる場合でトラバースのマルチスレッドも考慮に入れる場合
メールボックス実装は、TLSを使うか、スレッドIDをキーとしたマップとするなどが必要だろう。

４．オブジェクトの数はそれほど多くないと考えられる。たとえば１０万ポリゴンのメッシュを何十万個も表示するシーンなど普通はありえないだろう。
そのため、構築にはある程度時間がかけられる。

今のとこ僕が考えているオブジェクトレベルの空間構造としては以下がある。

KDツリー＋メールボックス
Uグリッド＋メールボックス
ハッシュUグリッド＋メールボックス
オクツリー＋メールボックス
BIH
３分木

今のところ僕の自作レンダラでは
KDツリー＋メールボックス、Uグリッド＋メールボックス、BIH、３分木
を実装し試してみた。
結果を今のところ経験論的なもので申し訳ないが以下に書く。

構築においてはよほどの数のオブジェクトを扱うのでなければ、わずかであり、
メッシュ構築時間と比べれば些細な時間なので気にしなくていいと思う。

トラバースにおいては、シーンによって異なるのでなんともいいがたいが、
メールボックスを使うものでは、KDツリーのほうがわずかに速いことが多いようだ。とくにオブジェクト同士の距離が大きいとUグリッドは効率が良くない。
BIHはメールボックスを使うものに比べ大分遅い。特にオブジェクト同士が密集してる場合は良くない。
３分木はメールボックスを使うものと同様のスピードが出せる。ただやはり密集してるとノードが分割できないので遅くなる。

以上からいまのところ、KDツリー＋メールボックスが一番オブジェクトレベルでの空間構造に適していると判断している。

第１候補：KDツリー＋メールボックス
第２候補：３分木

メールボックスはマルチスレッドではどうなるか実際試してみなければならない（まだ試してない・・・）だろう。
またいくつか実装を行ってないものもあるので、試してみたいと考えている。

2006-08-05

BIH実装

CG programming

大分前から各所で話題になっていたBIHですが遅ればせながら、実装して試しました。
BIHって用は分割位置が二つあるkdtreeなんですが、ようは内部の三角形を２つの空間に分けるとき適当にどっちかに入れるか決めてしまってその境目は適当にやってしまおうという、適当の極みみたいなデータ構造*1です。
いつものアルマジロで結果は以下のような感じ（CoreDuo T2300 1GB Memory）

時間（ms）	オクトリー	KDツリー	BIH
構築	4760	3882	1780
レンダリング	7132	7868	8365

まあ何せ構築が速い。だって分割軸の左か右かなんて三角形の重点みればいいんだもん。速いわけだ。
しかももうひとつ特徴としてひとつの三角形が複数の部分空間にまたがることがないため、メールボックスなんか、使う必要がない（使っても意味がない）*2です。

今回syoyoさんのところでソースを拝見しながら実装しました。この場を借りてお礼いたします。ありがとうございます。
氏のサイトで指摘されている大きな三角形があった場合ですが、これについては軸を選ぶとき、その基準となるバウンドを子に下るごとに三角形のリストから得るのではなく、親のバウンドから分割軸で分割したものをつかえば、あまり問題にならないはずです。あくまで「空間」を分割すればよいのです。

情報など、なにかご意見いただけたら幸いです。

以下にハンパなソースをおいときます。
http://www.wikiroom.com/ototoi/index.php?plugin=attach&refer=BIH&openfile=BIH.zip

*1:loose-kdtreeとでも名前をしたほうが・・・

*2:僕はもともとメッシュにメールボックスをつかうのは疑問に思っているのでその他の構造にも使ってませんが

2006-06-17

MemoryPoolについて

C++ programming

MemoryPoolという構造体がある。これは一種のアロケータで、あるサイズ分メモリーをブロックとして確保しておき、それをためて置く。これを必要になったときそれを使用する。Effecient C++にはそんな構造体が載っている。
いくつかの不具合を修正したので、以下にそれを示す。

2006-04-17

クラスを使おう！無名名前空間を利用しよう！

programming C++

オブジェクト指向言語であるC++においてクラスは基礎的な部品であり、論理構造を抽象化し、ソースコードの見通しを良くしてくれる。
クラスは他の関数ないしクラスのメンバ関数において、実装として局所的に使われるケースがあっても良い。なにもクラスは「再利用されなければならない」''わけではない!''。
つまりヘッダにかかれない−インターフェースとはならない、クラスがあっても一向に構わない。ここでは、このような実装のために使われる局所的なクラスを実装クラスと呼ぶことにする。

 // func.h
 void func();//関数プロトタイプ

 //func.cpp
 #include "func.h"
 #include <iostream>
 class FuncImp{
 public:
    void run(){
        std::cout << "func!\n" << std::endl;
    }
 }; 
 void func(){//関数の実装
    FuncImp fimp;
    fimp.run();//実装クラスに委譲
 }

さて上記のような実装クラスを用いることで、処理の実装を簡潔に記述することができる（このことについてはまたいずれ）。ヘッダには書かない実装クラスは積極的に書くべきであるが、上記ソースにはひとつ問題がある。それはクラスFuncImpリンケージが外向けに公開されているために別の翻訳単位で再宣言可能しても、再宣言したクラスはリンカから見逃されてしまうのだ。複数の翻訳単位で同じ名前のクラスが宣言された場合、先に現れたものが優先される。

 // main.cpp
 #include "func.h"
 class FuncImp{
 public:
    void run(){
        std::cout << "main!\n" << std::endl;
    }
 }; 
 int main(){
    func();
    
    FuncImp fimp;
    fimp.run():
 }

 #実行結果
 func!
 func! //main!となって欲しい

main.cpp側では直前に宣言・定義したクラスが使われずに、別の場所（func.h）で宣言・定義したクラスが使われてしまっている。
上のような状態を防ぐには、実装クラスの、宣言・定義を''無名ネームスペース''で囲むことだ。以下のようにする。

 //func.cpp
 #include "func.h"
 #include <iostream>
 namespace {//無名ネームスペース
   class FuncImp{
   public:
      void run(){
          std::cout << "func!\n" << std::endl;
      }
   }; 
 }//無名ネームスペース閉じ
 void func(){//関数の実装
    FuncImp fimp;//とくに型の参照はそのまま
    fimp.run();//実装クラスに委譲
 }

無名ネームスペースを活用することで、クラスの名前を外に公開することがなくなり、安心して実装クラスを宣言・定義することができる。

2006-03-26

compositeパターン

C++ programming

compositeパターンは複数のものを単数扱いして複雑な構造への処理を容易に行なえるようにするものだ。この適用範囲は思いのほか広い。これには、『複数のものを単数扱い』というより『単数の出力を複数の出力』とみなすとした方が分かりやすいかもしれない。