Optimize Greedy Meshing [WIP]

[Logyrac]

One of the main sources of time for chunk generation currently is the greedy mesher. currently it's a handful of monolithic jobs (one per direction).

I am in the process of a rewrite of the greedy mesher which will split the greedy meshing into multiple smaller jobs for better parallelization. This rewrite of the greedy mesher aims for a few things:

1. Split into multiple stages each with jobs designed to be ran on data in parallel for better job system utilization, and smaller individual jobs to not block important Unity jobs and affecting framerate.
2. Employ binary greedy meshing, using binary representations of the chunks to speed up most operations involved in the greedy meshing and culling steps.
3. Unification of the jobs regardless of direction. Instead of having multiple jobs for different directions employing similar logic, the logic will be laid out in a way that allows it to work for all 6 sides, this will make it easier to maintain as a change to the algorithm doesn't need to be implemented 6 times.
4. Trying to optimize the jobs instructions by optimizing for SIMD and reducing instruction count where possible (ie. instead of calculating an index from x, y and z with multiplication and division, if the loop's are ordered correctly this can be replaced with a single increment operation per loop instead of multiple multiplications and additions)

My hope is the result will be significantly more performant. The bulk of the code is done already, though it's largely untested, so if all goes well PR may be soon, otherwise a bit longer. I wanted to post this issue to let you know that I'm currently working on that area of the engine, in case you were thinking of spending time there as well so potential conflicts and time can be saved.

[BloodyFish]

Wow thanks!
I was just about to start work on this exact issue, so you doing this is a time saver!
Once this is done I will be able to start with infinite chunk generation (using LODs)!

[Logyrac]

This will take slightly longer than expected. Due to the binary nature of the approach it's limited to working on 32 and 64-bit sized chunks realistically, it can technically support any size under 64 but it's relatively wasteful to do so. This means with chunks currently having a height of 2000 poses some issue. To make the binary greedy meshing work the size of chunks would need to be standardized to increments of 64, and vertical height could be broken down into subchunks, similar to how Minecraft handles it. Meaning a subchunk would be 64^3 and a chunk could be 32 subchunks high (or 2048) with empty subchunks not needing to be stored in memory. Alternatively the system could be reworked to support fully 3D chunks, so a chunk would have not just an x and z position by a y position as well and each chunk would be 64^3, the only potential downside here being an increase in number of meshes/objects involved, but it would also mean that less would need to be updated if the chunk data changes, and would allow for theoretically unlimited height.

This would make the greedy meshing possible to do with this approach, but is a moderately substantial rework of the mesh and would involved some reworking of generation as well. I don't wish to start on any work that would be likely to conflict with anything you're actively working on or planning on working on here shortly, so if you have any concerns it'd be great to hear them.

[BloodyFish]

I was going to start infinite generation around the player and then look into LODs. Would that conflict with anything you are doing?

[Logyrac]

LODs will fundamentally require working with the meshing so LOD would definitely conflict. The meshing actually will have support for LOD when it's working. I guess it depends on how you want to handle LODs. This meshing rework is likely going to require changes to nearly every part of the engine, so it might be best to get those changes in first:

1. It's nice to support variable sized chunks but realistically it adds major complexity to deal with later and makes it hard to optimize for, so the chunks should probably be standardized to some power-of-2 size, since they're currently 64x64x2000 I'd propose 64.
2. Due to this the height of chunks wouldn't be able to be 2000, the chunks could be reworked one of two ways:
   • Have chunks only have X and Z positions but make them out of smaller 64-block-high sections, basically a subchunk system. This would make chunks still have a capped height but could be implemented in a way where it doesn't require changes to generation.
   • Have chunks have X, Y and Z positions and be 64^3. This would require reworking generation a bit but wouldn't have a cap on height.
3. Since we need the chunk data in a NativeArray for meshing, it may be nicer to generated directly into a NativeArray instead of a managed byte[]. If we do the subchunk system since the Y axis for coordinates is the largest contributor to index, these subchunks would each have their own range within the larger allocated block for the chunk, as such we could use NativeSlice for the generation.
4. Chunks are currently stored/tracked based on in-world position, which is a bit confusing, it may be better to store them based on their chunk location instread, not chunk location in-world (multiplied by chunk size and block size) but by the chunk's index, (0,1), (0,2), etc. And provide methods for converting to/from chunk positions to world positions ad etc.

Would like to hear your thoughts/opinions on these as this is your project.

[BloodyFish]

If you want I can get started on 2 and 4? I was going to work on chunk location fixes, and I already implemented sub chunking in an older version of the engine. So if you want I can work on implementing sub chunks as well.
Could you explain point 3?

I also want to thank you for your contributions. You have been extremely helpful and I have learned a lot form reading your code!

[Logyrac]

No problem, honestly I've been coding more this past week than the last several months, just kinda got back into the voxel mood and this repo felt like a good place to do some stuff with. If you wish to work on 2 and 4 by all means! I'll leave it to you whether you think having chunks with subchunks is better or worse than having fully cubic chunks.

As for point number 3, you have a byte[] called blocksArray1D that stores the data for the chunk, then when meshing you copy that data over to a NativeArray to send to the job. Since NativeArrays act mostly the same as arrays in C# normally it might be more efficient to use a NativeArray instead of the byte[] and directly set the blocks in the NativeArray<byte> instead of the byte[]. Another advantage of doing so is that byte[] isn't Burst-compatible, even with primitive types like byte in C# arrays are a managed type, meaning they are controlled by the GC and other internal memory management stuff, as such they can't be used in Burst, whereas NativeArray is a wrapped for a simple allocated region of memory outside the control of the GC and such is why you must manually manage freeing the memory via Dispose. Burst only allows a subset of C# that can be compiled to highly-optimized native code, since Burst-compiled code more resembles the type of code you'd make with a language like C it can't take advantage of data managed by the C# runtime. From the C# side NativeArrays work just about the same, you can index into them for getting and setting. Since for the meshing jobs the block array is ReadOnly we could just store the block data directly in the chunk as a NativeArray and pass that to the job. Having the chunk data directly in a NativeArray also opens the possibility to make the chunk generation Burst-compiled as long as the noise generation and other stuff it uses can also be Burst compatible.

Having said that one potential issue is that because the meshing occurs on a worker thread, it's possible the data in the native array could be modified in the middle of meshing, so perhaps it's not a good idea after all.

I will put the meshing on a slight pause for now until point 2 is finished, there's aspects of it I can work on until then.

[BloodyFish]

Great! I will let you know when I get around to that! I am a bit busy as school just started, so I’ll let you know when subchunks are implemented.

[Logyrac]

I could also implement them if you'd prefer, I just don't want to barge into this repo and suddenly change everything.

[BloodyFish]

Okay, I implemented sub-meshing!
It is much faster now.

[Logyrac]

@BloodyFish Alright, I've been pulling in your changes though I've made some fairly major reworks to parts of it as needed for the mesher, in specific:

1. I am Jobifying the generation as well.
2. To which end I have made the Spline and Noise classes Burst compatible.
3. I've refactored generation and meshing to separate classes which implement two interfaces IChunkGenerator and IChunkMesher
4. To make better use of the job system the jobs are made as IJobParallelFor where a seperate instance of the job is used for each direction/type pairing, In other words the jobs are broken up into far more much smaller pieces, so they can be better load balanced by Unity and take better advantage of the Job system.

I'm almost ready to test the system fully and see whether it's working, so maybe another day or so, but it contains some significant changes to Chunk, Generation, VoxelManager and more.

I already had a binary greedy mesher sitting around I made before, but it didn't support multiple voxel types because I stored the voxel type in a 3D texture and uploaded it to the GPU and fetched it in the fragment shader. This takes more GPU memory but did allow the mesh to greedy-mesh all solid voxels instead of only ones of same type. It was also designed around 32^3 chunks, reworking it to work with multiple types and 64^3 chunks has proven to be more difficult than I expected, but a fun project so far, and I learned about NativeStream today which I didn't know about, very useful in my case for combining the vertices from jobs for types and directions.

As the changes are pretty large each commit you make takes some time to fix merge conflicts (not complaining, I knew I'd have that issue when I started working on this), but once I'm done with testing and am working to finish a few things up I may request a brief pause for finalizing it before submitting the PR. Not just for my benefit of less merge conflicts to solve but also because I don't want to possibly invalidate work you put in. For the meantime no worries though.

[BloodyFish]

Sound great! I can’t wait to see what you’ve been working on; I’ve learned so much from your work! I won’t add anything new in the meantime to avoid any more conflicts.

[Logyrac]

Well I'm actually running into a lot of problems, so many Burst errors. For example Unity telling me that a NativeArray in a job is marked as [ReadOnly] but that I'm writing to it, when in-fact no, I am not writing to it, only reading. I even removed the [ReadOnly] attribute and it still gives me the error. Many issues like that that are driving me slightly insane, never had these issues before with Burst/Jobs. Haven't used jobs this extensively for a while so there must have been some pretty major changes in recent versions. I currently have no ETA, so if you wish to do stuff feel free for the time being, just if a change requires a substantial rework of something that one may be best to wait, but if you wanted to work on other aspects of it like player characters walking around on it or loading/unloading chunks as the player moves those shouldn't theoretically conflict, just probably avoid LOD work for now as that will directly conflict.

[BloodyFish]

Got it! I'll work on player stuff, and I also wanted to prioritize some other noise/generation fixes. Would that conflict?

[Logyrac]

Noise stuff might conflict as I made some changes to the noise generator to be Burst compatible, but I don't think it would be too difficult to work any changes you make in, I'll leave it up to you.

[BloodyFish]

All right,
I started work to give terrain some more variation by blending blocks into each other.

    public void GenerateChunk()
    {
        SetBlockArray();
        if(Random.Range(0, 2) == 1) RandomizeBlocks();
        isGenerated = true;
    }
    public void SetBlockArray()
    {
        float blockSize = Generation.BLOCK_SIZE;

        for(int i = 0; i < CHUNK_WIDTH * CHUNK_LENGTH; i++)
        {
            // i % 16 gives you the x coordinate, which cycles from 0 --> 15.
            // i / 16 gives you the z coordinate, which increases every 16 steps.

            // Position in 3D array
            int x = i % CHUNK_WIDTH;
            int z = i / CHUNK_WIDTH;

            // World position
            float xCoord = (x * blockSize) + chunkPos.x;
            float zCoord = (z * blockSize) + chunkPos.z;

            float contentalness = Generation.GetContenentalness(xCoord, zCoord);

            float slope = new float();
            int yVal = (int)Mathf.Ceil(Generation.instance.continentalnessToHeight_spline.EvaluateAtPoint(contentalness, 100 / blockSize, out slope));
            //Debug.Log(slope);

            for (int y = 0; y < CHUNK_HEIGHT; y++)
            {
                // Our chunk position assumes are blocks are 1 by one (by default our blocks are 1/4th the size of a normal block
                // So our 64 by 64 chunk of 1/4 sized voxels is equal to a 16 by 16 sized chunks of 1 by 1 voxel. 
                // We divide by blockSize (0.25) to find the actual y position of the voxel
                float yCoord = y + (chunkPos.y / blockSize);

                if (yCoord > yVal) { break; }

                int blockIndex = CalculateBlockIndex(x, y, z);
                if (slope > 3f)
                {
                    blockArray1D[blockIndex] = (byte)(Generation.instance.stoneBlock.block_ID + 1);

                }
                else
                {

                    if (yCoord <= 20 / blockSize)
                    {
                        blockArray1D[blockIndex] = (byte)(Generation.instance.underwaterBlock.block_ID + 1);

                    }
                    else if (yCoord == yVal)
                    {
                        blockArray1D[blockIndex] = (byte)(Generation.instance.mainBlock.block_ID + 1);

                    }
                    else
                    {
                        blockArray1D[blockIndex] = (byte)(Generation.instance.dirtBlock.block_ID + 1);

                    }
                }

                containsVoxel = true;

                
            }
        }
    }

    public void RandomizeBlocks()
    {
        Debug.Log("Test");

        byte[] originalBlocks = blockArray1D.ToArray();

        for (int i = 0; i < CHUNK_WIDTH * CHUNK_LENGTH; i++)
        {
            // i % 16 gives you the x coordinate, which cycles from 0 --> 15.
            // i / 16 gives you the z coordinate, which increases every 16 steps.

            // Position in 3D array
            int x = i % CHUNK_WIDTH;
            int z = i / CHUNK_WIDTH;

            Debug.Log("Checkpoint one");

            for (int y = 0; y < CHUNK_HEIGHT; y++)
            {
                int blockIndex = CalculateBlockIndex(x, y, z);

                // Give a certain chance to become the same type as a nearby voxel:
                if (Random.Range(0, 2) == 1)
                {
                    Vector3Int UP = new Vector3Int(0, 1, 0);
                    Vector3Int DOWN = new Vector3Int(0, -1, 0);
                    Vector3Int RIGHT = new Vector3Int(1, 0, 0);
                    Vector3Int LEFT = new Vector3Int(-1, 0, 0);
                    Vector3Int FORWARD = new Vector3Int(0, 0, 1);
                    Vector3Int BACK = new Vector3Int(0, 0, -1);

                    List<Vector3Int> possibleDirections = new List<Vector3Int>();

                    if (x < CHUNK_WIDTH - 1)
                    {
                        if (blockArray1D[CalculateBlockIndex(x + 1, y, z)] > 0) { possibleDirections.Add(RIGHT); }
                    }
                    if (x > 0)
                    {
                        if (blockArray1D[CalculateBlockIndex(x - 1, y, z)] > 0) { possibleDirections.Add(LEFT); }
                    }
                    if (y < CHUNK_HEIGHT - 1)
                    {
                        if (blockArray1D[CalculateBlockIndex(x, y + 1, z)] > 0) { possibleDirections.Add(UP); }
                    }
                    if (y > 0)
                    {
                        if (blockArray1D[CalculateBlockIndex(x, y - 1, z)] > 0) { possibleDirections.Add(DOWN); }
                    }

                    if (z < CHUNK_LENGTH - 1)
                    {
                        if (blockArray1D[CalculateBlockIndex(x, y, z + 1)] > 0) { possibleDirections.Add(FORWARD); }
                    }
                    if (z > 0)
                    {
                        if (blockArray1D[CalculateBlockIndex(x, y, z - 1)] > 0) { possibleDirections.Add(BACK); }
                    }

                    Debug.Log(possibleDirections.Count);
                    // Pick random direction
                    if (possibleDirections.Count > 0)
                    {
                        Vector3Int chosenDirection = possibleDirections[Random.Range(0, possibleDirections.Count)];
                        blockArray1D[blockIndex] = blockArray1D[CalculateBlockIndex(x + chosenDirection.x, y + chosenDirection.y, z + chosenDirection.z)];
                    }
                }
            }

        }
   
    }

Strangely, in the block

    public void GenerateChunk()
    {
        SetBlockArray();
        if(Random.Range(0, 2) == 1) RandomizeBlocks();
        isGenerated = true;
    }

RandomizeBlocks() is never called once. Not only this, but nothing generates at all when the line if(Random.Range(0, 2) == 1) RandomizeBlocks(); is added/