How to match edges of contiguous 2D arrays and Smooth them (Heightmaps)

Question

This problem is driving me crazy, I have searched and thicked but can't achieve a solution. I have some 2D arrays of floats [,] (by the way I'm using C#), and put together always form a square. There are 1,4,9,16... arrays. Each of this 2D arrays of floats represent a heightmap, so they are 129x129, 513x513, 1025x1025... and they are all the same. I import some values to the arrays through an algorithm from a heightmap file. The heightmap is a 8 bit raw, so I get a terraced look in the heightmap because there is only 256 shades of gray. Now I use a smoothing algorithm in each array (algorithm here: http://nic-gamedev.blogspot.com.es/2013/02/simple-terrain-smoothing.html) and it looks good, BUT, it is applied to each array, so the borders between them does not match, and when implementing the arrays to the terrain, there are gaps between them.

I have thinked about various solutions, one of them joinging the arrays in one big array and smoothing it, but I dont want to use that technic because I could have a ton of terrains, and I would need a gigantinc array.

So... any idea on how to do this? Please this is my first question because I can't figure out how to do it. Ask me if you need more info, and sorry for my english.

EDIT:

Ilustration:

Answer 1

What the algorithm that you're using is doing, is not looking outside the 2D array (let's call it a "block" from now on) it is smoothing (these are the if ((x - 1) > 0) // Check to left conditions).
Sure this prevents array index of of bounds errors, and for a block that doesn't have any neighbours this is fine, but not if you want the block to blend in with its neighbours.

The solution is quite straightforward really: If you want the edges of your blocks to blend smoothly with its neighbouring blocks, you'll have to use them when smoothing a block.
That is, you can still limit the values that you're smoothing to one block, but you have to be able to read the edges of its neighbouring blocks to calculate the proper averages.

I hope that this explanation is clear enough, if not just let me know and I'll write a little sample code.

By the way, the smoothing algorithm described on the blog you reffered to is implemented rather crudely. Instead of using multiple passes with a 3x3 convolution filter, you could try a single, larger filter. I found this page (see the first few paragraphs, upto "Alpha channel") to explain it quite well, although it is in java.

---

Allright, I've cooked up some sample code. One word of warning: I treat my 2d arrays as row-major, i.e. myArray[y, x], but I declare my indexer properties as [x, y].

First, lets create a class for Block, this allows for some helper methods and makes it easy to see in the rest of the code where we're dealing with a Block:

public class Block
{
    public const int Size = 8;

    private float[,] _values;

    public float this[int x, int y]
    {
        get { return _values[y, x]; }
        set { _values[y, x] = value; }
    }

    public Block(float value)
    {
        //Initialize all cells with the given value, this makes it easier to demo the code.
        _values = new float[Size, Size];
        for (int y = 0; y < Size; y++)
        {
            for (int x = 0; x < Size; x++)
                _values[y, x] = value;
        }
    }

    public string[] TextLines
    {
        get
        {
            List<string> lines = new List<string>();
            for (int y = 0; y < Size; y++)
            {
                StringBuilder sbLine = new StringBuilder();
                for (int x = 0; x < Size; x++)
                    sbLine.AppendFormat("{0:00} ", _values[y, x]);

                lines.Add(sbLine.ToString());
            }

            return lines.ToArray();
        }
    }
}

Next, we'll define an abstraction layer that will allow us to handle 3x3 Blocks as if it were one large area. Coordinates range from -8 to 15 inclusive.

/// <summary>
/// Wrapper around 3x3 Blocks, allows reading from a range of [-8, 15] x [-8, 15].
/// Not that writing is not supported.
/// </summary>
public class BlockContainer
{
    private Block[,] _blocks;

    public const float DefaultValue = 128;

    public float this[int x, int y]
    {
        get
        {
            int blockX = 1, blockY = 1;

            //If the coordinates exceed the center Block, move to the adjacent Block.
            if (x < 0)
            {
                blockX--;
                x += Block.Size;
            }
            else if (x >= Block.Size)
            {
                blockX++;
                x -= Block.Size;
            }

            if (y < 0)
            {
                blockY--;
                y += Block.Size;
            }
            else if (y >= Block.Size)
            {
                blockY++;
                y -= Block.Size;
            }

            //Get the Block to read from - if there is no Block, just return the DefaultValue.
            //This is not ideal, but for now it works.
            Block block = _blocks[blockY, blockX];
            return (block != null) 
                ? block[x, y] 
                : DefaultValue;        
        }
    }

    public BlockContainer(Block[,] blocks)
    {
        if (blocks == null || blocks.GetLength(0) != 3 || blocks.GetLength(1) != 3)
            throw new ArgumentException("Expected 3x3 Blocks.");        

        _blocks = blocks;
    }
}

And finally, the (Console) program that defines 4x2 Blocks as a terrain, and smooths 1 Block using these classes:

class Program
{
    private const float OneNinth = 1.0f / 9;

    /// <summary>
    /// Simple convolution filter that does a rectangle blur.
    /// </summary>
    private static float[,] Filter = new float[,]
    {
        {OneNinth, OneNinth, OneNinth},
        {OneNinth, OneNinth, OneNinth},
        {OneNinth, OneNinth, OneNinth},
    };

    /// <summary>
    /// Simple 4x2 terrain example. For demo purposes, each block consists of only 1 value.
    /// </summary>
    private static Block[,] Terrain = new Block[,]
    {
        { new Block(8f), new Block(16f), new Block(24f), new Block(32f) },
        { new Block(8f), new Block(32f), new Block(16f), new Block(8f) },
    };

    public static void Main(string[] args)
    {
        BlockContainer container = GetBlockContainer(2, 0);    //The Block with only 24f values.
        Block result = Apply3x3Filter(Filter, container);

        Console.WriteLine(string.Join(Environment.NewLine, result.TextLines));

        Console.WriteLine("Press enter to exit...");
        Console.ReadLine();
    }

    /// <summary>
    /// Gets the 3x3 Block area around (terrainX, terrainY) as a BlockContainer.
    /// </summary>
    private static BlockContainer GetBlockContainer(int terrainX, int terrainY)
    {
        Block[,] readBlocks = new Block[3, 3];
        for (int blockY = -1; blockY <= 1; blockY++)
        {
            for (int blockX = -1; blockX <= 1; blockX++)
            {
                int sourceX = terrainX + blockX;
                int sourceY = terrainY + blockY;

                if (sourceX >= 0 && sourceX < 4 && sourceY >= 0 && sourceY < 2)
                    readBlocks[blockY + 1, blockX + 1] = Terrain[sourceY, sourceX];
            }
        }

        return new BlockContainer(readBlocks);
    }

    private static Block Apply3x3Filter(float[,] filter, BlockContainer container)
    {
        Block resultBlock = new Block(0.0f);
        for (int y = 0; y < Block.Size; y++)
        {
            for (int x = 0; x < Block.Size; x++)
            {
                //Read the 3x3 area around (x, y) and multiply them with the values in the 
                //convolution filter.
                float sum = 0.0f;
                for (int fy = -1; fy <= 1; fy++)
                {
                    for (int fx = -1; fx <= 1; fx++)
                        sum += (container[x + fx, y + fy] * filter[fy + 1, fx + 1]);
                }

                //The sum is our averaged value for (x, y).
                resultBlock[x, y] = sum;
            }
        }

        return resultBlock;
    }
}

The output is:

57 59 59 59 59 59 59 60
21 24 24 24 24 24 24 27
21 24 24 24 24 24 24 27
21 24 24 24 24 24 24 27
21 24 24 24 24 24 24 27
21 24 24 24 24 24 24 27
21 24 24 24 24 24 24 27
21 21 21 21 21 21 21 22
Press enter to exit...

Which can be explained by that it has the Blocks with 16f to the left and below it, and 32f to the right of it. There is no Block above it, but we defined DefaultValue as 128, hence the average of 59.

I hope this explains things :) If you have any questions, just let me know.