グリッドハッシュ

by syoyo

lucille では主にレイトレの空間データ構造には一様グリッドを用いており、
一度にガバっと三次元ボクセル(たとえば voxel[128][128][128])という形でメモリを確保しています。

これだと、もっとも単純なのですが、物体の無いカラのボクセルでもメモリを
確保してしまうため、メモリを無駄に消費してしまうという欠点があります。

ひとつの解として、ハッシュを用いてカラのボクセルはメモリ確保しないという
方法があります。

グリッドハッシュは少し調べて試してみたことがあったのですが、
Arnold も空間データ構造にグリッドハッシュを利用していると聞き、
lucille でも、本格的に lucille に組み込んでデフォルトの空間データ構造に
しようかと考えています。

ボクセルハッシュ

視覚的な解説は、


http://www-evasion.imag.fr/Publications/2005/ZTKHRF05/spatial_subdivision.pdf

が参考になります。

通常のハッシュアルゴリズムとほとんど同じです。

まず、構築時では、物体をボクセルに登録します。
物体位置 (x, y, z) からハッシュ値を計算します。

hashval = hash(x, y, z) % HASH_TABLESIZE

この値でハッシュテーブルをルックアップします。

voxel = hashtable[hashval]

この voxel の場所にポリゴンを追加します。
しかし、ハッシュテーブルの数は有限で通常ボクセル分割数よりも少ないので、
異なる (x, y, z) でも同じハッシュ値と衝突してしまう可能性があります。
この場合はリンクリスト(チェイン)を作成します。
ボクセルには自身が対応する (x, y, z) の情報も保持しておきます。

found = false;
while (voxel) {
    if (voxel->x == x && voxel->y == y
&& voxel->z == z) {
        物体をこのボクセルに登録
        found = true;
        break;
    }

    voxel = voxel->next;
}

if (found!) {
    newvoxel = new voxel;
    物体と位置情報をこのボクセルに登録

    // リンクリストを作成
    newvoxel->next = hashtable[hashval];
    hashtable[hashval] = newvoxel;
}

トラバーサルのときも同じようにします。
まず 3DDDA でトラバース位置を計算、(x, y, z) からハッシュ値を計算し、
ハッシュテーブルからボクセルをルックアップします。
同じ (x, y, z) の値を持つボクセルでなかったら、リンクをたどって同じ (x, y, z)
の値を持つボクセルを見つけるまで繰り返します。

ボクセルハッシュの問題は、このリンクをたどる操作は、
そのままでは単純な線形探索になってしまうということです。
同じハッシュ値のテーブルに複数のボクセルが登録されてしまうと、
トラバーサル時のパフォーマンスが低下してしまいます。
これは、ボクセルの分割数が多くなると顕著に

とはいえ、たとえばリンクリストのボクセルを、
さらに kd-tree 化して空間データ構造
を作成するようにすれば、効率がよくなりそうです。  

ハッシュ値の計算

どのハッシュスキームにも言えることですが、
(x, y, z) のペア(今回は一様グリッドなので、x, y, z は整数でよい)から、
ハッシュ値を計算するハッシュ関数は、
なるべく計算が高速で、かつ生成されるハッシュ値にかたよりがないのが望ましいです。

私が知っているハッシュ関数は、以下の二つです。

Wyvill, Brian, 3D Grid Hashing Function,
Graphics Gems, p. 343-345, code: p. 733-734,
http://www.acm.org/pubs/tog/GraphicsGems/gems/Hash3D.c

M. Teschner, B. Heidelberger, M. Mueller, D. Pomeranets, M.
Gross,
Optimized Spatial Hashing for Collision Detection of
Deformable Objects
,”
Proc. Vision, Modeling, Visualization VMV’03,
Munich, Germany,
pp. 47-54, Nov. 19-21, 2003
http://cg.informatik.uni-freiburg.de/publications.htm

少しテストした感じでは、前者の分布は、後者にくらべるとあまりよくないようです。
また、後者は単純な線形合同法のような感じなので、非常に効率よくハッシュ関数を
計算できるという利点があります。

空間データ構造にハッシュを用いるのは、後者の論文のように、
軟体の衝突判定ではよく用いられているようです。

M. Teschner, S. Kimmerle, B. Heidelberger, G. Zachmann, L.
Raghupathi, A. Fuhrmann, M.-P. Cani, F. Faure, N.
Magnenat-Thalmann, W. Strasser, and P. Volino,
Collision Detection for Deformable
Objects
http://eg04.inrialpes.fr/Programme/STAR/STAR5.html
State of the Art Reports, EUROGRAPHICS 2004.

特に軟体のように毎フレーム物体の位置が変化する場合、
bsp のように物体を基準に空間を切るのではなく、
一様グリッドのように空間を基準に空間を切る(物体の形状に非依存)
ほうが効率がよいからのようです。

また、ハッシュをよく使う分野、たとえば通信や暗号などの研究分野にも、
もしかしたら計算が早く、グラフィックスにも使えるような
効率的なハッシュ関数があるのかもしれませんね。

オクツリーハッシュ

応用として、オクツリーをハッシュ化するオクツリーハッシュがあります。

Michael S. Warren and John K. Salmon,
“A parallel hashed oct-tree N-body
algorithm”,

In Supercomputing ’93, pages 12-21, Los Alamitos, IEEE
Comp. Soc, 1993
http://www.thesalmons.org/john/pubs/references.html

この論文では、ハッシュ値の計算には x, y, z のビットインターリーブを用いています。
子のオクツリーボクセルのトラバースを効率よく行うためのようです。
既存の CPU ではビットインターリーブを計算する専用の命令はないため、
以下のテーブルルックアップによる方法を使うのがベストでしょうか。

http://lucille.sourceforge.net/blog/archives/000365.html
http://lucille.sourceforge.net/blog/archives/000363.html

オクツリーハッシュも時間があれば試してみたいですね。

 

Advertisements