チェックはglslangValidator
で.2015年6月23日火曜日
2015年4月28日火曜日
Timsort
Timsortを, python 3.4.3のコードを1行1行追いながら移植.
GitHub-Timsort
以下のJava7の実装では例外が発生するケースでテストしてみた.
http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/
コードがかなり複雑. gallop_rightのあたりの理解がさっぱり.
ランダムデータではIntrosortの方が,
ソートされた部分が多いほどTimsortの方が速い,
とのことであるが, 実測はどうだろうか.
適材適所ではあるので, ライブラリに
アルゴリズムが複数あって困ることはない.
ついでにGoogle CodeからGitHubへ移行.
Exportボタンを押すだけで終了したので,
何か書くことも無し.
GitHub-Timsort
以下のJava7の実装では例外が発生するケースでテストしてみた.
http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/
コードがかなり複雑. gallop_rightのあたりの理解がさっぱり.
ランダムデータではIntrosortの方が,
ソートされた部分が多いほどTimsortの方が速い,
とのことであるが, 実測はどうだろうか.
適材適所ではあるので, ライブラリに
アルゴリズムが複数あって困ることはない.
ついでにGoogle CodeからGitHubへ移行.
Exportボタンを押すだけで終了したので,
何か書くことも無し.
2015年3月16日月曜日
Hopscotch Hashingとその他
Hopscotch Hashingに入れ換える.
簡単なテストでは, Google Dense HashMapより速いよう.
キーからハッシュ等で計算した最初の位置を, ハッシュ値と呼ぶことにする.
その位置に, その位置から後ろの同じハッシュ値のキーが入っている場所を,
ビットマップとして保存する.
4bitのビットマップで, 位置nのビットマップが
bitmap=0101
なら, n, n+2に, ハッシュ値nのキーが入っている.
・検索は, ビットマップのビット数先までしか検索しない.
ビットマップだけで空かどうかわかる.
・挿入は, 適当にビットマップのビット数 x M倍先までしか空きを検索しない.
論文ではM=8だそうです.
空きの位置を, ビットマップの範囲に入るまで移動してくる.
・削除は, 通常のマップの削除処理に追加で,
ハッシュ値と削除位置の差分からビットマップをクリアするだけ.
削除フラグは必要なし. 空きフラグは必要.
Cuckoo Hashingというのも.
Open Addressingに対して, ビットマップという余計なデータがある.
メモリ効率は仕方がないが, 追加の操作がビットマップに対する操作なのがポイントなのだろう.
ビットマップサイズ4バイト, M=8の場合で32バイト,
64バイトのキャッシュラインなら平均的に8割ぐらいキャッシュラインに入る.
Google Codeが終了のお知らせ.
引っ越し先はGitHubでいいのだろうけど,
お金払って安心を買いたい.
簡単なテストでは, Google Dense HashMapより速いよう.
キーからハッシュ等で計算した最初の位置を, ハッシュ値と呼ぶことにする.
その位置に, その位置から後ろの同じハッシュ値のキーが入っている場所を,
ビットマップとして保存する.
4bitのビットマップで, 位置nのビットマップが
bitmap=0101
なら, n, n+2に, ハッシュ値nのキーが入っている.
・検索は, ビットマップのビット数先までしか検索しない.
ビットマップだけで空かどうかわかる.
・挿入は, 適当にビットマップのビット数 x M倍先までしか空きを検索しない.
論文ではM=8だそうです.
空きの位置を, ビットマップの範囲に入るまで移動してくる.
・削除は, 通常のマップの削除処理に追加で,
ハッシュ値と削除位置の差分からビットマップをクリアするだけ.
削除フラグは必要なし. 空きフラグは必要.
Cuckoo Hashingというのも.
Open Addressingに対して, ビットマップという余計なデータがある.
メモリ効率は仕方がないが, 追加の操作がビットマップに対する操作なのがポイントなのだろう.
ビットマップサイズ4バイト, M=8の場合で32バイト,
64バイトのキャッシュラインなら平均的に8割ぐらいキャッシュラインに入る.
Google Codeが終了のお知らせ.
引っ越し先はGitHubでいいのだろうけど,
お金払って安心を買いたい.
2015年2月26日木曜日
Moment Shadow Mapping
Moment Shadow Mapping
Interactive 3D Graphics and Games 2015の論文です.
Game Developer Conferenceより参加したいかもしれない.
上: フィルタ無し, 中: PCF, 下: MSM.
Moment Shadow Mapping (MSM)は, 1024x1024を512x512にダウンサンプル,
１回ガウス関数でブラーをかけています. 16bit float RGBAのバッファを使用しています.
Percentage closer filtering (PCF)は, ５点サンプルしています.
光滲みを抑えるために,暗くなってしまいます.
光源方向と法線が直交に近い場合, カスケード間のギャップが大きくなるのを抑えたい.
ソフトシャドウに使わなければ, 処理負荷・メモリ使用量的にもPCFがよいかもしれない.
Variance Shadow Mapping よりは, Exponential Variance Shadow Mapping,
そして Moment Shadow Mappingの方がよさそうです.
詳しくないので, ふわっとした感想です.
ソフトシャドウ. カスケードの境目はまだ目立つ.
Interactive 3D Graphics and Games 2015の論文です.
Game Developer Conferenceより参加したいかもしれない.
上: フィルタ無し, 中: PCF, 下: MSM.
Moment Shadow Mapping (MSM)は, 1024x1024を512x512にダウンサンプル,
１回ガウス関数でブラーをかけています. 16bit float RGBAのバッファを使用しています.
Percentage closer filtering (PCF)は, ５点サンプルしています.
光滲みを抑えるために,暗くなってしまいます.
光源方向と法線が直交に近い場合, カスケード間のギャップが大きくなるのを抑えたい.
ソフトシャドウに使わなければ, 処理負荷・メモリ使用量的にもPCFがよいかもしれない.
Variance Shadow Mapping よりは, Exponential Variance Shadow Mapping,
そして Moment Shadow Mappingの方がよさそうです.
詳しくないので, ふわっとした感想です.
ソフトシャドウ. カスケードの境目はまだ目立つ.
2015年2月16日月曜日
2014年10月6日月曜日
Voxel Cone Tracing
Sparse Voxel Octreeではなく、レギュラーグリッドとミップマップです。
ボクセルの更新には特に工夫はなく、毎フレーム計算し直しです。
ベースは以下の2つです。
Geeks3D
Practical Real-Time Voxel-Based Global Illumination For Current GPUs
ボクセルグリッドは128x128x128のミップマップレベル6段階。
ディフューズに9本、スペキュラに4本のレイを飛ばします。
ボクセル化する際にスーパーサンプリングを行って、
ボクセルの不透明度を計算しています。
ボクセルに対して小さいもの、薄い布等は、
裏側で不正な結果が目立つようです。
ボクセル更新の工夫と、低解像度でGI計算すれば、
なんとか使いものになるかもしれない。
カスケードやクリップマップでLODを行うものが提案されていますが、
どちらも遠方の光漏れを防ぐ方法がないのではと思います。
ソースのようなもの
GitHub
ボクセルの更新には特に工夫はなく、毎フレーム計算し直しです。
ベースは以下の2つです。
Geeks3D
Practical Real-Time Voxel-Based Global Illumination For Current GPUs
ボクセルグリッドは128x128x128のミップマップレベル6段階。
ディフューズに9本、スペキュラに4本のレイを飛ばします。
ボクセル化する際にスーパーサンプリングを行って、
ボクセルの不透明度を計算しています。
ボクセルに対して小さいもの、薄い布等は、
裏側で不正な結果が目立つようです。
ボクセル更新の工夫と、低解像度でGI計算すれば、
なんとか使いものになるかもしれない。
カスケードやクリップマップでLODを行うものが提案されていますが、
どちらも遠方の光漏れを防ぐ方法がないのではと思います。
ソースのようなもの
GitHub
2014年7月31日木曜日
Embree
Embreeで遊ぶ。
Intelのレイトレーシングカーネル。
レイと三角形メッシュの衝突判定を行うライブラリ。
Intel SPMD Program Compiler(ISPC)を利用する。
ISPCのチュートリアルも少し見てみたので、
何か機会があれば利用しよう。
NEONも対応しているようですが、
あれのために使い辛い。
VisualStudioでは、ISPCのファイルのコンパイルに一手間かかります。
[プロジェクト]>[ビルドのカスタマイズ]>[既存ファイルの検索]
でEmbree/common/cmake/ispc.targetsを追加すると
ISPCの利用が楽になる。
ispc.props、ispc.rules、ispc.targets、ispc.xmlあたりを
別フォルダに保存して利用するのがいいかも。
白目が黒くなってるのは何かな？
EmbreeのサンプルとしてEmbree Rendererがあるのですが、
これだけでかなり遊べます。
PNG形式の画像をロードするにはImageMagickが必要です。
ImageMagickのビルドに挫折したため、
直接libpngでロードするコードを追加しました。
Embreeを知ったきっかけは、2014年5月号ぐらいのCG Worldで
VRayが使用しているという記事。
Siggraph2014で、Embreeについて発表があるよう。
Intelのレイトレーシングカーネル。
レイと三角形メッシュの衝突判定を行うライブラリ。
Intel SPMD Program Compiler(ISPC)を利用する。
ISPCのチュートリアルも少し見てみたので、
何か機会があれば利用しよう。
NEONも対応しているようですが、
あれのために使い辛い。
VisualStudioでは、ISPCのファイルのコンパイルに一手間かかります。
[プロジェクト]>[ビルドのカスタマイズ]>[既存ファイルの検索]
でEmbree/common/cmake/ispc.targetsを追加すると
ISPCの利用が楽になる。
ispc.props、ispc.rules、ispc.targets、ispc.xmlあたりを
別フォルダに保存して利用するのがいいかも。
白目が黒くなってるのは何かな？
EmbreeのサンプルとしてEmbree Rendererがあるのですが、
これだけでかなり遊べます。
PNG形式の画像をロードするにはImageMagickが必要です。
ImageMagickのビルドに挫折したため、
直接libpngでロードするコードを追加しました。
Embreeを知ったきっかけは、2014年5月号ぐらいのCG Worldで
VRayが使用しているという記事。
Siggraph2014で、Embreeについて発表があるよう。
登録:
投稿 (Atom)