Occlusion Culling

アルゴリズム

アルゴリズムの概要は以下の通り。

  1. 前処理
    1. Occluder selection
      階層的なbounding volumeによってviewに入っているオブジェクトを選び、 その中からoccluderの候補を選択する。
    2. Occlusion Map を作り、 estimation bufferを作る。
      occluderの候補に対して階層的にOcclusion mapを作る。
  2. cullingとレンダリング
    1. View-frustrum cullingを実行。
      標準的なviewによるcullingを実行。
    2. Overlap testsを実行。
    3. Depth testsを実行。
      Overlap testsがTrueになったオブジェクトだけに実行。
    4. レンダリング
      Depth testsがTrueならcullingを実行。(レンダリングしない)

Occluder Selection

Occlusion Map

hierarchical Occlusion Maps (HOM)を作る方法の概要は以下の通り。

  1. レベル0のOcclusion Mapを作る。
    (すべてのオブジェクトを投影したもの)
    レベル0のものはレンダリングする解像度よりも小さい解像度のものを使用すると処理が早い。
  2. レベル0からレベル1のOcclusion Mapを作る。
    以下、十分に小さい解像度になるまでレベルnからレベルn+1のOcclusion Mapを作る。

Overlap tests

Overlap tests 実行方法の概要は以下の通り。

  1. オブジェクトを囲むbounding boxを求める。
  2. 一番小さい解像度のレベルのOcclusion Mapでover lap testsを実行。
    bounding boxの領域が全て1.0の値ならばDepth testsを実行。
    (または、閾値以上の場合でも良い)
    bounding boxの領域が全て0.0の値ならば、そのオブジェクトを表示しない。
    bounding boxの領域の一部が0.0から1.0の間の値である場合は次に進む。
    (または、0.0から閾値以上の場合)
  3. 1段階低いレベルのOcclusion MapでOverlap testsを実行する。
    以下、Depth testsをするかどうか決定するまでレベルを低くしてゆく。
  4. 最終的にレベル0のOcclusion MapでOverlap testsを実行する。
    この段階でbounding boxの領域がDepth testsをするかどうか決まる。

閾値の求め方

int i;
int m[MAX_LEVEL_OF_OCCLUSION_MAP]; /* スクリーン・ブロック - レベルkのOcclusion Map の1ピクセルが元の画像のm[k]*m[k]ピクセルに相当する */
float Tk[MAX_LEVEL_OF_OCCLUSION_MAP]; /* 閾値 */
float L = SIZE_OF_NEGLIGIBLE_HOLES; /* Occlusion Map のどれだけの部分が0.0の値でも良いかを表す L < m[k]*m[k], 0 <= k && k < LEVEL_OF_OCCLUSION_MAP*/
int D = DISTRIBUTION_FACTOR; /* D = m[k+1]/m[k], 1 <= D && D <= 4 */

Tk[0] = 1 - L/(m[0]*m[0]);
for(i = 1; i < MAX_LEVEL_OF_OCCLUSION_MAP; i++)
{
	Tk[i] = 1 - D*(1 - Tk[i-1])/4;
}

例えば、1024x1024の解像度で、レベル0のOcclusion Mapが128x128の解像度だとすると8x8のブロックなので、Lを3*3だとすると、 Tk[0] = 1 - (3*3)/(8*8) = 0.86 となる。
そして、次のレベル1がレベル0の半分の解像度で16x16のブロックになるとD = 2になるので Tk[1] = 1 - 2*(1 - 0.86)/4 = 0.93 となる。

Depth tests

参考


home | index
Mail