UE5 C++Tutorial – Minecraft like Voxel Terrain Generation : Part 4 Greedy Meshing Implementation

Hello and welcome to codeblaze today we will be implementing the greedy meshing algorithm and this is going to be a bit longer video as i want to be as thorough as possible with the explanation so just sit back relax and let’s learn together first of all we’ll get the utility

Methods and the existing code out of the way and much of it you can actually copy from the existing chunk class so for example this constructor this is as it is a copy paste we are doing the same things here also like creating the mesh object the noise object and basically resizing the

Blocks array now the begin play method is again pretty simple all we need to do is call the generate blocks method then we generate the mesh and finally we apply the mesh right and next we can implement the generate blocks and this again you can just copy from the existing class since

The way we use the 2d height map doesn’t change and with this we basically fill in the blocks array depending upon the height map value we either start it to a stone block or an air block and the next existing method would be apply mesh and this also you can copy from the

Existing code the only difference here is now we are using the mesh data variable so rather than passing the triangles and the vertex arrays directly since we would be populating these in the mesh data variable that is the struct we created in the previous video

We will be using that to pass in the vertex data or the mesh data to create mesh section so with this we have our most of the existing code copied over uh we just need to implement a few utility methods so let’s get started with that so the first utility method

We’ll implement is get block index this is again the flattening method we have to convert three-dimensional indexes to one-dimensional index for the blocks array again you can just copy it over then we have this get block this is a new utility method that we have added but

This is also pretty simple all we do is we first check for the bounce so if any of the component of the index is greater than the size we return the air block or if it’s lower than zero we return an air block if that’s not the case we query the blocks

Array using the get block index okay so using this method we would ideally get the correct block wherever required now if you’re building a proper system in the cases of this bounce check you would i ideally want to check the neighboring chunks and return blocks from there that chunks

That way you can have faces curved between the chunks also and finally we need to implement compare mask and this is pretty simple so we just take m1 dot block equal to m2 dot block and m1 dot normal equal to m2 dot normal so we are basically comparing two

Mask values and returning a boolean result so we have all our utility methods done the only thing now left would be the generate mesh and create code and generate mesh is where the bulk of our greedy meshing algorithm will exist and create cord will be internally called to actually fill in

The mesh data areas so let’s get started with that now so the first thing we need to do in 3d meshing is actually iterate over all the three axises since we’ll be generating slices in all three directions now to do that i’ll just have a simple for loop

I’ll call this axis and this will run till three so that will represent the x y and z axis right so just to be clear about what i mean when i say a slice i created the simple illustration in blender so imagine we are iterating along the x-axis

Then a slice would be a perpendicular plane along the y-z-axis right now each of these slices are going to be on integral intervals so that would be the distance of a block and each of the slice would or it may or may not contribute to the final mesh

So there could be slices without any faces or there could be slices with just a single face or a multiple face like or the whole thing could be a face that depends upon the height map values right so all you need to understand here is that slices are nothing

Just planes perpendicular to the current axis direction so back in our for loop now we’ll define some variables uh which are going to be used throughout the greedy meshing stuff the first would be the reference to the perpendicular axises that we can store in constant

This is one so axis one would be nothing but axis plus one mod three right so if the current axis is axis zero this would return the value of one and that way we will be getting the reference to the one of the perpendicular axis and similarly we will have access to also

So this way we know the other two axises for the current axis right next we will store the limits along each axis so that is basically the x y and z components of the size variable that we have so i’ll have pawns in main axis limit

And this we can get from the size variable now these vector variables can be accessed like from an array like syntax so if i put this index axis and if i give a value of 0 that would be the x component but here we want

The value of the main axis so we just pass in this variable so depending upon the axis value we’ll get the limit across that main axis similarly we will store the limit for access 1 and axis 2 also access one limit this would be size axis one and i’ll duplicate this line so

This would be access to limit right i’ll change this to so these limits will be used in our internal for loops basically till when we want to iterate okay next we’ll have two more integer vectors so this would be delta axis x is 1 this should be nothing but nf and vector 0

We will initialize this to the 0 value and similarly we’ll have delta axis too i’ll explain the use of these variables later when they’re coming to point but for now you can basically take them as the growth in the particular direction when we start merging the faces

