範囲総和テーブル


~ Summed Area Tables ~






■はじめに

今回は、Simon Green氏がGDC2003で発表された(らしい。行ってないので知らない)、Summed Area Table(SAT)を実装してみました。

まぁ、いつものように適当にファイルが入っています。
APP WIZARD から出力されるフレームワークのファイルは紹介を省かせていただきます。

hlsl.fxシェーダの入ったエフェクトファイル
main.hアプリケーションのヘッダ
main.cppアプリケーションのソース

あと、実行ファイル、モデル及び、プロジェクトファイルが入っています。

■範囲総和テーブルとは

さて、今回の元資料は、NVIDIA社のGDC 2003 Presentationsのページの「Advanced OpenGL Game Programming」の項目にある「Summed Area Tables using Graphics Hardware」です。
範囲総和テーブルとは、1984年にFrank Crowが考案した積分計算したテクスチャを用いたフィルタリングの方法です。

値が1の元のテクスチャからSATを作って見ましょう。
最初に、横方向に現在のピクセルの色に、そのピクセルの左にあるピクセルの合計を足します。 この手順で、ピクセルの値は、そのピクセルのU座標の値になります。
次に、縦方向に現在のピクセルの値に、そのピクセルの上のピクセルの合計を足します。
この結果、ピクセルの値は、そのピクセルのU座標*V座標になります。
この値は、x軸とy軸に関して対称なので、実は縦方向と横方向の合成の順番を入れ替えても結果は変わりません。

例えば、32x32の大きさのSATは次のようになります(ただし、(赤、緑、青)=(3,2,1)の割合で色をつけています)。

さて、テクスチャの値は、T[U,V] = U * V になるのですが、 このテクスチャを使った計算に、次の等式が成り立ちます。

S[U+a, V+b] - S[U+a, V] - S[U, V+b] + S[U, V]
= (U+a)(V+b) - (U+a)V - U(V+b) + UV
=   UV + aV + bU + ab
 - (UV + aV)
 - (UV + bU)
 + UV
= ab

つまり、

S[U+a, V+b] - S[U+a, V] - S[U, V+b] + S[U, V] = [U+a, V+b]から[U, V]の範囲の面積

が成り立ちます。
次に、元のテクスチャの値がtUVで与えられる場合を考えて見ましょう。
この時、例えば、4x4のサイズのSATの端の値を計算すると、

S[3, 3] = t00 + t01 + t02 + t03
        + t10 + t11 + t12 + t13
        + t20 + t21 + t22 + t23
        + t30 + t31 + t32 + t33
S[3, 0] = t00 + t10 + t20 + t30
S[0, 3] = t00 + t01 + t02 + t03
S[0, 0] = t00

になるので、(U,V)=(0,0)、(a,b)=(3,3)の場合に、先ほどの計算は、

S[U+a, V+b] - S[U+a, V] - S[U, V+b] + S[U, V]
 = t11 + t12 + t13
 + t21 + t22 + t23
 + t31 + t32 + t33

となります。この値は、選択した範囲の合計なので、範囲の面積で割ると、範囲の平均値が求められます。一般化して、式としてまとめると、

(S[U+a, V+b] - S[U+a, V] - S[U, V+b] + S[U, V])/(a*b) = [U+a, V+b]から[U, V]のテクスチャの平均

と、書くことができます。
一度SATを求めてしまえば、4点をサンプリングするだけで、箱型の平均を取ることができます。
さらに、(a,b)の値は自由に取れるので、ぼかす量をピクセル単位に自由に調整することも簡単にできます。

■範囲総和テーブルの作成

SATは、浮動小数点数バッファが使えるようになって初めて実現できた手法です。
今回使用するのは、IEEE フォーマットの一番贅沢なD3DFMT_A32B32G32R32Fです。
これ以外のD3DFMT_A16B16G16R16F等のフォーマットでは、精度が不足して十分な結果が得られませんでした(GeForce FXでどのような結果が得られるのかはわかりませんが(缶持ってる人ためして~))。
ということで、最初にするのは、レンダリングターゲットを確保することです。
浮動小数点数のレンダリングターゲットを作成します。

main.cpp
0262:     // レンダリングターゲットの生成
0263:     if (FAILED(m_pd3dDevice->CreateDepthStencilSurface(MAP_WIDTH, MAP_HEIGHT, 
0264:         D3DFMT_D16, D3DMULTISAMPLE_NONE, 0, TRUE, &m_pMapZ, NULL)))
0265:         return E_FAIL;
0266:     // SAT
0267:     if (FAILED(m_pd3dDevice->CreateTexture(MAP_WIDTH, MAP_HEIGHT, 1,
0268:         D3DUSAGE_RENDERTARGET, D3DFMT_A32B32G32R32F, D3DPOOL_DEFAULT, &m_pSatTex, NULL)))
0269:         return E_FAIL;
0270:     if (FAILED(m_pSatTex->GetSurfaceLevel(0, &m_pSatSurf)))
0271:         return E_FAIL;

