Summed Area Table

コンピュートシェーダーに興味が出てきたので,練習がてらSummed Area Table作成してブラーをかけてみます。

https://docs.nvidia.com/gameworks/content/gameworkslibrary/graphicssamples/d3d_samples/d3dcomputefiltersample.htm

https://www.slideshare.net/egorodet/cpu-is-in-focus-again-implementing-dof-on-cpu

Summed Area Tableとは,テクスチャのテクセル ${t_{xy}}$ と表したときに,以下のようにX方向,Y方向に順番に和を取っていったテーブルのことです

${ \displaystyle \begin{eqnarray} T_{xy} = \sum_{i\leq x} \sum_{j\leq y} t_{ij} \end{eqnarray} }$

f:id:hikita12312:20171105202149p:plain:w400

Summed Area Tableを作成しておくと,テーブルから4点フェッチして重みを工夫してサンプルするだけで, 元のテクスチャの任意の矩形範囲内部のピクセルの積分が計算できます。

f:id:hikita12312:20171105202836p:plain:w300

${ \displaystyle \begin{eqnarray} I(x_1,y_1,x_2,y_2) = \frac{T_{x_2y_2} - T_{x_1y_2} - T_{x_2y_1} + T_{x_1y_1}}{(x_2-x_1)(y_2-y_1)} \end{eqnarray} }$

テーブルさえ作ってしまえば,どんな積分範囲であっても高速に計算ができるので, 被写界深度処理のようなピクセルによってブラー範囲(=積分範囲)を変えるというケースで特に有効かもしれません。

ただし,Summed Area Table自体の作成するときに, 全ピクセルに対して依存するピクセルの総和と計算しておく必要があるので,この計算コストが問題となります。

Summed Area Tableの作成

Summed Area Tableの作成には,Compute Shaderを利用しました。
実際のシェーダーコードとCPU側のソースは次のような感じです。

//// HLSL側のCompute Shader
Texture2D<float4> g_SrcTexture : register(t0);
SamplerState g_LinearSampler : register(s0);
RWTexture2D<float4> g_DstTexture : register(u0);
#define    PIXEL_SIZE g_aTemp[0].xy
groupshared float3 s_aTempBuffer[LENGTH];

[numthreads(LENGTH, 1, 1)]
void CS_CreateTable(uint3 position : SV_DispatchThreadID)
{
    const uint bufferId = position.x;
#ifdef PASS_1ST
    // 水平パス
    const uint2 texturePos = position.xy;
#endif
#ifdef PASS_2ND
    // 垂直パス
    const uint2 texturePos = position.yx;
#endif
        // テクスチャの読み込み
    s_aTempBuffer[bufferId] = SampleLod0(g_SrcTexture, g_LinearSampler, float2(texturePos)*PIXEL_SIZE).rgb;

    // イテレーション
    float3 addBuf;
    for (uint i = 0; i < ITERATION; ++i)
    {
        GroupMemoryBarrierWithGroupSync();
        const uint delta = (0x1 << i);
        const float3 buffer = (bufferId >= delta) ? (s_aTempBuffer[bufferId - delta]) : (0.0f);
        GroupMemoryBarrierWithGroupSync();
        s_aTempBuffer[bufferId] += buffer;

    }
    float4 ret = float4(0.0f, 0.0f, 0.0f, 1.0f);
    ret.rgb = s_aTempBuffer[bufferId];
    g_DstTexture[texturePos] = ret;
}

//// CPP側の擬似コード
// 水平方向加算
auto pPass = rPfxEffect.GetPass("SummedAreaTableCreate", "L512_1ST").lock();
auto pTempBuffer = rPfxEffect.GetTempTexturePool().Get(dstSize, dstSize, tableFormat, bindFlags).GetTextureView();
pPass->CSBindConstantBuffer(0, tempCB);
pPass->CSBindTexture(0, pSrcTextureView);
pPass->CSBindSampler(0, rPfxEffect.GetLinearSampler());
pPass->CSBindRWTexture(0, pTempBuffer);
result = rPfxEffect.Dispatch(pDeviceContext, pPass, 1, dstSize, 1);
// 垂直方向加算
pPass = rPfxEffect.GetPass("SummedAreaTableCreate", "L512_2ND").lock();
auto pResultTextureView = rPfxEffect.GetTempTexturePool().Get(dstSize, dstSize, tableFormat, bindFlags).GetTextureView();
pPass->CSBindConstantBuffer(0, tempCB);
pPass->CSBindTexture(0, pTempBuffer);
pPass->CSBindSampler(0, rPfxEffect.GetLinearSampler());
pPass->CSBindRWTexture(0, pResultTextureView);
result = rPfxEffect.Dispatch(pDeviceContext, pPass, 1, dstSize, 1);

このコードの要点をまとめると

X方向の加算とY方向の加算を別パスに分離
再帰的に加算をして計算量をテクスチャ幅のlogに落とす
シェーダーのグループ共有メモリを利用して,テクスチャフェッチ回数を最小限に減らす

という感じです。

何も考えずに加算をすると,テクスチャ幅 ${w}$ ]として,一つのピクセルあたり ${w}$ 回のループを回すことになります。
これを,以下の図のように2べき飛ばしで再帰的に加算をしていくことで, ${\log{(w)}}$ 回まで減らすことが可能です。

f:id:hikita12312:20171105204230p:plain:w300

この再帰計算を行うときに便利なのがgroupsharedで宣言されたグループ共有メモリです。 ${w}$ 個のスレッドを走らせるグループを ${h(=w)}$ 個作成し,それぞれのグループで ${w}$ 個のfloat3を計算バッファとして確保しておきます。
最初の一回だけこのバッファに対してテクスチャ読み出しをおこなって,あとの再帰的な加算を行うときはバッファを利用することで,テクスチャ読み出しを必要最低限に抑えます。

f:id:hikita12312:20171105205815p:plain:w600

Summed Area Tableの作成自体はVertex ShaderとPixel Shaderでも工夫をすれば可能ですが,再帰的に加算をする度にテクスチャ読み出しをするので, Compute Shaderほど高速には行なえません。 DirectX11ではグループ共有メモリは32KBまでしか利用できないので,float4で考えるとテクスチャサイズは2048が限界ということに注意が必要です。また,加算時の誤差が激しいので,32bit浮動小数テクスチャを利用しています。