So they will at the end represent the width and the height of a given face right next we will store another end vector this would be the chunk duration let’s call it chunk idea so this will represent the block blocks that we are iterating through so on all places we’ll basically be

Flattening this specific vector to get the correct block so we can again initialize this to the zero value finally we need an access mask right and again i’ll initialize this 2 and zero value f and with zero value so this mask would represent which axis is active so on

One of its components the x y and z component one of the value would be one so if the main axis we are iterating over the x axis this vector would be one zero zero so again this vector would be useful ahead so it’s better to store it or initialize it here only

Right and as i said it should represent the value of 1 depending upon which axis we are iterating over so we’ll set that using axis mask and i’ll say axis equal to 1. i notice i have a spelling mistake here yep that’s fine i don’t know what i’m thinking about yeah but

Now we’ll continue so finally now the last thing we need to declare is our mask so as i said earlier for each slice we will be creating a mask and that we would be storing in a t array so a t array of type f mask now f mass is a struct

That we declared in our class in the previous video so that is what we want and i’ll just call this mask and we can resize this array since we know the size of the mask and that would be the access limits of the perpendicular axis so

I’ll just call the set num and i’ll pass in axis one limit into axis two limit so again this would be a two dimensional array that we are flattening down to one dimension right and why the size would be access on an access to limit so that is pretty much visible from the

Earlier blender illustration that i showed so that would be the dimensions of the plane or the slice right so with this we have all our variables that we will be requiring but throughout the 3d meshing algorithms defined and next we are going to start with creating the mask for each slice

So now we will be start by trading along the main axis for each slice basically so i’ll just put a comment here nice and this we will do with again a for loop i’ll have a for loop here and this time we will be using the chunk iteration variable

We know that we are going to be trading over the main axis and by storing this iteration values in the chunk iteration variable uh it will be easier for us to access the blocks when required right so in the chunk iteration using the area accessor syntax we’ll say for the main axis

You start with -1 again i’ll explain why we need minus 1 here then you go till chunk iteration along this axis is less than the main axis limit okay and finally we won’t be giving any increment condition here since we’ll be doing that manually ahead

So you can just leave this part empty in the for loop and we’ll just open the brackets so the first thing that we define here is an another variable we’ll just call it n and this would be zero so n will basically represent the index inside the mask and again this would

Require some flattening but since it’s a two dimensional array we don’t need to deal with it much right so now i’ll explain how we’ll go about using the mask so back to this blender illustration if you consider a chunk which has size of three along

X axis as you can see we can have three blocks here between these slices so the number of slices required in that case would be 4 to cover up the whole mesh so in general you can say that the number of slices required is one plus the size

Along that direction right and with those slices you will be able to wrap or basically cover up the whole mesh now if we start the iteration through minus one we can call this slice as slice minus one then the block in this space would be block zero

This would be slice zero then block 1 slice 1 block 2 and finally the slice 2 and with that we’ll have all the slices covered and the mesh generated now for each slice we’ll be creating a mask and mask is nothing but a array and each value in that array

Would represent the block type and normal direction now to create the mask we need to iterate over the perpendicular directions basically we’ll have a nested two nested for loops here again so this would be a for loop and this also we’ll use the chunk iteration but this time we’ll

Go along the axis to for access to equal to 0 and concentration and iteration along access to should be less than the access to limit and finally we can say plus plus chunk iteration along access to right this should be our first loop and similarly i can just

Copy this since we need to do the same along axis one and with these two for loops we are basically iterating along the perpendicular axis so i’ll change this to axis one limit right then again we’ll open the bracket so now that we are iterating along the perpendicular axis we need to get

The current block here so i’ll just call constant current block and this would be equal to so here we’ll use the get block utility method so we will get the bounce check also to get block and we will be directly passing the chunk iteration so this will give us the current block

And finally we need a block along which we need to compare the current block to so that we can get from fonts auto um pair block this will be get block lock this will be chunk iteration chunk here plus the axis mask now by adding the access mask we will be

Getting the adjacent or the neighboring block in that particular direction or the direction along which we are iterating through the main axis now we will store the transparency result of these two blocks in some bowls so cons so this would nothing be but we’ll just compare the current block value to the

Air block value so we’ll take the current block not equal to here e block a so if this is the case then the current block is an opaque block and similarly we need to do the same for the compare block right and now depending upon these boolean values we’ll be filling in the

