Something other than Vertex Welding with Texture Atlas?

Question

What options (in C# with XNA) would there be for texture usage in a procedural generated 3D world made of cubes to increase performance? Yes, it's like Minecraft.

I've been doing a texture atlas and rendering faces individually (4 vertices per face), but I've also read in a couple places about using texture wrapping with two 1D atlases to merge adjacent faces with the same texture.

If two or more adjacent faces share the same image, it'd be quite easy to wrap in this way reducing vertices by a large amount. My problem with this is having too many textures, swapping too often, and many image related things like non-power of 2 images.

Is there a middle ground option between the 1D texture atlas trick and rendering 4 vertices per cube face?

This is a picture of what I have currently (in wireframe). 4 vertices per face seems extremely inefficient to me.

Answer 1

So I've really exceeded my time budget for this question, with my mega-answer. But here's an idea, which you can hopefully evaluate using the code I've provided in my other answer:

Basically, you have two texture coordinates per quad: One that is the same for all vertices of a given quad, to select the tile within the texture atlas. The second has coordinates that interpolate as normal for a fully-wrappable (not atlased) texture (so from 0..1 for a single tile, but extending beyond that for wrapping). You then combine those in a pixel shader to perform the wrapping.

This lets you do completely arbitrary wrapping - allowing 2D texture atlases and 2D merging of faces! Far better than the 1D atlas and 1D merging we were discussing before.

Here's a pixel-shader I threw together to do exactly that:

sampler TextureSampler : register(s0);

// Select the tile within a texture by its coordinates
// For a real implementation, you'd probably pass this in TEXCOORD1
float2 textureBase = float2(0, 0); 

// The size, in texture coordinates, of a tile
float2 tileSize = float2(1.0 / 16.0, 1.0 / 16.0);

float4 main(float4 color : COLOR0, float2 texCoord : TEXCOORD0) : COLOR0
{
    // Adjust the texture coordinate to map into a specific tile:
    texCoord = frac(texCoord) * tileSize + textureBase;

    return tex2D(TextureSampler, texCoord) * color;
}

technique TileMapRepeater
{
    pass Pass1
    {
        PixelShader = compile ps_2_0 main();
    }
}

It's tested working, although it gives seams if you don't use point-sampling. You might be able to get it to work with linear-sampling, but that's more effort and a lot more computationally expensive.

So the question would be: are extra pixel shader calculations and added vertex data worth the significant reduction in quads rendered? I'll leave it to you to figure that out :)

Answer 2

This is a performance question. So, as always, the answer is: measure it!

So this is exactly what I did:

The Y axis is time taken to render, and the X axis is the number of "faces" rendered (pre-merging).

By my own rough estimates, a "really big Minecraft vista" is somewhere around the middle of the X axis. This is all assuming reasonable culling (you're not drawing faces between solid cubes, you're not drawing the inside of caves, you're not drawing chunks behind you).

I've simplified by assuming that uniform orthographic square faces are adequate analogue to perspective-rendered faces. I've assumed full screen coverage with no overdraw, and 25% of faces are off-screen.

I've assumed BasicEffect, with VertexColorEnabled and TextureEnabled (so: a vertex buffer of VertexPositionColorTexture), is a reasonable approximation of your shader for performance purposes.

For this graph, I've guessed an average 4:1 merge ratio in a scene. And that uniform merging is a suitable approximation.

There are 6 lines on my graph. The top three are without merging faces (1 quad = 1 face). The bottom three are with faces merged (1 quad ≃ 4 faces). Each set of three tests are with different textures: a single-pixel texture, a 2D texture atlas and a 1D texture atlas. Each atlas is made up of 16-by-16 pixel tiles (like Minecraft)

Given the way the measurements are the same no matter what texture is used tells us that, on a modern graphics card (or, at least, on my graphics card), and with textures at that resolution, there's no performance downside to having a 1D texture atlas.

Of course, a major limitation on this is that XNA has a maximum texture size of 4096 (2048 in the Reach profile), which strictly limits the number of tiles you can have in a 1D atlas.

One potential work-around for this would be to have separate vertex buffers and batches for separate texture atlases. This would be a lot of additional work - so I didn't test this. In theory, this should allow you maintain this performance improvement, with limited negative impact, as long as you have the batches to spare - which may not be the case if you already rendering one batch per chunk.

And, of course, the two groups of lines on this graph tells us that merging faces gives a significant, measurable performance improvement. This performance improvement scales with the number of faces you can merge together.

This performance improvement exists even for relatively small numbers of faces, so it should still work if you have one vertex buffer per chunk - although the improvements may not be as significant. (I tested with a single vertex buffer for simplicity.)

Texture orientation may cause a reduction in the number of faces that can be merged or limit the available texture space (duplicating areas of texture should not affect performance, as texturing is not the limiting factor here). Another thing that will limit the number of faces that can be merged is lighting.

Of course, the slope of the graph tells us pretty much the same thing - and, in a more general sense - that fewer quads drawn means better performance, pretty-much linearly, no matter what method you are using to reduce the number of quads. (Note: quads cost both vertex processing time and raster time.)

So any method you have to reduce quads drawn is something you should consider implementing - whether that is face merging or culling.

At about the middle of that graph this performance optimisation represents an improvement of about 1.4% of frame time, on my GPU, at 60 FPS (the time for an entire frame at 60FPS is about 20 times higher than the visible graph area). And, again, it scales with the number of faces merged - for which I used a very generous estimate. So there's a very good chance that this performance optimisation may not provide sufficient improvement to justify the effort of its implementation.

---

Below is the code I used, which can be dropped into an empty XNA 4.0 project. You could use this for further performance experimentation.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Text;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;

namespace VertexMergeTest
{
    public class Game1 : Microsoft.Xna.Framework.Game
    {
        GraphicsDeviceManager graphics;

        public Game1()
        {
            graphics = new GraphicsDeviceManager(this);
            graphics.GraphicsProfile = GraphicsProfile.HiDef;
            graphics.PreferredBackBufferWidth = 1280;
            graphics.PreferredBackBufferHeight = 720;
            graphics.PreferMultiSampling = true; // Causes the rasterizer to do more work per polygon (subpixel sampling)
            graphics.IsFullScreen = true;

            Content.RootDirectory = "Content";

            // Unlock timer for performance measuring
            graphics.SynchronizeWithVerticalRetrace = false;
            IsFixedTimeStep = false;

            Window.AllowUserResizing = true;
            IsMouseVisible = true;
        }


        BasicEffect basicEffect;


        protected override void LoadContent()
        {
            SetupTextures();

            basicEffect = new BasicEffect(GraphicsDevice);
            basicEffect.VertexColorEnabled = true;
            basicEffect.TextureEnabled = true;

            Begin();
        }



        #region Textures

        void SetupTextures()
        {
            // Assume 16x16 tiles, arranged either 16x16 or 1x256 (note that this is the maximum texture height)
            Color[] buffer = new Color[16*16*16*16];
            for(int i = 0; i < buffer.Length; i++)
                buffer[i] = Color.White; // Assume texture contents don't affect performance

            whitePixel = new TextureInfo { texture = new Texture2D(GraphicsDevice, 1, 1), widthInTiles = 1, heightInTiles = 1 };
            whitePixel.texture.SetData(new[] { Color.White });

            twoDeeAtlas = new TextureInfo { texture = new Texture2D(GraphicsDevice, 16*16, 16*16), widthInTiles = 16, heightInTiles = 16 };
            twoDeeAtlas.texture.SetData(buffer);

            oneDeeAtlas = new TextureInfo { texture = new Texture2D(GraphicsDevice, 16*1, 16*16*16), widthInTiles = 1, heightInTiles = 16*16 };
            oneDeeAtlas.texture.SetData(buffer);
        }

        class TextureInfo
        {
            public Texture2D texture;
            public int widthInTiles, heightInTiles;


            public float TileWidthTexCoord { get { return 1f / (float)widthInTiles; } }
            public float TileHeightTexCoord { get { return 1f / (float)heightInTiles; } }

            public int TileCount { get { return widthInTiles * heightInTiles; } }

            public Vector2 GetTextureBase(int tile)
            {
                tile = tile % TileCount;
                int x = tile % widthInTiles;
                int y = tile / widthInTiles;
                return new Vector2(x * TileWidthTexCoord, y * TileHeightTexCoord);
            }
        }

        TextureInfo whitePixel, twoDeeAtlas, oneDeeAtlas;
        TextureInfo currentTexture;

        #endregion



        #region Buffers

        VertexBuffer vertexBuffer;
        IndexBuffer indexBuffer;

        void CleanupTest()
        {
            if(vertexBuffer != null)
                vertexBuffer.Dispose();
            if(indexBuffer != null)
                indexBuffer.Dispose();
            vertexCount = 0;
            indexCount = 0;
        }

        void CreateBuffers()
        {
            vertexBuffer = new VertexBuffer(GraphicsDevice, vertices.GetType().GetElementType(),
                    vertexCount, BufferUsage.WriteOnly);
            vertexBuffer.SetData(vertices, 0, vertexCount);

            indexBuffer = new IndexBuffer(GraphicsDevice, IndexElementSize.ThirtyTwoBits,
                    indexCount, BufferUsage.None);
            indexBuffer.SetData(indices, 0, indexCount);
        }

        #endregion



        #region Geometry

        VertexPositionColorTexture[] vertices = new VertexPositionColorTexture[endTestAtFaces * 4];
        int[] indices = new int[endTestAtFaces * 6];

        int vertexCount;
        int indexCount;
        int sideSize;


        void AddQuad(int x, int y, int width, int height, int tileTextureNumber)
        {
            Vector2 textureBase = currentTexture.GetTextureBase(tileTextureNumber);
            Vector2 textureWidth = new Vector2(currentTexture.TileWidthTexCoord * width, 0);
            Vector2 textureHeight = new Vector2(0, currentTexture.TileHeightTexCoord * height);


            vertices[vertexCount + 0] = new VertexPositionColorTexture
            {
                Position = new Vector3(x, y, 0),
                Color = Color.Lerp(Color.White, Color.Black, 0.1f),
                TextureCoordinate = textureBase
            };

            vertices[vertexCount + 1] = new VertexPositionColorTexture
            {
                Position = new Vector3(x, y+height, 0),
                Color = Color.Lerp(Color.White, Color.Black, 0.8f),
                TextureCoordinate = textureBase + textureHeight
            };

            vertices[vertexCount + 2] = new VertexPositionColorTexture
            {
                Position = new Vector3(x+width, y+height, 0),
                Color = Color.Lerp(Color.White, Color.Black, 0.6f),
                TextureCoordinate = textureBase + textureWidth + textureHeight
            };

            vertices[vertexCount + 3] = new VertexPositionColorTexture
            {
                Position = new Vector3(x+width, y, 0),
                Color = Color.Lerp(Color.White, Color.Black, 0.3f),
                TextureCoordinate = textureBase + textureWidth
            };


            indices[indexCount + 0] = vertexCount + 0;
            indices[indexCount + 1] = vertexCount + 1;
            indices[indexCount + 2] = vertexCount + 2;
            indices[indexCount + 3] = vertexCount + 2;
            indices[indexCount + 4] = vertexCount + 3;
            indices[indexCount + 5] = vertexCount + 0;


            vertexCount += 4;
            indexCount += 6;
        }

        #endregion



        #region Begin and End

        void Begin()
        {
            SetupTestSequence();
            WriteOutputHeader();

            facesInTest = facesPerTestIncrement;
            StartTestSequence();
        }

        void Finish()
        {
            File.WriteAllText("output.csv", outputText.ToString());

            Exit();
        }

        #endregion



        #region Test Sequence and Data Formatting

        StringBuilder outputText = new StringBuilder(8000);

        class Test
        {
            public string name;
            public Action<int> setupTest;
        }

        int currentTestNumber = 0;
        List<Test> testSequence = new List<Test>();

        void WriteOutputHeader()
        {
            // File Header
            outputText.AppendLine("Ticks per second = ," + Stopwatch.Frequency);
            outputText.AppendLine("Warmup Frames = ," + warmupFrames);
            outputText.AppendLine("Frames Per Measurement = ," + testFrames);
            outputText.AppendLine("Average Mergable Faces = ," + averageMergableFaces);
            outputText.AppendLine();

            // Column Headers
            outputText.Append("Faces");
            for(int i = 0; i < testSequence.Count; i++)
            {
                outputText.Append(',');
                outputText.Append(testSequence[i].name);
            }
        }

        void StartTestSequence()
        {
            outputText.AppendLine();
            outputText.Append(facesInTest);
            outputText.Append(',');

            currentTestNumber = 0;
            DoTestSetup(testSequence[currentTestNumber].setupTest, facesInTest);
            warmup = true;
        }

        void FinishTestAdvanceToNext(long resultTicks)
        {
            outputText.Append(resultTicks);

            if(++currentTestNumber < testSequence.Count)
            {
                // Next test in sequence
                outputText.Append(',');
                DoTestSetup(testSequence[currentTestNumber].setupTest, facesInTest);
            }
            else
            {
                // Increment face count and start the test sequence again
                facesInTest += facesPerTestIncrement;

                if(facesInTest > endTestAtFaces) // ... or finish all tests
                {
                    Finish();
                    return;
                }

                StartTestSequence();
            }

            // Start by warming up
            warmup = true;
        }


        void DoTestSetup(Action<int> setupAction, int faceCount)
        {
            CleanupTest();

            // Attempt to fill the display area with approximate squares:
            sideSize = (int)Math.Ceiling(Math.Sqrt(faceCount));

            setupAction(faceCount);

            CreateBuffers();
        }




        void SetupTestSequence()
        {
            testSequence.Add(new Test()
            {
                name = "Standard 0D",
                setupTest = (faceCount) =>
                    {
                        currentTexture = whitePixel;

                        for(int i = 0; i < faceCount; i++)
                        {
                            int x = i % sideSize;
                            int y = i / sideSize;

                            AddQuad(x, y, 1, 1, i / averageMergableFaces);
                        }
                    }
            });


            testSequence.Add(new Test()
            {
                name = "Standard 1D",
                setupTest = (faceCount) =>
                {
                    currentTexture = oneDeeAtlas;

                    for(int i = 0; i < faceCount; i++)
                    {
                        int x = i % sideSize;
                        int y = i / sideSize;

                        AddQuad(x, y, 1, 1, i / averageMergableFaces);
                    }
                }
            });


            testSequence.Add(new Test()
            {
                name = "Standard 2D",
                setupTest = (faceCount) =>
                {
                    currentTexture = twoDeeAtlas;

                    for(int i = 0; i < faceCount; i++)
                    {
                        int x = i % sideSize;
                        int y = i / sideSize;

                        AddQuad(x, y, 1, 1, i / averageMergableFaces);
                    }
                }
            });


            testSequence.Add(new Test()
            {
                name = "Merged 0D",
                setupTest = (faceCount) =>
                {
                    currentTexture = whitePixel;

                    for(int i = 0; i < faceCount; i++)
                    {
                        int x = i % sideSize;
                        int y = i / sideSize;

                        int width = Math.Min(averageMergableFaces, sideSize-x);
                        AddQuad(x, y, width, 1, i / averageMergableFaces);
                        i = i - 1 + width;
                    }
                }
            });


            testSequence.Add(new Test()
            {
                name = "Merged 1D",
                setupTest = (faceCount) =>
                {
                    currentTexture = oneDeeAtlas;

                    for(int i = 0; i < faceCount; i++)
                    {
                        int x = i % sideSize;
                        int y = i / sideSize;

                        int width = Math.Min(averageMergableFaces, sideSize-x);
                        AddQuad(x, y, width, 1, i / averageMergableFaces);
                        i = i - 1 + width;
                    }
                }
            });


            testSequence.Add(new Test()
            {
                name = "Merged 2D",
                setupTest = (faceCount) =>
                {
                    currentTexture = twoDeeAtlas;

                    for(int i = 0; i < faceCount; i++)
                    {
                        int x = i % sideSize;
                        int y = i / sideSize;

                        int width = Math.Min(averageMergableFaces, sideSize-x);
                        AddQuad(x, y, width, 1, i / averageMergableFaces);
                        i = i - 1 + width;
                    }
                }
            });
        }

        #endregion




        Stopwatch stopwatch = new Stopwatch();

        int frameCounter;
        const int warmupFrames = 100;
        const int testFrames = 400;
        bool warmup;

        const int facesPerTestIncrement = 500;
        int facesInTest = 0;
        const int endTestAtFaces = 100000;

        // This is the number of adjacent faces that could be merged
        const int averageMergableFaces = 4;


        protected override void Update(GameTime gameTime)
        {
            frameCounter++;

            if(warmup)
            {
                if(frameCounter >= warmupFrames)
                {
                    frameCounter = 0;
                    warmup = false;
                    stopwatch.Restart(); // Begin performance test this frame
                }
            }
            else
            {
                if(frameCounter >= testFrames)
                {
                    frameCounter = 0;

                    // End test this frame
                    stopwatch.Stop();
                    FinishTestAdvanceToNext(stopwatch.ElapsedTicks);
                }
            }

            base.Update(gameTime);
        }


        protected override void Draw(GameTime gameTime)
        {
            GraphicsDevice.Clear(Color.CornflowerBlue);


            // Setup camera
            basicEffect.World = Matrix.Identity;
            basicEffect.View = Matrix.Identity;
            basicEffect.Projection = Matrix.CreateOrthographicOffCenter(0, sideSize, 0, sideSize * 0.25f, -1, 1); // cut off 0.25 to simulate hidden faces


            GraphicsDevice.SetVertexBuffer(vertexBuffer);
            GraphicsDevice.Indices = indexBuffer;
            GraphicsDevice.SamplerStates[0] = SamplerState.PointWrap;

            basicEffect.Texture = currentTexture.texture;

            foreach(var pass in basicEffect.CurrentTechnique.Passes)
            {
                pass.Apply();

                GraphicsDevice.DrawIndexedPrimitives(PrimitiveType.TriangleList, 0, 0,
                        vertexCount, 0, indexCount / 3);
            }

            base.Draw(gameTime);
        }
    }
}