XNAでエリア総和テーブルの実験

XNAでエリア総和テーブルの実験をしてみました。(まだ実験段階で、未解決の問題があります)
参考にした資料はATIの２つのpdfファイル(1, 2)です。

テクスチャのあるエリアの色の平均を求めるのに、エリア総和テーブルを使うと、かなり効率的に行えます。
（この方法のおもしろい所は、10x10の領域の平均だろうが、1000x1000の領域の平均だろうが、同じ程度の計算で済んでしまうことです。一見1000x1000の方がずっと計算が多くなりそうですが、そうはならないのがエリア総和テーブルの面白いところです。これはどういうことかというと、「100時間走った車の速度の平均を求める計算は、1時間走った車の速度の平均を求める計算の100倍時間がかかるわけではない」理由と、本質的には同じです。ようするにどちらとも、始めと終わりの車の位置を出して、引き算して、時間で割ってやるだけでいいわけですからね。エリア総和テーブルを作るということは、車の速度のデータから、車の位置のデータを作り出すことと、本質的に同じです。とりあえず足しまくるのです。）

エリア総和テーブルとは、右上にあるエリアの合計を表すテーブルです。
例えばこんなテクスチャがあったとします。

2	4	1	3
1	0	2	0
0	3	0	2
2	1	0	4

すると、そのテクスチャのエリア総和テーブルはこんなんです：

2	6	7	10
3	7	10	13
3	10	13	18
5	13	16	25

テーブルの各値は、右上のエリアのテクスチャの色の合計です。

実装に関してまだ納得できないところもあるので、詳しい説明はまたの機会に一度にすることにします。
（別に説明を思いつかないわけじゃないですよ！噛み砕いた説明はもう思いついていますが、説明する本人が自信なさげだったら説得力がないじゃないですか！）

ではコードです（ちょっと引っかかるところがいくつかあるのですが・・・・・・）：
MyGame.cs

using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;

public class MyGame : Game
{
    GraphicsDeviceManager graphics;

    Texture2D texture;
    BasicEffect basicEffect;
    VertexDeclaration vertexDeclaration;

    Effect tableCreationEffect;
    RenderTarget2D renderTarget;
   

    public MyGame()
    {
        graphics = new GraphicsDeviceManager(this);
        Content.RootDirectory = "Content";
    }

    protected override void LoadContent()
    {
        //このinitTextureの引数をいろいろ変えてみることで、
        //テクスチャのサイズ（横幅）が変わり、
        //画面に表示される画像の滑らかさが変わります。
        //たとえば、initTexture(8);ならカクカクしますが、
        //initTexture(128)なら滑らかです。
        initTexture(128);

        renderTarget = new RenderTarget2D(
            GraphicsDevice,
            texture.Width, texture.Height,
            texture.LevelCount,
            SurfaceFormat.Vector4
            );

        tableCreationEffect = Content.Load<Effect>("SummedAreaTableCreator");
        basicEffect = new BasicEffect(GraphicsDevice, null);



        vertexDeclaration = new VertexDeclaration(
            GraphicsDevice,
            VertexPositionTexture.VertexElements
            );
        GraphicsDevice.VertexDeclaration = vertexDeclaration;
    }

    private void initTexture(int width)
    {
        texture = new Texture2D(
            GraphicsDevice,
            width, 1,
            1,
            TextureUsage.None,
            SurfaceFormat.Vector4
            );
        Vector4[] data = new Vector4[texture.Width * texture.Height];

        for (int i = 0; i < data.Length; i++)
            data[i] = Vector4.One / texture.Width;

        texture.SetData<Vector4>(data);
    }

    protected override void UnloadContent()
    {
        texture.Dispose();
        renderTarget.Dispose();

        basicEffect.Dispose();
        vertexDeclaration.Dispose();
    }

    protected override void Draw(GameTime gameTime)
    {
        GraphicsDevice.SetRenderTarget(0, renderTarget);
        GraphicsDevice.Clear(Color.CornflowerBlue);

        drawTexture(texture);

        createSummedAreaTable();

        GraphicsDevice.SetRenderTarget(0, null);
        GraphicsDevice.Clear(Color.CornflowerBlue);

        drawTexture(renderTarget.GetTexture());
    }

    private void createSummedAreaTable()
    {
        tableCreationEffect.Parameters["Width"].SetValue(renderTarget.Width);
        tableCreationEffect.Parameters["Height"].SetValue(renderTarget.Height);


        tableCreationEffect.Begin();

        for (int i = 0; i < System.Math.Log(texture.Width, 2); i++)
        {
            tableCreationEffect.CurrentTechnique.Passes[0].Begin();


            GraphicsDevice.SetRenderTarget(0, null);
            tableCreationEffect.Parameters["PreviousProduct"].SetValue(renderTarget.GetTexture());
            GraphicsDevice.SetRenderTarget(0, renderTarget);

            tableCreationEffect.Parameters["PassIndex"].SetValue(i);

            drawRect();


            tableCreationEffect.CurrentTechnique.Passes[0].End();
        }

        tableCreationEffect.End();

    }