Mask now to explain though that filling conditions i’ll again go back to the blender illustration so just hang in there so back here in blender if we consider this block to be the current block and if we are iterating along the x-axis so when we add the access

Mask we’ll basically be getting this block here and then we will be storing the transparency values of both the blocks now there can be four conditions possible here if the first would be if both these blocks are opaque blocks or stone blocks in that case we don’t need to do

Anything since the face here in between won’t be visible and similarly if both these blocks are transparent blocks or the air blocks in that case also we don’t need to do anything now if this block here is an opaque block but the block here is a transparent block in that case we

Need to create a face here that faces towards the compare block direction and vice versa is true so if this block here is an opaque block but this block here is a transparent block then we need to create a face that has a normal direction towards the current block

So this is how we’ll basically be filling our mask here and again by seeing the code it will be more clear so back in our code i’ll put an if condition here and i’ll say if the current block opaque is equal to the compare block opaque

So this will take care of both cases when both are true and when both are false so in that case we will fill in the mask here mask and as i said before n is the index through which we are iterating through the mask and

We can just say n plus plus so the value zero will come and then n will increment and i can say this would be f mass and for the block type i can just give it the null block since we had that defined in our enum anyway this is not

Going to be used and the normal direction would be 0 because we just don’t want to show or create a face here so again now we will do an else condition here else if else if the current block is open right but the compare block is not opaque in this case again

We will fill in the mask here with n plus plus this would be f mass f mass right the block type would be the current block type so this would be current block here since we are going to create a face according to the current block

Since that’s the opaque one and for this we’ll say normal direction of one basically if we are creating a phase towards the direction of the compare block we say the normal direction is one and in the else case here else would basically be when the compare block is opaque since that’s the

Only case remaining here again we’ll fill in the mask with n plus plus and this time with the block type would be from pair block and the normal value would be minus one so this value of one n minus one is basically for our own representation you could use some other complementary

Values here if you want right and i’ll just put a comma here right so basically with these two for loops we have filled the mask for the current slice now we’ll need to use this mask value to create the faces or the quads and to do that i’ll do some preparation here

So now we can safely increment the chunk iteration along the main axis if you remember we weren’t doing this here in the main loop you could move there also like with some refactoring i think it should be possible there but this is how i implemented it and since we will need to iterate

Through the mask again to create the quads i’ll set the mask iteration back to zero and i’m pretty sure i could have given it a better name other than n but yeah you could call it mask iteration so the next step that we are going to do is generate mesh from the mask

Okay so that’s the last thing that we need to do and after that we’ll have our algorithm complete so to generate mesh again we need to iterate over the whole mass and to do that we will have two nested for loops and j equal to zero j less than this two limit

And plus press j similarly we’ll have another for loop here for i equal to 0 less than axis one limit and for this internal for loop we don’t need the increment statement here we’ll be controlling it manually inside the loop the first thing you need to do is check

If the current mask value mask n has a normal value of not equal to zero since we need to create this only when the normal value is not equal to zero again normal value of 0 represents if both the blocks are transparent or opaque by doing this

We will be creating quads only when required right so we’ll store the current mask value in our variable i’ll just call it constructo current mass this would be equal to mass n again n is something that we need to iterate our increment inside our loops otherwise we won’t see any effect

And we will apply the i and j values of these loops back to the chunk iteration so now inside these loops this chunk integration will ultimately represent the vertex coordinates for the chord which you’ll see ahead how that happens for now you can just say junk iteration axis one equal to i

Since that is the thing getting over the axis one and axis to equal to j and then we’ll define a variable here called in width so this will represent the width of the current cord or how large it can grow the next step is basically merging of the faces

Or the mask values that have the same value so to find out the width of a current quad we basically need to expand along the axis one and in each step we just need to compare the mask values if they are same we can safely expand if they are different we

Break at that position and we know the maximum possible width for that given phase to do that we will just have a for loop here with width equal to one since one would be the smallest size of the face then we should have i plus width

Less than axis one limit since we don’t need we don’t want to go outside the limits or the outside the chunk our faces should be inside the chunk and along with this condition we need to make sure the mask value is same so we will call the compare mask function here