描画の最初の手順は元になる画像を作成することです。
基本的には、環境マップ作成時のように、レンダリングターゲットを切り替えて、普通に描画します。

main.cpp
0029: // 長いから短縮形を作ってみた
0030: #define RS   m_pd3dDevice->SetRenderState
0031: #define TSS  m_pd3dDevice->SetTextureStageState
0032: #define SAMP m_pd3dDevice->SetSamplerState
0362:         //-----------------------------------------------------
0363:         // レンダリングターゲットの保存
0364:         //-----------------------------------------------------
0365:         m_pd3dDevice->GetRenderTarget(0, &pOldBackBuffer);
0366:         m_pd3dDevice->GetDepthStencilSurface(&pOldZBuffer);
0367:         m_pd3dDevice->GetViewport(&oldViewport);
0368: 
0369:         //-----------------------------------------------------
0370:         // レンダリングターゲットの変更
0371:         //-----------------------------------------------------
0372:         m_pd3dDevice->SetRenderTarget(0, m_pSatSurf);
0373:         m_pd3dDevice->SetDepthStencilSurface(m_pMapZ);
0374:         // ビューポートの変更
0375:         D3DVIEWPORT9 viewport = {0,0 // 左上の座標
0376:                         , MAP_WIDTH  // 幅
0377:                         , MAP_HEIGHT // 高さ
0378:                         , 0.0f,1.0f};// 前面、後面
0379:         m_pd3dDevice->SetViewport(&viewport);
0380: 
0381:         // クリア
0382:         m_pd3dDevice->Clear(0L, NULL
0383:                         , D3DCLEAR_TARGET | D3DCLEAR_ZBUFFER
0384:                         , 0, 1.0f, 0L);

普通に描画

0410:         m_pd3dDevice->EndScene();

さて、いよいよSTAの作成です。
今回は、x方向のぼかしのために、縦線をテクスチャのサイズの数だけ引き、 隣のピクセルを加算することで、その左にあるピクセルの合計を計算しました。
y方向のぼかしには、横線を同じように引きます。

基本的には、前の線の描画の完了を待たなくてはいけないので、BeginScene/EndSceneで描画の終了を待ちます。
いちいち頂点情報を作成していますが、頂点バッファを用意しておいて描画すると早くなるかもしれませんね。

main.cpp
0412:         // ----------------------------------------------------
0413:         // SAT 計算
0414:         // ----------------------------------------------------
0415:         RS( D3DRS_ZENABLE, FALSE );
0416:         RS( D3DRS_LIGHTING, FALSE );
0417: 
0418:         TSS(0,D3DTSS_COLOROP,   D3DTOP_SELECTARG1);
0419:         TSS(0,D3DTSS_COLORARG1, D3DTA_TEXTURE);
0420:         TSS(1,D3DTSS_COLOROP,   D3DTOP_ADD);
0421:         TSS(1,D3DTSS_COLORARG1, D3DTA_CURRENT);
0422:         TSS(1,D3DTSS_COLORARG2, D3DTA_TEXTURE);
0423:         TSS(2,D3DTSS_COLOROP,   D3DTOP_DISABLE);
0424: 
0425:         m_pEffect->SetTechnique( m_hTechnique );
0426:         m_pEffect->Begin( NULL, 0 );
0427:         m_pd3dDevice->SetVertexDeclaration( m_pDecl );
0428:         m_pEffect->SetTexture(m_htSrcMap, m_pSatTex );
0429: 
0430:         m_pEffect->Pass( 0 );
0431:         for(i=0;i<MAP_WIDTH;i++){
0432:             FLOAT dx = (1.0f/MAP_WIDTH);
0433:             VERTEX Vertex[4] = {
0434:                 //       x                y     z        tu       tv
0435:                 {{ -1+2.0f*dx*(FLOAT)i, +1.0f, 0.1f}, dx*(FLOAT)i, 0,},
0436:                 {{ -1+2.0f*dx*(FLOAT)i, -1.0f, 0.1f}, dx*(FLOAT)i, 1,},
0437:             };
0438:             m_pd3dDevice->BeginScene();
0439:             m_pd3dDevice->DrawPrimitiveUP( D3DPT_LINELIST, 1, Vertex, sizeof( VERTEX ) );
0440:             m_pd3dDevice->EndScene();
0441:         }
0442:         m_pEffect->Pass( 1 );
0443:         for(i=0;i<MAP_HEIGHT;i++){
0444:             FLOAT dy = (1.0f/MAP_WIDTH);
0445:             VERTEX Vertex[4] = {
0446:                 //   x            y              z     tu    tv
0447:                 {{ -1.0f,  +1-2.0f*dy*(FLOAT)i, 0.1f}, 0, dy*(FLOAT)i },
0448:                 {{ +1.0f,  +1-2.0f*dy*(FLOAT)i, 0.1f}, 1, dy*(FLOAT)i },
0449:             };
0450:             m_pd3dDevice->BeginScene();
0451:             m_pd3dDevice->DrawPrimitiveUP( D3DPT_LINELIST, 1, Vertex, sizeof( VERTEX ) );
0452:             m_pd3dDevice->EndScene();
0453:         }
0454:         m_pEffect->End();

