Part 4

The comment box above is an empty container where our greedy meshing algorithm will run before we create the mesh section. I'm giving myself a little bit of room to think, since this is going to be... pretty complicated.

I could simplify my data structures quite a bit before running any any more algorithms. I don't need to create all these vertices, UVs, triangles and whatnot before creating my mesh. A long time ago I created a struct called QuadFace for this very purpose. It's a small, simple struct that contains a vector and an enum called Direction, which can be Top, Bottom, Left, Right, Front, or Back.

Back where I created a Quad, with all its vertex information, I will instead create a QuadFace struct and add it to a new array. I'm trying to reduce redundancy as much as I can, since updating a chunk right now causes a very slight frame spike, which means we are going to have to optimize like crazy.

That leaves the majority of the CreateQuad as temporarily dead code, but I'm going to have to reference some of the techniques I used in here, and Git does not play nicely with Blueprints, so we will leave it for later reference.

Fully wired up now, the CreateQuad method looks like this. I imagine this will save us some serious calculation time moving forward with this algorithm.

I'm going to rename it to CreateBlockFace, because I'm not actually creating a quad any more. I'm just creating a virtual representation of one.

To the left is maybe the most important method in the whole algorithm, CheckAll6SidesDoesAirBlockExist. This is the one that takes my voxel location, and if it neighbors and air block, I will create a face on that side. I wanted to leave this function alone, but I ran into a problem.

This was one of the more expensive methods, but it must be called once per voxel. Trouble it, I was actually calling it 6 times per voxel. Every time the branch (if statement) was run, it was doing this logic. Since the if statement was being run 6 times, it was checking on the block six times.

I'm starting to think that much of the optimization that will have to happen in this project will be making sure things that are meant to be done only once, are done once.

My first rough pass at the greedy meshing algorithm looks something like this. For now I'm only trying to figure out how to mesh a single strip.

I'm not worried about UV's or anything else right now either.

I'm quite concerned about how I can increase performance with remeshing a chunk, since players are going to be updating them all the time, and there will also be more than one block type! For now I'm getting 120 FPS, thank God! This may also run a bit faster in-game without all the editor overhead.

That said, I may end up having to do some sort of hybrid HISM/chunking solution. I know for a fact I can quickly place an HISM or static mesh, and then perhaps I could in the background update the chunk every now and then. The main reason I need these chunks is for efficient replication. That would be a working compromise, but a desperate one.

Now I need to update UVs for this quad. Drawing triangles is largely unchanged since it only relates to the integers used to reference the vertices' indexes. We only need to generate UVs for a single strip of our greedy meshing algorithm at this point.

Easier said than done.

So, in the time it's taken to implement the bones of the algorithm for a single strip of quad faces along the bottom of the left side, I've re-evaluated how I should do the scanning portion of this algorithm. It would be a great many fewer iterations if I kicked off the algorithm by sorting my QuadFaces into groups based on their face directions, and then running the greedy meshing quad generation algorithm based on that newly sorted array.

UE4 doesn't have an array sort node, so we will have to implement a sorting algorithm... in Blueprints only! (⌐■_■) I'm almost glad they didn't, because it's going to have to be hella fast. We have 4096 blocks and who-knows-how-many chunks to sort through, any time we update a Chunk. There are a couple neat things we can do to optimize this:

  • We know for sure that a given face will only have one Side. The first thing we can do is group like faces into new arrays. This will only take one iteration.

  • We don't actually need to sort, since we are always going to start scanning in the same direction. We just need to find the lowest value on the respective axes we are using before we start meshing. This means that we will only need to iterate through the array once, and once each through the 6 resultant sub-arrays. (per face)

  • Crazy idea--we will remove the face from our array once a mesh is occupying its vertices, further reducing the number of elements each iteration of our meshing algorithm needs to run per-update.

The grouping portion of our 'sorting' algorithm

This code finds the min value for a particular group (everything is now grouped by its face normal direction)

This is the code that crawls along a row. We will crawl vertically by calling this on each row. That's why we made it into a function.

Are you ready?