Compare mask function and to it we would pass the current mask value to which we are iterating that would be mask n plus the width and the second mask value would be the current mask right and finally we can say plus plus and this there would wouldn’t be any

Body in this for loop since we don’t need to do anything all our logic is happening here only so till the current till the mask values are same the width will keep on expanding and as soon as we have something with a different mask value or we hit the limit of the chunk

The this for loop will finish and at the end of this for loop we’ll have the width of the quad or the maximum size the quad can expand and similarly we need to do for the height also and height but the way we are going to do for

Height is we are going to compare the mask values alongside the width so first we will expand in axis 1 then we will check in axis 2 on how far we can go so to do this we’ll need uh two for loops basically nested loops and i’ll store a boolean flag also here

Bool done i’ll initialize this to false right so the first for loop that we are going to have is on height a height equal to 1 again that is the smallest size of the face j plus height should be less than access to limit and plus plus height

Now the reason we need a nested follow because we need to compare the mask values along each of the width on how long we have expanded so again if i show it in blender suppose for this face we have expanded till here now we are going to start expanding along the height

So we need to compare all these four blocks so till all these four blocks also have the same value okay now we can have the squad now if we expand more but this block has a different value so we can’t have a height of 3 so

Our height would be 2 and width would be 4 and that is how we will get those bigger faces and we would basically be merging them so back again here we will have another loop for i and this we can call k okay would go till width only you already

Know the value of width and again we’ll compare here so if compare mask so the current mask value would be mass n plus k like how much width we have gone plus the height into the axis one limit now the reason we need to multiply this is since we have kind of inputting

A two dimensional area index along the width and height so we just need to flatten it down so if we take this mask value and compare it to the current mask and till this is same we can continue okay now if this is not same we just set the done variable to false

And break the inner loop right and in the outer loop we’ll check if done we break the outer loop also this basically means that if at any point we get a mask value which is not comparable or not same to the current mask we break it out

And after these two for loops we have the width and height of the maximum possible quad using the current mask value so all we need to do is store these values in the delta variables so that will make it easier to do vector addition to find out the coordinates

So i’ll say delta axis one x is one equal to width and delta access to this is to equal to height right all now we need to do is create the quad and clear out the mask values that have already been used so just hang on for a bit more and we’ll

Finally have greedy meshing done now we can call the createquad method though we haven’t implemented it but we’ll do that later on we’ll call the create code method the first thing we need to pass in is the mask value that will be current mass then we need to pass in the axis mask

And finally four vectors representing the vertex positions of the chord and the way we are going to do that is uh the first vertex position would basically be chunk idea as i said once we set the ij values to the chunk itr variable this will represent the first vertex coordinate right

And the second coordinate here would be chunk idr so we are basically adding the width to the previous coordinate similarly we will do chunk itr plus delta axis 2 so in this case we have added the height and the final coordinate would be chunk iti plus delta axis one

And plus delta x is two so again this could be explained here in blender so chunk itr would represent this vertex here once we add the width we get this vertex and for the third vertex we had the i so we have this vertex here and when we add both of them

We finally get this fourth final vertex and with this we can create our code so all we need to do is implement this create code and fill in the mesh data now before that i want to complete this function here or generate mesh so after creating the quad we now just

Need to do some cleanup so i can set the delta x is one variable back to f you know zero value so i print vector zero value similarly we will set the delta x is two two also zero so we are basically resetting this and if possible you can actually get rid of

These variables if you refactor it in such a way and directly create your vectors here and finally we need to do is clear of the mask values so since we are iterating outside the current scope like when we do the growth we need to set the mask values that have already been

Consumed so for that we’ll have nested for loop i’ll just copy it over and explain it right this will go in high height and width so using the height and width we’ll set these mask values to null so that would basically mean these masks have already been considered

For creating quads so next time when we iterate over we’ll have the normal value as 0 so the function won’t do anything and finally the most important part we actually need to increment the i value and the end value and that is again pretty simple so i can be incremented by

The grid and that is the amount of values that we have considered across the axis one and n will also be incremented by width since that’s the number of masks we have already considered now we have considered more masks than these like the height masks also but those will be covered by

Setting these to zero so when while iterating the values that have already been considered during the height growth will come so those will have normal zero so it won’t do anything so this will again be width and similarly in the else condition for this upper if