頂点シェーダでは、頂点位置のテクセルと、1つとなりのテクセルをテクスチャ座標として指定して出力します。
テクセル中心をテクスチャ座標にきちんと合わせて出力します。

hlsl.fx
0047: // -------------------------------------------------------------
0048: // 頂点シェーダプログラム
0049: // -------------------------------------------------------------
0050: VS_OUTPUT VS_sat_x (
0051:       float4 Pos    : POSITION,          // モデルの頂点
0052:       float4 Tex    : TEXCOORD0          // テクスチャ座標
0053: ){
0054:     VS_OUTPUT Out = (VS_OUTPUT)0;        // 出力データ
0055:     
0056:     // 位置座標
0057:     Out.Pos = Pos;
0058:     
0059:     Out.Tex0 = Tex + float2( 0.5f/MAP_WIDTH, 0.5f/MAP_HEIGHT );
0060:     Out.Tex1 = Tex + float2(-0.5f/MAP_WIDTH, 0.5f/MAP_HEIGHT );
0061:     
0062:     return Out;
0063: }

ピクセルシェーダでは、レンダリングターゲット自身をテクスチャとして、 それぞれのテクセルを読み出します。
今回のプログラムでは、誤差を減らすように、色の値0.5を中心に上下に平等に値が変化するようにしました。

hlsl.fx
0083: // -------------------------------------------------------------
0084: // ピクセルシェーダプログラム
0085: // -------------------------------------------------------------
0086: float4 PS_sat(VS_OUTPUT In) : COLOR
0087: {   
0088:     float4 Color;
0089:     
0090:     Color  = tex2D( SrcSamp, In.Tex0 ) + tex2D( SrcSamp, In.Tex1 );
0091:     
0092:     return Color-0.5f;
0093: }

y軸方向のぼかしの場合には、ずらす位置を変えるように頂点シェーダを変更します。
頂点データを元から持っておけば、シェーダを切り替えることなく(固定機能も使えるでしょう)実行することもできるでしょう。

hlsl.fx
0065: // -------------------------------------------------------------
0066: // 頂点シェーダプログラム
0067: // -------------------------------------------------------------
0068: VS_OUTPUT VS_sat_y (
0069:       float4 Pos    : POSITION,          // モデルの頂点
0070:       float4 Tex    : TEXCOORD0          // テクスチャ座標
0071: ){
0072:     VS_OUTPUT Out = (VS_OUTPUT)0;        // 出力データ
0073:     
0074:     // 位置座標
0075:     Out.Pos = Pos;
0076:     
0077:     Out.Tex0 = Tex + float2( 0.5f/MAP_WIDTH, 0.5f/MAP_HEIGHT );
0078:     Out.Tex1 = Tex + float2( 0.5f/MAP_WIDTH,-0.5f/MAP_HEIGHT );
0079:     
0080:     return Out;
0081: }

この工程の結果、SATは、次のような画像になります(浮動小数点数バッファの値をそのまま出力しているので、値が1より大きな部分は飽和しています)。

■範囲総和テーブルを使ったぼかし

SATができたら、それを使ってぼかした画像を使います。
基本的には、レンダリングターゲットをフレームバッファに戻してから、四角形を描画するだけです。

