Part 2

Much of the content in the next few parts has been adapted from these fantastic blogs:
https://0fps.net/2012/06/30/meshing-in-a-minecraft-game/
https://www.gedge.ca/dev/2014/08/17/greedy-voxel-meshing

Apologies for the length of the content below (and in general), I wanted to document what I tried, what worked and what did not. In software development, many things we try don't always work and we have to try another way. Sometimes we have to think a bit outside the box. I hope sharing my process is as valuable to you as it is to me.

Note! In Unreal Engine, Z-axis is UP! Not Y-axis, like I'm used to.

Unreal Engine currently does not allow replication of Maps, which would be a much more convenient data type for me to use. I'm forced to replicate an array of structs. The struct I created is called BlockLocationType and the resultant array is called BlockLocationTypeArray.

These are my voxels, and I'm storing them in 16x16x16 Chunks. A LevelManager holds references to a collection of Chunks, and each Chunk keeps the aforementioned array of BlockLocationType.

How do I efficiently create meshes based on my voxel data that is now being replicated?

(above code is an unfinished idea, a spark to get the mind going!)

Challenges:

  • We don't have multidimensional arrays, just a single array of our struct. How will we "scan" in various directions?

  • How can we make sure we aren't spending any energy calculating meshes for faces that should be culled, or for voxel coordinates that are not even blocks? (air blocks)

Much thanks to 0fps.net for the inspiration and starting point to implement this! (images to the left from 0fps.net's article)

In my first attempt, I implemented culling with Hierarchical Instanced Static Meshes (HISMs), and that would have probably been enough for this project if HISMs could replicate reliably, or delete without doing expensive collision checks. Since they don't, I have no choice but to implement procedural meshes. And, since I'm using ProceduralMeshComponents, I have no choice but to implement greedy meshing if I want the map to hold a reasonable framerate.

The coolest thing I noticed in the 0fps.net article is that this complicated 3D problem can be reconstructed as a 2D problem if we consider cross sections 'slices' of vertices in each direction. However, we first need to create a procedural mesh that we can apply this cool idea to.

First, we need a working ProceduralMeshComponent.

Add a ProceduralMesh to the 16x16x16 Chunk actor.

It will have a method called UpdateMesh, which will be our entry point for all greedy meshing logic to come. The method UpdateMesh will take in as an argument the parent Chunk's BlockLocationTypeArray.

From this array of vectors, we then have to create some sort of 3D Matrix that we can then break into 2D components.

We will go through each BlockLocationType in BlockLocationTypeArray and add to a new set of IntVectors called Vertices, its vector location. After this, we will also add one more row, column, and whatever the Z-axis thing is, since our blocks start at the bottom-left-front, and we need those extra positions to get the top-right-back positions of our outermost top-right-back blocks.

I'm starting every cube at (0, 0, 0). All my math moving forward will be calculated in units of 100, which is the size of my cubes in Unreal Engine units. Note that for some reason in Unreal the X axis, in red, is represented with a negative vector direction, pointing to the left for some reason.

As I move along, I'm going to have to figure out an order in which I want to draw the triangles. That means I need to consistently define my vertices either clockwise or counter clockwise. I think shaders calculate the normals of triangles based on that. For now, I'm not going to worry about it.

The basic techniques I'm using to create this cube will be expanded upon when it comes time to make our more complicated meshes using the Greedy Meshing algorithm.

Soon, I will be defining my quads in terms of their min and max points in 2D space, which will be on various axes. To keep things unified, I will describe the two extrema in terms of (s0, t0) and (s1, t1) which I believe is what the (s, t) in the formula on the next page refers to. Hope I'm right! 😁 I may not have to describe each face, then, if I use st0 and st1 effectively, but I am not ready to think about that at this point in the process.

For now, I'm just going to use Root Location and increment +100 in each direction for each vertex point on every face.

But you can imagine that with 6 different faces to account for, this will get rather spaghetti rather quickly! I could either try to be really clever and come up with some neat way to pass in inputs, but for now I'm going to just make one method for each face in the enumeration. That method, though, will take in an IntVector location. All six of these quads I am creating will make a cube. Once the cube is made, I can start thinking about how to greedy mesh my voxel array. These methods I'm creating will likely be thrown away, but I need to implement this for my own understanding before moving on to the more complicated implementation.

After breaking each into its own method and a little cleanup... Looking good! 👀

This will make it much easier to conceptualize what it is I'm about to have to do.

Also, if I need to reorder indices, I can do so via flipping the yellow vector wires around where I make the array per side. That will make it easy to fix any normal direction issues that pop up later.

Now I have the bones for my method that will create a quad face. It's not compiling though, since I still need to specify triangles. I'll need to do UV's next, but I won't be able to see anything until I specify the triangles. I think I'll do that per quad, and add that to each of my 6 created functions, so I have fine grain control over the normal direction, like I mentioned before.Triangles are created based on the indices of the previously created vertices.

An easy way to achieve this is with the node called ConvertQuadToTriangles. I first created a local array of integers, with the indices [0, 1, 2, 3]. Before anything else happens in the method, my Triangles buffer is already valid and ready to go, though I may need to fiddle with the aforementioned yellow wires to get the direction facing the right way. The array this created probably looks something like [0, 1, 2, 2, 1, 3]. It's really nice not having to deal with this myself, though I'm wondering why it modifies an existing array buffer and doesn't just create a new one. 🤷‍♂️

My procedural mesh is still sad that it doesn't exist in the game world. What's missing now?

Not sure yet, but one thing I need to make sure to do is give the newly created mesh section its own index. I can do this like so:

After setting this little property called AutoActivate on the ProceduralMesh component to true, I can now see the quad face when I click 'Play' or 'Simulation.'


Progress! Let's go ahead and throw on some basic UV coordinates and a material.

I'll go ahead and set the material right before I create the quad face.

Add all six sides of the cube. This is temporary!

Cool! The material is being set, but there are obviously a couple things wrong.

The UV's are missing, which means that this is a solid color instead of our dirt texture.

Also, some triangles are not displaying correctly. That means I'll have to go fumble with the vertices, the yellow vector connections I mentioned earlier.

The missing UV problem is easy. All it takes is throwing on some UV's that match the order of the vertices. This also makes it easier to see what's going on with our triangles' orientations.

The problem on the right is caused by setting the wrong vertex location, it means you placed a vertex on the wrong point (not on the same plane as the quad you are intending to create.)

This may be caused by confusing the y-axis and the z-axis. Unreal defines its axes differently than most 3D software I'm used to.

Here is the final code I ended up using for generating face. This is temporary, and things are going to get much more complicated so I'm going to try to break things into nodes and classes where I can.

This particular caused me a lot of pain and it's worth mentioning in a bit more depth. Unreal engine seems to do things completely backwards when it comes to definitions of axes. Have they heard of the right hand rule at Epic Games? It feels like every axis is oriented in the wrong direction. I think a significant portion of the difficulties I have run into on this project can be attributed this. Sorry, I just had to get that off my chest.

Here's some finished code you can zoom around and take a look at, and a .gif of the finished block.

Sweet.