We will increment and i and n by one so else i plus plus and n plus plus right so with this we have completed our generate mesh method so that is all there is for the greedy meshing algorithm so only thing we need to do is implement this createquad method we

Basically use these vertex values to fill in the mesh dot that’s the last thing we do before compiling and testing so just hang on for like few more minutes and this has been dragging along but i want to be as thorough as possible in create quad the first thing we can do

Is compute the normal vector for the given chord and that i’ll just store here const auto normal and this would basically be an f vector of access mask into the mask dot normal right so this would be a vector along the axis so either one of the values would be one x

Y or z and that would be multiplied by mass dot normal so it would be either plus one or minus one right next we need to add the vertex array vertex data so i’ll just copy this we basically call vertices.add four times for all these four vertices and we multiply them by hundred

To scale it according to the unreal engines coordinates next we need to add the triangle data this again i’ll copy now there is a trick that i’m using here so basically the orientation or the order of our triangles should match the normal value and we can get the triangle values using the vertex

Count i have explained this previously also now to make the correct orientation come out we basically use the normal value so if you put in some example values here so let’s assume the vertex count is 0 and the normal value is 1 so we’ll basically be adding 0 3 2

Then this would be 3 0 and this would be two right so if you just iterate or basically put in some example values you’ll see how according to the right hand thumb rule on the left hand like depending upon the coordinate system this will give the correct orientation of the triangles

So again i’ll link down the anatomy of the cube video before because that explains it a much better way than i can ever so yeah with these things you’ll get the correct triangle value so you can just copy this if you want and next we’ll add the uv values so

I’ll set the uv values in the zero channel and i’m deliberately not scaling these uv values since i want to see the uv stretched out as i want to visualize the face is being merged but ideally you will multiply these ones with width and the height so you need to pass in

The width and the height also that we have computed here and basically wherever there is a one here in x-axis we pass in the width and where there is one here in y-axis we pass in the height so this is something i believe you can

Do it on your own and maybe i’ll show it when we actually do some textures here finally we need to add the normal that we computed above and this is just the same value being added four times for each vertex and the next thing we need to do is increment the vertex count

Okay vertex count by four so with this we have all of our implementation part done i’m just now going to try it out there could be any mistakes i have made and maybe you may have already identified those mistakes let’s just hope for the best that this works otherwise

We’ll have some kind of a bug fixing session after this right so let’s see the result now now if you have been exactly following my code you may be getting some weird results since i’m getting that since i’ve just changed the chunk world to spawn my greedy chunks and if i play

I get these weird faces going to the sky and well we all are humans and we make some silly mistakes and the reason for this is if we go back to our code and we see the breaking of our height i had said done to false which it should be true

So with this simple change if i go ahead and recompile you will get everything working correctly even i was well even i didn’t have complete faith in myself that the first time implementation would go correct but yeah these kind of mistakes happens but debugging this could be a nightmare

This is a small change figure out why it isn’t working luckily for me i had implemented this before so i could just compare it with that but if you have already spotted this mistake uh good for you i guess you are more addictive than me

So now that we have fixed that and if i play it we get our proper greedy chunks and since we don’t have we are not scaling our uv values you can see the grid pattern that unreal has in the default material stretching out and that clearly shows the bigger faces

That we are creating again you can just go into the wireframe mode and i’ll hide i’ll come out of this and i’ll hide the idom thing called sky sphere now we can just see the wireframe view of our basically chunks and you can clearly see the bigger faces

Now one thing to note is we are not using the most optimal growth algorithm since we are always checking along the width first and then the height so this is not the most optimal result but it’s good enough and it’s simple enough and you’ll definitely gain a huge

Amount of boost in performance since your vertex count should be around 10 of the original so as i showed earlier in my previous chunk class i was having around 20 000 vertices with greedy meshing it comes down to around 2000 that’s it for greedy meshing and

For this episode also i know it’s it has been a quite a long episode and in the next episodes i am going to show you a new meshing algorithm called marching cubes with that you will be able to create some smooth variants that episode may take a while to create

This matching cube is is something i need to implement myself first not that well versed with it but i’ll definitely get that out not totally not knowing about that so subscribe for the upcoming content if you have any suggestions or feedback leave them down below in the comments and leave a rating

And maybe share with your friend it helps the channel grow so thank you