0456:         //-----------------------------------------------------
0457:         // レンダリングターゲットを元に戻す
0458:         //-----------------------------------------------------
0459:         m_pd3dDevice->SetRenderTarget(0, pOldBackBuffer);
0460:         m_pd3dDevice->SetDepthStencilSurface(pOldZBuffer);
0461:         m_pd3dDevice->SetViewport(&oldViewport);
0462:         pOldBackBuffer->Release();
0463:         pOldZBuffer->Release();
0464:     }
0465:     if( SUCCEEDED( m_pd3dDevice->BeginScene() ) )
0466:     {
0467:         // バッファのクリア
0468:         m_pd3dDevice->Clear( 0L, NULL
0469:                         , D3DCLEAR_TARGET|D3DCLEAR_ZBUFFER
0470:                         , 0x00404080, 1.0f, 0L );
0471: 
0472:         if( m_pEffect != NULL ) 
0473:         {
0474:             //-------------------------------------------------
0475:             // シェーダの設定
0476:             //-------------------------------------------------
0477:             m_pEffect->SetTechnique( m_hTechnique );
0478:             m_pEffect->Begin( NULL, 0 );
0479:             m_pEffect->Pass( 2 );
0480: 
0481:             TSS(0,D3DTSS_COLOROP,   D3DTOP_SELECTARG1);
0482:             TSS(0,D3DTSS_COLORARG1, D3DTA_TEXTURE);
0483:             TSS(1,D3DTSS_COLOROP,    D3DTOP_DISABLE);
0484: 
0485:             VERTEX Vertex[4] = {
0486:                 //   x      y     z      tu tv
0487:                 {{  1.0f, -1.0f, 0.1f},   1, 1,},
0488:                 {{ -1.0f, -1.0f, 0.1f},   0, 1,},
0489:                 {{ -1.0f,  1.0f, 0.1f},   0, 0,},
0490:                 {{  1.0f,  1.0f, 0.1f},   1, 0,},
0491:             };
0492:             m_pd3dDevice->SetVertexDeclaration( m_pDecl );
0493:             m_pEffect->SetTexture(m_htSrcMap, m_pSatTex );
0494:             m_pd3dDevice->DrawPrimitiveUP( D3DPT_TRIANGLEFAN
0495:                             , 2, Vertex, sizeof( VERTEX ) );
0496: 
0497:             m_pEffect->End();
0498:         }

今回は、40x40テクセル分をぼかして出力します。
頂点シェーダでは、テクセルの上下左右の隅のテクセルを指定します。

hlsl.fx
0101: // -------------------------------------------------------------
0102: // 頂点シェーダプログラム
0103: // -------------------------------------------------------------
0104: VS_OUTPUT VS_out (
0105:       float4 Pos    : POSITION,          // モデルの頂点
0106:       float4 Tex    : TEXCOORD0          // テクスチャ座標
0107: ){
0108:     VS_OUTPUT Out = (VS_OUTPUT)0;        // 出力データ
0109:     
0110:     // 位置座標
0111:     Out.Pos = Pos;
0112:     
0113:     Out.Tex0 = Tex + float2( - 19.5f/MAP_WIDTH, -19.5f/MAP_HEIGHT );
0114:     Out.Tex1 = Tex + float2( - 19.5f/MAP_WIDTH, +20.5f/MAP_HEIGHT );
0115:     Out.Tex2 = Tex + float2( + 20.5f/MAP_WIDTH, -19.5f/MAP_HEIGHT );
0116:     Out.Tex3 = Tex + float2( + 20.5f/MAP_WIDTH, +20.5f/MAP_HEIGHT );
0117:     
0118:     return Out;
0119: }

ピクセルシェーダでは、公式に沿ってテクセルをサンプリングすると共に、 サンプリングした範囲の面積で結果を割ります。
最後に、差っぴいた0.5の分を加えるのを忘れないようにしましょう。

hlsl.fx
0121: // -------------------------------------------------------------
0122: // ピクセルシェーダプログラム
0123: // -------------------------------------------------------------
0124: float4 PS_out(VS_OUTPUT In) : COLOR
0125: {   
0126:     float4 Color;
0127:     
0128:     Color  =( tex2D( SrcSamp, In.Tex0 )
0129:             - tex2D( SrcSamp, In.Tex1 )
0130:             - tex2D( SrcSamp, In.Tex2 )
0131:             + tex2D( SrcSamp, In.Tex3 ))/(40.0f*40.0f);
0132: 
0133:     return Color+0.5f;
0134: }

■最後に

さすがに何度もBeginScene/EndSceneしてるので、重いですね。 重いと思っていたガウスフィルタよりも重たいです…
でも、積分計算してると思えばバク速の範囲でしょうか。

今回のプログラムは、不動小数点数バッファを使いますが、シェーダ自体はvs_1_1、ps_1_1で可能になっています。
結局はポストエフェクトなので、描画順序に依存するような処理に使うのは難しそうですね。
ということで、アンチエイリアスに使うのは難しい気がしますが…





もどる

imagire@gmail.com