    private void drawTexture(Texture2D texture)
    {
        basicEffect.TextureEnabled = true;
        basicEffect.Texture = texture;
        basicEffect.Begin();
        basicEffect.CurrentTechnique.Passes[0].Begin();

        drawRect();

        basicEffect.CurrentTechnique.Passes[0].End();
        basicEffect.End();
    }

    private void drawRect()
    {
        //四角形（テクスチャつき）の頂点
        VertexPositionTexture[] vertices = {
            new VertexPositionTexture(new Vector3(-1, 1, 0), new Vector2()),
            new VertexPositionTexture(new Vector3(1, 1, 0), new Vector2(1, 0)),
            new VertexPositionTexture(new Vector3(-1, -1, 0), new Vector2(0, 1)),
            
            new VertexPositionTexture(new Vector3(1, 1, 0), new Vector2(1, 0)),
            new VertexPositionTexture(new Vector3(1, -1, 0), new Vector2(1, 1)),
            new VertexPositionTexture(new Vector3(-1, -1, 0), new Vector2(0, 1))
        };

        GraphicsDevice.DrawUserPrimitives<VertexPositionTexture>(
            PrimitiveType.TriangleList,
            vertices,
            0,
            2
            );
    }

    static void Main()
    {
        using (MyGame game = new MyGame())
        {
            game.Run();
        }
    }
}

SummedAreaTableCreator.fx (Contentフォルダ内)

texture PreviousProduct;

sampler TextureSampler = sampler_state
{
    Texture = (PreviousProduct);
};

float Width;
float Height;
int PassIndex;


struct VertexPositionTexture
{
    float4 Position : POSITION;
    float2 TextureCoordinate : TEXCOORD;
};

VertexPositionTexture VertexShaderFunction(VertexPositionTexture input)
{
    return input;
}

float4 getColor(float2 texCoord)
{
    if(texCoord.x < 0 || texCoord.y < 0) return 0;
    else return tex2D(TextureSampler, texCoord + float2(0.5/Width, 0.5/Height));
}


float4 SumX(float2 textureCoordinate : TEXCOORD):COLOR
{
    return getColor(textureCoordinate + float2((-1/ Width) * exp2(PassIndex), 0))
        + getColor(textureCoordinate);
}


technique Technique1
{
    pass SumXPass
    {
        VertexShader = compile vs_1_1 VertexShaderFunction();
        PixelShader = compile ps_2_0 SumX();
    }
}

いきなり何かの画像のエリア総和テーブルを計算するのは難しいので、とりあえずは同じ色の詰まった1次元のテクスチャのエリア総和テーブルを作ってみました。（そのためY方向には足し算をしません）
もしうまくいけば、左から右に行くにしたがって色が足されていくので、徐々に明るくなっていき、きれいなグラデーションになるはずです。

なお、テクスチャに一番最初に入る色は、エリア総和テーブルで一番明るい色が白になるように決めました（もちろん実用では、複数のピクセルの色を足しまくるため、白より明るい色になることはしょっちゅうです。しかしそれではうまくいっているかどうか目で確認できません。テストファースト、テストファーストです）。
テクスチャのサイズはいろいろ変更することができ、大きくなればなるほど、テクスチャの最初の色は暗くなります。
これはエリア総和テーブルを作った時に、色があふれださないようにする工夫です。

ではinitTextureの引数をいろいろ変えていき、上手くいっているかのテストです。
結論を先に言うと、ビミョーですが、まあ見ていきましょう。

まずは2x1のテクスチャのエリア総和テーブルです。


なるほどうまくいっているようです。
ここでは

0.5

0.5

のテクスチャから、

0.5

1.0

のエリア総和テーブルが作られているのでしょう（多分）。
正しく実装で来ているのなら、こんな風に、これ以後も全部右端は白くなるはずです。


ここではうまくいっているようですが、もう少し大きくしてみるとどうでしょうか？
4x1を試してみます：


いやいや、おかしいよ！
どうなっているのでしょう？
グラデーションにならなきゃいけないのに、真ん中の２つが同じ色になってしまっています。
なにより右端は白じゃなくちゃいけません。

この問題はこの記事を書いている今のところ未解決です（わかる人教えてください！）。
さらに大きくすると、それほど深刻には見えなかったからです。

8x1:

左端と右端を除いた真ん中全部が同じ色になりはしないかとヒヤヒヤしましたが、杞憂でしたね。もっとも問題は全然よくなっていませんが。

16x1:

もしかしておかしくなる条件は「左にある」こと？
でもどうしてそんな・・・・・・

32x1:

右端はほとんど白です。
これを見た瞬間問題を解決しようというモチベーションがガタ落ちしました。

64x1:

こまかくなってきました。
しかし「左側問題」は相変わらず解決しません。

128x1:

いいでしょう、もうたくさんです。
これ以上大きくしても結果は変わらないでしょう。

でもいったいどうしてこんな問題が起きたのでしょう？
たぶん何かのインデックスが１つずれているとかそんなのだと思いますが・・・