Occlusion Culling
アルゴリズム
アルゴリズムの概要は以下の通り。
- 前処理
- Occluder selection
階層的なbounding volumeによってviewに入っているオブジェクトを選び、
その中からoccluderの候補を選択する。
- Occlusion Map を作り、
estimation bufferを作る。
occluderの候補に対して階層的にOcclusion mapを作る。
- cullingとレンダリング
- View-frustrum cullingを実行。
標準的なviewによるcullingを実行。
- Overlap testsを実行。
- Depth testsを実行。
Overlap testsがTrueになったオブジェクトだけに実行。
- レンダリング
Depth testsがTrueならcullingを実行。(レンダリングしない)
Occluder Selection
- Occlusion Preserving Simplification (OPS)
静的なLOD(levels-of-detail)を作る。
- Run-time Occluder Sellection
Occlusion Map
hierarchical Occlusion Maps (HOM)を作る方法の概要は以下の通り。
- レベル0のOcclusion Mapを作る。
(すべてのオブジェクトを投影したもの)
レベル0のものはレンダリングする解像度よりも小さい解像度のものを使用すると処理が早い。
- レベル0からレベル1のOcclusion Mapを作る。
以下、十分に小さい解像度になるまでレベルnからレベルn+1のOcclusion Mapを作る。
Overlap tests
Overlap tests 実行方法の概要は以下の通り。
- オブジェクトを囲むbounding boxを求める。
- 一番小さい解像度のレベルのOcclusion Mapでover lap testsを実行。
bounding boxの領域が全て1.0の値ならばDepth testsを実行。
(または、閾値以上の場合でも良い)
bounding boxの領域が全て0.0の値ならば、そのオブジェクトを表示しない。
bounding boxの領域の一部が0.0から1.0の間の値である場合は次に進む。
(または、0.0から閾値以上の場合)
- 1段階低いレベルのOcclusion MapでOverlap testsを実行する。
以下、Depth testsをするかどうか決定するまでレベルを低くしてゆく。
- 最終的にレベル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
参考
- HANSONG ZHANG : Effective Occlusion Culling for the Inerractive Display of Arbitrary Models
home | index
Mail