this might be one of the world's fastest binary greedy measures This Be Real it's probably not but it's it's really fast it is so blazingly fast that it probably puts your cold measure to shame that's how fast it is BL F Rusty baby today I'm going to share with you my journey in making one of the most optimized greedy measures you can probably do he going to get technical we're going to use spe twice manipulations it's going to be super interesting so let's jump right into it here we can see my old cold measure compar
that to my new fancy greed measure it generates quite a lot more triangles as you can see with the specific shape ofin the green measure generates about half the vertices that's great we just half the data to send to the GPU and half the amount of vertices we need to render of course the less noisy terrain we have the better theg the measure can reduce the triangle count so the benefit varies quite a lot but overall green maing always produce less vertices so it's great there's only one potential problem with green maching though and that
is that it's slow than using a cold measure or is it are you sure about that here's a benchmark of my first attempt at a greedy measure it takes on average 8 milliseconds to create a single chunk mesh compar that to my cold measure it only takes 0.6 millisecs greedy meching is 13 times slower here but let's be real for a second you can probably ship G with any of these measures our meshing needs are highly context dependent if you're constantly breaking blocks a c measure might be preferable you might take the Middle Road and
Implement a simplified greedy measure that is fast but not as space efficient as a full greedy measure here's an article of some people using that approach if you rarely break any blocks it doesn't actually matter if a greedy measure is slower so just use a greedy measure in that case you can also take a habid approach and use both of the meshing algorithms to get both speed and the data optimization but that greatly over complicates things and you need to rebuild meeses quite a lot more it doesn't sound like a good idea to be of
course the performance also changes depending on our voxal features do you use texturing do you bake ambient occlusion do you have lighting data there's not a simple answer to what measure is the best the only way to find out is to experiment with our specific setup and that I did when I first saw my greedy Mion performance I wasn't sure what to think of it this application I built is very minimal so we don't know if it's fast enough for our needs but as saw an opportunity if the greedy measure is equally fast as a
cold measure we would always used a greedy measure of course this was my first attempt at a greedy measure I'm sure there's space for optimization so the question is how much faster can I make this greedy measure well here is the result of me spending a full week optimizing it and managing to make it faster than the cold measure yes I somehow managed to make my greed measure faster than my cold measure now that sounds impossible it's insanely fast now I'm going to show you exactly how I did it buckle up first of all we
need to understand how grid D machine works so let's start with the visual representation imagine we are meshing top down one slice of a Shunk just the top part let's walk through the algorithm to see how these quads are formed we start at 0 and we first ask what block type are we working with here in this case grass now we have a 1ex one quad but we can grow this so we take a look on the voxel above and check if it's the same voxel type it's a grass block they are the same type
so we grow the quad's height we keep growing vertically until we hit a different block type in this case we hit an AIR block and we cannot grow this quad anymore we can however grow this horizontally as you can see we can only grow horizontally if all the blocks to the right are of the same type we see that all of the next ones are grass so that is okay we can grow it horizontally but in the next iteration all of the boxels aren't grass our quad cannot grow anymore so it's done we then advance
to the next location and we're not meshing any air blocks so we jump up to the next solid block then we try to grow that quad using the same method we have resolved all the Y coordinates on the first row so in the next iteration we jump to the next row and keep trying to go but as you can see this block has already been included in the first quad that is why we have to clear out the data for the quots we have previously mesed so as the algorithm goes the data we are working
with will eventually clear [Music] out taada it's a mesh you can imagine that every step in our algorithm we are probably indexing into some sort of array that holds our boxal data of course computers are really fast and indexing into an array of hundreds of thousands of times might not be a big deal but what if I told you we can figure out the height of her quad in a single operation no jumping around shaking boxes every now and then in some sort of loop we can figure out the height in a single operation we
are going to turn this into a binary problem binary solo 1 but first we need to rethink the data structure instead of having all of the block types in the same grid first we'll separate out the different block types into their own grid all the blocks in this plane is of the grass type and all of the blocks in this plane is the dirt type seeing as we know that all the types in this grid is grass we can represent the voxal as a Boolean false means there is no grass block true means there is
a grass block now better yet Boolean can be represented with a single bit and you can fit 32 booleans into a single 32bit integer instead of using a two-dimensional array we now have a flat array and every single element in our array holds data for the entire row it looks something like this in code now we finally get to see the incredible benefit we get from rethinking the data structure because we will now figure out the size of the quads using blazingly fast bitwise manipulations let's finally take a look at some code this function returns
a vector of quads and the data we are working with is of course our binary grid plane we're going to step through this code and visualize it at the same time so here we go we start at the bottom left corner at row Z and the y z first we need to find the first foxel that we need to make a quad out of to do that we need to count all of the air blocks because there might be air blocks before we reach our first foxel we will count the trailing Sero bits in this
example the first solid block is three units up we count three trailing Sero bits now we have our y position to calculate the height of our quad well we count all of the trailing positive bits it's a single operation and this function is incredibly fast so we now they have the heights now we want to grow horizontally so I construct the mosque of the Heights I'm not going to explain this in detail these are just basic bitwise calculations if you want you can pause the video and read my explanation here so we have a mosque
of the height it looks something just like this in binary so now we get the same area of bits in the next row and if all of the bits are the same that means we can grow into it as you can see here's the equal check and if they're not the same we want to break out of this Loop and that means this quad is done but in this case they are equal so we continue down into this part of the code now it's incredibly important here that we remove all of the bits that we
expand into in this case these ones turns into zeros if we don't the next iterations when we reach this row we might try to make a quad out of voxels that we have already bed that is the entire binary greedy meshing algorithm for a single slice of a chunk that is I understand this part can be pretty hard to follow along but I suspect many people watching this aren't making a greedy measure but if you are you should of course initialize this step by step to get a deeper understanding what is interesting about this code
is that we have just figured out all the quads we need and this function is incredibly fast blink and it's done all thanks to bitwise manipulations now let's zoom out a bit we have only seen how to make a single slice of a chunk the complete meshing algorithm had to make 32 slices per axis we make 32 slices facing left we make 32 slices facing right so forth here's the actual real Ming function that I'm calling this is a version without ambient occlusion because that complicates things a little bit in my explanation anyway this function
returns a shank mesh chunk mesh is just a list of vertices basically and as you can see I have separated out the creation of every single axis this line creates all the vertices facing up this line creates all the vertices facing down if I disable some of these as you can see there are gaps in the world now so what does this function actually do vertices from phas no AO of course we use the binary greeding machine function we just looked at but let's jump up to the start of this function first we Loop the
axis we Traverse in this case 32 times I have level of detail implemented here so some parts of the algorithms use different values but I won't dive into the details of that here here is where I construct the binary grid plane and of course we make different ones for every block type we iterate all the values in our binary plane and we need to fill out the voxal data as binary so we need to fetch our Vel data the tricky mindbending part here is that where we sample our Vel changes depend depending on what face
Direction We Are constructing if we make the up and down faces of course the axis we Traverse is on the y coordinate but the left and right faces we construct of course revers on the x-axis by this point we have the current voxel for the binary Grid at this row and this column but here we also retrieve the voxel from the previous axis we do not want to make quads for voxels that are inside the Shan we only want to Mees the face if the current foxel is solid and the previous foxel is air this
is called face coing if the face isn't C we will set the binary grid plane voxal bits to be true all of this code is just constructing the binary grid plane data of course using face cooling all that is left to do now is to construct the quads using our blazingly fast greedy measure function that is the entire greedy missing function skipping a little bit of details and the funny part is this is the slow greedy measure I showed you at the start the 8 millisecond per Shunk version the slow part of this algorithm is
right here constructing the binary PL data we are now going to see how we can make this 40 times faster and I needed to show you this slow version before I show you the blazingly fast version because things are about to get a lot more complicated and a lot more faster let's think about what we're doing here why is this code so slow well first of all this function is called six times for every face Direction then we Loop 32 times on the axis we then Loop for every single block type and I only have
three block types right now but when we add more block types the greedy measure will become slower that's a big problem right there we then Loop the binary grade on the X and Y AIS 32 * 32 times and the thing to note inside of this Loop we are sampling voxal data from our Shunk two times let's add the numbers up in this case we are sampling our Shunk data 1.1 million times for a single mesh if we had 10 block types instead of three we would be sampling boxels almost 4 million times just to
create a single mesh worst of all this function doesn't have ambient occlusion implemented so you can take this number times 27 or so if you're using ambient occlusion this is the root of the problem and we can get this number down to 39,000 we will only sample voxel data one time per voxel technically it's not true that's the best case scenario but it is substantially less and this sampling reduction alone is how we'll get a 40 times faster algorithm what I'm about to show you is one of the world's fastest binary greedy measures that that
I'm aware of so yeah you know here it [Music] is imagine if I ended the video right there you know what maybe I should have because this is one of the hardest things in the world to explain simply I'm going to try here we are this function constructs a Shunk mesh no surprise there our goal is to only sample voxels one sing single time that's what's going on right here interestingly we are sampling 32x 32x 32 times this chunk size includes a padding of two that's why I call it chunk size P it includes the
padding our algorithm requires adjacent Shunk data because to create the outer face of a Shunk we need to ensure that the neighbor outside of our chunk is an AIR block that's why we have a padding of one on each foxal side okay let's take a look back on the slow measure the most important knowledge we need from sampling the VX Sals is what blocks are solid and do they have an air Block in the previous axis we need to know what faces are called and which are not these are booleans yes we're going there time
to rethink this face calling part entirely so stick with me for a moment as a scramble your mind forget about binary and code for a moment let's take a breather and go to the drawing board imagine we are making this Shunk for Simplicity sake this is a 4x4 Shunk now imagine we are constructing the faces looking to the left where would the left looking faces be well right here as you you can see it makes sense these are the faces looking to the left now the reason we don't make a face here is because it
lies outside of our Chunk we still need the neighboring chunk data but we can only make faces inside of our Shunk now I want you to visualize where the faces would be that are facing right I will give it 2 seconds to think the right looking faces will be right here visually this makes sense nothing weird about it but why how do we reason about it well this solid block is facing an AIR block going back on the axis we are traversing same goes over here this block however has a solid touching solid so we
place no face over there to find our faces we only care about data lying in the same axis this is not worthy now let's visualize this as a binary grid once again we don't care right now what the block type is we only care if the block is solid or not knowing now that face cooling only cares about the same axis we can lay out the binary data like so this is now a flat array with integers now I want to show you how we can find this faces using bitwise manipulations let's just focus on
this column let's do some bitwise obervations to see how we can transform this data to find the cold faces first of all let's copy this column now let's bit shift this to the right now let's reverse all the bits ones become zeros zeros becomes ones and let's finally add the original row and this modified one together and this is the result what does these values mean well if we now overlay this data your notice something interesting the positive bits indicates where a face would go of course this foxel lies outside of our chunk so this
bit will be ignored in the future if we want to find the right looking faces we instead bit shift to the left here's what that looks like we copy the column bit shift to the left we flip the bits and finally end the original with our modified one and Bam there is our faces looking right we just calculated where the faces are just modifying an integer I encourage you to visualize this with different setups and you'll see it works every single time we can do face cing incredibly fast okay let's get back to the code
our goal now is to construct this spary grid I just showed you as you saw the faces looking left and right can use the same column data we just shift them differently to make the up or down faces we can use the same axis and to use the forward and back axis we can use the same grid we need to construct three different binary grids that we can face call and those grids are constructed right here the tricky part about this code is that I place all the three grids in a flat array so the
math is a little bit of a mess to give you some insight let me just show you how this data is actually laid out in memory chunk siiz padding times 2 is the amount of elements we need to make a 2d grid this is a 34x 34 grid so to get three grids into a flat array this is the amount of elements we need to skip to jump to the three different grids that's the memory layout that is why we index differently right here for the current voxel we are sampling this voxel has different coordinates
on these three axises this is the hardest thing to explain but I will attempt to if we construct the binary grid for the up and down phases of course we are traversing the y axis now the current voxels x and z position is the row and column and the Y position is the bit location if we construct the grid for the left and right faces AKA traversing the x-axis the current voel z and y position is the row and column and the X position is the bit location that is the idea behind this indexing and
this is really hard wrapping my mind around all of these coordinates took me a really long time to understand we can now do our face calling as you saw previously we use the same column to calculate both ascending and descending phes and that is what we're doing right here just as I showed you first we bit shift the column to the right one time we flip the bits we then end it together with the original column now we know where every single uncalled face is in this Shunk congratulations we just went over one of the
hardest things in this video probably Let's uh look on some boxels for a moment before we dive back in boxels our goal now is to find all the unold faces we us calculated and put them into our binary greedy measure algorithm we know the locations of the faces we've been working with binary now but we need to figure out what greedy plane does this phase belong to is it a dirt block is a grass block so let's jump into the code to see how all of this works so we iterate all the axises both ascending
and descending now we iterate 32x 32 times the x and z position here are the coordinates of the binary grid we get the face called column we is calculated from this x and z position and calculating the index for that is not very pretty you can pause to read my explanation there now right here I do some bit twice manipulations to clear the last and first bit of our column because these bits represents the voxel laying outside of our chunk the padding we don't want to make faces out of those we now have the column
data cleaned up and this is a integer we were working with we want to find all of the face locations we already have the x and z position what is missing is the y-coordinate and the Y coordinates of the faces is their bit location and we can find the first phase by calculating the trailing zeroed bits the Y position of this phase is two it has two trailing Sero bits we then clear out this positive bit these three lines will essentially go through all the face locations in this integer now we have the XY and
Z position of the face to get the true boxel position however we need to transform this data based on the axis we are traversing we are going to skip this part of the code because it calculates ambient occlusion which unfortunately is out of the scope of this video so ignore that for now since we now have the true boxal position we fetch the actual boxal data so we can get the block type so we can separate out different block types into different binary greedy planes I actually combined the block type and ambient occlusion as a
hash key just as you can't merge different block types together you cannot merge different ambient occlusion values and here I address a problem with the previous algorithm remember how the iteration time increased for every block type we had well instead of iterating all of the block types instead we get the block type and has it as a key into a hash map when all the faces are processed and put into the correct greedy plane we can finally call our binary greedy measure with different block types and different ambient inclusions I apologize if I went a
little bit fostter in the end I've been working on this video for a really long time but I hope at least the core ideas about this algorithm has been well presented let's do a quick overview here to summarize why this greedy measure is so fast we sample boxels one time up front and for every axis the Solid box get a binary representation and here is something really cool about this this code alone takes on average 62% of the execution time constructing this Vector takes on average 22% of the execution time and sampling the voxal data
into these three binary gdes take 40% of the execution time the actual greedy missing algorithm is faster than just generating the data how fascinating is that we calculate all the faces using bitwise manipulations and look at that execution time it's not even noticeable that we are calling this we then extract all the phase locations with sample our chunk data one additional time for every phase to get the block type actually we sample nine additional more times per phase if we include ambient occlusion it's not a huge deal but maybe there is some potential to optimize
the ambient occlusion sampling I don't know we finally calculate the quots using this blazingly fast binary greedy measure I have open sourced this entire boxal engine project I do not plan to make a public library for this greedy measure because foxal engines are pretty specific in features and data types and I personally want to use a specific measure designed to run my voxal engine but the source code is deer and if you if you want you can extract parts from it here are some really cool findings I made building this I sent this project to
my friend and he ran my benchmarks he has a way more powerful CPU than me I think mine is like 15 years old or something like that and this is just a few years old but amazingly the binary reg greedent measure ran equally fast on my PC as it did on his but the cold measure which isn't hyper optimized code was faster on his computer this was confusing shouldn't new CPUs generally run code faster well this is the only explanation I've been able to find it seems like bitwise manipulations and trailing zeros are already so
incredibly fast CPU operations that the speed difference in modern CPUs compared to old ones you won't actually see any big difference in performance how cool is that I am justified in using a really old CPU he he he wait a minute pause the video I just showed you an old Benchmark as I've been updating this function it's gotten faster and now there is a slight performance difference in my friends execution time compared to to mine but still the difference isn't that big why did I improve the code after editing this video oh man something else
interesting to note is that the majority of this algorithm is just doing face calling if we remove the Lost binary greeding machine part we can just make a regular cold measure that is incredibly optimized but why would you do that greedy meshing is probably worth it if it is this fast finally I'm want to talk about how I learned how to build this because I haven't found any videos articles guides on how this works well I mainly used two resources this video by Davis Morley taught me how B grey algorithms works it is the First
Resource that greedy machine finally clicked for me now the binary face cooling I learned from the C++ repository for a binary greedy measure and I would not have understood anything about this code unless I hadn't made my first slow attempt at a greedy measure I dissected this code line by line not understanding everything but as I visualized things with binary it finally clicked how all of this comes together it is not easy to find resources like this on box engine development so I hope this video can be a good resource for other developers wanting to
learn how to do binary machine blazingly fast [Music] thank you very thank you very
