Fix/Improve Chunk Mesh Building

[bonesoul]

Voxeliq currently uses an advanced optimization to improve rendering performance, in simple worlds while building the mesh for a chunk, instead of building the complete mesh for the chunk, it only builds it partially (basically it doesn't include blocks in the mesh where user can't seem them).

Check this graphic;

So lets say that a chunk may had landscape generated around y=50 ~ y=55.

• So with out the optimization, the mesh would contain all the blocks from y=0 to to y=55
• which means more blocks in the mesh = more polygons in the mesh = lower rendering performance.

So the ideas is that, user will not able to see blocks below the lowest-solid-block-index(y) in chunk.

As in the screenshot above, users will not be able to see blocks below the [chunk's lowest block index - 1](marked with purple).

And the optimization arrives here, where we only build the mesh between [chunks highest block index + 1] to [chunks lowest block index -1].

This optimization is all good and improves the rendering performance a lot but with a given drawback; with every set-block operation, chunk's highest block index and lowest block index values have to be updated.

In the current state of the engine, this is done in landscape-generation after every block-set operation;

air (empty) blocks
                    BlockStorage.Blocks[offset + y] = new Block(BlockType.None);
                    if (chunk.LowestEmptyBlockOffset > y) chunk.LowestEmptyBlockOffset = (byte)y;

---
(solid blocks)
                    BlockStorage.Blocks[offset + y] = new Block(BlockType.Dirt);
                    if (y > chunk.HighestSolidBlockOffset) chunk.HighestSolidBlockOffset = (byte)y;

The problem is that this is an engine and forcing game-developers for so, will increase the entry barrier of engine higher and will make things complex.

A solution is that using the available SetBlock methods which can find the chunk block belongs to and do the calculation on it's own.

        public static void SetBlockAt(int x, int y, int z, Block block)

The problem is that setting blocks in a block-engine is an operation used millions of times. The current method we use in first code snippet is automatic (or close enough being atomic at least in our context - as it just sets a byte value in our Flatten Block Storage array).

The latter solution in second snippet means calling that SetBlockAt() functions over and over millions of times, which for sure will decrease the performance a lot - here's a proof of concept test; http://www.dotnetperls.com/inline-optimization

So I've been looking for possible solutions and here's what I've came up with;

Statement Lamdas As I've discussed it here and they maybe a solution but I'm not sure yet, will check it further & profile.

Conventional way:
-----------------
L_0000: nop 
L_0001: ldarg.0 
L_0002: ldarg.1 
L_0003: ldarg.2 
L_0004: ldarg.3 
L_0005: call int32 VolumetricStudios.VoxeliqGame.Chunks.BlockCache::BlockIndexByRelativePosition(class VolumetricStudios.VoxeliqGame.Chunks.Chunk,
 uint8, uint8, uint8)

Statement Lambdas:
------------------
L_0000: nop 
L_0001: ldsfld class [mscorlib]System.Func5<class VolumetricStudios.VoxeliqGame.Chunks.Chunk, uint8, uint8, uint8,
 int32> VolumetricStudios.VoxeliqGame.Chunks.BlockCache::BlockIndexByRelativePosition3
L_0006: ldarg.0 
L_0007: ldarg.1 
L_0008: ldarg.2 
L_0009: ldarg.3 
L_000a: callvirt instance !4 [mscorlib]System.Func`5<class VolumetricStudios.VoxeliqGame.Chunks.Chunk, uint8, uint8, uint8, int32>::Invoke(!0, !1, !2, !3)

The second solution is MethodImplOptions.AggressiveInlining that was introduced with .net framework 4.5. But I'm not sure if we'll be able to change our engine projects framework version to 4.5. Will also try that.

I'm looking for other possible solutions.

Interesting reads on the topic;

• http://blogs.msdn.com/b/ericgu/archive/2004/01/29/64644.aspx

[bonesoul]

I've further started inspecting the issue.

• Will be using a custom version of BiomedTerrain.cs.
• Base code will be; https://github.com/raistlinthewiz/voxeliq/commit/212af471920d7bbbb1dddbe9e392534d753c59e7
• Nothing will be changed on the code except the inlined stuff.
• Will get IL decompiled and will also test with DotTrace 5.3 for the performance.
• Test will run on FlatDebugTerrain:GenerateBlocks() and total-run-time value for the function will be used.
• XNA,MonoGameGL will be used.

DotTrace 5.3 settings;

• Profiling type: Tracing
• Measure: Thread cycle time

[bonesoul]

Manually inlined version - WITH OFFSET CALCULATION OPTIMIZATION

Note that: This initial version only calculates offset once in the loop, where as other tests doesn't have the optimization. I'll be also posting a manually inlined version test without the offset-calculation-trick.

BiomedTerrain.GenerateBlocks()

code: https://github.com/raistlinthewiz/voxeliq/commit/212af471920d7bbbb1dddbe9e392534d753c59e7

        protected virtual void GenerateBlocks(Chunk chunk, int worldPositionX, int worldPositionZ)
        {
            float dirtHeight = this.GetRockHeight(worldPositionX, worldPositionZ);
            var offset = BlockStorage.BlockIndexByWorldPosition(worldPositionX, worldPositionZ);
            for (int y = (int)Chunk.MaxHeightIndexInBlocks; y >= 0; y--)
            {
                if ((float)y > dirtHeight)
                {
                    BlockStorage.Blocks[offset + y] = new Block(BlockType.None);
                    if ((int)chunk.LowestEmptyBlockOffset > y)
                    {
                        chunk.LowestEmptyBlockOffset = (byte)y;
                    }
                }
                else
                {
                    BlockStorage.Blocks[offset + y] = new Block(BlockType.Dirt);
                    if (y > (int)chunk.HighestSolidBlockOffset)
                    {
                        chunk.HighestSolidBlockOffset = (byte)y;
                    }
                }
            }
        }

[bonesoul]

Statement Lambda Tests;

protected virtual void GenerateBlocks(Chunk chunk, int worldPositionX, int worldPositionZ)
        {
            var dirtHeight = this.GetRockHeight(worldPositionX, worldPositionZ);

            for (int y = Chunk.MaxHeightIndexInBlocks; y >= 0; y--)
            {
                if (y > dirtHeight) // air
                {
                    SetBlock(chunk, worldPositionX, y, worldPositionZ, BlockType.None);
                }
                else // dirt level
                {
                    SetBlock(chunk, worldPositionX, y, worldPositionZ, BlockType.Dirt);
                }
            }
        }
        private Action<Chunk, int, int, int, BlockType> SetBlock = (Chunk chunk, int x, int y, int z, BlockType type) =>
        {
            var offset = BlockStorage.BlockIndexByWorldPosition(x, z);
            BlockStorage.Blocks[offset + y] = new Block(type);

            if ((type != BlockType.None) && (y > chunk.HighestSolidBlockOffset))
                chunk.HighestSolidBlockOffset = (byte)y;
            else if ((type == BlockType.None) && (chunk.LowestEmptyBlockOffset > y))
                chunk.LowestEmptyBlockOffset = (byte)y;
        };

[bonesoul]

Normal function tests

protected virtual void GenerateBlocks(Chunk chunk, int worldPositionX, int worldPositionZ)
        {
            var dirtHeight = this.GetRockHeight(worldPositionX, worldPositionZ);

            for (int y = Chunk.MaxHeightIndexInBlocks; y >= 0; y--)
            {
                if (y > dirtHeight) // air
                {
                    SetBlock(chunk, worldPositionX, y, worldPositionZ, BlockType.None);
                }
                else // dirt level
                {
                    SetBlock(chunk, worldPositionX, y, worldPositionZ, BlockType.Dirt);
                }
            }
        }
        private void SetBlock(Chunk chunk, int x, int y, int z, BlockType type)
        {
            var offset = BlockStorage.BlockIndexByWorldPosition(x, z);
            BlockStorage.Blocks[offset + y] = new Block(type);

            if ((type != BlockType.None) && (y > chunk.HighestSolidBlockOffset))
                chunk.HighestSolidBlockOffset = (byte)y;
            else if ((type == BlockType.None) && (chunk.LowestEmptyBlockOffset > y))
                chunk.LowestEmptyBlockOffset = (byte)y;
        }

[bonesoul]

.net 4.5 / [MethodImpl(MethodImplOptions.AggressiveInlining)]

protected virtual void GenerateBlocks(Chunk chunk, int worldPositionX, int worldPositionZ)
        {
            var dirtHeight = this.GetRockHeight(worldPositionX, worldPositionZ);

            for (int y = Chunk.MaxHeightIndexInBlocks; y >= 0; y--)
            {
                if (y > dirtHeight) // air
                {
                    SetBlock(chunk, worldPositionX, y, worldPositionZ, BlockType.None);
                }
                else // dirt level
                {
                    SetBlock(chunk, worldPositionX, y, worldPositionZ, BlockType.Dirt);
                }
            }
        }
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private void SetBlock(Chunk chunk, int x, int y, int z, BlockType type)
        {
            var offset = BlockStorage.BlockIndexByWorldPosition(x, z);
            BlockStorage.Blocks[offset + y] = new Block(type);

            if ((type != BlockType.None) && (y > chunk.HighestSolidBlockOffset))
                chunk.HighestSolidBlockOffset = (byte)y;
            else if ((type == BlockType.None) && (chunk.LowestEmptyBlockOffset > y))
                chunk.LowestEmptyBlockOffset = (byte)y;
        }

[bonesoul]

.net 4.0 / [MethodImpl(MethodImplOptions.NoInlining)]

protected virtual void GenerateBlocks(Chunk chunk, int worldPositionX, int worldPositionZ)
        {
            var dirtHeight = this.GetRockHeight(worldPositionX, worldPositionZ);

            for (int y = Chunk.MaxHeightIndexInBlocks; y >= 0; y--)
            {
                if (y > dirtHeight) // air
                {
                    SetBlock(chunk, worldPositionX, y, worldPositionZ, BlockType.None);
                }
                else // dirt level
                {
                    SetBlock(chunk, worldPositionX, y, worldPositionZ, BlockType.Dirt);
                }
            }
        }
        [MethodImpl(MethodImplOptions.NoInlining)]
        private void SetBlock(Chunk chunk, int x, int y, int z, BlockType type)
        {
            var offset = BlockStorage.BlockIndexByWorldPosition(x, z);
            BlockStorage.Blocks[offset + y] = new Block(type);

            if ((type != BlockType.None) && (y > chunk.HighestSolidBlockOffset))
                chunk.HighestSolidBlockOffset = (byte)y;
            else if ((type == BlockType.None) && (chunk.LowestEmptyBlockOffset > y))
                chunk.LowestEmptyBlockOffset = (byte)y;
        }

[bonesoul]

Vanilla version without the offset-optimization

        protected virtual void GenerateBlocks(Chunk chunk, int worldPositionX, int worldPositionZ)
        {
            float dirtHeight = this.GetRockHeight(worldPositionX, worldPositionZ);
            for (int y = (int)Chunk.MaxHeightIndexInBlocks; y >= 0; y--)
            {
                var offset = BlockStorage.BlockIndexByWorldPosition(worldPositionX, worldPositionZ);
                if ((float)y > dirtHeight)
                {
                    BlockStorage.Blocks[offset + y] = new Block(BlockType.None);
                    if ((int)chunk.LowestEmptyBlockOffset > y)
                    {
                        chunk.LowestEmptyBlockOffset = (byte)y;
                    }
                }
                else
                {
                    BlockStorage.Blocks[offset + y] = new Block(BlockType.Dirt);
                    if (y > (int)chunk.HighestSolidBlockOffset)
                    {
                        chunk.HighestSolidBlockOffset = (byte)y;
                    }
                }
            }
        }

[bonesoul]

I've came up with a good idea; CalculateHeightIndexes() method which will be called by chunk builders before actual mesh building starts which will automatically calculate HighestSolidBlockOffset and LowestEmptyBlockOffset for the chunk. - https://github.com/raistlinthewiz/voxeliq/commit/9ced7e110ef9c5d34579f2d515c87d52a9fe1d72

[bonesoul]

I've implemented the idea and now it all works good. And this optimization was all about;

Who wants to build all the mesh for the chunks?

Voxeliq will optimize out your chunk meshes:)